# Randomized Stochastic Gradient Descent Ascent

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 57 references that are in the map.
- First posted on arXiv 25 Nov 2021.

## Builds on (most cited first, 28 of 28)

- [Gaussian Error Linear Units (GELUs)](https://mlsanity.com/paper/1606.08415/) (2016)
- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Certifying Some Distributional Robustness with Principled Adversarial Training](https://mlsanity.com/paper/1710.10571/) (2017)
- [Learning Generative Models with Sinkhorn Divergences](https://mlsanity.com/paper/1706.00292/) (2017)
- [SGD: General Analysis and Improved Rates](https://mlsanity.com/paper/1901.09401/) (2019)
- [Stochastic Optimization for Large-scale Optimal Transport](https://mlsanity.com/paper/1605.08527/) (2016)
- [Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods](https://mlsanity.com/paper/1902.08297/) (2019)
- [Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron](https://mlsanity.com/paper/1810.07288/) (2018)
- [Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence](https://mlsanity.com/paper/2002.10542/) (2020)
- [Distributionally Robust Logistic Regression](https://mlsanity.com/paper/1509.09259/) (2015)
- [Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates](https://mlsanity.com/paper/1905.09997/) (2019)
- [Learning with minibatch Wasserstein : asymptotic and gradient properties](https://mlsanity.com/paper/1910.04091/) (2019)
- [Don't Jump Through Hoops and Remove Those Loops: SVRG and Katyusha are Better Without the Outer Loop](https://mlsanity.com/paper/1901.08689/) (2019)
- [A Single-Loop Smoothed Gradient Descent-Ascent Algorithm for Nonconvex-Concave Min-Max Problems](https://mlsanity.com/paper/2010.15768/) (2020)
- [Hybrid Block Successive Approximation for One-Sided Non-Convex Min-Max Problems: Algorithms and Applications](https://mlsanity.com/paper/1902.08294/) (2019)
- [On the Convergence and Robustness of Training GANs with Regularized Optimal Transport](https://mlsanity.com/paper/1802.08249/) (2018)
- [Stochastic Heavy Ball](https://mlsanity.com/paper/1609.04228/) (2016)
- [Accelerated Zeroth-Order and First-Order Momentum Methods from Mini to Minimax Optimization](https://mlsanity.com/paper/2008.08170/) (2020)
- [Variance Reduced Stochastic Gradient Descent with Neighbors](https://mlsanity.com/paper/1506.03662/) (2015)
- [An accelerated inexact proximal point method for solving nonconvex-concave min-max problems](https://mlsanity.com/paper/1905.13433/) (2019)
- [Semi-dual Regularized Optimal Transport](https://mlsanity.com/paper/1811.05527/) (2018)
- [Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning](https://mlsanity.com/paper/2008.10103/) (2020)
- [Proximal Gradient Descent-Ascent: Variable Convergence under KL Geometry](https://mlsanity.com/paper/2102.04653/) (2021)
- [On the Convergence of Stochastic Extragradient for Bilinear Games using Restarted Iteration Averaging](https://mlsanity.com/paper/2107.00464/) (2021)
- [Convergence of a Newton algorithm for semi-discrete optimal transport](https://mlsanity.com/paper/1603.05579/) (2016)
- [An Online Learning Approach to Generative Adversarial Networks](https://mlsanity.com/paper/1706.03269/) (2017)
- [Solving Non-Convex Non-Concave Min-Max Games Under Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1812.02878/) (2018)
- [On the Existence of Optimal Transport Gradient for Learning Generative Models](https://mlsanity.com/paper/2102.05542/) (2021)

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

- [Nest Your Adaptive Algorithm for Parameter-Agnostic Nonconvex Minimax Optimization](https://mlsanity.com/paper/2206.00743/) (2022)
- [TiAda: A Time-scale Adaptive Algorithm for Nonconvex Minimax Optimization](https://mlsanity.com/paper/2210.17478/) (2022)
- [Convergence of empirical subgradients for optimal transport-based objectives](https://mlsanity.com/paper/2605.28134/) (2026)

## Abstract (arXiv)

An increasing number of machine learning problems, such as robust or adversarial variants of existing algorithms, require minimizing a loss function that is itself defined as a maximum. Carrying a loop of stochastic gradient ascent (SGA) steps on the (inner) maximization problem, followed by an SGD step on the (outer) minimization, is known as Epoch Stochastic Gradient textitDescent Ascent (ESGDA). While successful in practice, the theoretical analysis of ESGDA remains challenging, with no clear guidance on choices for the inner loop size nor on the interplay between inner/outer step sizes. We propose RSGDA (Randomized SGDA), a variant of ESGDA with stochastic loop size with a simpler theoretical analysis. RSGDA comes with the first (among SGDA algorithms) almost sure convergence rates when used on nonconvex min/strongly-concave max settings. RSGDA can be parameterized using optimal loop sizes that guarantee the best convergence rates known to hold for SGDA. We test RSGDA on toy and larger scale problems, using distributionally robust optimization and single-cell data matching using optimal transport as a testbed.