Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 9: Top 15% of accepted NeurIPS papers, strong accept
review_content: 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.
main_review: Essential points:
This 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.

Suggestions: 
In 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.

limitations_and_societal_impact: yes
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: 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:

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.
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.

The 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). 
limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: 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.

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.
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.

However, 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κ.

Therefore, 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.

To 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.
limitations_and_societal_impact: Yes.
review_title: null

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)