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 (η−2Γ)+, with an exact early exit when η≤2Γ. Experiments on contextual fractional knapsack validate the geometry and certificates: continuous refinement reduces the 0.95-quantile and CVaR0.95 of regret by 9.1% and 13.1% relative to nominal PTO, while vertex-restricted refinement changes only 10.0% of nominal decisions.
Figures & tables
Figure 1: Geometry of residual and regret sets in cost coordinates (c1,c2) . The panels show normal-fan regions, a residual- ℓ2 ball, an exact-regret set, and the active pieces of an SPO + set.
Figure 2: Exact geometry validation for n=8 . (a) Active-piece counts across calibration levels. (b) Nominal certificate versus the margin upper bound at α=0.10 ; “Skip” denotes the fraction certified at zero without solving a robust master.
Table 2: Decision performance at α=0.10 ; lower regret is better. Q95 is the 0.95 quantile, CVaR95 is the average regret in the upper 5% tail, and Change is the fraction of decisions differing from nominal PTO.
Figure 3: Certified gap-ordered generation on 500 test contexts. (a) Exact-certification rate. (b) Median and 0.90 quantile of the certified optimality gap normalized by η .
Appendix figures & tables9 assets
Supplementary material from the paper’s appendix.
Appendix
Domain
M
Exact
Full set
Tie exp.
Meff
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
Appendix
Table 3: Certified anytime behavior by requested prefix budget. Exact, full-set, and tie-expansion columns are percentages; effective prefix sizes and runtimes are reported as median / 0.90 quantile. Search time is in milliseconds and paired-solve time is in seconds.
Method
α=.05
α=.10
α=.20
α=.30
α=.40
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- ℓ2 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
Appendix
Table 4: Marginal parameter and decision-regret coverage on the fixed n=8 test split. Each entry is parameter coverage / decision-regret coverage; the nominal target is 1−α .
Method
α=.05
α=.10
α=.20
α=.30
α=.40
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- ℓ2 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
Appendix
Table 5: Scale of the method-specific full-set regret certificates in Table 4 . Each entry is the median / 0.95 quantile over the 500 test observations.
Figure 4: Realized-regret distribution at α=0.10 . (a) Empirical regret quantiles. (b) Quantile-wise gap to Nominal PTO, where negative values are better. KNN–Ellipsoid is omitted for scale and retained in Table 2 .
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- ℓ2 RR
38.348
64.456
78.628
1.000
13.15628
KNN RR
52.924
119.828
146.999
1.000
14.37106
Appendix
Table 6: Objective-matched performance at n=20 and α=0.10 on 500 test observations. Change is the decision-change rate; Time is mean recorded time per instance (one solver thread for PTO, SPO+, and Box; up to twenty for Residual- ℓ2 and KNN).
Event
α=0.05
α=0.10
α=0.20
α=0.30
α=0.40
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
Appendix
Table 7: Empirical probabilities for the six validation events; nominal target 1−α . These marginal frequencies summarize one fixed-seed experiment and do not claim conditional coverage.
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
Appendix
Table 8: Prediction quality, decision regret, and refinement geometry. Active counts use the complete uncapped search; Lower values are better except for the skip rate.
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- ℓ2 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
Appendix
Table 9: Decision performance for real-data solar-grid allocation ( α=0.20 , 96 test months). Change is the decision-change rate; Time is the mean recorded solver-stage time. Lower regret is better.
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- ℓ2 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
Appendix
Table 10: Decision performance on the 8×8 transportation network with 32 arcs ( α=0.10 ). Entries average per-seed summaries over five seeds, each with 500 test observations. Change is the decision-change rate; Time is mean online time.
Decision-focused learning for linear optimization is complicated by the discontinuity of the optimizer, where small cost errors may leave the decision unchanged or move it to a different vertex. We show that this non-smooth pointwise behavior becomes locally quadratic after averaging over the data distribution, and we derive the curvature in closed form, specifically, a matrix-valued measure supported on the walls of the normal fan. This measure depends only on the feasible set, with the data distribution entering only as a weight. We then offer a tractable approximation for this curvature, computable with just one projection to the feasible set. We prove that the approximation weakly converges to the true population curvature. We offer one application of our findings, a decision-aware scenario generation method for expected-cost linear optimization. Our experiments test the quadratic and weak convergence laws and show a 30.8% regret improvement over uniform allocation on battery arbitrage.
Konstantinos Ziliaskopoulos, Alexander Vinel, Alice E. Smith
Auburn University Auburn, AL, USA · University of Alabama Tuscaloosa, AL, USA
Optimization problems routinely depend on uncertain parameters that must be predicted before a decision is made. Classical robust and regret formulations are designed to handle erroneous predictions and can provide statistical error bounds in simple settings. However, when predictions lack rigorous error bounds (as is typical of modern machine learning methods) classical robust models often yield vacuous guarantees, while regret formulations can paradoxically produce decisions that are more optimistic than even a nominal solution. We introduce Globalized Adversarial Regret Optimization (GARO), a decision framework that controls adversarial regret, defined as the gap between the worst-case cost and the oracle robust cost, uniformly across all possible uncertainty set sizes. By design, GARO delivers absolute or relative performance guarantees against an oracle with full knowledge of the prediction error, without requiring any probabilistic calibration of the uncertainty set. We show that GARO equipped with a relative rate function generalizes the classical adaptation method of Lepski to downstream decision problems. We derive exact tractable reformulations for problems with affine worst-case cost functions and polyhedral norm uncertainty sets, and provide a discretization and a constraint-generation algorithm with convergence guarantees for general settings. Finally, experiments demonstrate that GARO yields solutions with a more favorable trade-off between worst-case and mean out-of-sample performance, as well as stronger global performance guarantees.
Contextual decision making uses observed covariates to guide decisions under uncertainty. Two natural approaches are predict-then-optimize (PtO), which learns the conditional expected objective, and generate-then-optimize (GtO), which learns conditional uncertainty and optimizes using generated scenarios. We study when each approach is preferable by examining how the choice of learning target affects statistical accuracy and optimization tractability. Although PtO learns a narrower target, our regret bounds show how differences in smoothness can offset GtO's additional dimensional burden. Exploiting smoothness also raises an optimization tradeoff: within the class of nonnegative-weight PtO methods studied, a lower bound limits the gains from additional smoothness, while more flexible methods may introduce signed weights and lose the guarantee of preserving convexity. GtO preserves scenario-wise convexity, but requires learning a richer object and generating scenarios for optimization. Synthetic experiments and a real case study illustrate how these tradeoffs vary with data availability and problem structure. Together with the scope for reusing a model across tasks, our findings provide practical guidance for choosing between the approaches without identifying a universal winner.
L. Jeff Hong, Weihuan Huang, Xinyao Li
Department of Industrial and Systems Engineering, University of Minnesota, Minneapolis, MN 55455, U.S. · School of Management & Engineering, Nanjing University, Nanjing 210093, China