Curvature of regret improves decisions in linear optimization problems
The Curvature of Regret in Contextual Linear Optimization
Machine Learning
Summary
Choosing the best option in certain math problems can be tricky because small mistakes don't always change the decision, or they might change it suddenly. The paper shows that when looking at many examples together, this tricky behavior smooths out in a predictable way that follows a quadratic pattern. The authors found a formula to describe this smoothing and made an easy way to calculate it. They used this idea to create better scenarios for planning and showed it works well in battery charging decisions.
What this means in practice
- •For optimization engineers: Improve scenario generation for expected-cost linear optimization using curvature-based insights to reduce regret in decision-making.
- •For energy system operators: Enhance battery arbitrage strategies by applying curvature approximations to lower regret and improve performance.
Tested on one dataset.
Authors
Konstantinos Ziliaskopoulos, Alexander Vinel, Alice E. Smith
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.