Algorithmic stability for adaptive data analysis

By Raef Bassily, Kobbi Nissim, Adam D. Smith, Thomas Steinke, Uri Stemmer, Jonathan Ullman. 2015

304 citations recorded by the source corpus.

Adaptivity is an important feature of data analysis - the choice of questions to ask about a dataset often depends on previous interactions with the same dataset. However, statistical validity is typically studied in a nonadaptive model, where all questions are specified before the dataset is drawn. Recent work by Dwork et al. (STOC, 2015) and Hardt and Ullman (FOCS, 2014) initiated a general formal study of this problem, and gave the first upper and lower bounds on the achievable generalization error for adaptive data analysis. Specifically, suppose there is an unknown distribution P and a set of n independent samples x is drawn from P. We seek an algorithm that, given x as input, accurately answers a sequence of adaptively chosen ``queries'' about the unknown distribution P. How many samples n must we draw from the distribution, as a function of the type of queries, the number of queries, and the desired level of accuracy? In this work we make two new contributions towards resolving this question: We give upper bounds on the number of samples n that are needed to answer statistical queries. The bounds improve and simplify the work of Dwork et al. (STOC, 2015), and have been applied in subsequent work by those authors (Science, 2015; NIPS, 2015). We prove the first upper bounds on the number of samples required to answer more general families of queries. These include arbitrary low-sensitivity queries and an important class of optimization queries (alternatively, risk minimization queries). As in Dwork et al., our algorithms are based on a connection with algorithmic stability in the form of differential privacy. We extend their work by giving a quantitatively optimal, more general, and simpler proof of their main theorem that the stability notion guaranteed by differential privacy implies low generalization error. We also show that weaker stability guarantees such as bounded KL divergence and total variation distance lead to correspondingly weaker generalization guarantees.

Subfields: Artificial Intelligence, Computer Networks and Communications, Management Science and Operations Research, Statistical Learning Theory

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 Computer Networks and Communications

In Management Science and Operations Research

In Statistical Learning Theory

Citations in the corpus

Certified Robustness to Adversarial Examples with Differential Privacy (2018, background): “Previous work studies generalization properties of DP [4].”
The power of synergy in differential privacy: Combining a small curator with local randomizers (2019, methodology): “Dwork et al. [24] and Bassily et al. [7] showed that if a hypothesis h is the result of a di ﬀ er-entially private computation on a random sample, then the empirical error of h and its generalization error are guaranteed to be close.”
The structure of optimal private tests for simple hypotheses (2018, background): “For hypothesis tests with constant error probabilities, sample complexity bounds for differential privacy are equivalent, up to constant factors, to sample complexity bounds for other notions of distributional algorithmic stability, such as (ε,δ )-DP [31], concentrated DP [14, 34], KL- and TV-stabil”
Differential Privacy for Growing Databases (2018, methodology): “We ﬁrst show that our new public histogram update rule bounds this relative entropy increase (Lemma 15), and then show that the bound on the number of hard queries does not suﬀer too much relative to the static setting (Corollary 16).”
Heavy Hitters and the Structure of Local Privacy (2017, background): “The motivation for studying max-information comes from its ability to ensure generalization in adaptive data analysis [3, 9, 10, 32].”
Calibration for the (Computationally-Identifiable) Masses (2017, methodology): “Theorem 3.9 follows from tailoring the proof of the main “transfer” theorem of [BNS + 16] (Theorem 3.4) speciﬁcally to the requirements of our guess-and-check oracle and applying the diﬀerentially private mechanism described in Theorem 3.8.”
Private selection from private candidates (2018, background): “A beautiful recent line of work [2, 9] shows that when these analyses take the form of low-sensitivity queries, using differentially private versions of these analyses allows us to improve the sample complexity quadratically over what would otherwise be possible.”
Learning with Differential Privacy: Stability, Learnability and the Sufficiency and Necessity of ERM Principle (2015, background): “Dwork et al. (2015b) is part of an independent line of work (Hardt & Ullman, 2014; Bassily et al., 2015; Dwork et al., 2015a; Blum & Hardt, 2015) on adaptive data analysis, which also 1For instance, Frank McSherry described in a blog post an example of exploiting differential privacy for measure…”
The Unintended Consequences of Overfitting: Training Data Inference Attacks (2017, result): “algorithm with a suitably chosen parameter generalizes well with high probability. Subsequent work showed that similar results are true under related notions of privacy. In particular, Bassily et al. [18] studied a notion of privacy called total variation stability and proved good generalization wit”
White-box vs Black-box: Bayes Optimal Strategies for Membership Inference (2019, background): “In the context of differential privacy (Dwork et al., 2006), recent works (Wang et al., 2016; Bassily et al., 2016) suggest that guaranteeing privacy requires learning systems to generalize well, i.e. , to not overﬁt.”
Entropy-SGD optimizes the prior of a PAC-Bayes bound: Data-dependent PAC-Bayes priors via differential privacy (2017, background): “…of Entropy-SGLD rests on results in differential privacy (see (Dwork, 2008) for a survey) and its connection to generalization (Dwork et al., 2015b; Dwork et al., 2015a; Bassily et al., 2016; Oneto, Ridella, and Anguita, 2017), which can be viewed as a particularly stringent notion of stability.”