# Faster Single-loop Algorithms for Minimax Optimization without Strong Concavity

Source: [Faster Single-loop Algorithms for Minimax Optimization without Strong Concavity](<https://www.sota2.com/research/paper/68fa58c51e209131ce9b1478>)

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

Data updated: 2025-10-25T15:31:34.021Z

Authors: Junchi Yang, Antonio Orvieto, Aurelien Lucchi, Niao He

Published: 2021-12-10T15:35:42.000Z

## Abstract

Gradient descent ascent (GDA), the simplest single-loop algorithm for nonconvex minimax optimization, is widely used in practical applications such as generative adversarial networks (GANs) and adversarial training. Albeit its desirable simplicity, recent work shows inferior convergence rates of GDA in theory even assuming strong concavity of the objective on one side. This paper establishes new convergence results for two alternative single-loop algorithms -- alternating GDA and smoothed GDA -- under the mild assumption that the objective satisfies the Polyak-Lojasiewicz (PL) condition about one variable. We prove that, to find an $\\epsilon$-stationary point, (i) alternating GDA and its stochastic variant (without mini batch) respectively require $O(\\kappa^{2} \\epsilon^{-2})$ and $O(\\kappa^{4} \\epsilon^{-4})$ iterations, while (ii) smoothed GDA and its stochastic variant (without mini batch) respectively require $O(\\kappa \\epsilon^{-2})$ and $O(\\kappa^{2} \\epsilon^{-4})$ iterations. The latter greatly improves over the vanilla GDA and gives the hitherto best known complexity results among single-loop algorithms under similar settings. We further showcase the empirical efficiency of these algorithms in training GANs and robust nonlinear regression.

## 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: -4.

## Original sources and implementation

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

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