mlsanityData to 7 Oct 2026

Constants of Motion: The Antidote to Chaos in Optimization and Game Dynamics

arXiv 2109.03974 ↗First posted 8 Sep 2021math.OC cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

Several recent works in online optimization and game dynamics have established strong negative complexity results including the formal emergence of instability and chaos even in small such settings, e.g., 2× 2 games. These results motivate the following question: Which methodological tools can guarantee the regularity of such dynamics and how can we apply them in standard settings of interest such as discrete-time first-order optimization dynamics? We show how proving the existence of invariant functions, i.e., constant of motions, is a fundamental contribution in this direction and establish a plethora of such positive results (e.g. gradient descent, multiplicative weights update, alternating gradient descent and manifold gradient descent) both in optimization as well as in game settings. At a technical level, for some conservation laws we provide an explicit and concise closed form, whereas for other ones we present non-constructive proofs using tools from dynamical systems.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 32 of its 56 references that are in the map. First posted on arXiv 8 Sep 2021.

Builds on

32 of 56 references.

References · 32

  1. 2018Which Training Methods for GANs do actually Converge?cited by 672
  2. 2018Gradient Descent Finds Global Minima of Deep Neural Networkscited by 572
  3. 2017How to Escape Saddle Points Efficientlycited by 284
  4. 2016Deep Learning without Poor Local Minimacited by 233
  5. 2017Training GANs with Optimismcited by 217
  6. 2018A Variational Inequality Perspective on Generative Adversarial Networkscited by 144
  7. 2018Optimistic mirror descent in saddle-point problems: Going the extra (gradient) milecited by 132
  8. 2017No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysiscited by 127
  9. 2016Matrix Completion has No Spurious Local Minimumcited by 124
  10. 2017Cycles in adversarial regularized learningcited by 122
  11. 2018The Mechanics of n-Player Differentiable Gamescited by 118
  12. 2018Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimizationcited by 97
20 more
  1. 2019Open-ended Learning in Symmetric Zero-sum Gamescited by 96
  2. 2018The Unusual Effectiveness of Averaging in GAN Trainingcited by 73
  3. 2018Negative Momentum for Improved Game Dynamicscited by 59
  4. 2020No-regret learning and mixed Nash equilibria: They do not mixcited by 49
  5. 2017Gradient Descent Learns One-hidden-layer CNN: Don't be Afraid of Spurious Local Minimacited by 40
  6. 2019First-order methods almost always avoid saddle points: the case of vanishing step-sizescited by 35
  7. 2016Gradient Descent Only Converges to Minimizers: Non-Isolated Critical Points and Invariant Regionscited by 33
  8. 2017Multiplicative Weights Update with Constant Step-Size in Congestion Games: Convergence, Limit Cycles and Chaoscited by 29
  9. 2019Finite Regret and Cycles with Fixed Step-Size via Alternating Gradient Descent-Ascentcited by 28
  10. 2019Last-iterate convergence rates for min-max optimizationcited by 25
  11. 2019Vortices Instead of Equilibria in MinMax Optimization: Chaos and Butterfly Effects of Online Learning in Zero-Sum Gamescited by 24
  12. 2019Efficiently escaping saddle points on manifoldscited by 24
  13. 2020On the Impossibility of Global Convergence in Multi-Loss Optimizationcited by 16
  14. 2019Poincar'e Recurrence, Cycles and Spurious Equilibria in Gradient-Descent-Ascent for Non-Convex Non-Concave Zero-Sum Gamescited by 15
  15. 2019Depth-Width Trade-offs for ReLU Networks via Sharkovsky's Theoremcited by 15
  16. 2017First-order Methods Almost Always Avoid Saddle Pointscited by 14
  17. 2019Multi-Agent Learning in Network Zero-Sum Games is a Hamiltonian Systemcited by 13
  18. 2020Better Depth-Width Trade-offs for Neural Networks through the lens of Dynamical Systemscited by 9
  19. 2018Multiplicative Weights Update as a Distributed Constrained Optimization Algorithm: Convergence to Second-order Stationary Points Almost Alwayscited by 7
  20. 2018On the Computational Power of Online Gradient Descentcited by 1

Built on by

Not cited yet.