Resolving the Mixing Time of the Langevin Algorithm to its Stationary Distribution for Log-Concave Sampling

• URL: http://arxiv.org/abs/2210.08448v1
• Date: Sun, 16 Oct 2022 05:11:16 GMT
• Title: Resolving the Mixing Time of the Langevin Algorithm to its Stationary Distribution for Log-Concave Sampling
• Authors: Jason M. Altschuler and Kunal Talwar
• Abstract summary: This paper characterizes the mixing time of the Langevin Algorithm to its stationary distribution. We introduce a technique from the differential privacy literature to the sampling literature.
• Score: 34.66940399825547
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Sampling from a high-dimensional distribution is a fundamental task in statistics, engineering, and the sciences. A particularly canonical approach is the Langevin Algorithm, i.e., the Markov chain for the discretized Langevin Diffusion. This is the sampling analog of Gradient Descent. Despite being studied for several decades in multiple communities, tight mixing bounds for this algorithm remain unresolved even in the seemingly simple setting of log-concave distributions over a bounded domain. This paper completely characterizes the mixing time of the Langevin Algorithm to its stationary distribution in this setting (and others). This mixing result can be combined with any bound on the discretization bias in order to sample from the stationary distribution of the continuous Langevin Diffusion. In this way, we disentangle the study of the mixing and bias of the Langevin Algorithm. Our key insight is to introduce a technique from the differential privacy literature to the sampling literature. This technique, called Privacy Amplification by Iteration, uses as a potential a variant of R\'enyi divergence that is made geometrically aware via Optimal Transport smoothing. This gives a short, simple proof of optimal mixing bounds and has several additional appealing properties. First, our approach removes all unnecessary assumptions required by other sampling analyses. Second, our approach unifies many settings: it extends unchanged if the Langevin Algorithm uses projections, stochastic mini-batch gradients, or strongly convex potentials (whereby our mixing time improves exponentially). Third, our approach exploits convexity only through the contractivity of a gradient step -- reminiscent of how convexity is used in textbook proofs of Gradient Descent. In this way, we offer a new approach towards further unifying the analyses of optimization and sampling algorithms.

Related papers

• High-accuracy sampling from constrained spaces with the Metropolis-adjusted Preconditioned Langevin Algorithm [12.405427902037971]
  We propose a first-order sampling method for approximate sampling from a target distribution whose support is a proper convex subset of $mathbbRd$. Our proposed method is the result of applying a Metropolis-Hastings filter to the Markov chain formed by a single step of the preconditioned Langevin algorithm.
  arXiv  Detail & Related papers  (2024-12-24T23:21:23Z)
• An Improved Analysis of Langevin Algorithms with Prior Diffusion for Non-Log-Concave Sampling [27.882407333690267]
  We show that modified Langevin algorithm with prior diffusion can converge dimension independently for strongly log-concave target distributions. We also prove that the modified Langevin algorithm can also obtain the dimension-independent convergence of KL divergence with different step size schedules.
  arXiv  Detail & Related papers  (2024-03-10T11:50:34Z)
• Fast sampling from constrained spaces using the Metropolis-adjusted Mirror Langevin algorithm [12.405427902037971]
  We propose a new method for approximate sampling from distributions whose support is a compact and convex set. This algorithm adds an accept-reject filter to the Markov chain induced by a single step of the Mirror Langevin. We obtain an exponentially better dependence on the error tolerance for approximate constrained sampling.
  arXiv  Detail & Related papers  (2023-12-14T11:11:58Z)
• 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)
• Accelerated Bayesian imaging by relaxed proximal-point Langevin sampling [4.848683707039751]
  This paper presents a new accelerated proximal Markov chain Monte Carlo methodology to perform Bayesian inference in imaging inverse problems. For models that are smooth or regularised by Moreau-Yosida smoothing, the midpoint is equivalent to an implicit discretisation of an overdamped Langevin diffusion. For targets that are $kappa$-strongly log-concave, the provided non-asymptotic convergence analysis also identifies the optimal time step.
  arXiv  Detail & Related papers  (2023-08-18T10:55:49Z)
• Adaptive Annealed Importance Sampling with Constant Rate Progress [68.8204255655161]
  Annealed Importance Sampling (AIS) synthesizes weighted samples from an intractable distribution. We propose the Constant Rate AIS algorithm and its efficient implementation for $alpha$-divergences.
  arXiv  Detail & Related papers  (2023-06-27T08:15:28Z)
• Decomposed Diffusion Sampler for Accelerating Large-Scale Inverse Problems [64.29491112653905]
  We propose a novel and efficient diffusion sampling strategy that synergistically combines the diffusion sampling and Krylov subspace methods. Specifically, we prove that if tangent space at a denoised sample by Tweedie's formula forms a Krylov subspace, then the CG with the denoised data ensures the data consistency update to remain in the tangent space. Our proposed method achieves more than 80 times faster inference time than the previous state-of-the-art method.
  arXiv  Detail & Related papers  (2023-03-10T07:42:49Z)
• Convergence of the Riemannian Langevin Algorithm [10.279748604797911]
  We study the problem of sampling from a distribution with density $nu$ with respect to the natural measure on a manifold with metric $g$. A special case of our approach is sampling isoperimetric densities restricted to polytopes defined by the logarithmic barrier.
  arXiv  Detail & Related papers  (2022-04-22T16:56:00Z)
• 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)
• Differentiable Annealed Importance Sampling and the Perils of Gradient Noise [68.44523807580438]
  Annealed importance sampling (AIS) and related algorithms are highly effective tools for marginal likelihood estimation. Differentiability is a desirable property as it would admit the possibility of optimizing marginal likelihood as an objective. We propose a differentiable algorithm by abandoning Metropolis-Hastings steps, which further unlocks mini-batch computation.
  arXiv  Detail & Related papers  (2021-07-21T17:10:14Z)
• 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)

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.