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

By Noah Golowich, Sarath Pattathil, Constantinos Daskalakis, Asuman E. Ozdaglar. 2020

117 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Mechanics, Statistics and Probability, Statistical Learning Theory, Mathematical Optimization

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Statistics and Probability

In Statistical Learning Theory

In Mathematical Optimization

Citations in the corpus

Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization (2020, background): “This work has focused on attaining improved rates [3, 4,19,21,26,29–31, In the nonconvex-nonconcave setting, research has focused on identifying different notions of local min-max solutions [14, 24, 34, 35] and studying the existence and (local) convergence properties of learning methods to these…”
Tight last-iterate convergence rates for no-regret learning in multi-player games (2020, methodology): “For example, for the iterates z ( t ) of the EG algorithm, [GPDO20] (see (6)) used the potential function Φ( F G , z ( t ) ) := F G ( z ( t ) ) .”
Optimistic Dual Extrapolation for Coherent Non-monotone Variational Inequalities (2021, background): “The following problem remains open: Can single-call extragradient methods have explicit global convergence results beyond the monotone setting? (2)Recently, [13] shows the first tight last iterate result for general smooth convex-concave minimax problems with Lipschitz derivatives of operators.”