Proximal Point Approximations Achieving a Convergence Rate of O(1/k) for Smooth Convex-Concave Saddle Point Problems: Optimistic Gradient and Extra-gradient Methods

Aryan Mokhtari, Asuman E. Ozdaglar, Sarath Pattathil

Abstract

This paper establishes a unified theoretical framework for analyzing two prominent saddle point optimization algorithms: Optimistic Gradient Descent-Ascent (OGDA) and the Extra-gradient (EG) method. By characterizing both methods as approximations of the Proximal Point Method (PPM), the authors prove an $O(1/k)$ convergence rate for the primal-dual gap in smooth convex-concave problems. Notably, this work provides the first such rate for OGDA in the general smooth convex-concave setting and simplifies the existing proof for EG, all while removing the restrictive requirement for a bounded feasible set.

Introduction

Saddle point problems, formulated as $\min_x \max_y f(x, y)$, are the mathematical foundation for many critical challenges in modern machine learning, including the training of Generative Adversarial Networks (GANs), robust optimization, and zero-sum games. While standard Gradient Descent-Ascent (GDA) is effective for simple minimization tasks, it is notoriously unstable in saddle point settings, often resulting in oscillations or divergence.

To address these instabilities, researchers have turned to more sophisticated algorithms like the Extra-gradient (EG) method and Optimistic Gradient Descent-Ascent (OGDA). However, a significant theoretical gap persisted: while EG was known to converge, existing proofs often relied on the assumption of a "compact" (bounded) feasible set. Furthermore, a formal convergence rate for OGDA in the general smooth convex-concave case had not been established. This paper closes these gaps by providing a simplified, unified analysis that does not require the search space to be bounded.

The Proximal Point Framework

The authors' primary contribution is the interpretation of OGDA and EG as approximate variants of the Proximal Point Method (PPM).

The "Gold Standard": PPM

The Proximal Point Method is an implicit optimization strategy known for its extreme stability and a guaranteed $O(1/k)$ convergence rate. However, PPM is computationally expensive because each iteration requires solving a difficult sub-optimization problem, making it impractical for large-scale machine learning.

Approximating the Implicit Step

The authors demonstrate that OGDA and EG use clever gradient updates to "guess" the PPM step without solving the expensive sub-problem:

  • Extra-gradient (EG): Performs a "look-ahead" step to a midpoint and uses the gradient at that midpoint to update the main iterate.
  • Optimistic Gradient Descent-Ascent (OGDA): Uses a "momentum-like" term—specifically the difference between the current and previous gradients—to predict the future gradient direction.

By framing these algorithms as PPM-with-error, the authors utilize variational inequality techniques to prove that the iterates naturally stay within a bounded set and that the primal-dual gap (the difference between the maximum and minimum values of the objective) shrinks at a rate of $O(1/k)$.

Theoretical and Numerical Results

Unified Convergence Analysis

The paper proves that both OGDA and EG achieve a convergence rate of $O(1/k)$ for the primal-dual gap of averaged (ergodic) iterates in smooth convex-concave problems. This analysis is "short and simple" compared to previous literature and removes the necessity of assuming a bounded feasible set, as the boundedness of iterates is shown to be an emergent property of the algorithms themselves.

Computational Efficiency

While both methods share the same theoretical convergence rate, the paper highlights a key practical difference: OGDA is computationally cheaper. OGDA requires only one gradient evaluation per iteration, whereas EG requires two.

To validate these findings, the authors conducted experiments on a synthetic bilinear minimax problem: $$\min_{x \in \mathbb{R}^n} \max_{y \in \mathbb{R}^n} x^\top \mathbf{B}y$$ where $\mathbf{B}$ is a sparse random matrix. This setup serves as a classic stress test because it lacks strong convexity, causing standard methods to fail. The results confirmed that OGDA reached the same error levels as EG but required significantly fewer total gradient computations, providing a real-world speedup.

Discussion and Limitations

While this work provides a major step forward in the theoretical understanding of saddle point methods, some limitations remain:

  • Ergodic Convergence: The $O(1/k)$ rate applies to the averaged iterates. In many practical applications, the "last iterate" is preferred, but proving its convergence is more complex and often yields different rates.
  • Smoothness Assumption: The analysis assumes the objective function is smooth (Lipschitz continuous gradients). Future work is needed to extend these PPM-approximation proofs to non-smooth or stochastic settings where gradients may be noisy.
  • Strong Convexity: In cases where the problem is strongly convex-concave, these methods can achieve faster linear convergence rates. While the authors touch upon this, the primary focus of this paper remains the general $O(1/k)$ proof.

In conclusion, by unifying OGDA and EG under the umbrella of Proximal Point approximations, the authors provide a robust theoretical foundation for the algorithms currently powering complex minimax optimization in machine learning.

Summary updated

BibTeX
@article{mokhtari2020proximal,
  author = {Aryan Mokhtari and Asuman E. Ozdaglar and Sarath Pattathil},
  title = {{Proximal Point Approximations Achieving a Convergence Rate of O(1/k) for Smooth Convex-Concave Saddle Point Problems: Optimistic Gradient and Extra-gradient Methods}},
  journal = {SIAM J. Optim.},
  year = {2020},
  url = {https://openreview.net/forum?id=mAtCpNeq4Wv},
}
Figure