On the Suboptimality of Negative Momentum for Minimax Optimization

• URL: http://arxiv.org/abs/2008.07459v4
• Date: Tue, 26 Jan 2021 17:26:55 GMT
• Title: On the Suboptimality of Negative Momentum for Minimax Optimization
• Authors: Guodong Zhang, Yuanhao Wang
• Abstract summary: We show that negative momentum accelerates convergence of game dynamics locally, though with a suboptimal rate. This is the first work that provides an explicit convergence rate momentum in this setting.
• Score: 9.400440302623839
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Rapid Learning in Constrained Minimax Games with Negative Momentum [5.086470864936883]
  We introduce a novel framework for momentum buffer updating, which extends the findings of negative momentum from the unconstrained setting to the constrained setting. Experimental results on both Normal Form Games (NFGs) and Extensive Form Games (EFGs) demonstrate that our momentum techniques can significantly improve algorithm performance.
  arXiv  Detail & Related papers  (2024-12-31T16:32:51Z)
• On the Convergence of No-Regret Learning Dynamics in Time-Varying Games [89.96815099996132]
  We characterize the convergence of optimistic gradient descent (OGD) in time-varying games. Our framework yields sharp convergence bounds for the equilibrium gap of OGD in zero-sum games. We also provide new insights on dynamic regret guarantees in static games.
  arXiv  Detail & Related papers  (2023-01-26T17:25:45Z)
• Finding mixed-strategy equilibria of continuous-action games without gradients using randomized policy networks [83.28949556413717]
  We study the problem of computing an approximate Nash equilibrium of continuous-action game without access to gradients. We model players' strategies using artificial neural networks. This paper is the first to solve general continuous-action games with unrestricted mixed strategies and without any gradient information.
  arXiv  Detail & Related papers  (2022-11-29T05:16:41Z)
• Momentum Doesn't Change the Implicit Bias [36.301490759243876]
  We analyze the implicit bias of momentum-based optimization. We construct new Lyapunov functions as a tool to analyze the gap between the model parameter and the max-margin solution.
  arXiv  Detail & Related papers  (2021-10-08T04:37:18Z)
• Online Multiobjective Minimax Optimization and Applications [14.699969822572308]
  We introduce a simple but general online learning framework, in which an adaptive adversary introduces a new game. The learner's goal is to play so as to minimize the maximum coordinate of the cumulative vector-valued loss. We give a simple algorithm that can compete with the setting in which the adversary must announce their action first. This includes no regret learning: we can recover optimal algorithms and bounds for minimizing external regret, internal regret, adaptive regret, multigroup regret, subsequence regret, and a notion of regret in the sleeping experts setting.
  arXiv  Detail & Related papers  (2021-08-09T06:52:08Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  We propose a new algorithm for the min-player against smooth algorithms deployed by an adversary. Our algorithm is guaranteed to make monotonic progress having no limit cycles, and to find an appropriate number of gradient ascents.
  arXiv  Detail & Related papers  (2021-06-02T22:03:36Z)
• Complex Momentum for Learning in Games [42.081050296353574]
  We generalize gradient descent with momentum for learning in differentiable games to have complex-valued momentum. We empirically demonstrate that complex-valued momentum can improve convergence in games - like generative adversarial networks. We also show a practical generalization to a complex-valued Adam variant, which we use to train BigGAN to better scores on CIFAR-10.
  arXiv  Detail & Related papers  (2021-02-16T19:55:27Z)
• Chaos, Extremism and Optimism: Volume Analysis of Learning in Games [55.24050445142637]
  We present volume analyses of Multiplicative Weights Updates (MWU) and Optimistic Multiplicative Weights Updates (OMWU) in zero-sum as well as coordination games. We show that OMWU contracts volume, providing an alternative understanding for its known convergent behavior. We also prove a no-free-lunch type of theorem, in the sense that when examining coordination games the roles are reversed: OMWU expands volume exponentially fast, whereas MWU contracts.
  arXiv  Detail & Related papers  (2020-05-28T13:47:09Z)
• Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium [116.56359444619441]
  We develop provably efficient reinforcement learning algorithms for two-player zero-sum finite-horizon Markov games. In the offline setting, we control both players and aim to find the Nash Equilibrium by minimizing the duality gap. In the online setting, we control a single player playing against an arbitrary opponent and aim to minimize the regret.
  arXiv  Detail & Related papers  (2020-02-17T17:04:16Z)
• Accelerating Smooth Games by Manipulating Spectral Shapes [51.366219027745174]
  We use matrix iteration theory to characterize acceleration in smooth games. We describe gradient-based methods, such as extragradient, as transformations on the spectral shape. We propose an optimal algorithm for bilinear games.
  arXiv  Detail & Related papers  (2020-01-02T19:21:48Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.