Source-linked AI summary
Sampling from a log-concave distribution with Projected Langevin Monte Carlo
Sébastien Bubeck, Ronen Eldan, Joseph Lehec
TL;DR
Sampling from compactly supported log-concave measures is complicated by boundary reflection and the lack of curvature in the potential. The paper analyzes projected Langevin Monte Carlo, establishing total-variation sampling guarantees through reflected-process and discretization arguments, while leaving sharper polynomial dependencies and SGLD analysis open.
Problem
The paper studies sampling from a measure on a convex body with a smooth convex potential, where boundary reflection and the constant-potential case create analytical challenges.
Method
The paper views projected LMC as a discretization of reflected Brownian motion with drift, then combines coupling-based mixing analysis with Wasserstein-to-total-variation bounds.
Results
Theorem 1 provides a total-variation sampling guarantee under a specified step size and iteration count, including the uniform-target case.
Takeaways & Limitations
For the reflected Brownian motion, the paper obtains a mixing-time bound τ_mix ≤ 2R^2 and uses it to derive total-variation control for the chain.
Takeaways & Limitations
The paper leaves improving the polynomial dependence on dimension and inverse accuracy, as well as analyzing SGLD and its refinements, for future work.
Abstract
from arXiv · showhide
We extend the Langevin Monte Carlo (LMC) algorithm to compactly supported measures via a projection step, akin to projected Stochastic Gradient Descent (SGD). We show that (projected) LMC allows to sample in polynomial time from a log-concave distribution with smooth potential. This gives a new Markov chain to sample from a log-concave distribution. Our main result shows in particular that when the target distribution is uniform, LMC mixes in $\tilde{O}(n^7)$ steps (where $n$ is the dimension). We also provide preliminary experimental evidence that LMC performs at least as well as hit-and-run, for which a better mixing time of $\tilde{O}(n^4)$ was proved by Lov{á}sz and Vempala.
1 Introduction
The paper studies projected Langevin Monte Carlo for sampling log-concave measures on compact convex bodies, connecting the chain to projected SGD and reflected diffusions. Its analysis establishes polynomial-time sampling guarantees while addressing projection-induced boundary effects.
- Problem: The target measure is supported on a convex body K containing a radius-r Euclidean ball and contained in a radius-R Euclidean ball, with a convex, L-Lipschitz, β-smooth potential.The potential has Lipschitz-bounded gradients and the chain uses projection onto K.
- Method: The proposed Markov chain uses a stepsize η, independent standard Gaussian noise, projection onto K, and initialization X0 = 0.The chain is motivated by projected stochastic gradient updates, but its noise variance equals the stepsize.
- Results: For uniform targets, the main theorem guarantees TV(XN, µ) ≤ ε when η = eΘ(R^2/N) and N satisfies the theorem’s stated condition.The uniform distribution corresponds to a constant potential, an important case because the constrained diffusion lacks potential curvature.
- Context: Existing chains such as hit-and-run use zeroth-order potential access, whereas the proposed LMC chain uses a first-order oracle for ∇f(x).The paper positions this oracle distinction as a comparatively neglected issue in polynomial-time sampling.
- Analysis: The constrained chain is analyzed as a discretization of reflected Brownian motion with drift, whose boundary behavior introduces a Tanaka drift.The analysis uses coupling for the continuous process and geometric control of the discretization error.
- Analysis: The discretized and continuous processes are connected by first proving Wasserstein closeness and then deriving a total-variation bound for reflected Brownian motion with drift.This avoids directly applying Girsanov’s formula, which is obstructed by the Tanaka drift.
2 The constant potential case
For a constant potential, projected LMC is analyzed through reflected Brownian motion in a convex set. The section bounds discretization error and mixing, then converts these estimates into total-variation control toward the uniform stationary measure.
- Reflected Brownian motion: For constant f, the target is uniform on K, and the projected chain can be viewed as the reflection of a discretized Brownian motion.The discrete update is x_k+1 = P_K(x_k + g_k), while the continuous process remains in K through boundary reflection.
- Reflected Brownian motion: The Skorokhod construction represents reflection through a boundary local time supported where the process lies on ∂K.Tanaka’s construction gives existence and uniqueness for reflected paths in convex sets.
- Discretization: The discretization analysis compares reflected Brownian motion with the reflection of discretized Brownian motion and bounds their average distance.The comparison uses a stability lemma for Skorokhod problems, estimates of local time, and martingale inequalities.
- Mixing: The reflected Brownian motion has the uniform measure on K as a stationary and reversible distribution.Its generator is (1/2)∆ with Neumann boundary conditions, and Stokes’ formula identifies the normalized uniform measure as stationary.
- Mixing: Coupling by reflection yields mixing-time bounds for the reflected process, including exponential decay after the mixing time scale is reached.The section combines bounds from arbitrary starting points with the diameter R and related geometric quantities.
- Main result: The continuous-process estimates are combined with discretization and total-variation bounds to show that the projected chain is within ε of the uniform measure after the stated number of steps.The proof uses the displayed step-size relation and concludes directly that TV(X_N, µ) is at most ε.
3 The general case
The general case analyzes projected LMC through a reflected diffusion and bounds how its discretization approaches the target distribution. Convexity, coupling, change of measure, and boundary estimates yield mixing and total-variation guarantees.
- Continuous process: The reflected diffusion has the target measure μ as its unique stationary and reversible distribution.This follows from its generator with Neumann boundary condition and Stokes’ formula.
- Mixing time: Convexity of f preserves the mixing-time estimate established for the reflected diffusion.A reflection coupling of two reflected diffusions supplies the required contraction argument.
- Boundary control: The proof handles boundary reflection by coupling processes, estimating boundary-hitting behavior, and controlling Brownian motion with bounded drift.The potential assumptions provide |∇f(x)| ≤ L and β-smoothness throughout K.
- Final estimate: Combining the estimates yields a total-variation bound for the projected chain after time T+S, with step size η chosen sufficiently small.The resulting bound depends on W(T), dimension-dependent terms, and exponential decay in T.
4 Experiments
The experiments compare hit-and-run and LMC within a volume-estimation algorithm on boxes and box-and-ball bodies. LMC and hit-and-run produced similar volume estimates, while LMC was almost always slightly faster.
- Experimental setup: The volume algorithm was tested with hit-and-run and LMC on boxes and box-and-ball convex bodies across dimensions n = 10 × k, k = 1, …, 10.Volumes were normalized separately for the two body families, and termination time was recorded.
- Results: LMC and hit-and-run roughly computed similar normalized volumes, with hit-and-run slightly more accurate.The comparison used the reported normalized volume estimates for both body families.
- Results: LMC was almost always a bit faster than hit-and-run in these experiments.The authors describe the results as encouraging but preliminary.
- Limitations: More extensive experiments are needed to determine whether LMC is a practical competitor to hit-and-run.The reported evidence is limited to the tested volume-estimation settings.