跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv: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
arXiv ↗PDF ↗

摘要

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 nn i.i.d. samples from an unknown distribution P\mathcal{P} over a domain X\mathcal{X}, and our goal is to answer a sequence of kk adaptively chosen statistical queries with respect to P\mathcal{P}. The main question is how many queries we can support (i.e., how large kk can be), primarily as a function of the number of samples nn. This question has been intensively studied and is relatively well-understood for randomized mechanisms: there are computationally efficient mechanisms that support k≈n2k \approx n^2 queries, and no computationally efficient mechanism can answer k≫n2k \gg n^2 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 k=O~(n)k = \tilde{O}(n) queries.

作者备注:Contains a new proof in the plain model, using domain of size 2^{poly(n)}

AI 论文解读

基于摘要 · 非全文审阅

该论文研究自适应数据分析(ADA)中随机性是否必要,证明在分析师计算能力无界时,任何确定性机制在约 n 个查询后就会失败,从而表明随机性是严格必要的。

正在读取账号与研究记录…

版本差异

本站首次收录为 v3,暂无更早版本可对照。

观测到的版本

相邻记录可能跳过中间版本;首次发现 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 nn i.i.d. samples from an unknown distribution P\mathcal{P} over a domain X\mathcal{X}, and our goal is to answer a sequence of kk adaptively chosen statistical queries with respect to P\mathcal{P}. The main question is how many queries we can support (i.e., how large kk can be), primarily as a function of the number of samples nn. This question has been intensively studied and is relatively well-understood for randomized mechanisms: there are computationally efficient mechanisms that support k≈n2k \approx n^2 queries, and no computationally efficient mechanism can answer k≫n2k \gg n^2 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 k=O~(n)k = \tilde{O}(n) queries.

查看此版本解读 →查看此版本原文 ↗