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.

本文针对过拟合问题，提出了一种适用于自适应数据分析的算法，使用保留集重复验证后得到的假设，避免了过度拟合问题，同时利用描述长度和差分隐私，展示了在适应性场景下保证统计有效性的方法，并通过近似最大信息的方法将这些方法统一起来。