Regret Equals Covariance: A Closed-Form Characterization for Stochastic Optimization
econ.EM, cs.LG, math.ST, stat.CO, stat.TH
Submitted: 2026-05-13
Updated: 2026-09-27
Comments: 19 pages
License: http://creativecommons.org/licenses/by/4.0/
The gist: Quantifying regret typically involves repeatedly re-solving a stochastic optimization problem across simulated scenarios.
Terminology
Abstract
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) = z in Z c 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 sqrt tr(Σ c) 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.
Sources
- Radial Oscillations and Dynamical Instability Analysis for Linear-Quadratic GUP-modified White Dwarfs
- DC3: A learning method for optimization with hard constraints
- End-to-End Constrained Optimization Learning: A Survey
- Learning to Optimize
- Ionic liquid-electrode interface: classification of ions, saturation of layers, and structure-determined potentials
- Distributionally Robust Optimization: A Review
- RegFormer: An Efficient Projection-Aware Transformer Network for Large-Scale Point Cloud Registration
Related papers
- SLIM: Stochastic Learning and Inference in Overidentified Models
- High-dimensional censored MIDAS logistic regression for corporate survival forecasting
- Cross-Fitting-Free Debiased Machine Learning with Multiway Dependence
- Policy design in experiments with unknown interference
- Can large language models assist choice modelling? Insights into prompting strategies and current models' capabilities
- Causal Inference in Possibly Nonlinear Factor Models