Preventing False Discovery in Interactive Data Analysis Is Hard

By Moritz Hardt, Jonathan Ullman. 2014

139 citations recorded by the source corpus.

We show that, under a standard hardness assumption, there is no computationally efficient algorithm that given n samples from an unknown distribution can give valid answers to n3+o(1) adaptively chosen statistical queries. A statistical query asks for the expectation of a predicate over the underlying distribution, and an answer to a statistical query is valid if it is "close" to the correct expectation over the distribution. Our result stands in stark contrast to the well known fact that exponentially many statistical queries can be answered validly and efficiently if the queries are chosen non-adaptively (no query may depend on the answers to previous queries). Moreover, Dwork et al. [1], showed how to accurately answer exponentially many adaptively chosen statistical queries via a computationally inefficient algorithm. They also gave efficient algorithm that can answer nearly n2 adaptively chosen queries, which shows our result is almost quantitatively tight. Conceptually, our result demonstrates that achieving statistical validity alone can be a source of computational intractability in adaptive settings. For example, in the modern large collaborative research environment, data analysts typically choose a particular approach based on previous findings. False discovery occurs if a research finding is supported by the data but not by the underlying distribution. While the study of preventing false discovery in Statistics is decades old, to the best of our knowledge our result is the first to demonstrate a computational barrier. In particular, our result suggests that the perceived difficulty of preventing false discovery in today's collaborative research environment may be inherent.

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

Tight Lower Bounds for Differentially Private Selection (2017, methodology): “Techniques Our techniques build on the recent line of work proving lower bounds in differential privacy and related problems via either fingerprinting codes or techniques inspired by fingerprinting codes [16], [24], [25], [17], [18], [26].”
Algorithmic stability for adaptive data analysis (2015, methodology): “The general problem of adaptive data analysis was formally modeled and studied in recent papers by Dwork, Feldman, Hardt, Pitassi, Reingold, and Roth [DFH + 15b] and by Hardt and Ullman [HU14].”
Robust Traceability from Trace Amounts (2015, background): “Intuitively, Corollary 15 says that a smooth distribution (meaning”
Preserving Statistical Validity in Adaptive Data Analysis (2014, background): “The work of [26, 42] shows that, under standard cryptographic assumptions, the exponential running time of the algorithm instantiating our main result is unavoidable, and that the sample complexity of our efficient algorithm is nearly optimal, among all computationally efficient mechanisms for answe”
Between Pure and Approximate Differential Privacy (2015, methodology): “Fingerprinting codes were originally used in cryptography for watermarking digital content, but several recent works have shown they are intimately connected to lower bounds for differential privacy and related learning problems (Ullman, 2013; Bun et al., 2014; Hardt and Ullman, 2014; Steinke and Ul”
The Ladder: A Reliable Leaderboard for Machine Learning Competitions (2015, methodology): “In fact, recent work (Hardt & Ullman, 2014; Steinke & Ullman, 2014) shows that no computationally efficient estimator can achieve error o(1) on more than n2+o(1) adaptively chosen functions (under a standard hardness assumption).”
Private Multiplicative Weights Beyond Linear Queries (2014, background): “[17] A. Gupta, A. Roth, and J. Ullman.”
Learning with Differential Privacy: Stability, Learnability and the Sufficiency and Necessity of ERM Principle (2015, background): “Dwork et al. (2015b) is part of an independent line of work (Hardt & Ullman, 2014; Bassily et al., 2015; Dwork et al., 2015a; Blum & Hardt, 2015) on adaptive data analysis, which also 1For instance, Frank McSherry described in a blog post an example of exploiting differential privacy for measure…”
More General Queries and Less Generalization Error in Adaptive Data Analysis (2015, background): “Even for non-adaptive statistical queries, n (cid:38) log( k ) /α 2 samples are necessary, and [HU14, SU14] showed that n (cid:38) min { √ k, log”
Generalization in Adaptive Data Analysis and Holdout Reuse (2015, background): “It turns out this is for fundamental reasons – Hardt and Ullman [11] and Steinke and Ullman [19] prove that, under cryptographic assumptions, no efficient algorithm can answer more than quadratically many statistical queries chosen adaptively by an adversary who knows the true data distribution.”
The Complexity of Differential Privacy (2017, background): “Remarkably, both positive and negative results for differential privacy (including both information-theoretic and computational lower bounds as we have seen in this tutorial) have found analogues for the false discovery problem [44, 60, 98, 6], suggesting that it will also be a very fertile area for”
A Minimax Theory for Adaptive Data Analysis (2016, methodology): “The factor √ k is shown to be optimal (Steinke & Ullman, 2014; Hardt & Ullman, 2014) for polynomial time algorithms or any algorithms if the dimension of X is sufficiently large.”
FINGERPRINTING CODES AND THE PRICE OF APPROXIMATE DIFFERENTIAL PRIVACY∗ (2018, background): “These works [37, 48] effectively reverse a connection established in [19, 3], which used differentially private algorithms to obtain positive results for this problem.”
How Much Does Your Data Exploration Overfit? Controlling Bias via Information Usage (2015, background): “Exciting recent work in computer science [4, 13, 14, 19] has leveraged the connection between algorithmic stability and diﬀerential privacy to design speciﬁc diﬀerentially private mechanisms that reduce bias in adaptive data analysis.”
Calibrating Noise to Variance in Adaptive Data Analysis (2017, background): “This quadratic relationship between n and k was also shown to be optimal in the worst case (Hardt and Ullman, 2014; Steinke and Ullman, 2015).”