这篇论文把单调对抗者模型的误差速率定性了：d=1是Θ(1/n)，d≥2多一个log因子，证明很直接。
论文研究单调对抗者（monotone adversary）插入额外正确标注样本后的学习问题，回答 Larsen、Pabbaraju 和 Shetty 提出的开问题。作者证明，VC 维 d=1 时最小最大期望误差为 Θ(1/n)，d≥2 时为 Θ((d/n)log(n/d))，因此额外对数因子是内在代价。同样结论适用于 Littlestone 维 d_L，说明在线学习可达到的 O(d_L/n) 批量速率无法实现。一维上界由简单非恰当学习器配合留一论证达到；下界来自单个显式构造。
Optimal Rates for Learning with Monotone Adversaries
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.