Symplectic integrators are generally used to simulate Hamiltonian flows in practice. While a given Hamiltonian flow conserves a Hamiltonian, any symplectic integrator applied to that flow generally conserves a perturbed Hamiltonian specific to that integrator called the ”Modified Hamiltonian” (MH). And while the field of Hamiltonian dynamics was originally formulated to model physical systems that conserve energy, Hamiltonian flows also appear in applications across computer science and learning theory. The rigorous mathematical machinery used to derive and analyze symplectic integrators can be extended to derive algorithmic guarantees and analogous algorithms of interest in the aforementioned fields of research.

One particular example comes from algorithmic game theory. The joint behavior of two agents in a bilinear zero-sum game using greedy strategies in continuous time can be described via a Hamiltonian flow, and different discretization methods of the Hamiltonian flow correspond to different strategies for the two players in the game. Out of these strategies, we focus on the Alternating Mirror Descent (AMD) algorithm for constrained zero-sum games. We show that AMD is related by duality to the symplectic Euler discretization of Hamiltonian flow. We then prove some new error bounds on the MH for symplectic Euler when truncated at orders in the stepsize and compute the MH in closed-form when the original Hamiltonian is a quadratic function. Finally, we use these results to derive tigher complexity bounds for the total regret and duality gap of the average iterates for AMD, and show how these bounds could depend on the MH and its convergence.

A relaxed-pace seminar on impromptu subjects related to the interests of the audience.

Everyone is welcome.

The subjects are geometry, probability, combinatorics, dynamics, and more!