Privately releasing conjunctions and the statistical query barrier

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.

Authors

• Anupam Gupta 0001
• Moritz Hardt
• Aaron Roth 0001
• Jonathan R. Ullman

Keywords

• agnostic learning
• differential privacy
• submodular functions