Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
88,570 characters · 42 sections · 118 citation commands
Regret Equals Covariance: A Closed-Form Characterization for Stochastic Optimization
\vskip 0.3in
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 ElmachtoubGrigas2022, for pre-deployment parameter tuning, and for real-time monitoring of decision quality.
The standard tool is Sample Average Approximation (SAA) Shapiro2003, KleywegtEtAl2002: draw $B$ cost scenarios, solve the optimization problem for each, and average the resulting regrets. Reliable estimates require $B = 1000$--$10\,000$ scenarios king2012modeling, 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
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 ElmachtoubGrigas2022, we define expected regret as the cost of acting on $\mathbb{E}[c]$ rather than on the true realization $c$:
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 (ref)) is that regret decomposes as
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)$.
\paragraph{When is $R(c) = 0$?} Theorem (ref) 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:
For constrained QPs, smooth convex problems, and general Lipschitz programs, we derive explicit upper bounds on $|R(c)|$ (Theorem (ref)). 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.
\paragraph{Computational advantage.} The covariance in (ref) 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.
\paragraph{Sign of stochastic regret.} Our regret definition (ref) 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
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.
\paragraph{Relationship to OCO/OLO regret.} The online convex optimization (OCO) and online linear optimization (OLO) regret studied in the online learning literature Hazan2016, Shalev-Shwartz2012 is:
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.
\paragraph{Online-to-batch connection.} Despite these differences, the two notions are related through the standard online-to-batch conversion Cesa-Bianchi2004,Shalev-Shwartz2012. Let $(c_1, \ldots, c_T)$ be i.i.d.\ draws from $P_c$, and let $z_t = \pi^{*}(\mathbb{E}[c])$ for all $t$ (the constant policy). Then:
This limit depends on $\mathbb{E}[c]$, not on the full distribution $P_c$, so it does not recover stochastic regret (ref). The gap between the two is precisely the term $\mathbb{E}[c^{\top}\pi^{*}(c)] - \mathbb{E}[c]^{\top}\pi^{*}(\mathbb{E}[c])$, which is the quantity our paper characterizes.
Put differently, OLO regret for the constant policy converges to the suboptimality of the mean-optimal action at the mean cost, whereas stochastic regret measures the cost of ignoring the distribution of $c$ beyond its mean. The covariance decomposition (Theorem (ref)) is precisely a characterization of this second quantity.
\paragraph{Implications for OLO algorithm design.} The covariance formula has a direct implication for OLO: an algorithm that achieves $\mathrm{Regret}^{\mathrm{OLO}}_T / T = o(1)$ against the best fixed action will also achieve small mean-cost suboptimality as $T \to \infty$ by (ref), but it will not generally control the stochastic regret $|\mathrm{Regret}(c)|$ studied here, because this requires the policy to respond to the distribution of $c$, not just its mean. Conversely, a policy designed to minimize stochastic regret (i.e.\ one that exploits the covariance structure of $P_c$) may not be the best fixed action against an adversarial sequence. The two objectives are complementary, not equivalent.
\paragraph{Organization.} Section (ref) reviews related work. Section (ref) sets out assumptions and notation. Section (ref) states and proves the main theorems. Section (ref) presents experiments. Section (ref) applies the framework to portfolio management. Section (ref) concludes. Proofs of subsidiary results appear in the appendix.
The problem of quantifying regret in stochastic optimization spans several research areas: computational methods for uncertainty quantification, predict-then-optimize frameworks, and decision-focused learning. This section examines how the proposed covariance-based characterization advances each area.
The traditional approach to regret estimation uses Sample Average Approximation (SAA) (Shapiro2003, KleywegtEtAl2002, shapiro2009lectures), which estimates regret by solving the optimization problem repeatedly across sampled scenarios:
where $B$ is the number of scenarios. king2012modeling provide finite-sample bounds showing that the SAA error decreases as $\mathcal{O}(B^{-1/2})$, requiring large $B$ (typically 1000-10000) for precision, with computational complexity of $\mathcal{O}(Bn^2d^3)$. Recent work by bayraksan2015separability and lam2022advanced develops improved variance reduction techniques, but these still require solving an optimization problem for each scenario.
Bootstrap methods (PolitisRomano, efron1994introduction) provide an alternative for uncertainty quantification. HongEtAl2021 apply bootstrap to learning-based robust optimization, while GuptaKallus2022 use it for data pooling in stochastic optimization. lam2023distributionally develop bootstrap confidence intervals for stochastic programs with complexity $\mathcal{O}(Bnd^2)$. However, these methods provide distributional approximations rather than exact expected regret.
The control variates (glasserman2004monte, asmussen2007stochastic) use a correlation structure to reduce variance: $\hat{\theta}_{CV} = \hat{\theta} - \beta(Z - E[Z])$ where $Z$ is a control variate with known expectation and $\beta = \text{Cov}(\hat{\theta},Z)/\text{Var}(Z)$. Importance sampling (glynn1989indirect, owen2013monte) changes the sampling distribution to reduce variance. Recent work by picheny2023importance applies importance sampling to robust optimization, while blanchet2024unbiased develop unbiased Monte Carlo methods for stochastic programs. Quasi-Monte Carlo methods (sobol1967distribution, lecuyer2019recent) develop low-discrepancy sequences for numerical integration.
The proposed covariance-based characterization provides exact regret for LP/QP with $\mathcal{O}(nd^2)$ complexity—orders of magnitude faster than simulation—while offering closed-form analytical insights unavailable through numerical methods. Our Theorem (ref) shows that regret equals covariance, immediately suggesting optimal control variates. For any unbiased regret estimator $\hat{R}$, we can construct:
with $\beta = 1$ optimal when residual $R(c) = 0$ (LP/QP case). Our analytical characterization also suggests optimal importance sampling distributions and identifies which dimensions require finest discretization in QMC.
The predict-then-optimize (PtO) paradigm integrates prediction and optimization through learning models that directly optimize decision quality. ElmachtoubGrigas2022 introduced the "Smart Predict, then Optimize" (SPO) framework, proposing a loss function that measures decision quality rather than prediction accuracy, establishing that minimizing prediction error (e.g. MSE) does not necessarily minimize decision regret.
donti2017task pioneered task-based learning for energy systems, embedding optimization problems as differentiable layers in neural networks. Building on this, WilderEtAl2019 developed decision-focused learning for combinatorial optimization, while mandi2020interior extended these ideas to constraint programming. Recent work by dalle2022decision proposed decision-aware learning for contextual stochastic optimization, and kotary2021end developed end-to-end learning methods that backpropagate through optimization layers.
Recent work learns optimization algorithms themselves (chen2022finite, li2016learning). bengio2021machine survey machine learning for combinatorial optimization, while cappart2021combinatorial develop combinatorial optimization in the context of deep learning. AmosKolter2017 introduce OptNet, embedding QP solvers as differentiable layers, and agrawal2019differentiable develop cvxpy layers for general convex optimization, enabling backpropagation through optimization problems with complexity $\mathcal{O}(Tnd^2h)$ for $T$ training iterations and $h$ hidden units. berthet2020learning develop perturbed optimizers for zero-order differentiation.
Sadana2023ASO study contextual stochastic optimization where costs depend on features $x$: $c = g(x,\epsilon)$. ban2019big develop prescriptive analytics for contextual problems, while BERTSIMAS2023634 learn optimal decision trees for prescriptive analytics. Recent work has focused on regret-based loss functions: hu2023sample analyzed the consistency of SPO loss for linear programs, mandi2023decision developed noise-contrastive estimation for decision-focused learning, and balghiti2024optimal characterized optimal prediction for linear programs under various noise structures. shah2023sample studied the sample complexity of learning to optimize, while balghiti2022generalization and balghiti2023finite analyze generalization error and finite-sample regret bounds in data-driven optimization.
PtO frameworks require the evaluation of regret to measure decision quality. The covariance formula proposed in this paper provides:
This complements PtO by providing the analytical foundation for the regret that PtO models seek to minimize. For machine learning methods, our formula enables $\mathcal{O}(nd^2)$ evaluation versus $\mathcal{O}(Bn^2d^3)$ for simulation, provides analytical gradients for gradient-based training, and establishes theoretical benchmarks for achievable performance.
Sensitivity analysis in optimization (fiacco1983introduction, bonnans2000perturbation) studies how optimal solutions change with parameters. The envelope theorem (milgrom2002envelope) characterizes the derivative of the optimal value function. freund1985postoptimal develops sensitivity analysis for linear programming, while rao1979sensitivity extend the analysis to quadratic programs.
shapiro1990sensitivity and shapiro1991asymptotic developed first- and second-order sensitivity analysis for stochastic programs. dupacova1984stability and dupacova2002applications study the stability of stochastic programs under perturbations. Recent work by pichler2024optimal and maggioni2016bounds quantifies the stability of the solution using probability metrics. Infinitesimal perturbation analysis (IPA) (fu2006gradient, lecuyer1990unified, lecuyer2019recent) estimates gradients $\nabla_\theta E[L(\theta)]$ for discrete-event systems with complexity $\mathcal{O}(Bnd)$, but provides gradients rather than expected values and requires simulation.
Robust optimization (bentalrobust2009, bertsimas2011theory) optimizes for worst-case performance: $\min_{z \in Z} \max_{c \in U} c^T z$. bertsimas2004price introduce budgeted uncertainty sets for controlling conservatism, while bertsimas2018data extend to robust data-driven optimization. Although powerful for risk management, robust optimization provides worst-case bounds, not expected regret.
Distributionally Robust Optimization (DRO). DRO (rahimian2019distributionally, kuhn2019wasserstein) hedges against distributional uncertainty:
where $P$ is an ambiguity set. Recent work uses the Wasserstein distance to define $P$ (mohajerin2018data, blanchet2019robust). gao2023distributionally characterize the Wasserstein DRO problem for linear programs, blanchet2019quantifying develop quantitative stability results using optimal transport metrics, and chen2022finite provide finite-sample guarantees. pichler2024optimal connect optimal transport to stochastic dominance.
The Wasserstein-2 distance between the distributions $P$ and $Q$ is:
For Gaussian distributions, this has a closed form that involves covariance matrices (dowson1982frechet, givens1984class). blanchet2023statistical show connections between Wasserstein balls and moment constraints.
artzner1999coherent introduced coherent risk measures including CVaR. rockafellar2000optimization and rockafellar2002conditional develop optimization with CVaR constraints, while shapiro2014risk analyze risk-averse stochastic programming. Markowitz1952 pioneered mean-variance optimization and ruszczynski2006optimization developed general mean-risk models. Recent work by homem2016risk studies risk-averse stochastic programs.
While sensitivity analysis examines local behavior (how solutions change near a point), our solution characterizes global expected behavior (regret over the entire distribution). Prior work shows that $\frac{d\pi^*}{dc}$ exists; we prove $E[\text{Regret}] = \text{Cov}(c, \pi^*(c))$ exactly for LP/QP (see Table (ref) for comparison). Our covariance characterization reveals a fundamental structure complementary to DRO: DRO seeks the worst-case over distributions within the Wasserstein ball, while our work quantifies expected regret for a specific distribution. For Gaussian uncertainty, when $c \sim \mathcal{N}(\mu, \Sigma)$, the Wasserstein-2 distance to $\delta_\mu$ is: $W_2(\mathcal{N}(\mu,\Sigma), \delta_\mu) = \sqrt{\text{tr}(\Sigma)}$. Our regret bound $|R(c)| \leq L\|E[c]\|\sqrt{\text{tr}(\Sigma_c)}$ directly involves this Wasserstein distance, revealing deep connections between regret, covariance, and optimal transport. Regret can be viewed as a bilinear risk measure $\text{Regret}(c) = \text{Cov}(c, \pi^*(c))$ dependent on the joint distribution $(c, \pi^*(c))$, distinguishing it from classical risk measures that depend only on the cost distribution $P_c$.
The optimization problem ((ref)) is central to numerous applications. In portfolio management, Markowitz (1952) introduced mean-variance optimization, demiguel2009optimal studied optimal portfolio policies under estimation error, and recent work by ban2024machine has developed machine learning approaches. In energy systems, donti2017task and donti2021dc3 apply predict-then-optimize to energy forecasting and dispatch, while wilder2021end develops decision-focused learning for renewable energy. In supply chain, bertsimas2006inventory study robust and data-driven inventory optimization, while keskin2023dynamic develop adaptive inventory management. Other applications include food manufacturing (MehrotraEtAl2011), intensive care discharge decisions (ChanEtAl2012), burn patient care (ChanEtAl2013), utility crew management (AngalakudatiEtAl2014), medical screening (DeoEtAl2015), warehouse operations (GallienEtAl2015), online recommendations (BesbesEtAl2016), sales promotion (CohenEtAl2017), and data-driven pricing (FerreiraEtAl2016).
The computational cost of regret estimation has been studied primarily through the lens of Sample Average Approximation (SAA). KleywegtEtAl2002 show that $B = \mathcal{O}(\varepsilon^{-2})$ scenarios are needed to achieve absolute error $\varepsilon$, so that reliable estimates typically require $B = 1{,}000$--$10{,}000$ scenarios king2012modeling. Solving a single LP or QP with $n$ variables and $d$ constraints costs $\mathcal{O}(n^{2}d)$ pivots or $\mathcal{O}(nd^{2})$ interior-point iterations dyer2006computational; forming the full factorization raises this to $\mathcal{O}(n^{2}d^{3})$ in the worst case. Running $B$ independent solves, therefore, costs $\mathcal{O}(Bn^{2}d^{3})$ in total. guigues2012sampling tighten these bounds for multistage problems. Recent variance-reduction techniques bayraksan2015separability,lam2022advanced reduce the constant factor, but all simulation-based methods must solve at least one optimization problem per scenario.
Bootstrap confidence intervals LamZhou2023 achieve complexity $\mathcal{O}(Bnd^{2})$ and provide distributional approximations but not exact expected regret. Infinitesimal perturbation analysis fu2006gradient estimates gradients $\nabla_{\theta}\mathbb{E}[L(\theta)]$ at cost $\mathcal{O}(Bnd)$ but does not compute expected values directly. None of these methods yields a closed-form expression for regret.
The covariance-based characterization of Theorem (ref) gives rise to a regret estimator, the complexity of which depends critically on the information available to the practitioner. We distinguish two scenarios.
\paragraph{Scenario A: historical cost-decision pairs are available.} Suppose a practitioner holds an archive of $n$ pairs $\{(c_{i}, \pi^{*}(c_{i}))\}_{i=1}^{n}$. For example, at a trading desk, the archive may include logged historical cost realizations alongside the decisions made on each date, or a supply-chain operator with recorded demand-and-order histories. In this setting, estimating regret via the covariance formula requires only a single pass through the archive:
at cost $\mathcal{O}(nd^{2})$: one accumulation of $d$-dimensional means and one accumulation of the $d\times d$ outer-product sum. No optimization solve is required. SAA applied to the same archive would require solving $B$ fresh optimization problems at a cost of $\mathcal{O}(Bn^{2}d^{3})$ to estimate regret for a new candidate policy. The speedup is therefore a factor of $\mathcal{O}(Bn/d)$, which for typical values ($B = 1{,}000$, $n = 500$, $d = 20$) exceeds $\mathbf{25{,}000\times}$. Our portfolio experiment (Section (ref)) realizes this speedup on real data: across 119 monthly windows, the covariance estimator tracks realized regret closely while requiring no additional solves beyond the initial portfolio construction.
\paragraph{Scenario B: no historical data; $\pi^{*}(c_{i})$ must be computed from scratch.} If the practitioner has no archive of past decisions, estimating Cov$(c, \pi^{*}(c))$ via (ref) still requires computing $\pi^{*}(c_{i})$ for each sampled $c_{i}$, which costs $\mathcal{O}(n^{2}d^{3})$ in total, comparable to SAA. In this case, the formula offers structural rather than computational value: it provides a closed-form expression whose gradient $\nabla_{\theta}\mathrm{Cov}(c,\pi^{*}(c))$ can be computed analytically (Section (ref)), and it serves as a benchmark against which simulation estimates can be validated.
\paragraph{The unconstrained QP case: the strongest claim.} For unconstrained quadratic programs of the form $\min_{z}\, c^{\top}z + \frac{\lambda}{2}z^{\top}Qz$, the optimal decision is available in closed form:
Substituting into (ref) gives
which is computable from the covariance matrix $\Sigma_{c}$ alone via a single matrix inversion of cost $\mathcal{O}(d^{3})$ (amortized over all samples) and one trace evaluation of cost $\mathcal{O}(d^{2})$. This requires zero optimization solves regardless of whether historical data exist. The Markowitz portfolio problem ($Q = \Sigma_{c}$) is a direct instance; the formula then gives the exact regret analytically from the estimated covariance matrix of returns. This is the most computationally favorable regime, and the one where the $\mathcal{O}(nd^{2})$ versus $\mathcal{O}(Bn^{2}d^{3})$ comparison is most precisely justified.
\paragraph{Summary of complexity claims.} Table (ref) organizes these three cases. The general LP/QP speedup claimed in prior versions of this work applies specifically to Scenario A; for Scenario B the gain is structural, not computational. Section (ref) provides an empirical timing comparison across $B \in \{100, 500, 1{,}000, 5{,}000\}$ and $d \in \{5, 10, 20, 50\}$ that directly demonstrates the claimed scaling.
\paragraph{Prior knowledge requirements.} A natural concern is whether the covariance formula requires additional prior knowledge beyond what SAA uses. It does not. In Scenario A, both methods draw on the same historical archive of $(c_{i}, \pi^{*}(c_{i}))$ pairs; the covariance estimator simply applies a different---and cheaper---statistic to those pairs. In Scenario B, both methods must solve the optimisation problem for each sample; the covariance formula then offers the same information as SAA at comparable cost. For the unconstrained QP, the covariance is a function of $\Sigma_{c}$ alone, which can be estimated from historical cost observations without any decision data. In all cases no distributional assumption beyond finite second moments (Assumption 3.2) is required.
We work throughout with four standing assumptions. Together, they ensure that regret is well-defined, finite, and estimable from data.
\noindentCommentary. Completeness ensures that every sub-event of a null set is measurable, which is needed for the almost-sure Lipschitz argument in Lemma (ref).
\noindentCommentary. Absolute continuity of $P_{c}$ is the distributional condition that allows the LP zero-residual result to hold (Lemma (ref)); it is automatically satisfied by Gaussian, uniform, and all other standard continuous distributions, but it fails for discrete or rounded costs.
\noindentCommentary. Compactness bounds $\|\pi^{*}(c)\|$ uniformly in $c$, which is needed for the concentration bound of Theorem (ref). Full row rank rules out redundant constraints that would create degenerate normal-cone boundaries.
\noindentCommentary. Condition (iii) only requires optimality almost surely, not everywhere; this is what allows the LP case, where the minimizer is non-unique on the measure-zero boundaries between normal cones.
\noindentCommentary. These are standard for the sample mean estimator $\bar{c}$ by the LLN and CLT under Assumption (ref). Assumption (ref) is only invoked in the statistical results of Section (ref) (Theorems (ref)--(ref)).
The three regularity conditions on $\pi^{*}$ (Lipschitz, smooth, strongly convex) are not standing assumptions; they are invoked selectively by individual theorems and are summarized in Table (ref).
Figure (ref) shows the logical dependency structure of the eight results in this section. The results are divided into three layers.
\noindentLayer 1 — Core decomposition (Section (ref)). Theorem (ref) establishes the fundamental identity $\mathrm{Regret}(c) = \mathrm{Cov}(c,\pi^{*}(c)) + R(c)$ and bounds $|R(c)|$ under three regularity levels. All subsequent results depend on this theorem.
\noindentLayer 2 — Structure of the residual (Section (ref)) Theorem (ref) (exact equality conditions) and Lemma (ref) (LP measure-zero argument) together characterize when $R(c) = 0$ holds exactly. Theorem (ref) gives the explicit $\mathcal{O}(\|\Sigma_{c}\|^{2})$ expression for the constrained QP case. These are independent of each other but all build on Theorem (ref).
\noindentLayer 3 — Statistical theory (Section (ref)). Lemma (ref) and Theorems (ref)--(ref) translate the decomposition into estimators with finite-sample guarantees. They require Assumption (ref) in addition to Assumptions (ref)--(ref). Theorem (ref) (uniqueness) stands somewhat apart: it does not depend on sampling but shows that the covariance form is the only possible representation of regret.
\paragraph{Motivation.} Regret measures how much is lost by optimizing for the mean cost $\mathbb{E}[c]$ rather than the realized cost $c$. The central question of this paper is: does this operational quantity have a closed statistical form? Theorem (ref) answers yes: regret decomposes exactly into a covariance plus a residual $R(c)$. Here, the covariance is the standard measure of linear co-movement between costs and decisions. The residual captures the nonlinearity of the decision map $c \mapsto \pi^{*}(c)$.
\paragraph{Proof sketch.} The decomposition follows from a single algebraic step: add and subtract $\mathbb{E}[c]^{\top}\mathbb{E}[\pi^{*}(c)]$ inside the definition of regret and recognize the resulting two terms as the covariance and the residual, respectively. The three residual bounds then apply Jensen's inequality to $\|\mathbb{E}[\pi^{*}(c)] - \pi^{*}(\mathbb{E}[c])\|$ under successively stronger regularity — Lipschitz (via $\mathbb{E}[\|c-\mathbb{E}[c]\|] \leq \sqrt{\mathrm{tr}(\Sigma_c)}$), smooth (via second-order Taylor expansion), and strongly convex (via the sharper Lipschitz constant $L^2/\mu$). Full proof in Appendix (ref).
\paragraph{Implications.} The covariance term is computationally tractable: from $n$ historical cost-decision pairs it costs $\mathcal{O}(nd^{2})$ to estimate, versus $\mathcal{O}(Bn^{2}d^{3})$ for SAA (Section (ref)). The three bounds show that $|R(c)|$ shrinks as $\Sigma_c \to 0$ (low uncertainty) or $\mathbb{E}[c] \to 0$ (zero-mean costs); Theorem (ref) characterizes the cases where $R(c) = 0$ exactly.
\paragraph{Motivation.} The bounds in Theorem (ref) show that $R(c)$ is controlled by $\Sigma_{c}$, but they do not tell us when it vanishes entirely. The next two results answer this question: Theorem (ref) gives the algebraic conditions; Lemma (ref) provides the distributional argument needed to cover linear programs, where the algebraic condition fails pointwise but holds almost surely.
\paragraph{Proof sketch.} For (i): substituting $\pi^{*}(c) = Ac+b$ gives $\mathbb{E}[\pi^{*}(c)] = A\mathbb{E}[c]+b = \pi^{*}(\mathbb{E}[c])$, so $R(c) = 0$ by definition. For (ii) and (iii): these are algebraic restatements of the same condition. Necessity — that $R(c) = 0$ forces $\pi^{*}$ to satisfy conditional linearity — follows by taking directional derivatives of $\mathbb{E}[\pi^{*}(c)]$ with respect to the mean $\mu = \mathbb{E}[c]$ and applying the envelope theorem; if the residual must vanish for all distributions, $\pi^{*}$ must be affine in every direction. For (iv) and (v): see Lemma (ref) and Remark (ref) below. Full proof in Appendix (ref).
\paragraph{Implications.} This theorem is the key to Table (ref): conditions (i) and (v) justify the “Exact” entries for unconstrained QP; condition (iv) justifies the LP entry under the distributional caveat. For all other problem classes, the covariance formula is an approximation, and the bounds of Theorem (ref) apply.
\paragraph{Proof sketch.} Each vertex $v_k$ of $\mathcal{Z}$ is optimal for cost vectors $c$ such that $-c$ lies in its normal cone $\mathcal{N}_{\mathcal{Z}}(v_k)$. The normal cones tile $\mathbb{R}^d$ into a polyhedral fan; their shared boundaries are hyperplanes, which have Lebesgue measure zero. Since $P_c$ is absolutely continuous it assigns zero probability to these boundaries, so $\pi^{*}$ is locally constant — and hence Lipschitz with $L=0$ — almost surely. The Lipschitz bound from Theorem (ref) then gives $|R(c)| \leq 0$. Full proof in Appendix (ref).
\paragraph{Implications.} The measure-zero argument is what bridges the gap between the algebraic affinity condition (which LPs do not satisfy everywhere) and the practical zero-residual claim. It depends on $P_c$ being absolutely continuous; for discrete or rounded cost distributions this assumption fails and $R(c)$ may be nonzero (Remark (ref)).
\paragraph{Motivation for Theorem (ref).} For constrained QPs, $\pi^{*}$ is no longer globally affine (the projection onto the binding constraints introduces nonlinearity), so $R(c) \neq 0$ in general. The next result gives the exact leading-order expression for $R(c)$ in this case, which is needed to quantify approximation quality.
\paragraph{Proof sketch.} When constraints are inactive, the solution is $\pi^*(c) =-(Q+\lambda I)^{-1}c$ (affine), giving $R(c) = 0$. When constraints bind with positive probability, the solution is the projection $P_\mathcal{Z}(-(Q+\lambda I)^{-1}c)$. A second-order Taylor expansion of $\pi^*(c)$ around $\mathbb{E}[c]$ introduces a Hessian correction proportional to $\Sigma_c$; taking the inner product with $\mathbb{E}[c]$ yields the stated expression. For the Markowitz case, explicit computation of the Hessian of the projection with $Q = \Sigma_c$ gives the closed-form leading term. Full proof in Appendix (ref).
\paragraph{Implications.} The $\mathcal{O}(\|\Sigma_c\|^{2})$ scaling confirms that for well-diversified portfolios (small $\|\Sigma_c\|$) the covariance approximation is very accurate; the correction grows quadratically in uncertainty, not linearly. This justifies the "Very good approximation" rating for constrained QP in Table (ref).
The results in this section require Assumption (ref) in addition to Assumptions (ref)--(ref). They establish that the covariance estimator $\widehat{\mathrm{Cov}}(c,\pi^{*}(c))$ is a valid, well-calibrated substitute for $\mathrm{Regret}(c)$ in finite samples.
\paragraph{Motivation for Lemma (ref).} Although Theorem (ref) tells us when $R(c) = 0$ exactly, in practice the practitioner may face a problem class where $R(c) \neq 0$. Lemma (ref) provides a computable estimate of $R(c)$ from data, enabling a corrected regret estimate $\widehat{\mathrm{Cov}} + \hat{R}_n$ for the general case.
\paragraph{Proof sketch.} Expand $\mathbb{E}[\hat{R}_n]$ by conditioning on $\bar{c}$ and using the i.i.d.\ structure. The cross-terms from distinct samples ($i \neq j$) factor by independence; the diagonal terms ($i = j$) contribute $\frac{1}{n}\mathbb{E}[c^{\top}\pi^*(c)]$. A first-order Taylor expansion of $\pi^*(\bar{c})$ around $\mathbb{E}[c]$ introduces a bias of size $\frac{1}{n}\,\mathrm{tr}(\nabla_c\pi^*(\mathbb{E}[c])\Sigma_c) = \mathcal{O}(n^{-1})$, which vanishes as $n \to \infty$. The variance bound follows by applying the delta method to $\pi^*(\bar{c})$ and combining it with the variance of the sample mean $\bar{\pi}$. Full proof in Appendix (ref).
\paragraph{Implications.} The $\mathcal{O}(n^{-1})$ bias is negligible relative to the $\mathcal{O}(n^{-1/2})$ standard deviation for any $n \geq 2$, so $\hat{R}_n$ can be used directly to form corrected confidence intervals. Theorem (ref) uses the same estimator logic to bound regret when the mean is itself estimated from data.
\paragraph{Motivation for Theorem (ref).} In real-world applications, a practitioner uses $\hat{\mathbb{E}}[c]$ in place of the true $\mathbb{E}[c]$. This introduces an additional error on top of the residual $R(c)$. Theorem (ref) quantifies the combined effect.
\paragraph{Proof sketch.} Apply the mean-value theorem to expand $\pi^*(\hat{\mathbb{E}}[c])$ around $\pi^*(\mathbb{E}[c])$; the error term is bounded by the Lipschitz constant of $\pi^*$ times $\|\hat{\mathbb{E}}[c] - \mathbb{E}[c]\| = \mathcal{O}_P(n^{-1/2})$ from Assumption (ref). Adding this to the Theorem (ref) decomposition gives the stated form. Full proof in Appendix (ref).
\paragraph{Implications.} The estimation error from imperfect $\hat{\mathbb{E}}[c]$ is $\mathcal{O}_P(n^{-1/2})$, which is of the same order as the sampling error in $\widehat{\mathrm{Cov}}$ itself (Theorem (ref)). Using $\hat{\mathbb{E}}[c]$ in place of $\mathbb{E}[c]$ therefore does not change the asymptotic order of the regret estimator.
\paragraph{Motivation for Theorem (ref).} One might ask whether some other functional form — not involving covariance — could also represent regret exactly. Theorem (ref) shows the answer is no: the covariance form is unique up to a constant, so Theorem (ref) is not merely one of many possible representations.
\paragraph{Proof sketch.} Suppose $\psi_1$ and $\psi_2$ both represent regret; then $\mathbb{E}[\psi_1 - \psi_2] = 0$ for every distribution $P_c$ in the class. Since this equality must hold for all $P_c$ in a sufficiently rich family, a separating family argument (if $\int f\,d\mu = 0$ for all $\mu$ in a separating family, then $f = 0$ a.s.) forces $\psi_1 = \psi_2$ $\mathbb{P}$-a.s. Among all such representations, the minimum-variance one is exactly the centered inner product $(c-\mathbb{E}[c])^{\top}(\pi^*(c) - \mathbb{E}[\pi^*(c)])$, whose expectation is $\mathrm{Cov}(c,\pi^*(c))$ by definition. The Riesz representation theorem for $L^2(\mathbb{P})$ then establishes uniqueness. Full proof in Appendix (ref).
\paragraph{Implications.} Theorem (ref) closes the characterisation: not only is $\mathrm{Cov}(c,\pi^*(c))$ a valid representation of regret (Theorem (ref)), it is the only one. This underpins the gradient formula $\nabla_\theta\mathrm{Regret} = \nabla_\theta\mathrm{Cov}(c,\pi^*(c))$ cited in Section (ref).
\paragraph{Motivation for Theorems (ref) and (ref).} Theorems (ref)--(ref) establish the population-level result. The final two theorems give finite-sample guarantees for the sample covariance estimator $\widehat{\mathrm{Cov}}(c,\pi^*(c))$ used in practice.
\paragraph{Proof sketch.} Write the centered summands as $h_i = (c_i - \mathbb{E}[c])^{\top} (\pi^*(c_i) - \mathbb{E}[\pi^*(c)])$, bounded by $|h_i| \leq 2B^2(1+L)$. Hoeffding's inequality on the average $\frac{1}{n}\sum_i h_i$ gives the stated exponential bound; Bernstein's inequality yields a tighter version when $\mathrm{Var}(h_1)$ is small relative to the bound. Full proof in Appendix B.3.
\paragraph{Implications.} To achieve absolute error $\varepsilon$ with probability $1-\delta$, a sample size $n \geq \frac{2(B^2+L^2\sigma^2)\log(2/\delta)} {\varepsilon^2}$ suffices — the same $\mathcal{O}(\varepsilon^{-2})$ rate as SAA, but with the enormous constant-factor advantage that no optimization solves are needed in Scenario A (Section (ref)).
\paragraph{Proof sketch.} Decompose $\widehat{\mathrm{Regret}}_n - \mathrm{Regret}$ into $A_n - B_n$, where $A_n$ is a sample average of i.i.d.\ terms (handled by the classical CLT) and $B_n = \bar{c}^{\top}\pi^*(\bar{c}) - \mathbb{E}[c]^{\top}\pi^*(\mathbb{E}[c])$ is a smooth function of $\bar{c}$ (handled by the delta method). The delta method applied to the map $\mu \mapsto \mu^{\top}\pi^*(\mu)$ yields the gradient $g(\mathbb{E}[c])$; this term was missing from the original variance formula. Slutsky's theorem combines the two normal limits. Full proof in Appendix B.4.
\paragraph{Implications.} The CLT enables asymptotically valid confidence intervals for regret:
where $\hat{\sigma}^2_{\mathrm{regret}}$ is the plug-in estimator of $\sigma^2_{\mathrm{regret}}$. These intervals can be used directly for model comparison in predict-then-optimize frameworks without rerunning SAA.
For all experiments, we simulate 5,000 iterations with randomly generated problems. Cost means $\mu_c$ and covariance $\Sigma_c$ (positive definite) are fixed across iterations; individual costs $c_i \mathcal{N}(\mu_c, \Sigma_c)$ vary. We solve using Python cvxpy, compute empirical regret $\hat{E}[c^T {\pi}^*(c)] - \hat{E}[c^T {\pi}^*[\hat{E}[c])]$, and compare it to the theoretical $\text{Cov}(c, \pi^*(c))$.
This section explores the performance of the proposed regret estimation methodology for a simulated set of Linear Programming problems:
To understand the performance of the methodology in the linear programming setting, we first simulate 5,000 Linear Programming problems with $n$ variables and $d$ constraints. For all 5,000 trials, the vectors of the constraint parameters $\mathbf{A}_{d\times n}$ and $\mathbf{b}_{d\times 1}$ are selected at random as follows:
We generate $\mathbf{\mu}_{c,n\times 1}\sim\mathcal{N}(0,I)$ and a randomly-generated positive definite variance-covariance matrix $\mathbf{\Sigma}_{c,n\times n}$. For each of the 5,000 simulation iterations, we generate a distinct cost vector $\mathbf{c}_{n\times 1}\sim\mathcal{N}(\mathbf{\mu}_c,\mathbf{\Sigma}_c)$. Next, for each iteration, we solve the linear program using the Python cvxpy library (diamond2016cvxpy) to obtain a solution $\hat{z}$. We then calculate the empirical regret for each iteration as:
Following Theorem (ref), we next calculate the theoretical regret as the covariance between the costs and the decisions simultaneously across all costs and decisions across 5,000 sets of results:
Figure (ref) shows theoretical regret $\text{Cov}(c,z)$ converges quickly to -700.982 while empirical regret converges slower to -605.882 (13.57% error).
This section replicates the simulation, but for a quadratic optimization similar to the one deployed in portfolio management. We test Theorem (ref) on a standard Quadratic Program:
where $\lambda$ is a risk-aversion coefficient and $\Sigma_c$ is the variance-covariance matrix of costs $c$. We generate $\mathbf{\mu}_{c,n\times 1}\sim\mathcal{N}(0,I)$ and a randomly-generated positive definite variance-covariance matrix $\mathbf{\Sigma}_{c,n\times n}$. For each of the 5,000 simulation iterations, we generate a distinct cost vector $\mathbf{c}_{n\times 1}\sim\mathcal{N}(\mathbf{\mu}_c,\mathbf{\Sigma}_c)$.
With a risk-neutral specification ($\lambda=1$), we obtain the results shown in Figure (ref). The theoretical regret computed as a sample $Cov(c,z)$ converges to its long-run value of -7.729. The empirical regret converges to -5.332, implying a relative estimation error of 31%.
To examine the performance of the proposed regret model in Integer Programming, we consider the classic Knapsack problem that seeks to maximize the value of the integer-denominated items that fit into the knapsack subject to weight constraints $\mathbf{w}_{d\times 1}\sim\mathcal{U}[1,W_{max}]$. For simplicity, we constrain the total allowable weight of the knapsack to $\frac{1}{2}$ of the total weight of the items.
For all simulation iterations, we generate and fix the mean $\mathbf{\mu}_{values,d\times 1}\sim\mathcal{U}[1,10]$ and variance $\mathbf{\Sigma}_{values,d\times d}=2\cdot\mathbb{1}_{d\times d}$ of the values of the items to be included. Note that $\mathbf{\Sigma}_{values,d\times d}$ is 2 times the identity matrix that ensures the independence between the valuations of the items. In each simulation iteration, we simulate the values of the items by drawing random samples from the multivariate normal distribution with mean $\mathbf{\mu}_{values,d\times 1}$ and variance $\mathbf{\Sigma}_{values,d\times d}$. We used Python GLPK MI solver from the cvxpy library to find the optimal solution at each simulation iteration.
We obtain the results shown in Figure (ref). The theoretical small-sample regret computed as a sample $Cov(c,z)$ initially coincides with the empirical regret (-0.430), but diverges to its long-run value of 1.327 as more observations are acquired. This results in a relative estimation error of 132%.
As the studies presented in this section illustrate, the more complex and non-linear the objective function, the higher the error between the covariance-based regret estimate and the realized regret.
The proposed covariance-based methodology for estimating regret provides a quick method for forecasting the future performance of a given model. This section applies the methodology to real-world data. One of the pervasive questions in optimization is how to estimate future portfolio performance to maximize returns and minimize risks. In this section, we consider portfolios formed with financial data and examine their performance.
We used monthly data from the Center for Research in Security Prices (CRSP) for all U.S. listed securities from January 2015 through December 2024. We removed observations with missing monthly returns and eliminated observations with monthly returns less than -100% and greater than 1000%. We also removed observations with negative or zero prices, as well as micro-cap stocks with a market capitalization of less than US \$ 5 million, as measured by the CRSP-Compustat variable MktCap. In addition, we required that all included stocks had a trading history of at least 5 consecutive years and eliminated all stocks that had a history of less than 60 months. We ended up with 4487 stocks and 119 monthly observations.
Next, we created a rolling window estimator, where each month we formed a set of 100 portfolios of 50 stocks each, selected from our universe at random with replacement. For each stock, we generated the optimal portfolio decisions following the framework of Markowitz (1952) and estimated the expected portfolio regret using the covariance-based methodology proposed in this paper. In the next month snapshot, we compared the forecasted regret with the realized regret and reported the results. Figure (ref) shows the aggregate results for covariance-based predicted regret versus realized regret. As the Figure shows, over time, empirical regret approaches theoretical prediction.
The preceding experiments validate the covariance formula as a population-level characterization of regret. This section asks a different question: does the covariance oracle remain useful inside a training loop, where regret must be estimated repeatedly to select model checkpoints? We embed the covariance formula as a drop-in replacement for SAA inside an SPO+ training loop ElmachtoubGrigas2022, and compare wall-clock time and final held-out regret against using SAA for validation.
We use a shortest-path LP on a $4 \times 4$ directed grid graph as the downstream optimization problem, following the benchmark of ElmachtoubGrigas2022. The graph has $d = 24$ edges (variables); edges run rightward and downward only, giving a unique source--sink pair. The LP feasible region is $\mathcal{Z} = \{z \in \mathbb{R}^{d} : Az = b,\; z \geq 0\}$, where $A \in \mathbb{R}^{16 \times 24}$ is the node--edge incidence matrix and $b$ encodes unit flow from source to sink.
We generate $n_{\mathrm{train}} = 200$, $n_{\mathrm{val}} = 100$, and $n_{\mathrm{test}} = 100$ observations. Each sample consists of a context vector $x_{i} \sim \mathcal{N}(0, I_{p})$ with $p = 10$, and a cost vector $c_{i} = \sigma(x_{i} W^{*}) + \varepsilon_{i}$ where $\sigma(\cdot)$ is the element-wise sigmoid, $W^{*} \in \mathbb{R}^{p \times d}$ is a fixed true weight matrix, and $\varepsilon_{i} \sim \mathcal{N}(0, 0.3^{2} I_{d})$. Costs are clipped to $[10^{-2}, \infty)$ to ensure LP feasibility. Hindsight-optimal decisions $\{z^{*}_{i} = \pi^{*}(c_{i})\}$ are pre-solved once and cached; this is the historical archive that makes Scenario A of Section (ref) applicable.
A linear predictor $\hat{c}(x;\, W) = \mathrm{ReLU}(xW)$ with $W \in \mathbb{R}^{p \times d}$ is trained to map context features to predicted costs. We use the SPO+ surrogate loss ElmachtoubGrigas2022:
where $z^{*}(2\hat{c} - c) = \arg\min_{z \in \mathcal{Z}} (2\hat{c} - c)^{\top}z$ is the auxiliary LP solution. Gradients with respect to $\hat{c}$ are computed via the subgradient $2z^{*}(2\hat{c} - c)$ (treated as a constant). Training uses Adam with a learning rate of $5 \times 10^{-3}$, batch size 16, for 20 epochs.
At every other epoch, we evaluate two validation oracles on the held-out validation set $\{(c_{i}, z^{*}_{i})\}_{i=1}^{n_{\mathrm{val}}}$ and use the resulting regret estimate to select the best checkpoint.
We run three training configurations: covariance oracle; SAA oracle with $B = 50$; SAA oracle with $B = 200$.
Table (ref) reports wall-clock time per single validation call across $B \in \{10, 25, 50, 100, 200, 500\}$, averaged over five independent repetitions. The covariance oracle requires $0.063$\,ms per call, independent of $B$, because it performs only vector arithmetic on the cached decisions. The SAA oracle requires $4.4$--$6.1$\,ms across the $B$ range, dominated by the single LP solve at $\bar{c}_{\mathrm{val}}$; the marginal cost of additional scenarios is small relative to this fixed overhead. The covariance oracle is therefore 71--97$\times$ faster per validation call across all tested $B$ values. Extrapolating to $B = 1{,}000$ (a typical SAA requirement for accurate estimation), a single validation call would cost $\approx\!10$\,ms for SAA versus $0.063$\,ms for the covariance oracle: a $\mathbf{159\times}$ speedup.
\paragraph{Validation overhead during training.} Summing latency across all 10 validation calls made during the 20-epoch training run, the covariance oracle accumulates $0.001$\,s of validation overhead versus $0.048$\,s (SAA, $B=50$) and $0.053$\,s (SAA, $B=200$): a 42--46$\times$ reduction in time spent on validation. Total training wall-clock times are comparable across all three configurations ($\approx\!18$\,s; Table (ref)) because the SPO+ auxiliary LP solves inside the training loop (one per sample per batch step) dominate runtime regardless of the validation oracle. The covariance advantage is therefore most pronounced in settings where validation is called more frequently (e.g.\ early stopping with patience), or where $B$ is large enough that each SAA call adds materially to wall-clock time.
Test $|\mathrm{Regret}|$ is identical ($1.2384$) across all three configurations (Table (ref)). This confirms the central claim of the integration experiment: the covariance oracle selects checkpoints of equal quality to SAA while accumulating 42--46$\times$ less validation overhead. The result is consistent with the theoretical guarantee of Theorem (ref): since the covariance estimator is a consistent estimator of true regret (Theorem (ref)), it provides sufficient signal to distinguish good from poor checkpoints even though it is computed without any LP solve.
The covariance advantage in validation overhead grows with the frequency of validation, the value of $B$, and the cost of each LP solve. In large-scale settings (e.g., portfolio optimization with thousands of assets ($d \gg 24$), or supply-chain problems where each LP solve requires minutes), the SAA validation overhead can dominate training time entirely. The covariance oracle decouples validation cost from problem size, making frequent validation tractable at any scale.
Deployment requires a historical archive of $(c_{i}, \pi^{*}(c_{i}))$ pairs (Scenario A of Section (ref)). This is the same data that SAA uses; no additional data collection is needed. When no archive exists (Scenario B), the covariance formula still provides a closed-form expression and an analytic gradient, but the raw computational advantage over SAA does not apply.
This paper presents a closed-form framework for regret estimation, enabling pre-deployment parameter tuning while reducing computational requirements from $\mathcal{O}(Bn^2d^3)$ to $\mathcal{O}(nd^2)$.
Our work advances the literature in three fundamental ways:
Table (ref) summarizes how the proposed approach complements the existing work.
Although covariance appears throughout the optimization literature, no prior work establishes it as an exact characterization of regret. Several factors explain why: