4 ms·

Using MCMC for optimization is really strange. MCMC is for generating random samples from a probability distribution, not for optimization. Some variant of hill

by jules 13y ago

Using MCMC for optimization is really strange. MCMC is for generating random samples from a probability distribution, not for optimization. Some variant of hill climbing would be more appropriate here.

SilasX 13y ago
Aren't search problems equivalent to sampling problems in the first place? At least, that's the premise of something I read recently: http://www.americanscientist.org/issues/pub/2014/3/the-quest-for-randomness http://www.americanscientist.org/issues/pub/2014/3/the-quest...
- jules 13y ago
  No, they are completely different. Sampling problem is: given a probability distribution P(x), draw random samples from such that each x has probability P(x) to be generated. Optimization problem is: given a cost function f(x), find the x that minimizes f(x).
  - SilasX 13y ago
    What I meant was, approximal optimization problems are a species of search problem (find a solution "at least this good"), and search problems are equivalent to sampling problems (per the reference) in the sense that either is reducible to the other. (Obviously search and sampling problems have different definitions.)
pavpanchekha 13y ago
Strange—ingenious. Hill climbing is bad for these sorts of problems since it gets stuck in local maxima—an as the charts in the evaluation show, there are often multiple maxima in the floating point precision of a program. So instead you need any of a variety of methods that guarantee finding a global maximum eventually. Luckily, MCMC gives you such a guarantee, with better asymptotic probabilistic bounds than simulated annealing. In the evaluation, they have a comparison of MCMC to annealing and hill climbing.
- thisisdave 13y ago
  >with better asymptotic probabilistic bounds than simulated annealing This seems unlikely to me. The Metropolis algorithm is just simulated annealing with a constant temperature. Which means that simulated annealing includes Metropolis MCMC as a special case. Also, while simulated annealing is guaranteed to find the global optimum given infinite time (almost sure convergence), I'm not aware of any such guarantees for Metropolis.
- jules 13y ago
  > In the evaluation, they have a comparison of MCMC to annealing and hill climbing. Where do you see that? Searching the document for "annealing" brings up 0 results. They don't do a comparison with hill climbing either.
montecarl 13y ago
I imagine that with hill climbing you will get stuck at a local maximum, however, with MCMC you will eventually explore the entire space. Put another way, MCMC will tend to sample mostly from the low lying parts of the cost function with fluctuations that will take it to other regions of the problem space.

by jules 13y ago

SilasX 13y ago

Aren't search problems equivalent to sampling problems in the first place? At least, that's the premise of something I read recently: http://www.americanscientist.org/issues/pub/2014/3/the-quest-for-randomness http://www.americanscientist.org/issues/pub/2014/3/the-quest...

jules 13y ago
No, they are completely different. Sampling problem is: given a probability distribution P(x), draw random samples from such that each x has probability P(x) to be generated. Optimization problem is: given a cost function f(x), find the x that minimizes f(x).
- SilasX 13y ago
  What I meant was, approximal optimization problems are a species of search problem (find a solution "at least this good"), and search problems are equivalent to sampling problems (per the reference) in the sense that either is reducible to the other. (Obviously search and sampling problems have different definitions.)

pavpanchekha 13y ago

Strange—ingenious. Hill climbing is bad for these sorts of problems since it gets stuck in local maxima—an as the charts in the evaluation show, there are often multiple maxima in the floating point precision of a program. So instead you need any of a variety of methods that guarantee finding a global maximum eventually. Luckily, MCMC gives you such a guarantee, with better asymptotic probabilistic bounds than simulated annealing. In the evaluation, they have a comparison of MCMC to annealing and hill climbing.

thisisdave 13y ago
>with better asymptotic probabilistic bounds than simulated annealing This seems unlikely to me. The Metropolis algorithm is just simulated annealing with a constant temperature. Which means that simulated annealing includes Metropolis MCMC as a special case. Also, while simulated annealing is guaranteed to find the global optimum given infinite time (almost sure convergence), I'm not aware of any such guarantees for Metropolis.
jules 13y ago
> In the evaluation, they have a comparison of MCMC to annealing and hill climbing. Where do you see that? Searching the document for "annealing" brings up 0 results. They don't do a comparison with hill climbing either.

montecarl 13y ago

I imagine that with hill climbing you will get stuck at a local maximum, however, with MCMC you will eventually explore the entire space. Put another way, MCMC will tend to sample mostly from the low lying parts of the cost function with fluctuations that will take it to other regions of the problem space.