Randomized Stochastic Gradient Descent Ascent

Abstract

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 \textit{Descent 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.

References in corpus (22)

• Gaussian Error Linear Units (GELUs)
• On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems
• Distributionally Robust Logistic Regression
• Stochastic Optimization for Large-scale Optimal Transport
• Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods
• SBEED: Convergent Reinforcement Learning with Nonlinear Function Approximation
• Hybrid Block Successive Approximation for One-Sided Non-Convex Min-Max Problems: Algorithms and Applications
• Sample Complexity of Sinkhorn divergences
• On the Convergence and Robustness of Training GANs with Regularized Optimal Transport
• Semi-dual Regularized Optimal Transport
• Efficient Algorithms for Smooth Minimax Optimization
• Optimal Epoch Stochastic Gradient Descent Ascent Methods for Min-Max Optimization
• Accelerated Zeroth-Order and First-Order Momentum Methods from Mini to Minimax Optimization
• A Single-Loop Smoothed Gradient Descent-Ascent Algorithm for Nonconvex-Concave Min-Max Problems
• Learning with minibatch Wasserstein : asymptotic and gradient properties
• An accelerated inexact proximal point method for solving nonconvex-concave min-max problems
• Solving Non-Convex Non-Concave Min-Max Games Under Polyak-Łojasiewicz Condition
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning
• Proximal Gradient Descent-Ascent: Variable Convergence under KŁ Geometry
• Almost sure convergence rates for Stochastic Gradient Descent and Stochastic Heavy Ball
• Tighter Analysis of Alternating Stochastic Gradient Method for Stochastic Nested Problems
• On the Existence of Optimal Transport Gradient for Learning Generative Models