Is there an analog of Nesterov acceleration for gradient-based MCMC?
Yi-An Ma, Niladri S. Chatterji, Xiang Cheng, Nicolas Flammarion, Peter L. Bartlett, Michael I. Jordan
Abstract
We formulate gradient-based Markov chain Monte Carlo (MCMC) sampling as optimization on the space of probability measures, with Kullback–Leibler (KL) divergence as the objective functional. We show that an underdamped form of the Langevin algorithm performs accelerated gradient descent in this metric. To characterize the convergence of the algorithm, we construct a Lyapunov functional and exploit hypocoercivity of the underdamped Langevin algorithm. As an application, we show that accelerated rates can be obtained for a class of nonconvex functions with the Langevin algorithm.
Topics & Concepts
Markov chain Monte CarloMathematicsLangevin dynamicsMarkov chainAccelerationKullback–Leibler divergenceConvergence (economics)Metric (unit)Gradient descentApplied mathematicsMathematical optimizationStochastic gradient descentMonte Carlo methodDivergence (linguistics)AlgorithmComputer scienceArtificial intelligenceStatisticsLinguisticsEconomic growthClassical mechanicsPhysicsArtificial neural networkOperations managementPhilosophyEconomicsMarkov Chains and Monte Carlo MethodsAdvanced Neuroimaging Techniques and ApplicationsStochastic Gradient Optimization Techniques