← 研踪 PaperTrailarXiv:2607.07085 · v3
Is Randomness Necessary for Adaptive Data Analysis?
自适应数据分析中随机性是必要的吗?
首次提交 2026-07-08 15:17
版本更新 2026-11-19 02:57
雷达观测 2026-11-19 15:04
摘要
The Adaptive Data Analysis (ADA) problem formalizes the challenge of preventing false discovery and overfitting when a dataset is repeatedly reused. Formally, our input is a dataset containing i.i.d. samples from an unknown distribution over a domain , and our goal is to answer a sequence of adaptively chosen statistical queries with respect to . The main question is how many queries we can support (i.e., how large can be), primarily as a function of the number of samples . This question has been intensively studied and is relatively well-understood for randomized mechanisms: there are computationally efficient mechanisms that support queries, and no computationally efficient mechanism can answer queries. In this paper, we address a fundamental question: is randomness necessary for ADA? Despite a decade of work on ADA, this question remains open. A folklore observation dating back to the initial works on ADA is that randomness is {\em not} necessary when the analyst is computationally bounded. Yet, the necessity of randomness against computationally unbounded analysts has remained elusive. Our main contribution resolves this gap in the information-theoretic setting. Perhaps surprisingly, we show that randomness is {\em strictly necessary} to answer a non-trivial number of adaptive queries: when the analyst is unbounded, any deterministic mechanism can be forced to fail after just queries.
作者备注:Contains a new proof in the plain model, using domain of size 2^{poly(n)}
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v3 · 2026-11-19 02:57 · 最新观测版本
Is Randomness Necessary for Adaptive Data Analysis?
The Adaptive Data Analysis (ADA) problem formalizes the challenge of preventing false discovery and overfitting when a dataset is repeatedly reused. Formally, our input is a dataset containing i.i.d. samples from an unknown distribution over a domain , and our goal is to answer a sequence of adaptively chosen statistical queries with respect to . The main question is how many queries we can support (i.e., how large can be), primarily as a function of the number of samples . This question has been intensively studied and is relatively well-understood for randomized mechanisms: there are computationally efficient mechanisms that support queries, and no computationally efficient mechanism can answer queries. In this paper, we address a fundamental question: is randomness necessary for ADA? Despite a decade of work on ADA, this question remains open. A folklore observation dating back to the initial works on ADA is that randomness is {\em not} necessary when the analyst is computationally bounded. Yet, the necessity of randomness against computationally unbounded analysts has remained elusive. Our main contribution resolves this gap in the information-theoretic setting. Perhaps surprisingly, we show that randomness is {\em strictly necessary} to answer a non-trivial number of adaptive queries: when the analyst is unbounded, any deterministic mechanism can be forced to fail after just queries.
查看此版本解读 →查看此版本原文 ↗