自适应统计对手与无知统计对手是等价的

arXiv:2410.13548v3 公告类型：替换 摘要：我们解决了一个关于在对手篡改样本时执行统计任务（例如学习）能力的基本问题。这类对手由其能够实施的篡改类型以及其对样本的了解程度来定义。后者区分了样本自适应对手和样本无知对手：前者在选择篡改方式时知道样本的内容，而后者不知道。我们证明，对于所有类型的篡改，样本自适应对手和样本无知对手在样本规模的多项式因子范围内是\emph{等价的}。这解决了 [BLMT22] 提出的、并在 [CHL+23] 中进一步研究的主要开放问题。具体而言，考虑任意算法 $A$，即使样本无知对手篡改其输入，该算法仍能完成某项统计任务。我们证明，存在一个算法 $A'$，当相应的样本自适应对手篡改其输入时，该算法仍能完成同一任务。$A'$ 的构造十分简单，并且保持了 $A$ 的计算效率：它所需的样本数量是 $A$ 所使用样本数量的多项式倍，随后在其中运行 $A$，所使用的子样本是均匀随机抽取的。