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

By Luo Luo, Haishan Ye, Tong Zhang. 2020

145 citations recorded by the source corpus.

We consider nonconvex-concave minimax problems of the form $\min_{\bf x}\max_{\bf y} f({\bf x},{\bf y})$, where $f$ is strongly-concave in $\bf y$ but possibly nonconvex in $\bf x$. 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 adversary training and certifying robustness in deep learning. We are interested in finding an ${\mathcal O}(\varepsilon)$-stationary point of the function $\Phi(\cdot)=\max_{\bf 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.

Subfields: Artificial Intelligence, Computational Mechanics, Statistics and Probability, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Statistics and Probability

In Optimization & Training

Citations in the corpus

Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity (2021, background): “, 2021) or bounded variance (Juditsky et al., 2011; Yang et al., 2020; Lin et al., 2020a; Luo et al., 2020; Tran Dinh et al., 2020) and growth condition (Lin et al.”
AUC Maximization in the Era of Big Data and AI: A Survey (2022, background): “An improved complexity of O (1/ε(3)) is achieved in several recent works under the Lipschitz continuous assumption for the stochastic gradient ∇wF (w,α ; z) and ∇α F (w,α ; z) [75, 107], which is a stronger condition than the smoothness condition of the objective function.”
Global Convergence and Variance-Reduced Optimization for a Class of Nonconvex-Nonconcave Minimax Problems (2020, background): “We point out that Luo et al. [2020] recently introduced a variance-reduced algorithm for ﬁnding the stationary point of nonconvex-strongly-concave problems, which is again diﬀerent from our setting.”
Hybrid Variance-Reduced SGD Algorithms For Minimax Problems with Nonconvex-Linear Function (2020, methodology): “Moreover, our algorithm has only a single loop compared to [21, 43].”