CS Paper Radar

Towards optimal selection schedules for online active learning

Hugo Cui, Francesca Mignacco, Francesco Mori

cs.LG stat.MLcond-mat.dis-nn ·submitted 2026-10-16 13:54 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Should Pseudo-Labels Share Mini-Batches with Labeled Examples? Semi-Supervised Continual Active Learning with Limited Training Cost

cs.LG cs.AIcs.SDeess.AS ·2026-10-26 ·Shiqi Zhang, Tuomas Virtanen
similarity 0.67
Abstract

Active learning (AL) reduces annotation by querying informative examples. Continual active learning (CAL) also cuts the training cost, the total number of gradient steps, by training one model across AL rounds with a fixed number of mini-batch steps per round. Pseudo-labels add supervision without annotation, but they increase training cost. In CAL, where every round trains on a fixed number of mini-batches, whether and how pseudo-labeled examples should share these mini-batches with labeled examples is therefore open. We provide the first formalization of this problem as two decisions after each query, namely (i) which unlabeled examples should enter training with a pseudo-label and (ii) what share of each mini-batch they should take. Our method, semi-supervised continual active learning (SSCAL), works with any acquisition function. It admits pseudo-labels based on distances from unlabeled examples to labeled neighbors, caps their share, and reweights the loss on labeled examples to keep their expected gradient contribution unchanged. On frozen embeddings, its pseudo-labeler updates incrementally without extra model forward passes. Across two audio datasets, two frozen encoders, six acquisition functions and ten seeds, SSCAL ranks first on average among four protocols with equal training steps, answering the question affirmatively.

0.17

Oracle-Efficient and Parameter-Free Agnostic Smoothed Online Learning

cs.LG stat.ML ·2026-10-07 ·Sasha Voitovych, Adam Block, Alexander Rakhlin, Abhishek Shetty
similarity 0.66
Abstract

Online learning is an attractive framework in many domains because it permits well-defined learning even when data are dependent or chosen adversarially. This generality, however, comes at a steep price, introducing significant statistical and computational barriers. Recently, smoothed online learning has emerged as a promising framework that interpolates between the fully adversarial and fully stochastic settings by assuming that the conditional law of each covariate has density at most $1/σ$ with respect to some fixed base measure $μ$, and it is known to match the statistical and computational guarantees of classical learning while still allowing for much of the flexibility of online learning. However, existing oracle-efficient algorithms require either (i) sampling access to the base measure $μ$ or (ii) labels that are perfectly predicted by a fixed hypothesis. Both assumptions limit the applicability of these algorithms, in contrast to statistical learning, where empirical risk minimization (ERM) learns efficiently in the agnostic setting without any knowledge of the data distribution. We show that neither assumption is necessary, giving the first oracle-efficient algorithm that achieves sublinear regret in the agnostic setting without knowledge of $μ$. Our algorithm, based on Gaussian Follow-The-Perturbed-Leader, is parameter-free: it requires no knowledge of $μ$, the smoothing parameter $σ$, or the horizon $T$, and it achieves regret $\widetilde O(d\sqrt{T/σ})$ for binary classes of VC dimension $d$ with a single call to an ERM oracle per round, which is optimal up to a $\sqrt{d}$ factor. En route to establishing the regret bound, we introduce several new techniques that may be of independent interest.

0.46

AFA-BANDIT: Provably Near-Optimal Online Multi-Feature Classification Under Budget Constraints

cs.LG ·2026-10-06 ·AbdAlRahman Odeh, Teng-Hui Huang, Hesham El Gamal
theory similarity 0.66
Abstract · 10 pages, 3 figures

Active Feature Acquisition (AFA) is a classification problem in which an agent decides which costly features to acquire before predicting each sample's label. Unlike batch AFA, which trains a fixed policy and classifier offline on fully observed data, online AFA updates its predictor from revealed labels as samples arrive. Existing online methods either use deep reinforcement learning (RL) without performance guarantees or maximize cost-adjusted reward rather than enforce a global budget. We formulate online AFA as a combinatorial Bandits with Knapsacks (BwK) problem that couples acquisition and prediction. Unlike prior bandit-based AFA and classical BwK, our setting has combinatorial complexity, evolving rewards, a global budget, and structured side information. We obtain an improved regret upper bound over standard BwK bounds in this framework, leveraging a cardinality-aware confidence bound and the subset update structure. To avoid an exponentially large action space, we propose \emph{LP-Chain}, a variant that searches a cost-aware chain of feature subsets with a size that grows linearly with the number of features. While the regret upper bound is specific to the combinatorial framework, \emph{LP-Chain} empirically achieves comparable predictive performance. On synthetic data, \emph{LP-Chain} outperforms HEDGE-based BwK and deep RL-based online AFA baselines and scales favorably to more features.

0.26

Targeted Active Learning for Preference-Based Treatment Effects on Multivariate Outcomes

cs.LG stat.MLstat.ME ·2026-10-02 ·Lola Giordani, Mathieu Even, Chloé Geoffroy, Jean-Christophe Corvol, Raphaël Porcher +1 more
similarity 0.65
Abstract

Treatment efficacy is traditionally demonstrated on the basis of a single primary outcome. However, clinical decision-making usually requires consideration of multiple outcomes, balancing expected benefits against potential risks. The relative value assigned to these outcomes varies substantially from one patient to another. Given a preference rule over outcome profiles, treatment effects and optimal policies can be defined and estimated. Such a rule is rarely available in practice: it must itself be estimated from pairwise comparisons of outcome profiles, which are costly to collect from clinical experts. We propose an active learning framework that selects which comparisons to query. Standard criteria maximize the information gained on the preference rule itself. We instead target the quantities of interest, and select the query that most reduces uncertainty on the treatment effect and on the optimal policy induced by the learned rule. Under a Gaussian process model of the preference rule, we derive a closed-form approximation of this criterion. On semi-synthetic data built from a Parkinson's disease cohort with 13 clinical outcomes, our criterion achieves lower treatment effect estimation error and lower policy regret than existing criteria at equal query budget.

0.25

Online Adaptive Kernel Mixing for Gaussian Process Decision Making

cs.LG ·2026-09-17 ·Kavin Aravindan, Mani Tej Sriram, Gautam Dasarathy, Tejas Bodas
published similarity 0.65
Abstract · 35 pages, 9 figures. Accepted as a full paper at IFIP Performance 2026

Gaussian Processes (GPs) are widely used as surrogates for black-box functions in sequential decision-making problems such as Bayesian optimization (BO), level set estimation (LSE), and Bayesian active learning (BAL). GP performance critically depends on kernels, and standard kernels can lead to suboptimal decisions under misspecification. To address this, we introduce HACK GPs (Hedge Adaptive Cumulative Kernels), a method that views kernel selection as an online learning with expert advice problem. HACK treats each candidate kernel as a GP "expert" and updates a distribution over experts online using AdaHedge, based on a loss received as a proxy for their ability to fit the function and align with the task objective. We provide two variants of HACK: (i) Mixture of Gaussians (MoG) and (ii) categorical sampling. We establish general guarantees showing that, under a loss-gap condition, the weight concentrates on the best kernel and the resulting acquisition function is close to that of the best expert. Empirically, we observe robust performance across BO, LSE, and BAL compared to standard kernels such as Squared Exponential and Matern-5/2, as well as simple ensemble baselines.

0.33

Computationally Efficient Data Generation for Learning Nonlinear MPC Policies

eess.SY ·2026-11-07 ·Pietro Gori, Anton Pozharskiy, Franco Angelini, Manolo Garabini, Moritz Diehl +1 more
similarity 0.64
Abstract

Learning MPC requires large datasets generated by repeatedly solving MPC problems. For Nonlinear MPC (NMPC), dataset generation is computationally expensive because feasible initial states are difficult to sample efficiently. The feasible set is often non-convex or even disconnected, and many randomly sampled states are infeasible, leading to wasted optimization solves and unnecessary computational effort. In this work, we propose a data-generation framework for learning NMPC policies that combines active-set exploration with projection-based sampling. First, a bilevel formulation samples activity weights to promote solutions associated with different active sets while preserving optimality for the original NMPC problem; second, a simpler slack-based formulation uses weighted slack variables to target different active sets at the single level. These reference solutions are then used to construct local linearized feasible sets, from which candidate initial states are sampled and projected through the nonlinear NMPC problem to recover feasible and locally optimal training samples. Our approach is up to $37\times$ faster than baseline uniform sampling with $99\%$ acceptance rate, while maintaining a representative coverage of the feasible set.

0.13

On the Sample Complexity of Active Learning with Membership Queries

cs.LG stat.MLmath.ST ·2026-09-23 ·Ganghua Wang, Shaddin Dughmi
similarity 0.63
Abstract

This work revisits a fundamental question in active learning: how powerful is the ability to synthesize arbitrary queries? Compared to pool-based active learning, where the learner only selects queries from a given unlabeled pool, it has been observed that this seemingly mild change in query ability may dramatically alter the difficulty of statistical learning. In particular some hypothesis classes, such as two dimensional halfspaces, permit only polynomial error decay in the number of samples when the learner must draw its labels from the pool, yet become exponentially learnable once synthesized queries are allowed. This striking gap suggests that membership query synthesis induces a fundamentally different mode of learning, one that is not adequately captured by existing active learning theory and calls for new analytical tools to characterize its sample complexity for general hypothesis classes. Motivated by this phenomenon, we develop several sufficient conditions, present intriguing examples, and propose a conjectural perspective toward understanding which hypothesis classes admit efficient learning through synthesized queries.

0.23

Optimally Pacing Budget Spending and Learning

cs.LG cs.GT ·2026-10-08 ·Mark Braverman, Jingyi Liu, Jieming Mao, Jon Schneider, Eric Xue
similarity 0.63
Abstract

We establish near-optimal regret bounds for budget-constrained online learning against arbitrary classes of budget-pacing experts in the adversarial setting. In particular, given any class of $F$ experts and a candidate budget pacing schedule, we provide a full-information algorithm which obtains regret $O(D \sqrt{\log F}+ \sqrt{T\log F})$ against all experts whose cumulative spending stays within distance $D$ of this schedule, matching lower bounds established by Braverman et al. (2025). We additionally show that our technique extends to various problems in online resource allocation, where the learner gets to see the rewards and costs of the current options available to them, and establish $O(D\sqrt{\log F})$ regret bounds when fractional allocation is allowed. This is the first algorithm we are aware of which can achieve $o(\sqrt{T})$ guarantees for such tasks.

0.25