14
$\begingroup$

I'm learning about Markov Chain Monte Carlo methods, and to my undifferentiated mind, they basically resemble gradient descent with a stochastic component replacing the gradient computation. Is this a correct understanding. If not what key difference am I missing?

$\endgroup$
1
18
$\begingroup$

The key difference is that we are not attempting to optimize anything. Instead, we are attempting to estimate a density function - but not by estimating in some optimal manner a small number of parameters, instead by generating a lot of random numbers from the density function and going from there. So MCMC is really a random number generation technique, not an optimization technique.

To see what a gradient descent-like algorithm with a stochastic component looks like, check out stochastic approximation. The simultaneous perturbation variant is quite effective and accessible.

$\endgroup$
4
  • 2
    $\begingroup$ Thanks! I get that, but to me this is a difference of intent rather than technique. To me the density function in MCMC takes the place of the cost function in optimization. True, in the case of MCMC we don't stop when we reach the peak of the density but keep exploring, visiting each neighborhood proportional to the density landscape, but it looks remarkably similar. $\endgroup$ Dec 7 '13 at 19:39
  • 5
    $\begingroup$ I see your point, but somewhat disagree. With cost minimization, we know the cost function, and we are trying to find the peak. The stochastic gradient techniques pick a random direction (guided by history) with that objective. With MCMC, we don't try to reach the peak. With an independence sampler, we aren't even selecting the next proposal with any reference to our current location (so this would analogize to trying to min. a function by just randomly selecting inputs.) The only real similarity I see is solving a problem via random proposals with an acceptance step. $\endgroup$
    – jbowman
    Dec 7 '13 at 19:46
  • 2
    $\begingroup$ The Metropolis algorithm that we statisticians use to get samples from posterior distributions can also be used to optimize functions (that's what simulated annealing is), but it's still not stochastic gradient descent. $\endgroup$
    – Glen_b
    Dec 8 '13 at 0:21
  • 1
    $\begingroup$ Good! I wasn't seeing ghosts completely :) I realize MCMC is not gradient descent, but there are similarities, especially since the acceptance step compares the value of the new and old densities and effectively tries to climb up hill (with a little slip, if you will) $\endgroup$ Dec 8 '13 at 14:04
6
$\begingroup$

I know this question has been answered, but if anyone is interested in learning more on on jbowman's suggestion of random proposals with an acceptance step see Simulated Annealing:

http://en.wikipedia.org/wiki/Simulated_annealing

Excerpt:

"The method is an adaptation of the Metropolis-Hastings algorithm, a Monte Carlo method to generate sample states of a thermodynamic system..."

Typically slower then SGD, it's a good MC-based method for seeking global minima.

Java implementation for reference: https://github.com/wlmiller/BKTSimulatedAnnealing

$\endgroup$
0
$\begingroup$

While the accepted answer here is true, it is a bit misleading in light of recent theoretical work.

When you are doing gradient descent, you are trying to find the maximum a posterior (MAP) - aka the mode of your posterior distribution. While stochastic gradient descent (SGD) will only give you a point estimate, it will give you a trajectory that will allow you to explore the posterior density around your MAP estimate.

There is a ton of emerging literature around this, starting with Neal 2012 / Welling 2011 with Langevin dynamics and later Mandt 2017, Maddox 2019 and Zhang 2021. At this point, it is safe to say that SGD will generate a single MCMC draw from your posterior distribution.

$\endgroup$

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.