Active Learning via Regression Beyond Realizability
2025
Read Active Learning via Regression Beyond Realizability (2025) 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-2506-00316.txt.
Introduction
In active learning, a model asks for labels on the examples it most needs, saving costly human effort. Most methods assume the true pattern lies inside the model family, an assumption real data often breaks. Atul Ganju and co-authors present a 2025 framework that drops that assumption for multi-class classification.
Their method builds on surrogate risk minimization, fitting stand-in losses instead of raw error. As long as the model family is convex in shape, they show, label and sample costs stay comparable to the older guarantees. Older algorithms can be shown to fail in the looser setting where the new one still works. The algorithm proceeds in epochs, refitting on all queried data and combining the epoch models into its final classifier.
Catalog record
| YEAR | 2025 |
|---|---|
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 83 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-00316
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Active Learning via Regression Beyond Realizability Abstract 1 Introduction We study active learning for multi-class classification in the statistical learning framework, where the learner has access to a large pool of unlabeled data and can query labels from an oracle. The objective is to learn an accurate classifier while minimizing the number of label queries—that is, to simultaneously achieve low excess classification risk and label complexity. A promising recent approach to active learning is to reduce the problem to regression [ KAH+21 , SSSW23 , ZN22 , HY19 ] . Rather than directly optimizing the classification loss, these methods relax the problem to one of minimizing a convex, differentiable surrogate loss over a class of real-valued functions, thereby shifting the objective to approximating a real-valued target function whose associated classifier is expected to perform well under the original classification loss. This formulation enables the hypothesis class to encode additional structure—such as smoothness, margin, or regularization—that reflects assumptions about the target function, ultimately enabling the learning of richer, more expressive model classes. Furthermore, the differentiability of the surrogate facilitates the use of efficient gradient-based optimization techniques, which are essential for training complex models in modern machine learning systems. While surrogate-based methods have become a cornerstone of modern learning systems due to their flexibility and compatibility with gradient-based optimization, their theoretical guarantees—both in the active setting [ KAH+21 , SSSW23 , ZN22 , HY19 ] and even in the passive setting [ BJM06 ] —have critically relied on the realizability assumption: that the minimizer of the surrogate risk lies within the function class accessible to the learner. However, assuming that a setting is realizable is often too strong to hold in practice. To address this limitation, we develop a regression-based active learning algorithm that matches the accuracy and label complexity of prior realizability-based methods, while operating under conditions strictly milder than realizability. To this end, we first establish a passive learning result that extends the realizability-based theory of [ BJM06 ] . Specifically, we show that for convex function classes, there exists a broad family of classification-calibrated surrogate losses for which the excess classification risk can be upper bounded by the excess surrogate risk, provided a structural condition holds: namely, that the bias of the best-in-class function is lower bounded by a non-decreasing function of the bias of the surrogate risk minimizer. To demonstrate the generality of this condition, we construct an example in which realizability, and even approximate realizability, fails, yet our condition remains satisfied. Under additional distributional assumptions—such as those introduced by Massart and Tsybakov—our analysis yields sharper convergence rates, analogous to those obtained in the realizable setting by [ BJM06 ] . While this extension is conceptually simple, it serves as the foundation for our main contribution. Specifically, we design a novel, improper active learning algorithm for multi-class classification. Our algorithm achieves guarantees comparable to existing realizability-dependent, surrogate-based methods yet operates under a natural extension of our passive learning assumption that is strictly weaker than realizability. In contrast, existing algorithms such as those of [ HY19 , ZN22 ] fundamentally rely on realizability, and their analyses break down in the misspecified setting. Our algorithm is the first to offer surrogate-based active learning guarantees in such generality. Related Work: The study of active learning initially focused on the noise-free setting, where the label distribution is assumed to be perfectly consistent with some classifier in a known hypothesis class [ FSST97 , Das04 , Das05 , HY15 ] . Foundational contributions in this regime include the general label complexity bounds for arbitrary hypothesis classes established by [ Das05 ] , and the minimax rates derived by [ HY15 ] . As the noise-free setting was increasingly recognized as too restrictive, attention shifted to the agnostic setting, where no assumptions are made on the label distribution. The work of [ BBL06 ] introduced the disagreement-based framework and proposed the first algorithm for agnostic active learning with a nontrivial label complexity bound, as was later analyzed in [ Han07 ] . However, subsequent work showed that in the fully agnostic regime, active learning cannot, in general, significantly outperform passive learning [ Kä06 , Hsu10 , Han14 ] . To circumvent this limitation, a line of research focused on characterizing label complexity as a function of distributional noise. This led to significant improvements in label complexity under structured noise models [ CN08 , Han09 , Kol10 , Han11 , LCK17 ] . A particularly notable result by [ HY15 ] established minimax label complexity bounds for a broad class of noise models, demonstrating that under Tsybakov noise, active learning can provably outperform passive learning for any VC class. Although these results establish strong theoretical foundations, they rely on idealized algorithmic primitives such as classification oracles and are limited to relatively simple hypothesis classes. To address these shortcomings, a series of works explored surrogate loss minimization as an alternative framework for active learning, with several promising results under the realizability assumption [ AT07 , Min12 , HY19 , KAH+21 , ZN22 ] . Among these, the work of [ HY19 ] is most directly related to ours. Their key insight is that once the sign of the optimal predictor is known at a given point, its exact value becomes irrelevant for classification. This allows their algorithm to focus exclusively on the region where the sign remains uncertain. In particular, it operates by maintaining a version space that is progressively refined by optimizing the empirical surrogate risk over this region of uncertainty. As such, their algorithm obtains a good approximation of the optimal predictor and therefore is able to infer the sign at additional inputs with increasing confidence. Although this insight still holds in the misspecified setting, their algorithmic approach fundamentally relies on the realizability assumption. In fact, the authors remark that identifying a concise, a priori condition under which their guarantees would extend to the non-realizable case would require a substantially different algorithmic approach. In this respect, our algorithm departs significantly from theirs: rather than refining a single version space, we employ an improper learning strategy that constructs a piecewise aggregation of classifiers, each operating on a region of the input space where it maintains high confidence. Also relevant are the works of [ BJM06 ] , [ LRS15 ] , and [ ZN22 ] , each of which contributes essential mathematical ingredients to our analysis. The results of [ BJM06 ] provide the foundation for bounding classification excess risk in terms of surrogate excess risk. The work of [ LRS15 ] offers sharp bounds on the excess surrogate risk via localized Rademacher complexity. Finally, [ ZN22 ] introduce a framework for bounding label complexity in terms of the disagreement coefficient. As both the results of [ HY19 ] and [ ZN22 ] are for surrogate-minimization based active binary classification, we provide a more detailed comparison with their results later in the paper. Further related is the recent work of [ SSSW23 ] , which develops surrogate-based regression algorithms in the setting of selective sampling—an online variant of active learning in which the data generation process may be arbitrary, even adversarial. Separately, a number of works have investigated nonparametric active learning under smoothness and regularity