Towards optimal selection schedules for online active learning
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.
Related
- The data geometry of masking diffusion: Certified-optimal schedules via unmasking growth complexity
- Near-Optimal √K-Regret for Online Learning in Uninformed Markov Games
- Dimension-Optimal Dynamic Regret in Exp-Concave Online Learning
- Low-Budget Active Learning through Entropic Optimal Transport
- Age-Optimal Target Wake Time: Provably Good Wake Schedules for Energy-Constrained Wi-Fi Status Updating
BibTeX
@misc{cui2026towards,
title = {{Towards optimal selection schedules for online active learning}},
author = {Hugo Cui and Francesca Mignacco and Francesco Mori},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.23477},
eprint = {2610.23477},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.23477},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Towards optimal selection schedules for online active learning
AU - Hugo Cui
AU - Francesca Mignacco
AU - Francesco Mori
PY - 2026
DA - 2026/10/16
PB - arXiv
DO - 10.48550/arxiv.2610.23477
UR - https://arxiv.org/abs/2610.23477
AB - 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.
ER -