Preserving Statistical Validity in Adaptive Data Analysis

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

418 citations recorded by the source corpus.

A great deal of effort has been devoted to reducing the risk of spurious scientific discoveries, from the use of sophisticated validation techniques, to deep statistical methods for controlling the false discovery rate in multiple hypothesis testing. However, there is a fundamental disconnect between the theoretical results and the practice of data analysis: the theory of statistical inference assumes a fixed collection of hypotheses to be tested, or learning algorithms to be applied, selected non-adaptively before the data are gathered, whereas in practice data is shared and reused with hypotheses and new analyses being generated on the basis of data exploration and the outcomes of previous analyses. In this work we initiate a principled study of how to guarantee the validity of statistical inference in adaptive data analysis. As an instance of this problem, we propose and investigate the question of estimating the expectations of m adaptively chosen functions on an unknown distribution given n random samples. We show that, surprisingly, there is a way to estimate an exponential in n number of expectations accurately even if the functions are chosen adaptively. This gives an exponential improvement over standard empirical estimators that are limited to a linear number of estimates. Our result follows from a general technique that counter-intuitively involves actively perturbing and coordinating the estimates, using techniques developed for privacy preservation. We give additional applications of this technique to our question.

Subfields: Artificial Intelligence, Statistics and Probability, Safety, Robustness & Interpretability

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

In Statistics and Probability

In Safety, Robustness & Interpretability

Citations in the corpus

The Effect of Natural Distribution Shift on Question Answering Models (2020, methodology): “Although repeated test-set reuse puts pressure on the statistical guarantees of the holdout method (Dwork et al., 2015), a series of replication studies established there is no adaptive overﬁtting on popular clas-siﬁcation benchmarks like MNIST (Yadav & Bottou, 2019), CIFAR-10 (Recht et al., 2019),…”
Differentially Private Learning Needs Better Features (or Much More Data) (2020, background): “The reason is that differential privacy is itself a powerful regularizer (informally, differential privacy implies low generalization error (Dwork et al., 2015)), so our models all underfit the training data.”
The power of synergy in differential privacy: Combining a small curator with local randomizers (2019, background): “Dwork et al. [24] and Bassily et al. [7] showed that if a hypothesis h is the result of a di ﬀ er-entially private computation on a random sample, then the empirical error of h and its generalization error are guaranteed to be close.”
The structure of optimal private tests for simple hypotheses (2018, background): “when confidentiality is not a direct concern, as they provide generalization guarantees in an adaptive setting [29].”
Proving Differential Privacy via Probabilistic Couplings (2016, positive): “In the future, we plan to use our methods also for the veriﬁcation adaptive data analysis algorithms used to prevent false discoveries, such as the one proposed by Dwork et al. [15], and for the formal veriﬁcation of mechanism design [7].”
Algorithmic stability for adaptive data analysis (2015, methodology): “The striking results of Dwork et al. [DFH + 15b] gave the ﬁrst nontrivial algorithms for provably ensuring statistical validity in adaptive data analysis, allowing for even an exponential number of tests against the same sample.”
Heavy Hitters and the Structure of Local Privacy (2017, background): “The motivation for studying max-information comes from its ability to ensure generalization in adaptive data analysis [3, 9, 10, 32].”
Does learning require memorization? a short tale about a long tail (2019, background): “Moreover, they result in remarkably low gap between the training and test error that is formally explained by the generalization properties of DP [22].”
Privacy for Free: Posterior Sampling and Stochastic Gradient Monte Carlo (2015, background): “Unlike what is conjectured in Dwork et al. (2014), our observation seems to suggest that the computational barrier is not speciﬁc to diﬀerential privacy, but rather the barrier of learning in general.”
Make Up Your Mind: The Price of Online Queries in Differential Privacy (2016, background): “Another motivation for studying the relationship between these models is the recent line of work connecting di ﬀ erential privacy to statistical validity for adaptive data analysis [HU14, DFH + 15, SU15b, BNS + 16], which shows that di ﬀ erentially private algorithms for adaptively-chosen queries in”
The Ladder: A Reliable Leaderboard for Machine Learning Competitions (2015, background): “The goal of an accurate leaderboard is to guarantee that at each step t 6 k, the leaderboard accurately reflects the best classifier among those classifiers f1, . . . , fk submitted so far.”
Private Multiplicative Weights Beyond Linear Queries (2014, background): “[9] and Hardt and Ullman [21] showed a connection between differential privacy and generalization error in adaptive data analysis, in which the analyst asks an adaptively chosen sequence of queries.”
Interactive fingerprinting codes and the hardness of preventing false discovery (2014, methodology): “Our result builds on the techniques of Hardt and Ullman (2014), who rely on a combinatorial object called a fingerprinting code Boneh and Shaw (1998); Tardos (2008) to prove their hardness result.”
Private selection from private candidates (2018, background): “A beautiful recent line of work [2, 9] shows that when these analyses take the form of low-sensitivity queries, using differentially private versions of these analyses allows us to improve the sample complexity quadratically over what would otherwise be possible.”
Learning with Differential Privacy: Stability, Learnability and the Sufficiency and Necessity of ERM Principle (2015, methodology): “Theorem 7) In this Appendix, we describe how the results in Dwork et al. (2015b) can be used to obtain the forward direction of our characterization without going through a stability argument.”
Generalization for Adaptively-chosen Estimators via Stable Median (2017, methodology): “This allows us to bypass the known proofs of high-probability bounds that rely on relatively involved arguments (Dwork et al., 2014; Bassily et al., 2016; Rogers et al., 2016).”