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 utilize this bound 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 goes 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.

通过使用 Hamiltonian 动力学、李代数和辛数值积分器的结果，以及对连续时间 Hamiltonian 流通过辛欧拉方法的离散化的研究，我们提供了一个分析框架，并强调了修正 Hamiltonian (MH) 的存在和特性，计算了二次函数原 Hamiltonian 情况下的 MH，并得出新的误差界。我们利用这些结果展示了 Alternating Mirror Descent 算法的改进的总遗憾界限和平均迭代的对偶间隙。最后，我们提出了一个猜想，如果成立，会导致 AMD 的总遗憾为 O (K^ε)，平均迭代的对偶间隙为 O (K^-1+ε)，其中 ε>0，且在 MH 的特定收敛条件下可以取 ε=0。

交替镜像下降方法的辛分析

A Symplectic Analysis of Alternating Mirror Descent

It is known that the Langevin dynamics used in MCMC is the gradient flow of
the KL divergence on the Wasserstein space, which helps convergence analysis
and inspires recent particle-based variational inference methods (ParVIs). But
no more MCMC dynamics is understood in this way. In this work, by developing
novel concepts, we propose a theoretical framework that recognizes a general
MCMC dynamics as the fiber-gradient Hamiltonian flow on the Wasserstein space
of a fiber-Riemannian Poisson manifold. The "conservation + convergence"
structure of the flow gives a clear picture on the behavior of general MCMC
dynamics. The framework also enables ParVI simulation of MCMC dynamics, which
enriches the ParVI family with more efficient dynamics, and also adapts ParVI
advantages to MCMCs. We develop two ParVI methods for a particular MCMC
dynamics and demonstrate the benefits in experiments.

该论文提出了一个理论框架，将一般的 MCMC 动力学识别为在纤维 - 里曼诺泊松流形的 Wasserstein 空间上的纤维梯度哈密顿流，同时使 ParVI 模拟具有更高效的动力学，丰富了 ParVI 家族，证明了在实验中的优点。

理解 MCMC 动态作为 Wasserstein 空间上的流

Understanding MCMC Dynamics as Flows on the Wasserstein Space

Leveraging the coherent exploration of Hamiltonian flow, Hamiltonian Monte
Carlo produces computationally efficient Monte Carlo estimators, even with
respect to complex and high-dimensional target distributions. When confronted
with data-intensive applications, however, the algorithm may be too expensive
to implement, leaving us to consider the utility of approximations such as data
subsampling. In this paper I demonstrate how data subsampling fundamentally
compromises the efficient exploration of Hamiltonian flow and hence the
scalable performance of Hamiltonian Monte Carlo itself.

本文主要研究了数据子采样对于 Hamiltonian Monte Carlo 的计算效率与高维目标分布的影响，发现数据子采样会削弱 Hamiltonian 流的有效探索性能，从而损害了 Hamiltonian Monte Carlo 的可扩展性能。