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

arXiv:2605.14019v1 Announce Type: cross Abstract: Regret is the cost of uncertainty in algorithmic decision-making. Quantifying regret typically requires computationally expensive simulation via Sample Average Approximation (SAA), with complexity O(Bn^{2}d^{3}) in the number of scenarios B, variables n, and constraints d. % This paper proves that expected regret in any stochastic optimization problem admits the exact decomposition % egin{equation*} Regret(c) = Cov(c,,pi^{}(c)) + R(c), end{equation} % where c is the vector of uncertain parameters, pi^{}(c) is the optimal decision, and R(c) is a residual whose magnitude we bound explicitly under Lipschitz, smooth, and strongly convex conditions. % For linear programs and unconstrained quadratic programs, including the classical Markowitz portfolio problem, we prove R(c)=0 exactly, so that Regret(c) = Cov(c,pi^{}(c)) holds without approximation. % When historical cost-decision pairs {(c_i, pi^*(c_i))} are available, the covariance can be estimated in O(nd^{2}) time, which is orders of magnitude faster than SAA. The estimation is performed by a single pass through the data. % We derive concentration bounds, a central limit theorem, and an asymptotically unbiased residual estimator, and we validate all results on synthetic LP, QP, and integer programming instances and on a rolling-window portfolio experiment using ten years of CRSP equity data.

Source: arXiv cs.LG | 2026-05-15