On the Generalization Properties of Differential Privacy

Understand

A new line of work, started with Dwork et al., studies the task of answering statistical queries using a sample and relates the problem to the concept of differential privacy.

• By the Hoeffding bound, a sample of size $O(\log k/\alpha^2)$ suffices to answer $k$ non-adaptive queries within error $\alpha$, where the answers are computed by evaluating the statistical queries on the sample.
• This argument fails when the queries are chosen adaptively (and can hence depend on the sample).
• Dwork et al.