Timeline for Mathematical foundation of using MCMC in global optimization
Current License: CC BY-SA 3.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 6, 2016 at 0:32 | comment | added | zell | Thanks to your new edits. You said "note that $\pi(x) = \pi(E(x))$". Why that holds? | |
| Jan 5, 2016 at 17:40 | history | edited | Jorge Leitao | CC BY-SA 3.0 |
Major revision to the argumentation.
|
| Jan 5, 2016 at 16:41 | vote | accept | zell | ||
| Jan 5, 2016 at 16:40 | comment | added | zell | In your edits and cooments, you seem to say that "Because mcmc converges to the sampled distribution, we can eventually find the global minima". But why does convergence of mcmc implies the finding of the global minima? | |
| Jan 5, 2016 at 16:22 | comment | added | zell | @Leitao. Then, would you update your answer to make it more precise and rigorous? Since SA is not MCMC (which I did not realize), would you give a mathematical explanation of why MCMC (rather than SA) works (for finding global minima? Of course, it is necessary that we define the meaning of 'works' above. Thanks again. | |
| Jan 5, 2016 at 16:14 | history | edited | Jorge Leitao | CC BY-SA 3.0 |
Incorporated comments.
|
| Jan 5, 2016 at 16:02 | comment | added | Jorge Leitao | @zell, yes, MCMC are guaranteed to sample from the target distribution when detailed balance and ergodicity are fulfilled. However 1. stimulated annealing is not a MCMC because it is non-markovian (see also Brian's comment) and 2. MH with $\beta \rightarrow \infty$ does not fulfil detailed balance nor ergodicity. (E.g. once $E > E^*$, states with $E\le E^*$ are no longer visitable). | |
| Jan 5, 2016 at 15:57 | comment | added | Jorge Leitao | @BrianBorchers, The OP asked for "what is the reason why the Metropolis-Hasting algorithm can handle problem B". I answered that question, and justified why MH fails to guarantee a global maximum. Stimulated annealing is arguably a MCMC for the reason you mentioned, and it is arguably a MH algorithm, as it also violates detailed balance in the limit $\beta \rightarrow \infty$. For these reasons, I decided to only lightly touch the topic by making the connection of MH with S. Annealing. I agree with your remarks, but I don't see how they help to answer the question. | |
| Jan 5, 2016 at 15:53 | comment | added | zell | @Leitao. MCMC is guaranteed to converge to the sampled distribution -- reason why it shines. But in your response, you seem to ignore that fact. I up-voted for acknowledging your inputs only but I believe your vision about MCMC or simulated annealing is too limited to give a correct answer. | |
| Jan 5, 2016 at 15:40 | vote | accept | zell | ||
| Jan 5, 2016 at 15:48 | |||||
| Jan 5, 2016 at 15:40 | comment | added | Brian Borchers | I think you've missed the point of simulated annealing a bit. By using a carefully designed sequence of $\beta$ values, you can ensure that the simulated annealing algorithm will converge to a global optimum with high probability. Simulated annealing algorithms are actually very well established for solving global optimization problems. Note that because the resulting algorithm doesn't have the Markov property (it's non-stationary), the samples generated by simulated annealing aren't a proper sample from the distribution. | |
| Jan 5, 2016 at 15:36 | comment | added | Jorge Leitao | what that is supposed to mean @Xi'an? AFAIK historically MH was not used for optimisation all together, or was it? | |
| Jan 5, 2016 at 15:29 | comment | added | Xi'an | Note that historically the Metropolis-Hastings algorithm was not used for optimisation in the above sense. | |
| Jan 5, 2016 at 7:52 | history | answered | Jorge Leitao | CC BY-SA 3.0 |