Faster private release of marginals on small databases

Karthekeyan Chandrasekaran, Justin Thaler, Jonathan Ullman, Andrew Wan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We study the problem of answering k-way marginal queries on a database D ∈ ({0,1}d)n, while preserving differential privacy. The answer to a k-way marginal query is the fraction of the database's records x ∈ {0,1}d with a given value in each of a given set of up to k columns. Marginal queries enable a rich class of statistical analyses on a dataset, and designing efficient algorithms for privately answering marginal queries has been identified as an important open problem in private data analysis. For any k, we give a differentially private online algorithm that runs in time poly (n, 2°(d)) per query and answers any sequence of poly (n) many k-way marginal queries with error at most ±0.01 on every query, provided n ≳ d0.51. To the best of our knowledge, this is the first algorithm capable of privately answering marginal queries with a non-trivial worst-case accuracy guarantee for databases containing poly(d, k) records in time exp(o(d)). Our algorithm runs the private multiplicative weights algorithm (Hardt and Rothblum, FOCS '10) on a new approximate polynomial representation of the database. We derive our representation for the database by approximating the OR function restricted to low Hamming weight inputs using low-degree polynomials with coefficients of bounded L1-norm. In doing so, we show new upper and lower bounds on the degree of such polynomials, which may be of independent approximation-theoretic interest.

Original languageEnglish (US)
Title of host publicationITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science
PublisherAssociation for Computing Machinery
Pages387-401
Number of pages15
ISBN (Print)9781450322430
DOIs
StatePublished - 2014
Externally publishedYes
Event2014 5th Conference on Innovations in Theoretical Computer Science, ITCS 2014 - Princeton, NJ, United States
Duration: Jan 12 2014Jan 14 2014

Publication series

NameITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science

Conference

Conference2014 5th Conference on Innovations in Theoretical Computer Science, ITCS 2014
Country/TerritoryUnited States
CityPrinceton, NJ
Period1/12/141/14/14

ASJC Scopus subject areas

  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'Faster private release of marginals on small databases'. Together they form a unique fingerprint.

Cite this