Faster Algorithms for Privately Releasing Marginals

Abstract

We study the problem of releasing $k$-way marginals of a database $D\in (\{0,1{\}}^d{)}^n$, while preserving differential privacy. The answer to a $k$-way marginal query is the fraction of $D$'s records $x\in \{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 of a dataset, and designing efficient algorithms for privately releasing marginal queries has been identified as an important open problem in private data analysis (cf. Barak et. al., PODS '07). We give an algorithm that runs in time $d^{O(\sqrt{k})}$ and releases a private summary capable of answering any $k$-way marginal query with at most $\pm .01$ error on every query as long as $n\ge d^{O(\sqrt{k})}$. To our knowledge, ours is the first algorithm capable of privately releasing marginal queries with non-trivial worst-case accuracy guarantees in time substantially smaller than the number of $k$-way marginal queries, which is $d^{\Theta (k)}$ (for $k\ll d$).

Cited by in corpus (12)

• Collect at Once, Use Effectively: Making Non-interactive Locally Private Learning Possible
• Faster Private Release of Marginals on Small Databases
• Efficient Algorithms for Privately Releasing Marginals via Convex Relaxations
• Learning Coverage Functions and Private Release of Marginals
• Fingerprinting Codes and the Price of Approximate Differential Privacy
• Answering n^{2+o(1)} Counting Queries with Differential Privacy is Hard
• Dual Polynomials for Collision and Element Distinctness
• Space Lower Bounds for Itemset Frequency Sketches
• Private Multiplicative Weights Beyond Linear Queries
• Marginal Release Under Local Differential Privacy
• Strong Hardness of Privacy from Weak Traitor Tracing
• Order-Revealing Encryption and the Hardness of Private Learning