Poisson Midpoint Method for Log Concave Sampling: Beyond the Strong Error Lower Bounds

• URL: http://arxiv.org/abs/2506.07614v2
• Date: Mon, 14 Jul 2025 16:39:03 GMT
• Title: Poisson Midpoint Method for Log Concave Sampling: Beyond the Strong Error Lower Bounds
• Authors: Rishikesh Srinivasan, Dheeraj Nagaraj,
• Abstract summary: We study the problem of sampling from strongly log-concave distributions over $mathbbRd$ using the midpoint discretization for overdamped/underdamped Langevin dynamics.<n>We prove its convergence in the 2-Wasserstein distance ($W$), achieving a cubic speedup in dependence on the target accuracy ($epsilon$) over the Euler-Maruyama discretization.<n> Notably, in the case of underdamped Langevin dynamics, we demonstrate the complexity of $W$ convergence is much smaller than the complexity lower bounds for convergence in $L2$
• Score: 6.138671548064356
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of sampling from strongly log-concave distributions over $\mathbb{R}^d$ using the Poisson midpoint discretization (a variant of the randomized midpoint method) for overdamped/underdamped Langevin dynamics. We prove its convergence in the 2-Wasserstein distance ($W_2$), achieving a cubic speedup in dependence on the target accuracy ($\epsilon$) over the Euler-Maruyama discretization, surpassing existing bounds for randomized midpoint methods. Notably, in the case of underdamped Langevin dynamics, we demonstrate the complexity of $W_2$ convergence is much smaller than the complexity lower bounds for convergence in $L^2$ strong error established in the literature.

Related papers

• Polynomial time sampling from log-smooth distributions in fixed dimension under semi-log-concavity of the forward diffusion with application to strongly dissipative distributions [9.48556659249574]
  We provide a sampling algorithm with complexity in fixed dimension.<n>We prove that our algorithm achieves an expected $epsilon$ error in $KL$ divergence.<n>As an application, we derive an exponential complexity improvement for the problem of sampling from an $L$-log-smooth distribution.
  arXiv  Detail & Related papers  (2024-12-31T17:51:39Z)
• Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
  Recent studies show that a reproducing kernel Hilbert space (RKHS) is not a suitable space to model functions by neural networks. In this paper, we study a suitable function space for over- parameterized two-layer neural networks with bounded norms.
  arXiv  Detail & Related papers  (2024-04-29T15:04:07Z)
• 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)
• Langevin Monte Carlo for strongly log-concave distributions: Randomized midpoint revisited [4.551456632596834]
  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.
  arXiv  Detail & Related papers  (2023-06-14T13:18:09Z)
• 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)
• Hessian Averaging in Stochastic Newton Methods Achieves Superlinear Convergence [69.65563161962245]
  We consider a smooth and strongly convex objective function using a Newton method. We show that there exists a universal weighted averaging scheme that transitions to local convergence at an optimal stage.
  arXiv  Detail & Related papers  (2022-04-20T07:14:21Z)
• A Law of Robustness beyond Isoperimetry [84.33752026418045]
  We prove a Lipschitzness lower bound $Omega(sqrtn/p)$ of robustness of interpolating neural network parameters on arbitrary distributions. We then show the potential benefit of overparametrization for smooth data when $n=mathrmpoly(d)$. We disprove the potential existence of an $O(1)$-Lipschitz robust interpolating function when $n=exp(omega(d))$.
  arXiv  Detail & Related papers  (2022-02-23T16:10:23Z)
• Unadjusted Langevin algorithm for sampling a mixture of weakly smooth potentials [0.0]
  We prove convergence guarantees under Poincar'e inequality or non-strongly convex outside the ball. We also provide convergence in $L_beta$-Wasserstein metric for the smoothing potential.
  arXiv  Detail & Related papers  (2021-12-17T04:10:09Z)
• 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)
• Wasserstein distance estimates for the distributions of numerical approximations to ergodic stochastic differential equations [0.3553493344868413]
  We study the Wasserstein distance between the in distribution of an ergodic differential equation and the distribution in the strongly log-concave case. This allows us to study in a unified way a number of different approximations proposed in the literature for the overdamped and underdamped Langevin dynamics.
  arXiv  Detail & Related papers  (2021-04-26T07:50:04Z)
• 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.