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 the first algorithm that efficiently releases differentially private answers to of all Boolean conjunctions with 1 average error. This presents significant 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.
There are also several conditional lower bounds on the running time of private mechanisms for solving the query release problem. @cite_23 showed that under cryptographic assumptions, there exists a class of queries that can be privately released using the inefficient mechanism of @cite_21 , but cannot be privately released by any mechanism that runs in time polynomial in the dimension of the data universe (e.g. @math , when the data universe is @math ). Ullman and Vadhan @cite_26 extended this result to the class of conjunctions: they showed that under cryptographic assumptions, no polynomial time mechanism can answer even the set of @math conjunctions of two-literals!
@cite_21 @cite_23 @cite_26
2169570643 86647242
We demonstrate that, ignoring computational constraints, it is possible to release privacy-preserving databases that are useful for all queries over a discretized domain from any given concept class with polynomial VC-dimension. We show a new lower bound for releasing databases that are useful for halfspace queries over a continuous domain. Despite this, we give a privacy-preserving polynomial time algorithm that releases information useful for all halfspace queries, for a slightly relaxed definition of usefulness. Inspired by learning theory, we introduce a new notion of data privacy, which we call distributional privacy, and show that it is strictly stronger than the prevailing privacy notion, differential privacy. Assuming the existence of one-way functions, we show that there is no polynomial-time, dierentially private algorithm A that takes a database D2 (f0; 1g d ) n and outputs a database" ^ D all of whose two-way marginals are approximately equal to those of D. (A two-way marginal is the fraction of database rows x2f0; 1g d with a given pair of values in a given pair of columns.) This answers a question of (PODS ‘07), who gave an algorithm running in time poly(n; 2 d ). Our proof combines a construction of hard-to-sanitize databases based on digital signatures (by , STOC ‘09) with encodings based on the PCP Theorem. We also present both negative and positive results for generating " synthetic data, where the fraction of rows in D satisfying a predicate c are estimated by applying c to each row of ^ D and aggregating the results in some way.