A Symplectic Analysis of Alternating Mirror Descent

Jonas Katona, Xiuyuan Wang, Andre Wibisono

Abstract

Motivated by understanding the behavior of the Alternating Mirror Descent (AMD) algorithm for bilinear zero-sum games, we study the discretization of continuous-time Hamiltonian flow via the symplectic Euler method. We provide a framework for analysis using results from Hamiltonian dynamics, Lie algebra, and symplectic numerical integrators, with an emphasis on the existence and properties of a conserved quantity, the modified Hamiltonian (MH), for the symplectic Euler method. We compute the MH in closed-form when the original Hamiltonian is a quadratic function, and show that it generally differs from the other conserved quantity known previously in that case. We derive new error bounds on the MH when truncated at orders in the stepsize in terms of the number of iterations, $K$, and use these bounds to show an improved $\mathcal{O}(K^{1/5})$ total regret bound and an $\mathcal{O}(K^{-4/5})$ duality gap of the average iterates for AMD. Finally, we propose a conjecture which, if true, would imply that the total regret for AMD scales as $\mathcal{O}\left(K^{\varepsilon}\right)$ and the duality gap of the average iterates as $\mathcal{O}\left(K^{-1+\varepsilon}\right)$ for any $\varepsilon>0$, and we can take $\varepsilon=0$ upon certain convergence conditions for the MH.

Introduction

In the fields of optimization and game theory, finding the equilibrium of a bilinear zero-sum game is a foundational challenge. These games represent a mathematical "tug-of-war" where one player's gain is another's loss. While gradient-based strategies are commonly used to update player positions, simultaneous updates are notoriously unstable. In such systems, trajectories often spiral outward, gaining "energy" indefinitely and moving away from the Nash equilibrium.

To address this instability, researchers utilize Alternating Mirror Descent (AMD), where players update their strategies sequentially rather than simultaneously. While AMD is empirically more stable, providing rigorous theoretical bounds on its convergence and performance—measured by "regret"—has remained difficult. This research establishes a formal bridge between AMD and the centuries-old physics of Hamiltonian systems, treating the algorithm as a discrete-time physical simulation.

Theoretical Framework: Algorithms as Physics

The core insight of this work is that AMD is not merely an optimization heuristic; it is a symplectic integrator. Specifically, the authors prove that AMD is mathematically equivalent to the Symplectic Euler method applied to a specific Hamiltonian flow, provided appropriate linear and Legendre transformations are applied.

The Modified Hamiltonian (MH)

In classical physics, a Hamiltonian system conserves total energy. When we discretize these systems into steps (as an algorithm does), the original energy (the Hamiltonian) is no longer perfectly conserved. However, symplectic integrators like AMD conserve a "shadow" energy known as the Modified Hamiltonian (MH).

The authors utilize the Baker-Campbell-Hausdorff (BCH) formula and Poisson brackets—tools from Lie Algebra—to compute these energy corrections order-by-order. A significant achievement of this paper is the calculation of the MH in closed-form for quadratic functions, revealing that it differs from previously known conserved quantities in the literature.

Methodology and Numerical Evaluation

The researchers evaluated the framework using numerical simulations across several mathematical landscapes to test the limits of the Modified Hamiltonian:

  • Quadratic cases: Used to verify the accuracy of the closed-form MH.
  • Log-cosh landscapes: Used to visualize trajectories and observe energy conservation properties.
  • Quartic and Logarithmic cases: Served as "stress tests" to investigate the convergence criteria of the MH series in non-linear environments.

Key Results and Improved Bounds

By analyzing the algorithm through the lens of symplectic geometry, the authors derived significantly tighter performance bounds for AMD.

  1. Regret Bounds: The paper improves the total regret bound from the previous state-of-the-art $\mathcal{O}(K^{1/3})$ to $\mathcal{O}(K^{1/5})$, where $K$ represents the number of iterations.
  2. Duality Gap: The duality gap, which measures the distance of the players' average strategies from the optimal equilibrium, is shown to shrink at a rate of $\mathcal{O}(K^{-4/5})$, an improvement over the previous $\mathcal{O}(K^{-2/3})$.
  3. The Near-Optimality Conjecture: The authors propose a conjecture regarding the convergence of the MH series. If proven true for all orders of the stepsize, it would imply that regret could scale as $\mathcal{O}(K^{\varepsilon})$ for any $\varepsilon > 0$, suggesting that AMD is nearly perfect over long horizons.

Conclusion and Future Work

This research demonstrates that the stability of alternating updates in game theory is a direct consequence of their symplectic nature. By preserving the underlying geometry of the problem, AMD avoids the energy drift that plagues simultaneous update methods.

The primary limitation remains the convergence of the formal MH series, which may not sum to a finite value if the stepsize is too large or the landscape is sufficiently irregular. Future research may explore other symplectic integrators, such as the "Leapfrog" method, to determine if they can provide even more robust algorithms for complex game-theoretic landscapes.

Summary updated

Abstract

Motivated by understanding the behavior of the Alternating Mirror Descent (AMD) algorithm for bilinear zero-sum games, we study the discretization of continuous-time Hamiltonian flow via the symplectic Euler method. We provide a framework for analysis using results from Hamiltonian dynamics, Lie algebra, and symplectic numerical integrators, with an emphasis on the existence and properties of a conserved quantity, the modified Hamiltonian (MH), for the symplectic Euler method. We compute the MH in closed-form when the original Hamiltonian is a quadratic function, and show that it generally differs from the other conserved quantity known previously in that case. We derive new error bounds on the MH when truncated at orders in the stepsize in terms of the number of iterations, $K$, and use these bounds to show an improved $\mathcal{O}(K^{1/5})$ total regret bound and an $\mathcal{O}(K^{-4/5})$ duality gap of the average iterates for AMD. Finally, we propose a conjecture which, if true, would imply that the total regret for AMD scales as $\mathcal{O}\left(K^{\varepsilon}\right)$ and the duality gap of the average iterates as $\mathcal{O}\left(K^{-1+\varepsilon}\right)$ for any $\varepsilon>0$, and we can take $\varepsilon=0$ upon certain convergence conditions for the MH.
BibTeX
@misc{katona2024symplectic,
  author = {Jonas Katona and Xiuyuan Wang and Andre Wibisono},
  title = {{A Symplectic Analysis of Alternating Mirror Descent}},
  year = {2024},
  eprint = {2405.03472},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2405.03472},
}
Figure