Research map / Bandits and online learning / Online convex optimization and games

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

NeurIPS 2026 · Bandits and online learning › Online convex optimization and games · approach: Online learning with feedback graphs

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Shows an Omega(sqrt T) lower bound for distribution-agnostic learning with abstention in the adversarial injection model at VC dimension 1, and gives a potential-based framework yielding T^{1-1/k} rates via inference dimension and a T^{2/3} bound for halfspaces in R^2 via certificate dimension.

Problem

Online learning with abstention under adversarial injections (clean labels): the learner must minimize mistakes plus incorrect abstentions on i.i.d. rounds without knowing the distribution D or which rounds are injected; prior distribution-agnostic rates were sqrt(T) only for restricted classes, lea

Approach

A leave-k-out potential over labeled history, with a learner that predicts only when one label would cause a large potential drop; robust witnesses control how many i.i.d. points can be abstained upon via exchangeability. Instantiated by inference dimension and a new certificate dimension relaxation.

Key results

• Lower bound: every distribution-agnostic learner incurs Omega(sqrt T) expected combined error for a VC-1 class.
• Inference dimension k gives combined error tilde O(T^{1-1/k}); halfspaces in R^2 have certificate dimension 3, giving tilde O(T^{2/3}) distribution-agnostic.
• Potential learner's mistake count is bounded deterministically by c T^k/(k! alpha), with expected abstentions bounded by e m (alpha + c T^{k-1})^{1/k} log T.

Surprising findings

• Halfspaces in R^2, shown not robustly learnable under clean-label attacks without abstention, become learnable with sublinear combined error when abstention is allowed.

Limitations

• Lower bound uses an oblivious adversary; stronger adaptive lower bounds are open.
• Halfspace certificate result holds only when the learner starts with a sample of each label (technical condition).
• Halfspaces in R^d for d>=3 remain open; the upper bound relies on exchangeability-based analysis.

Experimental setup

Metrics: expected combined error

Baselines: Goel et al. 2024 distribution-agnostic algorithms known-D O(d^2 log T) algorithm

Builds on: adversarial injection model (Goel et al. 2024) inference dimension (Kane et al.) one-inclusion graph

Closest papers by meaning

• Agnostic Online Learning with Reliable Abstention (NeurIPS 2026 · similarity 0.93)
• Adversarial Resilience in Sequential Prediction via Abstention (NeurIPS 2023 · similarity 0.88)
• Theoretically Principled Trade-off between Robustness and Accuracy (ICML 2019 · similarity 0.87)
• Certified Adversarial Robustness with Additive Noise (NeurIPS 2019 · similarity 0.87)
• Towards Better Understanding of Training Certifiably Robust Models against Adversarial Examples (NeurIPS 2021 · similarity 0.87)
• Expressive Losses for Verified Robustness via Convex Combinations (ICLR 2024 · similarity 0.85)