Source-linked AI summary
The Curvature of Regret in Contextual Linear Optimization
Konstantinos Ziliaskopoulos, Alexander Vinel, Alice E. Smith
TL;DR
The remaining excess regret depends on whether the decision selected using f(X) is suboptimal under Q = E[C | X]. The paper derives wall-supported population curvature and approximates it with regularized curvature that can be computed using one projection onto the feasible set. 30.8% improvement in expected-cost regret over uniform allocation, averaged across 500 battery-arbitrage runs.
Problem
The remaining excess regret depends on whether the decision selected using f(X) is suboptimal under Q = E[C | X].
Source: §1 · p. 1Method
The paper derives wall-supported population curvature and approximates it with regularized curvature that can be computed using one projection onto the feasible set.
Source: §1 · pp. 2–3Results
30.8% improvement in expected-cost regret over uniform allocation, averaged across 500 battery-arbitrage runs.
Source: §2 · p. 4Takeaways & Limitations
Curvature can guide scenario allocation toward generated variance that is decision-relevant on LP walls.
Source: §1 · p. 3For integer programs, estimating curvature is more difficult because the projection and convex hull are not readily available.
Source: §2 · p. 4
Abstract
from arXiv · showhide
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.
1 Problem Setup and Main Results
Although pointwise LP regret is discontinuous, population regret is locally quadratic around the conditional mean cost Q = E[C | X]. Its curvature is a matrix-valued measure concentrated on optimizer-fan walls, with a regularized approximation that converges weakly and supports curvature-weighted scenario allocation.
1 Problem Setup and Main Results
- A small perturbation changes the decision only near a wall, and each crossing incurs O(ε) regret, yielding O(ε²) expected regret.The curvature integrand reflects conditional-cost density at the wall, decision-switch severity, and the error component orthogonal to the wall.Source: §1 · p. 2
- For LPs, prior quadratic-regularization and projection-based decision losses coincide with Kλ,s, whose λ-downarrow-0 target is K0.This identifies the population-curvature measure approximated by those constructions.Source: §1 · p. 2
- Under the stated regularity assumptions, population LP regret is locally quadratic, with closed-form curvature represented by a matrix-valued measure on optimizer-fan walls.The regret-relevant cost vector is the conditional mean Q = E[C | X].Source: §1 · pp. 2–3
- The regularized curvature Kλ,s converges weakly to K0 as λ decreases to zero and can be estimated after one projection onto the feasible set.The projection identifies the active face; its parallel-direction projector, scaled by 1/λ, gives Kλ,s.Source: §1 · pp. 2–3
- At the limit, only edges contribute to population regret; higher-dimensional faces and vertices contribute nothing.Vertices have zero tangent projector, while contributions from faces of dimension at least two vanish with λ.Source: §1 · p. 3
- For expected-cost LPs, local regret separates into a wall-weighted generator-bias term and a 1/M Monte Carlo covariance term.The allocation rule assigns more scenarios where generated dispersion aligns with curvature on LP walls, across a shared budget for contextual problems.Source: §1 · p. 3
2 Experiments & Conclusion
Experiments support the local quadratic and curvature-approximation claims, while battery arbitrage shows a regret gain from curvature-weighted scenario allocation. The conclusion notes a harder estimation boundary for integer programs.
Experiments
- 1.980 to 2.016 log–log slopes across triangle, pentagon, and cube tests were close to the predicted quadratic rate, with larger perturbations becoming less quadratic.Source: §2 · p. 4
- At λ = 2^-9, the approximation and analytic curvature differed by 5 · 10^-5% to 0.016% across three geometries.The experiments also verify that the approximation converges as λ → 0.Source: §2 · p. 4
- 30.8% lower expected-cost regret than uniform allocation was achieved on 24-hour battery arbitrage, with most scenario budget assigned to off-peak prices.The improvement is averaged across 500 runs.Source: Figure 2 · p. 4, §2 · p. 4
Conclusion
- The authors extend the curvature result to mixed integer programs, but estimating it is harder when projection and the convex hull are unavailable.Source: §2 · p. 4
A Proofs
The proofs establish that excess regret depends on the conditional mean and that perturbations produce a local quadratic contribution concentrated on optimizer walls. They also justify weak convergence of the regularized curvature and derive the one-projection surrogate and curvature-weighted scenario allocation.
Proof of Lemma 1
- The regret comparison reduces to the conditional mean: conditioning on X and canceling the common expected optimal-cost term yields the excess-regret expression.The optimizer’s optimality gives Q⊤g(X) ≥ zS(Q), with equality for w⋆(Q).Source: A Proofs · p. 7
Proof of Theorem 1
- At intersections of multiple walls, the contribution is O(ε3); elsewhere, a perturbation changes the optimizer only by crossing one wall.The degenerate set has codimension at least two, so its O(ε2) neighborhood combines with O(ε) pointwise regret.Source: A Proofs · pp. 7–8
- Across a regular wall, only cost vectors within O(ε) can cross it, and their O(ε) regret yields the local quadratic term after integration.The proof parameterizes cost vectors as q = a + tnE and rescales t = εu, using regularity of p and h.Source: A Proofs · pp. 7–8
Proof of Corollary 1
- For random generator errors, the proof separates bias and Monte Carlo error and applies the random-perturbation result under uniform regularity conditions.Conditional i.i.d. sampling supplies the covariance term in the bias–variance decomposition.Source: A Proofs · pp. 8, 11
Proof of Theorem 2
- Weak convergence holds because faces of dimension at least two and vertices vanish in the limit, while edge contributions persist and sum to K0.The convergence is tested by integrating against compactly supported matrix-valued functions; choosing Φ(q) = p(q)h(q)h(q)⊤ gives the curvature coefficient.Source: A Proofs · pp. 9–10
Proof of Proposition 1
- One projection identifies the active face, after which Kλ,s is its tangent-space projector scaled by 1/λ.The active-set form uses the constraint rows active at the projection.Source: A Proofs · p. 10
Proof of Proposition 2
- The optimal scenario allocation follows from minimizing the curvature-weighted variance term under a fixed budget, with zero-curvature contexts receiving zero budget.The practical implementation may impose a positive minimum count and allocate the remainder according to the rule.Source: A Proofs · pp. 11–12
B Experimental details
The experiments use three polytope geometries to test the quadratic regret expansion and compare curvature-based scenario allocation with uniform allocation in battery arbitrage. The appendix describes how curvature and regret are computed and how the battery scenarios are generated.
Quadratic-rate experiment
- The quadratic-rate test uses a triangle, pentagon, and cube, with empirical excess regret compared against the analytically computed curvature coefficient across decreasing perturbation sizes.It uses 2 × 10^6 samples and evaluates ε from 2^-1 to 2^-9.Source: B Experimental details · p. 12
Computing κp
- Curvature is computed by parameterizing normal-fan walls and evaluating their integrals with Gauss–Legendre quadrature; doubling the quadrature order changed reported values negligibly.The tests use constant and affine perturbations, which perform similarly.Source: B Experimental details · p. 12
Battery arbitrage experiment
- The CAISO battery experiment uses 24-hour price vectors; both generators use σ = 9.2103 USD/MWh and unit-norm directions, yielding equal total variance, with one shifting prices and the other changing peak/off-peak prices.Scenarios are averaged before the LP is solved; one sign raises peak prices by approximately 3.04 USD/MWh and lowers off-peak prices by approximately 2.53 USD/MWh, with the other sign reversing those changes.Source: B Experimental details · p. 13
Battery arbitrage implementation
- The implementation projects onto the battery polytope, computes regularized curvature in dispatch-variable space, then maps it back to price space.The battery polytope is represented in charge and discharge variables after eliminating state variables.Source: B Experimental details · p. 13
Conditional scenario generators
- The peak/off-peak generator changes prices in opposite directions across time bands, while the common-shift generator moves every hourly price together.Both use the same σ, set to the median hourly price variability across days.Source: B Experimental details · p. 13