Preventing False Discovery in Interactive Data Analysis Is Hard
Preventing False Discovery in Interactive Data Analysis Is Hard
复制标题
DOI：
10.1109/focs.2014.55
复制
发表时间：
2014-08
期刊：
影响因子：
--
通讯作者：
Moritz Hardt;Jonathan Ullman
中科院分区：
文献类型：
--
作者：
Moritz Hardt;Jonathan Ullman
我们表明，在标准硬度假设下，没有任何计算效率高的算法可以在给定未知分布的n个样本的情况下为n3+o（1）个自适应选择的统计查询提供有效答案。统计查询要求谓词对底层分布的期望，如果统计查询的答案“接近”对分布的正确期望，则该答案是有效的。我们的结果与众所周知的事实形成鲜明对比，即如果查询是非自适应选择的（没有查询可能依赖于以前的查询的答案），则可以有效和高效地回答指数级的许多统计查询。此外，Dwork等人。[1]展示了如何通过计算效率低下的算法准确地回答指数级的许多自适应选择的统计查询。他们也给出了有效的算法，可以回答近n2个自适应选择的查询，这表明我们的结果几乎是定量紧。从概念上讲，我们的研究结果表明，实现统计有效性单独可以在自适应设置的计算棘手的来源。例如，在现代大型协作研究环境中，数据分析师通常会根据以前的研究结果选择特定的方法。如果一项研究发现有数据支持，但没有潜在的分布支持，则会发生错误发现。虽然在统计学中防止错误发现的研究已经有几十年的历史了，但据我们所知，我们的结果是第一个证明计算障碍的结果。特别是，我们的研究结果表明，在今天的合作研究环境中，防止错误发现的感知困难可能是固有的。
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.