Beyond Prediction Residuals: Conformal Regret Calibration for Robust Contextual Linear Optimization
Organizations: Department of Industrial Engineering, Tsinghua University · Rotman School of Management, University of Toronto
Abstract
Predict-then-optimize systems convert contextual forecasts into decisions, yet conformal robust optimization typically calibrates prediction residuals rather than downstream loss. For linear optimization, this parameter-space geometry can be badly misaligned with decision risk: large objective perturbations may preserve the optimizer, while small boundary-crossing perturbations may cause substantial regret. We introduce Conformal Regret Sets, a post-hoc, model-agnostic framework that conformalizes an optimization-derived regret surrogate and uses its calibrated level set for minimax-regret refinement. We first show that directly conformalizing exact regret, although sufficient to certify the nominal predict-then-optimize decision, yields a degenerate robust problem: absent an exogenous bounded support, every alternative decision has unbounded worst-case regret. We therefore use SPO+, a pointwise upper bound on exact regret, as the conformal score, obtaining distribution-free finite-sample marginal regret guarantees under exchangeability. For contextual linear programs, the resulting set decomposes into polyhedral pieces aligned with the normal fan of the feasible polytope. A vertex is active if and only if its predicted suboptimality gap is at most half the calibrated threshold , enabling local, output-sensitive generation of all relevant pieces. Moreover, if is the predicted gap to the closest competing vertex, the nominal and refined decisions admit the sharper worst-case-regret certificate , with an exact early exit when . Experiments on contextual fractional knapsack validate the geometry and certificates: continuous refinement reduces the -quantile and of regret by and relative to nominal PTO, while vertex-restricted refinement changes only of nominal decisions.
Figures & tables
| Method | |||
|---|---|---|---|
| Regret set | 0.96/0.97 | 0.91/0.93 | 0.83/0.86 |
| Residual- set | 0.94/1.00 | 0.89/1.00 | 0.80/1.00 |
| Box set | 0.94/1.00 | 0.90/1.00 | 0.80/1.00 |
| KNN–Ellipsoid | 0.94/1.00 | 0.87/1.00 | 0.78/1.00 |
| Method | Mean | Q95 | CVaR95 | Change |
|---|---|---|---|---|
| Nominal PTO | 7.605 | 38.664 | 60.557 | 0.000 |
| Pure RR | 7.763 | 38.956 | 61.814 | 0.100 |
| Continuous RR | 11.117 | 35.137 | 52.618 | 0.990 |
| Residual- RO | 20.001 | 57.090 | 77.027 | 0.956 |
| Box RO | 8.824 | 40.673 | 64.430 | 0.284 |
| KNN RO | 624.111 | 1374.573 | 1682.087 | 1.000 |
Appendix figures & tables9 assets
Supplementary material from the paper’s appendix.
Appendix
| Domain | Exact | Full set | Tie exp. | Search (ms) | Solve (s) | ||
|---|---|---|---|---|---|---|---|
| Pure RR | 1 | 0.8 | 0.8 | 0.0 | 1.0/1.0 | 0.769/1.231 | 0.049/0.108 |
| Pure RR | 5 | 63.2 | 5.8 | 0.0 | 5.0/5.0 | 3.418/4.577 | 0.312/0.606 |
| Pure RR | 10 | 86.6 | 21.6 | 0.2 | 10.0/10.0 | 6.668/8.487 | 0.483/1.045 |
| Pure RR | 25 | 99.6 | 56.2 | 0.2 | 22.0/25.0 | 14.931/18.760 | 0.833/1.557 |
| Pure RR | 50 | 99.8 | 83.2 | 0.0 | 22.0/50.0 | 15.055/33.920 | 1.045/2.107 |
| Pure RR | 100 | 100.0 | 94.4 | 0.0 | 22.0/72.1 | 15.055/51.759 | 1.045/2.959 |
| Method | |||||
|---|---|---|---|---|---|
| SPO regret set (Continuous RR) | 0.964/0.974 | 0.912/0.926 | 0.826/0.862 | 0.706/0.802 | 0.656/0.816 |
| Residual- Cost-RO | 0.938/0.998 | 0.892/0.998 | 0.804/0.998 | 0.696/0.996 | 0.572/0.992 |
| Contextual Box Cost-RO | 0.942/1.000 | 0.904/1.000 | 0.796/1.000 | 0.714/1.000 | 0.608/0.998 |
| KNN–Ellipsoid Cost-RO | 0.936/1.000 | 0.868/1.000 | 0.778/1.000 | 0.678/1.000 | 0.570/1.000 |
| Method | |||||
|---|---|---|---|---|---|
| SPO regret set (Continuous RR) | 4.990/7.697 | 1.407/3.031 | 0.000/0.751 | 0.000/0.073 | 0.000/0.000 |
| Residual- Cost-RO | 35.783/55.768 | 30.142/47.248 | 23.427/37.042 | 18.935/30.515 | 14.934/25.445 |
| Contextual Box Cost-RO | 4.033/28.944 | 3.531/26.607 | 2.792/21.779 | 2.488/20.421 | 2.132/18.512 |
| KNN–Ellipsoid Cost-RO | 88.626/244.809 | 50.288/165.904 | 28.770/90.569 | 20.315/60.454 | 15.750/46.285 |
| Method | Mean | Q95 | CVaR95 | Change | Time (s) |
|---|---|---|---|---|---|
| Nominal PTO | 7.605 | 38.664 | 60.557 | 0.000 | 0.00124 |
| Pure RR | 7.763 | 38.956 | 61.814 | 0.100 | 1.41800 |
| Continuous RR | 11.117 | 35.137 | 52.618 | 0.990 | 1.88969 |
| Box RR | 17.890 | 57.051 | 73.152 | 0.986 | 0.10363 |
| Residual- RR | 38.348 | 64.456 | 78.628 | 1.000 | 13.15628 |
| KNN RR | 52.924 | 119.828 | 146.999 | 1.000 | 14.37106 |
| Event | |||||
|---|---|---|---|---|---|
| SPO score inclusion | 0.964 | 0.912 | 0.826 | 0.706 | 0.656 |
| Nominal regret | 0.994 | 0.978 | 0.928 | 0.850 | 0.816 |
| Pure RR set-relative certificate | 0.978 | 0.944 | 0.882 | 0.818 | 0.816 |
| Continuous RR set-relative certificate | 0.974 | 0.926 | 0.862 | 0.802 | 0.816 |
| Pure RR margin certificate | 0.980 | 0.946 | 0.888 | 0.820 | 0.816 |
| Continuous RR margin certificate | 0.982 | 0.942 | 0.882 | 0.806 | 0.816 |
| Predictor | RMSE | Nominal | Pure RR | Continuous RR | Active | Skip (%) |
|---|---|---|---|---|---|---|
| Ridge | 33.87 | 10.08 | 9.97 | 14.60 | 370.63 | 0.20 |
| Poly. KRR | 31.55 | 7.60 | 7.76 | 11.12 | 44.96 | 0.80 |
| RBF KRR | 32.15 | 7.56 | 7.70 | 11.35 | 45.47 | 0.80 |
| MLP | 31.96 | 7.75 | 7.84 | 11.74 | 45.66 | 0.60 |
| Random forest | 53.94 | 20.17 | 20.88 | 29.50 | 181.42 | 0.20 |
| Method | Mean | Q95 | CVaR95 | Change | Time (s) |
|---|---|---|---|---|---|
| Nominal PTO | 0.07869 | 0.2606 | 0.3718 | 0.000 | 0.00043 |
| Pure RR | 0.07869 | 0.2606 | 0.3718 | 0.000 | 0.01193 |
| Continuous RR | 0.08003 | 0.2059 | 0.2464 | 1.000 | 0.00547 |
| Residual- RO | 0.08006 | 0.2062 | 0.2471 | 1.000 | 0.00140 |
| Box RO | 0.1177 | 0.3541 | 0.4488 | 1.000 | 0.00038 |
| KNN RO | 0.09353 | 0.2365 | 0.3075 | 1.000 | 0.00130 |
| Method | Mean | Q95 | CVaR95 | Change | Time (s) |
|---|---|---|---|---|---|
| Nominal PTO | 0.843 | 3.720 | 5.379 | 0.000 | 0.00202 |
| Pure RR | 0.851 | 3.726 | 5.380 | 0.070 | 0.15305 |
| Continuous RR | 1.235 | 3.466 | 4.875 | 0.997 | 0.54145 |
| Residual- RO | 3.154 | 6.813 | 7.967 | 0.963 | 0.00378 |
| Box RO | 0.913 | 4.066 | 5.661 | 0.240 | 0.00190 |
| KNN RO | 3.235 | 9.609 | 12.874 | 0.851 | 0.00777 |
Predict-Then-Optimize
Predict-then-optimize trains or evaluates predictors by how well their outputs support downstream decisions under constraints.
See all 43 papers