PaperlayerView exact revision on arXiv

Source-linked AI summary

A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approach

Aryan Mokhtari, Asuman Ozdaglar, Sarath Pattathil

arXiv:1901.08511v4math.OCcs.LGstat.ML

TL;DR

The paper addresses fragmented analyses of EG and OGDA for saddle-point problems. It interprets both methods as approximations of PP, enabling convergence-rate analysis in bilinear and strongly convex-strongly concave settings and parameter generalization for OGDA.

  • Problem

    Prior analyses of EG and OGDA used disparate approaches across several settings, making their connections and unifying principles difficult to see.

  • Method

    The paper develops a unified analysis by interpreting EG and OGDA updates as approximations of the classical PP method.

  • Results

    The framework provides linear rate estimates for EG and OGDA, their generalizations, and generalized OGDA across bilinear and strongly convex-strongly concave saddle-point problems.

  • Takeaways & Limitations

    The PP approximation viewpoint supplies a common framework that recovers earlier bilinear convergence results and extends OGDA analysis to broader parameters and strongly convex-strongly concave problems.

  • Takeaways & Limitations

    Numerical experiments and proofs are presented in supplementary material due to space limitations, and PP updates may not be computationally affordable for general functions.

Abstract

from arXiv · show

In this paper we consider solving saddle point problems using two variants of Gradient Descent-Ascent algorithms, Extra-gradient (EG) and Optimistic Gradient Descent Ascent (OGDA) methods. We show that both of these algorithms admit a unified analysis as approximations of the classical proximal point method for solving saddle point problems. This viewpoint enables us to develop a new framework for analyzing EG and OGDA for bilinear and strongly convex-strongly concave settings. Moreover, we use the proximal point approximation interpretation to generalize the results for OGDA for a wide range of parameters.

1 Introduction

The paper studies EG and OGDA for convex-concave saddle point problems and unifies their analysis by interpreting both as approximations of PP. This perspective yields convergence results for bilinear and strongly convex-strongly concave settings, while the introduction frames prior analyses as disconnected.

  • Motivation: EG and OGDA are studied as gradient-based methods for finding saddle points in convex-concave problems.The paper motivates these methods partly through their empirical performance in GAN training.
  • Illustration: For the bilinear example, PP converges fastest, EG and OGDA approximate its trajectory and converge, while GDA diverges.Figure 1 compares the convergence trajectories for min_x max_y xy.
  • Motivation: Prior work analyzed EG and OGDA across different settings with disparate approaches, obscuring their connections and unifying principles.The paper identifies this lack of a unified view as a central motivation.
  • Contribution: The paper interprets both EG and OGDA updates as approximations of the classical PP method.This viewpoint is used as the organizing framework for subsequent analyses.
  • Contribution: The resulting framework analyzes bilinear and general strongly convex-strongly concave problems and derives linear convergence-rate results for EG, OGDA, and generalized OGDA.The paper recovers earlier bilinear rates while adding results for strongly convex-strongly concave OGDA and generalized OGDA.
  • Scope: The introduction notes that numerical experiments and proofs are placed in supplementary material because of space limitations.The stated limitation concerns the presentation location, not the scope of the theoretical results.

2 Preliminaries

The preliminaries define the convex-concave saddle-point setting, smoothness and strong curvature assumptions, and the condition numbers used in the analyses. They also establish notation for iterates and distances to the saddle point.

  • Definitions: A saddle point of a convex-concave function satisfies f(x*, y) ≤ f(x*, y*) ≤ f(x, y*) for all x and y.The definition specifies the equilibrium inequalities used for the problem class.
  • Assumptions: The paper considers bilinear objectives f(x, y) = x⊤By with a square full-rank B and a unique saddle point at (0, 0).For this case, the condition number is defined using the largest and smallest eigenvalues of B⊤B.
  • Assumptions: The general setting assumes continuous differentiability, µx-strong convexity in x, µy-strong concavity in y, and a unique saddle point.The analysis uses µ = min{µx, µy}.
  • Assumptions: The gradients are assumed Lipschitz in both variables, with L defined as max{Lx, Lxy, Ly, Lyx}.These constants describe within-variable and cross-variable gradient regularity.
  • Notation: Under the smoothness and strong-convexity assumptions, the problem condition number is κ := L/µ.This condition number is used to express convergence-rate results.
  • Notation: The paper denotes the k-th iterates by (xk, yk) and tracks their distance to the saddle point (x*, y*).Three iterative algorithms are introduced and analyzed using this notation.

3 Proximal Point method

The Proximal Point (PP) method provides a benchmark for EG and OGDA analysis, with updates defined implicitly through the saddle-point solution. It converges linearly in strongly convex-strongly concave settings and for the bilinear problem, although implementing its updates may be computationally expensive.

  • The PP method serves as a benchmark for analyzing Extra-gradient and Optimistic Gradient Descent Ascent methods.
  • PP updates for saddle-point problems are defined by xk+1 = xk −η∇xf(xk+1, yk+1) and yk+1 = yk + η∇yf(xk+1, yk+1).The updates evaluate gradients at the next iterate, making PP implicit.
  • Implementing PP may be computationally unaffordable because it requires computing inverse operators for general f.
  • PP converges linearly to the unique solution (0, 0) for the bilinear problem minx maxy x⊤By.
  • For strongly convex-strongly concave saddle-point problems, PP iterates converge linearly to the optimal solution.

4 Optimistic Gradient Descent Ascent method

OGDA is analyzed as an approximation of the proximal point method, yielding convergence results for bilinear and strongly convex-strongly concave saddle problems and permitting generalized parameters.

  • 4 Optimistic Gradient Descent Ascent method: OGDA is interpreted as a proximal point update with an additional error term, enabling convergence analysis in bilinear and strongly convex-strongly concave settings.The approximation viewpoint also supports generalized OGDA updates with unequal gradient and negative-momentum coefficients.
  • 4 Optimistic Gradient Descent Ascent method: OGDA combines current gradients with a negative-momentum correction based on the previous gradients.Its y-update uses η∇yf(xk, yk) plus the difference between current and previous gradients.
  • 4.1 Convergence rate of the OGDA Method: For bilinear problems with square, full-rank B, OGDA converges linearly in O(κ log(1/ǫ)) iterations.The result follows from analyzing OGDA as an approximation of proximal point.
  • 4.1 Convergence rate of the OGDA Method: For smooth, strongly convex-strongly concave objectives, OGDA also converges linearly and reaches error ǫ in O(κ log(1/ǫ)) iterations.The stated stepsize is η = 1/(4L).
  • 4.2 Generalized OGDA method: Generalized OGDA remains linearly convergent for a wide parameter range, so the update need not use a factor of 2.For α = β, the generalized update recovers original OGDA; Theorem 5 gives conditions when their difference is sufficiently small.

5 Extra-gradient method

EG uses a midpoint gradient evaluation and is analyzed as an approximation of proximal point. The paper establishes linear convergence for bilinear and smooth strongly convex-strongly concave problems.

  • 5 Extra-gradient method: EG first computes a primal-dual midpoint using the current gradient, then evaluates gradients at that midpoint to obtain the next iterate.This extra midpoint evaluation doubles EG’s computational complexity relative to vanilla GDA.
  • 5 Extra-gradient method: In bilinear problems, EG is an o(η2) approximation of the proximal point method.The approximation follows by replacing inverse factors with their second-order approximations in the proximal point update.
  • 5 Extra-gradient method: On the bilinear problem shown in Figure 2, PP, EG, and OGDA all converge linearly, while PP performs best.EG and OGDA stepsizes were tuned for best performance.
  • 5 Extra-gradient method: EG converges linearly for bilinear problems with square, full-rank B and reaches error ǫ in O(κ log(1/ǫ)) iterations.This matches the rate reported for bilinear problems by Tseng (1995) and improves the O(κ2 log(1/ǫ)) result reported from Liang and Stokes (2018).
  • 5 Extra-gradient method: For smooth strongly convex-strongly concave objectives, EG has linear convergence with computational complexity O(κ log(1/ǫ)).The theorem uses stepsize η = 1/(4L), with κ = L/µ.

6 Numerical Experiments

The experiments compare PP, EG, GDA, and OGDA on bilinear and strongly convex-strongly concave saddle-point problems. EG and OGDA converge linearly on the bilinear problem and track PP more closely than GDA in the quadratic experiment.

  • Bilinear problem: PP, EG, and OGDA all converge linearly to (x∗, y∗) = (0, 0) on the bilinear problem.GDA is omitted from the comparison because it diverges for this problem.
  • Strongly convex-strongly concave problem: EG and OGDA perform better than GDA on the strongly convex-strongly concave quadratic problem.The problem is a saddle-point reformulation of L2-regularized linear regression.
  • Strongly convex-strongly concave problem: EG and OGDA have convergence paths closer to PP, which has the fastest rate, than to GDA in the quadratic experiment.Figure 3 reports convergence in number of iterations, with EG, OGDA, and GDA stepsizes tuned for best performance.

7 Conclusions

The paper develops a unified proximal-point view of EG and OGDA for convex-concave saddle-point problems. It establishes linear-rate estimates in bilinear and strongly convex-strongly concave settings and extends the analysis to OGDA generalizations.

  • Conclusions: EG and OGDA can be interpreted as approximations of the classical PP method for convex-concave saddle-point problems.The paper focuses on discrete-time gradient-based methods.
  • Conclusions: The paper provides linear rate estimates for EG and OGDA in bilinear and strongly convex-strongly concave saddle-point problems.The estimates also cover generalizations of these methods.

8 Supplementary Material

The supplementary material derives explicit PP iterations and associated contraction arguments for bilinear and strongly convex-strongly concave problems. The proofs use symmetric matrix identities, singular-value decompositions, strong convexity, and saddle-point inequalities.

  • Bilinear PP analysis: The bilinear PP updates are rewritten into explicit algorithmic iterations using matrices Qx = (I + η2BB⊤)−1 and Qy = (I + η2B⊤B)−1.These matrices are introduced as symmetric and are used to simplify the update expressions.
  • Bilinear PP analysis: Lemma 1 establishes identities for B, Qx, and Qy through the singular value decomposition B = UΛV⊤.The proof uses the orthonormality of U and V and analogous simplifications for both matrices.
  • Bilinear PP analysis: The bilinear convergence proof bounds the squared iterate norm and uses λmin(BT B) = λmin(BBT ) to establish Theorem 1.The derivation substitutes the matrix identities into the norm expression before applying the minimum-eigenvalue relation.
  • Strongly convex-strongly concave analysis: The saddle-point property supplies the primal and dual inequalities needed to complete the contraction proof.The inequalities are evaluated at (xk+1, yk+1), then combined and regrouped in terms of rk.

8.3 Proof of Proposition 1

The proof starts from PP dynamics and uses Taylor expansions to approximate them with OGDA updates. The resulting primal and dual updates differ from PP by an error of order o(η2).

  • PP-to-OGDA approximation: The proof begins with PP dynamics and constructs an O(η2) approximation leading to OGDA.The PP updates provide the starting point for the approximation.
  • PP-to-OGDA approximation: Taylor expansions approximate Hessian and gradient terms at consecutive iterates with O(η) errors.The expansions are applied to ∇xxf, ∇xf, ∇xyf, and ∇yf.
  • PP-to-OGDA approximation: Substituting the Taylor approximations into the PP update yields the OGDA primal update plus an additional o(η2) error term.The derivation proceeds through the substitutions in Equations (52), (54), and (55).
  • PP-to-OGDA approximation: The same construction applies to the dual update, so the OGDA and PP updates differ by o(η2).The proof combines the primal and dual analyses after defining the relevant symmetric matrices.
  • Bilinear error analysis: For the bilinear problem, the OGDA update is separately written as an approximate PP update and its error is bounded using successive OGDA increments.The bound analyzes terms involving B, BB⊤, and prior iterates.

8.5 Proof of Theorem 4

The proof rewrites OGDA as a proximal-point update with an explicit error term, then bounds the resulting distance recursion under a stepsize restriction.

  • OGDA is represented in the compact operator form z = [x; y] with F(z) = [∇xf(x, y); −∇yf(x, y)].
  • The OGDA update equals a Proximal Point update perturbed by εk = η(F(zk+1) − 2F(zk) + F(zk−1)).
  • The proof derives a squared-distance inequality around the solution z∗ using F(z∗) = 0, squaring, and Young’s inequality.
  • The analysis follows the structure of Theorem 1 of Gidel et al. (2018) for OGDA iterates.
  • For η ≤ 1/4L, the coefficient 1 − 2ηµ − 4η^2L^2 is positive, allowing the final term to be omitted in the bound.

8.6 Proof of Theorem 5

The proof analyzes generalized OGDA by comparing it with Proximal Point updates, then extends the same approximation argument to Extragradient updates.

  • The generalized OGDA method uses xk+1 = xk − (α + β)Byk + βByk−1 and yk+1 = yk + (α + β)Byk − βByk−1.
  • For bilinear problems, the proof compares generalized OGDA with Proximal Point using stepsize α and sets η = max{α, β} under an additional assumption.
  • The generalized-parameter substitutions produce the same result as Theorem 3.
  • Extragradient updates are expanded through first-order Taylor terms, including Hessian-gradient interactions and an o(η) remainder.
  • The Proximal Point update is likewise approximated to second order by replacing future gradients with their updates and applying Taylor’s series.
  • Comparing the expansions shows that the difference between Proximal Point and Extragradient updates is at most o(η^2).

8.8 Proof of Theorem 6

The proof characterizes the bilinear Extragradient–Proximal Point discrepancy with symmetric error matrices and derives a strongly convex-strongly concave convergence bound.

  • The proof defines symmetric error matrices Ex and Ey, with Ex = I − η^2BB⊤ − (I + η^2BB⊤)^−1 and an analogous Ey.
  • These matrices are used to characterize and bound the difference between Extragradient and Proximal Point updates for bilinear problems.
  • The Extragradient updates are rewritten using Qx = (I + η^2BB⊤)^−1 and Qy = (I + η^2B⊤B)^−1, with error terms involving Ex and Ey.
  • After cancellation of cross terms, the bilinear update analysis combines the two coordinate expressions into a simplified bound.
  • Extragradient is written as a Proximal Point update with error εk = η(F(zk+1) − F(zk+1/2)).
  • For η = 1/4L, the condition η^2L^2 + 2ηµ − 1 < 1 yields the stated convergence inequality.
Loading 1901.08511v4…