Active Learning via Regression Beyond Realizability

2025/05/31 by Ganju, Atul, S.V.B. Aiyer, V. Sriraman +4
Computer Science · Decision Sciences · #Machine Learning and Algorithms #Advanced Bandit Algorithms Research #Machine Learning and Data Classification

paper · pdf · doi:10.48550/arxiv.2506.00316

Abstract

We present a new active learning framework for multiclass classification based on surrogate risk minimization that operates beyond the standard realizability assumption. Existing surrogate-based active learning algorithms crucially rely on realizability\unicodex2014the assumption that the optimal surrogate predictor lies within the model class\unicodex2014limiting their applicability in practical, misspecified settings. In this work we show that under conditions significantly weaker than realizability, as long as the class of models considered is convex, one can still obtain a label and sample complexity comparable to prior work. Despite achieving similar rates, the algorithmic approaches from prior works can be shown to fail in non-realizable settings where our assumption is satisfied. Our epoch-based active learning algorithm departs from prior methods by fitting a model from the full class to the queried data in each epoch and returning an improper classifier obtained by aggregating these models.

Citations

• Selective Sampling and Imitation Learning via Online Regression
• Efficient Active Learning with Abstention
• Nuances in Margin Conditions Determine Gains in Active Learning
• Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective
• Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles
• Adaptivity to Noise Parameters in Nonparametric Active Learning
• Minimax Analysis of Active Learning
• Plug-in Approach to Active Learning
• Fast learning rates for plug-in classifiers under the margin condition
• Decision theoretic generalizations of the PAC model for neural net and other learning applications

Related

• Beating the Minimax Rate of Active Learning with Prior Knowledge
• Convergence Rates of Active Learning for Maximum Likelihood Estimation
• Active Robust Learning
• Transductive Active Learning: Theory and Applications
• Learning Active Learning from Data