Eigenvalue-Decomposition Cost Denoising for Predict-then-Optimize
Abstract
Predict-then-optimize methods learn a mapping from features to unknown edge costs. They then solve the shortest-path problem on the predicted costs. We study a feature-free alternative for the case where the decision-maker observes many noisy cost vectors on a fixed network. The cost vectors are denoised by an eigenvalue decomposition (PCA) of their covariance matrix. Dijkstra's algorithm then runs on the result. We test this on the 5×5 grid of \citet{elmachtoub2022}, with $1000$ independent replications and a fresh ground truth in each. We compare against SPO+, against naive Dijkstra on noisy costs, and against two alternatives to a hand-picked rank k (the Gavish-Donoho threshold and a Ledoit-Wolf filter). We also test a hybrid of SPO+ and PCA. Four findings emerge. First, the rank matters. Keeping k=2 components performs worse than no denoising. Second, when costs are close to linear in the features, the Gavish-Donoho threshold recovers the true rank without supervision. PCA-denoised Dijkstra outperforms SPO+ at °=1, but underperforms SPO+ at °≥ 2. The hybrid works best at °=1 and is slightly better than SPO+ at °=2. Third, when costs are strongly nonlinear (°=4), the signal is no longer low-rank, and only the Ledoit-Wolf filter clearly beats the naive baseline. Fourth, the benefit of denoising grows with network size on grids, but not on a layered non-grid network at high nonlinearity.
Related
- Reduced Cost Influence Functions for Predict-then-Optimize under Noisy Data
- Geometric Identification in Predict-Then-Optimize Learning
- Conditional Decomposition Discrepancy: Separating Conditional Bias from Sampling Bias in Small-Sample Cross-Domain Cost Forecasting
- Hyperbolic Graph Representation Learning: Embed in One Metric, Optimize with Another
- Ask Before You Optimize: Dynamic Pre-Formulation Clarification for Interactive Optimization
BibTeX
@misc{aldridgekrawciw2026eigenvaluedecomposition,
title = {{Eigenvalue-Decomposition Cost Denoising for Predict-then-Optimize}},
author = {Henry Aldridge-Krawciw and Irene Aldridge},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.15111},
eprint = {2609.15111},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.15111},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Eigenvalue-Decomposition Cost Denoising for Predict-then-Optimize
AU - Henry Aldridge-Krawciw
AU - Irene Aldridge
PY - 2026
DA - 2026/10/11
PB - arXiv
DO - 10.48550/arxiv.2609.15111
UR - https://arxiv.org/abs/2609.15111
AB - Predict-then-optimize methods learn a mapping from features to unknown edge costs. They then solve the shortest-path problem on the predicted costs. We study a feature-free alternative for the case where the decision-maker observes many noisy cost vectors on a fixed network. The cost vectors are denoised by an eigenvalue decomposition (PCA) of their covariance matrix. Dijkstra's algorithm then runs on the result. We test this on the 5×5 grid of \citet{elmachtoub2022}, with $1000$ independent replications and a fresh ground truth in each. We compare against SPO+, against naive Dijkstra on noisy costs, and against two alternatives to a hand-picked rank k (the Gavish-Donoho threshold and a Ledoit-Wolf filter). We also test a hybrid of SPO+ and PCA. Four findings emerge. First, the rank matters. Keeping k=2 components performs worse than no denoising. Second, when costs are close to linear in the features, the Gavish-Donoho threshold recovers the true rank without supervision. PCA-denoised Dijkstra outperforms SPO+ at °=1, but underperforms SPO+ at °≥ 2. The hybrid works best at °=1 and is slightly better than SPO+ at °=2. Third, when costs are strongly nonlinear (°=4), the signal is no longer low-rank, and only the Ledoit-Wolf filter clearly beats the naive baseline. Fourth, the benefit of denoising grows with network size on grids, but not on a layered non-grid network at high nonlinearity.
ER -