# Reliable Abstention under Adversarial Injections: Tight Lower Bounds and New Upper Bounds

arXiv: https://arxiv.org/abs/2602.20111 · HTML: https://mlsanity.com/paper/2602.20111/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 33 references that are in the map.
- First posted on arXiv 23 Feb 2026.

## Builds on (most cited first, 21 of 21)

- [Poison Frogs! Targeted Clean-Label Poisoning Attacks on Neural Networks](https://mlsanity.com/paper/1804.00792/) (2018)
- [Beyond Perturbations: Learning Guarantees with Arbitrary Adversarial Test Examples](https://mlsanity.com/paper/2007.05145/) (2020)
- [Online Learning with Abstention](https://mlsanity.com/paper/1703.03478/) (2017)
- [Active classification with comparison queries](https://mlsanity.com/paper/1704.03564/) (2017)
- [Testable Learning with Distribution Shift](https://mlsanity.com/paper/2311.15142/) (2023)
- [The Power of Comparisons for Actively Learning Linear Classifiers](https://mlsanity.com/paper/1907.03816/) (2019)
- [Fast Rates for Online Prediction with Abstention](https://mlsanity.com/paper/2001.10623/) (2020)
- [Noise-tolerant, Reliable Active Classification with Comparison Queries](https://mlsanity.com/paper/2001.05497/) (2020)
- [Fast classification rates without standard margin assumptions](https://mlsanity.com/paper/1910.12756/) (2019)
- [Efficient Learning with Arbitrary Covariate Shift](https://mlsanity.com/paper/2102.07802/) (2021)
- [Robust learning under clean-label attack](https://mlsanity.com/paper/2103.00671/) (2021)
- [Tolerant Algorithms for Learning with Arbitrary Covariate Shift](https://mlsanity.com/paper/2406.02742/) (2024)
- [Learning Intersections of Halfspaces with Distribution Shift: Improved Algorithms and SQ Lower Bounds](https://mlsanity.com/paper/2404.02364/) (2024)
- [2 Notes on Classes with Vapnik-Chervonenkis Dimension 1](https://mlsanity.com/paper/1507.05307/) (2015)
- [Adversarial Resilience in Sequential Prediction via Abstention](https://mlsanity.com/paper/2306.13119/) (2023)
- [The Extended Littlestone's Dimension for Learning with Mistakes and Abstentions](https://mlsanity.com/paper/1604.06162/) (2016)
- [Efficient Discrepancy Testing for Learning with Distribution Shift](https://mlsanity.com/paper/2406.09373/) (2024)
- [Generalized comparison trees for point-location problems](https://mlsanity.com/paper/1804.08237/) (2018)
- [Active Learning with Simple Questions](https://mlsanity.com/paper/2405.07937/) (2024)
- [Learning with Monotone Adversarial Corruptions](https://mlsanity.com/paper/2601.02193/) (2026)
- [Adversarial Resilience against Clean-Label Attacks in Realizable and Noisy Settings](https://mlsanity.com/paper/2504.13966/) (2025)

## Built on by (most cited first, 3 of 3)

- [Bagging Robustly Learns VC Classes with Linear Sample Complexity](https://mlsanity.com/paper/2608.13514/) (2026)
- [Certify or Refuse: A Cross-Model Map for Selective Risk Control with Coverage Floors under Covariate Shift](https://mlsanity.com/paper/2608.10893/) (2026)
- [When Does More Correct Data Hurt? Insertion-Stability and the Limits of Dimension-Based Theory](https://mlsanity.com/paper/2608.14020/) (2026)

## Abstract (arXiv)

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 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(d2 log T) combined error for VC dimension d, while distribution-agnostic algorithms achieve only tildeO(√T) for restricted classes, leaving open whether this gap is fundamental. We resolve this question by proving a matching Omega(√T) lower bound for VC dimension 1, establishing a sharp separation between the two information regimes. On the algorithmic side, we introduce a potential-based framework driven by robust witnesses, small subsets of labeled examples that certify predictions while remaining resilient to adversarial contamination. We instantiate this framework using two combinatorial dimensions: (1) inference dimension, yielding combined error tildeO(T1-1/k) for classes of inference dimension k, and (2) certificate dimension, a new relaxation we introduce. As an application, we show that halfspaces in ℝ2 have certificate dimension 3, obtaining the first distribution-agnostic bound of tildeO(T2/3) for this class. This is notable since [Blum et al. 2021] showed halfspaces are not robustly learnable under clean-label attacks without abstention.