PaperlayerView exact revision on arXiv

Source-linked AI summary

Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problems

Noah Golowich, Sarath Pattathil, Constantinos Daskalakis, Asuman Ozdaglar

arXiv:2002.00057v2cs.LGmath.OCstat.ML

TL;DR

The paper addresses the lack of a last-iterate convergence rate for EG in smooth convex-concave saddle-point problems, where averaged iterates already have an O(1/T) guarantee. It analyzes EG and establishes a tight O(1/√T) last-iterate rate, yielding a quadratic separation from the averaged rate.

  • Problem

    Although EG’s averaged iterates have an O(1/T) rate, a last-iterate rate without strong convexity was not known.

    Source: §1 · p. 2

  • Method

    The paper proves an EG last-iterate upper bound under first- and second-order smoothness and establishes a lower bound using stationary CLI methods that include EG.

    Source: §1 · pp. 2–3, §3.1 · p. 7, §4.2 · p. 11

  • Results

    O(1/√T) is the tight last-iterate rate, versus O(1/T) for EG’s averaged iterates, giving a quadratic separation.

    Source: §1 · pp. 2–3

  • Takeaways & Limitations

    Last-iterate and averaged EG iterates have distinct convergence rates in smooth convex-concave saddle-point problems.

    Source: §1 · pp. 2–3

    Extending the lower bound, or proving a stronger upper bound, for algorithms with decaying step sizes remains future work.

    Source: §5 · p. 12

Abstract

from arXiv · show

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 $\Omega(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.

1. Introduction

For smooth convex-concave saddle-point problems, averaged EG iterates have an O(1/T) guarantee, but prior work had not established a last-iterate rate without strong convexity. This paper gives a tight O(1/√T) last-iterate rate, separating the two rates quadratically.

1. Introduction

  • Before this work, last-iterate convergence rates were known for strongly convex-strongly concave problems, but not for EG without strong convexity.Earlier convex-concave results established convergence, or rates for the best iterate, rather than a last-iterate rate.Source: §1 · p. 2
  • O(1/√T) is the EG last-iterate rate for monotone variational inequalities under first- and second-order smoothness, measured by either the square root of the Hamiltonian or the primal-dual gap.The introduction presents this as the first such guarantee for smooth convex-concave saddle-point problems.Source: §1 · p. 2
  • A tight Ω(1/√T) last-iterate lower bound yields a quadratic separation from EG’s O(1/T) averaged-iterate rate.The lower bound applies to stationary canonical linear iterative methods, including EG.Source: §1 · pp. 2–3

1.1. Related work

  • Prior last-iterate results cover special settings such as bilinear or sufficiently bilinear problems, while some related non-smooth convex-minimization methods require decaying step sizes.The paper distinguishes its setting from linear-rate results that rely on stronger structure or second-order methods.Source: §1.1 · p. 3
  • The lower-bound argument uses stationary CLI algorithms because averaging EG iterates can achieve O(1/T), and averaging must therefore be ruled out.The paper’s lower-bound framework is motivated by the fact that EG’s averaged iterates can be represented by a particular 2-CLI.Source: §1 · p. 2, §1.1 · p. 4

2. Preliminaries

The preliminaries set notation for the product domain and its associated operator, then define two measures of solution quality. In unconstrained problems, the primal-dual gap is evaluated on a compact region.

2. Preliminaries

  • Z denotes the product domain X × Y, and z denotes the concatenation (x, y); vector norms are Euclidean and matrix norms are spectral.The notation also defines gradients, positive-semidefinite ordering for symmetric matrices, and the diameter of Z.Source: §2 · p. 4
  • For convex-concave f, the associated operator F is monotone, and its variational inequality solution is equivalent to a global saddle point.The paper assumes f is twice differentiable.Source: §2 · p. 4
  • The Hamiltonian is the squared norm of f’s gradient and is zero at a global saddle point.It is one of the paper’s two measures of solution quality.Source: §2 · pp. 4–5
  • The primal-dual gap measures how much y fails to maximize f(x, ·) and x fails to minimize f(·, y).In the unconstrained setting the gap may be infinite over the full domain, so the paper uses a compact region, typically balls around the saddle point.Source: §2 · p. 5

3. Lower bound for first-order 1-SCLI algorithms

This section develops last-iterate lower bounds for first-order 1-SCLI algorithms using bilinear convex-concave problems. The bounds apply to constant-step EG and establish a quadratic convergence-rate gap between its last and averaged iterates.

3. Lower bound for first-order 1-SCLI algorithms

  • The lower-bound construction uses bilinear functions, which are convex-concave, to study first-order algorithms including EG.Source: §3 · p. 5, §3.1 · p. 7
  • The lower-bound setup takes the initial iterate to be zero without loss of generality, and uses D for the distance to the optimum and the gap-set radius.The same convention is used for the upper bounds.Source: §3 · pp. 5–6

3.1. 1-SCLI lower bound

  • Theorem 9 considers consistent 1-SCLI algorithms whose inversion matrix is a polynomial in the operator of degree at most k − 1.The paper notes that this polynomial-dependence assumption includes many known first-order 1-SCLI methods and is needed to rule out an algorithm that reaches the solution in one step.Source: §3.1 · p. 7
  • For EG with a constant step size, Theorem 9 establishes a quadratic gap in T between the convergence rates of averaged and last iterates; the excerpt provides the proof of item 1.Source: §3.1 · p. 8

4. Upper bound for extragradient

This section establishes last-iterate bounds for extragradient under smoothness assumptions, relates them to the proximal point algorithm, and outlines the proof strategy.

4. Upper bound for extragradient

  • Under monotonicity, Lipschitz continuity, and a Lipschitz derivative, Theorem 10 bounds the last iterate of extragradient and its primal-dual gap.The proof first finds an iterate with a small operator norm, then uses the Lipschitz derivative assumption to control later iterates.Source: §4 · p. 10, §4.2 · p. 11

4.1. Proximal point algorithm

  • The proximal point algorithm has an O(1/T) last-iterate rate even without the Lipschitz-derivative and Lipschitzness assumptions required for the extragradient bound.The cited proof relies on the operator norm decreasing monotonically.Source: §4.1 · p. 10

4.2. Proof of Theorem 10

  • The proof of Theorem 10 selects an iterate with small operator norm, then controls its increase at later steps using the Lipschitz derivative assumption.The final primal-dual-gap bound follows from the operator-norm bound and convex-concavity.Source: §4.2 · p. 11

5. Conclusion and Future Work

The conclusion gives an upper bound for EG's last-iterate primal-dual gap and identifies open questions about averaging and nonstationary algorithms.

5. Conclusion and Future Work

  • EG's Tth-iterate primal-dual gap is O(1/T), a bound shown tight among 1-SCLI algorithms and compared with the O(1/T) gap for averaged EG iterates.The authors identify the potential benefit of averaging in nonconvex-nonconcave problems as future work, noting experimental suggestions and its effectiveness in large-scale GANs.Source: §5 · p. 12
  • Extending Theorem 9's lower bound, or proving a stronger upper bound, for algorithms with decaying step sizes remains an open direction.The authors state that decaying EG step sizes cannot improve the Ω(1/√T) lower bound from Theorem 9.Source: §5 · pp. 12–13

A.1. Proof of items 2 and 3 of Theorem 9

This proof derives lower bounds by constructing a function and evaluating its primal-dual gap along the algorithm's iterates.

A.1. Proof of items 2 and 3 of Theorem 9

  • The proof computes the primal-dual gap on a bounded product domain using the construction chosen for the preceding lower-bound item.The construction's matrix and vector parameters depend on ν, and the proof evaluates the gap in a manner similar to its Hamiltonian calculation.Source: §A.1 · p. 17
  • The constructed function's extrema over x and y reduce to norms of affine expressions, which the proof uses to evaluate the gap.The expressions are D∥M⊤x + b2∥ and D∥My + b1∥, together written as D∥Az + b∥.Source: §A.1 · p. 17
  • The proof obtains the desired lower bound by combining its preceding inequalities with the normalization ∥A−1b∥ = D.The calculation treats convergence in function value after addressing the primal-dual gap.Source: §A.1 · p. 17

A.2. Supplementary lemmas for Theorem 9

The supplementary lemmas bound polynomials subject to degree and normalization constraints, supporting the paper's lower-bound analysis.

A.2. Supplementary lemmas for Theorem 9

  • Lemma 13 considers real-coefficient polynomials of degree at most k, normalized by r(0) = 1, for fixed k, t, and L.The proof describes its bound as improving the dependence on t relative to a result of Nemirovsky (1992, Section 2.3.B).Source: §A.2 · p. 19
  • Lemma 14 imposes the same polynomial normalization and degree bound, with L > μ > 0 and k ≤ L/μ − 1.The authors compare it with Azizian et al. (2019, Lemmas 5 & 12), claiming superior dependence on k and a simpler proof using similar techniques.Source: §A.2 · p. 19
  • The proof characterizes the Chebyshev polynomial of the first kind and uses its parity: odd degree gives an odd function, while even degree gives an even function.The parity follows from the stated characterization of Tk.Source: §A.2 · p. 19

A.3. Tightness of dependence on the degree k

This subsection establishes that the inverse dependence on degree k in the iteration-complexity bound is tight. It does so within a class of consistent 1-SCLI algorithms whose inversion matrices are polynomials in the operator.

A.3. Tightness of dependence on the degree k

  • The inverse dependence on k in Theorem 9’s iteration-complexity bound is tight.The proposition constructs a consistent 1-SCLI algorithm with an inversion matrix polynomial of degree at most k − 1.Source: §A.3 · p. 20
  • The proposition’s construction runs extragradient on a monotone linear operator F(z) = Az + b, initialized at zero with step size η = 1/(2L).The bounds are stated for bilinear-function operators to simplify notation, although the remark says they hold for any monotone linear operator.Source: §A.3 · p. 20
  • The proof represents the final iterate as the first iterate of a consistent 1-SCLI whose inversion matrix is polynomial in A.The displayed construction gives w(T) = N′(A)b, with N′ having degree at most 2T + 1 ≤ k − 1.Source: §A.3 · p. 21

Appendix B. Proofs of Lemmas 11 and 12

These appendix proofs collect preliminary inequalities and use smoothness and monotonicity properties of the operator Jacobian to establish Lemma 11.

B.1. Preliminary lemmas

  • For a monotone operator, the symmetric part of its Jacobian is positive semidefinite.The appendix states this as Lemma 16, citing Nesterov (2006).Source: §B.1 · p. 21
  • The preliminary proofs invoke scalar inequalities to derive bounds for vectors in R^n.The supplied proof passages use x² ≤ 2y² + 2(x − y)² and rs ≤ 2s² + 2(r − s)².Source: §B.1 · pp. 21–22

B.2. Proof of Lemma 11

  • The proof of Lemma 11 uses the fundamental theorem of calculus to relate operator values at shifted points.It also uses a Jacobian spectral-norm bound L and the assumption that F has a Λ-smooth Jacobian.Source: §B.2 · p. 22

B.3. Proof of Lemma 12

The proof of Lemma 12 bounds matrix expressions by decomposing matrices into symmetric and antisymmetric parts, then applies the resulting inequalities under a small-norm condition.

B.3. Proof of Lemma 12

  • The proof decomposes A and B into symmetric positive-semidefinite and antisymmetric parts before bounding their product.The symmetric parts are S and R; the antisymmetric parts are M and N.Source: §B.3 · p. 23
  • The proof combines auxiliary inequalities for the decomposed matrices with Lemmas 17 and 18.The displayed bounds apply for any ε > 0 and are used to control cross terms.Source: §B.3 · pp. 23–24
  • The argument completes with ε = 1/10 when L0 ≤ 1/30.Under that condition, the final displayed inequality is at most 2.Source: §B.3 · p. 24

Appendix C. Proof of Last Iterate convergence of Proximal Point

The appendix gives a last-iterate result for proximal point and presents two extragradient constructions: averaged iterates as a 2-CLI, and a lower-bound setup for time-varying step sizes.

Appendix C. Proof of Last Iterate convergence of Proximal Point

  • Lemma 19 supplies a monotonicity inequality used in the proximal-point proof.The appendix says Theorem 20’s proof follows readily from this lemma and prior results.Source: Appendix C · p. 25
  • For a monotone operator with a zero within distance D of the initialization, Theorem 20 gives a last-iterate guarantee for proximal point with any step size η > 0.For the specified product of balls and saddle-point operator, the theorem’s conclusion is expressed using the primal-dual gap.Source: Appendix C · p. 25

D.1. Averaged EG iterates are a 2-CLI with time-varying coefficients

  • Averaged extragradient iterates can be represented as a 2-CLI with time-varying coefficients.The section restricts to linear operators F(z) = Az + b to write the update in 2-CLI form.Source: §D.1 · p. 26

D.2. Lower bound for last iterate of EG with time-varying coefficients

  • Proposition 21 considers extragradient with arbitrary step sizes ηt in (0, 1/L) and states that a bilinear-function operator exists for this setting.The supplied proposition passage does not include the remainder of its conclusion.Source: §D.2 · p. 27
Loading 2002.00057v2…