Active Learning For Contextual Linear Optimization: A Margin-Based Approach
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
| Batch | Active budget | SL lower bound | Label ratio bound | ||
|---|---|---|---|---|---|
| Curvature lower bound | Leading label-ratio bound | ||
|---|---|---|---|
| Surrogate loss | SPO+ | Squared | MAE | Huber |
|---|---|---|---|---|
| Shortest path ( ) | 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 ( ) | 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 |
Appendix figures & tables26 assets
Supplementary material from the paper’s appendix.
Appendix
| Training loss | ||||
|---|---|---|---|---|
| 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 |
| Training loss | ||||
|---|---|---|---|---|
| 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 |
| 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] |
| Training loss | Labels | MBAL regret | SL regret | MBAL risk | SL risk |
|---|---|---|---|---|---|
| SPO+ | 3,000 | ||||
| SPO+ | 5,000 | ||||
| Squared | 3,000 | ||||
| Squared | 5,000 | ||||
| MAE | 3,000 | ||||
| MAE | 5,000 |
| 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] |
| Training loss | Labels | MBAL regret | SL regret | MBAL risk | SL risk |
|---|---|---|---|---|---|
| SPO+ | 3,000 | 0.0024831 | 0.0026841 | ||
| SPO+ | 5,000 | 0.0024398 | 0.00256 | ||
| Squared | 3,000 | 0.0022814 | 0.0023082 | ||
| Squared | 5,000 | 0.002282 | 0.0022925 | ||
| MAE | 3,000 | 0.002296 | 0.0023339 | ||
| MAE | 5,000 | 0.0022905 | 0.0023093 |
| 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] |
| 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] |
| 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] |
| 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] |
| 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] |
| 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] |
| 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] |
| Training loss | 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 |
| 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] |
Active Learning
Active learning selects the examples, labels, features, or experiments most useful for improving a model under limited budgets.
See all 330 papers