A First Runtime Analysis of Parallel Tempering in Quadratic Optimization

Abstract

Parallel tempering, or the replica exchange method, is a Markov Chain Monte Carlo (MCMC) sampling technique for finding low-energy states in complex landscapes by executing multiple processes at different temperatures and allowing for states to migrate between parallel processes based on the Metropolis criterion. Despite a growing interest in the technique as a randomized search heuristic, it is not clear when and why parallel tempering is effective. We conduct a first runtime analysis of the parallel tempering algorithm on a simple quadratic unconstrained binary optimization problem that induces a rugged energy landscape with tunable parameters. We prove that a single-temperature Metropolis process fails to efficiently optimize the problem at any temperature. In sharp contrast, a two-state parallel tempering approach using a low and a high temperature typically solves the problem in O(n^2 log n) iterations. The low-temperature process ensures stability, as it is unlikely to accept worsenings, whereas the high-temperature process facilitates exploration by traversing energy barriers. Improvements are discovered through exploration in the high-temperature process and transferred to the low-temperature process, where they are permanently retained. This effective interplay between processes demonstrates the power of parallel tempering and lends credence to its design.