Regret Equals Covariance: A Closed-Form Characterization for Stochastic Optimization
A distribution-free bound is given that depends only on the radius of the feasible region and the cost covariance of regret that holds for unconstrained and equality-constrained quadratic programs and many, but not all, linear programs.