PaperlayerView exact revision on arXiv

Source-linked AI summary

On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems

Tianyi Lin, Chi Jin, Michael I. Jordan

arXiv:1906.00331v10cs.LGmath.OCstat.ML

TL;DR

The paper addresses whether simple two-time-scale GDA and SGDA can be analyzed efficiently for nonconvex-concave minimax problems, where equal-step GDA may cycle or diverge. It develops a slowly changing-objective analysis and establishes nonasymptotic complexity bounds for finding stationary points of Φ. The results provide guarantees for these widely used algorithms, while their optimality remains open.

  • Problem

    The paper asks whether two-time-scale GDA and SGDA have provable nonasymptotic efficiency for nonconvex-concave minimax problems.

  • Method

    The paper analyzes two-time-scale GDA and SGDA using a technique for concave optimization with a slowly changing objective.

  • Results

    Two-time-scale GDA and SGDA return ε-stationary points with O(κ^2ε^-2) and O(κ^3ε^-4) evaluations in the nonconvex-strongly-concave case, and O(ε^-6) and O(ε^-8) in the nonconvex-concave case.

  • Takeaways & Limitations

    Two-time-scale GDA and SGDA are provably efficient in the stated nonconvex-(strongly)-concave settings.

  • Takeaways & Limitations

    The paper does not claim optimality, and the optimal rate for nonconvex-(strongly)-concave optimization remains open.

Abstract

from arXiv · show

We consider nonconvex-concave minimax problems, $\min_{\mathbf{x}} \max_{\mathbf{y} \in \mathcal{Y}} f(\mathbf{x}, \mathbf{y})$, where $f$ is nonconvex in $\mathbf{x}$ but concave in $\mathbf{y}$ and $\mathcal{Y}$ is a convex and bounded set. One of the most popular algorithms for solving this problem is the celebrated gradient descent ascent (GDA) algorithm, which has been widely used in machine learning, control theory and economics. Despite the extensive convergence results for the convex-concave setting, GDA with equal stepsize can converge to limit cycles or even diverge in a general setting. In this paper, we present the complexity results on two-time-scale GDA for solving nonconvex-concave minimax problems, showing that the algorithm can find a stationary point of the function $Φ(\cdot) := \max_{\mathbf{y} \in \mathcal{Y}} f(\cdot, \mathbf{y})$ efficiently. To the best our knowledge, this is the first nonasymptotic analysis for two-time-scale GDA in this setting, shedding light on its superior practical performance in training generative adversarial networks (GANs) and other real applications.

1 Introduction

The paper studies nonconvex-concave minimax optimization and asks whether two-time-scale GDA and SGDA have efficient nonasymptotic guarantees. It develops an analysis for these unequal-stepsize methods despite the difficulty that the ascent iterate may not track the maximizer.

  • The problem minimizes over x and maximizes over y, with f nonconvex in x, concave in y, and Y convex.
  • GDA updates x by descent and y by ascent, using stepsizes ηx and ηy.
  • Equal-stepsize GDA has convergence guarantees in convex-concave settings but can exhibit limit cycles or divergence more generally.
  • Two-time-scale GDA uses unequal stepsizes and has empirical and local-asymptotic support, but its algorithmic efficiency lacked a nonasymptotic analysis.
  • The stated results give O(κ^2ε^-2) and O(κ^3ε^-4) evaluations in the nonconvex-strongly-concave setting, and O(ε^-6) and O(ε^-8) in the nonconvex-concave setting, for GDA and SGDA respectively.
  • The paper introduces a technique for analyzing concave optimization with a slowly changing objective because y_t need not remain close to the maximizer at each iteration.

2 Related Work

Related work develops several guarantees for nonconvex-concave minimax optimization, but many methods use nested loops or restrictive assumptions. The paper positions two-time-scale GDA and SGDA as simpler alternatives with nonasymptotic guarantees.

  • Nonconvex-concave minimax problems have become a focus in optimization and machine learning, including adversarial and robust learning.
  • PGSMD/PGSVRG find approximate stationary points of Φ, but their guarantees require linearity in y and their algorithms use nested loops.
  • MGDA, ProxDIAG, and inexact proximal point methods provide convergence guarantees, while the latter methods achieve rates such as O(ε^-3.5) and O(ε^-3).
  • HiBSA is a single-loop method, but its analysis requires restrictive assumptions including that f is lower bounded.
  • Nonconvex-nonconcave work studies notions of goodness, oscillation reduction, and faster gradient dynamics, with some guarantees relying on variational stability or the Minty condition.
  • Online-learning analyses assess no-regret properties and last-iterate convergence of game dynamics.

3 Preliminaries

The preliminaries define stationarity for the value function Φ and motivate a Moreau-envelope surrogate when Φ may be nonsmooth. They also specify the two-time-scale GDA and SGDA procedures and their robust-classifier interpretation.

  • The minimax problem is equivalent to minimizing Φ(x) = max_y∈Y f(x,y), but finding its global minimum is generally NP hard because Φ is nonconvex.
  • For differentiable Φ, an ε-stationary point satisfies ∥∇Φ(x)∥≤ε.
  • In general nonconvex-concave problems, Φ need not be differentiable, motivating weak convexity and subgradient-based stationarity.
  • Two-time-scale GDA updates x by gradient descent and y by projected gradient ascent, then returns a uniformly sampled iterate.
  • The Moreau-envelope definition yields an alternative stationarity measure based on a small gradient of Φ1/2ℓ.
  • The Moreau-envelope stationarity notion is motivated by robust classification, where x is the classifier and y is adversarial noise.

4 Main Results

The paper establishes nonasymptotic complexity guarantees for two-time-scale GDA and SGDA in nonconvex-strongly-concave and nonconvex-concave minimax settings. The guarantees target stationary points of Φ or its Moreau envelope under bounded, convex constraint sets.

  • Algorithmic setup: Two-time-scale GDA and SGDA use separate descent and ascent stepsizes, with ηx smaller than ηy to reflect the problem’s nonsymmetric min-max structure.Classical GDA and SGDA use equal stepsizes, whereas the analyzed methods use unequal stepsizes; practitioners may prefer faster convergence for the inner maximization.
  • Main technical contribution: The analysis introduces a technique for concave optimization with a slowly changing objective because yt need not remain close to the maximizer y⋆(xt).This addresses why ∇xf(xt, yt) is not automatically a reasonable descent direction at every iteration.
  • Guarantee scope and limitations: The guarantees concern visiting a stationary point and returning a uniformly sampled iterate, not necessarily the final iterate xT.For stochastic GDA, minibatch size M = Θ(ε^-2) is necessary for the stated convergence property; with M = 1, the bound worsens to O(κ^3ε^-5).
  • Nonconvex-concave setting: In the nonconvex-concave setting, GDA and SGDA find an ε-stationary point in terms of Moreau envelopes using O(ε^-6) gradient and O(ε^-8) stochastic gradient evaluations.Here Φ is potentially nondifferentiable but is ℓ-weakly convex and L-Lipschitz; SGDA allows minibatch size M = 1 under the stated theorem.
  • Guarantee scope and limitations: The paper provides basic guarantees for simple, widely used methods rather than claiming optimality; constructing optimal nonconvex-concave algorithms remains beyond its scope.Existing bounds of approximately Õ(ε^-3) use more complicated algorithmic schemes, while the optimal rate remains open.

5 Overview of Proofs

The proof uses two-time-scale stepsizes so the maximization variable tracks a slowly changing objective. Strong concavity enables tracking the unique maximizer, while concavity without uniqueness requires blockwise control of function-value errors.

  • Empirical context: The overview introduces the complexity analysis for two-timescale GDA and reports empirical comparisons using WRM figures at γ = 0.4 and γ = 1.3.The figures plot test classification accuracy against time on MNIST, Fashion-MNIST, and CIFAR-10.
  • Proof strategy: The analysis sets ηx smaller than ηy, making x_t move more slowly than y_t.This keeps the maximization problem changing gradually during ascent.
  • Strongly concave setting: In the strongly concave case, y⋆(·) is κ-Lipschitz, so slow x_t movement keeps y⋆(x_t) slowly changing.The resulting tracking error δ_t is controlled through a descent inequality and a contraction recursion.
  • Concave setting: In the merely concave case, y⋆(x) may be nonunique and change dramatically, making distance to a selected maximizer unsuitable as the tracking error.The analysis instead uses Δ_t = f(x_t, z) − f(x_t, y_t) for z ∈ y⋆(x_t).
  • Concave setting: The concave-case proof controls the accumulated Δ_t by partitioning iterations into blocks where the concave problems are similar.The block size is B = O(ε^2/ηx), enabling a telescoping argument with an additional function-value cost.

6 Experiments

The experiments train Wasserstein robustness models on three image datasets and compare two-timescale GDA with GDmax under two perturbation settings. The model uses a convolutional neural network and specified adversarial-penalty parameters.

  • Experimental setup: The experiments train empirical Wasserstein robustness models on MNIST, Fashion-MNIST, and CIFAR-10.The classifier uses convolutional filter layers with ELU activations, followed by a fully connected layer and softmax output.
  • Compared methods: The section presents empirical results comparing two-timescale GDA with GDmax for WRM training.The supplied setup specifies the datasets, architecture, perturbation parameters, and baseline configuration.
  • Experimental setup: The adversarial perturbation settings use γ ∈ {0.4, 1.3}, matching the settings of Sinha et al. (2018).These values represent small and large adversarial perturbations in the stated setup.
  • Compared methods: GDmax is denoted GDmA and uses ηx = ηy = 10^-3 with 20 gradient-ascent steps in each inner loop.Two-timescale GDA is evaluated against this nested-loop baseline.

7 Conclusion

The paper concludes that two-time-scale GDA and SGDA have finite complexity guarantees for finding ε-stationary points in both strongly concave and concave maximization settings.

  • Conclusion: O(κ^2ε^-2) gradient evaluations and O(κ^3ε^-4) stochastic gradient evaluations suffice in the nonconvex-strongly-concave case.Both algorithms return an ε-stationary point under the stated setting.
  • Conclusion: O(ε^-6) gradient evaluations and O(ε^-8) stochastic gradient evaluations suffice in the nonconvex-concave case.The conclusion identifies these as the complexity results for two-time-scale GDA and SGDA.
  • Conclusion: The paper characterizes the two algorithms as provably efficient in the stated settings.It identifies deriving first-order lower bounds for nonconvex-concave minimax problems as future work.

A.1 Proof of Lemma 3.6

The appendix establishes properties of the value function Φ and connects approximate stationarity of Φ to gradient-based solutions of the inner maximization problem.

  • Value-function properties: Danskin’s theorem gives Φ(x) = max_y f(x,y) a subgradient representation through ∇x f(x, y⋆(x)) in the relevant settings.The weak-convexity construction uses Ψ(x) = max_y {f(x,y) + (ℓ/2)||x||^2}.
  • Value-function properties: The Moreau envelope Φ_1/(2ℓ) is differentiable, and its gradient controls the distance from x to the proximal point x̂.The appendix states ||x̂ − x|| = ||∇Φ_1/(2ℓ)(x)||/(2ℓ).
  • Strongly concave case: Strong concavity makes y⋆(·) unique and κ-Lipschitz, supporting smoothness and differentiability properties of Φ.The appendix concludes that Φ is 2κℓ-smooth when κ ≥ 1.
  • Inner maximization: When ||∇Φ(x̂)|| ≤ ε, gradient descent on the strongly concave inner problem obtains an approximate maximizer using O(κ log(1/ε)) gradient evaluations.The corresponding stochastic-gradient procedure requires O(1/ε^2) stochastic gradient evaluations.

B.1 Proof of Proposition 4.13

The proof applies an extragradient method to a regularized strongly convex-concave problem and transfers approximate stationarity back to Φ.

  • Proof strategy: The regularized problem adds ℓ∥x−x̂∥2 to f and is assumed strongly convex in x and concave in y.The minimizer x⋆(x̂) is uniquely defined, and extragradient produces an approximate solution.
  • Proof strategy: The proof relates the regularized minimizer's displacement from x̂ to the gradient of the smoothed function Φ1/2ℓ.Specifically, 2ℓ∥x⋆(x̂)−x̂∥=∥∇Φ1/2ℓ(x̂)∥≤ε.
  • Proof strategy: The constructed y+ is obtained by projecting a gradient-ascent step from y′ onto Y.This projected update is used to bound the x-gradient at (x′,y+).
  • Proof strategy: The x-gradient at the constructed point is bounded by the extragradient error, the distance to x⋆(x̂), and the regularization displacement.The bound decomposes ∥∇xf(x′,y+)∥ into three terms.
  • Complexity: The required number of gradient evaluations is O(ε−2) for the deterministic argument and O(ε−4) stochastic gradient evaluations.The same argument is stated for stochastic mirror-prox.

C.1 Choice of Parameters in Theorem 4.4 and 4.5

This section fixes unequal x- and y-step sizes and develops the descent and tracking inequalities used to establish two-timescale GDA and SGDA complexity.

  • Parameter setup: The analysis specifies ηx, ηy, and batch-size choices before proving the main theorems.These parameters are stated as important for the subsequent analysis.
  • Parameter setup: ηx=1/[16(κ+1)2ℓ] and ηy=1/ℓ yield the deterministic GDA iteration and gradient complexity bound in Theorem C.1.The theorem states that Algorithm 1 returns an ε-stationary point under these stepsizes.
  • Parameter setup: The stochastic algorithm uses the same stepsizes and M=max{1,48κσ2ε−2}, with complexity O((κ2ℓΔΦ+κℓ2D2)ε−2).This is the total gradient complexity stated for Algorithm 2.
  • Proof ingredients: The proof tracks δt=∥y⋆(xt)−yt∥2 and its stochastic counterpart to control the maximizer-tracking error.The tracking analysis uses strong concavity and the κ-Lipschitz property of y⋆.
  • Complexity: The resulting bounds imply iteration complexities for Algorithms 1 and 2, each with the same total gradient complexity as its iteration bound.The deterministic and stochastic conclusions are stated separately after summing the inequalities.

D.1 Choice of Parameters in Theorem 4.9 and 4.10

For the nonconvex-concave setting, the section chooses ε-dependent unequal stepsizes and proves complexity through function-gap and maximizer-tracking recursions.

  • Parameter choices: The deterministic algorithm uses ηy=1/ℓ and ηx=min{ε2/[16ℓL2], ε4/[4096ℓ3L2D2]}.Under Assumption 4.7, these choices support an ε-stationary-point guarantee.
  • Parameter choices: The stochastic algorithm uses M=1, ηx=min{ε2/[16ℓ(L2+σ2)], ε4/[8192ℓ3D2L2+σ2]}, and ηy=min{1/2ℓ, ε2/[16ℓσ2]}.These parameters are stated under Assumptions 4.1 and 4.7.
  • Proof ingredients: The proof defines Δt=Φ(xt)−f(xt,yt) to measure the maximization gap and derives recursive inequalities for deterministic and stochastic updates.The recursions use concavity, smoothness, convexity of Y, and projected ascent.
  • Proof ingredients: The analysis partitions the iterates into blocks and combines function-gap recursions with proximal-gradient relations.This produces the bounds used to control the averaged stationarity measure.
  • Complexity: The resulting iteration bounds for Algorithms 1 and 2 also give their total gradient complexities.The deterministic and stochastic conclusions are stated after combining the preceding inequalities.

E Results for GDmax and SGDmax

GDmax and SGDmax replace simultaneous ascent with an approximate max-oracle, yielding explicit oracle-based guarantees for strongly concave and concave maximization.

  • Algorithms: GDmax performs one x-gradient step after approximately maximizing f(xt−1,·) over Y.The max-oracle returns a point whose objective is within ζ of the maximum.
  • Strongly concave case: In the nonconvex-strongly-concave setting, GDmax uses ηx=1/[8κℓ] and ζ=ε2/[6ℓ], with total complexity O(κ2ε−2 log(ℓ/ε)).The max-oracle is implemented by O(κ log(ℓD2/ζ)) gradient-ascent iterations.
  • Strongly concave case: The stochastic strongly concave result uses a batch size M=max{1,12κσ2ε−2} and a stochastic ascent max-oracle.The stated theorem retains the O(κℓΔΦε−2) iteration bound.
  • Concave case: When σ2≲ε2, SGDmax matches GDmax's gradient complexity because stochastic gradients are sufficiently close to true gradients.The comparison is explicitly stated for the stochastic nonconvex-concave setting.
  • Max-oracle guarantees: The strongly concave max-oracle returns ∥y⋆−y∥2≤ζ/ℓ after O(κ log(ℓD2/ζ)) gradient evaluations.The stochastic oracle uses a batch size depending on σ2, κ, ℓ, and ζ.
Loading 1906.00331v10…