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

Source: [Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problems](<https://www.sota2.com/research/paper/68fa57721e209131ce9a55fb>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2025-10-25T14:43:29.035Z

Authors: Luo Luo, Haishan Ye, Zhichao Huang, Tong Zhang

Published: 2020-01-11T09:05:03.000Z

## Abstract

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.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

- [Stochastic Minimax Optimization on Theoretical Analysis](<https://www.sota2.com/research/sota/stochastic-minimax-optimization-on-theoretical-analysis.md>): Stochastic Minimax Optimization; Theoretical Analysis; Sample Complexity: -3.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/2001.03724>)

[PDF](<https://arxiv.org/pdf/2001.03724.pdf>)