stat.MLNov 9, 2026

Beyond Prediction Residuals: Conformal Regret Calibration for Robust Contextual Linear Optimization

Authors: Lingjie Zhao, Hansheng Jiang, Wei Qi

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 (η−2Γ)+(η-2Γ)_+, with an exact early exit when η≤2Γη\leq 2Γ. Experiments on contextual fractional knapsack validate the geometry and certificates: continuous refinement reduces the 0.950.95-quantile and CVaR⁡0.95\operatorname{CVaR}_{0.95} of regret by 9.1%9.1\% and 13.1%13.1\% relative to nominal PTO, while vertex-restricted refinement changes only 10.0%10.0\% of nominal decisions.

Figures & tables

Appendix figures & tables9 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. The Curvature of Regret in Contextual Linear Optimization

    Oct 1, 2026Konstantinos Ziliaskopoulos, Alexander Vinel, Alice E. SmithDecision-Focused LearningRegret Minimization

  2. Globalized Adversarial Regret Optimization: Robust Decisions with Uncalibrated Predictions

    Mar 26, 2026Jannis Kurtz, Bart P. G. van ParysRobust OptimizationPredict-Then-Optimize

  3. Contextual Decision Making: Predictive or Generative

    Oct 23, 2026L. Jeff Hong, Weihuan Huang, Xinyao LiPredict-Then-OptimizeDecision-Making under Uncertainty