Wednesday, March 27, 2024
Time  Items 

All day 

3:00pm 
03/27/2024  3:00pm 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 zerosum 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 zerosum 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 closedform 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. Location:
LOM 214
