Adding Correctly Labeled Examples Provably Makes Learning Harder: Monotone-Adversary Rate Pinned at Θ((d/n)log(n/d))

arXiv 2608.06337·medium signalXBlueskyLinkedInCopy link

This paper (2608.06337, submitted 2026-08-06 by Anay Mehrotra) settles an open question from Larsen, Pabbaraju, and Shetty about the monotone-adversary model, where an adversary appends extra examples that are all labeled correctly by the target hypothesis but chosen after seeing the clean sample — breaking exchangeability. The extra logarithmic factor turns out to be inherent, not an algorithmic artifact: minimax expected error is Θ(1/n) at VC dimension 1 but Θ((d/n)log(n/d)) for d≥2, and the same rates hold with Littlestone dimension substituted, so the clean online-to-batch O(d_L/n) rate is unattainable too. The counterintuitive takeaway is that correctly labeled data can degrade the achievable rate purely by correlating with the clean sample.