# Eigenvalue-Decomposition Cost Denoising for Predict-then-Optimize

arXiv: https://arxiv.org/abs/2609.15111 · HTML: https://mlsanity.com/paper/2609.15111/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 15 references that are in the map.
- First posted on arXiv 14 Sep 2026.

## Builds on (most cited first, 4 of 4)

- [Smart "Predict, then Optimize"](https://mlsanity.com/paper/1710.08005/) (2017)
- [Melding the Data-Decisions Pipeline: Decision-Focused Learning for Combinatorial Optimization](https://mlsanity.com/paper/1809.05504/) (2018)
- [From Predictive to Prescriptive Analytics](https://mlsanity.com/paper/1402.5481/) (2014)
- [Regret Equals Covariance: A Closed-Form Characterization for Stochastic Optimization](https://mlsanity.com/paper/2605.14019/) (2026)

## Abstract (arXiv)

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.