# Optimal Epoch Stochastic Gradient Descent Ascent Methods for Min-Max Optimization Source: [Optimal Epoch Stochastic Gradient Descent Ascent Methods for Min-Max Optimization]() Collection index: [llms.txt]() Data updated: 2025-10-25T14:31:44.072Z Authors: Yan Yan, Yi Xu, Qihang Lin, Wei Liu, Tianbao Yang Published: 2020-02-13T02:16:57.000Z ## Abstract 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. ## 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. - [Fairness Classification (Attractive label) on CelebA (test)](): Fairness classification (Attractive label); CelebA (test); pAUC: 0.8546. - [Fairness Classification (Big Nose label) on CelebA (test)](): Fairness classification (Big Nose label); CelebA (test); pAUC: 0.8023. ## Original sources and implementation [Original paper]() [PDF]()