Privately Releasing Conjunctions and the Statistical Query Barrier

Details Privately Releasing Conjunctions and the Statistical Query Barrier Privately Releasing Conjunctions and the Statistical Query Barrier

2010-11-04

arxiv.org/abs/1011.1296v4

Computer Science

Data Structures and Algorithms

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Privately Releasing Conjunctions and the Statistical Query Barrier does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Privately Releasing Conjunctions and the Statistical Query Barrier, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Privately Releasing Conjunctions and the Statistical Query Barrier will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-453218