Improved Langevin Monte Carlo for stochastic optimization via landscape modification

Abstract

Given a target function $H$ to minimize or a target Gibbs distribution $π_β^0 \propto e^{-βH}$ to sample from in the low temperature, in this paper we propose and analyze Langevin Monte Carlo (LMC) algorithms that run on an alternative landscape as specified by $H^f_{β,c,1}$ and target a modified Gibbs distribution $π^f_{β,c,1} \propto e^{-βH^f_{β,c,1}}$, where the landscape of $H^f_{β,c,1}$ is a transformed version of that of $H$ which depends on the parameters $f,β$ and $c$. While the original Log-Sobolev constant affiliated with $π^0_β$ exhibits exponential dependence on both $β$ and the energy barrier $M$ in the low temperature regime, with appropriate tuning of these parameters and subject to assumptions on $H$, we prove that the energy barrier of the transformed landscape is reduced which consequently leads to polynomial dependence on both $β$ and $M$ in the modified Log-Sobolev constant associated with $π^f_{β,c,1}$. This yield improved total variation mixing time bounds and improved convergence toward a global minimum of $H$. We stress that the technique developed in this paper is not only limited to LMC and is broadly applicable to other gradient-based optimization or sampling algorithms.