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?
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.
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:
"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
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.