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

Conformal robust optimization usually calibrates prediction residuals, although residual size can be poorly aligned with downstream regret. We introduce \emph{Conformal Regret Sets}, a post-hoc framework that conformalizes SPO+ and uses its calibrated level set for minimax-regret refinement. Directly conformalizing exact regret certifies the nominal predict-then-optimize decision but, without exogenous bounded support, leaves every alternative decision with unbounded worst-case regret. SPO+ avoids this degeneracy while retaining distribution-free finite-sample validity. For contextual linear programs, its level set decomposes into normal-fan-aligned polyhedra: a piece is nonempty exactly when its vertex has predicted gap at most half the calibrated threshold, and all active vertices can be generated locally. The same geometry yields margin-adaptive regret certificates and certified early termination. Fractional-knapsack experiments validate these results and show that continuous refinement reduces the $0.95$-quantile and $\operatorname{CVaR}_{0.95}$ of regret by $9.1\\%$ and $13.1\\%$ respectively.