Eigenvalue-Decomposition Cost Denoising for Predict-then-Optimize

Henry Aldridge-Krawciw and Irene Aldridge

Papers from arXiv.org

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\times5$ 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 $\deg=1$, but underperforms SPO+ at $\deg\geq 2$. The hybrid works best at $\deg=1$ and is slightly better than SPO+ at $\deg=2$. Third, when costs are strongly nonlinear ($\deg=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.

Date: 2026-09, Revised 2026-10
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://arxiv.org/pdf/2609.15111 Latest version (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:arx:papers:2609.15111

Access Statistics for this paper

More papers in Papers from arXiv.org
Bibliographic data for series maintained by arXiv administrators ().