Global Convergence and Variance-Reduced Optimization for a Class of Nonconvex-Nonconcave Minimax Problems

Abstract

Nonconvex minimax problems appear frequently in emerging machine learning applications, such as generative adversarial networks and adversarial learning. Simple algorithms such as the gradient descent ascent (GDA) are the common practice for solving these nonconvex games and receive lots of empirical success. Yet, it is known that these vanilla GDA algorithms with constant step size can potentially diverge even in the convex setting. In this work, we show that for a subclass of nonconvex-nonconcave objectives satisfying a so-called two-sided Polyak-Łojasiewicz inequality, the alternating gradient descent ascent (AGDA) algorithm converges globally at a linear rate and the stochastic AGDA achieves a sublinear rate. We further develop a variance reduced algorithm that attains a provably faster rate than AGDA when the problem has the finite-sum structure.

References in corpus (14)

• Towards Deep Learning Models Resistant to Adversarial Attacks
• Certifying Some Distributional Robustness with Principled Adversarial Training
• Stochastic Variance Reduction for Nonconvex Optimization
• On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems
• SBEED: Convergent Reinforcement Learning with Nonlinear Function Approximation
• What is Local Optimality in Nonconvex-Nonconcave Minimax Optimization?
• Gradient methods for convex minimization: better rates under weaker conditions
• Robust Optimization for Non-Convex Objectives
• Near-Optimal Algorithms for Minimax Optimization
• Stochastic Primal-Dual Methods and Sample Complexity of Reinforcement Learning
• Last-iterate convergence rates for min-max optimization
• First-order Convergence Theory for Weakly-Convex-Weakly-Concave Min-max Problems
• On the Global Convergence of Imitation Learning: A Case for Linear Quadratic Regulator
• A Stochastic Proximal Point Algorithm for Saddle-Point Problems

Cited by in corpus (20)

• Robust Federated Learning: The Case of Affine Distribution Shifts
• An Optimal Transport Approach to Personalized Federated Learning
• Accelerated Zeroth-Order and First-Order Momentum Methods from Mini to Minimax Optimization
• Minimax Estimation of Conditional Moment Models
• Complexity Lower Bounds for Nonconvex-Strongly-Concave Min-Max Optimization
• On the Impossibility of Global Convergence in Multi-Loss Optimization
• Derivative-Free Policy Optimization for Linear Risk-Sensitive and Robust Control Design: Implicit Regularization and Sample Complexity
• Hybrid Variance-Reduced SGD Algorithms For Nonconvex-Concave Minimax Problems
• A Decentralized Adaptive Momentum Method for Solving a Class of Min-Max Optimization Problems
• Near-optimal Local Convergence of Alternating Gradient Descent-Ascent for Minimax Optimization
• Gradient Free Minimax Optimization: Variance Reduction and Faster Convergence
• Limiting Behaviors of Nonconvex-Nonconcave Minimax Optimization via Continuous-Time Systems
• Gradient-free algorithm for saddle point problems under overparametrization
• Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity
• About some works of Boris Polyak on convergence of gradient methods and their development
• Minimax Problems with Coupled Linear Constraints: Computational Complexity, Duality and Solution Methods
• CDMA: A Practical Cross-Device Federated Learning Algorithm for General Minimax Problems
• Method with Batching for Stochastic Finite-Sum Variational Inequalities in Non-Euclidean Setting
• Towards Accurate Quantization and Pruning via Data-free Knowledge Transfer
• Minimax Optimization: The Case of Convex-Submodular