The Curvature of Regret in Contextual Linear Optimization

Konstantinos Ziliaskopoulos; Alexander Vinel; Alice E. Smith

cs.LGOct 1, 2026

The Curvature of Regret in Contextual Linear Optimization

Authors: Konstantinos Ziliaskopoulos, Alexander Vinel, Alice E. Smith

Organizations: Auburn University Auburn, AL, USA · University of Alabama Tuscaloosa, AL, USA

Abstract

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.

Figures & tables

Panel of Figure 1 — Figure 1 : The normal fan of a triangle feasible set. In the shaded $O(\varepsilon)$ neighborhood of the wall $q_{1}=q_{2}$ we show that an $O(\varepsilon)$ perturbation can change the decision only for cost vectors inside it, and each crossing incurs $O(\varepsilon)$ regret, which is the source of local quadratic behavior.

Panel of Figure 2 — Figure 2 : We demonstrate the local quadratic rate of population regret and compare generation rules, showing our curvature weighted rule correctly allocates budget to relevant generative variance.

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 3 — Figure 3 : The normal manifold of $S=[-1,1]^{2}$ , which partitions $\mathbb{R}^{d}$ into regions where the projection operator $\Pi_{S}$ is affine, and therefore by Proposition 1 $\mathsf{K}_{\lambda,s}=\nicefrac{{1}}{{\lambda}}\Pi_{T_{F}}$ is constant. The points are $x=s-\nicefrac{{q}}{{\lambda}}$ and $y=\Pi_{S}(x)$ the resulting projection. If two points $x$ and $x^{\prime}$ are in the same cell, they both project to the same face $F$ of $S$ . By Theorem 2 , only the edge cells (shaded dark) remain in the limit as $\lambda\downarrow 0$ .

Explore similar work

Decision-Focused Learning via Tangent-Space Projection of Prediction Error
May 2, 2026Junhyeong Lee, Sangjin Jin, Yongjae LeePlan Regret Prediction Error
Department of Industrial Engineering, Ulsan National Institute of Science and Technology, Ulsan, South Korea.
Regret Equals Covariance: A Closed-Form Characterization for Stochastic Optimization
May 13, 2026Irene AldridgeOptimal Regret Regret
Decision-Focused On-Policy Learning for Contextual Linear Optimization with Partial Feedback
May 31, 2026Wyame Benslimane, Tinghan Ye, Pascal Van Hentenryck +1Contextual Bandit Framework On-Policy
Department of Industrial Engineering and Operations Research University of California, Berkeley · H. Milton Stewart School of Industrial and Systems Engineering Georgia Institute of Technology

May 2, 2026, cs.LGJ/K move · Enter open · S save

Decision-Focused Learning via Tangent-Space Projection of Prediction Error

Junhyeong Lee, Sangjin Jin, Yongjae Lee

Department of Industrial Engineering, Ulsan National Institute of Science and Technology, Ulsan, South Korea.

Plan Regret Prediction Error Structural Constraints Solver Iterations

Open paper AskPDF arXiv

Decision-Focused Learning (DFL) trains predictors to improve downstream decision quality, but computing regret gradients typically requires differentiating through solvers or relying on surrogate losses, which can be computationally expensive or deviate from the true objective. We show that, under standard regularity with locally stable active constraints, the regret gradient admits a closed-form geometric characterization, equivalent to the prediction error projected onto the tangent space of active constraints, scaled by local curvature. This reveals that regret gradients can be obtained by filtering decision-irrelevant components from the MSE gradient, providing a simpler and more direct alternative to existing approaches. Based on this, we propose PEAR (Projected Error As Regret-gradient), which computes regret gradients via a reduced linear system over active constraints, avoiding differentiation through solver iterations or additional optimization solves. Experiments on LP benchmarks and a real-world QP task show that PEAR achieves the best decision quality among all baselines while being the most computationally efficient, with gains that persist under constraint shifts.

Abstract

Explore similar work

Decision-Focused Learning via Tangent-Space Projection of Prediction Error

Regret Equals Covariance: A Closed-Form Characterization for Stochastic Optimization

Decision-Focused On-Policy Learning for Contextual Linear Optimization with Partial Feedback