PaperlayerView exact revision on arXiv

Source-linked AI summary

Fast Extra Gradient Methods for Smooth Structured Nonconvex-Nonconcave Minimax Problems

Sucheol Lee, Donghwan Kim

arXiv:2106.02326v3math.OC

TL;DR

Smooth structured nonconvex-nonconcave minimax problems arise in applications including generative adversarial networks and adversarial training. This paper introduces FEG and establishes an accelerated squared-gradient-norm rate under Lipschitz continuity and negative comonotonicity.

  • Problem

    Smooth nonconvex-nonconcave minimax problems arise in generative adversarial networks and adversarial training, motivating study in optimization and machine learning.

    Source: §1 · p. 1

  • Method

    The paper develops FEG, a two-time-scale anchored extragradient method, plus FEG-A for unavailable parameters and stochastic S-FEG.

    Source: §1 · pp. 2–3, §5 · p. 6, §6 · p. 8

  • Results

    FEG achieves an O(1/k^2) squared-gradient-norm rate under Lipschitz continuity and negative comonotonicity, while S-FEG has an O(1/k^2) + O(ϵ) expected rate when noise variance decreases as O(ϵ/k).

    Source: §1 · p. 2

  • Takeaways & Limitations

    FEG-A adaptively uses backtracking line search when the global Lipschitz and comonotonicity parameters are unavailable.

    Source: §1 · p. 3, §5 · pp. 6–7

    S-FEG's stochastic error accumulates unless noise variance decreases at O(1/k); constant variance yields O(k) error accumulation.

    Source: §6 · p. 8

Abstract

from arXiv · show

Modern minimax problems, such as generative adversarial network and adversarial training, are often under a nonconvex-nonconcave setting, and developing an efficient method for such setting is of interest. Recently, two variants of the extragradient (EG) method are studied in that direction. First, a two-time-scale variant of the EG, named EG+, was proposed under a smooth structured nonconvex-nonconcave setting, with a slow $\mathcal{O}(1/k)$ rate on the squared gradient norm, where $k$ denotes the number of iterations. Second, another variant of EG with an anchoring technique, named extra anchored gradient (EAG), was studied under a smooth convex-concave setting, yielding a fast $\mathcal{O}(1/k^2)$ rate on the squared gradient norm. Built upon EG+ and EAG, this paper proposes a two-time-scale EG with anchoring, named fast extragradient (FEG), that has a fast $\mathcal{O}(1/k^2)$ rate on the squared gradient norm for smooth structured nonconvex-nonconcave problems; the corresponding saddle-gradient operator satisfies the negative comonotonicity condition. This paper further develops its backtracking line-search version, named FEG-A, for the case where the problem parameters are not available. The stochastic analysis of FEG is also provided.

1 Introduction

The introduction motivates efficient methods for smooth structured nonconvex-nonconcave minimax problems, where EG+ was known to converge slowly and fast anchored EG results concerned convex-concave problems. It introduces FEG and variants that extend the fast-rate analysis to the target setting and address unavailable parameters and stochastic gradients.

1 Introduction

  • The target problems arise in applications including generative adversarial networks and adversarial training.Source: §1 · p. 1
  • EG+ was the only known explicit method for the considered setting and had an O(1/k) squared-gradient rate, while EAG’s O(1/k^2) rate was studied for convex-concave problems.The paper focuses on negative comonotonicity for Lipschitz-continuous operators.Source: §1 · p. 2
  • FEG combines two-time-scale extragradient with anchoring and achieves an O(1/k^2) squared-gradient rate under Lipschitz continuity and negative comonotonicity.The paper describes this as the first accelerated method under the nonconvex-nonconcave setting.Source: §1 · pp. 1–2
  • For smooth convex-concave problems, FEG’s rate bound is about 27/4 times smaller than EAG’s and about four times larger than the O(1/k^2) first-order lower bound.For cocoercive operators, FEG also has a faster rate than a version of Halpern iteration.Source: §1 · p. 2
  • FEG-A uses backtracking line search to adaptively estimate problem parameters locally when global parameters are unavailable, while preserving the O(1/k^2) squared-gradient rate.The global Lipschitz and comonotonicity parameters can be conservative and are often unknown in practice.Source: §1 · p. 2
  • S-FEG uses an unbiased stochastic estimate of the saddle-gradient operator and is analyzed in expected squared-gradient norm for Lipschitz-continuous monotone operators.Its reported stable rate is O(1/k^2) + O(ϵ) when noise variance decreases at O(ϵ/k); otherwise, error accumulation makes it unstable.Source: §1 · pp. 2–3

2 Related work

FEG is presented as the first method with an O(1/k^2) squared-gradient-norm rate for smooth structured nonconvex-nonconcave problems. Earlier work developed fast rates for convex-concave problems, while nonconvex-nonconcave methods had O(1/k) rates.

2.1 Methods for convex-concave minimax problems

  • For convex-concave problems, extragradient-type methods achieve O(1/k) rates in squared gradient norm, a measure the paper says remains improvable.The duality-gap O(1/k) rate is order-optimal, unlike the squared-gradient-norm rate.Source: §2.1 · p. 3
  • Anchoring methods, including EAG, attain O(1/k^2) squared-gradient-norm rates for smooth convex-concave problems.Anchoring combines the initial point with the latest iterate at each iteration.Source: §2.1 · p. 3

2.2 Methods for nonconvex-nonconcave minimax problems

  • FEG is presented as the first method with an O(1/k^2) squared-gradient-norm rate under the nonconvex-nonconcave setting.Table 1 summarizes rates for extragradient-type methods under differing assumptions on the saddle-gradient operator.Source: §2.2 · p. 4, Table 1 · p. 4
  • Earlier nonconvex-nonconcave extragradient methods achieved O(1/k) squared-gradient-norm rates under MVI or weak MVI conditions, the latter implied by negative comonotonicity.The paper identifies EG+ as an O(1/k) method under weak MVI and thus negative comonotonicity.Source: §2.2 · p. 4

3 Preliminaries

The preliminaries specify assumptions for methods that seek first-order stationary points and distinguish operator conditions by their comonotonicity parameter. The section then previews FEG’s comparison with existing methods across three cases.

3 Preliminaries

  • The methods target first-order stationary points of the saddle-gradient operator under two main assumptions, whose details are not stated in this passage.A stationary point is specified as z* with F z* = 0.Source: §3 · p. 4
  • The ρ-comonotonicity cases are negative comonotonicity for ρ < 0, monotonicity for ρ = 0, and cocoercivity for ρ > 0.The paper focuses on negative comonotonicity, which it describes as weaker than the other two cases.Source: §3 · p. 4
  • An interaction-dominant condition with α ≥ 0 is presented as a nonconvex-nonconcave condition stronger than negative comonotonicity.The passage also states that γ-weakly-convex-weakly-concave functions satisfy the condition with α = −γ < 0.Source: §3 · pp. 4–5
  • The section previews comparisons in which FEG outperforms EG+, EAG, and Halpern iteration across the three comonotonicity cases.The passage does not give the individual comparison results.Source: §3 · p. 5

4 Fast extragradient (FEG) method for Lipschitz continuous and comonotone operators

FEG combines two-time-scale extragradient updates with anchoring to obtain an O(1/k^2) squared-gradient-norm rate for Lipschitz continuous comonotone operators. The section compares its guarantees with EG+, EAG, and Halpern iteration, then illustrates behavior on a toy nonconvex-nonconcave example.

4 Fast extragradient (FEG) method for Lipschitz continuous and comonotone operators

  • FEG has an O(1/k^2) squared-gradient-norm rate for L-Lipschitz continuous ρ-comonotone operators when ρ > −1/(2L).The section states this result for any solution z* of F.Source: §4 · p. 5

4.1 Comparison to EG+ under the negative comonotonicity (ρ < 0)

  • FEG improves on EG+’s O(1/k) rate under negative comonotonicity, with a wider stated region of convergence.EG+ is given an O(1/k) rate for −1/(8L) < ρ < 0; the FEG comparison cites a wider region, −1/(2L) < ρ < 0.Source: §4.1 · p. 5

4.2 Comparison to EAG under the monotonicity (ρ = 0)

  • For ρ = 0, FEG’s rate bound has constant 4, about 260/4-times and 27/4-times faster than EAG-C and EAG-V, respectively.The bound is about four times the first-order lower complexity bound, reducing the upper–lower bound gap from 27 to 4.Source: §4.2 · p. 6

4.3 Comparison to the Halpern iteration under the cocoercivity (ρ > 0)

  • FEG’s rate is slower than Halpern iteration in gradient computations generally, but faster when L < 1/(2ρ).For the restricted case, the passage states FEG is faster even by number of gradient computations.Source: §4.3 · p. 6

4.4 Toy example

  • In the toy example, FEG converges at an accelerated rate while EG+, EAG-C, EAG-V, and explicit Halpern iteration diverge.The example is presented as showing that the cited convex-concave convergence and acceleration guarantees do not generalize to the nonconvex-nonconcave setting.Source: §4.4 · p. 6

5 FEG with backtracking line-search

FEG-A uses backtracking line search to adapt FEG’s step parameters when global problem parameters are unavailable or conservative. The section states that its step sizes remain positively bounded and that it retains a fast squared-gradient-norm rate under the stated condition.

5 FEG with backtracking line-search

  • FEG-A adaptively decreases its step sizes to meet local Lipschitz-continuity and comonotonicity conditions.The line search updates τ and η; the method is intended for cases where global parameters are difficult to compute or unknown.Source: §5 · pp. 6–7
  • FEG-A’s step-size sequences have positive lower bounds, so the method is well-defined under the stated condition ρ > −τk/2.The passages also state that the local Lipschitz parameter can be smaller than the global L.Source: §5 · p. 7
  • FEG-A retains an O(1/k^2) squared-gradient-norm rate under the stated condition ρ > −τk/2.The stated bound reduces to FEG’s bound for τ−1 = 1/L and η0 = 1/L + 2ρ.Source: §5 · p. 7

6 FEG under stochastic setting

S-FEG applies a stochastic saddle-gradient oracle to the fast extragradient method. Its stated analysis assumes independent, unbiased noise with bounded second moments, and notes that noise must decrease to avoid accumulation.

6 FEG under stochastic setting

  • S-FEG uses noisy saddle-gradient estimates with independent, zero-mean errors and second moments σ²k/2.The section introduces the stochastic method for smooth convex-concave problems.Source: §6 · p. 8
  • The analysis provides an upper bound on S-FEG’s expected squared gradient norm for L-Lipschitz continuous monotone operators.The theorem applies to any solution z* of F under the stated stochastic-oracle assumptions.Source: §6 · p. 8
  • If stochastic error variance is constant, S-FEG’s error accumulates at O(k); variance must decrease at O(1/k) to avoid accumulation.The passage says the variance at the queried points must decrease at this order.Source: §6 · p. 8

7 Convergence analysis with nonincreasing potential lemma

The convergence analysis establishes a nonincreasing potential function and uses it to derive FEG’s convergence rate. The potential approach is also identified as the basis of related EAG and Halpern analyses.

7 Convergence analysis with nonincreasing potential lemma

  • The analysis uses a potential Vk = ak∥F zk∥² − bk⟨F zk, z0 − zk⟩ for FEG and gives a similar lemma for S-FEG.The passage connects this potential-function approach to analyses of EAG and Halpern iteration [6].Source: §7 · p. 8

Then the potential function

  • Under the lemma’s parameter and operator conditions, the defined potential satisfies Vk ≤ Vk−1 for all k ≥ 1.The potential coefficients are specified in the section, with the sequences and conditions stated in the preceding passages.Source: §7 · pp. 8–9, Then the potential function · p. 9

7.1 Convergence analysis for FEG

  • For FEG, the proof specializes the lemma to αk = 1/L, βk = 1/(k+1), and ρk = ρ, then derives the rate by bounding the potential and dividing by k².The proof uses ρ-comonotonicity to bound ⟨F zk, z0 − z*⟩ by ∥F zk∥∥z0 − z*∥.Source: §7.1 · p. 9

8 Discussion: first-order methods for Lipschitz continuous operators

The discussion constructs a smooth Lipschitz example where every class-A method starting at the origin retains a nonzero squared gradient norm. It concludes that convergence for arbitrary smooth problems cannot be guaranteed by this method class.

8 Discussion: first-order methods for Lipschitz continuous operators

  • The example places every class-A sequence from (0, 0) on the line x = y.Figure 3 depicts this constraint for L = R = 1.Source: Figure 3 · p. 10, §8 · p. 10
  • ∥F z_k∥² = 2LR for every iterate of any class-A method from (0, 0) on the constructed example.The example's saddle-gradient operator is Lipschitz continuous but not comonotone.Source: §8 · p. 10
  • The lemma implies that guaranteeing a stationary point for every smooth problem requires considering methods outside class A.The authors leave that search for future work.Source: §8 · pp. 9–10
  • The authors also leave finding weaker sufficient conditions than weak MVI or negative comonotonicity for future work.The passage specifies a restriction on the negative-comonotonicity parameter but is incomplete.Source: §8 · p. 10

9 Conclusion

The conclusion presents FEG as an accelerated method for smooth structured nonconvex-nonconcave problems, alongside adaptive and stochastic variants. It identifies broader settings and applications as future work.

9 Conclusion

  • FEG achieves an O(1/k^2) squared-gradient-norm rate for Lipschitz continuous, negative-comonotone operators in the considered setting.The paper describes this as the first such accelerated rate for that setting.Source: §9 · p. 10
  • FEG-A provides a backtracking line-search version, while S-FEG is studied for smooth convex-concave problems.The conclusion does not claim the stochastic analysis for the nonconvex-nonconcave setting.Source: §9 · p. 10
  • Extending the work to stochastic, composite, or more general nonconvex-nonconcave problems and applying it to more realistic problems remain future work.Source: §9 · p. 10

A.1 Proof of Example 1

The appendix proof material introduces the saddle envelope and its operator, records iterates for a second example, and points to an algorithmic description of FEG-A.

A.1 Proof of Example 1

  • The proof of Example 1 introduces the saddle envelope fη and its saddle-gradient operator Fη.The supplied passage states that Fη is strongly monotone.Source: §A.1 · p. 14

B.1 Proof of Example 2

  • The proof of Example 2 starts from z0 = (1, 0), gives iterates through z2 = (0, 1), and proceeds by induction.The listed iterate fragments continue with an eight-iterate sequence.Source: §B.1 · p. 14

C.1 A detailed description of FEG-A

  • Algorithm 4 provides a detailed description of FEG-A, the adaptive-step-size fast extragradient method.Source: §C.1 · p. 15

C.2 Proof of Lemma 5.1

These appendix sections give proof details for adaptive step-size bounds, the deterministic FEG rate, and the stochastic analysis. The supplied fragments specify assumptions and intermediate bounds rather than a complete account of each proof.

C.2 Proof of Lemma 5.1

  • The FEG-A line search tests operator differences against step-size-scaled iterate differences and updates its search indices when the tests fail.The proof establishes positive lower bounds for τ_k and η_k under its stated setup.Source: §C.2 · pp. 15–16

D.1 Proof of Lemma 7.1

  • The deterministic analysis tracks a potential combining the squared gradient norm with its alignment against z0 − z_k.Source: §C.3 · p. 16, §D.1 · p. 17

C.3 Proof of Theorem 5.1

  • The deterministic FEG proof gives ∥F z_k∥ ≤ 2∥z0 − z*∥ / ((k − 1)η_k + τ_k + 2ρ), using ρ-comonotonicity to bound the inner product by k∥F z_k∥∥z0 − z*∥.Source: §C.3 · p. 16

D.2 Convergence analysis for S-FEG

  • The S-FEG analysis assumes an L-Lipschitz, monotone operator and independent zero-mean noise with specified variance at each iterate.Its potential bound includes terms depending on the noise variances.Source: §D.2 · p. 19

D.3 Proof of Theorem 6.1

  • The theorem proof imposes noise-variance bounds of order ε/k for the iterates and intermediate estimates.The supplied proof fragment does not state the resulting bound.Source: §D.3 · p. 23

Related papers

Loading 2106.02326v3…