Analysis of Langevin Monte Carlo from Poincaré to Log-Sobolev

• URL: http://arxiv.org/abs/2112.12662v2
• Date: Wed, 10 Jul 2024 16:45:27 GMT
• Title: Analysis of Langevin Monte Carlo from Poincaré to Log-Sobolev
• Authors: Sinho Chewi, Murat A. Erdogdu, Mufan Bill Li, Ruoqi Shen, Matthew Zhang,
• Abstract summary: We provide the first convergence guarantees for the discrete-time Langevin Monte Carlo algorithm. Unlike prior works, our results allow for weak smoothness and do not require convexity or dissipativity conditions.
• Score: 25.18241929887685
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Classically, the continuous-time Langevin diffusion converges exponentially fast to its stationary distribution $\pi$ under the sole assumption that $\pi$ satisfies a Poincar\'e inequality. Using this fact to provide guarantees for the discrete-time Langevin Monte Carlo (LMC) algorithm, however, is considerably more challenging due to the need for working with chi-squared or R\'enyi divergences, and prior works have largely focused on strongly log-concave targets. In this work, we provide the first convergence guarantees for LMC assuming that $\pi$ satisfies either a Lata\l{}a--Oleszkiewicz or modified log-Sobolev inequality, which interpolates between the Poincar\'e and log-Sobolev settings. Unlike prior works, our results allow for weak smoothness and do not require convexity or dissipativity conditions.

Related papers

• Fast Convergence of $Φ$-Divergence Along the Unadjusted Langevin Algorithm and Proximal Sampler [14.34147140416535]
  We study the mixing time of two popular discrete time Markov chains in continuous space. We show that any $Phi$-divergence arising from a twice-differentiable strictly convex function $Phi$ converges to $0$ exponentially fast along these Markov chains.
  arXiv  Detail & Related papers  (2024-10-14T16:41:45Z)
• Provable Benefit of Annealed Langevin Monte Carlo for Non-log-concave Sampling [28.931489333515618]
  We establish an oracle complexity of $widetildeOleft(fracdbeta2cal A2varepsilon6right)$ for simple annealed Langevin Monte Carlo algorithm. We show that $cal A$ represents the action of a curve of probability measures interpolating the target distribution $pi$ and a readily sampleable distribution.
  arXiv  Detail & Related papers  (2024-07-24T02:15:48Z)
• Symmetric Mean-field Langevin Dynamics for Distributional Minimax Problems [78.96969465641024]
  We extend mean-field Langevin dynamics to minimax optimization over probability distributions for the first time with symmetric and provably convergent updates. We also study time and particle discretization regimes and prove a new uniform-in-time propagation of chaos result.
  arXiv  Detail & Related papers  (2023-12-02T13:01:29Z)
• Taming under isoperimetry [0.0]
  In this article we propose a Langevin-based scheme calledmathbfsTULA$ to sample from distributions with growing log. We derive non-asymientKL and consequently consequently satisfy a Log-Sobolev inequality.
  arXiv  Detail & Related papers  (2023-11-15T14:44:16Z)
• Towards a Complete Analysis of Langevin Monte Carlo: Beyond Poincar\'e Inequality [15.941909642134085]
  This research program was initiated by Vempala and Wibisono, who established results under log-Sobolev inequalities. Our results explicitly quantify the effect of the initializer on the performance of the Langevin Monte Carlo (LMC) algorithm.
  arXiv  Detail & Related papers  (2023-03-07T01:45:04Z)
• Mean-Square Analysis with An Application to Optimal Dimension Dependence of Langevin Monte Carlo [60.785586069299356]
  This work provides a general framework for the non-asymotic analysis of sampling error in 2-Wasserstein distance. Our theoretical analysis is further validated by numerical experiments.
  arXiv  Detail & Related papers  (2021-09-08T18:00:05Z)
• Faster Convergence of Stochastic Gradient Langevin Dynamics for Non-Log-Concave Sampling [110.88857917726276]
  We provide a new convergence analysis of gradient Langevin dynamics (SGLD) for sampling from a class of distributions that can be non-log-concave. At the core of our approach is a novel conductance analysis of SGLD using an auxiliary time-reversible Markov Chain.
  arXiv  Detail & Related papers  (2020-10-19T15:23:18Z)
• Convergence of Langevin Monte Carlo in Chi-Squared and Renyi Divergence [8.873449722727026]
  We show that the rate estimate $widetildemathcalO(depsilon-1)$ improves the previously known rates in both of these metrics. In particular, for convex and firstorder smooth potentials, we show that LMC algorithm achieves the rate estimate $widetildemathcalO(depsilon-1)$ which improves the previously known rates in both of these metrics.
  arXiv  Detail & Related papers  (2020-07-22T18:18:28Z)
• Kernel-Based Reinforcement Learning: A Finite-Time Analysis [53.47210316424326]
  We introduce Kernel-UCBVI, a model-based optimistic algorithm that leverages the smoothness of the MDP and a non-parametric kernel estimator of the rewards. We empirically validate our approach in continuous MDPs with sparse rewards.
  arXiv  Detail & Related papers  (2020-04-12T12:23:46Z)
• Spectral density estimation with the Gaussian Integral Transform [91.3755431537592]
  spectral density operator $hatrho(omega)=delta(omega-hatH)$ plays a central role in linear response theory. We describe a near optimal quantum algorithm providing an approximation to the spectral density.
  arXiv  Detail & Related papers  (2020-04-10T03:14:38Z)
• Optimal Epoch Stochastic Gradient Descent Ascent Methods for Min-Max Optimization [61.66927778694731]
  Epoch gradient descent method (a.k.a. Epoch-GD) proposed by Hazan and Kale (2011) was deemed a breakthrough for strongly convex minimization. Our result is the first one that shows Epoch-GDA can achieve the optimal rate of $O (1/T)$ for the duality gap of SCSC min-max problems.
  arXiv  Detail & Related papers  (2020-02-13T02:16:57Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.