Metraipolis › archive › dc_d2def5a0d883
Eigenvalue-Decomposition Cost Denoising for Predict-then-Optimize — arXiv:2609.15111
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.15111
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-16T00:15:44.872Z
- SHA-256 of the archived text
9403193e23c54b9b08fbfdab91ba99bf00bff1c5d2c1ab40a3302274ca75351a- Stable URL of this page
https://metraipolis.com/documento/dc_d2def5a0d883
How to cite
Eigenvalue-Decomposition Cost Denoising for Predict-then-Optimize — arXiv:2609.15111 — arXiv (en), https://arxiv.org/abs/2609.15111 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_d2def5a0d883 (Metraipolis archive dc_d2def5a0d883, sha256 9403193e23c54b9b08fbfdab91ba99bf00bff1c5d2c1ab40a3302274ca75351a)
BibTeX
@misc{dcd2def5a0d883,
title = {Eigenvalue-Decomposition Cost Denoising for Predict-then-Optimize — arXiv:2609.15111},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.15111},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_d2def5a0d883; sha256 9403193e23c54b9b08fbfdab91ba99bf00bff1c5d2c1ab40a3302274ca75351a},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.15111. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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 $°=1$, but underperforms SPO+ at $°\geq 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.
Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-09-15 in cs.LG).
Categorie arXiv: Econometrics (econ.EM) ; Machine Learning (cs.LG); Optimization and Control (math.OC); Spectral Theory (math.SP).
Pagina del lavoro: https://arxiv.org/abs/2609.15111 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-15T23:54:14.946Z dalla pagina https://arxiv.org/catchup/cs.LG/2026-09-15?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).