# A Stochastic GDA Method With Backtracking For Solving Nonconvex Concave Minimax Problems

arXiv: https://arxiv.org/abs/2403.07806 · HTML: https://mlsanity.com/paper/2403.07806/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Mar 2024.

## Built on by (most cited first, 6 of 6)

- [Enhance Image-to-Image Generation with LLaVA-generated Prompts](https://mlsanity.com/paper/2406.01956/) (2024)
- [Data Augmentation Through Random Style Replacement](https://mlsanity.com/paper/2504.10563/) (2025)
- [Anomaly Detection and Early Warning Mechanism for Intelligent Monitoring Systems in Multi-Cloud Environments Based on LLM](https://mlsanity.com/paper/2506.07407/) (2025)
- [Completely Parameter-Free Single-Loop Algorithms for Nonconvex-Concave Minimax Problems](https://mlsanity.com/paper/2407.21372/) (2024)
- [An Intelligent Fault Self-Healing Mechanism for Cloud AI Systems via Integration of Large Language Models and Deep Reinforcement Learning](https://mlsanity.com/paper/2506.07411/) (2025)
- [Safe and Adaptive Cloud Healing: Verifying LLM-Generated Recovery Plans with a Neural-Symbolic World Model](https://mlsanity.com/paper/2607.01595/) (2026)

## Abstract (arXiv)

We propose a stochastic GDA (gradient descent ascent) method with backtracking (SGDA-B) to solve nonconvex-concave (NCC) minimax problems of the form: minx maxy sumi=1N gi(xi)+f(x,y)-h(y), where h and gi for i=1,cdots,N are closed, convex functions, and for some L,μ≥ 0, f is L-smooth and f(x,·) is μ-strongly concave for all x in the problem domain. We consider the stochastic setting where one only has an access to an unbiased stochastic oracle of nabla f with a finite variance bound σ2. While most of the existing methods assume knowledge of L, μ and/or σ2, SGDA-B is agnostic to all of these problem parameters. Moreover, SGDA-B can support random block-coordinate updates. In the deterministic setting, i.e., σ2=0 and one can compute nabla f exactly, SGDA-B can compute an ε-stationary point within O(Lkappa2/ε2) and O(L3/ε4) gradient calls when μ>0 and μ=0, respectively, where kappatriangleq L/μ. In the stochastic setting, i.e., σ2>0, for any p∈(0,1) and ε>0, it can compute an ε-stationary point with high probability, which requires O(L kappa3 ε-4 log2(1/p)) and tildeO(L4ε-7log2(1/p)) stochastic oracle calls, with probability at least 1-p, when μ>0 and μ=0, respectively. To our knowledge, SGDA-B is the first GDA-type method with backtracking to solve NCC minimax problems and achieves the best complexity among the methods that are agnostic to L, μ and σ2. We also provide numerical results for SGDA-B on a distributionally robust learning problem illustrating the potential performance gains that can be achieved by SGDA-B.