The Curvature of Regret in Contextual Linear Optimization
Contextual linear optimization faces a discontinuity: small prediction errors can flip the LP solution to a different vertex, making regret non-differentiable pointwise. This paper proves that, after averaging over the data distribution, the population regret is locally quadratic with curvature concentrated on the walls of the normal fan. The authors derive the exact curvature measure $K_0$, provide a tractable single-projection approximation $\mathsf{K}_{\lambda,s}$, and apply it to scenario generation, showing a $30.8\%$ regret reduction on a battery arbitrage task.
The paper delivers a carefully constructed asymptotic theory that turns the combinatorial non-smoothness of LP regret into a closed-form geometric measure. Theorem 1 shows that excess regret scales as $\frac{\varepsilon^2}{2}\kappa_p(h)$ for small perturbations, with $\kappa_p$ supported on codimension-one walls, and Theorem 2 proves that the regularized surrogate $\mathsf{K}_{\lambda,s}$ converges weakly to this limit. The application to curvature-weighted scenario generation is elegant but narrow: it assumes polyhedral sets, Lipschitz densities, and a heuristic choice of $\lambda$ whose theoretical grounding is deferred to future work.
The derivation of the curvature measure $K_0$ is rigorous and geometrically intuitive. The proof strategy—handling degenerate intersections via codimension-two volume bounds and reducing regular wall crossings to the triangular integral of Lemma 2—is tight. The practical payoff is Proposition 1, which shows that the surrogate $\mathsf{K}_{\lambda,s}$ can be obtained from a single Euclidean projection by scaling the orthogonal projector onto the active face, making the method genuinely tractable.
The results are strictly local. The authors acknowledge that "As the size of the perturbations increases, the behavior of regret becomes increasingly less quadratic, as expected from the local characterization of Theorem 1" once perturbations grow beyond the asymptotic regime. Assumption 1 also demands Lipschitz densities and bounded perturbations on a compact set, which may fail in high-dimensional or heavy-tailed contextual settings.
A second limitation is practical applicability. The battery-arbitrage experiment relies on a heuristic for the regularization parameter, and the authors state: "We aim to provide a systematic calibration and theoretical analysis in the extended version." Moreover, the extension to integer programs is mentioned but left essentially open: "estimating curvature is more difficult, since the projection and the convex hull are not readily available."
The numerical evidence strongly supports the theoretical predictions in low dimensions: log-log excess-regret slopes are $1.980$–$2.016$ for a triangle, pentagon, and cube, and the empirical quadratic coefficients deviate from the analytical $\kappa_p(h)$ by only $0.84\%$–$2.75\%$ at the smallest tested perturbation. The weak-convergence claim is also verified with high precision. Comparison to related work is fair but limited; the paper correctly contrasts its exact second-order constant against margin-based fast-rate bounds, yet it does not benchmark the proposed scenario-generation rule against modern end-to-end decision-focused learning pipelines.
The paper provides substantial experimental detail in Appendix B, including polytope coordinates, quadrature orders, and the exact battery LP formulation. Algorithm 1 spells out the allocation rule. However, no code repository or hyperparameter configuration files are mentioned, and the smoothing parameter $\lambda$ is set by an ad hoc heuristic ($\widehat{\lambda} = \frac{\frac{1}{n_G}\sum_{i=1}^{n_G}\|\tilde{q}_i\|}{R}(\log \ell / n_G)^{1/3}$) that lacks theoretical justification in this version. Reproducing the 48-dimensional battery projection and the CAISO data pipeline is possible from the text but would require significant engineering without released code.
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.
Pick a starting point or write your own. Challenges run in the background, so you can keep reading while the AI investigates.
No challenges yet. Disagree with the review? Ask the AI to revisit a specific claim.