On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems

Abstract

We consider nonconvex-concave minimax problems, ${\min }_{\mathbf{x}}{\max }_{\mathbf{y}\in \mathcal{Y}}f(\mathbf{x},\mathbf{y})$, where $f$ is nonconvex in $\mathbf{x}$ but concave in $\mathbf{y}$ and $\mathcal{Y}$ is a convex and bounded set. One of the most popular algorithms for solving this problem is the celebrated gradient descent ascent (GDA) algorithm, which has been widely used in machine learning, control theory and economics. Despite the extensive convergence results for the convex-concave setting, GDA with equal stepsize can converge to limit cycles or even diverge in a general setting. In this paper, we present the complexity results on two-time-scale GDA for solving nonconvex-concave minimax problems, showing that the algorithm can find a stationary point of the function $\Phi (\cdot ):={\max }_{\mathbf{y}\in \mathcal{Y}}f(\cdot ,\mathbf{y})$ efficiently. To the best our knowledge, this is the first nonasymptotic analysis for two-time-scale GDA in this setting, shedding light on its superior practical performance in training generative adversarial networks (GANs) and other real applications.

Accepted by ICML 2020; 39 pages, 6 figures

References in corpus (12)

• GANs Trained by a Two Time-Scale Update Rule Converge to a Local Nash Equilibrium
• Robustness and Regularization of Support Vector Machines
• Distributionally Robust Logistic Regression
• A Variational Inequality Perspective on Generative Adversarial Networks
• A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approach
• The Mechanics of n-Player Differentiable Games
• 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
• Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile
• On Finding Local Nash Equilibria (and Only Local Nash Equilibria) in Zero-Sum Games
• On the Convergence and Robustness of Training GANs with Regularized Optimal Transport
• Efficient Algorithms for Smooth Minimax Optimization

Cited by in corpus (56)

• Game-Theoretic Multiagent Reinforcement Learning
• Hybrid Block Successive Approximation for One-Sided Non-Convex Min-Max Problems: Algorithms and Applications
• Non-convex Min-Max Optimization: Applications, Challenges, and Recent Theoretical Advances
• Robust Federated Learning: The Case of Affine Distribution Shifts
• GenDICE: Generalized Offline Estimation of Stationary Values
• Learning to Continuously Optimize Wireless Resource in a Dynamic Environment: A Bilevel Optimization Perspective
• Near-Optimal Algorithms for Minimax Optimization
• Conditional Sig-Wasserstein GANs for Time Series Generation
• Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problems
• Convergence of Learning Dynamics in Stackelberg Games
• A Decentralized Parallel Algorithm for Training Generative Adversarial Nets
• Global Convergence and Variance-Reduced Optimization for a Class of Nonconvex-Nonconcave Minimax Problems
• GANs May Have No Nash Equilibria
• Accelerated Zeroth-Order and First-Order Momentum Methods from Mini to Minimax Optimization
• An Optimal Transport Approach to Personalized Federated Learning
• Optimizing Two-way Partial AUC with an End-to-end Framework
• Towards Better Understanding of Adaptive Gradient Algorithms in Generative Adversarial Nets
• CoinDICE: Off-Policy Confidence Interval Estimation
• A Single-Loop Smoothed Gradient Descent-Ascent Algorithm for Nonconvex-Concave Min-Max Problems
• On Solving Minimax Optimization Locally: A Follow-the-Ridge Approach
• Communication-Efficient Distributed Stochastic AUC Maximization with Deep Neural Networks
• Zeroth-Order Algorithms for Nonconvex Minimax Problems with Improved Complexities
• Improved Algorithms for Convex-Concave Minimax Optimization
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning
• SGD Learns One-Layer Networks in WGANs
• Online and Bandit Algorithms for Nonstationary Stochastic Saddle-Point Optimization
• AlphaGAN: Fully Differentiable Architecture Search for Generative Adversarial Networks
• Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with $\mathcal{O}(1/k^2)$ Rate on Squared Gradient Norm
• Stability and Generalization of Stochastic Gradient Methods for Minimax Problems
• A Primal-Dual Smoothing Framework for Max-Structured Non-Convex Optimization
• Derivative-Free Policy Optimization for Linear Risk-Sensitive and Robust Control Design: Implicit Regularization and Sample Complexity
• Conditional Density Estimation, Latent Variable Discovery and Optimal Transport
• Hybrid Variance-Reduced SGD Algorithms For Nonconvex-Concave Minimax Problems
• Coping with Label Shift via Distributionally Robust Optimisation
• Distributionally Robust Deep Learning using Hardness Weighted Sampling
• Train simultaneously, generalize better: Stability of gradient-based minimax learners
• Gradient Free Minimax Optimization: Variance Reduction and Faster Convergence
• AdaGDA: Faster Adaptive Gradient Descent Ascent Methods for Minimax Optimization
• Nonconvex-Nonconcave Min-Max Optimization with a Small Maximization Domain
• Near Optimal Stochastic Algorithms for Finite-Sum Unbalanced Convex-Concave Minimax Optimization
• Forward Super-Resolution: How Can GANs Learn Hierarchical Generative Models for Real-World Distributions
• A Mathematical Framework for Learning Probability Distributions
• Minimax Problems with Coupled Linear Constraints: Computational Complexity, Duality and Solution Methods
• CDMA: A Practical Cross-Device Federated Learning Algorithm for General Minimax Problems
• Efficient Projection-Free Algorithms for Saddle Point Problems
• A New Primal-Dual Algorithm for a Class of Nonlinear Compositional Convex Optimization Problems
• Adversarial Monte Carlo Meta-Learning of Optimal Prediction Procedures
• Finding Second-Order Stationary Points in Nonconvex-Strongly-Concave Minimax Optimization
• Enhance Diffusion to Improve Robust Generalization
• On the Convergence Rate of Off-Policy Policy Optimization Methods with Density-Ratio Correction
• Making Method of Moments Great Again? -- How can GANs learn distributions
• Randomized Stochastic Gradient Descent Ascent
• Selective Classification via One-Sided Prediction
• FedMM: Saddle Point Optimization for Federated Adversarial Domain Adaptation
• Uncoupled Bandit Learning towards Rationalizability: Benchmarks, Barriers, and Algorithms
• Convex-Concave Min-Max Stackelberg Games