![[2602.20111] Reliable Abstention under Adversarial Injections: Tight Lower Bounds and New Upper Bounds](https://arxiv.org/static/browse/0.3.4/images/arxiv-logo-fb.png){kind=logo}
[2602.20111] Reliable Abstention under Adversarial Injections: Tight Lower Bounds and New Upper Bounds
Summary
This paper explores reliable abstention in online learning under adversarial injections, presenting new lower and upper bounds for error rates in machine learning models.
Why It Matters
Understanding how machine learning models can effectively handle adversarial inputs is crucial for developing robust systems. This research provides significant insights into the limitations and capabilities of learning algorithms in adversarial settings, which is vital for applications in AI safety and security.
Key Takeaways
- Establishes a tight lower bound of Ω(√T) for VC dimension 1 in adversarial settings.
- Introduces a potential-based framework using robust witnesses for improved prediction resilience.
- Demonstrates new distribution-agnostic bounds for halfspaces, enhancing understanding of their learnability under adversarial conditions.
Computer Science > Machine Learning arXiv:2602.20111 (cs) [Submitted on 23 Feb 2026] Title:Reliable Abstention under Adversarial Injections: Tight Lower Bounds and New Upper Bounds Authors:Ezra Edelman, Surbhi Goel View a PDF of the paper titled Reliable Abstention under Adversarial Injections: Tight Lower Bounds and New Upper Bounds, by Ezra Edelman and 1 other authors View PDF HTML (experimental) Abstract:We study online learning in the adversarial injection model introduced by [Goel et al. 2017], where a stream of labeled examples is predominantly drawn i.i.d.\ from an unknown distribution $\mathcal{D}$, but may be interspersed with adversarially chosen instances without the learner knowing which rounds are adversarial. Crucially, labels are always consistent with a fixed target concept (the clean-label setting). The learner is additionally allowed to abstain from predicting, and the total error counts the mistakes whenever the learner decides to predict and incorrect abstentions when it abstains on i.i.d.\ rounds. Perhaps surprisingly, prior work shows that oracle access to the underlying distribution yields $O(d^2 \log T)$ combined error for VC dimension $d$, while distribution-agnostic algorithms achieve only $\tilde{O}(\sqrt{T})$ for restricted classes, leaving open whether this gap is fundamental. We resolve this question by proving a matching $\Omega(\sqrt{T})$ lower bound for VC dimension $1$, establishing a sharp separation between the two information regimes. O...
