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

Ezra Edelman, Surbhi Goel · 2026

Read Reliable Abstention under Adversarial Injections: Tight Lower Bounds and New Upper Bounds by Ezra Edelman, Surbhi Goel (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-20111.txt.

Description

Online learners usually assume clean data, yet real streams mix ordinary examples with adversarially chosen ones, and the learner cannot tell which rounds are adversarial. A 2026 arXiv paper by Ezra Edelman and Surbhi Goel studies that adversarial injection model, where labels always agree with a fixed target concept and the learner may abstain from predicting.

Total error counts mistakes on rounds where the learner predicts plus incorrect abstentions on ordinary rounds. Earlier work showed oracle access to the underlying distribution yields combined error growing like dimension squared times log time. Distribution-agnostic algorithms reach only square-root growth for restricted classes. The paper settles whether that gap is fundamental. It proves a matching square-root lower bound for VC dimension one. The two information regimes are thus sharply separated. New upper bounds for the setting are also developed.

Catalog record

CREATOREzra Edelman, Surbhi Goel
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE76 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602-20111

Browse the full library · About the Tower of Babel