Source-linked AI summary
Generalization in Adaptive Data Analysis and Holdout Reuse
Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, Aaron Roth
TL;DR
Adaptive data analysis makes repeated holdout reuse and data-dependent hypothesis selection vulnerable to overfitting, limiting ordinary generalization guarantees. The paper introduces reusable-holdout validation and formalizes adaptive data reuse using differential privacy, description length, and approximate max-information. It shows that these approaches provide generalization guarantees and can be unified through approximate max-information, while identifying unresolved questions about stronger guarantees and scope limitations for approximate privacy.
Problem
Adaptive hypothesis selection and repeated holdout reuse can make standard validation overfit the holdout, undermining statistical validity.
Method
The paper develops reusable-holdout validation and analyzes adaptive data reuse using differential privacy, description length, and approximate max-information.
Results
Approximate max-information unifies differential-privacy and description-length approaches and supports generalization guarantees for adaptive analyses.
Takeaways & Limitations
Adaptive sequences can combine differentially private procedures with short-description outputs while preserving generalization guarantees through approximate max-information.
Takeaways & Limitations
The paper leaves open whether stronger guarantees than differential privacy are possible for adaptively reused holdouts and notes that strong approximate-privacy results are known only for bounded-range function outputs.
Abstract
from arXiv · showhide
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.
1 Introduction
Adaptive reuse of data can invalidate generalization, especially when holdout hypotheses are chosen from prior results. This paper develops reusable-holdout methods and approximate max-information to preserve statistical validity under adaptive analysis.
- Problem: Adaptive feature selection and repeated holdout reuse can make procedures depend on the data, causing overfitting and misleading generalization estimates.Freedman’s simulation illustrates this danger by selecting significant variables before regression, producing apparent relationships despite no true relationship.
- Generalization framework: Description length and differential privacy provide distinct generalization guarantees, and approximate max-information unifies them through adaptive composition and post-processing.The unified framework supports adaptive sequences combining differentially private algorithms with algorithms whose outputs have short descriptions.
- Reusable holdout: The paper proposes a general method that lets analysts validate results through a restricted interface to the holdout set while provably avoiding holdout overfitting.The method permits arbitrary analysis on training data, but controls access to the holdout through validation algorithms.
- Reusable holdout: For i.i.d. datasets, Thresholdout modifications prevent analysts from constructing functions that overfit the holdout, while answering exponentially many queries when overfitting occurs at most quadratically often.The number of answerable queries is exponential in the holdout sample size n under the stated condition.
- Generalization framework: Approximate max-information gives generalization guarantees, while pure differential privacy controls generalization for any dataset distribution and has stronger bounds for i.i.d. datasets.The differential-privacy result cited here applies only to pure differential privacy, the δ = 0 case.
2 Preliminaries and Basic Techniques
This section reviews differential privacy, adaptive composition, concentration, and description-length tools for controlling generalization in adaptive analyses.
- Concentration and sensitivity: McDiarmid’s inequality gives concentration for functions whose value changes by at most c when one dataset element changes.The section defines empirical averages and their sensitivity before applying the inequality.
- Differential privacy: Differential privacy protects against changes to one individual’s data and remains preserved under adaptive composition and post-processing.Adaptive composition executes analyses sequentially on the same dataset, with later algorithms depending on earlier outputs.
- Generalization via differential privacy: Differentially private algorithms that output low-sensitivity functions can generalize from i.i.d. datasets.For a c-sensitive function, privacy yields an exponential bound on the probability that empirical performance exceeds population performance by τ.
- Description length: Theorem 9 bounds adaptive bad-event probability by |Y| · β when every fixed output y has bad-event probability at most β.The result uses the size of the output range, equivalently the description length of the first algorithm’s output.
3 Max-Information
This section introduces approximate max-information as a measure of dataset-output dependence and develops its generalization, composition, and connections to privacy and description length.
- Definition and interpretation: Max-information measures how much observing an algorithm’s output can increase the likelihood of a dataset relative to independent sampling.It is defined through max-divergence between the joint distribution and the product of marginals.
- Definition and interpretation: Pure max-information equals the maximum infinity-divergence between algorithm outputs on two datasets.This characterization relates the information measure directly to output-distribution changes across inputs.
- Generalization via max-information: Approximate max-information controls adaptive bad-event probabilities through P[(S, A(S)) ∈ O] ≤ 2^k · max_y P[(S, y) ∈ O] + β.The bound transfers probability estimates for fixed outputs to the adaptively selected output.
- Composition: Max-information composes adaptively: k1 and k2 bounds combine to k1 + k2, while approximation parameters combine as β1 + β2.The composition lemma applies when the second algorithm has a uniform max-information bound for every first-algorithm output.
- Composition: Iterating the composition lemma yields guarantees for arbitrary sequential adaptive algorithms whose conditional steps have bounded approximate max-information.Each step may depend on all previous outputs.
- Post-processing: Approximate max-information is preserved under post-processing of an algorithm’s output.This property parallels the post-processing behavior of differential privacy.
- Connections to existing techniques: Description length and differential privacy are incomparable, but approximate max-information unifies their generalization arguments.Max-information bounds can also be translated into randomized description-length bounds for a statistically indistinguishable algorithm.
- Connections to existing techniques: Differential privacy gives low max-information, including a bound I∞(A, n) ≤ log e · εn for ε-differentially private algorithms.For i.i.d. datasets, the paper also proves a stronger approximate max-information bound.
4 Reusable Holdout
The paper presents two methods for adaptively reusing a holdout set while controlling overfitting: Thresholdout uses differential privacy, while SparseValidate uses description length. Thresholdout can validate exponentially many queries when relatively few overfit, and both approaches provide formal generalization guarantees.
- Thresholdout: Thresholdout uses differential privacy to answer adaptively chosen queries while preventing overfitting to the holdout set.It checks whether training and holdout means differ beyond a threshold, returning a training estimate for small differences and a noisy holdout estimate otherwise.
- Thresholdout: Thresholdout can efficiently validate an exponential in n number of queries as long as a relatively small number of them overfit.Its achievable tolerance scales as 1/√n up to a logarithmic factor when the budget grows sub-quadratically in n.
- Thresholdout: Thresholdout satisfies (2B/(σn), 0)-differential privacy and also satisfies (32B ln(2/δ)/(σn), δ)-differential privacy.The latter guarantee holds for any δ > 0.
- SparseValidate: SparseValidate validates many arbitrary queries by revealing information about the holdout set only when validation fails.Its analysis uses the short description length of the interaction transcript and requires the analyst to use the failure budget economically.
- SparseValidate: For SparseValidate, the probability of an adaptively generated query failing is bounded by ℓ_i · β_i, where ℓ_i = Pmin{i−1,B}.The factor ℓ_i counts possible response transcripts containing at most B validation failures.
- Comparison: SparseValidate does not provide corrections for overfitting, whereas Thresholdout returns corrected estimates through noisy holdout responses.A multivalued extension can provide corrections, but a separate dataset may be more economical for obtaining accurate estimates.
5 Experiments
The experiments illustrate how adaptive holdout reuse can cause overfitting and how Thresholdout prevents it while preserving useful classifier validation and discovery of true patterns.
- Experimental setup: The synthetic experiment adaptively selects variables correlated with the label, then builds a higher-accuracy classifier from the selected variables.Variables are selected using training and holdout correlations, with agreement in sign and a threshold of 1/√n required.
- Experimental setup: Thresholdout is implemented with T = 0.04 and τ = 0.01, using Gaussian rather than Laplacian noise in the experiments.These parameters are lower than those needed for the theoretical proof but suffice to prevent overfitting experimentally.
- Results: Figure 2 evaluates classifier accuracy on training, holdout, and fresh sets when class labels and data points are uncorrelated, with margins showing standard deviation.The corresponding caption describes the no-correlation setting and the three accuracy sets.
- Results: When some variables are correlated with the label, the reusable holdout still finds a good classifier while preventing overfitting.The experiment compares standard holdout and Thresholdout, and the authors state that reusable holdout supports discovery of true statistical patterns.
- Results: Figure 4 demonstrates essentially no overfitting to the holdout set for the classifier produced with Thresholdout.Thresholdout’s reported accuracy can also support further data-dependent decisions while mitigating holdout overfitting.
6 Conclusions
The paper unifies differential privacy and description-length approaches through approximate max-information, while identifying practical and theoretical questions that remain open.
- Conclusions: Differential privacy and description-length bounds preserve generalization guarantees for subsequent algorithms in adaptively chosen sequences of data analyses.The paper presents these techniques as having low max-information and therefore composable guarantees.
- Conclusions: The two techniques provide incomparable guarantees when used separately, but approximate max-information offers a unifying perspective and an adaptive composition theorem.The paper identifies this framework as connecting the two approaches rather than making them equivalent.
- Open questions: Additional empirical work is needed to understand when and how the theory should be applied in specific application scenarios.The authors also state that new theory is needed for stronger generalization guarantees under adaptive holdout reuse.
A From Max-information to Randomized Description Length
This section connects max-information with randomized description length by constructing new algorithms whose outputs are statistically close while having concise randomized descriptions. It also clarifies that this reduction is not an equivalence and may require access to an output marginal distribution.
- Randomized description length: Randomized description length bounds the probability of data-dependent bad events and implies generalization and approximate max-information guarantees.An algorithm with randomized description length k gives a 2^kβ bound for events that have probability at most β independently of its output.
- Randomized description length: Definition 28 assigns randomized description length k when every fixed setting of the algorithm’s random coins permits at most 2^k possible outputs.This operational definition extends ordinary description-length reasoning to randomized algorithms.
- Reduction: Lemma 31 constructs an algorithm A′ with randomized description length k + log ln(1/β′) whose output is within βS + β′ of A(S).The construction samples from a marginal distribution Z and accepts samples according to probabilities determined by the target distribution and Z.
- Reduction: Theorem 32 applies the reduction when A(S) has β-approximate max-information k, producing A′ with randomized description length k + log ln(1/β′).The argument uses the expected value of the dataset-dependent approximation parameter and applies Lemma 31 with Z = A(S).
- Consequences and limits: The reduction does not establish equivalence between max-information and randomized description length and requires knowledge of the marginal distribution A(S).The authors note that this prevents obtaining a description-length equivalent of one cited theorem for all i.i.d. datasets.
B Answering Queries via Description Length Bounds
This section presents a description-length analysis of a noise-free Median Mechanism for answering adaptively chosen statistical queries. The mechanism supports polylogarithmic sample scaling in the number of queries and provides a generalization guarantee.
- Description-length approach: The method answers any adaptively chosen sequence of m statistical queries using samples that scale only polylogarithmically in m.This is described as an exponential improvement over naively evaluating the queries exactly on the samples.
- Mechanism: The analysis uses a noise-free version of the Median Mechanism and establishes its properties through description-length bounds.The mechanism is based on the Median Mechanism of Roth and Roughgarden, originally used for adaptively chosen counting queries.
- Mechanism: The Median Mechanism takes a dataset and adaptively chosen functions φ1, . . . , φm, then returns answers a1, . . . , am for their statistical queries.Each function maps X to [0,1], and the mechanism is given an accuracy parameter τ.
- Mechanism: Only a small number of rounds return answers computed directly from the dataset S; other answers are computed from the consistent-dataset set.This sparsity property underlies the compact representation of the interaction.
- Description-length analysis: The analyst–mechanism interaction can be treated as one algorithm A whose output has short randomized description length.The query-answer sequence can be reconstructed by recording the indices and answers of rounds where the mechanism's answer differs from the public answer.
- Generalization guarantee: Combining concentration, union-bound, and description-length arguments with the mechanism's accuracy lemma yields a probability guarantee that all query answers generalize within the stated error parameters.The proof applies a generalization theorem to the set of datasets on which at least one query's empirical expectation differs from its population expectation, then sets τ = 3α.