Near-Optimal Algorithms for Minimax Optimization

Tianyi Lin, Chi Jin, Michael I. Jordan
Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:2738-2779, 2020.

Abstract

This paper resolves a longstanding open question pertaining to the design of near-optimal first-order algorithms for smooth and strongly-convex-strongly-concave minimax problems. Current state-of-the-art first-order algorithms find an approximate Nash equilibrium using $\tilde{O}(\kappa_x+\kappa_y)$ or $\tilde{O}(\text{min}\{\kappa_x\sqrt{\kappa_y}, \sqrt{\kappa_x}\kappa_y\})$  gradient evaluations, where $\kappa_x$ and $\kappa_y$ are the condition numbers for the strong-convexity and strong-concavity assumptions. A gap still remains between these results and the best existing lower bound $\tilde{\Omega}(\sqrt{\kappa_x\kappa_y})$. This paper presents the first algorithm with $\tilde{O}(\sqrt{\kappa_x\kappa_y})$ gradient complexity, matching the lower bound up to logarithmic factors. Our algorithm is designed based on an accelerated proximal point method and an accelerated solver for minimax proximal steps. It can be easily extended to the settings of strongly-convex-concave, convex-concave, nonconvex-strongly-concave, and nonconvex-concave functions. This paper also presents algorithms that match or outperform all existing methods in these settings in terms of gradient complexity, up to logarithmic factors.

Cite this Paper

BibTeX
@InProceedings{pmlr-v125-lin20a, title = {Near-Optimal Algorithms for Minimax Optimization}, author = {Lin, Tianyi and Jin, Chi and Jordan, Michael I.}, booktitle = {Proceedings of Thirty Third Conference on Learning Theory}, pages = {2738--2779}, year = {2020}, editor = {Abernethy, Jacob and Agarwal, Shivani}, volume = {125}, series = {Proceedings of Machine Learning Research}, month = {09--12 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v125/lin20a/lin20a.pdf}, url = {https://proceedings.mlr.press/v125/lin20a.html}, abstract = { This paper resolves a longstanding open question pertaining to the design of near-optimal first-order algorithms for smooth and strongly-convex-strongly-concave minimax problems. Current state-of-the-art first-order algorithms find an approximate Nash equilibrium using $\tilde{O}(\kappa_x+\kappa_y)$ or $\tilde{O}(\text{min}\{\kappa_x\sqrt{\kappa_y}, \sqrt{\kappa_x}\kappa_y\})$  gradient evaluations, where $\kappa_x$ and $\kappa_y$ are the condition numbers for the strong-convexity and strong-concavity assumptions. A gap still remains between these results and the best existing lower bound $\tilde{\Omega}(\sqrt{\kappa_x\kappa_y})$. This paper presents the first algorithm with $\tilde{O}(\sqrt{\kappa_x\kappa_y})$ gradient complexity, matching the lower bound up to logarithmic factors. Our algorithm is designed based on an accelerated proximal point method and an accelerated solver for minimax proximal steps. It can be easily extended to the settings of strongly-convex-concave, convex-concave, nonconvex-strongly-concave, and nonconvex-concave functions. This paper also presents algorithms that match or outperform all existing methods in these settings in terms of gradient complexity, up to logarithmic factors.} }
Endnote
%0 Conference Paper %T Near-Optimal Algorithms for Minimax Optimization %A Tianyi Lin %A Chi Jin %A Michael I. Jordan %B Proceedings of Thirty Third Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2020 %E Jacob Abernethy %E Shivani Agarwal %F pmlr-v125-lin20a %I PMLR %P 2738--2779 %U https://proceedings.mlr.press/v125/lin20a.html %V 125 %X This paper resolves a longstanding open question pertaining to the design of near-optimal first-order algorithms for smooth and strongly-convex-strongly-concave minimax problems. Current state-of-the-art first-order algorithms find an approximate Nash equilibrium using $\tilde{O}(\kappa_x+\kappa_y)$ or $\tilde{O}(\text{min}\{\kappa_x\sqrt{\kappa_y}, \sqrt{\kappa_x}\kappa_y\})$  gradient evaluations, where $\kappa_x$ and $\kappa_y$ are the condition numbers for the strong-convexity and strong-concavity assumptions. A gap still remains between these results and the best existing lower bound $\tilde{\Omega}(\sqrt{\kappa_x\kappa_y})$. This paper presents the first algorithm with $\tilde{O}(\sqrt{\kappa_x\kappa_y})$ gradient complexity, matching the lower bound up to logarithmic factors. Our algorithm is designed based on an accelerated proximal point method and an accelerated solver for minimax proximal steps. It can be easily extended to the settings of strongly-convex-concave, convex-concave, nonconvex-strongly-concave, and nonconvex-concave functions. This paper also presents algorithms that match or outperform all existing methods in these settings in terms of gradient complexity, up to logarithmic factors.
APA
Lin, T., Jin, C. & Jordan, M.I.. (2020). Near-Optimal Algorithms for Minimax Optimization. Proceedings of Thirty Third Conference on Learning Theory, in Proceedings of Machine Learning Research 125:2738-2779 Available from https://proceedings.mlr.press/v125/lin20a.html.

Related Material