Regret Equals Covariance: A Closed-Form Characterization for Stochastic Optimization
Irene Aldridge · 2026
Read Regret Equals Covariance: A Closed-Form Characterization for Stochastic Optimization by Irene Aldridge (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-14019.txt.
Introduction
Aldridge gives a closed-form account of regret in stochastic optimization. The usual route re-solves the problem across many simulated scenarios, at a cost that scales with scenario count and solve cost. Instead, regret can be read from the joint moments of the cost vector and the optimal decision. Regret splits into minus the covariance of cost and optimal decision, less a residual term. That residual vanishes when the optimal decision is affine in cost, which covers unconstrained and equality-constrained quadratic programs and many linear programs.
Catalog record
| CREATOR | Irene Aldridge |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 89268 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.14019
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Regret Equals Covariance: A Closed-Form Characterization for Stochastic Optimization Irene Aldridge 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 𝒪 ( B n 2 d 3 ) \mathcal{O}(Bn^{2}d^{3}) in the number of scenarios B B , variables n n , and constraints d d . This paper proves that expected regret in any stochastic optimization problem admits the exact decomposition Regret ( c ) = Cov ( c , π ∗ ( c ) ) + R ( c ) , \mathrm{Regret}(c)=\mathrm{Cov}(c,\,\pi^{*}(c))+R(c), where c c is the vector of uncertain parameters, π ∗ ( c ) \pi^{*}(c) is the optimal decision, and R ( c ) 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 R(c)=0 exactly, so that Regret ( c ) = Cov ( c , π ∗ ( c ) ) \mathrm{Regret}(c)=\mathrm{Cov}(c,\pi^{*}(c)) holds without approximation. When historical cost-decision pairs { ( c i , π ∗ ( c i ) ) } \{(c_{i},\pi^{*}(c_{i}))\} are available, the covariance can be estimated in 𝒪 ( n d 2 ) \mathcal{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. 1 Introduction A central goal in Operations Research and machine learning is to make optimal decisions efficiently under uncertainty. A recurring sub-problem is regret estimation : given a policy that acts on an estimate of unknown costs rather than the costs themselves, how much does that estimation error cost in objective value? Answering this question accurately is essential for model selection in predict-then-optimize (PtO) frameworks ( 43 ) , for pre-deployment parameter tuning, and for real-time monitoring of decision quality. The standard tool is Sample Average Approximation (SAA) ( 90 ; 62 ) : draw B cost scenarios, solve the optimization problem for each, and average the resulting regrets. Reliable estimates require B=1000 – 10\,000 scenarios ( 61 ) , and each scenario requires solving the optimization problem anew, resulting in a total complexity of \mathcal{O}(Bn^{2}d^{3}) for an LP or QP with n variables and d constraints. This is prohibitive when regret must be evaluated repeatedly (as in online learning or model-comparison workflows) or at a large scale. In this paper, we study the stochastic optimization problem \pi^{*}(c)\;\in\;\arg\min_{z\in\mathcal{Z}}\;\mathbb{E}[c]^{\top}z, (1) where c\in\mathcal{C}\subseteq\mathbb{R}^{d} is a random cost vector and \mathcal{Z}\subseteq\mathbb{R}^{d} is a known feasible region (possibly non-convex or combinatorial). Following 43 , we define expected regret as the cost of acting on \mathbb{E}[c] rather than on the true realization c : \mathrm{Regret}(c)\;\equiv\;\mathbb{E}\!\left[c^{\top}\pi^{*}(c)\right]-\mathbb{E}\!\left[c^{\top}\pi^{*}(\mathbb{E}[c])\right]\;\leq\;0, (2) where the inequality holds because \pi^{*}(c) minimizes c^{\top}z by definition. The quantity |\mathrm{Regret}(c)| measures the magnitude of the shortfall from perfect hindsight. Our main result (Theorem 3.6 ) is that regret decomposes as \mathrm{Regret}(c)=\underbrace{\mathrm{Cov}(c,\,\pi^{*}(c))}_{\text{covariance term}}\;+\;\underbrace{R(c)}_{\text{residual}}, (3) where \mathrm{Cov}(c,\pi^{*}(c))=\mathbb{E}[c^{\top}\pi^{*}(c)]-\mathbb{E}[c]^{\top}\mathbb{E}[\pi^{*}(c)] is the (scalar-valued) statistical covariance between costs and decisions, and R(c)=\mathbb{E}[c]^{\top}(\mathbb{E}[\pi^{*}(c)]-\pi^{*}(\mathbb{E}[c])) is a residual that captures Jensen’s inequality applied to the (generally nonlinear) map c\mapsto\pi^{*}(c) . When is R(c)=0 ? Theorem 3.7 characterizes the exact-equality cases. The residual vanishes when \pi^{*} is affine in c . This gives \mathrm{Regret}(c)=\mathrm{Cov}(c,\pi^{*}(c)) exactly. This holds for: • Linear programs , when c is drawn from a continuous distribution (so the measure-zero set of discontinuities of \pi^{*} does not affect the expectation); • Unconstrained quadratic programs , for which \pi^{*}(c)=-(Q+\lambda I)^{-1}c is globally affine. For constrained QPs, smooth convex problems, and general Lipschitz programs, we derive explicit upper bounds on |R(c)| (Theorem 3.6 ). The residual can be large for integer programs (up to 132\% relative error in our experiments), so we recommend using the covariance formula with caution for combinatorial problems. Computational advantage. The covariance in ( 3 ) is a standard second-moment quantity. When a practitioner has access to a historical archive of n cost-decision pairs \{(c_{i},\pi^{*}(c_{i}))\}_{i=1}^{n} , the sample covariance is computable in \mathcal{O}(nd^{2}) time: one pass through the data to accumulate means and the outer-product sum. This compares favorably with \mathcal{O}(Bn^{2}d^{3}) for SAA, which requires solving B fresh optimization problems. For unconstrained QPs, the closed form \pi^{*}(c)=-(Q+\lambda I)^{-1}c means the covariance is computable analytically from \Sigma_{c} alone, with no optimization solves. Without historical data or an analytic \pi^{*} , the complexity advantage does not apply; the formula then provides a closed-form structural insight rather than a computational shortcut. Sign convention and relationship to OCO/OLO regret Sign of stochastic regret. Our regret definition ( 2 ) satisfies \mathrm{Regret}(c)\leq 0 always. This is a direct consequence of optimality: since \pi^{*}(c) minimises c^{\top}z over \mathcal{Z} for every realisation c , while \pi^{*}(\mathbb{E}[c]) only minimises the objective at the mean, we have c^{\top}\pi^{*}(c)\;\leq\;c^{\top}\pi^{*}(\mathbb{E}[c])\quad\mathbb{P}\text{-a.s.}, (4) and taking expectations preserves the inequality. Thus \mathrm{Regret}(c)\leq 0 , with equality if and only if the mean-optimal decision is also optimal for every realisation \mathbb{P} -a.s. (i.e. there is no informational value in knowing c exactly). The quantity of practical interest is |\mathrm{Regret}(c)| , the magnitude of the shortfall: how much objective value is lost by acting on \mathbb{E}[c] rather than c . Throughout the paper we report and bound this magnitude. The negative sign reflects the information-theoretic fact that perfect hindsight can only help, never hurt. Remark 1.1 (Alternative sign conventions in the literature) . Some authors define stochastic regret as \mathbb{E}[c^{\top}\pi^{*}(\mathbb{E}[c])]-\mathbb{E}[c^{\top}\pi^{*}(c)]\geq 0 , i.e. the negation of our definition. We follow 43 , whose SPO loss is defined as we state in ( 2 ), so that the regret of the ideal clairvoyant policy is zero and any sub-optimal policy has strictly negative regret (greater cost). The covariance decomposition \mathrm{Regret}(c)=\mathrm{Cov}(c,\pi^{*}(c))+R(c) holds under either sign convention; under the negated convention, both sides change sign, leaving all structural results intact. Relationship to OCO/OLO regret. The online convex optimization (OCO) and online linear optimization (OLO) regret studied in the online learning literature ( 56 ; 89 , see e.g.) is: \mathrm{Regret}^{\mathrm{OLO}}_{T}(z^{*})\;=\;\sum_{t=1}^{T}c_{t}^{\top}z_{t}\;-\;\sum_{t=1}^{T}c_{t}^{\top}z^{*}, (5) where z_{1},\ldots,z_{T} is the sequence of decisions made before observing the corresponding costs c_{1},\ldots,c_{T} , and z^{*}=\arg\min_{z\in\mathcal{Z}}\sum_{t=1}^{T}c_{t}^{\top}z is the best fixed decision in hindsight. This is a cumulative quantity that compares the algorithm’s running total to that of the best static comparator. The stochastic regret studied in this paper is fundamentally different in three respects. 1. Static vs. dynamic comparator. OLO regret ( 5 ) compares against the best fixed action in hindsight. Stochastic regret ( 2 ) compares against the best cost-dependent action \pi^{*}(c) , which is allowed to vary with the realization. The stochastic benchmark is therefore stronger (harder to match) than the OLO benchmark. 2. Cumulative vs. expected loss. OLO regret accumulates over T rounds and is a random variable that depends on the full trajectory (c_{1},\ldots,c_{T}) . Stochastic regret ( 2 ) is an expectation over a single-round distribution P_{c} ; it is a