Learning-Augmented Online Minimization with Dual Predictions

Christian Coester, Alexa Tudose, Alexander Turoczy
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:21020-21045, 2026.

Abstract

We present learning-augmented algorithms for two general classes of online minimization problems: metrical task systems and laminar set cover. Both algorithms achieve improved theoretical guarantees using machine-learned predictions of an optimal solution to the dual linear program. Unlike optimal primal solutions, which can change drastically under tiny instance perturbations, these dual solutions are much more stable, which ensures the existence of good (and learnable) predictions for families of similar instances. While previous work has used dual predictions in offline settings and for online maximization problems, our algorithms are, to the best of our knowledge, the first demonstration that such dual predictions can be effective for online minimization. Our theoretical results are complemented by experiments on the $k$-server problem and the parking permit problem.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-coester26a, title = {Learning-Augmented Online Minimization with Dual Predictions}, author = {Coester, Christian and Tudose, Alexa and Turoczy, Alexander}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {21020--21045}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/coester26a/coester26a.pdf}, url = {https://proceedings.mlr.press/v306/coester26a.html}, abstract = {We present learning-augmented algorithms for two general classes of online minimization problems: metrical task systems and laminar set cover. Both algorithms achieve improved theoretical guarantees using machine-learned predictions of an optimal solution to the dual linear program. Unlike optimal primal solutions, which can change drastically under tiny instance perturbations, these dual solutions are much more stable, which ensures the existence of good (and learnable) predictions for families of similar instances. While previous work has used dual predictions in offline settings and for online maximization problems, our algorithms are, to the best of our knowledge, the first demonstration that such dual predictions can be effective for online minimization. Our theoretical results are complemented by experiments on the $k$-server problem and the parking permit problem.} }
Endnote
%0 Conference Paper %T Learning-Augmented Online Minimization with Dual Predictions %A Christian Coester %A Alexa Tudose %A Alexander Turoczy %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-coester26a %I PMLR %P 21020--21045 %U https://proceedings.mlr.press/v306/coester26a.html %V 306 %X We present learning-augmented algorithms for two general classes of online minimization problems: metrical task systems and laminar set cover. Both algorithms achieve improved theoretical guarantees using machine-learned predictions of an optimal solution to the dual linear program. Unlike optimal primal solutions, which can change drastically under tiny instance perturbations, these dual solutions are much more stable, which ensures the existence of good (and learnable) predictions for families of similar instances. While previous work has used dual predictions in offline settings and for online maximization problems, our algorithms are, to the best of our knowledge, the first demonstration that such dual predictions can be effective for online minimization. Our theoretical results are complemented by experiments on the $k$-server problem and the parking permit problem.
APA
Coester, C., Tudose, A. & Turoczy, A.. (2026). Learning-Augmented Online Minimization with Dual Predictions. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:21020-21045 Available from https://proceedings.mlr.press/v306/coester26a.html.

Related Material