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

Georgios Piliouras, Xiao WangarXiv 2021 · arXiv

Introduction

In traditional single-objective optimization, we generally expect algorithms to converge toward a local minimum. However, modern machine learning increasingly involves "games"—such as Generative Adversarial Networks (GANs) or multi-agent reinforcement learning—where multiple players optimize different functions simultaneously. In these complex environments, standard algorithms often fail to converge, instead spiraling into cycles or descending into unpredictable chaos.

Chaos is defined by "scrambled sets": pairs of points that start in close proximity but diverge wildly over time. While previous research identified chaotic behavior in small-scale games, there has been a lack of methodological tools to prove when a system will remain regular. This paper addresses that gap by drawing inspiration from classical physics to provide a theoretical "antidote" to chaos.

The Physics of Optimization: Invariant Functions

The authors leverage the concept of Invariant Functions (or "Constants of Motion"). In physics, quantities like energy or momentum are conserved, restricting a particle's movement to specific geometric surfaces. By applying this logic to discrete-time optimization algorithms, the researchers demonstrate that common algorithms are far more predictable than previously feared.

Invariant functions restrict the movement of optimization trajectories to specific surfaces, preventing the 'scrambled' behavior characteristic of chaos.

Methodological Approach

  1. Closed-Form Invariants: For specific cases like Alternating Gradient Descent in coordination games, the authors derived explicit mathematical formulas for these constants.
  2. Non-Constructive Proofs: For general algorithms (Gradient Descent, MWU, and Manifold Gradient Descent), they utilized dynamical systems theory to prove that these invariant functions must exist, even if a simple formula is not readily available.
  3. Numerical Validation: The findings were validated through simulations of synthetic utility functions, such as the bilinear function $f(x, y) = xy$, visualizing how trajectories are constrained to specific level curves.

Key Insights: Chaos as a Lack of Invariants

A central thesis of the paper is that chaos can be viewed as a fundamental lack of invariant functions. By identifying enough invariants, the "degrees of freedom" in a system are reduced until chaos becomes mathematically impossible.

The theoretical framework connecting invariant functions to the classification of orbits and the negation of chaos.
  • The "Topologically Large" Guarantee: For Gradient Descent and Multiplicative Weights Update (MWU) with small step sizes, the authors prove that independent invariant functions exist on an open dense subset of the space. This implies that for almost any starting point, the system remains regular.
  • Negation of Chaos: In coordination games, the existence of even a single continuous invariant function is sufficient to prove that "scrambled sets" have a Lebesgue measure of zero. Essentially, chaos becomes a "zero-probability" event.
  • Oracle Classifiers for Orbits: These invariants act as a "fingerprint" for an orbit; two points belong to the same trajectory if and only if all their invariant function values match.

Key Results

  • Alternating Gradient Descent: In bipartite network coordination games, the system was proved to be highly regular. The authors provided an explicit invariant formula involving the norms of the weights and the interaction matrix.
  • Gradient Descent & MWU: For a $d$-dimensional space, the existence of $d$ independent invariant functions was established, implying highly regular dynamics on a topologically large subset of the phase space.
  • Manifold Generalization: These results extend to Manifold Gradient Descent, showing the "antidote" works even on complex, non-Euclidean geometries.

Limitations and Future Work

While groundbreaking, the study relies on the assumption of "small enough" step sizes. It remains an open question how these invariants behave under the aggressive learning rates common in deep learning. Furthermore, while the paper proves these functions exist, they are often non-constructive; finding interpretable invariants for complex neural networks remains a significant challenge. Future research may focus on using these invariants for dimensionality reduction, projecting massive multi-agent systems onto their conserved surfaces to simplify analysis.

Summary updated

Abstract

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\times 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.
BibTeX
@misc{piliouras2021constants,
  author = {Georgios Piliouras and Xiao Wang},
  title = {{Constants of Motion: The Antidote to Chaos in Optimization and Game Dynamics}},
  year = {2021},
  eprint = {2109.03974},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2109.03974},
}
Figure