[Busec] Fwd: Theory Seminar today at 3:00 - Moritz Hardt (MSR and Princeton)

Sharon Goldberg goldbe at cs.bu.edu
Fri Apr 1 14:58:13 EDT 2011


---------- Forwarded message ----------
From: Steve Homer <homer at cs.bu.edu>
Date: Fri, Apr 1, 2011 at 1:11 PM
Subject: Theory Seminar today at 3:00 - Moritz Hardt (MSR and Princeton)
To: Steve Homer <homer at cs.bu.edu>

       Boston University -- Computer Science Department

                Friday Theory Seminar

           Moritz Hardt on April 1, 3:00

On Friday, March 25 at 3:00, Moritz Hardt
will speak on,

"Privately Releasing Conjunctions and the Statistical Query Barrier."

The talk is in MCS 137 at 111 Cummington Street.
Note: This is the seminar room next to our usual room (MCS 135).


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 makes progress on an important 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.

Joint work with Anupam Gupta, Aaron Roth and Jon Ullman.

Sharon Goldberg
Computer Science, Boston University

More information about the Busec mailing list