Lower Bounds on Metropolized Sampling Methods for Well-Conditioned Distributions
Year: 2022

Abstract:
We give lower bounds on the performance of two of the most popular sampling methods in practice, the Metropolis-adjusted Langevin algorithm (MALA) and multi-step Hamiltonian Monte Carlo (HMC) with a leapfrog integrator, when applied to well-conditioned distributions. Our main result is a nearly-tight lower bound of Ω̃(κd) on the mixing time of MALA from an exponentially warm start, matching a line of algorithmic results [DCWY18, CDWY19, LST20a] up to logarithmic factors and answering an open question of [CLA20]. We also show that a polynomial dependence on dimension is necessary for the relaxation time of HMC under any number of leapfrog steps, and bound the gains achievable by changing the step count. Our HMC analysis draws upon a novel connection between leapfrog integration and Chebyshev polynomials, which may be of independent interest.

heading: 1 Introduction
text: Sampling from a continuous distribution in high dimensions is a fundamental problem in algorithm design. As sampling serves as a key subroutine in a variety of tasks in machine learning [AdFDJ03], statistical methods [RC99], and scientific computing [Liu01], it is an important undertaking to understand the complexity of sampling from families of distributions arising in applications.
The more restricted problem of sampling from a particular distribution family we call “wellconditioned” has garnered a substantial amount of recent research effort from the algorithmic learning and statistics communities. This specific family is interesting for a number of reasons. First, it is practically relevant: Bayesian methods have found increasing use in machine learning applications [Bar12], and many distributions in these settings are well-conditioned, such as multivariate Gaussians, mixture models with small separation, and densities arising from Bayesian logistic regression with a Gaussian prior [DCWY18]. Moreover, for several widely-used sampler implementations in popular packages [Aba16, CGH+17], such as the Metropolis-adjusted Langevin algorithm (MALA) and Hamiltonian Monte Carlo (HMC), the target having a small condition number is in some sense a minimal assumption for known provable guarantees (discussed more thoroughly in Section 1.2).
Finally, the highly-documented success of first-order (gradient) methods in optimization [Bec17], which are particularly favorable in the well-conditioned setting, has driven interest in connections between optimization and sampling. Exploring this connection has been highly fruitful: since seminal work of [JKO98], demonstrating that the Langevin dynamics which MALA and HMC discretize has an interpretation as gradient descent on density space, a flurry of work [Dal17, CCBJ18, DCWY18, DR18, DM19, DMM19, CDWY19, CV19, SL19, MMW+19, LST20a, LST20b, CLA+20] has ob-
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
tained improved upper bounds for the mixing of various Langevin discretizations for well-conditioned sampling. Many of these works draw inspiration from first-order optimization.
On the other hand, demonstrating lower bounds on the complexity of sampling tasks (in the wellconditioned regime or otherwise) has proven remarkably challenging. To our knowledge, there are few unconditional lower bounds for sampling tasks. This is in stark contrast to the theory of optimization, where there are matching upper and lower bounds for a variety of problems and query models, such as convex optimization under first-order oracle access [Nes03]. This gap in the algorithmic theory of sampling is our primary motivation: we aim to answer the following more restricted question.
What is the complexity of the popular sampling methods, MALA and HMC, for sampling well-conditioned distributions?
The problem we study is still less general than unconditional query lower bounds for sampling, in that our lower bounds are algorithm-specific; we characterize the performance of particular sampling algorithms on a distribution family. However, we believe asking this question, and developing an understanding of it, is an important first step towards a theory of complexity for sampling. On the one hand, algorithm-specific lower bounds highlight their weaknesses, pinpointing bottlenecks in attaining faster rates; this is useful for algorithm designers, as it clarifies what key barriers must be overcome. On the other hand, the hard instances which arise in designing lower bounds may have important structural properties, paving the way to stronger and more general bounds.
For these reasons, we focus on characterizing the complexity of MALA and HMC (see Section 2 for algorithm definitions), which are often the samplers of choice in practice, by lower bounding their performance when they are used to sample from densities proportional to exp(−f(x)), where f : Rd → R has a finite condition number κ < ∞.1 We call such a density “well-conditioned.” Finally, we explicitly assume throughout that κ = O(d4), as otherwise in light of our lower bounds the general-purpose logconcave samplers of [LV07, JLLV20, Che21] are preferable.

heading: 1.1 Our results
text: Our primary contribution is a nearly-tight characterization of the performance of MALA for sampling from two high-dimensional distribution families without a warm start assumption: well-conditioned Gaussians, and the more general family of well-conditioned densities. We prove the following two lower bounds on MALA’s complexity, which is a one-parameter algorithm (for a given target distribution) depending only on step size. We fix a scale [1, κ] on the problem, as otherwise nonscale-invariance can be exploited to give more trivial lower bounds (cf. Appendix B, supplement).
Theorem 1. For every step size, there is a target Gaussian on Rd whose negative log-density always has Hessian eigenvalues in [1, κ], such that the relaxation time of MALA is Ω( κ √ d√
log d ).
Theorem 2. For every step size, there is a target density on Rd whose negative log-density always has Hessian eigenvalues in [1, κ], such that the relaxation time of MALA is Ω( κdlog d ).
To give more context, MALA is a Metropolis-adjusted Markov chain, which performs updates preserving the stationary distribution. It can be derived by applying a filter on the Euler discretization of the Langevin dynamics, a stochastic differential equation with stationary density ∝ exp(−f(x)):
dxt = −∇f(xt)dt+ √ 2dWt,
where Wt is Brownian motion. Such Metropolis-adjusted methods typically provide total variation distance guarantees, and attain logarithmic dependence on the target accuracy.2 The mixing of such chains is governed by their relaxation time, also known as the inverse spectral gap.
However, in continuous space, it is not always clear how to relate the relaxation time and mixing time, the time it takes to reach total variation 1e to the stationary distribution from a given start (we
1f has condition number κ if it is L-smooth and µ-strongly convex (has all second derivatives in the range [µ,L]), where κ = L
µ ; we overload this terminology and say the density itself has condition number κ.
2This contrasts with a different family of unadjusted discretizations, which are analyzed by coupling them with the stochastic differential equation they simulate (see e.g. [Dal17, CCBJ18] for examples), at the expense of a polynomial dependence on the target accuracy; we focus on Metropolis-adjusted discretizations in this work.
choose 1e to match the literature, but any constant smaller than 1 will do). There is extensive research on when these two quantities are relateable [BGL14], but typically these arguments are tailored to chain-specific properties, causing relaxation time bounds to not be entirely satisfactory in some cases. We complement Theorems 1 and 2 with a mixing time lower bound from an exponentially warm start.
Theorem 3. For every step size, there is a target density on Rd whose negative log-density always has Hessian eigenvalues in [1, κ], such that MALA initialized at an exp(d)-warm start requires Ω( κd
log2 d )
iterations to reach e−1 total variation distance to the stationary distribution.
We remark that Theorem 3 is the first mixing time lower bound for discretizations of the Langevin dynamics we are aware of: other related bounds have primarily been on relaxation times [CV19, LST20a, CLA+20]. It is unknown how to obtain a starting distribution for a general κ-conditioned distribution with warmness better than κd (obtained byN (x∗, 1LI) where L is the smoothness and x ∗ is the mode).3 A line of work [DCWY18, CDWY19, LST20a] analyzed the performance of MALA under this start, culminating in a mixing time of Õ(κd), where Õ hides logarithmic factors in κ, d, and the target accuracy. On the other hand, a recent work [CLA+20] demonstrated that MALA obtains a mixing time scaling as Õ(poly(κ) √ d), initialized at a polynomially warm start,4 and further showed that such a mixing time is tight (in its dependence on d). They posed as an open question whether it was possible to obtain Õ(poly(κ)d1−Ω(1)) mixing from an explicit start.
We address this question via Theorem 3, showing the Õ(κd) rate of [LST20a] for MALA applied to a κ-conditioned density is nearly tight. To prove Theorems 1-3, in each case we exhibit an exp(−d)-sized set according to the stationary measure where either the chain cannot move in poly(d) steps, or must choose a very small step size. Beyond exhibiting a mixing bound, this demonstrates the subexponential warmness assumption in [CLA+20] is necessary for their improved bound. To our knowledge, this is the first nearly-tight characterization of a specific sampler’s performance, and improves bounds of [CLA+20, LST20a]. It also implies going beyond Õ(κd) mixing for general well-conditioned densities requires subexponential warmness.
The lower bound statement of Theorem 3 is warmness-sensitive, and is of the following (somewhat non-standard) form: for β = exp(d), we provide a lower bound on the quantity
inf algorithm parameters sup starts of warmness≤β
densities in target family
mixing time of algorithm.
In other words, we are allowed to choose both the hard density and starting distribution adaptively based on the algorithm parameters (in the case of MALA, our choices are in response to the step size). We note that this type of lower bound is compatible with standard conductance-based upper bound analyses, which typically only depend on the starting distribution through the warmness parameter.
We further study the multi-step generalization of MALA, known as Hamiltonian Monte Carlo with a leapfrog integrator (which we refer to as HMC). In addition to a step size η, HMC is parameterized by a number of steps per iteration K, making K gradient queries in every step to perform a discretization of the Langevin dynamics, before applying a Metropolis filter. Multi-step HMC has the potential of attaining overall runtime gains by effectively taking longer steps. It was recently shown [CDWY19] that under higher derivative bounds, balancing η and K more carefully depending on problem parameters could break the apparent κd barrier of MALA, even from an exponentially warm start.
It is natural to ask if there is a stopping point for improving HMC. We demonstrate that HMC cannot obtain a better relaxation time than Õ(κ √ dK−1) for any K, even when the target is a Gaussian. Since every HMC step requires K gradients, this suggests Ω̃(κ √ d) queries are necessary.
Theorem 4. For every step size and count, there is a target Gaussian on Rd whose negative logdensity always has Hessian eigenvalues in [1, κ], such that the relaxation time of HMC is Ω( κ √ d
K √ log d ).
In Appendix B of the supplement, we also lower bound how much increasing K can improve HMC in the in-between range κ √ d to κd. In particular, we demonstrate that if K ≤ dc for some constant c, then K-step HMC can only improve the relaxation time of Theorem 4 by roughly K2, showing that
3The warmness of a distribution is the worst-case ratio between measures it and the stationary assign to a set. 4As discussed, it is currently unknown how to obtain such a warm start generically.
to truly go beyond a κd relaxation time by a dΩ(1) factor, the step size must scale polynomially with the dimension. Our mixing lower bound technique in Theorem 3 does not directly extend to give a complementary lower bound for Theorem 4 for all K, but we defer this to interesting future work.

heading: 1.2 Prior work
text: Sampling from well-conditioned distributions (as well those with stronger higher derivative bounds) is an extremely active and rich research area, so for brevity we focus on discussing two types of related work in this section: upper bounds for the MALA and HMC Markov chains, and lower bounds for sampling and related problems. We defer to e.g. [Dal17, CCBJ18, DCWY18, DR18, DM19, DMM19, CDWY19, CV19, SL19, MMW+19, LST20a, LST20b, CLA+20] and references therein for a more complete account on progress on well-conditioned sampling.
Theory of MALA and HMC. MALA was originally proposed in [Bes94], and subsequently its practical and theoretical performance has received extensive treatment in the literature (cf. [PSC+15]). Several analyses related to the well-conditioned setting we study predate [DCWY18], e.g. [RT96, BRH12], but they consider more restricted settings or do not state explicit dependences on κ and d.
Recently, a line of work has obtained a sequence of upper bounds on the mixing of MALA. First, [DCWY18] demonstrated a mixing time of Õ(κd+ κ1.5 √ d) from a polynomially warm start, and the same authors later proved the same bound under an explicit exponentially warm start [CDWY19]. Later, [LST20a] demonstrated that under an appropriate averaging scheme, the mixing time could be improved to Õ(κd) with no low-order dependence. Finally, [CLA+20] recently demonstrated that from a polynomially warm start, MALA mixes in time Õ(poly(κ) √ d) for general κ-conditioned distributions and in time Õ(poly(κ) 3 √ d) for Gaussians, and posed the open question of attaining similar bounds from an explicit (exponentially) warm start, a primary motivation for our exploration.
HMC can be viewed as a multi-step generalization of MALA, with two parameters (a step size η and a step count K); when K = 1, it matches MALA exactly. For larger K, the algorithm simulates the (continuous-time) Hamiltonian dynamics with respect to the potential f(x) + 12 ‖v‖ 2 2 where f is the target’s negative log-density and v is an auxiliary “velocity;” intuitively, larger K leads to more faithful discretizations. However, there are few explicit analyses of the (Metropolis-adjusted) HMC algorithm on well-conditioned distributions.5 To our knowledge, the only upper bound for the mixing of HMC stronger than known analyses of its specialization MALA is by [CDWY19], which gave a suite of bounds balancing three parameters: the conditioning κ, the dimension d, and the Hessian Lipschitz parameter LH , under an additional bounded third derivatives assumption. Supposing LH is polynomially bounded by the smoothness L, they demonstrate that HMC can sometimes achieve sublinear dependence on d in number of gradient queries, where the improvement depends on κ and d (e.g. if κ ∈ [d 13 , d 23 ] and LH ≤ L1.5, κd 11 12 gradients suffice). This prompts the question: can HMC attain complexity independent of d, assuming higher derivative bounds, from an explicit warm start? Theorem 4 answers this negatively (at least in terms of relaxation time) using an exponentially-sized bad set; moreover, our hard distribution is a Gaussian, with vanishing derivatives of order ≥ 3.
Lower bounds for sampling. The bounds most closely relevant to those in this paper are given by [LST20a], who showed that the MALA step size must scale inversely in κ for the chain to have a constant chance of moving, and [CLA+20], who showed it must scale as d− 1 2 . Theorem 2 matches or improves both bounds simultaneously while giving an explicit hard distribution and exp(−d)-sized bad set. Moreover, both [LST20a, CLA+20] gave strictly spectral lower bounds, complemented by our Theorem 3, a mixing time lower bound. We briefly mention several additional lower bound results in sampling-adjacent literature, related to this work. Recently, [CLW20] exhibited an information-theoretic lower bound on unadjusted discretizations simulating the underdamped Langevin dynamics, whose dimension dependence matches the upper bound of [SL19] (leaving the precise κ dependence open). Finally, [GLL20] and [CBL20] give information-theoretic lower bounds for estimating normalizing constants of well-conditioned distributions and the number of stochastic gradient queries required by first-order sampling under noisy gradient access respectively.
5There has been considerably more exploration of the unadjusted variant [MV18, MS19, BE21], which typically obtain mixing guarantees scaling polynomially in the inverse accuracy (as opposed to polylogarithmic).

heading: 2 Preliminaries
text: General notation. For d ∈ N we let [d] := {i ∈ N | 1 ≤ i ≤ d}. For positive semidefinite A, ‖·‖A is its induced seminorm ‖x‖A = √ x>Ax. We use ‖·‖p to denote the `p norm for p ≥ 1, and ‖·‖∞ is the maximum entry absolute value. We let N (µ,Σ) denote the multivariate Gaussian with mean µ ∈ Rd and covariance Σ ∈ Rd×d. We let I ∈ Rd×d denote the identity matrix when dimensions are clear, and is the Loewner order on the positive semidefinite cone. We say twice-differentiable f : Rd → R is L-smooth and µ-strongly convex for 0 ≤ µ ≤ L if µI ∇2f(x) LI for all x ∈ Rd. For any x, y ∈ Rd, this implies ‖∇f(x)−∇f(y)‖2 ≤ L ‖x− y‖2, and that f satisfies the quadratic bounds f(x)+〈∇f(x), y − x〉+µ2 ‖y − x‖ 2 2 ≤ f(y) ≤ f(x)+〈∇f(x), y − x〉+ L 2 ‖y − x‖ 2 2. The condition number of such f is κ := Lµ . We assume κ is at least a constant for convenience; a lower bound of 10 suffices for all our results. ForA ⊆ Rd,Ac is its complement and π(A) := ∫ x∈A dπ(x) is its measure under π. We say ρ is β-warm with respect to π if dρdπ (x) ≤ β everywhere, and define ‖π − ρ‖TV := supA⊆Rd π(A)− ρ(A). Finally, Eπ [g] = ∫ g(x)dπ(x) and Varπ [g] = Eπ [ g2 ] − (Eπ [g])2. Sampling. Consider a Markov chain defined on Rd with transition kernel {Tx}x∈Rd , so that∫ Tx(y)dy = 1 for all x. Further, denote the stationary distribution of the Markov chain by π∗. We define the Dirichlet form g : Rd → R with respect to the chain by E(g, g) = 1 2 ∫∫ (g(x)− g(y))2Tx(y)dπ∗(x)dy. The mixing of the chain is governed by its spectral gap:
λ ({Tx}x∈Rd) := inf g
{ E(g, g)
Varπ∗ [g]
} . (1)
The relaxation time is the inverse spectral gap. Finally, we recall the definition of a Metropolis filter, which takes arbitrary proposal distributions {Px}x∈Rd and defines a reversible chain with stationary distribution π∗. The Metropolis filtered chain has transition distributions {Tx}x∈Rd defined by
Tx(y) := Px(y) min (
1, dπ∗(y)Py(x) dπ∗(x)Px(y)
) for all y 6= x. (2)
Whenever the proposal is rejected by the modified distributions above, the chain does not move.
MALA. We formally define the Metropolis-adjusted Langevin algorithm (MALA). Fix a distribution π on Rd, with density dπdx (x) = exp(−f(x)), and suppose f is twice-differentiable. MALA is defined by performing a Euler discretization of the Langevin dynamics up to time h > 0, and then applying a Metropolis filter: define the proposal distribution at a point x by Px := N (x− h∇f(x), 2hI). We obtain the MALA transition distribution by applying the definition (2), which yields
Tx(y) ∝ exp ( − ‖y − (x− h∇f(x))‖22
4h
) min 1, exp ( −f(y)− ‖x−(y−h∇f(y))‖ 2 2 4h ) exp ( −f(x)− ‖y−(x−h∇f(x))‖ 2 2
4h
)  . (3)
HMC. The Metropolized HMC algorithm is governed by two parameters, a step size η > 0 and a step countK ∈ N. From iterate x, HMC performs the following updates from x0 ← x, v0 ∼ N (0, I).
1. For 0 ≤ k < K: (a) vk+ 12 ← vk − η 2∇f(xk), xk+1 ← xk + ηvk+ 12 , vk+1 ← vk − η 2∇f(xk+1)
Each loop is known in the literature as a “leapfrog” step, and discretizes Hamilton’s equations for H(x, v) := f(x) + 12 ‖v‖ 2 2; for additional background, we refer the reader to [CDWY19]. Metropolized HMC performs the above algorithm from a point x, and accepts xK with probability
min { 1,
exp (−H(xK , vK)) exp (−H(x0, v0))
} . (4)
Supplementary material. Due to space constraints in this abridged version, we defer additional exposition and many proofs to the full version of this paper, contained in the supplement.

heading: 3 Lower bounds for MALA
text: In this section, we give the main constructions and technical tools we develop in proving Theorem 3. En route, we also summarize our proofs of Theorems 1 and 2. Our starting point is the observation (also made in [CLA+20]) that for a MALA step size h, the spectral gap of the MALA Markov chain scales no better than O(h+ h2), witnessed by a simple one-dimensional Gaussian.
Lemma 1 (Corollary 1, supplement). The spectral gap of MALA for sampling from the density ∝ exp(−f), where f(x) = 12x 2 1 + f−1(x−1) (x−1 drops the first coordinate), is O(h+ h 2).
Following Lemma 1, our strategy for proving Theorems 1 and 2 is to show a dichotomy on the choice of step size: either h is so large such that we can construct an exp(d)-warm start where the chain is extremely unlikely to move (e.g. the step almost always is filtered), or it is small enough to imply a poor spectral gap directly by Lemma 1. In the former case (large step size), it is enough to give an exp(−d)-sized set according to the stationary measure, from which the chain rejects with probability 1− poly(d−1): this implies a conductance lower bound with the given witness set, which yields a spectral gap bound by the well-known Cheeger’s inequality [Che69]. We use this argument to rule out different step size ranges with explicit functions and witness sets. Ruling out h = ω( √
log d · 1 κ √ d ): proof of Theorem 1. In the Gaussian case, we achieve this
by explicitly characterizing the rejection probability. Our hard function is the simple quadratic fhq(x) = 1 2x 2 1 + κ 2 ‖x−1‖ 2 2. Straightforward calculations then yield the following bound on the log-acceptance probability in (3) (ignoring the first coordinate for simplicity, as it does not dominate).
Lemma 2 (Lemma 3, supplement). For fixed x ∈ Rd and y ∼ Px according to MALA, with high probability, fhq(x)− fhq(y) + 14h ( ‖y − (x− h∇fhq(x))‖22 − ‖x− (y − h∇fhq(y))‖ 2 2 ) is at most
Θ ( hκ2 (( 2hκ− h2κ2 ) ‖x‖22 − 2hd )) + (2h)1.5κ2|1− hκ| ‖x‖2 √ log d. (5)
From this point, we observe that as long as ‖x‖22 is at least a constant factor away from its expectation (≈ dκ ), the dominant behavior of (5) scales as −h
2κ2d. We pick the “small ball” warm start ‖x‖22 ≤ d 2κ , which captures at least exp(−d) of the mass of π
∗. These calculations imply that from this warm start, the rejection probability is exp(−Ω(h2κ2d)), which implies any h = ω( √ log d· 1
κ √ d )
cannot leave the set with high probability; combined with Lemma 1, this proves Theorem 1.
Ruling out h = ω(log d· 1κd ): proof of Theorem 2. We now move onto the general well-conditioned setting. As a thought experiment, we observe the upper bound analysis of [DCWY18] for MALA has a d dependence which is bottlenecked by the noise term only. Even the “Metropolized random walk” where the proposal is simply xg ← x+ √ 2hg has upper bound analyses scaling linearly in d. Thus, it is natural to study the effect of the noise, and construct a hard distribution based around it.
We first formalize this intuition, demonstrate that for step sizes not ruled out by Theorem 1, all terms in the rejection probability other than those due to the effect of the noise are low-order. Lemma 3 (Lemma 10, supplement). For fixed x ∈ Rd with ‖∇f(x)‖2 = O( √ κd), with high
probability over g ∼ N (0, I), and xg ← x+ √ 2hg, y ← xg − h∇f(x) according to MALA,
f(x)− f(y) + 1 4h
( ‖y − (x− h∇f(x))‖22 − ‖x− (y − h∇f(y))‖ 2 2 ) ≤ o(hκd)
+f(x)− f(xg) + 1
4h
( ‖xg − (x− h∇f(x))‖22 − ‖x− (xg − h∇f(xg))‖ 2 2 ) .
In other words, to show a high-probability −Ω(hκd) upper bound on the log-acceptance, it suffices to understand the second line of the above display (since other terms do not dominate). Moreover, the effect of the noise is coordinatewise separable (since N (0, I) is a product distribution). Thus, it suffices to show a hard one-dimensional density where the log-acceptance has expectation −Ω(hκ), and apply sub-Gaussian concentration to show a product distribution very likely obtains −Ω(hκd). At this point, we reduce to the following self-contained problem: let x ∈ R, let π∗ ∝ exp(−f1d) be one-dimensional with second derivative ≤ κ, and let xg = x+ √ 2hg for g ∼ N (0, 1). We wish to
construct f1d such that for x in a constant probability region over exp(−f1d) (the “bad set”), Eg∼N (0,1) [ −f1d(xg) + f1d(x)− 1
2 〈x− xg, f ′1d(x) + f ′1d(xg)〉
] = −Ω(hκ), (6)
where the contents of the expectation in (6) are the log-rejection probability along one coordinate by a straightforward calculation. By forming a product distribution using f1d as a building block, and combining with the remaining low-order terms due to the drift∇f(x), we attain an exp(−d)-sized region where the rejection probability is exp(−Ω(hκd)), completing Theorem 2. It remains to construct such a hard f1d. The calculation
−f1d(xg) + f1d(x)− 1
2 〈x− xg, f ′1d(x) + f ′1d(xg)〉 = −2h ∫ 1 0 ( 1 2 − s ) g2f ′′1d(x+ s(xg − s))ds
suggests the following approach: since f ′′1d > 0 always, and the integral puts negative mass on s ∈ [0, 12 ) and positive on s ∈ ( 1 2 , 1], we want our bad set to have large f ′′ 1d, but most moves g to result in a smaller f ′′1d. Our construction patterns this intuition: we choose 6
f1d(x) = κ 3 x2 − κh 3 cos x√ h =⇒ f ′′1d(x) = 2κ 3 + κ 3 cos x√ h ,
such that our bad set is when cos x√ h is relatively large (which occurs with probability→ 12 for small h in one dimension). The period of our construction scales with √ h, so that most moves √ 2hg of size O( √ h) will “skip a period” and hence hit a region with small second derivative, satisfying (6).
We demonstrate our hard function fhard, a product of d − 1 copies of f1d and a one-dimensional Gaussian, satisfies the following bound. Combining it with Lemmas 3 and 1, and using the hard set of points whose gradient is O( √ κd) and whose coordinatewise cosine is Ω(1) (which we show has measure ≥ exp(−d), since it coordinatewise captures roughly half the mass), yields Theorem 2. Lemma 4 (Lemmas 7-8, supplement). For fixed x ∈ Rd with cos xi√
h > 0.1 coordinatewise for
2 ≤ i ≤ d, with high probability over g ∼ N (0, I) and xg ← x+ √ 2hg,
f(x)− f(xg) + 1
4h
( ‖xg − (x− h∇f(x))‖22 − ‖x− (xg − h∇f(xg))‖ 2 2 ) = −Ω(hκd).
From relaxation time to mixing time: proof of Theorem 3. We now turn our attention to proving Theorem 3, our main mixing time lower bound. Implicitly in the above discussion, we already proved such a lower bound for h = ω(log d · 1κd ): we use either the cosine construction fhard or the Gaussian construction fhq for relevant ranges of h, along with their exp(−d)-sized hard sets, to show the chain cannot leave the starting set in polynomially many steps within these step size ranges.
We consider the remaining range, h = O(log d · 1κd ). Intuitively, our goal is to show that it takes roughly 1h steps to explore the whole space, a simple goal in the absence of filtering which becomes problematic when accounting for the filter. Because it is correlated between coordinates, it is hard to reason about the effect on any particular coordinate, and moreover Gaussian concentration does not
6We note [CLA+20] also used a (different, but similar) cosine-based construction for their lower bound.
directly apply when the acceptances are not independent of the choice of noise. The question here then becomes: how do we decouple the randomness of the process from the randomness of the filter?
We accomplish this decoupling in two steps. First, we analyze the effect of an “idealized” MALA with no filter, where with high probability over the randomly sampled Gaussian vectors, it takes roughly 1h log d ≈ κd log2 d steps to move ‖x‖2 by a constant. It remains to account for the filter.
Our main observation is that for the only remaining range h = O(log d · 1κd ), we know such a small step size (scaling with d rather than √ d) is overkill for rapid mixing on Gaussians, which only require a step size √ d larger. Thus, for this range we choose our hard density to be the simple Gaussian N (0, I). We show that with constant probability, in κd log2 d
steps the true MALA chain never rejects. This allows us to couple MALA with our idealized chain, proving a mixing time lower bound.
Formally, our main technical lemma to this effect is stated in the following. By initializing at the exp(d)-warm start ‖x‖22 ≤ 1 2d (the “small ball” from Theorem 1’s proof), and combining with our lower bounds on the other ranges of h, we conclude our proof of Theorem 3.
Lemma 5 (Lemma 11, supplement). Consider iterating the MALA Markov chain with h = O(log d · 1 κd ) on N (0, I) for T iterations, with starting distribution the marginal on ‖x‖ 2 2 ≤ 1 2d. With
probability at least 99100 , both of the following events occur for T = o ( κd log2 d ) :
1. Throughout the Markov chain with iterates {xt}0≤t<T , we always have ‖xt‖2 ≤ 0.9 √ d.
2. Throughout the Markov chain, the Metropolis filter never rejected.

heading: 4 Lower bounds for HMC
text: In this section, we present our main HMC lower bound, Theorem 4. We recall that HMC has two parameters: a number of steps K ≥ 2 (as the K = 1 case is handled by MALA), and a step size η > 0. Throughout, we focus our attention on the case of a quadratic f(x) = 12x
>Ax. Without loss of generality (by rotational invariance of HMC), we assume A = diag (λ) for 1 ≤ λ ≤ κ entrywise. Structure of HMC: a detour to Chebyshev polynomials. The starting point of our lower bound construction is a novel characterization of HMC’s behavior on quadratics via Chebyshev polynomials. By directly analyzing the recurrences generating the HMC iterates (cf. Section 2), we show the following relationship between some iterate xk and the initial position and velocity (x0, v0).
Lemma 6 (Lemma 13, supplement). For f(x) = 12x >diag (λ)x, iterates {xk}0≤k≤K satisfy
[xk]i = pk(η 2λi)[x0]i + ηqk(η 2λi)[v0]i, where pk(z) := ∑
0≤j≤k
(−1)j · k k + j
· ( k + j
2j
) zj , qk(z) := ∑ 0≤j≤k−1 (−1)j · ( k + j 2j + 1 ) zj .
We further observe that the polynomials pk and qk are related to the classical Chebyshev polynomials. Let Tk be the kth Chebyshev polynomial of the first kind, and let Uk the kth Chebyshev polynomial of the second kind. These polynomial families are very well-studied due to their extremal properties, and indeed their relationship to the acceleration phenomenon in first-order optimization has been known for some time [Har13, Bac19]. Roughly, these polynomials oscillate between ±1 in the range [−1, 1] (which contains all their zeroes), and outside this range they rapidly explode. We observe that the Chebyshev polynomials are related to the HMC coefficient polynomials:
pk(z) = Tk
( 1− z
2
) , qk(z) = Uk−1 ( 1− z
2
) .
Magically, the extremal points in [−1, 1] where Tk is ±1 are exactly the same as the zeroes of Uk−1. Combining with Lemma 6, this yields the somewhat surprising conclusion that there are choices of step size η where the chain cannot move in a coordinate, oscillating between ±[x0]i regardless of the choice of v0! We use this observation heavily in our lower bound construction to rule out η ranges.
Ruling out the Chebyshev extremal region η2 ≥ π 2
κK2 . We first restrict to the intermediate range 1 ≥ η2 ≥ π 2
κK2 . We show (Proposition 4, supplement) ∃j ∈ [K − 1] such that 1 ≤ λj ≤ κ, for λj := 2 ( 1− cos ( jπ K )) η2 , for 1 ≥ η2 ≥ π 2 κK2 .
The reason we choose this definition is that the {λj}j∈[K−1] are precisely the points where (for z := η2λj) TK(1− z2 ) = ±1 and Uk−1(1− z 2 ) = 0. Hence, by picking a hard quadratic function with at least one eigenvalue at the specified λj , we can force the chain to never leave any symmetric set in that coordinate, regardless of the random velocity chosen and number of steps K.
Finally, for η2 ≥ 1, we observe the hard function f(x) = κ2 ‖x‖ 2 2 is a simple counterexample. In particular, for λ = κ, η2 ≥ 1, and z = η2λ, we see that pk(z) blows up due to the behavior of Chebyshev polynomials outside [−1, 1], as 1− z2 falls outside this range. We use this to argue the acceptance probability from any starting point and any number of steps is exp(−Ω(d)). Stronger η bounds under a constant gap. The Chebyshev polynomial argument demonstrates that to avoid this extremal behavior, we should choose η2 = O( 1κK2 ). We now give a lower bound argument under the stronger assumption that η2 ≤ 1κK2 , with the understanding there is a constant gap between this assumption and the region ruled out by the Chebyshev argument.
The main observation (Lemma 14, supplement) is that under this assumption, the coefficients of pk and qk supplied in Lemma 6 decay rapidly. In particular, for polynomial pK , the coefficient ratios are
(−η2κ)j+1 (
K K+j+1
) ( K+j
2j ) (−η2κ)j ( K K+j ) ( K+j 2j
) = (−η2κ) (K + j)(K − j)(2j + 2)(2j + 1) ∈ [−0.1, 0], assuming η2κ ≤ 1K2 . This implies that both the polynomials pK and qK are governed by their first terms, up to constants, and thus we can apply the proof techniques of Theorem 1. Indeed, we demonstrate that up to a K factor, in this step size range HMC behaves just like MALA, and thus its spectral gap only loses a K (which balances the K gradient queries per iteration).
Removing the constant gap. The final obstacle in our HMC construction is to close the gap between the η2 ≤ 1κK2 required by our geometric argument, and the η 2 ≤ π 2
κK2 implied by behavior of Chebyshev polynomials. We bypass this by taking a hard quadratic fhqc which weights two coordinates by 1 and κ, and the remaining coordinates by κπ2 . On d− 2 coordinates, we obtain(
−η2 κ π2 ) (K + j)(K − j) (2j + 2)(2j + 1) ∈ [−0.1, 0] for all η2 ≤ π 2 κK2 ,
showing the relevant polynomials rapidly converge. This is the dominant behavior, as eventually the denominators of these ratios outweighs any constant gap, and thus the κ coordinate can only hurt us by so much, concluding the proof of Theorem 4.

heading: 5 Conclusion
text: We presented relaxation time lower bounds for the MALA and HMC Markov chains at every step size and scale, as well as a mixing time bound for MALA from an exponentially warm start. We highlight in this section a number of unexplored directions left open by our work, beyond direct strengthenings of our results, which we find interesting and defer to a future exploration.
Variable or random step sizes. The lower bounds of this paper were for MALA and HMC Markov chains with a fixed step size. For variable step sizes which take e.g. values in a bounded multiplicative range, we believe our arguments can be modified to also give relaxation time lower bounds for the resulting Markov chains. However, the arguments of Section 4 (our HMC lower bound) are particularly brittle to large multiplicative ranges of candidate step sizes, because they rely on the locations of Chebyshev polynomial zeroes, which only occur in a bounded range. From an algorithm design perspective, this suggests that adaptively or randomly choosing step size ranges may be effective in improving the performance of HMC. Such a result would also give theoretical justification to the No-U-Turn sampler of [HG14], a common HMC alternative in practice. We state as an
explicit open problem: can one obtain improved upper bounds, such as a √ κ dependence or a dimension-independent rate, for example by using variations of these strategies (variable step sizes)?
Necessity of κ lower bound. All of our witness sets throughout the paper are exp(−d) sized. It was observed in [DCWY18] that it is possible to construct a starting distribution with warmness arbitrarily close to √ κ d; the marginal restriction of our witness set obtains this bound for all κ ≥ e2. However, recently [LST20b] proposed a proximal point reduction for sampling, showing (for mixing bounds scaling at least linearly in κ) it suffices to sample a small number of regularized distributions, with conditioning arbitrarily close to 1. Adjusting constants, we can modify our Gaussian lower bounds (Theorems 1 and 4) to have witness sets with measure cd for c arbitrarily close to 1. However, our witness set for the family of hard non-Gaussian distributions encounters a natural barrier at measure 2d, as it is sign-restricted by the cosine function. We find it interesting to see if a stronger construction rules out existing warm starts for all κ ≥ 1, or if an upper bound can take advantage of the [LST20b] reduction to obtain improved dependences on dimension.

heading: Acknowledgments
text: We would like to thank Santosh Vempala for numerous helpful conversations, pointers to the literature, and writing suggestions throughout the course of this project.
YL and RS are supported by NSF awards CCF-1749609, DMS-1839116, and DMS-2023166, a Microsoft Research Faculty Fellowship, a Sloan Research Fellowship, and a Packard Fellowship. KT is supported by NSF Grant CCF-1955039 and the Alfred P. Sloan Foundation.

Review summaries:
This paper studies two well-known sampling algorithms for well-conditioned log concave distributions: the Metropolos adjusted Langevin algorithm (MALA) and Hamiltonian Montecarlo (HMC). The main contributions of the paper are:  1. A lower bound $\tilde\Omega(d\kappa)$ for the mixing time of MALA from an $\exp(d)$-warm start. This bound is sharp. 2. A lower bound on the relaxation time of HMC with $K$-steps per iteration of $\tilde\Omega(\kappa\sqrt{d}/K)$. 3. Lower bounds on the relaxation time for MALA under Gaussian and general distributions.

The paper proves a mixing time lower bound for Metropolized Langevin (MALA) on distributions with smooth and strongly convex potentials, starting at an exponential warm start. The lower bound matches the best known upper bounds. It also proves a mixing time lower bound for HMC on the class of Gaussians with condition number kappa from an exponential warm start.

This paper proves lower bounds on the performance of two important sampling algorithms, the Metropolis-adjusted Langevin algorithm (MALA) and Hamiltonian Monte Carlo (HMC), for strongly log-concave and log-smooth target distributions. The paper first proves upper bounds on the spectral gap for these algorithms, assuming that the target is either Gaussian or more generally log-concave. These results are then used to prove lower bounds on the mixing time of MALA for exponential warm starts, which are perhaps the clearest and most compelling results obtained. Therefore, I will summarize this result in more detail.  Suppose that the target distribution is strongly log-concave and log-smooth in dimension d and with condition number κ. Previous algorithmic works have shown that MALA mixes after dκ steps from an exponentially warm start (which can be obtained by initializing at a Gaussian with appropriate variance). On the other hand, the recent work by Chewi et al. shows that MALA mixes after poly(κ) d^{½} steps under a polynomially warm start (and it is unknown how to achieve such a warm start in practice). This current paper sheds light on this situation by constructing a hard target distribution such that when initialized at a particular exp(d) warm start, MALA requires κd steps to mix.