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

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.

References in corpus (12)

• Stochastic Dual Coordinate Ascent Methods for Regularized Loss Minimization
• Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods
• Hybrid Block Successive Approximation for One-Sided Non-Convex Min-Max Problems: Algorithms and Applications
• Learning with Average Top-k Loss
• Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problems
• Stochastic AUC Maximization with Deep Neural Networks
• Decomposing Linearly Constrained Nonconvex Problems by a Proximal Primal Dual Approach: Algorithms, Convergence, and Applications
• Randomized First-Order Methods for Saddle Point Optimization
• Linear Convergence of the Primal-Dual Gradient Method for Convex-Concave Saddle Point Problems without Strong Convexity
• Frank-Wolfe Algorithms for Saddle Point Problems
• Gradient Primal-Dual Algorithm Converges to Second-Order Stationary Solutions for Nonconvex Distributed Optimization
• Exploiting Strong Convexity from Data with Primal-Dual First-Order Algorithms

Cited by in corpus (8)

• Accelerated Zeroth-Order and First-Order Momentum Methods from Mini to Minimax Optimization
• Training Robust Deep Models for Time-Series Domain: Novel Algorithms and Theoretical Analysis
• Stability and Generalization of Stochastic Gradient Methods for Minimax Problems
• Tighter Analysis of Alternating Stochastic Gradient Method for Stochastic Nested Problems
• Generalization Bounds for Stochastic Saddle Point Problems
• AdaGDA: Faster Adaptive Gradient Descent Ascent Methods for Minimax Optimization
• A New Primal-Dual Algorithm for a Class of Nonlinear Compositional Convex Optimization Problems
• Randomized Stochastic Gradient Descent Ascent