Lower Bounds on Metropolized Sampling Methods for Well-Conditioned Distributions
Authors: Yin Tat Lee
Ruoqi Shen
Kevin Tian
Venue: NeurIPS 2021 Oral (2021)
Keywords: sampling
computational statistics
Bayesian methods
Langevin dynamics
Hamiltonian Monte Carlo

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 $\widetilde{\Omega}(\kappa d)$ on the mixing time of MALA from an exponentially warm start, matching a line of algorithmic results \cite{DwivediCW018, ChenDWY19, LeeST20a} up to logarithmic factors and answering an open question of \cite{ChewiLACGR20}. 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.

Lower Bounds on Metropolized Sampling Methods for Well-Conditioned Distributions
Yin Tat Lee University of Washington and Microsoft Research y yintat@uw.ed.
Ruoqi Shen University of Washington shenr30cs. washington, edu
Kevin Tian Stanford University
kjtian@stanf ord. edu
Abstract
We give lower bounds on the performance of two the most popular sampling methods in practice, the Metropolis-adjusee Langevin algorithm (MALA) and multi-step Hamiltonian Monte Carlo (HMC) with a leapfrog integrator, when ap- plied to well-conditioned distributions. Our main result nearly-tight lower bound of (2(dd) on the mixing time of MALA from an exponentially warm start, matching line of algorithmic results [DWWY18] CDW LST20a] up to loga- rithmic factors and answering an open question of [CLA 20). We also show that a polynomial dependence 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 novel connection between leapfrog integration and Chebyshev polynomials, which may be of independent interest.
1
Introduction
Sampling from a continuous distribution in high dimensions is fundamental problem in algorithm design. As sampling serves key subroutine in variety of tasks in machine learning [AdFD103) 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 "well- conditioned" has garnered 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 in machine learning applications Bar12] and many distributions these settings are well-conditioned, such as multivariate Gaussians, mixture models with small separation, and densities arising from Bayesian logistic regression with Gaussian prior (DCWY18) Moreover, for several widely-used sampler implementations popular packages [Aba 16 [GH 17), such the Metropolis-adjusted Langevin algorithm (MALA) and Hamiltonian Monte Carlo (HMC), the target having small condition number is in some sense minimal assumption for known provable guarantees (discussed more thoroughly in Section 1.2).
Finally, the documeed success of first-order (gradient) methods in optimization Bee 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 [JK098), demonstrating that the Langevin dynamics which MALA and HMC discretize has an interpretation as gradient descent on density space, flurry of work Daal1 CCBJ18 DCWYII
DRI8 [M19 DMM19 CDWY19 CV19 SL19 MMW 19 ST ST20bb
CLA 20 has ob-
35th Conference on Neural Information Processing Systems (NcurIPS 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 well- conditioned regime or otherwise) has proven remarkably challenging. To 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 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-sppecffe specifie; 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-speciff 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 cxp(-f
where has a finite condition number < oo. We call such a density "well-conditioned." Finally, we explicitly assume throughout that O d as otherwise in light of our lower bounds
f: -R +
[
the general-pe general-purpose purpose logconcave samplers of LV07 220 Che21] are preferable.
1.1 Our results
Our primary contribution is nearly- characterization of the performance of MALA for sampling from two nigh-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 given target distribution) depending only step size. We fix a scale [1, k) on the problem, as otherwise non- scale-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 TRd whose negative log-density always has Hessian eigenvalues in [1, ki), such that the relaxation time of MALA is 2 KVa
Vlog
Theorem 2.
For every step size, there is a target density on Idd whose negative log- log-density always has Hessian eigenvalues in [1, Ki., such that the relaxation time of MALA is Q
ad
Tog 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, stochastic differential equation with stationary density exp(-f(x)))
dx, - V f + V2dWe.
where We is Brownian motion. Such Metropolis-adfjusted methods typically provide total variation distance guarantees, and attain logarithmic dependence on the target accuracy ? 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 1 to the stationary distribution from a given start (we
'f has condition number x it T-smooth and p-strongly convex (has all second derivatives in the range [M, L.D. where x = f/s we overload this terminology and say the density itself has condition number x. Thii contrasts with a different family of unadjusted discretizations, which are analyzed by coupling them with the stochastic differential equation they simulate (see e.g. CCBJ18 for examples), at the expense of polynomial dependence the target accuracy; focus on Metropolis adjustee discretizations in this work.

---

choose 1 to match the literature, but any constant smaller than 1 will do). There is extensive research on when these two quantities are relateable [GL14], but typically these arguments are tailored to chain-specifie properties, causing relaxation time bounds to not be entirely satisfactory in some cases. We complement Theorems [ with a mixing time lower bound from an exponentially warm start.
Theorem 3. For every step size, there is target density on IR whose negative log deg-iissty always has xd Hessian eigenvalues in [1, kl. such that MALA initialized at an exp(d)-wan start requires 92( log² d
iterations to reach 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 [ST20al CLA 20). It is unknown how to obtain a starting distribution for general k-conditioned distribution with warmness better than nn (obtained by (a=,, ((²)),)) where L is the smoothness and x is the mode) A line of work (DCWY18] CDWY19 LST20a| analyzed the performance of MALA under this start, culminating in a mixing time of (kd), where Ô 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 (poly(xx) d), initialized at a polynomially warm start and further showed that such mixing time is tight (in its dependence on d). They posed as open question whether was possible obtain ((poly(s)) (x:)d mixing from an explicit start.
We address this question via Theorem 3 showing the Ö(kd) rate of [ST20a for MALA applied to a s-conditioned density is nearly tight. To prove Theorems 13 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 [CL.A+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 (Kd) mixing for general well-conditioned densities requires subexponential warmness.
The lower bound statement of Theorem 3 is warmness- sarmnnss-sensitivee, and is of the following (somewhat
non-standard) form: for B = exp(d), we provide a lower bound on the quantity
inf
sup starts of warmness 5.0 densities target family
mixing time of algorithm.
algorithun parameters
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-basee 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 as HMC). In addition to a step size 1). 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 dynamies, 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 1) and K more carefully depending on problem parameters could break the apparent nd barrier of MALA, even from exponentially warm start.
It is natural to ask if there is stopping point for improving HMC. We demonstrate that HMC cannot obtain a better relaxation time than OK1 for any K, even when the target Gaussian. Since every HMC step requires K gradients, this suggests ((xvdd) d) queries are necessary.
Theorem 4, For every step size and count, there is a target Gaussian on Bd whose negative log- svd K KVllgd
density always has Hessian eigenvalues in [1, kl,, such that the relaxation time of HMC is M
In Appendix of the supplement, we also lower bound how much increasing K can improve HMC in the be-between range kV to Rd. In particular, we demonstrate that if K S d for some constant c, then K-step HMC can only improve the relaxation time of Theorem 4 by roughly K2, showing that
P The warmness of distribution the worst-case ratio between measures and the stationary assign to a set. As discussed, it is currently unknown how obtain such a warm start generically.
3

---

to truly go beyond kd relaxation time by a dd(1) factor, the step size must scale polynomially with the dimension. Our mixing lower bound technique T not directly extend give a complementary lower bound for Theorem for all K, but we defer this to interesting future work.
1.2 Prior work
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 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. [Da177 CCBJ18] DCWY18) DRT8 DM19
DMM19 CDWY19 CV19, SL19 MMW 19 LST20a LST20b CLA and references therein for more complete account progress 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 (DCWYT8), e-g. [RT96] BRH12, but they consider more restricted settings or do not state explicit dependences on and d.
Recently, line of work has obtained a sequence of upper bounds on the mixing of MALA. First, DCWY18 demonstrated a mixing time of O(kd + x1.5 from a polynomially warm start, and the same authors later proved the same bound under an explicit exponentially warm start [CDWY19) Later, [[.ST20a] demonstrated that under an appropriate averaging scheme, the mixing time could be improved to Ö(Rd) with no low-order dependence. Finally, [CLA*20 recently demonstrated that from polynomially warm start, MALA mixes in time ((poly(x) for general x-conditioned distributions and in time ((poly(k) Vd) 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 multi-step generalization of MALA, with two parameters (a step size ry and a step count K); when K = 1, it matches MALA exactly. For larger K, the algorithm simulates the Conninuuus-time Hamiltonian dynamics with respect to the potential fxx + 2 ||:1 where f is the target's 's negative log-density and is an auxiliary "velocity;" intuitively, larger K leads to more faithful discretizations. However, there are few explicit analyses of the cestropolis-adjjstee
HMC algorithm on well-conditioned distributions | 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 K, the dimension d, and the Hessian Lipschitz parameter LH. under an additional bounded third derivatives assumption. Supposing L 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 k and 1.5 kd gradients suffice). This prompts the question: can HMC attain complexity independent of d, assuming higher derivative bounds, from an explicit warm start? Theorem answers this negatively (at least in terms of relaxation time) using an exponentially-sizae bad set; moreover, our hard distribution is a Gaussian, with vanishing derivatives of order 2 3.
d (e.g. if ς E [d's d and Lи S 1.5,
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 k for the chain to have a constant chance of moving, and ICLA+20) who showed it must scale as d 3. Theorem 2 matches or improves both bounds simultaneously while giving an explicit hard distribution and exp(-d)-sized bad set. Moreover, both [LST200a CLA +20 gave strictly spectral lower bounds, complemented by our Theorem 3 mixing time lower bound. We briefly mention several additional lower bound results in an cinommmiion-theoreee lower bound on unadjusted discretizations simulating the underdamped Langevin dynamics, whose dimension dependence matches the upper bound of [SL19] (leaving the precise k dependence open). Finally, GLL20) and [CBL20) give inffrmmaiion-thoortte 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.
literature, related to this work. Recently, (CLW20) exhibited
'There has been considerably more exploration of the unadjusted variant MV118 MS19 BE211. which typically obtain mixing guarantees scaling polynomially in the inverse accuracy (as opposed to polylogarithmic.

---

2 Preliminaries
General notation. For d E N we [d] = NiEN d). For positive semidefinite A, I1-Ill its induced seminorm ||>|| vx Az. We use I-l1p p to denote the Ep norm for p 2 L, and II- is the maximum entry absolute value. We let (M, Σ) denote the multivariate Gaussian with mean μ Rd and covariance Σ Raxd We let I E Raxdd denote the identity matrix when dimensions are clear, and < is the Loewner order on the positive semidefinite cone. We say twice-differentiable f Rdd - IR is T-smooth and j-strroggy convex for 0 S 1 I I. if μI V2 f(x) 3 III for all Rd. For any 2, E Rd this implies [v)(x) (f(i) S L|| vlly. and that satisfies the quadratic bounds f(*) (V/((,,
2) 2 ly x1I2 S f(y) S (())+(V((())). - x) + 1 lly x1|2 The condition number of such f is K := We assume A is at least a constant for convenience; a lower bound of 10 suffices for all our results. For A Hd A is its complement and (A) See dT(x) its measure under и. We say is B-warm with respect to if an (x:) S B everywhere, and define || -Pll = AuRA IT (A) - ((4). Finally, E. [g] f g(x ((z)dT(()) and Var, [g] E. [g²] (E,,r [g])²
Sampling. Consider a Markov chain defined on Rd with transition kernel (Te ze so that (v)dy = 1 for all z. Further, denote the stationary distribution of the Markov chain by n². We define the Dirichlet form 9 Rdd - IR with respect to the chain by Egg,g) [f(((()) (z))) (x)dy. The mixing of the chain governed by its spectral gap:
A ((TT)aeRR)) == = inf E(g.g) Var,
The relaxation time is the inverse spectral gap. Finally, we recall the definition of a Metropolis filter, which takes arbitrary proposal distributions (Px JaeR and defines a reversible chain with stationary distribution x². The Metropolis filtered chain has transition distributions (Tr JreRe defined by
Tx(y) Py((y) min (1,dT'
dm (v) PM)
(' for all x.
Whenever the proposal is rejected by the modified distributions above, the chain does not move.
MALA. We formally define the Metropolii-adjusted Langevin algorithm (MALA). Fix distribu- dz tion π on Rd, with density dz (x) cxp(-f(tprropcoo (x)). and suppose f is wiicediiffreetiable. MALA is de- fined by performing Euler discretization of the Langevin dynamics up to time h > and then apply- ing a Metropolis filter: define the proposal distribution at point x by Pa := N (x f 2h1).
We obtain the MALA transition distribution by applying the definition
which yields
lly (x Tz(1) x exp (-1l-
( min
exp
(f(y)
|| - Ce-vy-VV AV
4h
1,
(3)
4h
exp (f((x)
11 (x AV f(=))
4h
HMC.
The Metropolized HMC algorithm is governed by two parameters, a step size n > 0 and x, HMC performs the following updates from 2o +- F, vo (O,
step count K E N. From iterate
1. For 0 < < K: (a) Uk+ + 2/ Vf(())) 2641 c I& + 17++ Uk+1 + Ux (
Each loop is known in the literature a "leapfrog" step, and discretizes Hamilton's equations for H(x, u) == f(x) + ||: for additional background, refer the reader [CDWY19. Metropolized HMC performs the above algorithm from a point x, and accepts DK with probability
min (1.
(xp(--(2 uk])
(4)
cx vo))
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.
5

---

3 Lower bounds for MALA
In this section, we give the main constructions and technical tools we develop in proving Theorem En route, we also summarize our proof' of Theorems | and 2 Our starting point is the observation (also made in [CLA ) that for a MALA step size h. the spectral gap of the MALA Markov chain scales no better than O(h + A²), witnessed by simple one-dimensional Gaussian.
Lemma 1 (Corollary 1, supplement). The spectral gap of MALA for sampling from the density x exp(- f). where f(x 2 + f-1(x=1) (x-1 drops the first coordinate), O(h + h²).
Following Lemma 1 our strategy for proving Theorems | andd I to show a dichotomy on the choice of step size: either / 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), it is small enough imply poor spectral gap directly by Lemma] []] In the former case (large step size), is enough to give an exp(-d)-sized set according to the stationary measure, from which the chain rejects with probability 1 1- poly(d '): this implics a conductance lower bound with the given witness set, which yields a spectral gap bound by the well- Cheeger's inequality [Che69]. We use this argument to rule out different step size ranges with explicit functions and witness sets.
Ruling out h - w(vlogd- ): proof of Theorem I In the Gaussian case, we achieve this by explicitly characterizing the rejection probability. Our hard function is the simple quadratic fig(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 E Ra and y ~ Pa according to MALA, with high probability, fz)( - fln(t) + 4h (Ily (x NV fin (z))) - -|1=- - (y -V fmg (1)))) at most
+ (hn? ((2hr - h² n²2 |0:1 2hd) ) + (2h) 2 2.1
had ||ا||| Vlogd. d.
(5)
From this point, we observe that as long as ||=:[[ is at least a constant factor away from its expectation (~ d), the dominant behavior of (5) scales as ndd We pick the "small ball" warm start || S 2x which captures at least exp(-d) of the mass of x². These calculations imply that from this warm start, the rejection probabiliiyy is exp(- which implies any h w(Vlog d m cannot leave the set with high probability; combined with Lemma [ this proves Theorem [
d.
Ruling out = wlog d- : proof of Theorem 2 We now move onto the general well-conditioned setting. As thought experiment, we observe the upper bound analysis of (DCWYT8] for MALA has a d dependence which is bottlenecked by the noise term only. Even the "Metropolized random walk" where the proposal is simply &g + x + V2hg 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 T all terms in the rejection probability other than those due the effect of the noise are low-order.
Lemma 3 (Lemma 10, supplement). For fixed x E Rdd with [=)(2) = OVrd),, with high probability over g (0, I), and Fg + + V2hg, + Fg hV f(z) according to MALA,
[(x) f()) + 4h [Iv - (x 1G--VJCC (VS(())) 2 1 (y NV (N(()) S <((hnd)
+f(x) - f(x,)) + 4h
1
[|r, - (a hV hVf())) || (0, NVF(E)))1)
In other words, to show a high- probbprobbyilittyy (hudd) upper bound on the lcg-accep,,nce, 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 (O I) is a product distribution). Thus, suffices to show hard one-dimensional density where the log -cceatceee has expectation -(((k)) and apply sub-Gaussian concentration to show a product distribution very likely obtains - -(hkd).
At this point, we reduce to the following self-contained problem: let x E R, let 'T" x exp(- be one-dimensional with second derivative S k. and let Ig x + / 22hg for g (O, 1). We wish to

---

construct fia such that for in constant probability region over exp(-fia) (the "bad set"),
fia((z)) Bg-N(101)) [
+ fia(x) 3 (
fla(x)))) -Q(hk))
(6)
where the contents of the expectation in 6 are the log-rejection probability along one coordinate by a straightforward calculation. By forming product distribution using fia as a building block, and combining with the remaining low-order terms due to the drift ff(2). attain exp( (op(-d)) -d)-sizdd
region where the rejection probability is exp(-Q((kxd)) completing Theorem 2
It remains to construct such hard Sia- The calculation
-fia(zg) + fia(z) (x Zg. fialz) Ka(#g)) =-2h ([))))
g flal s(x, s))ds
suggests the following approach: since Sä 0 always, and the integral puts negative mass on E [0, 2)) and positive on E (1. 1], we want our bad set to have large für but most moves g to result smaller fia-- Our construction patterns this intuition: we choose
T Vh f((())=
2k
K
fia(z) = 3
COs
+ cos
3
Vh
such that our bad set is when cos # is relatively large (which occurs with probability + for small h in one dimension). The period of construction scales with Vh, that most moves /2hg of size ((Vh) will "skip period" and hence hit region with small second derivative, satisfying (
Vh
9-
-0.6
-0.4
-0,7
0
0.2
0.4
0.6
bad set
Figure 1: Second derivative of our hard function Sia- 10, h = 0.01. Starting from inside the hard region, average over g ~N I), move by V2hg decreases the second derivative.
We demonstrate our hard function fhard a product of d copies of fia and a one-dimensional Gaussian, satisfies the following bound. Combining it with Lemmas 3 and [ and using the hard set of points whose gradient is ((Vrs)) and whose coordinatewise cosine is S2(1) (which we show has measure 2 exp(-d). since it coordinatewise captures roughly half the mass), yields Theorem 2
Lemma 4 (Lemmas 7-8, supplement). For fixed Rd with cos v > 0.1 coordinatewise for 2 < i d, with high probability over g IO, and xgg x + /2hg.
f(x) s(xg)
(1:.g ( AV || (2g (V
-(((kd)
4h
We now turn our attention to proving Theorem 33] our main mixing time lower bound. Implicitly in the above discussion, we already proved such lower bound for / w(log d ):): construction fig 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.
From relaxation time to mixing time: proof of Theorem 3
either the cosine construction fhard or the Gaussian
We consider the remaining range, roughly steps to explore the whole space, a simple goal in the absence 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
Ollog d ad) Intuitively, our goal is to show that it takes
We note CLA 20) also used (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 Fng d 2 red log" d steps to move ||=||| by constant. It remains to account for the filter.
Our main observation is that for the only remaining range h = Ollog d A we know such a small step size (scaling with d rather than vd) is overkill for rapid mixing on Gaussians, which only require a step size vd larger. Thus, for this range we choose our hard density to be the simple Gaussian (O, I). We show that with constant probability, in log" steps the true MALA chain never rejects. This allows to couple MALA with our idealized chain, proving mixing time lower bound.
rd
Formally, our main technical lemma this effect is stated in the following, By initializing at the exp(d)-warm) start | S jdd (the "small ball" from Theorem 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 tterating the MALA Markov chain with h = O(log d- ) on ((O, I) for T iterations, with starting distribution the marginal on ||0l| I 3d. With probability at least 99 both of the following events occur for T= 100
Rd log
1. Throughout the Markov chain with iterates (xerosteT, we always have ||oell2 S v.
2. Throughout the Markov chain, the Metropolis filter never rejected.
4 Lower bounds for HMC
In this section, present our main HMC lower bound, Theorem 4 We recall that HMC has two parameters: a number of steps K 2 2 (as the K = case is handled by MALA), and a step size r > 0. Throughout, we focus our attention on the case of a quadratic f(x) 1xx" Az. Without loss of generality (by rotational invariance of HMC), we assume A = diag (A) for 1 S X S K entrywise.
Structure of HMC: 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 (ef. Section 2). show the following relationship between some iterate 2 and the initial position and velocity (To, vo).
Lemma 6 (Lemma 13, supplement). For f(x) 2/=== diag (A) x. iterates (Ex satisfy
[uk]i -pu(77 pn(()>>e)(zan (x)o + n Mooli k
( kk (k+))) ))² =', (x)=) = (-1)-
k + ( 2 +
where pr pz(2) = (-1) OSiSk k k+j 2j
USisk-1
We further observe that the polynomials pæ and q related to the classical Chebyshev polynomials. Let Ti be the 1th Chebyshev polynomial of the first kind, and let Us the htth 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 [Harl3] Bac19] Roughly, these polynomials oscillate between +1 1 in the range [-1,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:
(2) = Th (1 -1-2) 2 qn(2) = Un U (1-
Magically, the extremal points in [-1, 1] where Ty. is 11 are exactly the same as the zeroes of Uk- -1- Combining with L this yields the somewhat surprising conclusion that there are choices of step size 7) where the chain cannot move a coordinate, oscillating between + [ra]: regardless of the choice of og! We use this observation heavily in our lower bound construction to rule out 17 ranges.
8

---

Ruling out the Chebyshev extremal region 1f²
kk We first restrict to the intermediate range We show (Proposition 4, supplement) 3j E [ 1] such that 1 I Xy S K, for
1 2 n k
Ry 2 cos
im K
for
KK
The reason we choose this definition is that the { (Aybje(K-1)
precisely the points where (for = Ay) (1 $) 1 and I )) 0. Hence, by picking hard quadratic function with at least one eigenvalue at the specified Aj. 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 n72 1, we observe the hard function f(x)
| 222 is simple counterexample. In that (=) blows up due to the behavior of
particular, for À = K, x72 2 1, and 1 Chebyshev polynomials outside [-1, 1,, as 1 - ÿ falls outside this range. We use this to argue the acceptance probability from any starting point and any number of steps is exp(-S(dd))
Stronger 17 bounds under constant gap. The Chebyshev polynomial argument demonstrates that to avoid this extremal behavior, we should choose r/² O (( We now give lower bound argument under the stronger assumption that 172 xkZ, with the understanding there is constant gap between this assumption and the region ruled out by the Chebyshev argument.
The main observation (Lemmaa 14, supplement) is that under this assumption, the coefficients of pk and qu supplied in Lemma 6
decay rapidly, In particular, for polynomial pk. the coefficient ratios are
(-1
K
(K+)) 2j
Æ+ク+1
(K (K+ - -) (-
E el-0.1,
(-1Rk))
K
K+))
(2j (2j-2) +
assuming v/ax RT. This implies that both the polynomials pk and чK are governed by their first terms, up to constants, and thus we can apply the proof techniques of Theorem Indeed, we demonstrate that up 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 HMC construction is to close the gap KK implied by behavior of Chebyshev polynomials. We bypass this by taking hard quadratic June which weights two coordinates by 1 and K, and the remaining coordinates by x On d coordinates, we obtain
between the 172 < k required by our geometric argument, and the 172 < x²
K (K))(K- -) 2 (2)+ 1) E [ for all of
(-1p 1イ
k
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 x coordinate can only hurt us by so much, concluding the proof of Theorem
Conclusion
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 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 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 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), common HMC alternative in practice. We state an

---

explicit open problem: can one obtain improved upper bounds, such a v dependence innension-independen rate, for example by using variations of these strategies (variable step sizes)?
Necessity of A lower bound. All of our witness sets throughout the paper are exp( exp(-d) sized. It was observed in [DCWY18] that it possible construct starting distribution with warmness arbitrarily close to /K", the marginal restriction of our witness set obtains this bound for all A 2 e². However, recently [LST20b] proposed 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 Gaussian lower bounds (Theorems and to have witness sets with measure e for c arbitrarily close to 1. However, our witness set for the family of hard non-Gaussian distributions encounters natural barrier measure 24, as it is sign-restricted by the cosine function. We find it interesting to see if a stronger construction rules existing warm starts for all K Z 1, if an upper bound can take advantage of the (LST20b) reduction to obtain improved dependences on dimension.
Acknowledgments
We would like thank Santosh Vempala for numerous helpful conversations, pointers to the literature, and writing suggestions throughout the course of this project.
YL and RS supported by NSF awards CCF-1749609, DMS-18391 16, and DMS-20231 Microsoft Research Faculty Fellowship, Sloan Research Fellowship, and a Packard Fellowship. KT supported by NSF Grant 1C5-0995039 and the Alfred Sloan Foundation.
10

---

References
[Abal6] Martín Abadi. Tensorflow: learning functions at scale. In Proceedings of the 21st ACM SIGPLAN International Conference Functional Programmingg ICFP 2016, Nara, Japan, September 18-22, 2016, page 1, 2016.
[AdFDJ03] Christophe Andrieu, Nando de Freitas. Arnaud Doucet, and Michael I. Jordan. An introduction to MCMC for machine learning. Machine Learning. 50(1-2):5 2003.
[Bac19] Francis Bach. Polynomial magic Chebyshev polynomials. https://francisbadt com/ satebyshev--olyyoomaa.
2019.
[Bar12] David Barber. Bayesian reasoning and machine learning. Cambridge University Press,
2012.
[BE21] Nawaf Bou-Rabee and Andreas Eberle. Mixing time guarantees for unadjusted hamil- tonian monte carlo. CoRR, 0bss/2005000887, 2021.
[Bec17] Amir Beck. First-Order Methods in Optimization. Society for Industrial and Applied Mathematics, 2017.
[Bes94] Julian Besag- Comments on "representations of knowledge in complex systems" by u. grenander and mi miller. Journal of the Royal Statistical Society, Series B, 56:591-592, 1994.
[BGL14) Dominique Bakry, Ivan Gentil, and Michel Ledoux. Analysis and Geometry of Markov Diffusion Operators. Springer, 2014.
[BRH12] Nawaf Bou-Rabee and Martin Hairer. Nonasymptotic mixing of the mala algorithm. IMA Journal of Numerical Analysis, 33(1):80-110, 2012.
[CBL20] Niladri S. Chatterji, Peter L. Bartlett, and Philip M. Long. Oracle lower bounds for stochastic gradient sampling algorithms. CoRR, abs/2002.00291, 2020.
[CCBJ18] Xiang Cheng, Niladri S. Chatterji, Peter L. Bartlett, and Michael I. Jordan. Under- damped langevin MCMC: A non-asymptotic analysis. In Conference On Learning Theory, COLT 2018, Stockholm, Sweden, 6-9 July 2018, pages 10000323,200 2018.
[CDWY19] Yuansi Chen, Raaz Dwivedi, Martin J. Wainwright, and Bin Yu. Fast mixing of metropolized hamiltonian monte carlo: Benefits of multi-step gradients. CoRR, hts/1905.122477 2019.
[CGH+17] 17] Bob Carpenter, Andrew Gelman, Matthew D. Hoffman, Daniel Lee, Ben Goodrich, Michael Betancourt, Marcus Brubaker, Jiqiang Guo, Peter Li, and Allen Riddell. Stan: probabilistic programming language. Journal of Statistical Software, 76(1), 2017.
[Che69] Jeff Cheeger. A lower bound for the smallest eigenvalue of the laplacian. In Proceedings of the Princeton conference in honor of Professor S. Bochner, pages 195-199, 1969.
[Che21] Yuansi Chen. An almost constant lower bound of the isoperimetric coefficient in the kls conjecture. CoRR, abs/2011. 1.661,, 2021.
[CIA++0] Sinho Chewi, Chen Lu, Kwangjun Ahn, Xiang Cheng, Thibaut Le Gouic, and Philippe Rigollet. Optimal dimension dependence of the metropolis-adjusted langevin algorithm. CoRR, abs/2012. 12810, 2020.
[CLW20] Yu Cao, Jianfeng Lu, and Lihan Wang. Complexity of randomized algorithms for underdamped langevin dynamics. CoRR, abs/2003.09906, 2020.
[CV19] Zongchen Chen and Santosh S. Vempala. Optimal convergence rate of hamiltonian monte carlo for strongly logconeave distributions. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDM 2019, September 20-22, 2019, Massachusetts Institute of Technology, Cambridge, MA, USA, pages 64:1-64:12, 2019.

---

[Dal17] Arnak S Dalalyan. Theoretical guarantees for approximate sampling from smooth and log-concave densities. Journal of the Royal Statistical Society: Series (Staristical Methodology), 79(3)6651-676, 2017.
[DCWY18] Raaz Dwivedi, Yuansi Chen, Martin J. Wainwright, and Bin Yu. Log-coneave sampling: Metropolis-hasting algorithms are fast! In Conference On Learning Theory, COLT 2018, Stockholm, Sweden, 6-9 July 2018, pages 793-797, 2018.
[DM19] Alain Durmus and Éric Moulines. nigh-dimensional bayesian inference via the unad- justed langevin algorithm. Bernoulli, 25(44))2254-
2019.
[DMM19] Alain Durmus, Szymon Majewski, and Blazej Miasojedow, Analysis of langevin monte carlo via convex optimization. J. Mach. Learn. Res., 20:73:1-73:46, 2019.
[DR18] Amak S.
Dalalyan and Lionel Riou-Durand. On sampling from log-concave density using kinetic langevin diffusions. CoRR, abs/ 0ts/1807.0900 00338,, 2018.
[GLL20] Rong Ge. Holden Lee, and Jianfeng Lu. Estimating normalizing constants for log- concave distributions: algorithms and lower bounds. In Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 579-586, 2020.
[Har13] Moritz Hardt. The zen of gradient descent. the Zeee-ze--e of- grrddientddeeeeee
html 2013.
[HG14] Matthew D. Hoffman and Andrew Gelman. The no-u-turn sampler: adaptively setting path lengths in hamiltonian monte carlo. Mach. Learn. Res., 15()):1593-1623, 2014.
[JKO98] Richard Jordan, David Kinderlehrer, and Felix Otto. The variational formulation of the fokker-planck equation. SIAM Journal on Mathematical Analysis, 29(1): 1-17, 1998.
[JLLV20] He Jia, Aditi Laddha, Yin Tat Lee, and Santosh S. Vempala. Reducing isotropy and volume to KLS: an o(n 2x² volume algorithm. CoRR, 0tts/2008.021445 2020.
[Liu01] Jun S. Liu. Monte Carlo Strategies in Scientific Computing. Springer-Veriee New York, 2001.
[LST20a] Yin Tat Lee, Ruoqi Shen, and Kevin Tian. Logsmooth gradient concentration and tighter runtimes for metropolized hamiltonian monte carlo. In Conference on Learning Theory, COLT 2020, 2020.
[LST20b] Yin Tat Lee, Ruoqi Shen, and Kevin Tian. Structured logconcave sampling with restricted gaussian oracle. CoRR, abs/2010.03106, 2020.
[LV07] László Lovász and Santosh S. Vempala. The geometry of logconcave functions and sampling algorithms. Random Struct, Algorithmss, 3003):007-35,, 2007.
[MMW+ 19] Wenlong Mou, Yi-An Ma, Martin J. Wainwright, Peter L. Bartlett, and Michael I. Jordan. High-order langevin diffusion yields an accelerated MCMC algorithm. CoRR, 108199 2019.
[MS19] Oren Mangoubi and Aaron Smith. Mixing of hamiltonian monte carlo on strongly log-concave distributions 2: Numerical integrators. In The 22nd International Confer- ence on Artificial Intelligence and Statistics, AISTATS 2019, 16-18 April 2019, Naha, Okinawa, Japan, pages 186-595,77 2019.
[MV18] Oren Mangoubi and Nisheeth K. Vishnoi. Dimensionally tight bounds for second-order hamiltonian monte carlo. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018 NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pages 6030-6040 2018
[Nes03] Yurii Nesterov. Introductory Lectures on Convex Optimization: A Basic Course, volume I. 2003.
12

---

[PSC 15] Marcelo Alejandro Pereyra, Philip Schniter, Emilie Chouzenoux, Jean- -hn-Christtphe Pesquet, Jean Yves Tourneret, Alfred O. Hero, and Steve McLaughlin. A survey of stochastic simulation and optimization methods in signal processing. IEEE Journal on Selected Topics in Signal Processing, 10(2):224-241 241, 2015.
[RC99] Christian P. Robert and George Casella. Monte Carlo Statistical Methods. Springer- Verlag New York. 1999.
[RT96] Gareth O Roberts and Richard L Tweedie. Exponential convergence of langevin distributions and their discrete approximations. Bernoulli, 2(4))341-363, 1996.
[SL19] Ruoqi Shen and Yin Tat Lee. The randomized midpoint method for log- sam- pling. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8- 14, 2019, Vancouver, BC, Canada, pages 2098 2109, 2019.
13


Reviews:
[{"review_id": "TV-1gBb4kgD", "reviewer": "Reviewer_D3MQ", "summary": "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:\n\n1. A lower bound $\\tilde\\Omega(d\\kappa)$ for the mixing time of MALA from an $\\exp(d)$-warm start. This bound is sharp.\n2. A lower bound on the relaxation time of HMC with $K$-steps per iteration of $\\tilde\\Omega(\\kappa\\sqrt{d}/K)$.\n3. Lower bounds on the relaxation time for MALA under Gaussian and general distributions.", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper addresses very relevant algorithms and the fundamental problem of sampling from log concave distributions. It introduces novel techniques, such as the use of Chebyshev polynomials. Some of their lower bounds are nearly tight, in an area where currently lower bounds (of any type) are scarce.\n\nThe main drawback of the paper is the fact that their analyses are algorithmic dependent. However, I am not aware of any general purpose lower bounds for sampling (except for very specific cases, such as in 1D). ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "75PIUPrXuk", "reviewer": "Reviewer_xRQt", "summary": "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.", "questions": "", "limitations": "", "rating": 9, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Essential points:\nThis is a very interesting paper that fills in a gap in the study of lower bounds of popular sampling algorithms. To my knowledge, it is the first paper that proves a non-asymptotic lower bound for sampling in high dimensions from a feasible start. It also raises many questions that are worth pursuing for a full understanding of the well known sampling algorithms, MALA and HMC. For instance, when focusing on the dimension dependence, the result of this paper shows that MALA converges at rate d under an exponential warm start, but past work shows that when the warmness is polynomial in the dimension, the convergence occurs at rate d^{½}, so is there a sharp threshold when the rate changes? Another interesting question is whether it is possible to construct a poly(d) warm start, using fewer than d queries to the potential. If this is not possible, then this paper would have nailed down the dimension dependence of MALA on distributions with smooth and strongly convex potentials.\n\nSuggestions: \nIn Section 3 of supplementary: first paragraph says deriving a “lower bound on the spectral gap”, but instead it should be lower bound on relaxation time, or upper bound on spectral gap.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "-C8Pe2o9ebo", "reviewer": "Reviewer_QuWv", "summary": "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.\n\nSuppose 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.", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This is an excellent addition to the sampling literature: it studies two of the most important sampling algorithms using only natural assumptions and constitutes another major step towards understanding the complexity of these algorithms (and of the sampling problem more generally). Therefore, I strongly recommend acceptance.\n\nHowever, there is an important detail which is glossed over in the introduction of the paper and deserves to be carefully discussed. Namely, one of the core results of this paper, the mixing time lower bound for MALA discussed above, is obtained by constructing a very specific initialization which is exponentially warm. Notably, this initialization is not the standard one used to initialize MALA (a Gaussian with appropriate variance), so the lower bound does not apply to the MALA algorithm as used in practice. Rather, this paper proves the weaker statement that the worst-case mixing time of MALA, over all target distributions in the class AND over all initializations with warm start parameter <= exp(d), is at least dκ. In other words, this paper shows that the previous analyses of MALA which achieve dκ cannot be improved, in the sense that the prior analyses assume only that the initialization is exp(d) warm and obtain their mixing time bounds (and so the analyses do not rule out that the initialization could be the adversarial one constructed in this paper), but it does not preclude the possibility that there are feasible ways of initializing MALA (indeed, perhaps even the standard one with a Gaussian) which mix faster than dκ.\n\nTherefore, it seems that an important problem left open in this work is whether MALA initialized at an appropriate Gaussian has a mixing time closer to the κd lower bound in this work, or closer to the faster mixing time bound of Chewi et al.\n\nTo summarize, I believe this issue is important enough to merit careful discussion upfront. Yet this issue does not change the fact that the results obtained in this paper are quite interesting and important.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper provides lower bounds on mixing and relaxation times of popular sampling algorithms for log-concave distributions. The reviewers all agree that this is a strong contribution that fills in a gap in the existing literature. This is a strong paper!
Decision: Accept (Oral)