正确标签的对抗性数据插入会令学习难度增加对数因子，即使在可在线学习的类别中也如此。
Optimal Rates for Learning with Monotone Adversaries
- 设计一个基于留一法思想的非正规学习器，在VC维为1时达到最优率
- 证明在VC维≥2时，最坏情况下误差率必含对数项，无法避免
- 揭示了正确标签的对抗性样本破坏交换性，使学习更难
单调对抗者观察独立同分布的带标签样本，并附加有限数量自己选择的样本，每个样本均被目标假设正确标记。学习者看到合并样本的随机打乱，但需在原始分布上评分。尽管所有样本标签正确，但插入内容依赖于干净样本，导致联合样本不可交换。此前研究发现经验风险最小化可实现期望误差$O((d/n)"log(n/d))$（VC维为$d$），且所有已知最优学习器都可能被推离$Θ(d/n)$的最优率（标准PAC学习）。本文证明该额外对数项是本质性的：当$VC$维为1时，最坏情形下最小最大期望误差为$Θ(1/n)$；当$VC$维$≥2$时，为$Θ((d/n)"log(n/d))$。同样结果适用于小石维数$ d_{\mathrm L} $，表明干净的在线转批量率$O(d_{\mathrm L}/n)$也无法达成。因此，即便类具有有限误判界，添加正确标签的对抗样本仍会使学习难度增加对数因子。维度1的上界由一个简单非正规学习器达成，其分析借鉴了单排除图的留一法论证。所有下界均来自单一构造：一个显式类别与先验，其中两个目标假设在非零质量点上不同，却生成相同样本。
原文摘要 · Abstract (English)
A monotone adversary observes an i.i.d. labeled sample and appends a finite number of further examples of its choice, every one of them labeled correctly by the target hypothesis. The learner sees a uniform shuffle of the combined sample and is scored on the original distribution. Every example is correctly labeled, but the insertions depend on the clean sample, so the combined sample is not exchangeable. Larsen, Pabbaraju, and Shetty, who introduced this model, showed that empirical risk minimization attains expected error $O((d/n)\log(n/d))$ for classes of VC dimension $d$, and that every known optimal learner can be pushed away from the $Θ(d/n)$ rate, optimal for PAC learning. They asked whether the extra logarithm is an artifact of those particular algorithms or an inherent consequence of the lack of exchangeability. We show that this additional cost is inherent beyond VC dimension one. In the worst case over classes of VC dimension $d$ and over known finite insertion budgets, the minimax expected error is $Θ(1/n)$ at $d=1$ and $Θ((d/n)\log(n/d))$ for $d\geq 2$. The same rates hold with Littlestone dimension $d_{\mathrm L}$ in place of $d$, so the clean online-to-batch rate $O(d_{\mathrm L}/n)$ is unattainable as well. Thus, somewhat counterintuitively, adding correctly labeled examples can make learning harder by a logarithmic factor, even for classes that admit finite mistake bounds in online learning. The dimension-one upper bound is achieved by a simple improper learner whose analysis adapts the leave-one-out argument underlying the one-inclusion graph. All of our lower bounds are elementary and come from a single construction: an explicit class and prior on which two target hypothesis, which differ a point of nonnegligible mass, produce the same sample.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。