Generalization in Adaptive Data Analysis and Holdout Reuse

Abstract

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.

References in corpus (4)

• Learning with Differential Privacy: Stability, Learnability and the Sufficiency and Necessity of ERM Principle
• The Ladder: A Reliable Leaderboard for Machine Learning Competitions
• On the Generalization Properties of Differential Privacy
• More General Queries and Less Generalization Error in Adaptive Data Analysis

Cited by in corpus (36)

• Adaptive Machine Unlearning
• Generalization Bounds via Information Density and Conditional Information Density
• Tighter risk certificates for neural networks
• How much does your data exploration overfit? Controlling bias via information usage
• Pointwise Maximal Leakage
• Individual Privacy Accounting via a Renyi Filter
• Reasoning About Generalization via Conditional Mutual Information
• Generalization Error Bounds Via Rényi-, $f$-Divergences and Maximal Leakage
• Information Complexity and Generalization Bounds
• Differentially Private False Discovery Rate Control
• Data-dependent PAC-Bayes priors via differential privacy
• Private Stochastic Non-Convex Optimization: Adaptive Algorithms and Tighter Generalization Bounds
• Information-Theoretic Generalization Bounds for Stochastic Gradient Descent
• Identifying Statistical Bias in Dataset Replication
• Separating Adaptive Streaming from Oblivious Streaming
• Improving Robustness to Model Inversion Attacks via Mutual Information Regularization
• PAC-Bayes Analysis Beyond the Usual Bounds
• A Blockchain-Based Approach for Saving and Tracking Differential-Privacy Cost
• A necessary and sufficient stability notion for adaptive generalization
• Scalable and Provably Accurate Algorithms for Differentially Private Distributed Decision Tree Learning
• Mitigating Bias in Adaptive Data Gathering via Differential Privacy
• Natural Analysts in Adaptive Data Analysis
• Robustness, Privacy, and Generalization of Adversarial Training
• Upper Bounds on the Generalization Error of Private Algorithms for Discrete Data
• The Everlasting Database: Statistical Validity at a Fair Price
• On the Generalization of Models Trained with SGD: Information-Theoretic Bounds and Implications
• Wasserstein PAC-Bayes Learning: Exploiting Optimisation Guarantees to Explain Generalisation
• On Adaptive Distance Estimation
• Private Learning Implies Online Learning: An Efficient Reduction
• Optimal multiclass overfitting by sequence reconstruction from Hamming queries
• Constructing Privacy Channels from Information Channels
• Optimizing Information-theoretical Generalization Bounds via Anisotropic Noise in SGLD
• Outcome Indistinguishability
• A Rademacher Complexity Based Method fo rControlling Power and Confidence Level in Adaptive Statistical Analysis
• Achieving Dalenius' Goal of Data Privacy with Practical Assumptions
• EntropyDB: A Probabilistic Approach to Approximate Query Processing