What is Local Optimality in Nonconvex-Nonconcave Minimax Optimization?

Abstract

Minimax optimization has found extensive applications in modern machine learning, in settings such as generative adversarial networks (GANs), adversarial training and multi-agent reinforcement learning. As most of these applications involve continuous nonconvex-nonconcave formulations, a very basic question arises---"what is a proper definition of local optima?" Most previous work answers this question using classical notions of equilibria from simultaneous games, where the min-player and the max-player act simultaneously. In contrast, most applications in machine learning, including GANs and adversarial training, correspond to sequential games, where the order of which player acts first is crucial (since minimax is in general not equal to maximin due to the nonconvex-nonconcave nature of the problems). The main contribution of this paper is to propose a proper mathematical definition of local optimality for this sequential setting---local minimax, as well as to present its properties and existence results. Finally, we establish a strong connection to a basic local search algorithm---gradient descent ascent (GDA): under mild conditions, all stable limit points of GDA are exactly local minimax points up to some degenerate points.

arXiv commentThis paper has been published at ICML2020. This new version made a correction to Proposition 19, and added more related works

References in corpus (10)

• GANs Trained by a Two Time-Scale Update Rule Converge to a Local Nash Equilibrium
• Towards Deep Learning Models Resistant to Adversarial Attacks
• No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis
• Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods
• On Finding Local Nash Equilibria (and Only Local Nash Equilibria) in Zero-Sum Games
• Stochastic subgradient method converges at the rate $O(k^{-1/4})$ on weakly convex functions
• Convergence of Learning Dynamics in Stackelberg Games
• Local Saddle Point Optimization: A Curvature Exploitation Approach
• Negative Momentum for Improved Game Dynamics
• Finding Mixed Nash Equilibria of Generative Adversarial Networks

Cited by in corpus (43)

• Unsupervised Domain Adaptation through Self-Supervision
• Game-Theoretic Multiagent Reinforcement Learning
• Non-convex Min-Max Optimization: Applications, Challenges, and Recent Theoretical Advances
• Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problems
• Convergence of Learning Dynamics in Stackelberg Games
• Stochastic AUC Maximization with Deep Neural Networks
• Global Convergence and Variance-Reduced Optimization for a Class of Nonconvex-Nonconcave Minimax Problems
• Efficient Algorithms for Smooth Minimax Optimization
• GANs May Have No Nash Equilibria
• Accelerated Zeroth-Order and First-Order Momentum Methods from Mini to Minimax Optimization
• On Solving Minimax Optimization Locally: A Follow-the-Ridge Approach
• Min-Max Optimization without Gradients: Convergence and Applications to Adversarial ML
• A Single-Loop Smoothed Gradient Descent-Ascent Algorithm for Nonconvex-Concave Min-Max Problems
• Communication-Efficient Distributed Stochastic AUC Maximization with Deep Neural Networks
• Zeroth-Order Algorithms for Nonconvex Minimax Problems with Improved Complexities
• Implicit competitive regularization in GANs
• Rényi Fair Inference
• The limits of min-max optimization algorithms: convergence to spurious non-critical sets
• SGD Learns One-Layer Networks in WGANs
• Local Stochastic Gradient Descent Ascent: Convergence Analysis and Communication Efficiency
• A Unified Analysis of First-Order Methods for Smooth Games via Integral Quadratic Constraints
• Newton-type Methods for Minimax Optimization
• Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Games
• On Tilted Losses in Machine Learning: Theory and Applications
• Online and Bandit Algorithms for Nonstationary Stochastic Saddle-Point Optimization
• On the Suboptimality of Negative Momentum for Minimax Optimization
• Delta-STN: Efficient Bilevel Optimization for Neural Networks using Structured Response Jacobians
• Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with $\mathcal{O}(1/k^2)$ Rate on Squared Gradient Norm
• A Decentralized Adaptive Momentum Method for Solving a Class of Min-Max Optimization Problems
• Regret minimization in stochastic non-convex learning via a proximal-gradient approach
• Generative Minimization Networks: Training GANs Without Competition
• Optimality and Stability in Non-Convex Smooth Games
• Tractable contextual bandits beyond realizability
• Minimax Dynamics of Optimally Balanced Spiking Networks of Excitatory and Inhibitory Neurons
• High-Dimensional Robust Mean Estimation via Gradient Descent
• Majorized Semi-proximal Alternating Coordinate Method for Nonsmooth Convex-Concave Minimax Optimization
• NCVX: A User-Friendly and Scalable Package for Nonconvex Optimization in Machine Learning
• A Limited-Capacity Minimax Theorem for Non-Convex Games or: How I Learned to Stop Worrying about Mixed-Nash and Love Neural Nets
• Optimality Conditions for Constrained Minimax Optimization
• Imitation with Neural Density Models
• Pure Characteristics Demand Models and Distributionally Robust Mathematical Programs with Stochastic Complementarity Constraints
• Robust MIMO Radar Waveform-Filter Design for Extended Target Detection in the Presence of Multipath
• Zeroth-Order Methods for Convex-Concave Minmax Problems: Applications to Decision-Dependent Risk Minimization