Privately Releasing Conjunctions and the Statistical Query Barrier
Speaker: Aaron Roth , MSR New England and UPenn
Date: May 17 2011
Time: 4:15PM to 5:15PM
Location: 32-155
Host: Scott Aaronson, CSAIL, MIT
Contact: Be Blackburn , 3-6098, imbe@mit.edu
Relevant URL: 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 isup to polynomial factorsequal 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 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.
This talk is based on joint work with Anupam Gupta, Moritz Hardt, and
Jon Ullman.
See other events that are part of Theory Colloquium 2010/2011
See other events happening in May 2011
