The Power of Parallelism in Stochastic Search for Global Optimum: Keynote Paper

We explore the power of parallelism in a stochastic search for global optimum in high-dimensional optimization problems. This search, that often navigates a large solution space through a Markov-Chain Monte Carlo (MCMC) process, needs to make stochastic decisions at every step and needs to escape from local optima. Through parallelism, we are able to survey an entire neighbourhood (all states with Hamming distance of 1) to make efficient moves, use multiple replicas at different temperatures, such as in parallel tempering, or deploy a population of replicas at the same temperature. Once combined, these methods of parallelism can yield 100x to 10,000x speedups.