The Curvature of Regret in Contextual Linear Optimization

AI summary

Overview

Research area: Decision-focused learning and predict-then-optimize systems, specifically the geometry of regret in contextual linear optimization.

Technical level: Advanced. The paper relies on polyhedral geometry (normal fans, walls, jumps of the optimizer), matrix-valued measures, weak convergence of measures, and Euclidean projection onto polytopes.

Scope in one sentence: The paper shows that although the pointwise regret of a linear program's optimizer is discontinuous in the predicted cost vector, population regret becomes locally quadratic after averaging over the data distribution, and it derives that curvature in closed form as a measure supported on the walls of the optimizer's normal fan.

Authors and affiliations: Konstantinos Ziliaskopoulos and Alexander Vinel (Auburn University, Auburn, AL, USA); Alice E. Smith (University of Alabama, Tuscaloosa, AL, USA). arXiv:2610.01980v1 [cs.LG], 01 October 2026.

What This Paper Is About

In Predict-then-Optimize systems, a model first forecasts the unknown cost coefficients of a linear program and then solves the LP to obtain a decision. A small forecasting error usually leaves the optimal decision unchanged, but occasionally it flips the decision to a different vertex, so the regret as a function of the cost vector is discontinuous and non-smooth point by point. The paper asks what happens to this regret when it is averaged over the data distribution, and it shows the averaged (population) regret is locally quadratic in the size of the prediction error, with curvature that can be written down in closed form and approximated tractably.

Key Contributions

1. A quadratic law for population regret. The paper proves that excess regret scales as ε²/2 times a curvature coefficient κ_p(h) as the perturbation size ε decreases, even though the pointwise regret is discontinuous.

2. A closed-form curvature measure concentrated on walls. The curvature is expressed as a sum of integrals over the codimension-one walls of the normal fan, with an explicit integrand combining the density of the conditional cost at the wall, the severity of the decision switch, and the component of the prediction error orthogonal to the wall. The wall structure depends only on the feasible set, with the data distribution entering only as a weight.

3. A tractable, projection-based approximation with a convergence proof. The paper defines a quadratically regularized decision rule whose Jacobian gives a regularized curvature matrix K_{λ,s}, shows it is computable from a single projection to the feasible set, and proves it weakly converges to the true population curvature measure K_0 as λ goes to zero.

4. An application to decision-aware scenario generation. The curvature is used to derive a local bias-variance decomposition of generated-scenario regret and a curvature-weighted allocation rule that assigns scenario budget to generators whose dispersion aligns with curvature on the LP walls.

Main Findings

• Wall-concentrated curvature: Population curvature is supported on the codimension-one walls of the normal fan, a set of measure zero, identified as the collection of walls W(S). As a result it does not appear as an ordinary Hessian at individual cost vectors.

• Local quadratic rate: Under stated regularity assumptions, with f_ε(X) = Q + εh(Q) where Q = E[C | X], the excess regret satisfies R(f_ε) − R*_X = (ε²/2) κ_p(h) + o(ε²); equivalently the limit of 2(R(f_ε) − R*_X)/ε² as ε decreases to zero equals κ_p(h).

• Closed-form integrand: The curvature is κ_p(h) = Σ_{W in W(S)} ∫_W [p(q)/||d_W||] (d_W^T h(q))² dH^{d−1}(q), where p is the density of the conditional cost, d_W the jump vector of the wall, and h the perturbation field. The paper describes this as a decomposition into (i) density at the wall, (ii) severity of the decision switch, and (iii) the error component orthogonal to the wall.

• Matrix-valued measure K_0: The curvature can be written as the integral of p(q)h(q)^T dK_0 h(q), where K_0 = Σ_W (d_W d_W^T / ||d_W||) H^{d−1} restricted to W. Because K_0 is singular and supported on the walls, it is difficult to estimate directly.

• Regularized surrogate and weak convergence: With w_{λ,s}(q) = arg min_{w in S} {q^T w + (λ/2)||w − s||²}, which equals Π_S(s − q/λ), the regularized curvature is K_{λ,s}(q) = −D_q w_{λ,s}(q) = (1/λ) J Π_S(s − q/λ). As λ decreases to zero, K_{λ,s} weakly converges to K_0, and consequently E[h(Q)^T K_{λ,s}(Q) h(Q)] = κ_p(h) + O(λ). Combining with the quadratic law gives R(f_ε) − R*X = (ε²/2) E[h^T K{λ,s}(Q) h] + o(ε²) + O(ε²λ).

• Only edges survive the limit: At λ → 0, only edges contribute to the population regret, while higher-dimensional faces and vertices contribute nothing. Vertices contribute nothing because the tangent space is {0}; faces with dimension at least 2 contribute O(λ) and vanish in the limit.

• One projection suffices: For y = Π_S(s − q/λ) and the face F containing y in its relative interior, K_{λ,s}(q) = (1/λ) Π_{T_F} for almost every q, where T_F = span(F − F). If S = {w : Aw ≤ β} and A_F stacks the rows active at y, then Π_{T_F} = I_d − A_F^T (A_F A_F^T)^† A_F. The paper describes K_{λ,s} as a smoothed surrogate of the wall density, O(1) in magnitude on a tube of width O(λ) around each wall.

• Excess regret depends only on the conditional mean: Lemma 1 establishes that R(f) − R*_X = E[Q^T w*(f(X)) − z_S(Q)] ≥ 0, so the relevant cost vector is the conditional mean Q = E[C | X] rather than E[C].

• Random perturbation extension: The quadratic law extends to random perturbations; with Γ(q) = E[ΔΔ^T | Q = q], the expected regret is (ε²/2) Σ_E ∫_{F_E} [p(q)/||d_E||] d_E^T Γ(q) d_E dH^{d−1}(q) + o(ε²).

• Bias-variance split for scenario generation: For generator k with mean μ_k(X), covariance Σ_k(X), bias b_k(X) = μ_k(X) − Q(X), and joint error term η_k² = ||b_k||²_{L²(P_X)} + 1/M_k, the regret decomposes into a decision-relevant bias term (1/2)E[b_k^T K_{λ,s}(Q) b_k], a decision-relevant Monte Carlo noise term (1/(2M_k)) E[tr(K_{λ,s}(Q) Σ_k)], and remainders o(η_k²) + O(λ η_k²). Only the second term depends on the number of scenarios.

• Experiment: quadratic rate validation. On a 2D triangle, a 2D pentagon, and a 3D cube, empirical log–log slopes of excess regret ranged from 1.980 to 2.016, close to the quadratic rate of 2 predicted by the theory. Behavior became less quadratic as perturbation size increased.

• Experiment: approximation accuracy. The empirical quantity E[h(Q)^T K_{λ,s}(Q) h(Q)] at λ = 2^{-9} was within 5·10^{-5}% to 0.016% of κ_p(h) across the three geometries, and the empirical quadratic coefficient 2(R(f_ε) − R*_X)/ε² at the smallest perturbation ε = 2^{-9} differed from the analytically computed curvature by only 0.84% to 2.75%.

• Experiment: battery arbitrage. In a 24-hour battery arbitrage LP using CAISO price data, with two generators (a common price shift and a peak versus off-peak generator) and λ = 11.55 set by a scale-normalized heuristic, the allocation rule identified off-peak prices as most decision relevant and produced a 30.8% improvement in expected-cost regret over uniform allocation, averaged across 500 runs.

• Integer program extension: Because integer programs can be represented by an LP on their convex hull, the same quadratic behavior and curvature exist, but estimating curvature is harder since the projection and convex hull are not readily available.

Methodology in Plain English

The authors start from a standard Predict-then-Optimize setup: a feasible set S that is a compact convex polytope, a cost predictor f, and regret measured against the best achievable regret R*_X when decisions may depend only on the features X. They first show, via a conditioning argument, that the excess regret depends only on the conditional mean Q = E[C | X].

They then study what happens when the predictor is nearly correct, writing f_ε(X) = Q + εh(Q) for a small perturbation field h. The key geometric fact is that the optimizer is constant on each cone of the polytope's normal fan, and the cones meet on walls that correspond to edges of S. A small perturbation can only change the decision if the cost vector sits within O(ε) of a wall, and when a wall is crossed the regret incurred is proportional to the distance the perturbation carries the cost vector past the wall. Multiplying the O(ε) probability of being near a wall by the O(ε) regret of crossing yields O(ε²), which the authors make exact by reducing the per-wall calculation to a small one-dimensional integral (evaluated in closed form as b²/2) and by showing that the set where three or more optimizer cones meet contributes only O(ε³) and therefore vanishes at second order.

Because the resulting curvature is a matrix-valued measure supported on a measure-zero set, comparing it pointwise to a smooth matrix-valued function is inappropriate. The authors therefore use the weak formulation of measures, integrating both the true curvature measure and a regularized surrogate against compactly supported Lipschitz test matrices. The surrogate is built from a quadratically regularized decision rule anchored at a reference point s in the relative interior of S, which is equivalent to a Euclidean projection of s − q/λ onto S. On each cell of the polytope's normal manifold the projection is affine, so its Jacobian is the orthogonal projector onto the directions spanned by the projected face; scaling by 1/λ over a tube of width O(λ) produces a smoothed wall density. They then apply this machinery to expected-cost stochastic programs driven by the sample mean of M generated scenarios, splitting the local regret into a generator bias term and a 1/M Monte Carlo covariance term weighted by curvature, and allocate scenario budget proportionally to the square root of tr(K_{λ,s} Σ).

Why This Matters

Impact on research. The paper explains why decision-focused learning for linear optimization behaves better than the discontinuity of the optimizer would suggest: the non-smoothness is a pointwise phenomenon that disappears under averaging, leaving a quadratic local landscape whose curvature lives on decision boundaries. It also identifies the object that several existing approaches—margin conditions for fast regret rates, local quadratic and metric losses in decision-focused learning, and quadratic regularization and projection methods for differentiable prediction maps—are approximating in the λ → 0 limit, unifying them under the measure K_0.

Real-world applications (as identified or implied by the paper's framing):

• Energy: the paper's own experiment uses a 24-hour battery arbitrage LP with CAISO electricity price data, with peak versus off-peak price generators.
• Contextual stochastic optimization with expensive conditional scenario generation, where a fixed generation budget must be shared across many decision problems.
• Evaluation criteria and loss design for decision-focused learning pipelines, using the curvature as a measure of decision relevance.
• Decision-aware compression and local statistical efficiency in contextual linear optimization, named as potential applications in the paper.

Industry relevance. Any operation that forecasts uncertain coefficients and then solves a linear program—pricing, procurement, scheduling, energy dispatch, inventory allocation—can use the curvature-weighted allocation rule to spend limited simulation or generative modeling compute where uncertainty actually changes the decision, rather than spreading it uniformly. The reported 30.8% regret improvement over uniform allocation on battery arbitrage gives a concrete sense of the potential gain.

Future Directions

1. Integer programs. Although the theory carries over to (mixed) integer programs through the LP on their convex hull, the projection and convex hull are not readily available, so an approximation applicable to IPs is needed.

2. Weaker regularity conditions. Identifying relaxed conditions on the cost density p(q) under which quadratic behavior still persists is left open.

3. Choosing λ and s. Quantifying how the choice of the reference point s controls the approximation bias of K_{λ,s}, and developing practical guidelines for selecting λ and s, are named as future work. In the experiments λ was set by a scale-normalized heuristic with no general rule stated.

4. Additional applications. Beyond the scenario allocation rule presented, the authors point to local statistical efficiency in contextual linear optimization, decision-aware compression, and evaluation criteria for decision-focused learning.

Target Audience

Researchers and graduate students working at the intersection of machine learning and optimization—especially decision-focused learning, predict-then-optimize, contextual stochastic optimization, and scenario generation—who are comfortable with polyhedral geometry, measure-theoretic convergence arguments, and linear programming. Practitioners designing scenario generation or simulation budgets for optimization under uncertainty will benefit from the allocation heuristic, though the theoretical sections require an advanced mathematical background. Beginners will find the qualitative message accessible (regret is locally quadratic, curvature lives on decision boundaries, one projection suffices) but the derivations advanced.

Authors’ 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.