Towards optimal selection schedules for online active learning

Hugo Cui; Francesca Mignacco; Francesco Mori

stat.MLOct 16, 2026

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

Abstract

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,\omega)

plane for the final-error minimization. Colored regions indicate

p_{t}(\cdot)=1

. The myopic rule

p^{\circ}_{\epsilon,t}(\cdot)

( 10 ) is shown in blue. The horizon-optimized intermediate-margin schedule

p^{\star}_{\epsilon,t}(\cdot)=\mathds{1}[a_{t}^{\star}\leq|\cdot|\leq b_{t}^{\star}]

( 11 ), with

a_{t}^{\star}

and

b_{t}^{\star}

set to minimize the final error, is shown in yellow. Parameters:

\gamma=0.4

\eta=0.5

m_{0}=0

q_{0}=0.15

t_{F}=20

. ( right ) Final generalization error

\varepsilon_{g,t_{F}}

vs. query budget

\gamma

. Parameters:

\eta=0.5

m_{0}=0

q_{0}=0.15

t_{F}=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,\omega)

plane for cumulative-cost minimization. Colored regions indicate

p_{t}(\cdot)=1

. The myopic rule

p^{\circ}_{\mathcal{R},t}(\cdot)

, greedily maximizing the cost decrease at each time, is shown in blue. The horizon-optimized inner-margin schedule

p^{\star}_{\mathcal{R},t}(\cdot)=\mathds{1}[|\cdot|\leq b_{t}]

, with

b_{t}

set to minimize the final cumulative cost, is shown in yellow. Parameters:

\Delta=0.3

\eta=0.5

m_{0}=0

q_{0}=0.15

t_{F}=20

. ( right ) Cumulative cost

\mathcal{R}_{t_{F}}

vs. the query price

\Delta

. Parameters:

\eta=0.5

m_{0}=0

q_{0}=0.15

t_{F}=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 .

Panel of Figure 3 — Figure 3: Cumulative cost $\mathcal{R}_{t}$ and number of queries $\mathcal{Q}_{t}$ versus mistakes $\mathcal{M}_{t}$ (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 $\nicefrac{{K}}{{t}}$ threshold, with tunable bandwidth $K$ . The query cost was set to $\Delta=0.2$ . Hyperparameters were tuned in hindsight to minimize $\mathcal{R}_{t_{F}}$ , among a grid of $50$ values. The black curve represents the simple thresholding strategy $p^{\circ}_{t}(\cdot)=\mathds{1}[|\cdot|\leq\nicefrac{{K^{\circ}}}{{t}}]$ , where $K^{\circ}\approx 2.52$ is the asymptotically optimal value prescribed by ( 15 ) for $q_{0}=0.1,\eta=2,\Delta=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

p^{\circ}_{\mathcal{R},t}

( 19 ) (blue) for

\Delta=0.46

and a naive inner-margin threshold on the network output

p_{t}(\cdot)=\mathds{1}[|v^{\top}g(\cdot)|\leq 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

\eta=1

. The untrained readout is

v=(1,1)^{\top}

. 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

p_{t}(\omega)=\mathds{1}_{|\omega|<1}

. Lines are obtained by numerically integrating the ODEs ( 7 ), while symbols mark numerical simulations of a single SGD trajectory at

d=1000

. Parameters:

\eta=0.5

m_{0}=0

q_{0}=0.15

t_{F}=10

Figure 6: Selection policies in the

(t,\omega)

plane for final-error (top row) and cumulative-cost (bottom row) minimization. The colored regions indicate

p_{t}(\omega)=1

. Parameters:

\eta=0.5

m_{0}=0

q_{0}=0.15

t_{F}=20

Strategy	Policy $p_{t}(\omega)$	Variables optimized (Fig. 1 )	Variables optimized (Fig. 2 )
Myopic	$\mathds{1}[S_{t}(\omega)+\nu<0]$	one scalar $\nu$ , so that the query rate equals $\gamma$	nothing
Inner margin, constant	$\mathds{1}[\|\omega\|\leq\kappa]$	nothing: the budget fixes $\kappa$	one scalar $\kappa$
Inner margin, schedule	$\mathds{1}[\|\omega\|\leq\kappa_{t}]$	time-dependent $\kappa_{t}$	time-dependent $\kappa_{t}$
Intermediate margin, constant	$\mathds{1}[a\leq\|\omega\|\leq b]$	one scalar $a$ , with $b$ fixed by the budget at each $a$	two scalars $a,b$
Intermediate margin, schedule	$\mathds{1}[a_{t}\leq\|\omega\|\leq b_{t}]$	time-dependent $a_{t}$ and $b_{t}$	time-dependent $a_{t}$ and $b_{t}$
Random	$p$ , independent of $\omega$ and $t$	nothing: the budget forces $p=\gamma$	one scalar $p$

Appendix

Table 1: Policy families compared in Figs. 1 (right) and 2 (right).

Panel of Figure 7 — Figure 7: Same as Fig. 3 (right), for $\Delta=0.1,\,0.4$ .

Panel of Figure 8 — 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 $\Delta=0.2,\,0.4$ .

Panel of Figure 9 — Figure 9: Same as Fig. 3 (left), for $\Delta=0.1,\,0.4$ .

Figure 10: Test error

\epsilon_{g,t}

as a function of training time, with online SGD with logistic loss, under the myopic policy

p^{\circ}_{\mathcal{R},t}

( 13 ). Solid lines represent single runs in dimension

d=100

, dashed lines represent the theoretical prediction for the

t\rightarrow\infty

asymptotics of Conjecture E.1 .

Active Learning

Active learning selects the examples, labels, features, or experiments most useful for improving a model under limited budgets.

See all 277 papers

QueryMarket: Cost-Aware Online Active Learning in Data Markets
Jun 16, 2026Xiwen Huang, Pierre PinsonActive Learning
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
Large Classification-Risk-Optional Label Acquisition
Sep 6, 2026F. Setoudehtanzangi, Geoffrey J. McLachlanActive Learning Multiclass Classification
Dipartimento di Scienze Statistiche, Universit`a di Padova, Padova, Italy · School of Mathematics and Physics, The University of Queensland, Australia
Active Learning with Imperfect Labels: Optimal Labeler Assignment and Sample Selection
Dec 14, 2025Pouya Ahadi, Blair Winograd, Camille Zaug +3Human-in-the-Loop Annotation Active Learning
School of Industrial and Systems Engineering Georgia Institute of Technology Atlanta, GA 30332, USA · Ford Motor Company

Jun 16, 2026J/K move · Enter open · S save

QueryMarket: Cost-Aware Online Active Learning in Data Markets

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

Active Learning

Open paper AskPDF arXiv

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.

Abstract

Active Learning

Explore similar work

QueryMarket: Cost-Aware Online Active Learning in Data Markets

Large Classification-Risk-Optional Label Acquisition

Active Learning with Imperfect Labels: Optimal Labeler Assignment and Sample Selection