Agnostic Online Learning with Reliable Abstention

We study online learning in the adversarial injection model [GHMS23], where each instance is either drawn i.i.d. from an unknown distribution or is an arbitrary adversarial injection. The learner never knows which rounds are adversarial, but may abstain without penalty on adversarial injections. The learner's goal is to make few total misclassifications and few abstentions on i.i.d. instances. This model lies between classical statistical learning, governed by the VC dimension, and adversarial online learning, governed by the Littlestone dimension. Unlike prior work, which has largely focused on the realizable setting, we consider an agnostic formulation that allows arbitrary labels. We present an online algorithm that guarantees sublinear excess misclassification error and sublinear abstention error, against oblivious and adaptive adversaries, for function classes that admit bounded bracketing number witnessed by brackets of bounded VC dimension. Our algorithm is distribution-independent and does not require prior knowledge of the distribution. As corollaries, we obtain new learning guarantees for halfspaces (linear classifiers) and richer classes such as feed-forward neural networks with threshold activations.