Provable Convergence and Limitations of Geometric Tempering for Langevin Dynamics

We thank reviewer mTXb for their detailed reading of our submission, especially the appendix. We have integrated all their suggestions relating to presentation and typos. We respond to the reviewer's question about how practical successes of tempering mesh with our theory in the general response above, and here respond to the minor questions.

Varying the proposal distribution $\nu$ --- For our lower bounds, we use the proposal $\nu = \mathcal{N}(0, 1)$ as is common [1, 2, 3] (indeed this choice is even a default in the Bayesian software package Blackjax), and the analysis is indeed tailored to this choice. The other common choice, which you mention, is the so-called ``uniform proposal", where $\nu = \mathcal{L}$ is the Lebesgue measure. This setting, however, is not precisely covered by our framework, since we need $\nu$ to be a probability measure. On the other hand, our upper bounds can nearly be extended to this case by using the following trick. Consider the scheme $\pi^{\gamma_t}$, for $\gamma_0 > 0$ and $\gamma_t$ non-decreasing. Then if we let $\nu = \pi^{\gamma_0}$ and set $\lambda_t := \frac{\gamma_t - \gamma_0}{1 - \gamma_0}$, we obtain $\mu_t = \pi^{\gamma_t}$. In other words, we can recover the uniform proposal in our framework so long as $\gamma_0 > 0$, so that there is initially at least some weight on $\pi$.

Convergence rate of tempering with a linear schedule in Proposition 7 --- We are not aware of any references which establish similar rates as this result, either for tempered or non-tempered Langevin.

[1] Zhang et al. Differentiable Annealed Importance Sampling and the Perils of Gradient Noise. NeurIPS, 2021.

[2] Thin et al. Monte Carlo Variational Auto-Encoders. ICML, 2021.

[3] Dai et al. An Invitation to Sequential Monte Carlo Samplers. Journal of the American Statistical Association, 2020.

We thank reviewer pomC for their attentive reading of our paper and positive review. We have integrated all their suggestions relating to presentation and typos. We agree with reviewer pomC that discussing when tempering can be useful in practice, as well as comparing to vanilla Langevin is important, and do so in our general response to all reviewers.

We thank reviewer 8HQm for their careful reading of our paper. Let us respond to their question concerning the motivation for considering Gaussian proposals $\nu = \mathcal{N}(0, 1)$. We emphasize that these proposals are indeed used in practice, especially in Bayesian settings. For example, see (1, 2, 3) for three papers which use Gaussian proposals. In fact, the popular Bayesian software library Blackjax even makes the Gaussian proposal the default initialization. More generally, geometric tempering makes sense for a broad variety of proposal distributions, and so we believe that an investigation at this level of generality is of basic interest. Finally, we mention that our upper bounds can yield bounds for schemes of the form $\pi^{\gamma_t}$, so long as $\gamma_0 > 0$ and is non-decreasing: indeed, if we let $\nu = \pi^{\gamma_0}$ and set $\lambda_t := \frac{\gamma_t - \gamma_0}{1 - \gamma_0}$, then $\mu_t = \pi^{\gamma}$.

[1] Zhang et al. Differentiable Annealed Importance Sampling and the Perils of Gradient Noise. NeurIPS, 2021.

[2] Thin et al. Monte Carlo Variational Auto-Encoders. ICML, 2021.

[3] Dai et al. An Invitation to Sequential Monte Carlo Samplers. Journal of the American Statistical Association, 2020.

We thank the reviewer Exbp for their attentive reading: we will correct all typos and better structure the related works paragraphs. We respond below to their other questions and comments.

Applicability of Corollary 5 --- the corollary requires initializing Langevin dynamics at the proposal, i.e. $p_0 = \nu$, but we do not require that $\lambda_0 = 0$. We refer the reviewer to the short proof in Appendix C.1: to control $\mathrm{KL}(p_0\|\mu_0)$ we use the tempering rule, and ultimately simply bound $\lambda_0$ by $1$.

Theorem 9 in case $\lambda_i$ is close to $1$--- We are in complete agreement with the reviewers' intution, and note that in Theorem 9, $\delta_k$ is defined as $\delta_k := 8m^2 e^{-(1 - \lambda_k)m^2}$, so that when $\lambda_k$ is close to $1$, there is no exponential slow-down. Actually, Theorem 9 makes this intuition quantitative and states that so long as $1 - \lambda_k \leqslant C m^{-2}$, the slow-down will only be of polynomial order in the mean separation.

Choosing an optimal proposal distribution knowing some information about the target distribution --- consider the setup when the target is a mixture of two symmetric Gaussian distributions and we initialize with a Gaussian located “in between” the two target modes, specifically at the barycenter. Then, convergence is provably fast for Tempered Langevin [1, Example 1] and related sampling processes [2]. Yet, initializing in this way requires knowing the locations of all target modes: this would require solving a “global optimization” problem, which can be a harder problem than the original problem of sampling from the target distribution [3].

Do the lower bounds hold in higher dimensions? --- We expect that the lower bounds go through in higher dimensions with minor modifications. The key high-level point in all of the lower bounds is that at intermediate times, the tempering path becomes bimodal, and if the law $p_t$ of the particle following the tempering is too concentrated in one of the modes vs. another, it will take exponential time to spread mass between the modes (for example, see Prop. 22 in Appendix D). In other words, and as illustrated in Fig. 4 Appendix E, the core phenomenon behind our lower bounds is the fact that along the geometric path, mass tends to “teleport” from one mode to another, preventing Langevin to converge as the particles eventually get stuck in the first encountered mode.

All of this translates intuitively, and likely rigorously, without issue to higher dimensions. We chose to present the lower bounds in dimension $1$ for simplicity, as well as to make it clear that the problem is not a curse of dimensionality (which may be common across methods), but instead a problem specifically with the tempered Langevin itself.

Why additional dissipativity assumption? --- Our only use of the dissipativity assumptions is to control the second moment of $p_t$, the law of the process $X_t$ given in (9). At a technical level, the reason why we have this extra assumption as compared to the standard analyses of vanilla Langevin is precisely because of the additional terms arising from the tempering. Weakening this assumption further is an interesting direction for future work.

Convergence under weaker functional inequalities than log-Sobolev? --- The main technical novelty of our analysis is the way that we deal with the new terms arising from the tempering dynamics (see Step 1 and Step 2 in Appendix A.2, as well as the supporting Lemmas in Appendix A.4). In particular, the extra terms which arise here are particularly suitable to analysis when the Lyapunov function is $\mathrm{KL}$. For example, we are not aware of a straightforward means of extending our analysis to $\chi^2$. Since these alternative functional inequalities imply convergence in alternative Lyapunov functions (e.g. Poincaré involves analysis in $\chi^2$), we are therefore not aware of a straightforward extension of our results to weaker isoperimetric assumptions.

[1] Guo et al. Provable Benefit of Annealed Langevin Monte Carlo for Non-log-concave Sampling. Arxiv, 2024.

[2] Madras and Zheng. On the Swapping Algorithm. Journal of Random Struct. Algorithms, 2003.

[3] Ma et al. Sampling can be faster than optimization. PNAS, 2019.

I thank the authors for their detailed response. I'm happy to recommend acceptance, and have decided to keep my score based on my perceived significance of the results.