# Regret Equals Covariance: A Closed-Form Characterization for Stochastic Optimization

arXiv: https://arxiv.org/abs/2605.14019 · HTML: https://mlsanity.com/paper/2605.14019/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 96 references that are in the map.
- First posted on arXiv 13 May 2026.

## Builds on (most cited first, 24 of 24)

- [Counterfactual Explanations without Opening the Black Box: Automated Decisions and the GDPR](https://mlsanity.com/paper/1711.00399/) (2017)
- [Computational Optimal Transport](https://mlsanity.com/paper/1803.00567/) (2018)
- [CVXPY: A Python-Embedded Modeling Language for Convex Optimization](https://mlsanity.com/paper/1603.00943/) (2016)
- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [OptNet: Differentiable Optimization as a Layer in Neural Networks](https://mlsanity.com/paper/1703.00443/) (2017)
- [Differentiable Convex Optimization Layers](https://mlsanity.com/paper/1910.12430/) (2019)
- [Smart "Predict, then Optimize"](https://mlsanity.com/paper/1710.08005/) (2017)
- [Data-driven Distributionally Robust Optimization Using the Wasserstein Metric: Performance Guarantees and Tractable Reformulations](https://mlsanity.com/paper/1505.05116/) (2015)
- [Combinatorial optimization and reasoning with graph neural networks](https://mlsanity.com/paper/2102.09544/) (2021)
- [Melding the Data-Decisions Pipeline: Decision-Focused Learning for Combinatorial Optimization](https://mlsanity.com/paper/1809.05504/) (2018)
- [Differentiation of Blackbox Combinatorial Solvers](https://mlsanity.com/paper/1912.02175/) (2019)
- [Learning to Optimize](https://mlsanity.com/paper/1606.01885/) (2016)
- [Distributionally Robust Stochastic Optimization with Wasserstein Distance](https://mlsanity.com/paper/1604.02199/) (2016)
- [Wasserstein Distributionally Robust Optimization: Theory and Applications in Machine Learning](https://mlsanity.com/paper/1908.08729/) (2019)
- [End-to-End Constrained Optimization Learning: A Survey](https://mlsanity.com/paper/2103.16378/) (2021)
- [Interior Point Solving for LP-based prediction+optimisation](https://mlsanity.com/paper/2010.13943/) (2020)
- [A Survey of Contextual Optimization Methods for Decision Making under Uncertainty](https://mlsanity.com/paper/2306.10374/) (2023)
- [Learning with Differentiable Perturbed Optimizers](https://mlsanity.com/paper/2002.08676/) (2020)
- [Finite-Sample Guarantees for Wasserstein Distributionally Robust Optimization: Breaking the Curse of Dimensionality](https://mlsanity.com/paper/2009.04382/) (2020)
- [End-to-End Learning and Intervention in Games](https://mlsanity.com/paper/2010.13834/) (2020)
- [Data-Pooling in Stochastic Optimization](https://mlsanity.com/paper/1906.00255/) (2019)
- [Decision-Aware Conditional GANs for Time Series Data](https://mlsanity.com/paper/2009.12682/) (2020)
- [Learning-based Robust Optimization: Procedures and Statistical Guarantees](https://mlsanity.com/paper/1704.04342/) (2017)
- [Benchmarking PtO and PnO Methods in the Predictive Combinatorial Optimization Regime](https://mlsanity.com/paper/2311.07633/) (2023)

## Built on by (most cited first, 4 of 4)

- [Evaluating AI Investment Strategies](https://mlsanity.com/paper/2606.08791/) (2026)
- [Optimizing Regret](https://mlsanity.com/paper/2607.18866/) (2026)
- [Eigenvalue-Decomposition Cost Denoising for Predict-then-Optimize](https://mlsanity.com/paper/2609.15111/) (2026)
- [Jacobian Rank Collapse in Decision-Focused Learning](https://mlsanity.com/paper/2609.39261/) (2026)

## Abstract (arXiv)

Quantifying regret typically involves repeatedly re-solving a stochastic optimization problem across simulated scenarios. Such an approach is costly: the cost scales with the number of scenarios and the cost of each solve. We propose that regret can instead be measured using the joint moments of the cost vector c and the optimal decision π^*(c). Working with the optimal concave and Lipschitz under only a feasible region value function v(c) = minz∈ Z c^top z, we show that regret always decomposes as Regret = -Cov(c,π^*(c)) - R(c) for a residual R(c). We further show that R(c)=0 when π^* is affine in c, which holds for unconstrained and equality-constrained (e.g., budget-constrained Markowitz) quadratic programs and many, but not all, linear programs. For all cases, we give a distribution-free bound Regret ≤ D√tr(Sigmac) that depends only on the radius of the feasible region and the cost covariance. We also derive concentration and asymptotic-normality results for the empirical regret, the latter under an explicit and checkable non-degeneracy condition.