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.
20,208 characters
Eigenvalue-Decomposition Cost Denoising as an Alternative to Predict-then-Optimize for Shortest-Path Problems
\maketitle
\begin{abstract}
Predict-then-optimize methods such as Smart ``Predict, then Optimize''
(SPO+) of \citet{elmachtoub2022} learn a mapping from contextual features
to unknown edge costs and then solve the induced combinatorial problem on
the predicted costs. This approach is powerful but relies on the
predictive model being well specified: when the true cost-generating
process is nonlinear in the features and the predictor is linear, SPO+'s
performance degrades as the misspecification grows. We propose and
evaluate a structurally different remedy for a specific but common
setting: when the decision-maker observes many noisy realizations of the
same underlying cost process, the realized cost vectors themselves can be
treated as a noisy signal and denoised directly, via eigenvalue
decomposition (equivalently, Principal Component Analysis) of their
covariance matrix, before ever invoking a predictive model. We instantiate
this idea on the $5\times5$ grid shortest-path benchmark introduced by
\citet{elmachtoub2022}, retaining only the top-$k$ eigenvectors of the
training cost covariance matrix and projecting new noisy cost
observations onto that subspace prior to solving with Dijkstra's
algorithm \citep{dijkstra1959}. We find that the choice of $k$ is
decisive: keeping only $k{=}2$ eigenvectors discards real signal and
underperforms even the naive noisy-cost baseline, while setting $k{=}5$ to
match the true latent feature dimension makes eigenvalue-denoised
Dijkstra the best-performing method at every misspecification level
tested, outperforming SPO+ by a wide margin under high misspecification.
\end{abstract}
\section{Introduction}
Many operational decisions are shortest-path problems in disguise: routing
a vehicle, scheduling a sequence of tasks, or moving a packet through a
network, all reduce to finding a minimum-cost path through a graph whose
edge costs are not known in advance but must be estimated from data
\citep{vera2021,chen2004}. The dominant paradigm for this class of
problems is \emph{predict-then-optimize}: fit a model that maps observed
features to edge costs, then feed the predicted costs into an
off-the-shelf combinatorial solver. The Smart ``Predict, then Optimize''
(SPO+) framework of \citet{elmachtoub2022} refined this paradigm by
replacing the usual squared-error training loss with a convex surrogate
of the true \emph{decision} loss, so that the predictive model is trained
to make good \emph{decisions} rather than merely accurate point
predictions of cost.
SPO+ and its relatives \citep{bertsimas2020,ban2019,donti2017,wilder2019}
all share an implicit assumption: that a hypothesis class exists (in
SPO+'s case, linear functions of the features) rich enough to capture the
true cost-generating process reasonably well. When this assumption fails
-- when the true process is a nonlinear function of the features but the
predictor is constrained to be linear -- the predictor is
\emph{misspecified}, and SPO+'s decision quality degrades as the degree of
nonlinearity increases, a pattern we reproduce and quantify in Section
\ref{sec:experiments}.
This paper asks a different question. Suppose the decision-maker does not
need to predict costs from features at all, but instead directly observes
many independent, noisy realizations of the cost vector for the
\emph{same} underlying network -- e.g. repeated daily commutes over the
same road network, where each day's travel times are a noisy draw from a
common but unknown structure. In this setting, the natural tool is not a
supervised predictor but an \emph{unsupervised} one: treat the collection
of observed cost vectors as a data matrix, and denoise it. If the true
cost signal occupies a low-dimensional subspace of the full edge-cost
space -- which it will if it is driven by a small number of latent
factors, as in the \citet{elmachtoub2022} synthetic design -- then an
eigenvalue decomposition (equivalently, PCA
\citep{pearson1901,hotelling1933}) of the observed cost covariance matrix
should recover that subspace, and reconstructing each new observation
using only its top-$k$ eigencomponents should suppress much of the
idiosyncratic noise while retaining the signal. This is exactly the logic
behind optimal singular-value shrinkage for matrix denoising
\citep{gavish2014}, and behind the use of eigendecomposed covariance
structure in decision-making more broadly -- most famously in
mean-variance portfolio theory \citep{markowitz1952}, and, in the specific
context of decision-theoretic regret, in the closed-form
regret-equals-covariance characterization of \citet{aldridge2026regret}.
See also \citet{aldridge2025optimize} for a complementary discussion of
reordering the predict/optimize pipeline.
We make this idea concrete for the shortest-path setting and compare it
head-to-head against three natural baselines: Dijkstra's algorithm run on
the (unobservable, oracle) true costs; Dijkstra run naively on the raw
noisy/misspecified costs; and SPO+. Our central empirical finding is that
the eigenvalue-denoising approach is highly sensitive to the number of
retained components $k$: an undersized $k$ discards real signal and
underperforms doing nothing at all, while a correctly sized $k$ makes the
method the best of the four across every misspecification level we test,
including levels at which SPO+ itself breaks down.
\section{Related Work}
\paragraph{Shortest paths and predict-then-optimize.}
Dijkstra's algorithm \citep{dijkstra1959} remains the standard exact
solver for nonnegative-weight shortest-path problems, and constrained and
large-scale variants continue to be an active area
\citep{vera2021,chen2004}. When edge costs are not directly observed,
predict-then-optimize methods learn them from contextual features.
\citet{elmachtoub2022} introduced the SPO and SPO+ loss functions, convex
surrogates for the true regret of a decision induced by a predicted cost
vector, and showed both statistical and computational advantages over
training a predictor with a generic loss (e.g. squared error) that
ignores the downstream optimization structure. Related decision-focused
learning frameworks include the predictive-prescriptive framework of
\citet{bertsimas2020}, the data-driven newsvendor analysis of
\citet{ban2019}, and end-to-end task-based learning through the
optimization layer itself \citep{donti2017,wilder2019}. All of these
methods are supervised: they require paired (feature, realized-cost)
training data and a hypothesis class for the feature-to-cost map.
\paragraph{Eigenvalue decomposition and denoising.}
Principal Component Analysis \citep{pearson1901,hotelling1933} is the
classical tool for finding the low-dimensional subspace that best explains
the variance of a data matrix, and is equivalent to an eigenvalue
decomposition of the (empirical) covariance matrix. When a data matrix is
a low-rank signal plus noise, keeping only the leading eigen/singular
components is a standard and asymptotically principled denoising
strategy; \citet{gavish2014} characterize the optimal number of components
to retain (and the optimal shrinkage of their singular values) under a
spiked-covariance noise model. Unlike predict-then-optimize, this
denoising approach requires no feature-to-cost hypothesis class at all --
only repeated observations of the cost vector -- and is consequently
immune to the specific failure mode of predictor misspecification that
afflicts SPO+.
\paragraph{Regret and covariance.}
Closest in spirit to our evaluation methodology is
\citet{aldridge2026regret}, which shows that for stochastic linear
programs (including shortest path), expected regret relative to acting on
the mean cost decomposes exactly into a covariance term between the
realized cost and the realized optimal decision, with no residual for
continuous-cost LPs. We use ordinary realized-cost regret (relative to the
oracle optimum) throughout this paper as our evaluation metric, and note
that the covariance-based estimator of that reference could serve as a
cheaper drop-in replacement for the Sample Average Approximation
regret estimates we compute directly, an avenue we leave to future work.
\citet{aldridge2025optimize} separately considers reordering the
predict/optimize pipeline itself, a complementary idea to the denoise-only
approach studied here.
\section{Methodology}
\label{sec:methodology}
\subsection{Grid and Cost Generation}
We use the same $5\times5$ directed acyclic grid graph as
\citet{elmachtoub2022}'s shortest-path experiments: $25$ nodes arranged in
a grid, edges permitted only rightward and downward, giving $d=40$ edges,
a source at the top-left corner, and a sink at the bottom-right corner. For
a feature vector $x\in\mathbb{R}^p$ ($p=5$) drawn i.i.d.\ $N(0,I_p)$, and a
fixed random matrix $B\in\{-1,+1\}^{d\times p}$, the \emph{true} (noise-free)
cost of edge $e$ is
\begin{equation}
c^{\text{true}}_e(x) \;=\; \left[\frac{1}{\sqrt p}(Bx)_e + 3\right]^{\deg},
\label{eq:true-cost}
\end{equation}
where $\deg\in\{1,2,4\}$ controls the degree of nonlinearity in the
features -- $\deg=1$ is linear (well specified for a linear predictor),
and larger $\deg$ increasingly misspecifies any linear model. The
\emph{observed} (misspecified/noisy) cost is
\begin{equation}
c^{\text{noisy}}_e(x) \;=\; c^{\text{true}}_e(x)\cdot \varepsilon_e,
\qquad \varepsilon_e \sim \mathrm{Uniform}[1-\bar\varepsilon,\,1+\bar\varepsilon],
\label{eq:noisy-cost}
\end{equation}
with $\bar\varepsilon = 0.5$ throughout. This is exactly the synthetic
design of \citet{elmachtoub2022}, with the true and noisy costs exposed
separately so that we can evaluate decision quality against the
noise-free ground truth while only ever \emph{acting} on noisy
observations.
\subsection{Baselines}
\begin{description}
\item[(1) Dijkstra on true costs.] Solves the shortest path directly on
$c^{\text{true}}(x)$ for each test instance. This is an oracle upper
bound: no real decision-maker has access to $c^{\text{true}}$, but it
defines the zero-regret reference point for all other methods.
\item[(2) Dijkstra on misspecified (noisy) costs.] Solves the shortest
path directly on the raw observation $c^{\text{noisy}}(x)$, ignoring that
it is a noisy realization rather than the true expected cost. This is the
naive baseline.
\item[(3) SPO+ \citep{elmachtoub2022}.] A linear predictor $\hat c(x) = Wx$
is trained on $(x_i, c^{\text{noisy}}_i)$ pairs from a training set, using
the SPO+ subgradient method (Algorithm~\ref{alg:spoplus}), and the
shortest path is then solved on $\hat c(x)$ for each test instance.
\end{description}
\begin{algorithm}[t]
\caption{SPO+ training (subgradient descent), following \citet{elmachtoub2022}}
\label{alg:spoplus}
\begin{algorithmic}[1]
\State Initialize $W \gets$ small random matrix
\For{epoch $= 1, \dots, E$}
\For{each training example $(x_i, c_i, z_i^\ast)$ in random order}
\State $\hat c \gets W x_i$
\State $z_{\text{spo}} \gets \arg\min_{z \in \mathcal Z} \left(2\hat c - c_i\right)^\top z$ \Comment{shortest-path oracle}
\State $\nabla_{\hat c} \gets 2\left(z_i^\ast - z_{\text{spo}}\right)$
\State $W \gets W - \eta\, \nabla_{\hat c}\, x_i^\top$ \Comment{plus $\ell_2$ regularization}
\EndFor
\EndFor
\end{algorithmic}
\end{algorithm}
\subsection{Eigenvalue-Decomposition Denoising}
\label{sec:denoising-method}
Our proposed method (4) requires no feature-to-cost hypothesis class.
Instead, from a training sample of $n$ noisy cost vectors
$C \in \mathbb{R}^{n\times d}$ (rows are training instances, columns are
edges), we compute the empirical mean $\bar c = \frac1n \sum_i C_i$, the
centered data $\tilde C = C - \bar c$, and the empirical covariance
\begin{equation}
\Sigma \;=\; \frac1n\, \tilde C^\top \tilde C \;\in\; \mathbb{R}^{d\times d}.
\end{equation}
Because $\Sigma$ is symmetric positive semi-definite, its eigenvalue
decomposition $\Sigma = V\Lambda V^\top$ has real, non-negative
eigenvalues; let $V_k \in \mathbb{R}^{d\times k}$ collect the eigenvectors
associated with the $k$ largest eigenvalues. For a new noisy observation
$c^{\text{noisy}}$, the denoised reconstruction is the projection onto the
affine subspace spanned by these top-$k$ directions:
\begin{equation}
c^{\text{denoised}} \;=\; \bar c \;+\; V_k V_k^\top \left(c^{\text{noisy}} - \bar c\right).
\label{eq:denoise}
\end{equation}
$V_k$ and $\bar c$ are fit once on the training set and then applied
prospectively to each test instance, exactly as $W$ is fit once and
applied prospectively in SPO+ -- both methods use only training data to
build a fixed object that is applied, unchanged, to new test instances.
The shortest path is then solved on $c^{\text{denoised}}$ with Dijkstra.
The rationale for Eq.~\eqref{eq:denoise} is that under the generative
model of Eq.~\eqref{eq:true-cost}, the true cost signal is driven by only
$p=5$ latent coordinates (linearly, before the $\deg$ power is applied),
so it plausibly concentrates in a low-dimensional subspace of the
$d=40$-dimensional edge-cost space, whereas the multiplicative noise
$\varepsilon_e$ in Eq.~\eqref{eq:noisy-cost} is comparatively
unstructured across edges. Retaining only the top-$k$ eigendirections
should therefore capture a disproportionate share of the signal while
discarding a disproportionate share of the noise -- \emph{provided} $k$
is large enough to actually span the signal subspace. We test this
directly by comparing $k=2$ against $k=5$ (the true latent dimension) in
Section~\ref{sec:experiments}.
\section{Experimental Setup}
For each misspecification level $\deg \in \{1,2,4\}$ we draw $n_{\text{train}}=200$
training instances and $n_{\text{test}}=300$ test instances from
Eqs.~\eqref{eq:true-cost}--\eqref{eq:noisy-cost}, sharing a single random
matrix $B$ across the train/test split. SPO+ is trained for 50 epochs of
subgradient descent with learning rate $0.02$ and $\ell_2$ penalty
$10^{-4}$ (Algorithm~\ref{alg:spoplus}). The eigen-denoiser
(Eq.~\eqref{eq:denoise}) is fit once on the training cost matrix, for
$k \in \{2, 5\}$. All four methods are evaluated on the \emph{same} test
instances, and every method's chosen path is scored by its \textbf{true}
cost $c^{\text{true}}(x)^\top z$, so that method (1) always attains the
minimum possible cost by construction; we report the other three methods'
mean regret relative to that oracle optimum,
$\text{regret} = \mathbb E\!\left[\frac{c^{\text{true}\top} z - c^{\text{true}\top} z^\ast}{c^{\text{true}\top}z^\ast}\right]$.
\section{Results}
\label{sec:experiments}
\subsection{Undersized Denoising ($k=2$)}
Table~\ref{tab:k2} reports results when only the top 2 eigenvectors are
retained, capturing between 33\% and 43\% of the training cost variance
depending on $\deg$. At every misspecification level, eigenvalue-denoised
Dijkstra is the \emph{worst} of the four methods, including worse than
doing nothing (the naive noisy-cost baseline).
\begin{table}[h]
\centering
\caption{Mean regret relative to the true-cost optimum, $k=2$ retained eigenvectors.}
\label{tab:k2}
\begin{tabular}{@{}lrrrr@{}}
\toprule
$\deg$ & Noisy (naive) & SPO+ & Eigen-denoised ($k{=}2$) & Var.\ explained \\
\midrule
1 & 6.82\% & 3.61\% & 13.41\% & 33.4\% \\
2 & 5.18\% & 6.59\% & 25.86\% & 42.7\% \\
4 & 4.55\% & 26.12\% & 77.71\% & 39.4\% \\
\bottomrule
\end{tabular}
\end{table}
\subsection{Correctly-Sized Denoising ($k=5$)}
Table~\ref{tab:k5} repeats the experiment with $k=5$, matching the true
latent feature dimension $p$. The ranking reverses completely:
eigenvalue-denoised Dijkstra becomes the \emph{best} method at every
misspecification level, and its advantage over SPO+ widens sharply as
$\deg$ grows -- at $\deg=4$, SPO+'s regret (26.12\%) is nearly double that
of the denoised method (14.67\%), and both are far worse than the
denoised method's own regret at lower $\deg$.
\begin{table}[h]
\centering
\caption{Mean regret relative to the true-cost optimum, $k=5$ retained eigenvectors.}
\label{tab:k5}
\begin{tabular}{@{}lrrrr@{}}
\toprule
$\deg$ & Noisy (naive) & SPO+ & Eigen-denoised ($k{=}5$) & Var.\ explained \\
\midrule
1 & 6.82\% & 3.61\% & \textbf{1.60\%} & 60.3\% \\
2 & 5.18\% & 6.59\% & \textbf{1.74\%} & 76.3\% \\
4 & 4.55\% & 26.12\% & \textbf{14.67\%} & 70.9\% \\
\bottomrule
\end{tabular}
\end{table}
\subsection{Discussion}
Two patterns are worth isolating. First, SPO+'s regret grows sharply with
$\deg$ (3.61\% $\to$ 6.59\% $\to$ 26.12\%): as the true cost becomes more
nonlinear in the features, a linear predictor becomes more misspecified,
and no amount of SPO-consistent training can fix a hypothesis class that
cannot represent the target function. Second, the eigen-denoiser's regret
is comparatively insensitive to $\deg$ when $k$ is correctly sized
(1.60\% $\to$ 1.74\% $\to$ 14.67\%): because the denoiser never attempts
to model the feature-to-cost \emph{functional form} at all, it is not
directly harmed by that function becoming more nonlinear -- it only needs
the realized cost vectors to continue concentrating in a $k$-dimensional
subspace, which they do for any $\deg$ given how Eq.~\eqref{eq:true-cost}
is constructed. The method's sensitivity to $\deg$ that does remain
(1.60\% at $\deg=1$ growing to 14.67\% at $\deg=4$) is attributable to the
increasing dispersion of the underlying cost distribution at higher
$\deg$, which the fraction of variance explained (70--76\% at $k=5$,
rather than 100\%) does not fully capture.
These results should not be read as ``denoising dominates
predict-then-optimize.'' Rather, the two methods fail in different
regimes and for different reasons: SPO+ fails when the hypothesis class
cannot represent the true cost function; eigenvalue denoising fails when
$k$ is chosen without regard to the effective rank of the underlying
signal. In our setting the correct $k$ happened to be knowable in advance
because we generated the data ourselves; in practice, $k$ would need to
be chosen by a model-selection procedure (e.g.\ cross-validated
reconstruction error, or the spiked-covariance threshold of
\citet{gavish2014}) rather than assumed.
\section{Limitations and Future Work}
Our experiments use a single, small ($25$-node) grid and a synthetic cost
process whose true rank is known by construction; real cost data will not
come with a known target rank, and selecting $k$ well is itself a
nontrivial estimation problem \citep{gavish2014}. The denoising approach
also requires \emph{repeated} observations of costs on a \emph{fixed}
network topology, which SPO+ does not require -- SPO+ can price out an
edge cost never seen at training time as long as its features are
in-distribution, whereas the eigen-denoiser has no mechanism to
generalize beyond the covariance structure it was fit on. A natural next
step is a hybrid: use SPO+ (or any feature-based predictor) to produce an
initial cost estimate, and use eigenvalue denoising of the \emph{residual}
between predicted and observed costs to further clean the signal before
optimizing, potentially combining the strengths of both approaches. We
also flag, per \citet{aldridge2026regret}, that the covariance-based
regret estimator could replace our direct Sample Average Approximation
of regret at a fraction of the computational cost for larger problems,
which we leave to future work.
\section{Conclusion}
We introduced and evaluated an eigenvalue-decomposition-based alternative
to predict-then-optimize for shortest-path problems with misspecified,
noisy costs. The method requires no feature-to-cost model and instead
denoises repeated cost observations directly via PCA of their covariance
matrix. Its performance is highly sensitive to the number of retained
components: an undersized choice underperforms doing nothing, while a
correctly sized choice outperforms SPO+ substantially, particularly under
high model misspecification where SPO+'s linear hypothesis class
struggles. The two approaches are complementary rather than competing,
and combining them is a promising direction for future work.
\bibliographystyle{plainnat}
\bibliography{references}