The Curvature of Regret in Contextual Linear Optimization
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.
Related
- Curvature-Independent Regret Bounds for Distributed Online Optimization on Hadamard Manifolds
- Tight Regret Bound for Online Inverse Linear Optimization via Multiscale Matrix Weights
- Online Inverse Integer Linear Optimization via Small-Gradient Skipping: Constant Regret and Finite Mistakes
- Preventing Model Extraction in Contextual Linear Optimization
- Policy Regret for Embedding Model Routing: Contextual Bandits with Low-Rank Experts
BibTeX
@misc{ziliaskopoulos2026curvature,
title = {{The Curvature of Regret in Contextual Linear Optimization}},
author = {Konstantinos Ziliaskopoulos and Alexander Vinel and Alice E. Smith},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.01980},
eprint = {2610.01980},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.01980},
}
RIS
TY - UNPB
TI - The Curvature of Regret in Contextual Linear Optimization
AU - Konstantinos Ziliaskopoulos
AU - Alexander Vinel
AU - Alice E. Smith
PY - 2026
DA - 2026/10/01
PB - arXiv
DO - 10.48550/arxiv.2610.01980
UR - https://arxiv.org/abs/2610.01980
AB - 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.
ER -