跳到正文
研踪PaperTrail

论文库

检索计算机领域论文,按研究方向、作者或关键词筛选。

部分采集异常
正在读取账号与研究记录…

全站更新概况

+1111新增论文
+874其中 AI 相关
+133已有论文修订
+97新增 AI 导读

arXiv 最近完成扫描:2026-11-20 07:46 · 全站最近入库:2026-11-19 19:09各信源进度 →

统计口径与数据新鲜度

统计 2026-11-19 08:39 — 2026-11-20 08:39(北京时间) · 点击数字查看对应简报;AI 相关包含在新增论文内。

最近完成检查:2026-11-20 07:46最近发现新增版本:2026-11-19 19:09库内论文最新更新时间:2026-11-19 02:59

每分钟刷新已保存的数据。空检查不代表采集异常;新收录可能包含历史论文。AI 导读按新增版本计数。

27,982 已收录论文23,249 AI 相关8,559 有修订112 HF 社区发现

浏览论文库

时间范围跟随排序:版本更新、本站收录或首次发表。最新收录可能包含历史论文。部分信源异常,查看状态 →

找到 1 篇论文 · 按版本更新时间排序上轮扫描起点 2026-11-20 07:44(北京时间)
版本更新 · v3arXiv:2607.07085

自适应数据分析中随机性是必要的吗?

Is Randomness Necessary for Adaptive Data Analysis?

Edith Cohen, Haim Kaplan, Yishay Mansour, Shay Sapir, Uri Stemmer, Eliad Tsfadia

AI 速读 基于摘要

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

cs.CR · cs.DS · cs.LG

查看原文摘要

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