cs.LGMay 11, 2023

Active Learning For Contextual Linear Optimization: A Margin-Based Approach

Authors: Mo Liu, Paul Grigas, Heyuan Liu, Zuo-Jun Max Shen

Organizations: Department of Statistics and Operations Research, University of North Carolina, Chapel Hill, NC, 27599 · Department of Industrial Engineering and Operations Research, University of California, Berkeley, Berkeley, CA, 94720

Abstract

We develop the first active learning method for contextual linear optimization. Specifically, we introduce a label acquisition algorithm that sequentially decides whether to request the ``labels'' of feature samples arriving in an unlabeled data stream, where the labels correspond to the objective coefficients in the linear optimization problem. The label acquisition rule is guided by the decision loss induced by the predicted coefficients, known as the Smart Predict-then-Optimize (SPO) loss. Motivated by the structure of the SPO loss, our algorithm uses the distance to degeneracy as a margin-based criterion for label acquisition. The algorithm processes incoming feature samples in batches, acquiring within each batch only the labels of samples whose distance to degeneracy falls below a rejection threshold. We derive non-asymptotic bounds for direct SPO-loss minimization over a general hypothesis class and for surrogate-loss minimization over a linear prediction class. These bounds demonstrate that, under certain natural conditions, our margin-based active learning algorithm requires fewer labels than supervised learning to achieve the same excess population risk for the chosen training loss. We provide concrete examples in which these conditions hold under continuous (sub-)Gaussian noise. Finally, we present numerical evidence demonstrating the practical value of our approach in applications such as personalized pricing and shortest-path problems.

Figures & tables

Appendix figures & tables26 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

May 24, 2026

Active Learning for Stochastic Contextual Linear Bandits

A key goal in stochastic contextual linear bandits is to efficiently learn a near-optimal policy. Prior algorithms for this problem learn a policy by strategically sampling actions but naively (passively) sampling contexts from the underlying context distribution. However, in many practical scenarios -- including online content recommendation, survey research, and clinical trials -- practitioners can actively sample or recruit contexts based on prior knowledge of the context distribution. Despite this potential for active learning, the role of strategic context sampling in stochastic contextual linear bandits is underexplored. We propose an algorithm that learns a near-optimal policy by strategically sampling rewards of context-action pairs. We prove instance-dependent theoretical guarantees demonstrating that our active context sampling strategy can improve over the minimax rate by up to a factor of d\sqrt{d}, where dd is the linear dimension. We show empirically that our algorithm reduces the number of samples needed to learn a near-optimal policy, in tasks such as warfarin dose prediction and joke recommendation.
Oct 16, 2026

Towards optimal selection schedules for online active learning

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.
Jul 7, 2026

The Approximation Ratio for the Risk of Myopic Bayesian Active Learning for Linear Regression

Active learning studies the fundamental question: what data should we choose to observe? The greedy algorithm in optimal experiment design is a common heuristic and also equivalent to myopic Bayesian active learning for linear regression, the common framework where long-term planning is replaced with the one-step optimal choice. In this work, we prove a first-of-its-kind approximation ratio for the greedy algorithm's risk that is tight up to an absolute constant. The approximation ratio is linear in the maximum initial leverage score (MILS), a newly identified quantity fundamental to the greedy algorithm's performance. Finally, we illustrate the results with simple numerical simulations.