On the Generalization Properties of Differential Privacy

Abstract

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. showed that if the answers are computed with $(\epsilon ,\delta )$-differential privacy then $O(\epsilon )$ accuracy is guaranteed with probability $1-O({\delta }^{\epsilon })$. Using the Private Multiplicative Weights mechanism, they concluded that the sample size can still grow polylogarithmically with the $k$. Very recently, Bassily et al. presented an improved bound and showed that (a variant of) the private multiplicative weights algorithm can answer $k$ adaptively chosen statistical queries using sample complexity that grows logarithmically in $k$. However, their results no longer hold for every differentially private algorithm, and require modifying the private multiplicative weights algorithm in order to obtain their high probability bounds. We greatly simplify the results of Dwork et al. and improve on the bound by showing that differential privacy guarantees $O(\epsilon )$ accuracy with probability $1-O(\delta \log (1/\epsilon )/\epsilon )$. It would be tempting to guess that an $(\epsilon ,\delta )$-differentially private computation should guarantee $O(\epsilon )$ accuracy with probability $1-O(\delta )$. However, we show that this is not the case, and that our bound is tight (up to logarithmic factors).

This paper was merged with another manuscript and is now subsumed by arXiv:1511.02513

References in corpus (1)

• More General Queries and Less Generalization Error in Adaptive Data Analysis

Cited by in corpus (12)

• MixMatch: A Holistic Approach to Semi-Supervised Learning
• Train faster, generalize better: Stability of stochastic gradient descent
• Generalization in Adaptive Data Analysis and Holdout Reuse
• Towards Formalizing the GDPR's Notion of Singling Out
• The Ladder: A Reliable Leaderboard for Machine Learning Competitions
• Comparative Study of Differentially Private Data Synthesis Methods
• Recent advances in deep learning theory
• Stability and Generalization of Learning Algorithms that Converge to Global Optima
• Chasing Your Long Tails: Differentially Private Prediction in Health Care Settings
• Tighter Generalization Bounds for Iterative Differentially Private Learning Algorithms
• The Everlasting Database: Statistical Validity at a Fair Price
• An Empirical Study on the Intrinsic Privacy of SGD