4
$\begingroup$

We want to sample from the distribution $P(\theta \mid X)$, which we only know up to a multiplicative constant. In Langvin MCMC, our Markov Chain is $$ \theta_{t+1} = \theta_t + \frac{\epsilon_t}{2}\left ( \nabla P(\theta_t) + \sum_{i = 1}^n \nabla P(x_i \mid \theta_t) \right ) + \sqrt{\epsilon_t}\mu, $$ where $\mu \sim N(0,I)$ and $\epsilon_t$ is the stepsize.

This is a discrete time approximation of the continuous time process $$ \frac{d \theta_t}{d t} = \frac{1}{2}\nabla P(\theta_t \mid X) + \xi(t). $$ where $\xi(t)$ is the time derivative of Brownian motion.

If $\epsilon_t$ is a constant, then for the distribution to converge to the posterior we need to adjust each step with Metropolis-Hastings. However if $\epsilon_t$ is decreasing (with some assumptions such as $\sum_{t = 1}^\infty \epsilon_t = \infty$ and $\sum_{t = 1}^\infty \epsilon_t^2 < \infty$) will we converge to the posterior?

My reason for asking is that there has been a lot of work on Langvin MCMC with stochastic gradients and it is not clear to me if all the error is due just to the estimate of the gradients or the discretization of the continuous time Markov Chain with even with decreasing stepsize.

$\endgroup$
4
$\begingroup$

You wrote a very weird expression for Langevin MCMC (which is a special case of Diffusion Markov Chain Monte Carlo). On the right hand side you only have gradients of the prior and the likelihood at time $t$ (plus, of course the Gaussian noise), but you don't have the state at time $t$ $\boldsymbol{\theta}_t$. How's that possible, considering that Diffusion MCMC comes from a forward Euler discretization of a stochastic differential equation (SDE)? That's not the expression I know, and I think it's wrong.

Using the symbol $h$ for the step size ($\epsilon_t$ sounds too much like an error term to me), the expression I know for Langevin MCMC is:

$$ \boldsymbol{\theta}_{t+1} = \boldsymbol{\theta}_t + 0.5h\left( \nabla \log{g(\mathbf{y}|\boldsymbol{\theta}_t)}+\nabla\log{\pi(\boldsymbol{\theta}_t)}\right) + \sqrt{h}\mu $$

where $\pi(\boldsymbol{\theta})$ is the prior and $g(\mathbf{y}|\boldsymbol{\theta})$ is the likelihood for a data vector $\mathbf{y}$. I'm considering the non-adaptive case ($h_t=h \ \forall t$).

Concerning your question, the answer is: it depends. In some cases Langevin MCMC is stable for a fixed, small enough $h$, while in other cases it explodes even if $h_t$ is chosen adaptively at each step. Just to be clear, I stress that I'm referring to Langevin MCMC, not the Metropolis-adjusted Langevin Algorithm (MALA), i.e., a step of Langevin MCMC followed by a Metropolis-Hastings step. Also, let's separate two different problems: convergence of the Euler discretization to the target (posterior) distribution when $h\to 0$, and stability of a given discretization (fixed $h$). For the first point, there are regularity conditions which guarantee that the Euler discretization has a stationary measure which converges, for $h\to 0$, to the stationary measure of the continuous-time SDE: see

Second-order discretization schemes of stochastic differential systems for the computation of the invariant law

Other important convergence results can be found here:

Convergence of Numerical Time-Averaging and Stationary Measures via Poisson Equations

Exponential Convergence of Langevin Distributions and Their Discrete Approximations

For the second point, even if we restrict to cases where the regularity conditions hold, the Euler discretization of the diffusion SDE can be unstable for a given value of $h$. Given a specific Bayesian model (i.e., a choice of $g$ and $\pi$), it can be difficult in practice to find a value of $h$ such that Langevin MCMC is stable. Numerical experiments seem to indicate that, if the conditions for convergence are satisfied, then the choice $h=O(1/p)$, where $p$ is the number of parameters, can lead to a stable discretization. However, it's not necessary to find a suitable $h$ by trial and error. There are some theoretical indications on how to choose $h$ adaptively in order to make Langevin MCMC stable:

An adaptive Euler–Maruyama scheme for SDEs: convergence and stability

Here you have a very nice discussion on how to use Langevin MCMC "in practice", which also lists all the references I linked to, and much more:

Applying diffusion-based Markov chain Monte Carlo

$\endgroup$
2
  • 1
    $\begingroup$ Yes the expression for Langevin MCMC was missing the $\theta_t$ term. I edited my question to include it. $\endgroup$
    – xeqql
    Apr 26 '17 at 23:13
  • $\begingroup$ @xeqql yes, that, and also logs are missing inside the gradients. See the last link I provided. $\endgroup$
    – DeltaIV
    Apr 27 '17 at 6:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.