Faster Algorithms for Privately Releasing Marginals

By Justin Thaler, Jonathan Ullman, Salil P. Vadhan. 2012

103 citations recorded by the source corpus.

We study the problem of releasing k-way marginals of a database D∈({0, 1}d)n, while preserving differential privacy. The answer to a k-way marginal query is the fraction of D'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 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 ±.01 error on every query as long as $n \geq 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Θ(k) (for k≪d).

Subfields: Artificial Intelligence, Computational Theory and Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Marginal Release Under Local Differential Privacy (2017, background): “The use of Hadamard transform for mate-rializing marginals was considered by early work in the centralized differential privacy model, but has fallen from favor in the centralized model, supplanted by more involved privacy mechanisms [7, 19, 34].”
Fingerprinting codes and the price of approximate differential privacy (2013, neutral): “A is (ε, δ)-differentially private if for every two adjacent databases D ∼ D′ and every subset S ⊆ R, Pr [A(D) ∈ S] ≤ eε Pr[A(D′) ∈ S] + δ.”
Private Multiplicative Weights Beyond Linear Queries (2014, background): “In the setting of counting queries, such algorithms are known for special cases such as interval queries [4] and marginal queries [16, 20, 28, 7, 13].”
Collect at Once, Use Effectively: Making Non-interactive Locally Private Learning Possible (2017, unknown): “(Thaler et al., 2012) employed polynomials for marginal queries.”
Answering Multi-Dimensional Analytical Queries under Local Differential Privacy (2019, background): “, multiplicative weights [19–21], Chebyshev polynomials [33], maximum entropy estimation [27], and sampling [7].”
How to Use Heuristics for Differential Privacy (2018, background): “Since then, a number of algorithms and hardness re-sults have been given [UV10, GHRU13, KRSU10, TUV12, HRS12, FK14, CTUW14].”
The Complexity of Differential Privacy (2017, unknown): “5 (Marginals via low-degree approximation [102]).”
Empirical Risk Minimization in Non-interactive Local Differential Privacy Revisited (2018, methodology): “The polynomial approximation approach has been used under central model in [1, 25, 21, 26] and the dimension reduction has been used in local model in [2, 26].”