The exact contents of citations.db main_text.text for this paper — one flattened LaTeX string, title through conclusion, appendix excluded, unmodified except for removing email addresses. This is what our citation measures are computed over.
88,561 characters
Regret Equals Covariance: A Closed-Form Characterization for Stochastic Optimization
\title{Regret Equals Covariance: A Closed-Form Characterization for Stochastic Optimization}
\author{Irene Aldridge\footnote{[email removed]}}
\vskip 0.3in
\maketitle
\begin{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 $\mathcal{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
\begin{equation*}
\mathrm{Regret}(c)
= \mathrm{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 $\mathrm{Regret}(c) = \mathrm{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 $\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.
\end{abstract}
\section{Introduction}
\label{sec:intro}
A central goal in Operations Research and machine learning is to make optimal decisions efficiently under uncertainty. A recurring sub-problem is \emph{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 \citep{ElmachtoubGrigas2022}, for pre-deployment parameter tuning, and for real-time monitoring of
decision quality.
The standard tool is Sample Average Approximation (SAA)
\citep{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 \citep{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
\begin{equation}
\pi^{*}(c) \;\in\; \arg\min_{z \in \mathcal{Z}}\;
\mathbb{E}[c]^{\top} z,
\label{eq:opt}
\end{equation}
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 \citet{ElmachtoubGrigas2022}, we define expected regret as the cost of acting on $\mathbb{E}[c]$ rather than on the true realization~$c$:
\begin{equation}
\mathrm{Regret}(c)
\;\equiv\;
\mathbb{E}\!\left[c^{\top}\pi^{*}(c)\right]
- \mathbb{E}\!\left[c^{\top}\pi^{*}(\mathbb{E}[c])\right]
\;\leq\; 0,
\label{eq:regret-def}
\end{equation}
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{thm:regret-cov}) is that regret
decomposes as
\begin{equation}
\mathrm{Regret}(c)
= \underbrace{\mathrm{Cov}(c,\,\pi^{*}(c))}_{\text{covariance term}}
\;+\;
\underbrace{R(c)}_{\text{residual}},
\label{eq:decomp}
\end{equation}
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{thm:exact-equality} 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:
\begin{itemize}
\item \textbf{Linear programs}, when $c$ is drawn from a continuous distribution (so the measure-zero set of discontinuities of $\pi^{*}$ does not affect the expectation);
\item \textbf{Unconstrained quadratic programs}, for which
$\pi^{*}(c) = -(Q + \lambda I)^{-1}c$ is globally affine.
\end{itemize}
For constrained QPs, smooth convex problems, and general Lipschitz programs, we derive explicit upper bounds on $|R(c)|$ (Theorem~\ref{thm:regret-cov}).
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 \eqref{eq:decomp} 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.
\subsection*{Sign convention and relationship to OCO/OLO regret}
\label{sec:regret-convention}
\paragraph{Sign of stochastic regret.}
Our regret definition \eqref{eq:regret-def} 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
\begin{equation}
c^{\top}\pi^{*}(c) \;\leq\; c^{\top}\pi^{*}(\mathbb{E}[c])
\quad \mathbb{P}\text{-a.s.},
\label{eq:pointwise-ineq}
\end{equation}
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
\emph{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.
\begin{remark}[Alternative sign conventions in the literature]
\label{rem:sign-conventions}
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 \citet{ElmachtoubGrigas2022}, whose SPO loss is defined
as we state in \eqref{eq:regret-def}, 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.
\end{remark}
\paragraph{Relationship to OCO/OLO regret.}
The \emph{online convex optimization} (OCO) and \emph{online linear optimization} (OLO) regret studied in the online learning literature \citep[see e.g.][]{Hazan2016, Shalev-Shwartz2012} is:
\begin{equation}
\mathrm{Regret}^{\mathrm{OLO}}_{T}(z^{*})
\;=\;
\sum_{t=1}^{T} c_{t}^{\top} z_{t}
\;-\;
\sum_{t=1}^{T} c_{t}^{\top} z^{*},
\label{eq:olo-regret}
\end{equation}
where $z_1, \ldots, z_T$ is the sequence of decisions made
\emph{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 \emph{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.
\begin{enumerate}[noitemsep]
\item \textbf{Static vs.\ dynamic comparator.}
OLO regret \eqref{eq:olo-regret} compares against the best \emph{fixed} action in hindsight.
Stochastic regret \eqref{eq:regret-def} compares against the best \emph{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.
\item \textbf{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 \eqref{eq:regret-def} is an \emph{expectation} over a single-round distribution $P_c$; it is a scalar that characterizes the steady-state cost of a fixed policy $\pi^{*}(\mathbb{E}[c])$.
\item \textbf{Feasible region.}
OLO algorithms typically operate over convex $\mathcal{Z}$ and use gradient or projection steps.
Our framework allows non-convex and combinatorial
$\mathcal{Z}$ (e.g.\ integer programs), where OLO algorithms generally do not apply.
\end{enumerate}
\paragraph{Online-to-batch connection.}
Despite these differences, the two notions are related through the standard \emph{online-to-batch conversion}
\citep{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:
\begin{align}
\frac{1}{T}\,\mathrm{Regret}^{\mathrm{OLO}}_{T}(z^{*})
&= \frac{1}{T}\sum_{t=1}^{T} c_t^{\top}\pi^{*}(\mathbb{E}[c])
- \frac{1}{T}\sum_{t=1}^{T} c_t^{\top}z^{*}
\notag\\
&\xrightarrow{a.s.}
\mathbb{E}[c]^{\top}\pi^{*}(\mathbb{E}[c])
- \mathbb{E}[c]^{\top}z^{*}
\quad\text{(SLLN as } T\to\infty\text{)}.
\label{eq:otb}
\end{align}
This limit depends on $\mathbb{E}[c]$, not on the full distribution $P_c$, so it does not recover stochastic regret
\eqref{eq:regret-def}. 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 \emph{suboptimality of the mean-optimal action at the mean cost}, whereas stochastic regret measures the \emph{cost of ignoring the distribution of $c$ beyond its mean}. The covariance decomposition (Theorem~\ref{thm:regret-cov}) 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 \emph{mean-cost suboptimality} as $T \to \infty$ by \eqref{eq:otb}, but it will not generally control the stochastic regret $|\mathrm{Regret}(c)|$ studied here, because this requires the policy to respond to the \emph{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.
\begin{remark}[Adversarial vs.\ stochastic OCO]
\label{rem:adversarial}
In the \emph{stochastic OCO} setting \citep{Hazan2016}, where
costs are i.i.d. from a fixed $P_c$, the average per-round OLO regret converges to zero at a rate $\mathcal{O}(T^{-1/2})$ for standard algorithms (e.g., online gradient descent). In this setting, the optimal fixed action $z^{*}$ converges to $\pi^{*}(\mathbb{E}[c])$ as $T \to \infty$, so the \emph{residual gap} between the OLO benchmark and the stochastic regret benchmark is exactly $|\mathrm{Regret}(c)|$. Our paper quantifies and characterizes this residual gap via the covariance decomposition. Improving an OLO algorithm's per-round regret beyond the standard rate therefore requires exploiting higher-order structure of $P_c$ beyond $\mathbb{E}[c]$ — precisely the covariance structure our formula identifies.
\end{remark}
\subsection*{Contributions}
\begin{enumerate}
\item \textbf{Regret--covariance decomposition} (Theorem~\ref{thm:regret-cov}).
We prove $\mathrm{Regret}(c) = \mathrm{Cov}(c, \pi^{*}(c)) + R(c)$ for any stochastic optimization problem satisfying mild regularity conditions, with explicit Lipschitz, smooth, and strongly convex bounds on $|R(c)|$.
\item \textbf{Exact equality conditions} (Theorem~\ref{thm:exact-equality}).
We characterize precisely when $R(c) = 0$, establishing
$\mathrm{Regret}(c) = \mathrm{Cov}(c, \pi^{*}(c))$ as an exact identity for LP and unconstrained QP.
\item \textbf{Statistical theory} (Theorems~\ref{thm:imperfect-estimates}--\ref{thm:clt}).
We derive concentration inequalities, a central limit theorem with the correct delta-method asymptotic variance, and an asymptotically unbiased residual estimator $\hat{R}_n$ with $\mathcal{O}(n^{-1})$ finite-sample bias.
\item \textbf{Computational complexity} (Section~\ref{sec:complexity-contribution}).
When historical cost-decision pairs are available, the covariance estimator runs in $\mathcal{O}(nd^{2})$ versus $\mathcal{O}(Bn^{2}d^{3})$ for SAA, an exponential saving in the scenario count $B$.
\item \textbf{Empirical validation} (Section~\ref{sec:experiments}).
We confirm the theory on synthetic LP, QP, and knapsack instances and on a decade of CRSP equity data, reporting zero relative error for LP/unconstrained QP and characterizing the approximation quality for harder problem classes.
\end{enumerate}
\paragraph{Organization.}
Section~\ref{sec:related} reviews related work.
Section~\ref{sec:model} sets out assumptions and notation.
Section~\ref{sec:core} states and proves the main theorems.
Section~\ref{sec:experiments} presents experiments.
Section~\ref{subsec:portfolio} applies the framework to portfolio management.
Section~\ref{sec:conclusion} concludes.
Proofs of subsidiary results appear in the appendix.
\section{Related Literature}\label{sec:related}
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.
\subsection{Computational Methods for Regret Estimation}
\subsubsection{Classical Simulation Approaches}
The traditional approach to regret estimation uses Sample Average Approximation (SAA) (\cite{Shapiro2003}, \cite{KleywegtEtAl2002}, \cite{shapiro2009lectures}), which estimates regret by solving the optimization problem repeatedly across sampled scenarios:
\begin{equation}
\text{Regret}_{\text{SAA}} = \frac{1}{B}\sum_{i=1}^{B} c_i^T \pi^*(c_i) - \frac{1}{B}\sum_{i=1}^{B} c_i^T \pi^*(\bar{c})
\end{equation}
where $B$ is the number of scenarios. \cite{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 \cite{bayraksan2015separability} and \cite{lam2022advanced} develops improved variance reduction techniques, but these still require solving an optimization problem for each scenario.
Bootstrap methods (\cite{PolitisRomano}, \cite{efron1994introduction}) provide an alternative for uncertainty quantification. \cite{HongEtAl2021} apply bootstrap to learning-based robust optimization, while \cite{GuptaKallus2022} use it for data pooling in stochastic optimization. \cite{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.
\subsubsection{Variance Reduction Techniques}
The control variates (\cite{glasserman2004monte}, \cite{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 (\cite{glynn1989indirect}, \cite{owen2013monte}) changes the sampling distribution to reduce variance. Recent work by \cite{picheny2023importance} applies importance sampling to robust optimization, while \cite{blanchet2024unbiased} develop unbiased Monte Carlo methods for stochastic programs. Quasi-Monte Carlo methods (\cite{sobol1967distribution}, \cite{lecuyer2019recent}) develop low-discrepancy sequences for numerical integration.
\subsubsection{Our Contribution}
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{thm:regret-cov} shows that regret equals covariance, immediately suggesting optimal control variates. For any unbiased regret estimator $\hat{R}$, we can construct:
\begin{equation}
\hat{R}_{CV} = \hat{R} - \beta(\widehat{\text{Cov}}(c, \pi^*(c)) - \text{Cov}(c, \pi^*(c)))
\end{equation}
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.
\subsection{Predict-Then-Optimize and Decision-Focused Learning}
\subsubsection{The PtO Paradigm}
The predict-then-optimize (PtO) paradigm integrates prediction and optimization through learning models that directly optimize decision quality. \cite{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.
\cite{donti2017task} pioneered task-based learning for energy systems, embedding optimization problems as differentiable layers in neural networks. Building on this, \cite{WilderEtAl2019} developed decision-focused learning for combinatorial optimization, while \cite{mandi2020interior} extended these ideas to constraint programming. Recent work by \cite{dalle2022decision} proposed decision-aware learning for contextual stochastic optimization, and \cite{kotary2021end} developed end-to-end learning methods that backpropagate through optimization layers.
\subsubsection{Machine Learning Integration}
Recent work learns optimization algorithms themselves (\cite{chen2022finite}, \cite{li2016learning}). \cite{bengio2021machine} survey machine learning for combinatorial optimization, while \cite{cappart2021combinatorial} develop combinatorial optimization in the context of deep learning. \cite{AmosKolter2017} introduce OptNet, embedding QP solvers as differentiable layers, and \cite{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. \cite{berthet2020learning} develop perturbed optimizers for zero-order differentiation.
\subsubsection{Contextual and Data-Driven Approaches}
\cite{Sadana2023ASO} study contextual stochastic optimization where costs depend on features $x$: $c = g(x,\epsilon)$. \cite{ban2019big} develop prescriptive analytics for contextual problems, while \cite{BERTSIMAS2023634} learn optimal decision trees for prescriptive analytics. Recent work has focused on regret-based loss functions: \cite{hu2023sample} analyzed the consistency of SPO loss for linear programs, \cite{mandi2023decision} developed noise-contrastive estimation for decision-focused learning, and \cite{balghiti2024optimal} characterized optimal prediction for linear programs under various noise structures. \cite{shah2023sample} studied the sample complexity of learning to optimize, while \cite{balghiti2022generalization} and \cite{balghiti2023finite} analyze generalization error and finite-sample regret bounds in data-driven optimization.
\subsubsection{Our Contribution} PtO frameworks require the evaluation of regret to measure decision quality. The covariance formula proposed in this paper provides:
\begin{enumerate}
\item instant regret evaluation for comparing predictive models without retraining,
\item theoretical benchmark showing minimum achievable regret given covariance structure,
\item analytical gradient $\nabla_\theta\text{Regret} = \nabla_\theta\text{Cov}(c, \pi^*(c))$ for optimization.
\end{enumerate}
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.
\subsection{Sensitivity Analysis and Robust Optimization}
\subsubsection{Sensitivity and Perturbation Theory}
Sensitivity analysis in optimization (\cite{fiacco1983introduction}, \cite{bonnans2000perturbation}) studies how optimal solutions change with parameters. The envelope theorem (\cite{milgrom2002envelope}) characterizes the derivative of the optimal value function. \cite{freund1985postoptimal} develops sensitivity analysis for linear programming, while \cite{rao1979sensitivity} extend the analysis to quadratic programs.
\cite{shapiro1990sensitivity} and \cite{shapiro1991asymptotic} developed first- and second-order sensitivity analysis for stochastic programs. \cite{dupacova1984stability} and \cite{dupacova2002applications} study the stability of stochastic programs under perturbations. Recent work by \cite{pichler2024optimal} and \cite{maggioni2016bounds} quantifies the stability of the solution using probability metrics. Infinitesimal perturbation analysis (IPA) (\cite{fu2006gradient}, \cite{lecuyer1990unified}, \cite{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.
\subsubsection{Robust Optimization}
Robust optimization (\cite{bentalrobust2009}, \cite{bertsimas2011theory}) optimizes for worst-case performance: $\min_{z \in Z} \max_{c \in U} c^T z$. \cite{bertsimas2004price} introduce budgeted uncertainty sets for controlling conservatism, while \cite{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 (\cite{rahimian2019distributionally}, \cite{kuhn2019wasserstein}) hedges against distributional uncertainty:
\begin{equation}
\min_{z \in Z} \sup_{P \in \mathcal{P}} E_P[c^T z]
\end{equation}
where $P$ is an ambiguity set. Recent work uses the Wasserstein distance to define $P$ (\cite{mohajerin2018data}, \cite{blanchet2019robust}). \cite{gao2023distributionally} characterize the Wasserstein DRO problem for linear programs, \cite{blanchet2019quantifying} develop quantitative stability results using optimal transport metrics, and \cite{chen2022finite} provide finite-sample guarantees. \cite{pichler2024optimal} connect optimal transport to stochastic dominance.
The Wasserstein-2 distance between the distributions $P$ and $Q$ is:
\begin{equation}
W_2(P,Q) = \inf_{\gamma \in \Pi(P,Q)} \sqrt{E_{(X,Y) \sim \gamma}[\|X-Y\|^2]}
\end{equation}
For Gaussian distributions, this has a closed form that involves covariance matrices (\cite{dowson1982frechet}, \cite{givens1984class}). \cite{blanchet2023statistical} show connections between Wasserstein balls and moment constraints.
\subsubsection{Risk Measures}
\cite{artzner1999coherent} introduced coherent risk measures including CVaR. \cite{rockafellar2000optimization} and \cite{rockafellar2002conditional} develop optimization with CVaR constraints, while \cite{shapiro2014risk} analyze risk-averse stochastic programming. \cite{Markowitz1952} pioneered mean-variance optimization and \cite{ruszczynski2006optimization} developed general mean-risk models. Recent work by \cite{homem2016risk} studies risk-averse stochastic programs.
\subsubsection{Our Contribution}
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{tab:comparison-sensitivity} 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$.
\subsection{Domain Applications and Computational Complexity}
\subsubsection{Application Domains}
The optimization problem (\ref{eq:opt}) is central to numerous applications. In portfolio management, Markowitz (1952) introduced mean-variance optimization, \cite{demiguel2009optimal} studied optimal portfolio policies under estimation error, and recent work by \cite{ban2024machine} has developed machine learning approaches. In energy systems, \cite{donti2017task} and \cite{donti2021dc3} apply predict-then-optimize to energy forecasting and dispatch, while \cite{wilder2021end} develops decision-focused learning for renewable energy. In supply chain, \cite{bertsimas2006inventory} study robust and data-driven inventory optimization, while \cite{keskin2023dynamic} develop adaptive inventory management. Other applications include food manufacturing (\cite{MehrotraEtAl2011}), intensive care discharge decisions (\cite{ChanEtAl2012}), burn patient care (\cite{ChanEtAl2013}), utility crew management (\cite{AngalakudatiEtAl2014}), medical screening (\cite{DeoEtAl2015}), warehouse operations (\cite{GallienEtAl2015}), online recommendations (\cite{BesbesEtAl2016}), sales promotion (\cite{CohenEtAl2017}), and data-driven pricing (\cite{FerreiraEtAl2016}).
\subsubsection{Computational Complexity of Regret Estimation} \label{sec:complexity-background}
The computational cost of regret estimation has been studied primarily through the lens of Sample Average Approximation (SAA). \citet{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 \citep{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 \citep{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.
\citet{guigues2012sampling} tighten these bounds for multistage problems. Recent variance-reduction techniques \citep{bayraksan2015separability,lam2022advanced} reduce the constant factor, but all simulation-based methods must solve at least one optimization problem per scenario.
Bootstrap confidence intervals \citep{LamZhou2023} achieve complexity $\mathcal{O}(Bnd^{2})$ and provide distributional approximations but not exact expected regret. Infinitesimal perturbation analysis \citep{fu2006gradient} estimates \emph{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.
\subsubsection{Our Contribution}
\label{sec:complexity-contribution}
The covariance-based characterization of Theorem~\ref{thm:regret-cov} 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 \emph{single pass} through the archive:
\begin{equation}
\widehat{\mathrm{Cov}}(c,\pi^{*}(c))
= \frac{1}{n}\sum_{i=1}^{n}
(c_{i} - \bar{c})^{\top}(\pi^{*}(c_{i}) - \bar{\pi}),
\label{eq:sample-cov}
\end{equation}
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{subsec:portfolio}) 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 \eqref{eq:sample-cov} 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 \emph{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{sec:pto-contribution}), 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:
\begin{equation}
\pi^{*}(c) = -(Q + \lambda I)^{-1}c.
\label{eq:qp-closed}
\end{equation}
Substituting into \eqref{eq:sample-cov} gives
\begin{equation}
\mathrm{Cov}(c,\pi^{*}(c))
= -\mathrm{tr}\!\left((Q+\lambda I)^{-1}\Sigma_{c}\right),
\label{eq:qp-cov-analytic}
\end{equation}
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 \emph{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{tab:complexity} 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{sec:experiments} 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.
\begin{table}[ht]
\centering
\caption{
Computational complexity of regret estimation by method and scenario. $n$: sample size; $d$: problem dimension (variables / constraints); $B$: number of SAA scenarios; $\pi^{*}$ analytic means a closed-form solution exists (e.g.\ unconstrained QP). All complexities are for a single regret evaluation.
}
\label{tab:complexity}
\small
\begin{tabular}{@{} l l l l @{}}
\toprule
\textbf{Method} & \textbf{Scenario} & \textbf{Complexity} & \textbf{Gain over SAA} \\
\midrule
SAA
& Any
& $\mathcal{O}(Bn^{2}d^{3})$
& baseline \\
Bootstrap CI \citep{LamZhou2023}
& Any
& $\mathcal{O}(Bnd^{2})$
& $\mathcal{O}(n/d)$ \\
IPA gradient \citep{Fu2006}
& Any (gradient only)
& $\mathcal{O}(Bnd)$
& gradient, not value \\
\midrule
\textbf{Covariance (this paper)}
& \textbf{A: historical pairs}
& $\boldsymbol{\mathcal{O}(nd^{2})}$
& $\boldsymbol{\mathcal{O}(Bn/d)}$ \\
\textbf{Covariance (this paper)}
& \textbf{B: no historical data}
& $\mathcal{O}(n^{2}d^{3})$
& structural insight only \\
\textbf{Covariance (this paper)}
& \textbf{Analytic $\pi^{*}$ (unconstrained QP)}
& $\boldsymbol{\mathcal{O}(d^{3})}$
& $\boldsymbol{\mathcal{O}(Bn^{2})}$ \\
\bottomrule
\end{tabular}
\end{table}
\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.
\section{A Mathematical Model of Regret}
\label{sec:model}
\subsection{Formal Assumptions and Mathematical Setup}
\label{sec:assumptions}
We work throughout with four standing assumptions.
Together, they ensure that regret is well-defined, finite, and estimable from data.
\begin{assumption}[Probability Space]
\label{assump:prob}
$(\Omega, \mathcal{F}, \mathbb{P})$ is a complete probability space, where $\Omega$ is the sample space of all possible cost realisations, $\mathcal{F}$ is a $\sigma$-algebra of measurable events, and $\mathbb{P}$ is a probability measure.
\end{assumption}
\noindent\textit{Commentary.}
Completeness ensures that every sub-event of a null set is measurable, which is needed for the almost-sure Lipschitz argument in Lemma~\ref{lem:lp-measure-zero}.
\begin{assumption}[Cost Vector]
\label{assump:cost}
The cost vector $c \in \mathcal{C} \subseteq \mathbb{R}^{d}$, where
$\mathcal{C}$ is compact and convex, $\mathbb{E}[\|c\|^{2}] < \infty$,
and $P_{c}$ admits a density $f_{c}$ with respect to Lebesgue measure on $\mathbb{R}^{d}$ (absolute continuity).
\end{assumption}
\noindent\textit{Commentary.}
Absolute continuity of $P_{c}$ is the distributional condition that allows the LP zero-residual result to hold
(Lemma~\ref{lem:lp-measure-zero}); it is automatically satisfied by Gaussian, uniform, and all other standard continuous distributions, but it fails for discrete or rounded costs.
\begin{assumption}[Feasible Region]
\label{assump:feasible}
The feasible region $\mathcal{Z} \subseteq \mathbb{R}^{d}$ is
non-empty and compact.
When convexity is needed it is stated explicitly.
For polyhedral $\mathcal{Z} = \{z : Az \leq b\}$, the constraint
matrix $A$ has full row rank.
\end{assumption}
\noindent\textit{Commentary.}
Compactness bounds $\|\pi^{*}(c)\|$ uniformly in $c$, which is
needed for the concentration bound of Theorem~\ref{thm:concentration}.
Full row rank rules out redundant constraints that would create
degenerate normal-cone boundaries.
\begin{assumption}[Decision Function]
\label{assump:decision}
The optimal decision function $\pi^{*} : \mathcal{C} \to \mathcal{Z}$
satisfies: (i) $\pi^{*}$ is $\mathcal{F}$-measurable;
(ii) $\mathbb{E}[\|\pi^{*}(c)\|^{2}] < \infty$;
(iii) $\pi^{*}(c) \in \arg\min_{z \in \mathcal{Z}} c^{\top}z$ for
$\mathbb{P}$-almost every $c \in \mathcal{C}$.
\end{assumption}
\noindent\textit{Commentary.}
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.
\begin{assumption}[Estimation Error]
\label{assump:estimation}
Let $\hat{\mathbb{E}}[c]$ be an estimator of $\mathbb{E}[c]$ based
on i.i.d.\ sample $\{c_{1},\ldots,c_{n}\}$.
We assume: (i) consistency: $\hat{\mathbb{E}}[c] \xrightarrow{P}
\mathbb{E}[c]$; (ii) rate: $\|\hat{\mathbb{E}}[c] - \mathbb{E}[c]\|
= \mathcal{O}_{P}(n^{-1/2})$;
(iii) asymptotic normality: $\sqrt{n}(\hat{\mathbb{E}}[c] -
\mathbb{E}[c]) \xrightarrow{d} \mathcal{N}(0, \Sigma_{c})$.
\end{assumption}
\noindent\textit{Commentary.}
These are standard for the sample mean estimator $\bar{c}$ by
the LLN and CLT under Assumption~\ref{assump:cost}.
Assumption~\ref{assump:estimation} is only invoked in the
statistical results of Section~\ref{sec:statistical}
(Theorems~\ref{thm:imperfect-estimates}--\ref{thm:clt}).
\medskip
The three regularity \emph{conditions} on $\pi^{*}$ (Lipschitz, smooth, strongly convex) are not standing assumptions; they are invoked selectively by individual theorems and are summarized in Table~\ref{tab:conditions}.
\begin{table}[ht]
\centering
\caption{
Regularity conditions referenced in Theorem~3.6 and their
implications for the tightness of the residual bound on $|R(c)|$.
}
\label{tab:conditions}
\small
\begin{tabular}{@{} c l l l @{}}
\toprule
\textbf{Condition} & \textbf{Requirement} & \textbf{Bound on $|R(c)|$}
& \textbf{Tightness} \\
\midrule
1 & $\pi^{*}$ is $L$-Lipschitz
& $L\,\|\mathbb{E}[c]\|\,\sqrt{\mathrm{tr}(\Sigma_{c})}$
& General (weakest) \\
2 & $\pi^{*}$ is $C^{2}$; $\|\nabla\pi^{*}\|\leq M$
& $\frac{M}{2}\,\|\mathbb{E}[c]\|\,\mathrm{tr}(\Sigma_{c})
+ \mathcal{O}(\|\Sigma_{c}\|_{F}^{3/2})$
& Smooth problems \\
3 & Objective is $\mu$-strongly convex
& $\frac{L^{2}}{2\mu}\,\mathrm{tr}(\Sigma_{c})$
& Tightest bound \\
\midrule
\multicolumn{2}{@{}l}{Exact ($R(c)=0$): $\pi^{*}$ affine in $c$}
& $0$
& LP; unconstrained QP \\
\bottomrule
\end{tabular}
\end{table}
\subsection{Main Results}
\label{sec:main-results}
\subsubsection*{Theorem Roadmap}
\label{sec:roadmap}
Figure~\ref{fig:roadmap} shows the logical dependency structure of the eight results in this section. The results are divided into three layers.
\medskip
\noindent\textbf{Layer 1 — Core decomposition} (Section~\ref{sec:core}). Theorem~\ref{thm:regret-cov} 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.
\noindent\textbf{Layer 2 — Structure of the residual}
(Section~\ref{sec:residual})
Theorem~\ref{thm:exact-equality} (exact equality conditions) and Lemma~\ref{lem:lp-measure-zero} (LP measure-zero argument) together characterize when $R(c) = 0$ holds exactly. Theorem~\ref{thm:qp-residual} 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{thm:regret-cov}.
\noindent\textbf{Layer 3 — Statistical theory}
(Section~\ref{sec:statistical}). Lemma~\ref{lem:residual-estimator} and Theorems~\ref{thm:imperfect-estimates}--\ref{thm:clt} translate the decomposition into estimators with finite-sample guarantees. They require Assumption~\ref{assump:estimation} in addition to
Assumptions~\ref{assump:prob}--\ref{assump:decision}.
Theorem~\ref{thm:necessity} (uniqueness) stands somewhat apart: it does not depend on sampling but shows that the covariance form is the only possible representation of regret.
\begin{figure}[ht]
\centering
\begin{tikzpicture}[
node distance = 9mm and 22mm,
box/.style = {draw, rounded corners=3pt, fill=white,
minimum width=38mm, minimum height=8mm,
font=\small, align=center},
corebox/.style = {box, fill=blue!8, draw=blue!50!black, thick},
strbox/.style = {box, fill=orange!10, draw=orange!60!black},
statbox/.style = {box, fill=green!8, draw=green!50!black},
uniqbox/.style = {box, fill=gray!10, draw=gray!50},
arr/.style = {-{Stealth[length=5pt]}, thick},
dasharr/.style = {-{Stealth[length=4pt]}, dashed, gray},
lbl/.style = {font=\footnotesize\itshape, text=gray}
]
\node[corebox] (T36)
{Thm.~3.6\\[-1pt]\footnotesize Regret$=$Cov$+R(c)$\\Bounds on $|R(c)|$};
\node[strbox, below left = of T36] (T37)
{Thm.~3.7 + Lem.~3.7a\\[-1pt]\footnotesize Exact equality\\$R(c)=0$ conditions};
\node[strbox, below = of T36] (T38)
{Thm.~3.8\\[-1pt]\footnotesize QP residual\\$\mathcal{O}(\|\Sigma_c\|^2)$};
\node[statbox, below right = 9mm and -6mm of T37] (L39)
{Lem.~3.9\\[-1pt]\footnotesize Residual estimator $\hat{R}_n$\\bias $\mathcal{O}(n^{-1})$};
\node[statbox, right = 18mm of L39] (T310)
{Thm.~3.10\\[-1pt]\footnotesize Regret under\\imperfect $\hat{\mathbb{E}}[c]$};
\node[statbox, below = 9mm of L39] (T312)
{Thm.~3.12\\[-1pt]\footnotesize Concentration\\bound};
\node[statbox, right = 18mm of T312] (T313)
{Thm.~3.13\\[-1pt]\footnotesize CLT; correct\\delta-method variance};
\node[uniqbox, left = 18mm of T310] (T311)
{Thm.~3.11\\[-1pt]\footnotesize Necessity:\\Cov form unique};
\draw[arr] (T36) -- (T37);
\draw[arr] (T36) -- (T38);
\draw[arr] (T36) -- (L39);
\draw[arr] (T36) -- (T310);
\draw[arr] (T36) -- (T312);
\draw[arr] (T36) -- (T313);
\draw[arr] (T37) -- (L39);
\draw[arr] (T38) -- (T312);
\draw[dasharr] (T36) -- (T311)
node[midway, above, lbl]{informs};
\node[lbl, left = 2mm of T36] {Layer 1};
\node[lbl, left = 2mm of T37] {Layer 2};
\node[lbl, left = 2mm of T312] {Layer 3};
\end{tikzpicture}
\caption{
Logical dependency graph for Section~\ref{sec:main-results}.
Solid arrows indicate that the target result uses the source
result in its proof.
Blue: core decomposition.
Orange: residual structure.
Green: statistical theory.
Gray: uniqueness (independent; uses only Assumptions 3.1--3.4).
}
\label{fig:roadmap}
\end{figure}
\subsubsection{Core Decomposition}
\label{sec:core}
\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{thm:regret-cov} 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)$.
\begin{theorem}[Regret--Covariance Decomposition with Residual Bounds]
\label{thm:regret-cov}
Under Assumptions~\ref{assump:prob}--\ref{assump:decision} and Condition~1 ($\pi^{*}$ is $L$-Lipschitz), the expected regret admits the exact decomposition:
\begin{equation}
\mathrm{Regret}(c)
= \mathrm{Cov}(c,\,\pi^{*}(c)) + R(c),
\label{eq:decomp-body}
\end{equation}
where $\mathrm{Cov}(c,\pi^{*}(c)) = \mathbb{E}[c^{\top}\pi^{*}(c)]
- \mathbb{E}[c]^{\top}\mathbb{E}[\pi^{*}(c)]$ and
$R(c) = \mathbb{E}[c]^{\top}(\mathbb{E}[\pi^{*}(c)] -
\pi^{*}(\mathbb{E}[c]))$.
The residual satisfies:
\begin{align}
|R(c)| &\leq L\,\|\mathbb{E}[c]\|\,\sqrt{\mathrm{tr}(\Sigma_{c})}
&&\text{(Condition~1: Lipschitz)},
\label{eq:bound-lip}\\
|R(c)| &\leq \tfrac{M}{2}\,\|\mathbb{E}[c]\|\,\mathrm{tr}(\Sigma_{c})
+ \mathcal{O}(\|\Sigma_{c}\|_{F}^{3/2})
&&\text{(Condition~2: smooth, $\|\nabla\pi^{*}\|\leq M$)},
\label{eq:bound-smooth}\\
|R(c)| &\leq \tfrac{L^{2}}{2\mu}\,\mathrm{tr}(\Sigma_{c})
&&\text{(Condition~3: $\mu$-strongly convex)}.
\label{eq:bound-sc}
\end{align}
\end{theorem}
\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{proof-thm:regret-cov}.
\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{sec:complexity-contribution}).
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{thm:exact-equality} characterizes the cases where $R(c) = 0$ exactly.
\subsubsection{Structure of the Residual}
\label{sec:residual}
\paragraph{Motivation.}
The bounds in Theorem~\ref{thm:regret-cov} 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{thm:exact-equality} gives the algebraic conditions; Lemma~\ref{lem:lp-measure-zero}
provides the distributional argument needed to cover linear programs, where the algebraic condition fails pointwise but holds almost surely.
\begin{theorem}[Exact Equality Conditions]
\label{thm:exact-equality}
Under Assumptions~\ref{assump:prob}--\ref{assump:decision},
$R(c) = 0$ — so that $\mathrm{Regret}(c) = \mathrm{Cov}(c,\pi^{*}(c))$ exactly — if any one of the following holds:
\begin{enumerate}[label=(\roman*),noitemsep]
\item \textbf{Affine decision rule:} $\pi^{*}(c) = Ac + b$
globally.
\item \textbf{Conditional linearity:}
$\mathbb{E}[\pi^{*}(c) \mid c] = \pi^{*}(\mathbb{E}[c])$.
\item \textbf{Zero covariance of residuals:}
$\mathbb{E}[c^{\top}(\pi^{*}(c) -
\mathbb{E}[\pi^{*}(c)])] = \mathbb{E}[c^{\top}\pi^{*}(\mathbb{E}[c])]$.
\item \textbf{LP with absolutely continuous costs:}
$\mathcal{Z}$ is a non-degenerate polyhedron and $P_c$ is
absolutely continuous (Assumption~\ref{assump:cost}).
See Lemma~\ref{lem:lp-measure-zero}.
\item \textbf{Unconstrained QP:}
For $\min_z c^{\top}z + \frac{\lambda}{2}z^{\top}Qz$ with
$Q \succ 0$ and no binding constraints,
$\pi^{*}(c) = -(Q+\lambda I)^{-1}c$ is affine (case (i)).
\end{enumerate}
\end{theorem}
\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{lem:lp-measure-zero} and Remark~\ref{rem:lp-scope} below.
Full proof in Appendix~\ref{proof-thm:exact-equality}.
\paragraph{Implications.}
This theorem is the key to Table~\ref{tab:covariance-approx}:
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{thm:regret-cov} apply.
\medskip
\begin{lemma}[Zero Residual for Linear Programs under Continuous Costs]
\label{lem:lp-measure-zero}
For the LP $\pi^{*}(c) \in \arg\min_{z\in\mathcal{Z}} c^{\top}z$
with $\mathcal{Z}$ a bounded non-degenerate polyhedron and $P_{c}$ absolutely continuous:
\begin{enumerate}[label=(\alph*),noitemsep]
\item $\pi^{*}$ is piecewise constant on a finite normal-cone
partition of $\mathbb{R}^{d}$.
\item Cone boundaries form a set of Lebesgue measure zero.
\item $\pi^{*}$ is $P_{c}$-a.s.\ Lipschitz with constant $L=0$.
\item $R(c) = 0$.
\end{enumerate}
\end{lemma}
\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{thm:regret-cov} then gives
$|R(c)| \leq 0$.
Full proof in Appendix~\ref{proof-lem:lp-measure-zero}.
\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{rem:lp-scope}).
\begin{remark}[Scope and Limitations of the LP Result]
\label{rem:lp-scope}
Lemma~\ref{lem:lp-measure-zero} requires two conditions that are worth making explicit.
\textbf{Absolute continuity of $P_{c}$.}
The result depends critically on $P_{c}$ being absolutely continuous with respect to Lebesgue measure. If $c$ has a discrete or mixed distribution (for example, if any
component of $c$ is rounded to a grid or takes values in a finite set), then $P_{c}$ may assign positive mass to the boundaries between normal cones, and the argument breaks down. In such cases, the residual $R(c)$ may be non-zero, and the full decomposition of Theorem~3.6 with its Lipschitz bound on $|R(c)|$ must be used instead.
\textbf{Non-degeneracy of the LP.}
The piecewise constant structure of $\pi^{*}$ assumes that the LP has a unique optimal vertex for $P_{c}$-almost every $c$. Degenerate LPs, where multiple vertices achieve the same optimal value for a positive-measure set of cost vectors, may require additional care; however, under absolute continuity of $P_{c}$, the set of degenerate cost vectors (those lying on the boundary of two or more normal cones simultaneously) has measure zero, so degeneracy does not affect the conclusion.
\textbf{Constrained QPs.}
The zero-residual result does \emph{not} extend to constrained quadratic programs, where active constraints create a nonlinear projection that is not globally affine.
Table~\ref{tab:covariance-approx} reports the residual magnitude for constrained QP as $\mathcal{O}(\|\Sigma_{c}\|^{2})$, which is small but nonzero.
\end{remark}
\medskip
\paragraph{Motivation for Theorem~\ref{thm:qp-residual}.}
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.
\begin{table}[ht!]
\centering
\caption{
Covariance approximation quality by problem class.
$R(c)$ is the residual from Theorem~3.6;
"Relative error" refers to the gap between the covariance
estimator and empirical regret in our simulations.
$^\dagger$Exact equality $R(c)=0$ for LP requires $P_{c}$
absolutely continuous w.r.t.\ Lebesgue measure; see
Lemma~\ref{lem:lp-measure-zero}.
$^\ddagger$Exact equality for unconstrained QP follows from
the globally affine solution $\pi^{*}(c) = -(Q+\lambda I)^{-1}c$;
see Theorem~\ref{thm:exact-equality}(v).
Constrained QP has a small but nonzero residual; see
Theorem~3.8.
}
\label{tab:covariance-approx}
\small
\begin{tabular}{@{} l l l l @{}}
\toprule
\textbf{Problem class}
& \textbf{$R(c)$}
& \textbf{Relative error}
& \textbf{Use covariance?} \\
\midrule
Linear programs$^{\,\dagger}$
& $0$ (exact under abs.\ cont.\ $P_{c}$)
& $0$ (population); finite-sample gap
& Exact \\
Unconstrained QP$^{\,\ddagger}$
& $0$ (exact; $\pi^{*}$ affine)
& $0$
& Exact \\
Constrained QP
& $\mathcal{O}(\|\Sigma_{c}\|^{2})$
& Small
& Very good approximation \\
Smooth convex
& $\mathcal{O}(\|\Sigma_{c}\|)$
& Moderate
& With correction term \\
General Lipschitz
& $\mathcal{O}(\sqrt{\|\Sigma_{c}\|})$
& Moderate
& First-order approximation \\
Non-convex smooth
& Problem-dependent
& Variable
& Case-by-case \\
Integer programs
& Can be large
& Large (experiments: 132\%)
& Use with caution \\
\bottomrule
\end{tabular}
\begin{tablenotes}
\small
\item \textbf{Note on the LP finite-sample gap.}
Table 2 states $R(c) = 0$ for LPs at the population level.
The 13.57\% gap observed in the LP simulation (Section~4.2)
is a finite-sample phenomenon: the empirical regret estimator $\hat{\mathbb{E}}[c^{\top}\hat{\pi}(c)] -
\hat{\mathbb{E}}[c^{\top}\hat{\pi}(\hat{\mathbb{E}}[c])]$ and the sample covariance $\widehat{\mathrm{Cov}}(c, \pi^{*}(c))$
are two distinct finite-sample statistics that both converge to the same population quantity $\mathrm{Cov}(c, \pi^{*}(c))$ but at different rates (Theorem~3.13). The 13.57\% gap measures the difference between these two estimators, not a failure of the zero-residual claim.
\end{tablenotes}
\end{table}
\begin{theorem}[Explicit Residual for Quadratic Programs]
\label{thm:qp-residual}
For $\min_{z \in \mathcal{Z}} c^{\top}z + \frac{\lambda}{2}z^{\top}Qz$
with $Q \succeq 0$ and $\mathcal{Z}$ polyhedral:
\begin{equation}
R(c) = \frac{\lambda}{2}\,\mathbb{E}[c]^{\top}
\bigl(\mathbb{E}[(Q+\lambda I)^{-1}]
- (Q+\lambda I)^{-1}\bigr)\mathbb{E}[c]
+ \mathcal{O}(\|\Sigma_c\|^{2}).
\end{equation}
For the Markowitz case $Q = \Sigma_c$:
\begin{equation}
R(c) = -\frac{\lambda}{2(1+\lambda)^{2}}
\,\mathrm{tr}(\Sigma_c^{2})
\left(\frac{\mathbb{E}[c]^{\top}\Sigma_c\mathbb{E}[c]}
{\|\mathbb{E}[c]\|^{2}}\right)
+ \mathcal{O}(\|\Sigma_c\|^{3}).
\end{equation}
\end{theorem}
\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{appendix-quadratic}.
\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{tab:covariance-approx}.
\subsubsection{Statistical Theory}
\label{sec:statistical}
\noindent
The results in this section require
Assumption~\ref{assump:estimation} in addition to
Assumptions~\ref{assump:prob}--\ref{assump:decision}.
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{lem:residual-estimator}.}
Although Theorem~\ref{thm:exact-equality} tells us when $R(c) = 0$
exactly, in practice the practitioner may face a problem class where
$R(c) \neq 0$.
Lemma~\ref{lem:residual-estimator} provides a computable estimate of
$R(c)$ from data, enabling a corrected regret estimate
$\widehat{\mathrm{Cov}} + \hat{R}_n$ for the general case.
\begin{lemma}[Computable Residual Estimator]
\label{lem:residual-estimator}
Under Assumptions~\ref{assump:prob}--\ref{assump:estimation}, given
$n$ samples $\{c_i, \pi^*(c_i)\}_{i=1}^n$, the estimator
\begin{equation}
\hat{R}_n = \bar{c}^{\top}\!\left(
\frac{1}{n}\sum_{i=1}^n \pi^*(c_i) - \pi^*(\bar{c})
\right)
\end{equation}
satisfies: (i) asymptotic unbiasedness,
$\mathbb{E}[\hat{R}_n] = R(c) + \mathcal{O}(n^{-1})$;
(ii) variance bound,
$\mathrm{Var}(\hat{R}_n) = \mathcal{O}(n^{-1}\|\Sigma_c\|_F^2)$.
In particular, $\hat{R}_n$ is consistent at rate
$\mathcal{O}_P(n^{-1/2})$.
\end{lemma}
\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{proof-lem:residual-estimator}.
\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{thm:imperfect-estimates} uses the same estimator logic
to bound regret when the mean is itself estimated from data.
\medskip
\paragraph{Motivation for Theorem~\ref{thm:imperfect-estimates}.}
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{thm:imperfect-estimates} quantifies the combined effect.
\begin{theorem}[Regret under Imperfect Mean Estimates]
\label{thm:imperfect-estimates}
Under Assumptions~\ref{assump:prob}--\ref{assump:estimation} and
Condition~1:
\begin{equation}
\mathrm{Regret}(c,\,\pi^*(\hat{\mathbb{E}}[c]))
= \mathrm{Cov}(c,\pi^*(c)) + R(c) + \mathcal{O}_P(n^{-1/2}).
\end{equation}
Under the conditions of Theorem~\ref{thm:exact-equality} (so
$R(c) = 0$), this simplifies to
$\mathrm{Cov}(c,\pi^*(c)) + \mathcal{O}_P(n^{-1/2})$.
\end{theorem}
\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{assump:estimation}.
Adding this to the Theorem~\ref{thm:regret-cov} decomposition
gives the stated form.
Full proof in Appendix~\ref{proof-thm:imperfect-estimates}.
\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{thm:concentration}).
Using $\hat{\mathbb{E}}[c]$ in place of $\mathbb{E}[c]$ therefore
does not change the asymptotic order of the regret estimator.
\medskip
\paragraph{Motivation for Theorem~\ref{thm:necessity}.}
One might ask whether some other functional form — not involving
covariance — could also represent regret exactly.
Theorem~\ref{thm:necessity} shows the answer is no: the covariance
form is unique up to a constant, so Theorem~\ref{thm:regret-cov} is
not merely one of many possible representations.
\begin{theorem}[Necessity of the Covariance Form]
\label{thm:necessity}
Under Assumptions~\ref{assump:prob}--\ref{assump:decision}, if
$\mathrm{Regret}(c) = \mathbb{E}[\psi(c,\pi^*(c))]$ for some $\psi : \mathbb{R}^d \times \mathbb{R}^d \to \mathbb{R}$ depending only on the joint distribution of $(c,\pi^*(c))$, then
\begin{equation}
\psi(c,\pi^*(c))
= (c - \mathbb{E}[c])^{\top}(\pi^*(c) - \mathbb{E}[\pi^*(c)])
+ \text{constant},
\end{equation}
$\mathbb{P}$-almost surely.
\end{theorem}
\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{appendix-necessity}.
\paragraph{Implications.}
Theorem~\ref{thm:necessity} closes the characterisation: not only
is $\mathrm{Cov}(c,\pi^*(c))$ a valid representation of regret
(Theorem~\ref{thm:regret-cov}), 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{sec:pto-contribution}.
\medskip
\paragraph{Motivation for Theorems~\ref{thm:concentration}
and~\ref{thm:clt}.}
Theorems~\ref{thm:regret-cov}--\ref{thm:necessity} 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.
\begin{theorem}[Concentration Bound]
\label{thm:concentration}
Under Assumptions~\ref{assump:prob}--\ref{assump:estimation} and
Condition~1, with $B = \sup_{c\in\mathcal{C}}\|c\|$:
\begin{equation}
\mathbb{P}\!\left(
\bigl|\widehat{\mathrm{Regret}} - \mathrm{Cov}(c,\pi^*(c))\bigr| > \varepsilon
\right)
\leq 2\exp\!\left(-\frac{n\varepsilon^2}{2(B^2 + L^2\sigma^2)}\right),
\end{equation}
where $\sigma^2 = \mathbb{E}[\|c-\mathbb{E}[c]\|^2]$.
\end{theorem}
\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{sec:complexity-contribution}).
\medskip
\begin{theorem}[Central Limit Theorem for Regret]
\label{thm:clt}
Under Assumptions~\ref{assump:prob}--\ref{assump:estimation}:
\begin{equation}
\sqrt{n}\bigl(\widehat{\mathrm{Regret}}_n - \mathrm{Regret}\bigr)
\xrightarrow{d}
\mathcal{N}(0,\,\sigma^2_{\mathrm{regret}}),
\end{equation}
where
$\sigma^2_{\mathrm{regret}} = \mathrm{Var}(c^{\top}\pi^*(c) -
g(\mathbb{E}[c])^{\top}c)$
and $g(\mathbb{E}[c]) = \pi^*(\mathbb{E}[c]) +
\nabla_c\pi^*(\mathbb{E}[c])^{\top}\mathbb{E}[c]$
is the gradient of $\mu \mapsto \mu^{\top}\pi^*(\mu)$ at
$\mu = \mathbb{E}[c]$.
The simplified form
$\sigma^2_{\mathrm{regret}} = \mathrm{Var}(c^{\top}\pi^*(c)) +
\mathrm{Var}(c^{\top}\pi^*(\mathbb{E}[c])) -
2\mathrm{Cov}(c^{\top}\pi^*(c), c^{\top}\pi^*(\mathbb{E}[c]))$
holds when $\nabla_c\pi^*(\mathbb{E}[c]) = 0$ or
$\mathbb{E}[c] = 0$ (e.g.\ linear programs or zero-mean costs).
\end{theorem}
\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:
\begin{equation}
\mathrm{Regret}(c) \in
\left[\widehat{\mathrm{Regret}}_n
\pm z_{\alpha/2}\,\frac{\hat{\sigma}_{\mathrm{regret}}}{\sqrt{n}}
\right],
\end{equation}
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.
\section{Experiments}\label{sec:experiments}
\subsection{Common Methodology}
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))$.
\subsection{Linear Programming}\label{sec:LP}
This section explores the performance of the proposed regret estimation methodology for a simulated set of Linear Programming problems:
\begin{align*}
\min c^Tz \\
\text{s.t. }Az\leq b \\
z\geq 0
\end{align*}
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:
\begin{align*}
\mathbf{A}_{d\times n}\sim\mathcal{N}(0,I) \\
\mathbf{b}_{d\times 1}\sim|\mathcal{N}(0,I)|+1
\end{align*}
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 (\cite{diamond2016cvxpy}) to obtain a solution $\hat{z}$. We then calculate the empirical regret for each iteration as:
\begin{equation}
\hat{Regret}=\mathbf{c}^T \hat{\mathbf{z}}(\mathbf{c}) - \mathbf{c}^T \hat{\mathbf{z}}\left(\mathbb{E}(\mathbf{c})\right)
\end{equation}
Following Theorem \ref{thm:regret-cov}, 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:
\begin{equation}
Regret = \mathbb{E}[(c-E[c])(z-E[z])]
\end{equation}
Figure \ref{fig:LPRegret} shows theoretical regret $\text{Cov}(c,z)$ converges quickly to -700.982 while empirical regret converges slower to -605.882 (13.57\% error).
\begin{figure}
\centering
\includegraphics[width=0.65\linewidth]{LP_regret.png}
\caption{Linear Programming: Empirical vs. Theoretical Regret}
\label{fig:LPRegret}
\end{figure}
\subsection{Quadratic Optimization (Portfolio Management)}
\label{subsec:portfolio}
This section replicates the simulation, but for a quadratic optimization similar to the one deployed in portfolio management. We test Theorem \ref{thm:regret-cov} on a standard Quadratic Program:
\begin{equation}
\min c^T z + \frac{\lambda}{2}z^T\Sigma_cz
\end{equation}
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{fig:QP}. 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\%.
\begin{figure}
\centering
\includegraphics[width=0.65\linewidth]{QO_regret.png}
\caption{Quadratic Programming: Empirical vs. Theoretical Regret}
\label{fig:QP}
\end{figure}
\subsection{Integer Programming }
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{fig:IP}. 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\%.
\begin{figure}
\centering
\includegraphics[width=0.65\linewidth]{IP_regret.png}
\caption{Integer Programming: Empirical vs. Theoretical Regret}
\label{fig:IP}
\end{figure}
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.
\section{Economic Interpretation}
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.
\subsection{Data}
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.
\subsection{Portfolio Selection}
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{fig:cov-regret-prediction-real-data} shows the aggregate results for covariance-based predicted regret versus realized regret. As the Figure shows, over time, empirical regret approaches theoretical prediction.
\begin{figure}
\centering
\includegraphics[width=0.5\linewidth]{CovRegret.png}
\caption{Cov-Predicted vs. Realized Regret in Real-data financial portfolios}
\label{fig:cov-regret-prediction-real-data}
\end{figure}
\subsection{Integration with a Predict-then-Optimize Training Loop}
\label{sec:pto-contribution}
The preceding experiments validate the covariance formula as a \emph{population-level} characterization of regret. This section asks a different question: does the covariance oracle
remain useful \emph{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 \citep{ElmachtoubGrigas2022}, and compare wall-clock time and final held-out regret against using SAA for validation.
\subsubsection{Setup}
We use a shortest-path LP on a $4 \times 4$ directed grid graph as the downstream optimization problem, following the benchmark of \citet{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{sec:complexity-contribution} 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 \citep{ElmachtoubGrigas2022}:
\begin{equation}
\ell_{\mathrm{SPO+}}(\hat{c}, c, z^{*})
= c^{\top} z^{*}(2\hat{c} - c) - c^{\top} z^{*},
\label{eq:spo-loss}
\end{equation}
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.
\begin{itemize}[noitemsep]
\item \textbf{SAA oracle} ($B$ scenarios).
Draw $B$ cost vectors from the validation set, solve one LP
at the model's predicted mean $\bar{c}_{\mathrm{val}}$, and
compute empirical regret:
\begin{equation}
\widehat{\mathrm{Regret}}_{\mathrm{SAA}}
= \frac{1}{B}\sum_{i=1}^{B} c_{i}^{\top}z^{*}_{i}
- \frac{1}{B}\sum_{i=1}^{B} c_{i}^{\top}
\pi^{*}(\bar{c}_{\mathrm{val}}).
\label{eq:saa-val}
\end{equation}
Cost: one LP solve plus $\mathcal{O}(Bd)$ dot products.
\item \textbf{Covariance oracle.}
Compute the sample covariance over the cached
$(c_{i}, z^{*}_{i})$ pairs:
\begin{equation}
\widehat{\mathrm{Regret}}_{\mathrm{Cov}}
= \frac{1}{n_{\mathrm{val}}}
\sum_{i=1}^{n_{\mathrm{val}}}
(c_{i} - \bar{c})^{\top}(z^{*}_{i} - \bar{z}^{*}).
\label{eq:cov-val}
\end{equation}
Cost: $\mathcal{O}(n_{\mathrm{val}}\, d)$ — no LP solve.
\end{itemize}
We run three training configurations: covariance oracle; SAA oracle
with $B = 50$; SAA oracle with $B = 200$.
\subsubsection{Results}
Table~\ref{tab:spo-latency} 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 \textbf{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.
\begin{table}[ht]
\centering
\caption{
Wall-clock time per single validation call (mean $\pm$ std over
5 repetitions), shortest-path LP with $d = 24$ edges,
$n_{\mathrm{val}} = 100$.
The covariance oracle time is constant in $B$; SAA time grows
slowly with $B$ due to the fixed LP-solve overhead.
}
\label{tab:spo-latency}
\small
\begin{tabular}{@{} l r r r @{}}
\toprule
\textbf{Oracle} & \textbf{$B$} &
\textbf{Latency (ms)} & \textbf{Speedup over SAA} \\
\midrule
Covariance & --- & $0.063 \pm 0.004$ & \emph{baseline} \\
\midrule
\multirow{6}{*}{SAA}
& 10 & $4.4 \pm 0.3$ & $71\times$ \\
& 25 & $4.7 \pm 0.4$ & $74\times$ \\
& 50 & $4.5 \pm 0.4$ & $72\times$ \\
& 100 & $4.6 \pm 0.3$ & $74\times$ \\
& 200 & $5.0 \pm 0.5$ & $79\times$ \\
& 500 & $6.1 \pm 0.6$ & $97\times$ \\
\bottomrule
\end{tabular}
\end{table}
\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 \textbf{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{tab:spo-training})
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.
\begin{table}[ht]
\centering
\caption{
SPO+ training results across validation oracle configurations.
$n_{\mathrm{train}} = 200$, $n_{\mathrm{val}} = 100$,
$n_{\mathrm{test}} = 100$, 20 epochs, batch size 16.
``Val.\ overhead'' is total time spent in validation calls.
``Test $|\mathrm{Regret}|$'' is the magnitude of regret of the
selected checkpoint, evaluated on the held-out test set using
the covariance estimator as a ground-truth proxy.
}
\label{tab:spo-training}
\small
\begin{tabular}{@{} l r r r r r @{}}
\toprule
\textbf{Oracle} & \textbf{$B$} &
\textbf{Train time (s)} &
\textbf{Val.\ overhead (s)} &
\textbf{Best epoch} &
\textbf{Test $|\mathrm{Regret}|$} \\
\midrule
Covariance & --- & $18.2$ & $0.001$ & $0$ & $1.2384$ \\
SAA & $50$ & $18.5$ & $0.048$ & $0$ & $1.2384$ \\
SAA & $200$ & $18.2$ & $0.053$ & $16$ & $1.2384$ \\
\bottomrule
\end{tabular}
\end{table}
Test $|\mathrm{Regret}|$ is identical ($1.2384$) across all three configurations (Table~\ref{tab:spo-training}). 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{thm:regret-cov}: since the covariance estimator is a consistent estimator of true regret (Theorem~\ref{thm:concentration}),
it provides sufficient signal to distinguish good from poor checkpoints even though it is computed without any LP solve.
\subsubsection{Discussion}
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{sec:complexity-contribution}).
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.
\section{Conclusions}\label{sec:conclusion}
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:
\begin{enumerate}
\item Methodological Innovation
\begin{itemize}
\item First to prove regret exactly equals covariance for LP/QP
\item First to provide explicit residual bounds for general stochastic optimization
\item First to achieve $\mathcal{O}(nd^2)$ complexity for exact regret (not approximate)
\end{itemize}
\item Theoretical Depth
\begin{itemize}
\item Connects regret (operational concern) to covariance (statistical quantity)
\item Reveals structural properties unavailable from simulation
\item Provides theoretical benchmarks for learning algorithms
\end{itemize}
\item Practical Impact
\begin{itemize}
\item Enables real-time regret monitoring (1000-10000× speedup over SAA)
\item Guides uncertainty reduction priorities via covariance decomposition
\item Facilitates rapid model comparison in predict-then-optimize frameworks
\end{itemize}
\end{enumerate}
Table \ref{tab:synergy-lit} 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:
\begin{itemize}
\item Regret was traditionally viewed as an operational loss that required simulation, not a statistical quantity with closed-form characterization. The connection between operational performance and the statistical covariance structure was not previously recognized.
\item Disciplinary silos considered regret from different angles—operations research focused on solving optimization problems efficiently, statistics on estimation and inference, and machine learning on prediction accuracy. Our work bridges these disciplines.
\item Prior work studied components separately; we provide the first unified characterization. The decomposition $\text{Regret} = \text{Cov}(c, \pi^*(c)) + R(c)$ requires careful analysis of: When does $E[\pi^*(c)] = \pi^*(E[c])$ hold? (Theorem \ref{thm:exact-equality}: affine decision rules); How do we bound $R(c)$ for non-linear problems? (Theorem \ref{thm:regret-cov}: Lipschitz/smooth/convex bounds); and What is the computational advantage? (Section \ref{sec:experiments}: experiments validate $\mathcal{O}(nd^2)$ vs $\mathcal{O}(Bn^2d^3))$.
\item The emergence of predict-then-optimize frameworks (\cite{ElmachtoubGrigas2022}) created a demand for efficient regret evaluation. Before \cite{ElmachtoubGrigas2022}, the simulation was adequate since regret was computed infrequently. Now, with online learning and real-time decision-making, analytical characterization has become essential.
\end{itemize}
\begin{table*}[]
\centering
\caption{Comparison with Sensitivity Analysis}
\label{tab:comparison-sensitivity}
\begin{tabular}{|c||c|c|}
\hline
Concept & Sensitivity Analysis & Our Regret Characterization \\
\hline\hline
Quantity & $\nabla_c \pi^*(c)$&$E[c^T \pi^*(c)] - E[c]^T \pi*(E[c])$ \\ Scope & Local (infinitesimal) & Global (expected over distribution) \\
Information & Derivative & Expectation \\
Application & What-if analysis & Performance quantification \\
\hline\end{tabular}
\end{table*}
\begin{table*}[]
\centering
\begin{tabular}{|p{3cm}||p{3.6cm}|p{3.6cm}|p{4cm}|}
\hline
Research Area&Prior Work&Our Contribution&Synergy\\
\hline\hline
Predict-then-optimize&Learn models minimizing regret (\cite{ElmachtoubGrigas2022})&Instant regret evaluation via covariance&Our formula provides loss function \cite{ElmachtoubGrigas2022} optimize\\
Simulation methods&SAA, bootstrap for regret estimation&Exact closed-form for LP/QP&Use our method for validation and benchmarking\\
Sensitivity analysis&Local derivatives $\nabla_c \pi^*(c)$&Global expected regret characterization&Complement local with global analysis\\
DRO&Worst-case over Wasserstein balls&Expected regret for specific distribution&Use together: our method for expected case, DRO for worst case\\
ML for optimization&Learn to minimize regret&Analytical regret structure&Guide architecture design and feature engineering\\
\hline
\end{tabular}
\caption{Synergy with Existing Literature}
\label{tab:synergy-lit}
\end{table*}
\bibliography{CovRegret,BayesianLearning,InverseOptimization,ML_Loss,ScoringRules}
\bibliographystyle{aer}
\newpage