arXiv：cs.LG（机器学习，全量分类）· Guy Blanc, Gregory Valiant·· 15 小时前AI 评分48
样本自适应与样本无关统计对手被证明等价
Adaptive and oblivious statistical adversaries are equivalent
AI 导读
研究证明，对任意类型的样本污染，样本自适应对手与样本无关对手在样本量多项式因子范围内等价，解决了 [BLMT22] 提出的核心开放问题。给定能在样本无关对手污染下完成统计任务的算法 A，可构造出同样计算高效的算法 A' 应对对应的样本自适应对手：A' 请求多项式更大的样本，再在均匀随机子样本上运行 A。该成果发表于 STOC'25。
正文
Abstract:We resolve a fundamental question about the ability to perform a statistical task, such as learning, when an adversary corrupts the sample. Such adversaries are specified by the types of corruption they can make and their level of knowledge about the sample. The latter distinguishes between sample-adaptive adversaries which know the contents of the sample when choosing the corruption, and sample-oblivious adversaries, which do not. We prove that for all types of corruptions, sample-adaptive and sample-oblivious adversaries are \emph{equivalent} up to polynomial factors in the sample size. This resolves the main open question introduced by [BLMT22] and further explored in [CHL+23].
Specifically, consider any algorithm $A$ that solves a statistical task even when a sample-oblivious adversary corrupts its input. We show that there is an algorithm $A'$ that solves the same task when the corresponding sample-adaptive adversary corrupts its input. The construction of $A'$ is simple and maintains the computational efficiency of $A$: It requests a polynomially larger sample than $A$ uses and then runs $A$ on a uniformly random subsample.
| Comments: | Appeared at STOC' 25 |
| Subjects: | Machine Learning (cs.LG); Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS) |
| Cite as: | arXiv:2410.13548 [cs.LG] |
| (or arXiv:2410.13548v3 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2410.13548 arXiv-issued DOI via DataCite |
Submission history
From: Guy Blanc [view email]
[v1]
Thu, 17 Oct 2024 13:42:56 UTC (56 KB)
[v2]
Fri, 29 Aug 2025 20:08:50 UTC (65 KB)
[v3]
Wed, 30 Sep 2026 20:29:13 UTC (49 KB)
来源：arXiv：cs.LG（机器学习，全量分类） · arxiv.org