Eigenvalue-Decomposition Cost Denoising for Predict-then-Optimize

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 citetelmachtoub2022, 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≥ 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.