# Preventing False Discovery in Interactive Data Analysis is Hard

arXiv: https://arxiv.org/abs/1408.1655 · HTML: https://mlsanity.com/paper/1408.1655/

## Key facts

- Cited by 34 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Aug 2014.

## Built on by (most cited first, 30 of 34)

- [Better and Simpler Lower Bounds for Differentially Private Statistical Estimation](https://mlsanity.com/paper/2310.06289/) (2023)
- [On the power of adaptivity in statistical adversaries](https://mlsanity.com/paper/2111.10352/) (2021)
- [A Bias-Accuracy-Privacy Trilemma for Statistical Estimation](https://mlsanity.com/paper/2301.13334/) (2023)
- [A Framework for Adversarial Streaming via Differential Privacy and Difference Estimators](https://mlsanity.com/paper/2107.14527/) (2021)
- [Adaptive Data Analysis with Correlated Observations](https://mlsanity.com/paper/2201.08704/) (2022)
- [On Differential Privacy and Adaptive Data Analysis with Bounded Space](https://mlsanity.com/paper/2302.05707/) (2023)
- [Subsampling Suffices for Adaptive Data Analysis](https://mlsanity.com/paper/2302.08661/) (2023)
- [Lower Bounds for Private Estimation of Gaussian Covariance Matrices under All Reasonable Parameter Regimes](https://mlsanity.com/paper/2404.17714/) (2024)
- [Rip van Winkle's Razor: A Simple Estimate of Overfit to Test Data](https://mlsanity.com/paper/2102.13189/) (2021)
- [PAC Verification of Statistical Algorithms](https://mlsanity.com/paper/2211.17096/) (2022)
- [Smooth Lower Bounds for Differentially Private Algorithms via Padding-and-Permuting Fingerprinting Codes](https://mlsanity.com/paper/2307.07604/) (2023)
- [Generalization in the Face of Adaptivity: A Bayesian Perspective](https://mlsanity.com/paper/2106.10761/) (2021)
- [On Leakage in Machine Learning Pipelines](https://mlsanity.com/paper/2311.04179/) (2023)
- [On the Robustness of CountSketch to Adaptive Inputs](https://mlsanity.com/paper/2202.13736/) (2022)
- [A Polynomial Time, Pure Differentially Private Estimator for Binary Product Distributions](https://mlsanity.com/paper/2304.06787/) (2023)
- [Adaptive Data Analysis in a Balanced Adversarial Model](https://mlsanity.com/paper/2305.15452/) (2023)
- [Private PAC Learning May be Harder than Online Learning](https://mlsanity.com/paper/2402.11119/) (2024)
- [Fingerprinting Codes Meet Geometry: Improved Lower Bounds for Private Query Release and Adaptive Data Analysis](https://mlsanity.com/paper/2412.14396/) (2024)
- [Tricking the Hashing Trick: A Tight Lower Bound on the Robustness of CountSketch to Adaptive Inputs](https://mlsanity.com/paper/2207.00956/) (2022)
- [Generalization Bounds for Stochastic Gradient Langevin Dynamics: A Unified View via Information Leakage Analysis](https://mlsanity.com/paper/2112.08439/) (2021)
- [Adaptive Data Analysis for Growing Data](https://mlsanity.com/paper/2405.13375/) (2024)
- [Tight Bounds for Answering Adaptively Chosen Concentrated Queries](https://mlsanity.com/paper/2507.13700/) (2025)
- [Making Progress Based on False Discoveries](https://mlsanity.com/paper/2204.08809/) (2022)
- [Relaxed Models for Adversarial Streaming: The Advice Model and the Bounded Interruptions Model](https://mlsanity.com/paper/2301.09203/) (2023)
- [Verification of Neural Networks Local Differential Classification Privacy](https://mlsanity.com/paper/2310.20299/) (2023)
- [Bayesian Perspective on Memorization and Reconstruction](https://mlsanity.com/paper/2505.23658/) (2025)
- [The Cost of Compression: Tight Quadratic Black-Box Attacks on Sketches for ℓ2 Norm Estimation](https://mlsanity.com/paper/2507.16345/) (2025)
- [Lower Bounds for Public-Private Learning under Distribution Shift](https://mlsanity.com/paper/2507.17895/) (2025)
- [Efficient Adaptive Data Analysis over Dense Distributions](https://mlsanity.com/paper/2602.07732/) (2026)
- [Is Randomness Necessary for Adaptive Data Analysis?](https://mlsanity.com/paper/2607.07085/) (2026)

## Abstract (arXiv)

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, a recent work by Dwork et al. shows how to accurately answer exponentially many adaptively chosen statistical queries via a computationally inefficient algorithm; and how to answer a quadratic number of adaptive queries via a computationally efficient algorithm. The latter result implies that our result is tight up to a linear factor in n. 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.