Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problems
This provides theoretical insights for optimization practitioners by highlighting a performance gap between iterate types in saddle point problems, though it is incremental as it builds on known results.
The paper tackles the convergence rate of the last iterate in smooth convex-concave saddle point problems using the Extragradient algorithm, showing it converges at a rate of O(1/√T) and proving this is tight with a lower bound of Ω(1/√T), revealing a quadratic separation from the averaged iterate's O(1/T) rate.
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 $Ω(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.