Towards optimal selection schedules for online active learning
Authors: Hugo Cui, Francesca Mignacco, Francesco Mori
Organizations: Université Paris-Saclay, CNRS, Laboratoire de mathématiques d’Orsay, 91405, Orsay, France · Joseph Henry Laboratories of Physics and Lewis–Sigler Institute, Princeton University, Princeton NJ 08544, USA · Initiative for the Theoretical Sciences, The Graduate Center, City University of New York, 365 Fifth Ave, New York NY 10016, USA · Center of Mathematical Sciences and Applications, Harvard University, 20 Garden Street, Cambridge MA 02138, USA
We consider the problem of online linear classification, where a stream of unlabeled samples is available, and annotation is costly. We investigate the optimal query policy, that prescribes whether and when a sample should be labeled and used for a training step, or instead discarded, so as to minimize a given objective. We focus on the realizable case, under Gaussian design, in the high-dimensional regime where data dimension and number of unlabeled samples grow proportionally. We consider two objectives: 1) the generalization error under a labeling budget, and 2) a cumulative cost function where mistakes have unit cost and queries cost Δ. We first show that the myopic policies that greedily minimize at all times the increment in the objective correspond to either small or intermediate-margin policies, that prescribe the selection of samples whose margins fall within certain intervals that shrink with time. Within this class, we numerically ascertain the optimal schedules for the selection thresholds that minimize the final values of the objectives. Taking inspiration from the myopic policy for the cumulative cost, we design a very simple query policy schedule that we compare to other proposed heuristics, on synthetic data and real medical image datasets. Finally, we discuss myopic policies for two-layer neural networks, and exemplify how naive margin-based policies can cease to be optimal.
Figures & tables
Figure 1: ( left ) Selection policies in the (t,ω) plane for the final-error minimization. Colored regions indicate pt(⋅)=1 . The myopic rule pϵ,t∘(⋅) ( 10 ) is shown in blue. The horizon-optimized intermediate-margin schedule pϵ,t⋆(⋅)=\mathds1[at⋆≤∣⋅∣≤bt⋆] ( 11 ), with at⋆ and bt⋆ set to minimize the final error, is shown in yellow. Parameters: γ=0.4 , η=0.5 , m0=0 , q0=0.15 , tF=20 . ( right ) Final generalization error εg,tF vs. query budget γ . Parameters: η=0.5 , m0=0 , q0=0.15 , tF=20 . Lines represent theoretical predictions while symbols mark single-trajectory SGD simulations at d=1000 . For details on the policies see Table 1 .
Figure 2: ( left ) Selection policies in the (t,ω) plane for cumulative-cost minimization. Colored regions indicate pt(⋅)=1 . The myopic rule pR,t∘(⋅) , greedily maximizing the cost decrease at each time, is shown in blue. The horizon-optimized inner-margin schedule pR,t⋆(⋅)=\mathds1[∣⋅∣≤bt] , with bt set to minimize the final cumulative cost, is shown in yellow. Parameters: Δ=0.3 , η=0.5 , m0=0 , q0=0.15 , tF=20 . ( right ) Cumulative cost RtF vs. the query price Δ . Parameters: η=0.5 , m0=0 , q0=0.15 , tF=20 . Lines represent theoretical predictions while symbols mark single-trajectory SGD simulations at d=1000 . Constant and optimal intermediate-margin families collapse to the inner-margin strategies once optimized. For details on the policies see Table 1 .
Figure 3: Cumulative cost Rt and number of queries Qt versus mistakes Mt (inset) for the first-order and adaptive b-sampling algorithms ( Cesa-Bianchi et al., 2004 ) (blue, orange), the logistic sampling algorithm ( Sculley, 2007 ) (green) and the active perceptron algorithm ( Dasgupta et al., 2005 ) (red), for binary classification on isotropic Gaussian data in dimension d=200 ( left ), and the pneumonia diagnosis task on chest X-ray images ( Kermany et al., 2018 ) ( right ). Purple curves mark a random (constant, margin-independent) strategy. Brown curves represent an inner margin policy with shrinking \nicefracKt threshold, with tunable bandwidth K . The query cost was set to Δ=0.2 . Hyperparameters were tuned in hindsight to minimize RtF , among a grid of 50 values. The black curve represents the simple thresholding strategy pt∘(⋅)=\mathds1[∣⋅∣≤\nicefracK∘t] , where K∘≈2.52 is the asymptotically optimal value prescribed by ( 15 ) for q0=0.1,η=2,Δ=0.2 . Shades mark one standard deviation over 5 trials, with the dataset reshuffled at each run.
Figure 4: Preactivations Wx selected by the myopic policy pR,t∘ ( 19 ) (blue) for Δ=0.46 and a naive inner-margin threshold on the network output pt(⋅)=\mathds1[∣v⊤g(⋅)∣≤0.35] (yellow). The weights W in ( 19 ) were extracted from a GeLU-activated two-layer neural network with r=2 hidden neurons, trained without data selection on the logistic loss for 1000 steps, at d=500 and η=1 . The untrained readout is v=(1,1)⊤ . The decision boundary of the network is represented in dashed lines.
Appendix figures & tables7 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 5: Summary statistics m and q as a function of training time t , for the constant policy pt(ω)=\mathds1∣ω∣<1 . Lines are obtained by numerically integrating the ODEs ( 7 ), while symbols mark numerical simulations of a single SGD trajectory at d=1000 . Parameters: η=0.5 , m0=0 , q0=0.15 , tF=10 .
Figure 6: Selection policies in the (t,ω) plane for final-error (top row) and cumulative-cost (bottom row) minimization. The colored regions indicate pt(ω)=1 . Parameters: η=0.5 , m0=0 , q0=0.15 , tF=20 .
Strategy
Policy pt(ω)
Variables optimized (Fig. 1 )
Variables optimized (Fig. 2 )
Myopic
\mathds1[St(ω)+ν<0]
one scalar ν , so that the query rate equals γ
nothing
Inner margin, constant
\mathds1[∣ω∣≤κ]
nothing: the budget fixes κ
one scalar κ
Inner margin, schedule
\mathds1[∣ω∣≤κt]
time-dependent κt
time-dependent κt
Intermediate margin, constant
\mathds1[a≤∣ω∣≤b]
one scalar a , with b fixed by the budget at each a
two scalars a,b
Intermediate margin, schedule
\mathds1[at≤∣ω∣≤bt]
time-dependent at and bt
time-dependent at and bt
Random
p , independent of ω and t
nothing: the budget forces p=γ
one scalar p
Appendix
Table 1: Policy families compared in Figs. 1 (right) and 2 (right).
Figure 7: Same as Fig. 3 (right), for Δ=0.1,0.4 .
Figure 8: Same as Fig. 3 , for the Covid-19 diagnosis task from chest X-ray scans Chowdhury et al. (2020) ; Rahman et al. (2021) , for Δ=0.2,0.4 .
Figure 9: Same as Fig. 3 (left), for Δ=0.1,0.4 .
Figure 10: Test error ϵg,t as a function of training time, with online SGD with logistic loss, under the myopic policy pR,t∘ ( 13 ). Solid lines represent single runs in dimension d=100 , dashed lines represent the theoretical prediction for the t→∞ asymptotics of Conjecture E.1 .
Data acquisition is a major bottleneck for learning in real-time streams: analysts must decide on the fly which labels to purchase while respecting a rolling budget. However, existing online active learning rarely unifies pricing, information gain, and rolling budget constraints under concept drift. We introduce QueryMarket, a market-inspired framework that queries each incoming data point based on its estimated utility to the model and its price. Within this framework, we propose OVBAL (online variance-based active learning), which integrates data pricing with information-driven selection by estimating each sample's marginal utility via a D-optimality criterion with exponential forgetting and executing cost-aware purchases under rolling budget constraints. OVBAL yields a simple, fully online decision rule that adapts to nonstationary streams and heterogeneous label costs. Experiments on synthetic data and a real-world solar power generation forecasting task show that OVBAL is particularly effective under seller-centric pricing and yields a more favorable long-run error-cost trade-off in the real-world task under both pricing schemes.
Xiwen Huang, Pierre Pinson
Dyson School of Design Engineering, Imperial College London, London, SW7 2DB, U.K. · Dyson School of Design Engineering, Imperial College London, London, U.K. · Halfspace (part of Accenture) +2
We study how a limited labeling budget should be allocated to minimize multiclass zero-one classification risk. We consider parametric classification problems in which features are observed for all sampling units while class labels can be acquired selectively. By combining the Fisher information supplied by an acquired label with the local geometry of multiclass excess risk, we derive an acquisition criterion that minimizes the leading asymptotic coefficient of expected multiclass excess risk. The resulting rule values a label according to how strongly its information is aligned with parameter directions that perturb the active Bayes decision boundary, rather than according to posterior uncertainty or global parameter information alone. We characterize the oracle acquisition design, establish its threshold structure, and derive face-specific and cost-sensitive extensions. An analytic example shows that posterior uncertainty and classification value can produce different, and even reversed, acquisition rankings. We further develop a two-stage adaptive procedure that attains the oracle leading-risk criterion under regularity conditions and provide explicit results for Gaussian discriminant analysis. Three-class QDA experiments illustrate the resulting acquisition geometry, while an application to the six-class Statlog Landsat Satellite data shows that classification-risk acquisition can differ materially from both uncertainty-based acquisition and the complete-classification-information comparator. The adaptive classification-risk design attains lower mean error than this Fisher comparator across the labeling budgets considered, although it does not uniformly outperform entropy or margin sampling and differences among the targeted strategies become small as the labeling budget increases.
F. Setoudehtanzangi, Geoffrey J. McLachlan
Dipartimento di Scienze Statistiche, Universit`a di Padova, Padova, Italy · School of Mathematics and Physics, The University of Queensland, Australia
Active Learning (AL) is commonly used in applications where labeling data is expensive or time-consuming. In practice, however, labels are often noisy due to varying labeler expertise and annotation uncertainty, especially for complex or ambiguous samples. Learning from such imperfectly labeled data can degrade classifier performance. We propose an AL framework that explicitly accounts for label noise by optimally assigning labelers and selecting samples to minimize labeling error. Our approach, called OLAS (Optimal Labeler Assignment and Sampling), uses a noise model that depends on both labeler accuracy and model uncertainty to guide these decisions. We develop two tractable optimization formulations: one for assigning samples to labelers to minimize worst-case noise, and another for selecting samples while controlling overall label noise. Theoretical results provide closed-form solutions under mild conditions. Empirical evaluations on benchmark datasets and a real-world warranty claim classification problem show that OLAS achieves the highest or near-highest classification accuracy among existing AL strategies across most settings, using only a single label per sample.
Pouya Ahadi, Blair Winograd, Camille Zaug +3
School of Industrial and Systems Engineering Georgia Institute of Technology Atlanta, GA 30332, USA · Ford Motor Company