Reliable Learning via Abstention
April 3, 2026 @ 11:00 am - 12:00 pm
Surbhi Goel (University of Pennsylvania)
E18-304
Event Navigation
Abstract: When a learning system is deployed, the data it encounters may no longer resemble its training data. The nature of this shift is typically unknown, whether due to changing conditions, adversarial manipulation, or simply a new deployment context. Without assumptions on the shift, reliable prediction is in general impossible, as the test distribution may bear no resemblance to the training data. This talk studies a simple but powerful response: allow the learner to abstain from prediction when it lacks sufficient evidence. The goal is to guarantee that whenever the learner does predict, it is usually correct, while still requiring it to predict on most benign inputs.
I will begin with selective classification, where a classifier trained on one distribution must achieve low error on a different, unknown test distribution, while abstaining infrequently on the original distribution. I will then present a generalization to sequential decision-making: an agent trained on expert demonstrations in one environment must decide when to stop acting in a new environment with arbitrarily different dynamics. By validating entire trajectories rather than individual steps, we achieve sample complexity that is independent of the horizon. A key question across both settings is computational efficiency: all prior algorithms for selective classification were intractable even for basic classes such as halfspaces. I will describe how spectral outlier-removal techniques yield the first efficient algorithms for halfspaces, decision trees, and related classes under standard assumptions on the training distribution. Time permitting, I will discuss a complementary result in online learning with adversarial data corruption, where abstention provably enables guarantees that are impossible without it.
Based on joint works with Ezra Edelman, Steve Hanneke, Shay Moran, Jonathan Pei, Abhishek Shetty, Kostas Stavropoulos, Arsen Vasilyan, and James Wang.
