证明了自适应与非自适应对抗者在统计任务中等价，简化了安全学习分析。
Adaptive and oblivious statistical adversaries are equivalent
- 用随机子样本构造新算法，将非自适应对抗场景转为自适应场景。
- 新算法仅需多项式放大样本量，即可在自适应对抗下保持原算法性能。
- 适用于研究鲁棒学习、对抗样本防御的学者，尤其关注安全性理论者。
我们解决了在对手污染样本时执行统计任务（如学习）能力的一个基本问题。对手按其可施加的污染类型和对样本内容的了解程度分类，后者区分了在选择污染时知晓样本内容的样本自适应对手，以及不知情的样本无关对手。我们证明：对于所有类型的污染，样本自适应对手与样本无关对手在样本规模的多项式因子内是等价的。该结论解决了 [BLMT22] 提出并由 [CHL+23] 进一步探讨的主要开放问题。具体而言，对于任意一个在样本无关对手污染下仍能完成统计任务的算法 $A$，我们构造出一个算法 $A'$，使其在对应样本自适应对手污染下同样有效。$A'$ 的构造简单且保持 $A$ 的计算效率：只需请求比 $A$ 多项式倍的样本，然后在均匀随机子样本上运行 $A$。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。