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 (3)

• Robust Optimization for Non-Convex Objectives
• Stochastic Primal-Dual Methods and Sample Complexity of Reinforcement Learning
• On the Global Convergence of Imitation Learning: A Case for Linear Quadratic Regulator

Cited by in corpus (6)

• Robust Federated Learning: The Case of Affine Distribution Shifts
• Minimax Estimation of Conditional Moment Models
• Complexity Lower Bounds for Nonconvex-Strongly-Concave Min-Max Optimization
• A Decentralized Adaptive Momentum Method for Solving a Class of Min-Max Optimization Problems
• Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity
• Minimax Optimization: The Case of Convex-Submodular