Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problems

Abstract

We consider nonconvex-concave minimax optimization problems of the form ${\min }_{\mathbf{x}}{\max }_{\mathbf{y}\in \mathcal{Y}}f(\mathbf{x},\mathbf{y})$, where $f$ is strongly-concave in $\mathbf{y}$ but possibly nonconvex in $\mathbf{x}$ and $\mathcal{Y}$ is a convex and compact set. We focus on the stochastic setting, where we can only access an unbiased stochastic gradient estimate of $f$ at each iteration. This formulation includes many machine learning applications as special cases such as robust optimization and adversary training. We are interested in finding an $\mathcal{O}(\epsilon )$-stationary point of the function $\Phi (\cdot )={\max }_{\mathbf{y}\in \mathcal{Y}}f(\cdot ,\mathbf{y})$. The most popular algorithm to solve this problem is stochastic gradient decent ascent, which requires $\mathcal{O}({\kappa }^3{\epsilon }^{-4})$ stochastic gradient evaluations, where $\kappa$ is the condition number. In this paper, we propose a novel method called Stochastic Recursive gradiEnt Descent Ascent (SREDA), which estimates gradients more efficiently using variance reduction. This method achieves the best known stochastic gradient complexity of $\mathcal{O}({\kappa }^3{\epsilon }^{-3})$, and its dependency on $\epsilon$ is optimal for this problem.

References in corpus (13)

• On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems
• Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods
• Non-convex Finite-Sum Optimization Via SCSG Methods
• Hybrid Block Successive Approximation for One-Sided Non-Convex Min-Max Problems: Algorithms and Applications
• Multi-Agent Reinforcement Learning via Double Averaging Primal-Dual Optimization
• SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient
• A Simple Proximal Stochastic Gradient Method for Nonsmooth Nonconvex Optimization
• What is Local Optimality in Nonconvex-Nonconcave Minimax Optimization?
• A Simple Practical Accelerated Method for Finite Sums
• Reducing Noise in GAN Training with Variance Reduced Extragradient
• Efficient Algorithms for Smooth Minimax Optimization
• A Stochastic Proximal Point Algorithm for Saddle-Point Problems
• Towards More Efficient Stochastic Decentralized Learning: Faster Convergence and Sparse Communication

Cited by in corpus (13)

• Accelerated Zeroth-Order and First-Order Momentum Methods from Mini to Minimax Optimization
• Optimal Epoch Stochastic Gradient Descent Ascent Methods for Min-Max Optimization
• Zeroth-Order Algorithms for Nonconvex Minimax Problems with Improved Complexities
• Lower Complexity Bounds of Finite-Sum Optimization Problems: The Results and Construction
• Provably Faster Algorithms for Bilevel Optimization
• Hybrid Variance-Reduced SGD Algorithms For Nonconvex-Concave Minimax Problems
• AdaGDA: Faster Adaptive Gradient Descent Ascent Methods for Minimax Optimization
• Near Optimal Stochastic Algorithms for Finite-Sum Unbalanced Convex-Concave Minimax Optimization
• CDMA: A Practical Cross-Device Federated Learning Algorithm for General Minimax Problems
• Finding Second-Order Stationary Points in Nonconvex-Strongly-Concave Minimax Optimization
• Federated Deep AUC Maximization for Heterogeneous Data with a Constant Communication Complexity
• FedMM: Saddle Point Optimization for Federated Adversarial Domain Adaptation
• On the Convergence Rate of Off-Policy Policy Optimization Methods with Density-Ratio Correction