Preventing False Discovery in Interactive Data Analysis Is Hard
Authors:
- Moritz HardtMHMoritz Hardt
- Jonathan UllmanJUJonathan Ullman
- 1 October 2014
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 454-463
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.Keywords
All Related Versions
This publication has 11 references indexed in Scilit:
- How robust are linear sketches to adaptive inputs?2013
- A Multiplicative Weights Mechanism for Privacy-Preserving Data Analysis2010
- Interactive privacy via the median mechanism2010
- On the complexity of differentially private data release2009
- Optimal probabilistic fingerprint codesJournal of the ACM, 2008
- Calibrating Noise to Sensitivity in Private Data Analysis2006
- 10.1162/153244302760200704Applied Physics Letters, 2000
- Collusion-secure fingerprinting for digital dataIEEE Transactions on Information Theory, 1998
- Tracing Traitors1994
- Efficient noise-tolerant learning from statistical queries1993