Evolutionary stochastic gradient Langevin dynamics: overcoming local traps in large-scale Bayesian sampling

The scalability of stochastic gradient MCMC algorithms has made them increasingly important for Bayesian analysis of big data. However, these algorithms are prone to getting trapped in local energy minima. We introduce a novel algorithm—evolutionary stochastic gradient Langevin dynamics (ESGLD)— that is particularly effective at mitigating local-trap behavior when simulating posterior distributions in big data scenarios. ESGLD operates with a population of Markov chains, each at a different temperature, and these chains interact through a snooker operator. The snooker operator performs a short run of SGLD along the line connecting the current sample to a selected anchor point. As long as a mode is located by other chains in the population, the target chain can transition to it by running the snooker operator, particularly when the mode is sharp and well-separated from others. The snooker operator enables the Markov chain to effectively escape local traps while maintaining invariance with respect to the target distribution. This significantly accelerates convergence, especially when the energy landscape is rugged. We provide theoretical guarantees for the convergence of the ESGLD algorithm in the big data regime and demonstrate its numerical effectiveness through simulated and real data examples, with the latter modeled by neural networks.