# Generalization in Adaptive Data Analysis and Holdout Reuse

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

## Key facts

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

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

- [Adaptive Machine Unlearning](https://mlsanity.com/paper/2106.04378/) (2021)
- [Privacy Auditing with One (1) Training Run](https://mlsanity.com/paper/2305.08846/) (2023)
- [Information-Theoretic Generalization Bounds for Stochastic Gradient Descent](https://mlsanity.com/paper/2102.00931/) (2021)
- [Non-Euclidean Differentially Private Stochastic Convex Optimization: Optimal Rates in Linear Time](https://mlsanity.com/paper/2103.01278/) (2021)
- [Reproducibility in Learning](https://mlsanity.com/paper/2201.08430/) (2022)
- [Tighter expected generalization error bounds via Wasserstein distance](https://mlsanity.com/paper/2101.09315/) (2021)
- [Enhancing Adversarial Training with Second-Order Statistics of Weights](https://mlsanity.com/paper/2203.06020/) (2022)
- [Stability is Stable: Connections between Replicability, Privacy, and Adaptive Generalization](https://mlsanity.com/paper/2303.12921/) (2023)
- [Differentially Private Decoding in Large Language Models](https://mlsanity.com/paper/2205.13621/) (2022)
- [On the Generalization of Models Trained with SGD: Information-Theoretic Bounds and Implications](https://mlsanity.com/paper/2110.03128/) (2021)
- [RepLiQA: A Question-Answering Dataset for Benchmarking LLMs on Unseen Reference Content](https://mlsanity.com/paper/2406.11811/) (2024)
- [An Algorithmic Framework for Bias Bounties](https://mlsanity.com/paper/2201.10408/) (2022)
- [HappyMap: A Generalized Multi-calibration Method](https://mlsanity.com/paper/2303.04379/) (2023)
- [Understanding Generalization via Leave-One-Out Conditional Mutual Information](https://mlsanity.com/paper/2206.14800/) (2022)
- [A Survey on Machine Unlearning: Techniques and New Emerged Privacy Risks](https://mlsanity.com/paper/2406.06186/) (2024)
- [Information Complexity and Generalization Bounds](https://mlsanity.com/paper/2105.01747/) (2021)
- [Reconciling Individual Probability Forecasts](https://mlsanity.com/paper/2209.01687/) (2022)
- [The Benchmarking Epistemology: Validity Theory for Evaluating Machine Learning Models](https://mlsanity.com/paper/2510.23191/) (2025)
- [What You See is What You Get: Principled Deep Learning via Distributional Generalization](https://mlsanity.com/paper/2204.03230/) (2022)
- [Valid Inference After Causal Discovery](https://mlsanity.com/paper/2208.05949/) (2022)
- [Adaptive Data Analysis with Correlated Observations](https://mlsanity.com/paper/2201.08704/) (2022)
- [On Differential Privacy and Adaptive Data Analysis with Bounded Space](https://mlsanity.com/paper/2302.05707/) (2023)
- [Subsampling Suffices for Adaptive Data Analysis](https://mlsanity.com/paper/2302.08661/) (2023)
- [An Analysis on Ensemble Learning optimized Medical Image Classification with Deep Convolutional Neural Networks](https://mlsanity.com/paper/2201.11440/) (2022)
- [Leveraging PAC-Bayes Theory and Gibbs Distributions for Generalization Bounds with Complexity Measures](https://mlsanity.com/paper/2402.13285/) (2024)
- [Many AI Analysts, One Dataset: Navigating the Agentic Data Science Multiverse](https://mlsanity.com/paper/2602.18710/) (2026)
- [Weight Expansion: A New Perspective on Dropout and Generalization](https://mlsanity.com/paper/2201.09209/) (2022)
- [Trade-offs in Data Memorization via Strong Data Processing Inequalities](https://mlsanity.com/paper/2506.01855/) (2025)
- [Model-agnostic bias mitigation methods with regressor distribution control for Wasserstein-based fairness metrics](https://mlsanity.com/paper/2111.11259/) (2021)
- [Adaptive Data Analysis in a Balanced Adversarial Model](https://mlsanity.com/paper/2305.15452/) (2023)

## Abstract (arXiv)

Overfitting is the bane of data analysts, even when data are plentiful. Formal approaches to understanding this problem focus on statistical inference and generalization of individual analysis procedures. Yet the practice of data analysis is an inherently interactive and adaptive process: new analyses and hypotheses are proposed after seeing the results of previous ones, parameters are tuned on the basis of obtained results, and datasets are shared and reused. An investigation of this gap has recently been initiated by the authors in (Dwork et al., 2014), where we focused on the problem of estimating expectations of adaptively chosen functions. In this paper, we give a simple and practical method for reusing a holdout (or testing) set to validate the accuracy of hypotheses produced by a learning algorithm operating on a training set. Reusing a holdout set adaptively multiple times can easily lead to overfitting to the holdout set itself. We give an algorithm that enables the validation of a large number of adaptively chosen hypotheses, while provably avoiding overfitting. We illustrate the advantages of our algorithm over the standard use of the holdout set via a simple synthetic experiment. We also formalize and address the general problem of data reuse in adaptive data analysis. We show how the differential-privacy based approach given in (Dwork et al., 2014) is applicable much more broadly to adaptive data analysis. We then show that a simple approach based on description length can also be used to give guarantees of statistical validity in adaptive settings. Finally, we demonstrate that these incomparable approaches can be unified via the notion of approximate max-information that we introduce.