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\times 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 $°\ge 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.

arXiv comment12 pages