Markov chain Monte Carlo (MCMC) methods sample from an arbitrary target distribution approximately, by simulating a Markov chain whose stationary distribution coincides with the target distribution. MCMC methods can also be used to sample from posterior distributions in Bayesian inference.
Langevin dynamics.
Metropolis adjustment.
Hamiltonian/hybrid Monte Carlo (HMC).
Diffusion-based MCMC samples from a target distribution by simulating a diffusion process whose stochastic differential follows an autonomous Ito stochastic differential equation (ISDE): $\text{d} \mathbf{x} = a(\mathbf{x})~\text{d} t + b(\mathbf{x})~\text{d} \mathbf{w}$, such that $\mathbf{x}_t \overset{d}{\to} \rho(x)$. In first-order Langevin dynamics (LD), $a(x) = - \nabla U(x)$ and $b = \sqrt{2} I_n$, where potential $U(x) = -\log f(x)$ and $f(x) \propto \rho(x)$ is an unnormalized density. In second-order Langevin dynamics, aka Hamiltonian dyanmics, $\text{d} \mathbf{x} = \mathbf{v}~\text{d} t$, $\text{d} \mathbf{v} = (- \nabla U(x) - D \mathbf{v})~\text{d} t + \sqrt{2D} I_n~\text{d} \mathbf{w}$, where dissipation parameter $D > 0$.
Numerical integration schemes for this ISDE approximate the transition function of the continuous-time diffusion with repeated application of a transition function of a small time step: given $P^t = e^{t \mathcal{L}}$, $t \in T$, design $P_h$, $h \in T$, such that $P_h^l \mathbf{x} \approx P^{l h} \mathbf{x}$. We denote the numerical solution as $\mathbf{x}^n_t$, e.g. at the l-th step $\mathbf{x}^n_{l h} = P_h^l \mathbf{x}_0$; we further simplify this notation by $\mathbf{x}_l$ when it causes no confusion. Kth-order local integrator is a numerical integrator $P_h$ whose action on every smooth bounded function approximates that of the diffusion to the $K$-th order: $\forall f \in (C^2(X), \|\cdot\|_\infty)$, $P_h f = P^h f + O(h^{K+1})$.
The simpliest numerical integrator is the the Euler integrator, which is of order one. The Euler integrator for the first-order Langevin dynamics is: $\mathbf{x}_l = \mathbf{x}_{l-1} - \nabla U(\mathbf{x}_{l-1}) h + \sqrt{2h} \mathbf{z}$ where $\mathbf{z}$ is the n-dimensional standard Gaussian vector. The Euler integrator for the first-order Hamiltonian dynamics is: $\mathbf{v}_l = \mathbf{v}_{l-1} - \nabla U(\mathbf{x}_{l-1}) h - D \mathbf{v}_{l-1} h + \sqrt{2Dh} \mathbf{z}$ and $\mathbf{x}_l = \mathbf{x}_{l-1} + \mathbf{v}_l h$. Symmetric splitting integrator (SSI) is a second-order integrator, which splits the local generator into a symmetric sequence of sub-generators that can be solved analytically [@ChenCY2015]; it also applies to stochastic gradient MCMC, where a stochastic version of the full gradient is used.
MCMC on Riemann manifolds:
Stochastic gradient MCMC (SG-MCMC):
SG-MCMC on Riemann manifold: