Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problems

Noah Golowich, Sarath Pattathil, Constantinos Daskalakis, Asuman Ozdaglar
Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:1758-1784, 2020.

Abstract

In this paper we study the smooth convex-concave saddle point problem. Specifically, we analyze the last iterate convergence properties of the Extragradient (EG) algorithm. It is well known that the ergodic (averaged) iterates of EG converge at a rate of $O(1/T)$ (Nemirovski, 2004). In this paper, we show that the last iterate of EG converges at a rate of $O(1/\sqrt{T})$. To the best of our knowledge, this is the first paper to provide a convergence rate guarantee for the last iterate of EG for the smooth convex-concave saddle point problem. Moreover, we show that this rate is tight by proving a lower bound of $\Omega(1/\sqrt{T})$ for the last iterate. This lower bound therefore shows a quadratic separation of the convergence rates of ergodic and last iterates in smooth convex-concave saddle point problems.

Cite this Paper

BibTeX
@InProceedings{pmlr-v125-golowich20a, title = {Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problems}, author = {Golowich, Noah and Pattathil, Sarath and Daskalakis, Constantinos and Ozdaglar, Asuman}, booktitle = {Proceedings of Thirty Third Conference on Learning Theory}, pages = {1758--1784}, 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/golowich20a/golowich20a.pdf}, url = {https://proceedings.mlr.press/v125/golowich20a.html}, abstract = { In this paper we study the smooth convex-concave saddle point problem. Specifically, we analyze the last iterate convergence properties of the Extragradient (EG) algorithm. It is well known that the ergodic (averaged) iterates of EG converge at a rate of $O(1/T)$ (Nemirovski, 2004). In this paper, we show that the last iterate of EG converges at a rate of $O(1/\sqrt{T})$. To the best of our knowledge, this is the first paper to provide a convergence rate guarantee for the last iterate of EG for the smooth convex-concave saddle point problem. Moreover, we show that this rate is tight by proving a lower bound of $\Omega(1/\sqrt{T})$ for the last iterate. This lower bound therefore shows a quadratic separation of the convergence rates of ergodic and last iterates in smooth convex-concave saddle point problems.} }
Endnote
%0 Conference Paper %T Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problems %A Noah Golowich %A Sarath Pattathil %A Constantinos Daskalakis %A Asuman Ozdaglar %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-golowich20a %I PMLR %P 1758--1784 %U https://proceedings.mlr.press/v125/golowich20a.html %V 125 %X In this paper we study the smooth convex-concave saddle point problem. Specifically, we analyze the last iterate convergence properties of the Extragradient (EG) algorithm. It is well known that the ergodic (averaged) iterates of EG converge at a rate of $O(1/T)$ (Nemirovski, 2004). In this paper, we show that the last iterate of EG converges at a rate of $O(1/\sqrt{T})$. To the best of our knowledge, this is the first paper to provide a convergence rate guarantee for the last iterate of EG for the smooth convex-concave saddle point problem. Moreover, we show that this rate is tight by proving a lower bound of $\Omega(1/\sqrt{T})$ for the last iterate. This lower bound therefore shows a quadratic separation of the convergence rates of ergodic and last iterates in smooth convex-concave saddle point problems.
APA
Golowich, N., Pattathil, S., Daskalakis, C. & Ozdaglar, A.. (2020). Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problems. Proceedings of Thirty Third Conference on Learning Theory, in Proceedings of Machine Learning Research 125:1758-1784 Available from https://proceedings.mlr.press/v125/golowich20a.html.

Related Material