# Algorithmic Stability for Adaptive Data Analysis

arXiv: https://arxiv.org/abs/1511.02513 · HTML: https://mlsanity.com/paper/1511.02513/

## Key facts

- Cited by 88 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Nov 2015.

## Built on by (most cited first, 30 of 88)

- [Unlocking High-Accuracy Differentially Private Image Classification through Scale](https://mlsanity.com/paper/2204.13650/) (2022)
- [Adaptive Machine Unlearning](https://mlsanity.com/paper/2106.04378/) (2021)
- [Machine Unlearning via Algorithmic Stability](https://mlsanity.com/paper/2102.13179/) (2021)
- [Privacy Auditing with One (1) Training Run](https://mlsanity.com/paper/2305.08846/) (2023)
- [Hyperparameter Tuning with Renyi Differential Privacy](https://mlsanity.com/paper/2110.03620/) (2021)
- [Learning with User-Level Privacy](https://mlsanity.com/paper/2102.11845/) (2021)
- [Non-Euclidean Differentially Private Stochastic Convex Optimization: Optimal Rates in Linear Time](https://mlsanity.com/paper/2103.01278/) (2021)
- [Information-theoretic generalization bounds for black-box learning algorithms](https://mlsanity.com/paper/2110.01584/) (2021)
- [Low-Degree Multicalibration](https://mlsanity.com/paper/2203.01255/) (2022)
- [Reproducibility in Learning](https://mlsanity.com/paper/2201.08430/) (2022)
- [Stability is Stable: Connections between Replicability, Privacy, and Adaptive Generalization](https://mlsanity.com/paper/2303.12921/) (2023)
- [Leveraging Public Data for Practical Private Query Release](https://mlsanity.com/paper/2102.08598/) (2021)
- [A Unifying Perspective on Multi-Calibration: Game Dynamics for Multi-Objective Learning](https://mlsanity.com/paper/2302.10863/) (2023)
- [Causal Imitation Learning under Temporally Correlated Noise](https://mlsanity.com/paper/2202.01312/) (2022)
- [An Algorithmic Framework for Bias Bounties](https://mlsanity.com/paper/2201.10408/) (2022)
- [On the Privacy Properties of GAN-generated Samples](https://mlsanity.com/paper/2206.01349/) (2022)
- [Statistical Indistinguishability of Learning Algorithms](https://mlsanity.com/paper/2305.14311/) (2023)
- [Estimating informativeness of samples with Smooth Unique Information](https://mlsanity.com/paper/2101.06640/) (2021)
- [Generalization Bounds for Noisy Iterative Algorithms Using Properties of Additive Noise Channels](https://mlsanity.com/paper/2102.02976/) (2021)
- [Unifying Re-Identification, Attribute Inference, and Data Reconstruction Risks in Differential Privacy](https://mlsanity.com/paper/2507.06969/) (2025)
- [Information Complexity and Generalization Bounds](https://mlsanity.com/paper/2105.01747/) (2021)
- [Reconciling Individual Probability Forecasts](https://mlsanity.com/paper/2209.01687/) (2022)
- [Multicalibrated Regression for Downstream Fairness](https://mlsanity.com/paper/2209.07312/) (2022)
- [Stability and Generalization for Markov Chain Stochastic Gradient Methods](https://mlsanity.com/paper/2209.08005/) (2022)
- [List and Certificate Complexities in Replicable Learning](https://mlsanity.com/paper/2304.02240/) (2023)
- [On the power of adaptivity in statistical adversaries](https://mlsanity.com/paper/2111.10352/) (2021)
- [A Bias-Accuracy-Privacy Trilemma for Statistical Estimation](https://mlsanity.com/paper/2301.13334/) (2023)
- [What You See is What You Get: Principled Deep Learning via Distributional Generalization](https://mlsanity.com/paper/2204.03230/) (2022)
- [How Spurious Features Are Memorized: Precise Analysis for Random and NTK Features](https://mlsanity.com/paper/2305.12100/) (2023)
- [Differentially Private Coordinate Descent for Composite Empirical Risk Minimization](https://mlsanity.com/paper/2110.11688/) (2021)

## Abstract (arXiv)

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 the 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: (i) 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). (ii) 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. 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 stability implies low generalization error. We also study weaker stability guarantees such as bounded KL divergence and total variation distance.