Research map / Probabilistic and scientific modeling / Variational and generative sampling

Provable Benefit of Annealed Langevin Monte Carlo for Non-log-concave Sampling

ICLR 2025 · Probabilistic and scientific modeling › Variational and generative sampling · approach: Hamiltonian Monte Carlo

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 the first non-asymptotic KL oracle-complexity bound for annealed Langevin Monte Carlo on non-log-concave targets, using Girsanov and optimal-transport action, with no isoperimetry assumption.

Problem

Sampling from non-log-concave, multimodal densities with smooth potentials; existing annealed MCMC has no quantitative guarantees, and LMC mixing can be exponential in mode separation.

Approach

Bounds the KL error of annealed LD/LMC via Girsanov against a reference process that tracks a curve of interpolating measures, with complexity governed by the Wasserstein action of the curve rather than LSI/PI constants; uses a single LMC step per annealing stage with an exponential integrator.

Key results

• Oracle complexity of annealed LMC is Õ(dβ²A²/ε⁶) for KL accuracy ε², versus exponential e^{Θ(βr²)} for standard LMC on two-mode Gaussian mixtures.
• For a two-component Gaussian mixture, the total complexity for TV accuracy ε is Õ(d³β²r⁴(r⁴β²∨d²)ε⁻⁶), polynomial in r.
• Numerical experiment on a 6-Gaussian mixture shows near-linear log-log growth of iterations with r, consistent with polynomial dependence.

Measured effects reported in the paper

Surprising findings

• Only a single LMC step per annealing stage is needed when T is large and steps are small, rather than multiple steps per intermediate distribution.

Limitations

• Worse epsilon dependence (ε⁻⁶) than LMC under strong log-concavity.
• Assumes a known global minimizer location with bounded norm R and smooth potential.
• Experiments are small-scale numerical checks on a toy mixture.

Experimental setup

Benchmarks: mixture of 6 Gaussians (synthetic)

Metrics: iterations to reach KL 0.2 and 0.1

Baselines: LMC Proximal Sampler STLMC RDMC RS-DMC ZOD-MC

Builds on: Langevin Monte Carlo Girsanov theorem Benamou-Brenier formula simulated tempering

Closest papers by meaning

• The Randomized Midpoint Method for Log-Concave Sampling (NeurIPS 2019 · similarity 0.90)
• Langevin Monte Carlo for strongly log-concave distributions: Randomized midpoint revisited (ICLR 2024 · similarity 0.90)
• Double-Loop Unadjusted Langevin Algorithm (ICML 2020 · similarity 0.89)
• 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.89)
• Zeroth-Order Sampling Methods for Non-Log-Concave Distributions: Alleviating Metastability by Denoising Diffusion (NeurIPS 2024 · similarity 0.88)
• Chain of Log-Concave Markov Chains (ICLR 2024 · similarity 0.87)