Mirrored Langevin Dynamics
share
We generalize the Langevin Dynamics through the mirror descent framework for first-order sampling. The naïve approach of incorporating Brownian motion into the mirror descent dynamics, which we refer to as Symmetric Mirrored Langevin Dynamics (S-MLD), is shown to connected to the theory of Weighted Hessian Manifolds. The S-MLD, unfortunately, contains the hard instance of Cox--Ingersoll--Ross processes, whose discrete-time approximation exhibits slow convergence both theoretically and empirically. We then propose a new dynamics, which we refer to as the Asymmetric Mirrored Langevin Dynamics (A-MLD), that avoids the hurdles of S-MLD. In particular, we prove that discretized A-MLD implies the existence of a first-order sampling algorithm that sharpens the state-of-the-art Õ(ϵ^-6d^5) rate to Õ(ϵ^-2d), when the target distribution is strongly log-concave with compact support. For sampling on a simplex, A-MLD can transform certain non-log-concave sampling problems into log-concave ones. As a concrete example, we derive the first non-asymptotic Õ(ϵ^-4d^6) rate for first-order sampling of Dirichlet posteriors.
READ FULL TEXT