Sampling as optimization in the space of measures: The Langevin dynamics as a composite optimization problem

Abstract

We study sampling as optimization in the space of measures. We focus on gradient flow-based optimization with the Langevin dynamics as a case study. We investigate the source of the bias of the unadjusted Langevin algorithm (ULA) in discrete time, and consider how to remove or reduce the bias. We point out the difficulty is that the heat flow is exactly solvable, but neither its forward nor backward method is implementable in general, except for Gaussian data. We propose the symmetrized Langevin algorithm (SLA), which should have a smaller bias than ULA, at the price of implementing a proximal gradient step in space. We show SLA is in fact consistent for Gaussian target measure, whereas ULA is not. We also illustrate various algorithms explicitly for Gaussian target measure, including gradient descent, proximal gradient, and Forward-Backward, and show they are all consistent.

arXiv commentTo appear at the Conference on Learning Theory (COLT), July 2018

References in corpus (13)

• A Conceptual Introduction to Hamiltonian Monte Carlo
• A Variational Perspective on Accelerated Methods in Optimization
• User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradient
• Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysis
• Stein Variational Gradient Descent as Gradient Flow
• Underdamped Langevin MCMC: A non-asymptotic analysis
• Log-concave sampling: Metropolis-Hastings algorithms are fast
• Convergence of Langevin MCMC in KL-divergence
• Rapid Mixing of Hamiltonian Monte Carlo on Strongly Log-Concave Distributions
• A Hitting Time Analysis of Stochastic Gradient Langevin Dynamics
• On the convergence of Hamiltonian Monte Carlo
• First-order Methods for Geodesically Convex Optimization
• Convergence of the Forward-Backward Algorithm: Beyond the Worst Case with the Help of Geometry

Cited by in corpus (12)

• Sampling Can Be Faster Than Optimization
• Is There an Analog of Nesterov Acceleration for MCMC?
• Langevin Monte Carlo and JKO splitting
• Optimal Convergence Rate of Hamiltonian Monte Carlo for Strongly Logconcave Distributions
• Exponential ergodicity of mirror-Langevin diffusions
• Primal Dual Interpretation of the Proximal Stochastic Gradient Langevin Algorithm
• Stochastic Proximal Langevin Algorithm: Potential Splitting and Nonasymptotic Rates
• SVGD as a kernelized Wasserstein gradient flow of the chi-squared divergence
• Understanding MCMC Dynamics as Flows on the Wasserstein Space
• A Particle-Based Algorithm for Distributional Optimization on \textit{Constrained Domains} via Variational Transport and Mirror Descent
• Self-Paced Deep Reinforcement Learning
• A Probabilistic Interpretation of Self-Paced Learning with Applications to Reinforcement Learning