Abstract
Uncertainty sampling is a prevalent active learning algorithm that queries sequentially the annotations of data samples which the current prediction model is uncertain about. However, the usage of uncertainty sampling has been largely heuristic: (i) There is no consensus on the proper definition of "uncertainty" for a specific task under a specific loss; (ii) There is no theoretical guarantee that prescribes a standard protocol to implement the algorithm, for example, how to handle the sequentially arrived annotated data under the framework of optimization algorithms such as stochastic gradient descent. In this work, we systematically examine uncertainty sampling algorithms under both stream-based and pool-based active learning. We propose a notion of equivalent loss which depends on the used uncertainty measure and the original loss function and establish that an uncertainty sampling algorithm essentially optimizes against such an equivalent loss. The perspective verifies the properness of existing uncertainty measures from two aspects: surrogate property and loss convexity. Furthermore, we propose a new notion for designing uncertainty measures called "loss as uncertainty". The idea is to use the conditional expected loss given the features as the uncertainty measure. Such an uncertainty measure has nice analytical properties and generality to cover both classification and regression problems, which enable us to provide the first generalization bound for uncertainty sampling algorithms under both stream-based and pool-based settings, in the full generality of the underlying model and problem. Lastly, we establish connections between certain variants of the uncertainty sampling algorithms with risk-sensitive objectives and distributional robustness, which can partly explain the advantage of uncertainty sampling algorithms when the sample size is small.
Introduction
In machine learning, Active Learning aims to select the most informative data points for labeling to maximize model performance with minimal annotation cost. The most common strategy, Uncertainty Sampling, involves querying labels for examples where the model's prediction is most uncertain. Despite its widespread use, uncertainty sampling has historically lacked a rigorous theoretical foundation. There is no consensus on defining "uncertainty" across different tasks (e.g., classification vs. regression), and few guarantees exist regarding the convergence of models updated with these biased samples. This work addresses these gaps by providing a mathematical framework for uncertainty sampling.
Methodology: The Stream-Based Protocol
The authors formalize uncertainty sampling in a stream-based setting, where data points arrive sequentially. The decision to query a label is based on an uncertainty function $U(\theta; X)$.
As shown in Algorithm 1, the model parameters $\theta$ are updated using stochastic gradient descent only when a label is queried. The probability of querying is determined by the uncertainty measure, effectively weighting the gradient updates.
The Equivalent Loss Framework
A central contribution of this work is the concept of Equivalent Loss. The authors demonstrate that performing gradient descent on samples chosen with probability $U$ is mathematically equivalent to performing SGD on a modified loss function, $\tilde{l}$. This equivalent loss is defined through a partial differential equation (PDE) linking the uncertainty measure, the original loss, and the model parameters.
Figure 3 illustrates how the equivalent loss $\tilde{l}$ behaves under different conditions. This perspective helps explain why certain heuristic measures, like threshold-based sampling, can fail: they may lead to non-convex equivalent losses, causing the model to get trapped in local minima unless initialized with a strong "warm start."
Loss as Uncertainty
The authors propose a unified principle: Loss as Uncertainty. By using the conditional expected loss as the uncertainty measure, the equivalent loss becomes the square of the original loss. This principle provides a consistent approach for both classification and regression. In regression, for instance, estimated mean-squared error can serve as the uncertainty metric, providing a "plug-and-play" solution for active learning in continuous domains.
Key Results and Robustness
The framework enables the derivation of the first generalization bounds for uncertainty sampling in both stream-based and pool-based settings. The model achieves a convergence rate of $O(1/\sqrt{T})$ for convex losses, matching passive learning while requiring significantly fewer queries. Empirical validation on datasets such as Dry Bean, Covertype, and Forest Fires confirms the theory, with the "loss-as-uncertainty" approach consistently outperforming uniform sampling.
Furthermore, the paper establishes a link between uncertainty sampling and Distributionally Robust Optimization (DRO). This suggests that uncertainty sampling does more than save labels; it enhances model robustness against "worst-case" data distributions, explaining its advantages even when sample sizes are small.
Conclusion
By moving from heuristics to a rigorous theoretical framework, this work provides a standard protocol for active learning. Future research will address the practical challenges of estimating conditional expected loss (calibration) and extending these theoretical guarantees to non-convex deep learning models.
Summary updated