Extra-Gradient and Optimistic Gradient Descent Converge in Iterates Faster than $O(1/\sqrt{T})$ in All Monotone Lipschitz Variational Inequalities

In this work, we show that the extra-gradient and optimistic gradient descent-ascent methods, arguably the de facto algorithms for solving variational inequalities (VIs) and saddle-point opti- mization problems, converge in iterates at a rate strictly faster than the established lower bound of Ω(1/√T ) in all monotone smooth variational inequalities. These rates apply to both constant and line-search-free, AdaGrad-type step sizes, where no decrease property is generally guaranteed. We believe these results are especially noteworthy in light of recent lower bounds which established that, for any fixed time horizon T , an adversary could construct a monotone Lipschitz VI in which the the iterate at time T is bounded Ω(1/√T ) away from the solution. Our results imply that, even on such adversarially constructed examples, the extra-gradient type method’s slow convergence is only transitory.