Source-linked AI summary
High-dimensional Bayesian inference via the Unadjusted Langevin Algorithm
Alain Durmus, Eric Moulines
TL;DR
The paper addresses high-dimensional sampling of a distribution known through a potential U, a problem arising in Bayesian inference and machine learning. It analyzes Euler-discretized Langevin sampling under smooth strong-convexity assumptions, deriving dimension-explicit non-asymptotic guarantees for constant and decreasing step sizes. The results cover Wasserstein and total variation convergence, weighted empirical estimation, and an application to binary regression.
Problem
The problem is to sample a high-dimensional posterior distribution π with density proportional to e^-U, supporting uncertainty quantification in Bayesian inference.
Method
The paper studies ULA, the Euler-Maruyama discretization of Langevin diffusion, with constant or decreasing step sizes and Gaussian innovations.
Results
The paper obtains explicit dimension-dependent non-asymptotic bounds for Wasserstein and total variation convergence, weighted empirical estimation, and binary-regression inference.
Takeaways & Limitations
The reported bounds improve prior total-variation and decreasing-step-size convergence rates and quantify ULA performance for high-dimensional sampling.
Takeaways & Limitations
The analysis assumes U is continuously differentiable with globally Lipschitz gradient and strongly convex, and includes a separate total-variation contraction setting.
Abstract
from arXiv · showhide
We consider in this paper the problem of sampling a high-dimensional probability distribution $π$ having a density with respect to the Lebesgue measure on $\mathbb{R}^d$, known up to a normalization constant $x \mapsto π(x)= \mathrm{e}^{-U(x)}/\int_{\mathbb{R}^d} \mathrm{e}^{-U(y)} \mathrm{d} y$. Such problem naturally occurs for example in Bayesian inference and machine learning. Under the assumption that $U$ is continuously differentiable, $\nabla U$ is globally Lipschitz and $U$ is strongly convex, we obtain non-asymptotic bounds for the convergence to stationarity in Wasserstein distance of order $2$ and total variation distance of the sampling method based on the Euler discretization of the Langevin stochastic differential equation, for both constant and decreasing step sizes. The dependence on the dimension of the state space of these bounds is explicit. The convergence of an appropriately weighted empirical measure is also investigated and bounds for the mean square error and exponential deviation inequality are reported for functions which are measurable and bounded. An illustration to Bayesian inference for binary regression is presented to support our claims.
1 Introduction
The paper develops non-asymptotic, dimension-explicit convergence guarantees for ULA when sampling strongly log-concave high-dimensional distributions. It analyzes constant and decreasing step sizes, discretization bias, weighted empirical estimates, and Bayesian binary regression.
- Bayesian inference seeks full posterior samples to quantify uncertainty and prevent overfitting, motivating high-dimensional sampling methods.
- The paper studies ULA, the Euler-Maruyama discretization of Langevin diffusion, using Gaussian innovations and constant or decreasing step sizes.
- Explicit bounds improve prior total-variation results for ULA iterates under fixed and non-increasing step sizes, with Wasserstein and total-variation guarantees.
- For fixed step sizes, achieving precision ε requires O(dε^-2) or O(dε^-1) iterations in Wasserstein or total variation, up to logarithmic factors, depending on smoothness.
- Decreasing step sizes yield convergence to π, with explicit rates for γ_k = γ_1k^-α and an optimal bound from the reported family at α = 1.
- The paper also bounds weighted empirical-estimator error and deviations, including O(dε^-4) or O(dε^-3) iteration requirements for mean-square error.
2 Non-asymptotic bounds in Wasserstein distance of order 2 for ULA
This section establishes explicit non-asymptotic W2 convergence bounds for ULA under smoothness and strong convexity, covering decreasing and constant step sizes with dimension-dependent rates.
- Langevin diffusion: Under H1 and H2, the Langevin diffusion has a unique invariant distribution π and contracts geometrically in W2.For any x,y and t>0, W2(δxPt,δyPt)≤e^-mt∥x−y∥, and convergence to π is likewise exponentially controlled.
- ULA construction: ULA uses Gaussian innovations and either constant or decreasing step sizes, forming an inhomogeneous Markov chain with kernels Rγk.For constant γ, Rγ has a unique stationary distribution πγ under the stated step-size restriction.
- Decreasing step sizes: For non-increasing step sizes, the results give explicit W2 bounds for ULA under H1 and H2, including geometric contraction and convergence to π when γk→0 and Σγk diverges.The contraction results are dimension-independent, while the iteration-complexity bounds retain explicit dependence on d and ε.
- Sharper regularity bounds: Under H3, the precision dependence improves, and when L̃=0 the dimension dependence becomes O(d^1/2 log(d)).The paper identifies non-degenerate d-dimensional Gaussian distributions as an example with L̃=0.
- Complexity: For fixed precision ε, ULA requires O(dε^-2) iterations in W2 up to logarithmic terms under H1 and H2.The paper jointly selects the step size and iteration count to meet the target precision.
- Finite horizon: With finite horizon n, choosing γ=γn yields W2 error of order O(log(n)/n), improving to O(log(n)/n)^2 when H3 holds.These bounds are obtained by optimizing the step size for the fixed computational horizon.
3 Quantitative bounds in total variation distance
This section develops non-asymptotic total-variation bounds for Langevin discretizations, using reflection coupling and semigroup regularization to treat constant and decreasing step sizes. The resulting bounds quantify discretization error and iteration complexity under assumptions on U, with improvements over earlier results in selected regimes.
- Method: Reflection coupling upper-bounds the total variation distance between two Langevin diffusions, while semigroup regularization makes bounded measurable functions Lipschitz for positive times.These ingredients support the paper’s total-variation analysis and its Bayesian application to credible regions.
- Decreasing step sizes: For decreasing step sizes γk = γ1/k^α, the total-variation error is d^1/2 O(ℓ^-α/2) for α ∈ (0,1) and d^1/2 O(ℓ^-1/2) for α = 1.The α = 1 result applies under the stated condition γ1 > 2κ^-1.
- Constant step size: For constant step size, a sufficient iteration count for total-variation precision ε is d log(d) O(|log(ε)| ε^-2) with an appropriate step size.The paper states that this matches the result obtained in.
- Constant step size: When H3 holds, the stationary discretization error improves to order d O(γ |log(γ)|), while requiring a stronger assumption than the corresponding general bound.For ˜L = 0, the bound becomes d^1/2 O(γ |log(γ)|) and is sharp up to a logarithmic factor.
- Constant step size: With H3, a suitable constant step size yields an iteration bound of order d log^2(d) O(ε^-1 log^2(ε)), improving the precision dependence of earlier bounds.For the standard Gaussian case, the paper describes the bound as sharp up to logarithmic factors in dimension and precision.
4 Mean square error and concentration for bounded measurable functions
The section analyzes weighted empirical estimators for Lipschitz and bounded measurable functions, deriving mean-square error bounds and exponential deviation inequalities for decreasing and constant step sizes.
- Estimator and error decomposition: The weighted estimator targets π(f) and its mean-square error decomposes into squared bias and variance.The bias is bounded using Wasserstein or total variation results, while variance bounds depend on the function class.
- Lipschitz functions: For Lipschitz functions, the optimal any-time rate with γk = γ1/k^α is obtained at α = 1/3.This rate coincides with the step-size rate used in prior work to derive a central limit theorem.
- Constant step sizes: Under fixed horizon, optimizing the constant step size and burn-in period gives bounds of order n^-1/2 under H1 and H2, and n^-2/3 under H1, H2 and H3.The total number of iterations n + N is held fixed in this setting.
- Bounded measurable functions: For bounded measurable functions, total-variation analysis yields fixed-step mean-square-error conclusions matching the Lipschitz case up to logarithmic terms.This function class is emphasized as relevant for estimating credibility regions in Bayesian statistics.
- Concentration: For γk = γ1k^-α with α ∈ [0,1), exponential concentration has order exp(−Cr^2γ1n^(1−α)).The constant C is independent of γ1 and n, under the stated assumptions and step-size conditions.
5 Numerical experiments
The numerical section applies ULA to Bayesian binary regression and compares its empirical posterior accuracy with Polya-Gamma Gibbs sampling and MALA across synthetic and real data settings.
- Bayesian binary regression: The binary regression model uses Gaussian priors for unknown regression coefficients and a logistic likelihood for binary observations.The posterior density is specified up to a proportionality constant.
- Polya-Gamma comparison: For a synthetic d = 5, p = 100 example, ULA is compared with Polya-Gamma Gibbs sampling using constant and decreasing step-size sequences.The experiment uses 10^8 Polya-Gamma samples and 10^3 ULA runs with 10^6 effective iterations.
- Polya-Gamma comparison: The empirical distributions in Figure 2 compare Polya-Gamma Gibbs sampling with ULA under constant γk = γ1 and decreasing γk = γ1k^-1/2 step sizes.The left and right panels correspond to the constant and decreasing schedules, respectively.
- Accuracy metric: Marginal accuracy compares each sampler’s componentwise empirical distributions with the corresponding marginal posterior distributions.The comparison is performed for every component across each data set.
- Accuracy results: Figure 3 reports mean marginal accuracy across dimensions for German, Australian, Heart disease, Pima Indian diabetes, and Musk data sets.The figure organizes these data sets across five labeled panels or positions.
6 Contraction in total variation for functional autoregressive models
This section constructs couplings for inhomogeneous functional autoregressive chains and derives dimension-independent total-variation contraction bounds under Lipschitz assumptions.
- Assumptions: The contraction analysis assumes each hk is k-Lipschitz.This is the stated AR1 condition used in the total-variation result.
- Model and coupling: The chain is an inhomogeneous Markov chain with kernels Pk, and Qn denotes the marginal distribution of Xn.The coupling construction uses kernels Kk on pairs of states.
- Total-variation contraction: The resulting upper bound for ∥δxQn − δyQn∥TV does not depend on the dimension d.The bound is obtained by controlling the probability that the coupled chains have not met.
- Model and coupling: The coupling updates combine Gaussian proposals with a Bernoulli decision and a correction map based on hk.The construction defines a transference plan between Pk(x, ·) and Pk(y, ·).
- Proof strategy: The proof uses Lindvall’s inequality and backward induction to bound the probability that Xk and Yk remain distinct.Gaussian noise properties enter through the coupling construction and Lemma 20.
A Proofs of Section 2
The appendix section collects postponed proofs for the convergence results developed in Section 2 under assumption H1.
- Proofs: Under H1, cited results establish the relevant bound for all x, y ∈ Rd.The detailed proof is postponed to the appendix material referenced by the section.
A.1 Proof of Proposition 1
The proof establishes moment control for the Langevin diffusion and uses synchronous coupling to derive Wasserstein contraction under strong convexity.
- Moment control: The generator applied to squared distance from the minimizer yields a drift inequality involving the strong-convexity constant m and dimension d.The bound is A V(x) ≤ 2(−mV(x) + d), leading through Grönwall’s inequality to a second-moment estimate.
- Moment control: Invariance of π and truncation by z ∧ c provide a uniform stationary second-moment bound of d/m.The argument uses Jensen’s inequality, dominated convergence, and monotone convergence.
- Wasserstein contraction: A coupled pair of Langevin diffusions driven by the same Brownian motion supplies a coupling between δxP_t and δyP_t.The Lipschitz condition on ∇U ensures a unique strong solution for the coupled SDE.
- Wasserstein contraction: The coupling estimate bounds W2(δxP_t, δyP_t) by the root mean square distance between the coupled processes.This follows directly from the definition of Wasserstein distance of order 2.
A.2 Proof of Proposition 2
The proof shows that the discretized Langevin kernel admits a unique stationary distribution by establishing contraction under an admissible constant step size.
- Contraction: For γ ∈ (0, 2/(m + L)), the proof derives a one-step contraction inequality around the minimizer.The restriction γ ≤ 2/(m + L) is used in the final inequality, after which induction completes the argument.
- Stationarity: The kernel Rγ has a unique stationary distribution πγ because compact sets are accessible and small for Rγ.The proof invokes a standard Markov-chain result after establishing the relevant stability estimate.
A.3 Proof of Proposition 3
The proof establishes contraction and stationary behavior for the Euler scheme, then extends the analysis to decreasing step sizes through diffusion–discretization couplings and auxiliary bounds.
- Constant step sizes: For γ ≤ 2/(m + L), Rγ is a strict contraction in W2 and has a unique invariant distribution πγ.The contraction implies uniqueness of the fixed point in P2(R^d).
- Auxiliary estimates: Moment estimates for the diffusion are obtained from strong convexity, generator inequalities, and Grönwall-type arguments.These estimates control terms involving distances from the minimizer and from arbitrary starting points.
- Constant step sizes: The proof controls discretization error by coupling the Langevin diffusion with the linear interpolation of the Euler approximation.Taking the diffusion’s initial distribution as π yields explicit Wasserstein bounds for the Euler iterates.
- Decreasing step sizes: For non-increasing step sizes with γ1 ≤ 1/(m + L), auxiliary lemmas provide almost-sure bounds for the coupled diffusion and Euler scheme.The proof applies these bounds in the same coupling framework used for constant step sizes.
- Decreasing step sizes: When step sizes decrease to zero while cumulative time diverges, the proof shows the associated error terms vanish asymptotically.The argument uses monotonicity, Cesàro convergence, and Γn → +∞.
B Proofs of Section 3
The postponed proofs derive convergence and variance bounds for ULA using Wasserstein and total-variation estimates, Gaussian Poincaré inequalities, martingale decompositions, and step-size controls.
- Convergence bounds: The total-variation arguments combine Wasserstein bounds with Pinsker’s inequality and diffusion estimates.The resulting proofs apply triangle inequalities and previously established propositions.
- Convergence bounds: For constant step size γ ≤ 1/(m + L), exponential contraction estimates are combined with Theorem 12 to obtain the stated bound.The proof uses κ ≥ 2m and the inequality 1 − t ≤ e^-t.
- Empirical measures: Gaussian Poincaré inequalities control variances because each Euler transition is Gaussian with mean y − γ∇U(y) and covariance 2γ I_d.The proof propagates Lipschitz bounds through backward functions and transition kernels.
- Empirical measures: The empirical-measure analysis represents centered additive functionals as sums of martingale increments relative to the Euler filtration.Backward functions are introduced through the Markov property to control these increments.
- Decreasing step sizes: For decreasing step sizes with γk → 0 and Γk → +∞, constants independent of the step-size sequence control the resulting bounds.The proof establishes these controls through decompositions indexed by cumulative step times.
C.3 Proof of Theorem 17
The proof establishes Laplace-transform bounds for Euler approximations and related quantities under H1 and H2, using Gaussian log-Sobolev inequalities, Lipschitz properties, and Markov's inequality. These bounds support the result for non-increasing step-size sequences.
- Laplace-transform bounds: The argument repeatedly bounds Laplace transforms of Lipschitz functions under Euler-transition distributions.The proof uses decompositions into increments and iterated bounds for the relevant transition kernels.
- Analytic bounds: Gaussian log-Sobolev inequalities provide uniform bounds for Lipschitz functions under the Gaussian Euler transition kernel.The kernel has mean x − γ∇U(x) and covariance matrix 2γ I_d.
- Completion of the proof: Proposition 32 supplies bounds for Lipschitz functions, which are combined with Markov's inequality to prove Theorem 17.The proof also decomposes bounded measurable functions into Lipschitz and bounded components before applying the resulting estimates.
D.2 Distribution of hitting time of 0 for Ornstein-Ulhenbeck processes
This section introduces the hitting time of zero for a one-dimensional Ornstein-Uhlenbeck process and states its distribution in terms of the standard normal cumulative distribution function. Several related figure files are listed as available in PNG format.
- Hitting time: The hitting time of zero is defined as T̃_0 = inf{t ≥ 0 : Ũ_t = 0}.The definition records the first time the Ornstein-Uhlenbeck process reaches zero.
- Distribution: Proposition 34 states the hitting-time distribution for a ∈ R, θ, σ > 0, and t > 0 using Φ, the standard normal cumulative distribution function.The displayed distribution formula is attributed to the cited reference.