A Symplectic Analysis of Alternating Mirror Descent

arXiv:2405.03472v1 Announce Type: cross
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 …

abstract algebra algorithm amd analysis arxiv behavior continuous cs.gt cs.lg cs.na dynamics flow framework games math.ds math.na math.oc numerical results study sum type understanding via