PaperlayerView exact revision on arXiv

Source-linked AI summary

Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problems

Luo Luo, Haishan Ye, Zhichao Huang, Tong Zhang

arXiv:2001.03724v2cs.LGmath.OCstat.ML

TL;DR

Stochastic nonconvex-strongly-concave minimax optimization seeks approximate stationary points when the objective is possibly nonconvex in x and strongly concave in y. SREDA recursively estimates gradients with variance reduction and a concave maximizer on y. It achieves O(κ^3ε^-3) stochastic gradient complexity, with optimal dependency on ε.

  • Problem

    The paper studies how to find an O(ε)-stationary point of Φ in stochastic minimax problems that are possibly nonconvex in x and strongly concave in y.

    Source: §1 · p. 1

  • Method

    SREDA recursively tracks a variance-reduced gradient estimator and uses stochastic variance-reduced gradient ascent with a concave maximizer on y.

    Source: §1 · p. 2, §4.1 · p. 5

  • Results

    O(κ^3ε^-3) stochastic gradient evaluations achieve an O(ε)-stationary point, with the ε-dependency optimal and the complexity better than state-of-the-art algorithms.

    Source: §4.2 · p. 6, §7 · p. 9

  • Takeaways & Limitations

    The paper presents SREDA as the first stochastic algorithm attaining optimal dependency on ε for this minimax setting.

    Source: Broader Impact · p. 9

    The complexity’s optimality with respect to κ remains unknown.

    Source: §7 · p. 9

Abstract

from arXiv · show

We consider nonconvex-concave minimax optimization problems of the form $\min_{\bf x}\max_{\bf y\in{\mathcal Y}} f({\bf x},{\bf y})$, where $f$ is strongly-concave in $\bf y$ but possibly nonconvex in $\bf x$ and ${\mathcal Y}$ is a convex and compact set. We focus on the stochastic setting, where we can only access an unbiased stochastic gradient estimate of $f$ at each iteration. This formulation includes many machine learning applications as special cases such as robust optimization and adversary training. We are interested in finding an ${\mathcal O}(\varepsilon)$-stationary point of the function $\Phi(\cdot)=\max_{\bf y\in{\mathcal Y}} f(\cdot, {\bf y})$. The most popular algorithm to solve this problem is stochastic gradient decent ascent, which requires $\mathcal O(\kappa^3\varepsilon^{-4})$ stochastic gradient evaluations, where $\kappa$ is the condition number. In this paper, we propose a novel method called Stochastic Recursive gradiEnt Descent Ascent (SREDA), which estimates gradients more efficiently using variance reduction. This method achieves the best known stochastic gradient complexity of ${\mathcal O}(\kappa^3\varepsilon^{-3})$, and its dependency on $\varepsilon$ is optimal for this problem.

1 Introduction

The paper studies stochastic minimax problems with a possibly nonconvex objective in x and strong concavity in y, targeting approximate stationary points of the maximized objective. It proposes SREDA, which recursively estimates gradients using variance reduction to reduce stochastic gradient complexity.

1 Introduction

  • The setting generalizes convex-concave minimax problems and includes applications such as regularized empirical risk minimization, AUC maximization, robust optimization, adversarial training, and reinforcement learning.Source: §1 · p. 1
  • The target is an approximate stationary point of Φ because its possible nonconvexity makes finding a global minimum infeasible in general.Source: §1 · p. 1
  • Prior deterministic and finite-sum methods do not cover this paper’s stochastic setting, while the comparison reports a sharper result than Minimax PPA for n > κ^2.Source: §1 · p. 2
  • SREDA uses recursive variance reduction and a multi-step concave maximizer on y to balance learning rates, batch sizes, and iteration counts across x and y.The method targets an O(ε)-stationary point of Φ.Source: §1 · p. 2
  • O(κ^3ε^-3) stochastic gradient evaluations give SREDA the best-known upper bound and optimal dependency on ε for this problem.The paper relates the ε-dependency to the O(ε^-3) lower bound for general nonconvex stochastic first-order algorithms [6].Source: §1 · p. 2

2 Notation and Preliminaries

The preliminaries state assumptions and notation for the stochastic minimax setting, then define stationarity and tools for handling the constraint on y.

2 Notation and Preliminaries

  • The analysis assumes a lower-bounded Φ, average Lipschitz gradients, concavity of each component in y, strong concavity of f in y, and bounded component-gradient variance.Source: §2 · pp. 2–3
  • Under Lipschitz-gradient and strong-concavity assumptions, Φ has a Lipschitz gradient and the maximizing response y*(·) is unique.Source: §2 · p. 3
  • The goal is an O(ε)-stationary point in expectation, defined by a gradient norm ∥∇Φ(x)∥₂ ≤ O(ε).Source: §2 · p. 3
  • Projection onto Y and the y-gradient mapping provide notation for addressing the constraint on the maximization variable.Source: §2 · p. 3

3 Related Work

Related work covers stochastic algorithms for nonconvex-strongly-concave minimax problems and variance-reduction methods developed for optimization and saddle-point settings.

3.1 Nonconvex-Strongly-Concave Minimax

  • SGDmax uses a nested max-oracle loop and requires O(κ^3ε^-4 log(1/ε)) stochastic gradient evaluations; SGDA avoids the nested loop with O(κ^3ε^-4) complexity.Both approaches update y more frequently than x, through repeated ascent or a larger y learning rate.Source: §3.1 · pp. 3–4

3.2 Variance Reduction Techniques

  • SARAH and SPIDER estimate gradients recursively; SPIDER achieves O(ε^-3) complexity for nonconvex optimization, matching the lower bound [6].Source: §3.2 · p. 4
  • Prior variance-reduced minimax methods mainly address convex-concave settings, including finite-sum strongly-convex-strongly-concave problems with linear convergence.The cited examples extend SVRG and SAGA [9].Source: §3.2 · p. 4

4 Algorithms and Main Results

SREDA combines recursive gradient estimation with a multi-step concave maximizer to find an O(ε)-stationary point of the stochastic nonconvex-strongly-concave minimax objective. The section establishes O(κ^3ε^-3) stochastic gradient complexity, an optimal ε-dependence, and an extension to the finite-sum case.

4.1 Stochastic Recursive Gradient Descent Ascent

  • SREDA recursively tracks gradient estimates and uses stochastic variance-reduced ascent within a multi-step concave maximizer to update y.The method seeks both accurate gradients at (x_k, y_k) and a small y-gradient mapping so f(x_k, y_k) approximates Φ(x_k).Source: §4.1 · pp. 5–6
  • PiSARAH initializes y0 to the desired accuracy with O(κ^2ε^-2 log(κ/ε)) gradient evaluations.It extends inexact SARAH to the constrained case.Source: §4.1 · p. 5
  • Each period starts with a batch of S1 = O(κ^2ε^-2) samples, followed by recursive updates using S2 = O(κε^-1) samples.The concave maximizer uses inner step size λ = O(1/ℓ) to keep the y-gradient mapping small without dramatic changes to y.Source: §4.1 · pp. 5–6

4.2 Complexity Analysis

  • Choosing q = O(ε^-1) balances large-batch evaluations against concave-maximizer iterations and their smaller batches.The stated evaluation count combines initialization, large batches every q iterations, and concave maximization at each outer iteration.Source: §4.2 · p. 6
  • E||∇Φ(ˆx)||² ≤ 1504ε with O(κ^3ε^-3) stochastic gradient evaluations; this is SREDA’s stated guarantee.The parameter choices also yield K = O(κε^-2) outer iterations.Source: §4.2 · p. 6
  • The ε^-3 dependence is optimal: a separable objective reduces the minimax problem to stochastic nonconvex minimization, which requires at least O(ε^-3) evaluations.The construction uses f(x, y) = g(x) + h(y), with g nonconvex and h strongly concave.Source: §4.2 · pp. 6–7

4.3 Extension to Finite-sum Case

  • For finite-sum problems with n ≥ κ^2, SREDA requires only minor modifications and is more efficient than Minimax PPA.The finite-sum version replaces selected stochastic-gradient steps with full gradients and uses PSARAH for initialization.Source: §4.3 · p. 7

5 Sketch of Proofs

The proof tracks changes in f(x_k, y_k) and its gradient rather than directly tracking Φ(x_k) and the distance to the maximizing y. It bounds the objective decrease and the gap to Φ, then relates the gradient estimate to stationarity.

5 Sketch of Proofs

  • The analysis uses f(x_k, y_k) and its gradient instead of directly tracking Φ(x_k) and ||y_k − y*(x_k)||².This contrasts with Lin et al.’s analysis of SGDA [25].Source: §5 · p. 8
  • The proof splits each iteration’s change in f into A_k, which decreases f, and B_k, which measures the gap between f(x_{k+1}, y_{k+1}) and Φ(x_{k+1}).In expectation, E[A_k] ≤ −O(κ^-1ε) and E[B_k] ≤ O(κ^-1ε²/ℓ).Source: §5 · p. 8
  • An O(ε)-accurate estimate of E||∇Φ(x_k)||² by E||v_k||² yields an output with E||∇Φ(ˆx)||² ≤ O(ε) and O(κ^3ε^-3) evaluations.The same proof idea is also used for Theorem 2.Source: §5 · p. 8

6 Numerical Experiments

The experiments evaluate SREDA and baseline algorithms on six real-world datasets for distributionally robust optimization. Figure 1 tracks the gradient norm of the objective against epochs.

6 Numerical Experiments

  • Experiments compare SREDA with GDAmax, GDA, SGDA, and Minimax PPA on six real-world datasets.The datasets are a9a, w8a, gisette, mushrooms, sido0, and rcv1.Source: §6 · p. 8
  • The algorithms use tuned step sizes and step-size ratios; stochastic methods also use tuned mini-batch sizes.SREDA uses the finite-sum version with q = m = ⌈n/S2⌉ heuristically.Source: §6 · p. 8
  • Figure 1 plots ∥∇Φ(x)∥2 against epochs for the DRO model across the six datasets and the compared algorithms.Table 2 is identified as a summary of the datasets used in the experiments.Source: Figure 1 · p. 9, Table 2 · p. 9

7 Conclusion

The conclusion presents SREDA for stochastic nonconvex-strongly-concave minimax problems and reports its stochastic gradient complexity. It also identifies unresolved questions about condition-number dependence and extension beyond strong concavity.

7 Conclusion

  • SREDA finds an O(ε)-stationary point of Φ with stochastic gradient complexity O(κ^3ε^-3), optimal in its dependency on ε.The paper reports this complexity as better than state-of-the-art algorithms.Source: §7 · p. 9
  • SREDA also applies to the finite-sum case and performs well when n is larger than κ^2.Source: §7 · p. 9
  • Whether SREDA's complexity is optimal with respect to κ remains unknown, and extending it to problems without strong concavity is an open question.Source: §7 · p. 9

Broader Impact

The broader impact section frames SREDA as a theoretical contribution to stochastic minimax optimization. The technical tools section gathers inequalities and results used in the analysis.

Broader Impact

  • The paper presents SREDA as the first stochastic algorithm with optimal dependency on ε and suggests applying it to more machine-learning applications.It says the result helps understanding minimax optimization without a convex-concave assumption.Source: Broader Impact · p. 9

A Technical Tools

  • The technical tools include inequalities from convex optimization, martingale variance bounds, and gradient mapping.Source: A Technical Tools · p. 13
  • For convex and compact C, projection is nonexpansive: the distance between projected points is at most the distance between their inputs.Source: A Technical Tools · p. 13
  • Lemma 5 introduces a gradient mapping for a function with an ℓ-Lipschitz gradient over a convex set.Source: A Technical Tools · p. 13

B Some Results of Concave Maximizer

The concave-maximizer analysis bounds two auxiliary quantities and relates their progress across iterations. It also provides a bound on the gradient-mapping magnitude after an epoch of iterations on y.

B Some Results of Concave Maximizer

C Initialization via Projected Inexact SARAH

The section introduces PiSARAH as an initialization method for a constrained stochastic convex minimization problem and analyzes its gradient-mapping convergence and evaluation cost.

C Initialization via Projected Inexact SARAH

  • The setup assumes compact convex C, convex component functions, a μ-strongly-convex objective, average ℓ-Lipschitz gradients, and bounded component-gradient variance.The condition number is defined as κ = μ/ℓ.Source: C Initialization via Projected Inexact… · pp. 20–21
  • PiSARAH is proposed for problem (15), with each epoch analyzed through ConcaveMaximizer applied to −g(·).The initialization is framed as a stochastic constrained convex minimization (concave maximization) problem.Source: C Initialization via Projected Inexact… · pp. 20–21
  • The inner-loop estimator recursively updates its gradient estimate using paired stochastic gradients evaluated at consecutive iterates.After the inner loop, the next iterate is selected uniformly from the loop iterates.Source: C Initialization via Projected Inexact… · p. 21
  • PiSARAH initialization targets a gradient-mapping bound of O(κ^-2ε^2) with O(κ^2ε^-2 log(κ/ε)) stochastic gradient evaluations.The section describes this initialization as aiming to keep the gradient mapping no larger than O(κ^-2ε^2).Source: C Initialization via Projected Inexact… · p. 22

D The Proof of Theorem 1

The proof analyzes changes in f and the y-gradient mapping, then extends the argument to finite-sum and initialization settings and treats two n-regimes.

D The Proof of Theorem 1

  • Theorem 1’s proof splits each iteration’s objective change into A_k, the function-value decrease, and B_k, the gap between f(x_{k+1}, y_{k+1}) and Φ(x_{k+1}).The analysis focuses on f(x_k,y_k) and the gradient mapping with respect to y rather than directly on Φ(x_k) and the distance to y*(x_k).Source: D The Proof of Theorem 1 · p. 23

E The proof of Theorem 2

  • For Theorem 2’s finite-sum case, full gradients replace the stochastic case’s large-batch sample, and constrained SARAH initializes y_0.The proof is described as requiring minor modifications to Theorem 1’s analysis.Source: E The proof of Theorem 2 · p. 26

E.1 Initialization by Projected SARAH

  • Projected SARAH is used to initialize y_0 by solving a convex optimization problem with an average-smooth convex component and a strongly convex objective.The passage introduces a convergence result for this initialization procedure but does not state its bound in the supplied text.Source: §E.1 · p. 27

E.2 The case of n ≥κ2

  • E||∇Φ(ˆx)||² ≤ 1504ε is also obtained in the n ≥ κ² case under the stated parameter setting.The passage introduces the total stochastic-gradient evaluation complexity but does not provide its expression.Source: §E.2 · p. 28

E.3 The case of n ≤κ2

  • E||∇Φ(ˆx)||² ≤ 1504ε is obtained in the n ≤ κ² case by setting q = 1, which makes Δ_k zero and tightens intermediate bounds.The section says the remaining proof follows Theorem 1's analysis.Source: §E.3 · p. 28
Loading 2001.03724v2…