On the Suboptimality of Negative Momentum for Minimax Optimization
arXiv:2008.07459
Abstract
Smooth game optimization has recently attracted great interest in machine learning as it generalizes the single-objective optimization paradigm. However, game dynamics is more complex due to the interaction between different players and is therefore fundamentally different from minimization, posing new challenges for algorithm design. Notably, it has been shown that negative momentum is preferred due to its ability to reduce oscillation in game dynamics. Nevertheless, the convergence rate of negative momentum was only established in simple bilinear games. In this paper, we extend the analysis to smooth and strongly-convex strongly-concave minimax games by taking the variational inequality formulation. By connecting momentum method with Chebyshev polynomials, we show that negative momentum accelerates convergence of game dynamics locally, though with a suboptimal rate. To the best of our knowledge, this is the \emph{first work} that provides an explicit convergence rate for negative momentum in this setting.
arXiv commentAISTATS 2021
References in corpus (16)
- Unsupervised Representation Learning with Deep Convolutional Generative Adversarial Networks
- The Numerics of GANs
- A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approach
- SBEED: Convergent Reinforcement Learning with Nonlinear Function Approximation
- On Finding Local Nash Equilibria (and Only Local Nash Equilibria) in Zero-Sum Games
- What is Local Optimality in Nonconvex-Nonconcave Minimax Optimization?
- Stochastic Variance Reduction Methods for Policy Evaluation
- Near-Optimal Algorithms for Minimax Optimization
- Convergence of Learning Dynamics in Stackelberg Games
- Differentiable Game Mechanics
- GANs May Have No Nash Equilibria
- On the Iteration Complexity of Oblivious First-Order Optimization Algorithms
- Improved Algorithms for Convex-Concave Minimax Optimization
- A Unified Analysis of First-Order Methods for Smooth Games via Integral Quadratic Constraints
- Average-case Acceleration Through Spectral Density Estimation
- Optimality and Stability in Non-Convex Smooth Games