Search papers, labs, and topics across Lattice.
This paper studies online learning with abstention under adversarial injections, where a learner faces a stream of mostly i.i.d. data interspersed with adversarial examples, and aims to minimize combined error from mistakes and incorrect abstentions. The authors resolve the open question of the gap between distribution-specific and distribution-agnostic algorithms by proving a tight $Ω(\sqrt{T})$ lower bound for VC dimension 1, demonstrating a fundamental separation. They also introduce a potential-based framework using robust witnesses and the novel concept of certificate dimension, achieving improved distribution-agnostic upper bounds, including $\tilde{O}(T^{2/3})$ for halfspaces in $\mathbb{R}^2$.
Even with the option to abstain, distribution-agnostic learners in adversarial settings are provably worse than those with distribution knowledge, but a new "certificate dimension" approach offers a path to tighter bounds.
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 $Ω(\sqrt{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 \emph{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) \emph{inference dimension}, yielding combined error $\tilde{O}(T^{1-1/k})$ for classes of inference dimension $k$, and (2) \emph{certificate dimension}, a new relaxation we introduce. As an application, we show that halfspaces in $\mathbb{R}^2$ have certificate dimension $3$, obtaining the first distribution-agnostic bound of $\tilde{O}(T^{2/3})$ for this class. This is notable since [Blum et al. 2021] showed halfspaces are not robustly learnable under clean-label attacks without abstention.
