Langevin Monte Carlo for strongly log-concave distributions: Randomized midpoint revisited

• URL: http://arxiv.org/abs/2306.08494v2
• Date: Fri, 16 Jun 2023 11:32:49 GMT
• Title: Langevin Monte Carlo for strongly log-concave distributions: Randomized midpoint revisited
• Authors: Lu Yu, Avetik Karagulyan, Arnak Dalalyan
• Abstract summary: We conduct an analysis of the midpoint discretization for the vanilla Langevin process. This analysis helps to clarify the underlying principles and provides valuable insights. We establish new guarantees for the kinetic Langevin process with Euler discretization.
• Score: 4.551456632596834
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We revisit the problem of sampling from a target distribution that has a smooth strongly log-concave density everywhere in $\mathbb R^p$. In this context, if no additional density information is available, the randomized midpoint discretization for the kinetic Langevin diffusion is known to be the most scalable method in high dimensions with large condition numbers. Our main result is a nonasymptotic and easy to compute upper bound on the Wasserstein-2 error of this method. To provide a more thorough explanation of our method for establishing the computable upper bound, we conduct an analysis of the midpoint discretization for the vanilla Langevin process. This analysis helps to clarify the underlying principles and provides valuable insights that we use to establish an improved upper bound for the kinetic Langevin process with the midpoint discretization. Furthermore, by applying these techniques we establish new guarantees for the kinetic Langevin process with Euler discretization, which have a better dependence on the condition number than existing upper bounds.

Related papers

• 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)
• Parallelized Midpoint Randomization for Langevin Monte Carlo [6.555157647688725]
  Investigation focuses on target distributions characterized by smooth and strongly log-concave densities. We revisit the parallelized randomized midpoint method and employ proof techniques recently developed for analyzing its purely sequential version. We derive upper bounds on the Wasserstein distance between the sampling and target densities.
  arXiv  Detail & Related papers  (2024-02-22T10:26:46Z)
• 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)
• Sobolev Space Regularised Pre Density Models [51.558848491038916]
  We propose a new approach to non-parametric density estimation that is based on regularizing a Sobolev norm of the density. This method is statistically consistent, and makes the inductive validation model clear and consistent.
  arXiv  Detail & Related papers  (2023-07-25T18:47:53Z)
• Curvature-Independent Last-Iterate Convergence for Games on Riemannian Manifolds [77.4346324549323]
  We show that a step size agnostic to the curvature of the manifold achieves a curvature-independent and linear last-iterate convergence rate. To the best of our knowledge, the possibility of curvature-independent rates and/or last-iterate convergence has not been considered before.
  arXiv  Detail & Related papers  (2023-06-29T01:20:44Z)
• Resolving the Mixing Time of the Langevin Algorithm to its Stationary Distribution for Log-Concave Sampling [34.66940399825547]
  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.
  arXiv  Detail & Related papers  (2022-10-16T05:11:16Z)
• Convex Analysis of the Mean Field Langevin Dynamics [49.66486092259375]
  convergence rate analysis of the mean field Langevin dynamics is presented. $p_q$ associated with the dynamics allows us to develop a convergence theory parallel to classical results in convex optimization.
  arXiv  Detail & Related papers  (2022-01-25T17:13:56Z)
• 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)
• Wasserstein Control of Mirror Langevin Monte Carlo [2.7145834528620236]
  Discretized Langevin diffusions are efficient Monte Carlo methods for sampling from high dimensional target densities. We consider Langevin diffusions on a Hessian-type manifold and study a discretization that is closely related to the mirror-descent scheme.
  arXiv  Detail & Related papers  (2020-02-11T13:16:31Z)

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.