# Optimal Epoch Stochastic Gradient Descent Ascent Methods for Min-Max Optimization

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Feb 2020.

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

- [AdaGDA: Faster Adaptive Gradient Descent Ascent Methods for Minimax Optimization](https://mlsanity.com/paper/2106.16101/) (2021)
- [Learning Distributionally Robust Models at Scale via Composite Optimization](https://mlsanity.com/paper/2203.09607/) (2022)
- [Single-Loop Stochastic Algorithms for Difference of Max-Structured Weakly Convex Functions](https://mlsanity.com/paper/2405.18577/) (2024)

## Abstract (arXiv)

Epoch gradient descent method (a.k.a. Epoch-GD) proposed by Hazan and Kale (2011) was deemed a breakthrough for stochastic strongly convex minimization, which achieves the optimal convergence rate of O(1/T) with T iterative updates for the it objective gap. However, its extension to solving stochastic min-max problems with strong convexity and strong concavity still remains open, and it is still unclear whether a fast rate of O(1/T) for the it duality gap is achievable for stochastic min-max optimization under strong convexity and strong concavity. Although some recent studies have proposed stochastic algorithms with fast convergence rates for min-max problems, they require additional assumptions about the problem, e.g., smoothness, bi-linear structure, etc. In this paper, we bridge this gap by providing a sharp analysis of epoch-wise stochastic gradient descent ascent method (referred to as Epoch-GDA) for solving strongly convex strongly concave (SCSC) min-max problems, without imposing any additional assumption about smoothness or the function's structure. To the best of our knowledge, our result is the first one that shows Epoch-GDA can achieve the optimal rate of O(1/T) for the duality gap of general SCSC min-max problems. We emphasize that such generalization of Epoch-GD for strongly convex minimization problems to Epoch-GDA for SCSC min-max problems is non-trivial and requires novel technical analysis. Moreover, we notice that the key lemma can also be used for proving the convergence of Epoch-GDA for weakly-convex strongly-concave min-max problems, leading to a nearly optimal complexity without resorting to smoothness or other structural conditions.