On the Generalization Properties of Differential Privacy

By Kobbi Nissim, Uri Stemmer. 2015

39 citations recorded by the source corpus.

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).

Subfields: Artificial Intelligence, Sociology and Political Science, Safety, Robustness & Interpretability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Sociology and Political Science

In Safety, Robustness & Interpretability

Citations in the corpus

MixMatch: A Holistic Approach to Semi-Supervised Learning (2019, background): “For this reason, learning with differential privacy is, in practice, a form of regularization [33].”
On the Intrinsic Privacy of Stochastic Gradient Descent (2019, background): “In these cases, and in much work studying SGD, the focus is on understanding the generalisation properties of the algorithm, however the links between general notions of stability, privacy, and generalisation have already been established [7], [22], [36].”
Generalization Bounds for Uniformly Stable Algorithms (2018, methodology): “Our approach to proving the high-probability generalization bounds is based on the technique introduced by Nissim and Stemmer [NS15] (see [Bas+16]) to show that differentially private algorithm have strong generalization properties.”
Generalization in Adaptive Data Analysis and Holdout Reuse (2015, methodology): “Using results from [7, 14] we show that for datasets consisting of i.”
Online Learning via the Differential Privacy Lens (2017, unknown): “For example, the DP lens has been used successfully in designing coalition-proof mechanisms [25] and preventing false discovery in statistical analysis [10, 13, 17, 28].”