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

arXiv: https://arxiv.org/abs/2109.03974 · HTML: https://mlsanity.com/paper/2109.03974/

## Key facts

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

## Builds on (most cited first, 30 of 32)

- [Which Training Methods for GANs do actually Converge?](https://mlsanity.com/paper/1801.04406/) (2018)
- [Gradient Descent Finds Global Minima of Deep Neural Networks](https://mlsanity.com/paper/1811.03804/) (2018)
- [How to Escape Saddle Points Efficiently](https://mlsanity.com/paper/1703.00887/) (2017)
- [Deep Learning without Poor Local Minima](https://mlsanity.com/paper/1605.07110/) (2016)
- [Training GANs with Optimism](https://mlsanity.com/paper/1711.00141/) (2017)
- [A Variational Inequality Perspective on Generative Adversarial Networks](https://mlsanity.com/paper/1802.10551/) (2018)
- [Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile](https://mlsanity.com/paper/1807.02629/) (2018)
- [No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis](https://mlsanity.com/paper/1704.00708/) (2017)
- [Matrix Completion has No Spurious Local Minimum](https://mlsanity.com/paper/1605.07272/) (2016)
- [Cycles in adversarial regularized learning](https://mlsanity.com/paper/1709.02738/) (2017)
- [The Mechanics of n-Player Differentiable Games](https://mlsanity.com/paper/1802.05642/) (2018)
- [Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimization](https://mlsanity.com/paper/1807.04252/) (2018)
- [Open-ended Learning in Symmetric Zero-sum Games](https://mlsanity.com/paper/1901.08106/) (2019)
- [The Unusual Effectiveness of Averaging in GAN Training](https://mlsanity.com/paper/1806.04498/) (2018)
- [Negative Momentum for Improved Game Dynamics](https://mlsanity.com/paper/1807.04740/) (2018)
- [No-regret learning and mixed Nash equilibria: They do not mix](https://mlsanity.com/paper/2010.09514/) (2020)
- [Gradient Descent Learns One-hidden-layer CNN: Don't be Afraid of Spurious Local Minima](https://mlsanity.com/paper/1712.00779/) (2017)
- [First-order methods almost always avoid saddle points: the case of vanishing step-sizes](https://mlsanity.com/paper/1906.07772/) (2019)
- [Gradient Descent Only Converges to Minimizers: Non-Isolated Critical Points and Invariant Regions](https://mlsanity.com/paper/1605.00405/) (2016)
- [Multiplicative Weights Update with Constant Step-Size in Congestion Games: Convergence, Limit Cycles and Chaos](https://mlsanity.com/paper/1703.01138/) (2017)
- [Finite Regret and Cycles with Fixed Step-Size via Alternating Gradient Descent-Ascent](https://mlsanity.com/paper/1907.04392/) (2019)
- [Vortices Instead of Equilibria in MinMax Optimization: Chaos and Butterfly Effects of Online Learning in Zero-Sum Games](https://mlsanity.com/paper/1905.08396/) (2019)
- [Last-iterate convergence rates for min-max optimization](https://mlsanity.com/paper/1906.02027/) (2019)
- [Efficiently escaping saddle points on manifolds](https://mlsanity.com/paper/1906.04321/) (2019)
- [On the Impossibility of Global Convergence in Multi-Loss Optimization](https://mlsanity.com/paper/2005.12649/) (2020)
- [Poincar'e Recurrence, Cycles and Spurious Equilibria in Gradient-Descent-Ascent for Non-Convex Non-Concave Zero-Sum Games](https://mlsanity.com/paper/1910.13010/) (2019)
- [Depth-Width Trade-offs for ReLU Networks via Sharkovsky's Theorem](https://mlsanity.com/paper/1912.04378/) (2019)
- [First-order Methods Almost Always Avoid Saddle Points](https://mlsanity.com/paper/1710.07406/) (2017)
- [Multi-Agent Learning in Network Zero-Sum Games is a Hamiltonian System](https://mlsanity.com/paper/1903.01720/) (2019)
- [Better Depth-Width Trade-offs for Neural Networks through the lens of Dynamical Systems](https://mlsanity.com/paper/2003.00777/) (2020)

## 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.