Privately releasing conjunctions and the statistical query barrier

By Anupam Gupta, Moritz Hardt, Aaron Roth, Jonathan Ullman. 2010

149 citations recorded by the source corpus.

Suppose we would like to know all answers to a set of statistical queries C on a data set up to small error, but we can only access the data itself using statistical queries. A trivial solution is to exhaustively ask all queries in C. Can we do any better? We show that the number of statistical queries necessary and sufficient for this task is---up to polynomial factors---equal to the agnostic learning complexity of C in Kearns' statistical query (SQ)model. This gives a complete answer to the question when running time is not a concern. We then show that the problem can be solved efficiently (allowing arbitrary error on a small fraction of queries) whenever the answers to C can be described by a submodular function. This includes many natural concept classes, such as graph cuts and Boolean disjunctions and conjunctions. While interesting from a learning theoretic point of view, our main applications are in privacy-preserving data analysis: Here, our second result leads to an algorithm that efficiently releases differentially private answers to all Boolean conjunctions with 1% average error. This presents progress on a key open problem in privacy-preserving data analysis. Our first result on the other hand gives unconditional lower bounds on any differentially private algorithm that admits a (potentially non-privacy-preserving) implementation using only statistical queries. Not only our algorithms, but also most known private algorithms can be implemented using only statistical queries, and hence are constrained by these lower bounds. Our result therefore isolates the complexity of agnostic learning in the SQ-model as a new barrier in the design of differentially private algorithms.

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, methodology): “Several approaches use the multiplicative weight update method to iteratively pick an output distribution [19, 20, 18].”
Distributed Private Heavy Hitters (2012, background): “There has been little work in this more restrictive model–the problems of learning [KLN + 08] and query release [GHRU11] in the local model are well understood 1 , but only up to polynomial factors that do not imply tight bounds for the heavy hitters problem.”
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] + δ.”
A Simple and Practical Algorithm for Differentially Private Data Release (2010, background): “If A and B are distributions over the domain D of records, where A is a synthetic distribution intended to approximate a true distribution B with respect to query q , then the Mul-tiplicative Weights update rule recommends updating the weight A places on each record x by: The proportionality sign in”
Private Learning and Sanitization: Pure vs. Approximate Differential Privacy (2013, background): “[18] have given reductions in both directions between agnostic learning of a concept class C, and the sanitization task for the same class C.”
The Johnson-Lindenstrauss Transform Itself Preserves Differential Privacy (2012, background): “Other mechanisms for preserving differential privacy include the Exponential Mechanism of McSherry and Talwar [25], [5]; the recent Multiplicative Weights mechanism of Hardt and Rothblum [19] and its various extensions [17], [14], [15]; the Median Mechanism [28] and a boosting mechanism of Dwork et ”
Private Multiplicative Weights Beyond Linear Queries (2014, methodology): “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].”
Simultaneous Private Learning of Multiple Concepts (2015, background): “In terms of sample complexity, it is known that private learning (for the case k = 1) is an easier task than data sanitization, and several reductions from private learning to data sanitization were given in [19, 5, 6].”
The power of localization for efficiently learning linear separators with noise (2013, background): “…more broadly, problems of noisy learning are related to seminal results in approximation-hardness [1, 27], cryptographic assumptions [14, 39], and are connected to other classic questions in learning theory (e.g., learning DNF formulas [34]), and appear as barriers in differential privacy [26].”
Answering n{2+o(1)} counting queries with differential privacy is hard (2012, background): “As we mentioned earlier, there has also been considerable interest, and some success, in constructing efficient sanitizers for very simple classes of counting queries such as conjunctions [11, 15, 19], decision lists [19], and halfspaces [2].”
Faster Algorithms for Privately Releasing Marginals (2012, methodology): “A recent series of works [11, 4, 15] have shown how to privately release answers to k -way marginal queries with small average error (over various distributions on the queries) with both running time and minimum database size much smaller than d k (e.g. d O (1) for product distributions [11, 4] and…”
Sample Complexity Bounds for Differentially Private Learning (2011, background): “More work on this line includes Roth (2010) and Gupta et al. (2011).”
Iterative Constructions and Private Data Release (2011, methodology): “It also generalizes the offline multiplicative weights mechanism [12, 14].”
Heavy Hitter Estimation over Set-Valued Data with Local Differential Privacy (2016, background): “Local differential privacy (LDP) [22, 14] is a data collection framework based on -differential privacy [10].”
The power of factorization mechanisms in local and central differential privacy (2019, background): “Then for every k ≤ d ∈ N and ε, α smaller than an absolute constant, Marginal queries have been extremely well studied in diﬀerential privacy [BCD + 07, KRSU10, GHRU11, HRS12, TUV12, CTUW14, DNT15].”