Research map / Learning theory and algorithms / Sample complexity
Langevin Monte Carlo for strongly log-concave distributions: Randomized midpoint revisited
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives nonasymptotic, computable W2 upper bounds for randomized midpoint kinetic Langevin (RKLMC) and an improved kappa-dependence bound for Euler kinetic Langevin (KLMC) on strongly log-concave targets.
Problem
Sampling from smooth strongly log-concave densities in high dimension with large condition number; existing error bounds for randomized midpoint kinetic Langevin are loose, depend on unspecified constants, or require initialization at the minimizer and carry extra factors.
Approach
Uses a summation-by-parts argument in place of telescoping sums to remove the extra nmh factor from the discretization error of randomized midpoint methods, applies it to RLMC and RKLMC with explicit small constants, and transfers the technique to Euler KLMC to obtain a kappa^{3/2}-free-of-extra-factor improved dependence.
Key results
- RKLMC bound with explicit constants: W2 error <= 1.6 rho^n W2(nu_0,pi) + 0.1 sqrt(rho^n E[f(theta_0)-f(theta_*)]/m) + 0.2(gamma h)^3 sqrt(kappa p/m) + 10(gamma h)^{3/2} sqrt(p/m), with rho=exp(-mh), removing the extra nmh factor of prior bounds.
- KLMC (Euler) bound: W2 <= 2 rho^n W2(nu_0,pi) + 0.05 sqrt(...) + 0.9 gamma h sqrt(kappa p/m), with step gamma h = eps kappa^{-1/2} giving n ~ 5 kappa^{3/2} eps^{-1} log(20/eps) iterations.
- RKLMC corollary gives n ~ kappa eps^{-2/3}(25+3(eps^2 kappa)^{1/6}) log(20/eps) gradient-evaluation complexity, matching the best known rate.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use randomized midpoint rather than Euler discretization for kinetic Langevin | KLMC · ε=0.1, κ=10^1 | iterations: 8.4\times 10^3 -> 1.0\times 10^4 | Hurt |
| Use randomized midpoint rather than Euler discretization for kinetic Langevin | KLMC · ε=0.1, κ=10^5 | iterations: 8.4\times 10^9 -> 1.1\times 10^8 | Helped |
| Use randomized midpoint rather than Euler discretization for kinetic Langevin | KLMC · ε=0.1^3, κ=10^1 | iterations: 1.6\times 10^6 -> 4.5\times10^{5} | Helped |
| Use randomized midpoint rather than Euler discretization for kinetic Langevin | KLMC · ε=0.1^3, κ=10^5 | iterations: 1.6\times 10^{12} -> 4.5\times10^{\hphantom{0}9} | Helped |
| Use randomized midpoint rather than Euler discretization for kinetic Langevin | KLMC · ε=0.1^5, κ=10^1 | iterations: 2.3\times 10^{8\hphantom{0}} -> 1.5\times 10^{7\hphantom{0}} | Helped |
| Use randomized midpoint rather than Euler discretization for kinetic Langevin | KLMC · ε=0.1^5, κ=10^5 | iterations: 2.3\times 10^{14} -> 1.5\times 10^{11} | Helped |
| Use randomized midpoint rather than Euler discretization for vanilla Langevin | LMC · ε=0.1, κ=10^1 | iterations: 1.2\times 10^4 -> 3.6\times 10^3 | Helped |
| Use randomized midpoint rather than Euler discretization for vanilla Langevin | LMC · ε=0.1, κ=10^5 | iterations: 1.2 \times 10^8 -> 4.5\times 10^{8} | Mixed |
| Use randomized midpoint rather than Euler discretization for vanilla Langevin | LMC · ε=0.1^3, κ=10^1 | iterations: 2.2\times 10^8 -> 3.8\times 10^5 | Helped |
| Use randomized midpoint rather than Euler discretization for vanilla Langevin | LMC · ε=0.1^3, κ=10^5 | iterations: 2.2\times 10^{12} -> 2.0\times 10^{10} | Helped |
| Use randomized midpoint rather than Euler discretization for vanilla Langevin | LMC · ε=0.1^5, κ=10^1 | iterations: 3.2\times 10^{12} -> 4.6\times 10^{7\hphantom{0}} | Helped |
| Use randomized midpoint rather than Euler discretization for vanilla Langevin | LMC · ε=0.1^5, κ=10^5 | iterations: 3.2\times 10^{16} -> 9.9\times 10^{11} | Helped |
Limitations
- Requires gamma >= 5M, stronger than the gamma >= 2M used in prior KLMC analyses.
- RKLMC bound depends on initial error W2(nu_0,pi), so non-minimizer initialization makes iteration count scale polynomially in the initial error.
- Analysis uses synchronous coupling; the conjectured kappa/eps non-synchronous improvement is not proven.
Experimental setup
Metrics: W2 distance bound number of gradient evaluations
Baselines: LMC KLMC RLMC RKLMC (prior bounds)
Builds on: randomized midpoint method Langevin Monte Carlo kinetic Langevin Monte Carlo
Closest papers by meaning
- The Poisson Midpoint Method for Langevin Dynamics: Provably Efficient Discretization for Diffusion Models (NeurIPS 2024 · similarity 0.92)
- Non-asymptotic Error Bounds in $\mathcal{W}_2$-Distance with Sqrt(d) Dimension Dependence and First Order Convergence for Langevin Monte Carlo beyond Log-Concavity (ICML 2025 · similarity 0.90)
- Provable Benefit of Annealed Langevin Monte Carlo for Non-log-concave Sampling (ICLR 2025 · similarity 0.90)
- Faster Diffusion Sampling with Randomized Midpoints: Sequential and Parallel (ICLR 2025 · similarity 0.88)
- Provable Convergence and Limitations of Geometric Tempering for Langevin Dynamics (ICLR 2025 · similarity 0.88)
- Fast Non-Log-Concave Sampling under Nonconvex Equality and Inequality Constraints with Landing (NeurIPS 2025 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.