ResearchPod Summary
In standard statistical learning, we assume data are i.i.d. or at least exchangeable. However, real-world datasets are often curated through filtering, reweighting, or augmentation. The monotone adversary model isolates the impact of such curation by allowing an adversary to observe a clean i.i.d. sample and append a finite number of additional examples, provided every appended example is labeled correctly by the target hypothesis. Because the adversary's choices depend on the clean sample, the resulting dataset loses the exchangeability property that standard generalization bounds rely on.
Prior work by Larsen, Pabbaraju, and Shetty (2026) showed that empirical risk minimization (ERM) achieves an error rate of O((d/n)log(n/d)) for classes of VC dimension d, but they could not determine if this logarithmic gap was an artifact of specific algorithms or an inherent statistical difficulty. This paper settles the question by establishing matching lower bounds for all learners, including improper ones, across all VC dimensions d >= 2. The author uses an explicit construction of hypothesis classes and priors where two target hypotheses, differing on a point of significant mass, produce identical samples when the adversary is allowed to adapt its insertions.
This result provides the first algorithm-independent proof that data curation—even when perfectly labeled—can make a learning problem strictly harder. It reverses the classical intuition where ERM is often considered suboptimal; here, ERM is actually an optimal learner. It also highlights that the "clean" rate of O(d/n) is fragile and sensitive to the loss of exchangeability, suggesting that practitioners should be cautious when applying standard generalization guarantees to datasets that have been adaptively modified.
AI-generated third-party summary by ResearchPod. Not official content or an endorsement by the paper authors or affiliated organizations.