Generalization in Adaptive Data Analysis and Holdout Reuse

By Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, Aaron Roth. 2015

264 citations recorded by the source corpus.

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 [7], 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 [7] 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. This, in particular, allows the preservation of statistical validity guarantees even when an analyst adaptively composes algorithms which have guarantees based on either of the two approaches.

Subfields: Artificial Intelligence

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

Citations in the corpus

Differentially Private Password Frequency Lists (2016, background): “[11] recently showed that differential privacy can have the positive side effect of preventing over-fitting!”
Algorithmic stability for adaptive data analysis (2015, methodology): “…settings, for example: in multistage inference algorithms where data are preprocessed (say, to select features or restrict to a principal subspace) before the main analysis is performed; in scoring data-based competitions [BH15]; and in the re-use of holdout or test data [DFH + 15c, DFH + 15a].”
Heavy Hitters and the Structure of Local Privacy (2017, background): “The max information [7] of an algorithm is a measure of how much information it reveals about a randomly chosen input.”
LOGAN: Membership Inference Attacks Against Generative Models (2017, background): “ack likely correlates with other leakage, as well as with overﬁtting of the model. In fact, the relationship between robust privacy protections and generalizations have been discussed by Dwork et al. [15]. Attack Overview. We consider both black-box and white-box attacks. In the former, the adversar”
Towards Practical Differentially Private Convex Optimization (2019, positive): “For reasonable values of the privacy parameters, the accuracy of the best private model is within 2% of the baseline for two of these datasets, essentially identical to the baseline for one of them, and even slightly higher than the baseline for one of the datasets! This provides empirical evidence ”
Identifying Statistical Bias in Dataset Replication (2020, background): “For example, evaluating on benchmarks alone may steer us towards models that adaptively overfit (Reunanen, 2003; Rao et al., 2008; Dwork et al., 2015) to the test set and do not generalize.”
When is memorization of irrelevant training data necessary for high-accuracy learning? (2020, background): “More formally, it is known that differential privacy implies a bound on the mutual information I(X;M) [27, 17, 34, 10].”
A comparative analysis of gradient boosting algorithms (2019, background): “In fact, it has been shown that reusing the training data multiple times can lead to overfitting (Dwork et al. 2015).”
Adaptive Machine Unlearning (2021, methodology): “We formally describe R A distr in Algorithm 3.”
Controlling Bias in Adaptive Data Analysis Using Information Theory (2015, background): “We discuss the close connections to recent work inspired by differential privacy [3, 7, 8, 11].”
A General Characterization of the Statistical Query Complexity (2016, background): “In the opposite direction: differentially private algorithms for answering linear queries were recently shown to imply algorithms for the challenging problem of answering adaptively chosen statistical queries (Dwork et al., 2014, 2015; Bassily et al., 2015).”
Differentially Private Decoding in Large Language Models (2022, result): “More broadly, this connection may support the observation that in some cases DP methods provide better generalization (Dwork et al., 2015).”
Fides: Towards a Platform for Responsible Data Science (2017, methodology): “To control for these issues related to multiple hypothesis testing, Fides automatically establishes a reusable holdout set [17], and restricts access to the underlying data during the exploratory phase to preserve statistical validity.”