How Well Does the Metropolis Algorithm Cope With Local Optima?
The Metropolis algorithm (MA) is a classic stochastic local search heuristic. It avoids getting stuck in local optima by occasionally accepting inferior solutions. To better and in a rigorous manner understand this ability, we conduct a mathematical runtime analysis of the MA on the CLIFF benchmark. Apart from one local optimum, cliff functions are monotonically increasing towards the global optimum. Consequently, to optimize a cliff function, the MA only once needs to accept an inferior solution. Despite seemingly being an ideal benchmark for the MA to profit from its main working principle, our mathematical runtime analysis shows that this hope does not come true. Even with the optimal temperature (the only parameter of the MA), the MA optimizes most cliff functions less efficiently than simple elitist evolutionary algorithms (EAs), which can only leave the local optimum by generating a superior solution possibly far away. This result suggests that our understanding of why the MA is often very successful in practice is not yet complete. Our work also suggests to equip the MA with global mutation operators, an idea supported by our preliminary experiments.
Code (1)
Tasks
Evolutionary AlgorithmsSimilar Papers 제목 키워드 기반
Distributed Metropolis Sampler with Optimal Parallelism
The Metropolis-Hastings algorithm is a fundamental Markov chain Monte Carlo (MCMC) method for sampling and inference. With the advent of Big Data, distributed and parallel variants of MCMC methods are attracting increase…
QFold: Quantum Walks and Deep Learning to Solve Protein Folding
Predicting the 3D structure of proteins is one of the most important problems in current biochemical research. In this article, we explain how to combine recent deep learning advances with the well known technique of qua…
Deep LearningProtein FoldingCyclical Kernel Adaptive Metropolis
We propose cKAM, cyclical Kernel Adaptive Metropolis, which incorporates a cyclical stepsize scheme to allow control for exploration and sampling. We show that on a crafted bimodal distribution, existing Adaptive Metropo…
WarpLDA: a Cache Efficient O(1) Algorithm for Latent Dirichlet Allocation
Developing efficient and scalable algorithms for Latent Dirichlet Allocation (LDA) is of wide interest for many applications. Previous work has developed an O(1) Metropolis-Hastings sampling method for each token. Howeve…
Training neural networks using Metropolis Monte Carlo and an adaptive variant
We examine the zero-temperature Metropolis Monte Carlo algorithm as a tool for training a neural network by minimizing a loss function. We find that, as expected on theoretical grounds and shown empirically by other auth…