Last-Iterate Convergence of Optimistic Gradient Method for Monotone Variational Inequalities

Eduard Gorbunov, Adrien Taylor, Gauthier Gidel

Abstract

The Past Extragradient (PEG) method, also known as the Optimistic Gradient method, has seen a recent surge in interest within the optimization community due to the emergence of variational inequality formulations in machine learning. Recently, for the unconstrained case, Golowich et al. [2020] proved that a $O(1/N)$ last-iterate convergence rate in terms of the squared norm of the operator can be achieved for Lipschitz and monotone operators with a Lipschitz Jacobian. In this work, by introducing a novel analysis through potential functions, we show that (i) this $O(1/N)$ last-iterate convergence can be achieved without any assumption on the Jacobian of the operator, and (ii) it can be extended to the constrained case, which was not derived before even under Lipschitzness of the Jacobian. The proof is significantly different from previous approaches, and its discovery was computer-aided. These results close the open question of the last iterate convergence of PEG for monotone variational inequalities.

Introduction

Many modern machine learning tasks—including training Generative Adversarial Networks (GANs), robust optimization, and multi-agent reinforcement learning—are formulated as Variational Inequalities (VIs) rather than simple function minimization.

In standard minimization, researchers typically focus on the last iterate (the final model weights). However, in the context of VIs and minimax games, proving that the last iterate actually converges to the solution is notoriously difficult. Most existing proofs only show that the average of all iterates converges (ergodic convergence). In practice, practitioners use the last iterate, making theoretical guarantees for it highly desirable.

Until this work, the "Optimistic Gradient" (PEG) method—a highly efficient "single-call" algorithm—only had a last-iterate proof for unconstrained problems that assumed the operator's derivative (the Jacobian) was smooth. This assumption is often unrealistic and hard to verify. Furthermore, there was no last-iterate proof at all for constrained cases where variables must stay within a specific set.

Methodology: Computer-Aided Discovery

The authors employ a sophisticated framework called Performance Estimation Problems (PEP) to bridge the gap between numerical observation and theoretical proof.

  1. Computer-Aided Discovery: Instead of guessing a proof by hand, the authors formulated the search for a convergence bound as a Semidefinite Program (SDP). By solving these programs numerically, they could observe the worst-case behavior of the algorithm directly.
  2. Potential Functions (Lyapunov Analysis): By analyzing the "dual" of these computer-generated results, the authors identified a new potential function—a mathematical expression guaranteed to decrease at every step of the algorithm.
  3. Past Extragradient (PEG): The analysis focuses on PEG, which uses a gradient from a previous step to "anticipate" the geometry of the problem, making it more stable than standard gradient descent-ascent.

The core novelty lies in the construction of these potential functions, which combine the distance to the solution with the squared norm of the operator in a way that doesn't require the Jacobian to be Lipschitz.

Key Insights

  • Simpler Assumptions: The $O(1/N)$ rate holds under only two standard conditions: the operator must be monotone (pointing in the right direction) and Lipschitz (it doesn't change too abruptly). No knowledge of second derivatives (Jacobian) is required.
  • Non-Monotonicity of the Norm: A key insight is that the norm of the operator (the "error" signal) does not actually decrease at every single step. This oscillation is why previous researchers struggled to find a proof. The authors' new potential function accounts for this by looking at multiple consecutive iterates.

Key Results

The paper provides concrete upper bounds for the convergence rate, confirming the $O(1/N)$ "gold standard" for first-order methods.

Numerical verification of the $O(1/k)$ last-iterate convergence rate using Performance Estimation Problems (PEP).
  • Unconstrained Case: The squared norm of the operator at step $N$ is bounded by: $$\|F(x^N)\|^2 \le \frac{123 L^2 \|x^0 - x^*\|^2}{N + 32}$$
  • Constrained Case: The proof extends to the "Projected PEG" method, establishing a similar $O(1/N)$ rate for the squared residual (a measure of distance from optimality conditions).
  • Tightness: As shown in the PEP results above, these results match known lower bounds, indicating that the $O(1/N)$ rate is optimal for this class of algorithms.

Limitations and Future Work

While this work closes a major open question, several avenues remain for future research:

  • Large Constants: The multiplicative constants (like 123) are quite large. Numerical experiments suggest the "real" constant is smaller, but the proof sacrificed tightness for readability.
  • Stepsize Restrictions: The proof requires a slightly smaller stepsize ($\gamma \le 1/3L$ or $1/4L$) than what is sometimes used in practice.
  • Deterministic Setting: This work focuses on the deterministic setting. Extending these last-iterate results to the stochastic setting, common in large-scale ML, remains a major challenge.
  • Non-Monotone Problems: Understanding last-iterate behavior in non-monotone settings (like complex GAN architectures) is the next frontier for optimization theory.

Summary updated

Abstract

The Past Extragradient (PEG) [Popov, 1980] method, also known as the Optimistic Gradient method, has known a recent gain in interest in the optimization community with the emergence of variational inequality formulations for machine learning. Recently, in the unconstrained case, Golowich et al. [2020] proved that a $O(1/N)$ last-iterate convergence rate in terms of the squared norm of the operator can be achieved for Lipschitz and monotone operators with a Lipschitz Jacobian. In this work, by introducing a novel analysis through potential functions, we show that (i) this $O(1/N)$ last-iterate convergence can be achieved without any assumption on the Jacobian of the operator, and (ii) it can be extended to the constrained case, which was not derived before even under Lipschitzness of the Jacobian. The proof is significantly different from the one known from Golowich et al. [2020], and its discovery was computer-aided. Those results close the open question of the last iterate convergence of PEG for monotone variational inequalities.
BibTeX
@inproceedings{gorbunov2022last,
  author = {Eduard Gorbunov and Adrien Taylor and Gauthier Gidel},
  title = {{Last-Iterate Convergence of Optimistic Gradient Method for Monotone Variational Inequalities}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=U3JMGvCmMl},
}
Figure