Optimal Acceleration for Minimax and Fixed-Point Problems is Not Unique

Taeho Yoon, Jaeyeon Kim, Jaewook J. Suh, Ernest K. Ryu
Proceedings of the 41st International Conference on Machine Learning, PMLR 235:57244-57314, 2024.

Abstract

Recently, accelerated algorithms using the anchoring mechanism for minimax optimization and fixed-point problems have been proposed, and matching complexity lower bounds establish their optimality. In this work, we present the surprising observation that the optimal acceleration mechanism in minimax optimization and fixed-point problems is not unique. Our new algorithms achieve exactly the same worst-case convergence rates as existing anchor-based methods while using materially different acceleration mechanisms. Specifically, these new algorithms are dual to the prior anchor-based accelerated methods in the sense of H-duality. This finding opens a new avenue of research on accelerated algorithms since we now have a family of methods that empirically exhibit varied characteristics while having the same optimal worst-case guarantee.

Cite this Paper

BibTeX
@InProceedings{pmlr-v235-yoon24b, title = {Optimal Acceleration for Minimax and Fixed-Point Problems is Not Unique}, author = {Yoon, Taeho and Kim, Jaeyeon and Suh, Jaewook J. and Ryu, Ernest K.}, booktitle = {Proceedings of the 41st International Conference on Machine Learning}, pages = {57244--57314}, year = {2024}, editor = {Salakhutdinov, Ruslan and Kolter, Zico and Heller, Katherine and Weller, Adrian and Oliver, Nuria and Scarlett, Jonathan and Berkenkamp, Felix}, volume = {235}, series = {Proceedings of Machine Learning Research}, month = {21--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v235/main/assets/yoon24b/yoon24b.pdf}, url = {https://proceedings.mlr.press/v235/yoon24b.html}, abstract = {Recently, accelerated algorithms using the anchoring mechanism for minimax optimization and fixed-point problems have been proposed, and matching complexity lower bounds establish their optimality. In this work, we present the surprising observation that the optimal acceleration mechanism in minimax optimization and fixed-point problems is not unique. Our new algorithms achieve exactly the same worst-case convergence rates as existing anchor-based methods while using materially different acceleration mechanisms. Specifically, these new algorithms are dual to the prior anchor-based accelerated methods in the sense of H-duality. This finding opens a new avenue of research on accelerated algorithms since we now have a family of methods that empirically exhibit varied characteristics while having the same optimal worst-case guarantee.} }
Endnote
%0 Conference Paper %T Optimal Acceleration for Minimax and Fixed-Point Problems is Not Unique %A Taeho Yoon %A Jaeyeon Kim %A Jaewook J. Suh %A Ernest K. Ryu %B Proceedings of the 41st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2024 %E Ruslan Salakhutdinov %E Zico Kolter %E Katherine Heller %E Adrian Weller %E Nuria Oliver %E Jonathan Scarlett %E Felix Berkenkamp %F pmlr-v235-yoon24b %I PMLR %P 57244--57314 %U https://proceedings.mlr.press/v235/yoon24b.html %V 235 %X Recently, accelerated algorithms using the anchoring mechanism for minimax optimization and fixed-point problems have been proposed, and matching complexity lower bounds establish their optimality. In this work, we present the surprising observation that the optimal acceleration mechanism in minimax optimization and fixed-point problems is not unique. Our new algorithms achieve exactly the same worst-case convergence rates as existing anchor-based methods while using materially different acceleration mechanisms. Specifically, these new algorithms are dual to the prior anchor-based accelerated methods in the sense of H-duality. This finding opens a new avenue of research on accelerated algorithms since we now have a family of methods that empirically exhibit varied characteristics while having the same optimal worst-case guarantee.
APA
Yoon, T., Kim, J., Suh, J.J. & Ryu, E.K.. (2024). Optimal Acceleration for Minimax and Fixed-Point Problems is Not Unique. Proceedings of the 41st International Conference on Machine Learning, in Proceedings of Machine Learning Research 235:57244-57314 Available from https://proceedings.mlr.press/v235/yoon24b.html.

Related Material