Preventing False Discovery in Interactive Data Analysis Is Hard
The DOI matches its Crossref record; 2 of the 2 references it cites were found in a registry or an index.
Abstract
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Controlling the False Discovery Rate: A Practical and Powerful Approach to Multiple Testing
Benjamini, Y., & Hochberg, Y. (1995) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/j.2517-6161.1995.tb02031.x · Cited by 109,482
Calibrating Noise to Sensitivity in Private Data Analysis
Dwork, C., McSherry, F., Nissim, K., & Smith, A. (2006) · Lecture Notes in Computer Science · doi:10.1007/11681878_14 · Cited by 7,272
Cited by
Exposed! A Survey of Attacks on Private Data
Dwork, C., Smith, A., Steinke, T., & Ullman, J. (2017) · Annual Review of Statistics and Its Application · doi:10.1146/annurev-statistics-060116-054123 · Cited by 259
Self-citationMore Than Privacy: Applying Differential Privacy in Key Areas of Artificial Intelligence
Zhu, T., Ye, D., Wang, W., Zhou, W., & Yu, P. S. (2022) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2020.3014246 · Cited by 219
Generalization in Adaptive Data Analysis and Holdout Reuse
Dwork, C., Feldman, V., Hardt, M., Pitassi, T., Reingold, O., & Roth, A. (2015) · arXiv · doi:10.48550/arxiv.1506.02629 · Cited by 152
Self-citationThe Ladder: A Reliable Leaderboard for Machine Learning Competitions
Blum, A., & Hardt, M. (2015) · arXiv · doi:10.48550/arxiv.1502.04585 · Cited by 92
Self-citation
Metadata
- Authors
- Hardt, M., & Ullman, J.
- Venue
- 2014 IEEE 55th Annual Symposium on Foundations of Computer Science
- Publisher
- IEEE
- Published
- 2014-10
- Pages
- 454-463
- ISSN
- 0272-5428 (ISSN-L)
- OpenAlex
- W2077641783
- Cited by
- 78
- References
- 2
- FWCI
- 4.15
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Preventing False Discovery in Interactive Data Analysis Is Hard. https://app.cochat.ai/papers/10.1109/focs.2014.55
- The paper
- Hardt, M., & Ullman, J. (2014). Preventing False Discovery in Interactive Data Analysis Is Hard. 2014 IEEE 55th Annual Symposium on Foundations of Computer Science. https://doi.org/10.1109/focs.2014.55
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.