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
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
Figure 1: Decision uncertainty at a fixed prediction as the confidence region changes.
Figure 2: Decision uncertainty for equally sized confidence regions at different distances to degeneracy.
σ
ϵ
Batch k
Active budget
SL lower bound
Label ratio bound
0.1
10−6
28
10,225
19,962
0.513
0.1
10−7
32
75,338
199,620
0.378
1
10−5
32
75,338
199,620
0.378
1
10−6
36
606,439
1,996,205
0.304
Table 1: Finite total-label comparisons for Example 6.6 , with 95% confidence and all 32 warm-up labels included. The active budget is a sufficient upper bound, and the supervised lower bound is rounded down. Label-ratio bounds are rounded upward. The horizon is T=2k−1 ; these are deterministic probability bounds. Lower is better.
σ
Curvature lower bound h0
vSL/Jℓ
Leading label-ratio bound
1.0
1.4125×10−4
37.2044
0.761
1.5
1.6752×10−4
54.1463
0.523
2.0
1.5370×10−4
63.6146
0.445
Table 2: Population certificates for Example 6.7 , with κ=1 , pd=4 , and 95% confidence. The curvature lower bounds are rounded down and apply throughout the coefficient box under the full and specified selected feature laws. The leading ratios for Proposition 6.5 are rounded upward. Noise variance is fixed within each row. Lower is better.
Figure 3: SPO regret for the shortest path problems under SPO+ training. Each panel shows means over 30 paired trials and pointwise 90% bootstrap intervals, using the latest completed-batch predictor at warm-up, every 250 labels through 3,000, and at 4,000 and 5,000. Warm-up sizes are 100 and 200; acquired-label counts include warm-up and match exactly within each method pair. Both settings use the fixed fourth-root threshold and square-root slack. Panel (a) uses Gaussian features and independent multiplicative coordinate noise; panel (b) uses bounded features and independent additive Gaussian noise.
Figure 4: SPO regret for personalized pricing under SPO+ training. Curves show means over 30 paired trials at warm-up and completed-batch endpoints 2mj−1 , j=1,…,11 ; shaded regions give pointwise 90% bootstrap intervals. The horizontal coordinate is the mean acquired-label count, including 200 warm-up labels, with exactly matched counts within each method pair. The vertical axis is logarithmic.
Surrogate loss
SPO+
Squared
MAE
Huber
Shortest path ( 3×3 )
108.419 [79.182, 145.766]
5.232 [3.778, 7.262]
4.605 [3.348, 6.347]
4.051 [3.103, 5.347]
Mean acquired labels
5,000.0
5,000.0
5,000.0
5,000.0
Shortest path ( 5×5 )
1.664 [1.548, 1.789]
1.653 [1.421, 1.927]
1.837 [1.617, 2.077]
1.696 [1.446, 1.985]
Mean acquired labels
5,000.0
5,000.0
5,000.0
5,000.0
Personalized pricing
9.096 [3.657, 40.637]
0.804 [0.463, 1.512]
5.055 [2.648, 13.233]
3.600 [1.848, 11.667]
Mean acquired labels
1,050.5
288.0
408.5
308.9
Table 3: SPO regret ratios under four training losses for the same data and settings used in Sections 7.1 and 7.2 . Each ratio divides mean supervised-learning SPO regret by mean MBAL-SPO regret, with a pointwise 90% paired bootstrap interval in brackets. Each entry uses 30 pairs, evaluated at 5,000 acquired labels for both grids and at T=2047 for pricing. Counts include warm-up and match within each method pair; pricing counts differ across losses.
Appendix figures & tables26 assets
Supplementary material from the paper’s appendix.
Appendix
Training loss
n0
b0
s0
δH
SPO+
100
0.631675
0.05
–
Squared
100
2.22757
0.00767514
–
MAE
100
2.22805
0.271243
–
Huber
100
2.22742
0.00222361
0.0116452
Appendix
Table 4: Fixed initialization for the 3×3 independent-coordinate-noise setting. All losses use the schedules in ( 99 ). The Huber cutoff and scales are calibrated on development samples; full-precision inputs are retained in the numerical files.
Training loss
n0
b0
s0
δH
SPO+
200
0.208528
0.025
–
Squared
200
0.0890489
0.0234022
–
MAE
200
0.0891542
0.93674
–
Huber
200
0.0891638
0.00819009
0.0133885
Appendix
Table 5: Fixed initialization for the bounded-feature 5×5 setting with additive Gaussian cost noise. The prediction class and fixed schedule orders are unchanged across training losses.
Labels
SPO+
Squared
MAE
Huber
500
21.824 [14.488, 34.395]
5.093 [3.665, 7.089]
3.909 [3.202, 4.796]
4.169 [3.225, 5.454]
1,000
29.828 [16.942, 56.591]
7.022 [5.471, 9.067]
6.621 [5.282, 8.210]
6.402 [4.957, 8.229]
2,000
96.884 [69.964, 129.619]
6.776 [5.177, 9.048]
5.338 [4.191, 6.848]
5.173 [4.061, 6.590]
3,000
62.447 [48.875, 81.168]
4.532 [3.498, 5.884]
3.375 [2.806, 4.102]
3.017 [2.424, 3.818]
4,000
110.062 [80.980, 144.559]
6.058 [4.519, 8.146]
5.470 [4.079, 7.495]
4.780 [3.718, 6.197]
5,000
108.419 [79.182, 145.766]
5.232 [3.778, 7.262]
4.605 [3.348, 6.347]
4.051 [3.103, 5.347]
Appendix
Table 6: SPO regret ratios for the 3×3 grid over the full label range. Columns identify training losses. Each cell uses all thirty pairs and divides mean supervised-learning SPO regret by mean MBAL-SPO regret, with its pointwise 90% paired bootstrap interval.
Figure 5: SPO regret for the 3×3 shortest path problem under SPO+ training. Curves retain all thirty paired trials and show means at warm-up, every 250 labels through 3,000, and at 4,000 and 5,000, using the latest completed-batch predictor. Shading gives pointwise 90% bootstrap intervals. Counts include warm-up and match within each method pair. The label axis is linear and the regret axis is logarithmic.
Figure 6: SPO regret for the 3×3 shortest path problem under Squared training. Curves retain all thirty paired trials and show means at warm-up and 500, 1,000, 2,000, 3,000, 4,000, and 5,000 labels, using the latest completed-batch predictor. Shading gives pointwise 90% bootstrap intervals. Counts include warm-up and match within each method pair. The label axis is linear and the regret axis is logarithmic.
Figure 7: SPO regret for the 3×3 shortest path problem under MAE training. Curves retain all thirty paired trials and show means at warm-up and 500, 1,000, 2,000, 3,000, 4,000, and 5,000 labels, using the latest completed-batch predictor. Shading gives pointwise 90% bootstrap intervals. Counts include warm-up and match within each method pair. The label axis is linear and the regret axis is logarithmic.
Figure 8: SPO regret for the 3×3 shortest path problem under Huber training. Curves retain all thirty paired trials and show means at warm-up and 500, 1,000, 2,000, 3,000, 4,000, and 5,000 labels, using the latest completed-batch predictor. Shading gives pointwise 90% bootstrap intervals. Counts include warm-up and match within each method pair. The label axis is linear and the regret axis is logarithmic.
Training loss
Labels
MBAL regret
SL regret
MBAL risk
SL risk
SPO+
3,000
2.259×10−6
1.411×10−4
1.457×10−5
1.519×10−4
SPO+
5,000
1.006×10−6
1.091×10−4
1.304×10−5
1.215×10−4
Squared
3,000
1.217×10−7
5.516×10−7
1.262×10−5
1.300×10−5
Squared
5,000
6.012×10−8
3.145×10−7
1.232×10−5
1.274×10−5
MAE
3,000
1.694×10−7
5.716×10−7
1.258×10−5
1.288×10−5
MAE
5,000
8.070×10−8
3.716×10−7
1.222×10−5
1.267×10−5
Appendix
Table 7: Mean SPO regret and full realized-cost SPO risk for the 3×3 grid. The first column identifies the training loss; every regret column uses ( 18 ). All thirty pairs are retained. Full SPO risk includes the irreducible cost-noise contribution and differs from SPO regret.
Labels
SPO+
Squared
MAE
Huber
500
1.559 [0.851, 3.074]
1.139 [1.016, 1.289]
1.289 [1.179, 1.416]
1.228 [1.082, 1.395]
1,000
1.754 [1.371, 2.312]
1.571 [1.393, 1.776]
1.540 [1.391, 1.699]
1.647 [1.481, 1.828]
2,000
1.328 [1.018, 1.740]
1.731 [1.540, 1.936]
1.710 [1.510, 1.932]
1.707 [1.522, 1.914]
3,000
1.850 [1.752, 1.957]
2.328 [2.013, 2.693]
2.321 [2.026, 2.651]
2.342 [2.005, 2.730]
4,000
1.519 [1.456, 1.589]
1.850 [1.597, 2.144]
1.858 [1.604, 2.147]
1.812 [1.523, 2.145]
5,000
1.664 [1.548, 1.789]
1.653 [1.421, 1.927]
1.837 [1.617, 2.077]
1.696 [1.446, 1.985]
Appendix
Table 8: SPO regret ratios for the 5×5 grid over the full label range. Columns identify training losses. Each cell uses all thirty pairs and divides mean supervised-learning SPO regret by mean MBAL-SPO regret, with its pointwise 90% paired bootstrap interval.
Figure 9: SPO regret for the 5×5 shortest path problem under SPO+ training. Curves retain all thirty paired trials and show means at warm-up, every 250 labels through 3,000, and at 4,000 and 5,000, using the latest completed-batch predictor. Shading gives pointwise 90% bootstrap intervals. Counts include warm-up and match within each method pair. The label axis is linear and the regret axis is logarithmic.
Figure 10: SPO regret for the 5×5 shortest path problem under Squared training. Curves retain all thirty paired trials and show means at warm-up and 500, 1,000, 2,000, 3,000, 4,000, and 5,000 labels, using the latest completed-batch predictor. Shading gives pointwise 90% bootstrap intervals. Counts include warm-up and match within each method pair. The label axis is linear and the regret axis is logarithmic.
Figure 11: SPO regret for the 5×5 shortest path problem under MAE training. Curves retain all thirty paired trials and show means at warm-up and 500, 1,000, 2,000, 3,000, 4,000, and 5,000 labels, using the latest completed-batch predictor. Shading gives pointwise 90% bootstrap intervals. Counts include warm-up and match within each method pair. The label axis is linear and the regret axis is logarithmic.
Figure 12: SPO regret for the 5×5 shortest path problem under Huber training. Curves retain all thirty paired trials and show means at warm-up and 500, 1,000, 2,000, 3,000, 4,000, and 5,000 labels, using the latest completed-batch predictor. Shading gives pointwise 90% bootstrap intervals. Counts include warm-up and match within each method pair. The label axis is linear and the regret axis is logarithmic.
Training loss
Labels
MBAL regret
SL regret
MBAL risk
SL risk
SPO+
3,000
2.262×10−4
4.185×10−4
0.0024831
0.0026841
SPO+
5,000
1.798×10−4
2.993×10−4
0.0024398
0.00256
Squared
3,000
2.276×10−5
5.298×10−5
0.0022814
0.0023082
Squared
5,000
2.183×10−5
3.609×10−5
0.002282
0.0022925
MAE
3,000
3.372×10−5
7.825×10−5
0.002296
0.0023339
MAE
5,000
2.774×10−5
5.095×10−5
0.0022905
0.0023093
Appendix
Table 9: Mean SPO regret and full realized-cost SPO risk for the 5×5 grid. The first column identifies the training loss; every regret column uses ( 18 ). All thirty pairs are retained. Full SPO risk includes the irreducible cost-noise contribution and differs from SPO regret.
b0 multiplier
SPO+
Squared
MAE
Huber
0.5
102.721 [53.818, 194.028]
11.436 [6.891, 18.573]
5.361 [2.669, 10.263]
7.749 [5.081, 11.390]
1
35.454 [24.590, 45.799]
7.756 [4.480, 14.357]
4.041 [2.314, 6.807]
6.855 [4.118, 11.122]
2
33.322 [21.770, 44.669]
8.922 [5.563, 13.809]
4.778 [2.675, 8.599]
7.045 [4.150, 12.164]
Appendix
Table 10: Sensitivity to the initial rejection scale for the 3×3 grid at 3,000 labels. All other loss-specific settings are fixed. Each complete cell reports the SPO regret ratio over ten pairs and its pointwise 90% paired bootstrap interval. Unavailable cells display the completed-pair count.
b0 multiplier
SPO+
Squared
MAE
Huber
0.5
0.604 [0.298, 1.561]
2.123 [1.748, 2.587]
1.982 [1.488, 2.614]
2.182 [1.728, 2.739]
1
1.581 [1.177, 2.152]
2.382 [1.996, 2.892]
2.178 [1.712, 2.723]
2.363 [1.923, 2.910]
2
1.744 [1.539, 2.009]
2.424 [2.032, 2.933]
2.204 [1.730, 2.746]
2.400 [1.956, 2.925]
Appendix
Table 11: Sensitivity to the initial rejection scale for the 5×5 grid at 3,000 labels. All other loss-specific settings are fixed. Each complete cell reports the SPO regret ratio over ten pairs and its pointwise 90% paired bootstrap interval. Unavailable cells display the completed-pair count.
ϵ
SPO+
Squared
MAE
Huber
0.005
92.976 [38.133, 180.305]
5.458 [3.233, 9.841]
3.116 [1.873, 5.909]
5.626 [2.972, 11.873]
0.01
35.454 [24.590, 45.799]
7.756 [4.480, 14.357]
4.041 [2.314, 6.807]
6.855 [4.118, 11.122]
0.03
66.660 [51.379, 83.149]
5.209 [3.772, 7.280]
3.826 [2.931, 5.159]
3.705 [2.867, 4.871]
Appendix
Table 12: Sensitivity to independent multiplicative noise amplitude for the 3×3 grid at 3,000 labels. All other loss-specific settings are fixed. Each complete cell reports the SPO regret ratio over ten pairs and its pointwise 90% paired bootstrap interval. Unavailable cells display the completed-pair count.
σc
SPO+
Squared
MAE
Huber
0.01
2.369 [1.927, 2.950]
2.389 [2.026, 2.844]
2.232 [1.783, 2.774]
2.393 [1.986, 2.928]
0.02
1.581 [1.177, 2.152]
2.382 [1.996, 2.892]
2.178 [1.712, 2.723]
2.363 [1.923, 2.910]
0.06
1.107 [0.916, 1.349]
Unavailable 9/10 pairs
1.464 [1.232, 1.748]
1.507 [1.280, 1.774]
Appendix
Table 13: Sensitivity to additive Gaussian cost-noise standard deviation for the 5×5 grid at 3,000 labels. All other loss-specific settings are fixed. Each complete cell reports the SPO regret ratio over ten pairs and its pointwise 90% paired bootstrap interval. Unavailable cells display the completed-pair count.
n0
SPO+
Squared
MAE
Huber
50
57.635 [27.770, 95.377]
7.720 [4.501, 14.408]
3.887 [2.236, 6.530]
6.897 [4.175, 11.226]
100
35.454 [24.590, 45.799]
7.756 [4.480, 14.357]
4.041 [2.314, 6.807]
6.855 [4.118, 11.122]
200
31.370 [20.175, 49.107]
7.366 [4.280, 13.658]
4.221 [2.507, 6.872]
6.391 [3.765, 10.714]
Appendix
Table 14: Sensitivity to the warm-up size for the 3×3 grid at 3,000 labels. All other loss-specific settings are fixed. Each complete cell reports the SPO regret ratio over ten pairs and its pointwise 90% paired bootstrap interval. Unavailable cells display the completed-pair count.
n0
SPO+
Squared
MAE
Huber
100
1.976 [1.724, 2.295]
2.381 [1.976, 2.920]
2.283 [1.840, 2.796]
2.420 [2.014, 2.941]
200
1.581 [1.177, 2.152]
2.382 [1.996, 2.892]
2.178 [1.712, 2.723]
2.363 [1.923, 2.910]
500
Unavailable 9/10 pairs
2.166 [1.769, 2.723]
1.950 [1.499, 2.504]
1.926 [1.497, 2.500]
Appendix
Table 15: Sensitivity to the warm-up size for the 5×5 grid at 3,000 labels. All other loss-specific settings are fixed. Each complete cell reports the SPO regret ratio over ten pairs and its pointwise 90% paired bootstrap interval. Unavailable cells display the completed-pair count.
b0 multiplier
SPO+
Squared
MAE
Huber
0.5
15.678 [6.550, 66.369]
1.211 [1.000, 1.469]
2.614 [1.109, 13.491]
2.791 [1.629, 7.013]
1
38.608 [24.746, 69.717]
1.000 [1.000, 1.000]
3.213 [1.319, 33.715]
2.783 [1.532, 6.202]
2
6.554 [4.215, 12.954]
1.260 [1.002, 1.725]
7.296 [2.900, 23.275]
2.783 [1.353, 10.026]
Appendix
Table 16: Sensitivity to the initial rejection scale in personalized pricing at T=2047 . Multipliers apply to each loss’s frozen b0 ; the fourth-root threshold, square-root slack, and other parameters remain fixed. Each cell reports the SPO regret ratio over ten pairs and its pointwise 90% paired bootstrap interval.
Training loss
n0
b0
s0
Cost divisor
Coefficient bound
SPO+
200
0.17222
2.22352
100
8
Squared
200
0.0113622
1.6844
1000
0.8
MAE
200
0.00101832
14.8865
100
8
Huber
200
0.00119286
0.0740007
100
8
Appendix
Table 17: Fixed pricing initialization and numerical cost units. The initial scales and coefficient bound are expressed on the indicated normalized training-cost scale. Every loss uses the fixed schedules in ( 99 ).
Training loss
Mean labels
MBAL regret
SL regret
SL/MBAL
SPO+
1,050.5
0.017644
0.16048
9.096 [3.657, 40.637]
Squared
288.0
3.0981
2.4911
0.804 [0.463, 1.512]
MAE
408.5
21.384
108.1
5.055 [2.648, 13.233]
Huber
308.9
28.94
104.2
3.600 [1.848, 11.667]
Appendix
Table 18: Mean SPO regret in original revenue units for pricing at T=2047 , with the SPO regret ratio and its pointwise 90% paired bootstrap interval. Each loss uses all thirty paired trials. Counts include warm-up and match within each method pair.
Figure 13: SPO regret for personalized pricing under Squared training. Curves show means over thirty paired trials at warm-up and the eleven completed batches, with pointwise 90% bootstrap intervals. The horizontal coordinate is mean acquired labels, including 200 warm-up labels, and counts match within each method pair. The regret axis is logarithmic. Every checkpoint and large individual regret is retained.
Figure 14: SPO regret for personalized pricing under MAE training. Curves show means over thirty paired trials at warm-up and the eleven completed batches, with pointwise 90% bootstrap intervals. The horizontal coordinate is mean acquired labels, including 200 warm-up labels, and counts match within each method pair. The regret axis is logarithmic. Every checkpoint and large individual regret is retained.
Figure 15: SPO regret for personalized pricing under Huber training. Curves show means over thirty paired trials at warm-up and the eleven completed batches, with pointwise 90% bootstrap intervals. The horizontal coordinate is mean acquired labels, including 200 warm-up labels, and counts match within each method pair. The regret axis is logarithmic. Every checkpoint and large individual regret is retained.
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, where d 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.
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.
Hugo Cui, Francesca Mignacco, Francesco Mori
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 +1
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.
Stephen Mussmann
School of Computer Science Georgia Institute of Technology