Accelerating Smooth Games by Manipulating Spectral Shapes

Abstract

We use matrix iteration theory to characterize acceleration in smooth games. We define the spectral shape of a family of games as the set containing all eigenvalues of the Jacobians of standard gradient dynamics in the family. Shapes restricted to the real line represent well-understood classes of problems, like minimization. Shapes spanning the complex plane capture the added numerical challenges in solving smooth games. In this framework, we describe gradient-based methods, such as extragradient, as transformations on the spectral shape. Using this perspective, we propose an optimal algorithm for bilinear games. For smooth and strongly monotone operators, we identify a continuum between convex minimization, where acceleration is possible using Polyak's momentum, and the worst case where gradient descent is optimal. Finally, going beyond first-order methods, we propose an accelerated version of consensus optimization.

arXiv commentAppears in: Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics (AISTATS 2020). 34 pages

References in corpus (9)

• Which Training Methods for GANs do actually Converge?
• The Numerics of GANs
• A Universal Catalyst for First-Order Optimization
• A Variational Inequality Perspective on Generative Adversarial Networks
• The Mechanics of n-Player Differentiable Games
• On Finding Local Nash Equilibria (and Only Local Nash Equilibria) in Zero-Sum Games
• On the Iteration Complexity of Oblivious First-Order Optimization Algorithms
• The Limit Points of (Optimistic) Gradient Descent in Min-Max Optimization
• Accelerated Schemes For A Class of Variational Inequalities

Cited by in corpus (11)

• Near-Optimal Algorithms for Minimax Optimization
• Explore Aggressively, Update Conservatively: Stochastic Extragradient Methods with Variable Stepsize Scaling
• Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problems
• Smooth Monotone Stochastic Variational Inequalities and Saddle Point Problems: A Survey
• A Unified Analysis of First-Order Methods for Smooth Games via Integral Quadratic Constraints
• Tight last-iterate convergence rates for no-regret learning in multi-player games
• Average-case Acceleration Through Spectral Density Estimation
• Optimality and Stability in Non-Convex Smooth Games
• Near-optimal Local Convergence of Alternating Gradient Descent-Ascent for Minimax Optimization
• Universal Average-Case Optimality of Polyak Momentum
• Complex Momentum for Optimization in Games