PaperlayerView exact revision on arXiv

Source-linked AI summary

Log-concave sampling: Metropolis-Hastings algorithms are fast

Raaz Dwivedi, Yuansi Chen, Martin J. Wainwright, Bin Yu

arXiv:1801.02309v4stat.MLstat.CO

TL;DR

The paper asks how quickly one can sample from strongly log-concave densities while controlling total-variation error. It analyzes MALA and MRW through proposal-and-accept-reject chains, obtaining faster explicit bounds for MALA than ULA and supporting them numerically.

  • Problem

    The paper addresses the need for explicit mixing-time dependence on dimension and error tolerance when comparing Langevin-type sampling algorithms.

  • Method

    The paper analyzes MALA and MRW as proposal steps followed by Metropolis-Hastings accept-reject steps, alongside numerical experiments.

  • Results

    For smooth strongly log-concave densities, MALA has mixing-time scaling κd log(1/δ), versus κ^2d/δ^2 for ULA; MRW is O(κ) slower than MALA.

  • Takeaways & Limitations

    Metropolis-Hastings adjustment is practically useful because the adjusted algorithms mix significantly faster than the corresponding algorithms without it.

  • Takeaways & Limitations

    The comparisons are based on upper bounds, and the simulations indicate that larger step sizes may yield faster mixing than those used in theorem statements.

Abstract

from arXiv · show

We consider the problem of sampling from a strongly log-concave density in $\mathbb{R}^d$, and prove a non-asymptotic upper bound on the mixing time of the Metropolis-adjusted Langevin algorithm (MALA). The method draws samples by simulating a Markov chain obtained from the discretization of an appropriate Langevin diffusion, combined with an accept-reject step. Relative to known guarantees for the unadjusted Langevin algorithm (ULA), our bounds show that the use of an accept-reject step in MALA leads to an exponentially improved dependence on the error-tolerance. Concretely, in order to obtain samples with TV error at most $δ$ for a density with condition number $κ$, we show that MALA requires $\mathcal{O} \big(κd \log(1/δ) \big)$ steps, as compared to the $\mathcal{O} \big(κ^2 d/δ^2 \big)$ steps established in past work on ULA. We also demonstrate the gains of MALA over ULA for weakly log-concave densities. Furthermore, we derive mixing time bounds for the Metropolized random walk (MRW) and obtain $\mathcal{O}(κ)$ mixing time slower than MALA. We provide numerical examples that support our theoretical findings, and demonstrate the benefits of Metropolis-Hastings adjustment for Langevin-type sampling algorithms.

1. Introduction

The paper studies explicit mixing-time guarantees for Metropolis-adjusted samplers targeting log-concave densities, addressing limitations of existing non-explicit or biased analyses. Its main comparison shows faster best-known upper bounds for MALA than ULA, with additional results for MRW and weakly log-concave targets.

  • Motivation: Fixed-step ULA can remain asymptotically biased because it lacks a Metropolis-Hastings correction.The resulting chain may fail to converge to the target stationary distribution.
  • Contributions: The paper provides explicit total-variation mixing-time upper bounds for MALA under general log-concave distributions.Earlier MALA guarantees were described as non-explicit, restricted, or expressed in modified Wasserstein distance.
  • Additional result: A second contribution gives explicit non-asymptotic mixing-time bounds for the zeroth-order Metropolized random walk.Both MALA and MRW use accept-reject steps and converge to their target distributions in the infinite-step limit.
  • Main result: κd log(1/δ) is the MALA mixing-time scaling for smooth strongly log-concave densities, versus κ^2d/δ^2 for ULA.The comparison concerns the best-known upper bounds for obtaining δ-accurate samples.
  • Main result: MALA can use a larger step size because its Metropolis adjustment removes the limiting discretization bias, whereas ULA must control that bias with a smaller step size.This mechanism is presented as explaining MALA’s relative speed-up.

2. Background and problem set-up

The paper formulates MCMC convergence through Markov-chain proposals, stationary distributions, and total-variation mixing time, then reviews random-walk and Langevin methods. The central distinction is that Metropolis-Hastings correction restores the target stationary distribution, unlike unadjusted discretization.

  • Markov-chain framework: MCMC constructs a Markov chain with a stationary distribution equal or close to the target, then simulates it for a prescribed number of steps.Mixing-time analysis determines how many steps are needed for a δ-accurate sample.
  • Markov-chain framework: The δ-mixing time is the minimum number of steps needed to reach within δ of the target in total variation from a specified initial distribution.The definition applies for δ in (0,1).
  • Langevin methods: The Langevin proposal is N(x − h∇f(x), 2hI_d), combining a gradient-driven move with Gaussian noise.The step size h is chosen suitably.
  • Proposal classes: Zeroth-order methods query density values, whereas first-order methods additionally use gradient information.MRW is presented as a zeroth-order method, while Langevin methods use gradients of f.
  • ULA: ULA is the forward-Euler discretization of Langevin diffusion, but its stationary distribution can differ from the target and may fail to exist for poorly chosen step sizes.Careful choices of step size and iteration count yield non-asymptotic approximation guarantees.
  • MALA: MALA uses the same Langevin proposal followed by a Metropolis-Hastings accept-reject step, ensuring convergence to the target distribution Π.The paper also adapts MALA for smooth but not strongly convex objectives and compares its rate with ULA.

3. Main results

The paper gives explicit mixing-time bounds for MALA and MRW, including warm-start and practical initialization results for strongly and weakly log-concave targets. MALA improves the known ULA dependence on error tolerance, while MRW is slower by a factor of O(κ).

  • Scope: The results cover MALA and MRW mixing times for strongly log-concave densities, with additional bounds for weakly log-concave densities.The analysis includes warm starts and feasible starting distributions, including an approximately known mode and smoothness upper bound.
  • MALA from warm starts: O(dκ log(1/δ)) is the MALA mixing-time scaling when r(δ/2β) is treated as constant, with linear dependence on dimension.The bound applies for strongly log-concave targets from a β-warm start under the stated step-size choice.
  • Comparison with ULA: MALA has exponentially better dependence on δ and better dependence on κ than the O(κ^2d/δ^2) ULA bound.The paper states that MALA retains linear dependence on d while improving the known ULA upper bound.
  • MRW: O(κ) is the extra factor in MRW’s mixing-time bound relative to MALA.The paper relates this gap to MRW using function values while MALA uses first-order information, and identifies possible improvement as future work.
  • Feasible initialization: A feasible start is obtained from the Gaussian μ⋆ = N(x⋆, L^-1I_d), whose warmness is bounded using the condition number κ = L/m.The paper also analyzes a proxy start with an approximate mode and an upper bound on L; the resulting MALA bound increases additively, with an O((L̃/L · ε/d))-fraction increase relative to μ⋆.
  • Feasible initialization: Gradient descent can compute an ε-approximate mode in O(κ log(1/ε)) gradient evaluations when gradient information is available.This supports constructing practical initial distributions when exact parameters are unavailable.

4. Numerical experiments

The experiments compare ULA, MALA, and MRW across Gaussian, weakly log-concave, Gaussian-mixture, and logistic-regression settings using several convergence diagnostics. Overall, MALA shows faster empirical convergence, while warmness and step-size choices materially affect interpretation.

  • Experiment setup: Four experiments examine multivariate Gaussian sampling, Gaussian-mixture sampling, Bayesian logistic-regression inference, and step-size effects on acceptance.Diagnostics include quantile errors, discretized TV error, MAP-estimate error, trace plots, and autocorrelation plots.
  • 4.1.1 Strongly log-concave density: 0.84, 1.01, and 0.97 are the observed dimension-dependence slopes for MALA, ULA, and MRW, respectively, in the non-isotropic Gaussian experiment.The covariance condition number is fixed at κ = 4, with approximate mixing times averaged over 10 independent runs.
  • 4.1.1 Strongly log-concave density: 2.23 versus 0.33 is the observed inverse-error slope for ULA versus both MALA and MRW, suggesting 1/δ^2 for ULA and log(1/δ) for the Metropolis-adjusted chains.The comparison uses log-log regressions of approximate mixing time against 1/δ.
  • 4.1.2 Weakly log-concave density: MALA and MRW are evaluated on a Gaussian with λmax(Σ) = 1000 and λmin(Σ) = 1 to mimic weak log-concavity.The approximate mixing time is the first iteration at which the 75% quantile error in a selected direction falls below δ.
  • 4.1.3 Warmness in simulations: The simulations use a non-warm initial distribution with β = O(e^d), yet observed mixing times are d times faster than the corresponding Corollary 1 bounds.The authors suggest those bounds may improve by a factor of d.
  • 4.2 Behavior for Gaussian mixture distribution: ULA converges significantly slower than MALA on the Gaussian mixture; smaller ULA steps slow convergence, while larger steps increase asymptotic bias.Trace plots and autocorrelation plots likewise report faster stabilization or greater efficiency for MALA than for ULA and MRW.

5. Proofs

The paper’s proofs use conductance-based arguments and organize the main convergence results around three auxiliary lemmas.

  • The proof section introduces conductance bounds before stating three auxiliary lemmas supporting the main theorems.
  • Theorem 1 is proved first after the auxiliary lemmas are introduced.
  • Sections 5.3–5.5 prove the three key lemmas, followed by the proof of Theorem 2 in Section 5.6.

5.1 Conductance bounds and auxiliary results

This section develops conductance tools and auxiliary results for analyzing MALA, including concentration, flow, and proposal regularity inside a high-probability region.

  • Conductance bounds: The analysis uses s-conductance to quantify probability flow across disjoint sets relative to stationary mass.
  • Conductance bounds: A conductance mixing bound for reversible lazy chains with β-warm starts motivates lower-bounding Φs and optimizing s.
  • Auxiliary results: Strongly log-concave distributions concentrate around their mode inside a Euclidean ball with high stationary probability.
  • Auxiliary results: A flow lemma lower-bounds transitions when nearby points have sufficiently close transition distributions.
  • MALA-specific properties: MALA proposals are close at nearby points, and its accept-reject step is well behaved inside the truncated ball for suitable step sizes.

5.2 Proof of Theorem 1

The proof of Theorem 1 combines local MALA regularity, a high-probability region, and conductance optimization to obtain the claimed mixing-time bound.

  • The proof first establishes favorable MALA-update properties inside a high-probability region using Lemma 3.
  • The transition distributions at nearby points are controlled by combining proposal bounds with an accept-reject error bound.
  • These local transition controls yield a lower bound on the s-conductance of MALA.
  • Choosing s, ϵ, and h appropriately and applying the convergence rate completes the stated mixing-time bound.

5.3 Proof of Lemma 1

Lemma 1 constructs a high-probability Euclidean region around the mode by combining sub-Gaussian concentration with a bound on the mean–mode distance.

  • The proof establishes sub-Gaussianity of the target distribution and then uses concentration around its mean.
  • Hargé’s result transfers Gaussian convex-function bounds to the strongly log-concave target representation.
  • Standard quadratic-form tail bounds produce a high-probability ball around the mean.
  • A bound on the distance between the mean and mode expands this region to a ball around the mode.

5.4 Proof of Lemma 2

The proof establishes the conductance ingredient for log-concave sampling by truncating the target distribution and partitioning the state space into cases. An isoperimetric inequality supplies the key separation bound.

  • Isoperimetric setup: The proof applies a log-concave isoperimetric inequality to the truncated distribution ΠK.The truncated density is represented as a product of log-concave functions and a Gaussian density, enabling the inequality with σ = 1/√m.
  • Case analysis: The two cases are mutually exclusive and cover all possibilities for the masses of A′1 and A′2.One case occurs when at least one set has sufficiently small mass; the complementary case assumes both have at least half the corresponding partition mass.
  • Conclusion: The inequalities for the two cases combine to establish the conductance claim (24).The second case follows by combining inequalities (40), (41), and (42), while the first is handled directly from the set-mass assumption.
  • Partition of the state space: The sets A1 and A2 partition Rd, while A′1, A′2, and A′3 divide the truncated region K for the case analysis.Figure 11 illustrates the partition, and A′3 is the portion of K outside A′1 ∪ A′2.
  • Transition bounds: The proof uses stationarity and complementary-set identities to relate transition probabilities across A1 and A2.For u and v in K, the separation assumption provides a distance lower bound used in the conductance argument.

5.5 Proof of Lemma 3

The proof bounds the local discrepancy between Gaussian proposal distributions and controls MALA acceptance probabilities. Smoothness, strong convexity, Gaussian concentration, and Pinsker’s inequality yield the required claims.

  • Proposal comparison: Pinsker’s inequality converts a Kullback–Leibler bound between Gaussian proposals into a total variation bound.The proposal distributions share covariance, so their KL divergence depends on the difference between their means.
  • Regularity bounds: The Hessian sandwich mI_d ⪯ ∇^2f(z) ⪯ LI_d controls the proposal mean differences through strong convexity and smoothness.The operator norm is used to bound the relevant matrix expressions.
  • Acceptance ratio: The MALA accept-reject ratio is expressed using the target density and forward and reverse proposal densities.The proposal from x is N(x − h∇f(x), 2hI_d), and the proof lower-bounds the log ratio by decomposing it into terms M1, M2, and M3.
  • Exponent control: Strong convexity and smoothness provide lower bounds for the terms governing the acceptance-ratio exponent.The proof separately bounds M1, M2, and M3 before combining the resulting inequalities.
  • High-probability acceptance: The acceptance ratio is bounded below with high probability by controlling Gaussian noise and the proposal displacement.A suitable step-size condition gives T ≥ −ϵ/16 with probability at least 1 − ϵ/16, implying an exponential lower bound on acceptance.
  • Conclusion: Substituting the acceptance lower bound into the total variation estimate completes the proof of the claim.The bound α = exp(−ϵ/16) and exp(−ϵ/16) ≥ 1 − ϵ/16 are used in the final step.

5.6 Proof of Theorem 2

The proof derives the MRW mixing bound by controlling proposal overlap and conductance under the relevant step-size restriction. Gaussian proposal comparisons and concentration bounds support the final convergence estimate.

  • Proof strategy: The proof follows the structure of the earlier MALA theorem while establishing high-probability bounds for MRW proposals.It begins by stating claims that control the transition behavior needed for the conductance argument.
  • Proposal distribution: The MRW proposal is Gaussian with mean x and covariance 2hI_d.Pinsker’s inequality and the Gaussian KL expression are used to bound proposal differences.
  • Concentration control: Gaussian tail bounds control the noise terms and the scalar χ involving the gradient and proposal noise.The argument uses χ ∼ N(0, ∥∇f(x)∥_2^2) together with chi-squared tail bounds.
  • Conclusion: The resulting inequalities imply the required bound and yield the claimed MRW mixing-time estimate.The proof combines the high-probability control of f(x) − f(z) with the convergence rate (22).

6. Discussion

The discussion summarizes explicit mixing-time results for MALA and MRW and emphasizes the practical value of Metropolis-Hastings adjustment. It also identifies open questions about step sizes, method classes, and comparisons with HMC.

  • Main results: For strongly log-concave targets, MALA and MRW receive non-asymptotic mixing-time bounds based on proposal and accept-reject phases.The discussion presents these bounds as explicit analyses for log-concave sampling.
  • Practical implication: Metropolis-Hastings adjustment is reported to make the analyzed algorithms mix significantly faster than corresponding methods without it.The stated comparison is especially with ULA for the same sampling task.
  • Scope and open questions: The results are upper bounds, and simulations suggest tightness for the step sizes used in the theorem statements.The authors note that larger step sizes might still be possible because simulations indicate limited dependence on the warmness parameter β.
  • Method-class comparison: The gap between first-order and zeroth-order sampling methods remains unresolved despite a factor-κ difference obtained in this work.The paper asks whether this factor represents a sharp separation between the two method classes.
  • Relation to HMC: HMC is described as a multi-step generalization of MALA and is reported to have superior empirical mixing across a broad class of distributions.The discussion distinguishes practical Metropolized HMC from several idealized or unadjusted theoretical analyses.

Appendix A. Some basic properties

The appendix states basic properties of strongly convex and smooth functions used in the proofs, including equivalent Hessian characterizations.

  • The appendix introduces basic properties of strongly convex and smooth functions used in the paper’s proofs.
  • Strong convexity: For twice differentiable convex f, m-strong convexity is equivalent to the Hessian bound ∇2f(x) ⪰ mI_d for every x.
  • Smoothness: For twice differentiable convex f, L-smoothness is equivalent to the Hessian bound ∇2f(x) ⪯ LI_d for every x.
Loading 1801.02309v4…