Abstract

We study the problem of sampling from a distribution $\mu$ with density proportional to $e^{-V}$ for a potential function $V:\bb R^d\to \bb R$ with query access to $V$ and $\grad V$. We begin with two standard assumptions on $\mu$:

(1) The potential function $V$ is $L$-smooth.
(2) The second moment of $\mu$ is finite, , $\E[X\sim \mu]{\|X\|^2}\leq M$ for some $M<\infty$.

Recently, He and Zhang (COLT, 2025) showed that the query complexity for sampling from this family of distributions can be as large as $\tp{\frac{LM}{d\eps}}^{\Omega(d)}$, where $\eps$ is the target accuracy in total variation distance, and this indicates that the constant can be arbitrarily large. On the other hand, another common assumption in the literature on diffusion-based sampling algorithms (see , the work of Chen, Chewi, Li, Li, Salim and Zhang (ICLR, 2023)) strengthens the smoothness condition (1) on $V$ to the following:

(1*) The potential function of every distribution along the Ornstein-Uhlenbeck process starting from $\mu$ is $L$-smooth.

We show that under the assumptions (1*) and (2), the query complexity of sampling from $\mu$ can be reduced to $\!{poly}(L,d)\cdot \tp{\frac{Ld+M}{\eps^2}}^{\+O(L+1)}$, which is polynomial in $d$ and $\frac{1}{\eps}$ when $L=\+O(1)$ and $M=\!{poly}(d)$. This improves the algorithm with quasi-polynomial query complexity developed by Huang, Zou, Dong, Ma and Zhang (COLT, 2024). Our results imply that the seemingly moderate strengthening of the smoothness condition (1) to (1*) leads to an exponential separation in the query complexity for sampling.

Furthermore, we show that together with the assumption (1*) and the stronger moment assumption that $\norm{X}$ is $\lambda$-sub-Gaussian for $X\sim\mu$, the constant of $\mu$ is at most $\+O\tp{\lambda}^{2(L+1)}$. We can also establish a modified log-Sobolev inequality for $\mu$ under these conditions. As an application of our technique, we obtain a new estimate of the modified log-Sobolev constant for a specific class of mixtures of strongly log-concave distributions.

1 Introduction↩︎

We study the problem of sampling from a probability distribution $\mu$ over $\bb R^d$ with density $\propto e^{-V}$, given query access to the value and gradient of its potential function $V:\bb R^d\to \bb R$. This is a fundamental computational task across various fields, including theoretical computer science, machine learning, and statistical physics. The problem of sampling has been studied extensively, resulting in numerous proposed algorithms (see [1] for a modern and comprehensive treatment).

A long line of research established that these algorithms converge within polynomial-many queries (with regard to $d$) under various metrics when $\mu$ is log-concave (e.g., [2]–[5]), or satisfies good isoperimetric inequalities (e.g., [5]–[8]). However, the problem becomes significantly more challenging beyond these well-behaved settings, and much less is known. For the lower bounds in the most general case, the results of [9], [10] indicate that any sampling algorithm requires $\tp{\frac{LM}{\eps d}}^{\Omega(d)}$ number of queries in general for the class of distributions that satisfy only the following two minimal assumptions, where $\eps$ is the desired accuracy in total variation distance:

Assumption 1. The potential function $V$ is differentiable and $L$-smooth, , for any $x,y\in \bb R^d$, $\|\grad V(x)-\grad V(y)\| \leq L \|x-y\|$.

Assumption 2. The second moment $\E[X\sim \mu]{\|X\|^2}\leq M$ for some $M<\infty$.

These distributions do not necessarily satisfy the log-concavity property or good isoperimetric inequalities, leading to a growing interest in understanding the extent to which efficient sampling algorithms exist under these minimal conditions. Some previous works show that efficient sampling is still possible when the target distributions possess specific structures, such as being a mixture of Gaussians or having a similar shape (, see [9]). Other works derive convergence bounds in terms of intricate parameters of the target distribution, such as the action of a curve ([11]). These works primarily reply on annealing or tempering methods.

Another parallel line of research shows that denoising diffusion probabilistic models (DDPMs) can sample from the target distribution $\mu$ with polynomial queries under very weak conditions, as long as the score functions along the Ornstein-Uhlenbeck process (OU process) can be estimated efficiently (e.g., [12]–[15]).

Following this line, the work of [16]–[18] attempts to further provide a direct implementation of score function estimation without relying on neural networks. Let $\set{X^{\!{OU}}(t)}_{t\geq 0}$ be the OU process starting from $\mu$ and $\xi^{\!{OU}}_t$ be the law of $X^{\!{OU}}(t)$. The work [17] designs a recursive procedure to estimate the score functions and shows that a total query complexity of at most $\exp\tp{\+O(\ol{L}^3)\cdot \!{polylog}(Ld+M)}$ can be achieved with $\ol L = \sup_{t\geq 0} L_t^{\!{OU}}$. Crucially, this result relies on the regularity of $\set{\xi_t^{\!{OU}}}_{t\geq 0}$, formulated as follows:

Assumption 3. The potential function $-\log \xi^{\!{OU}}_t$ is twice differentiable and $L^{\!{OU}}_t$-smooth for any $t\in [0,\infty)$.

While 3 is a prevalent technical condition in the analysis of diffusion-based algorithms (e.g., [12]–[15], [19]), its precise nature and implications remain a subject of discussion. On one hand, some studies refer to it as a standard or relaxible assumption (e.g., [17], [20]). On the other hand, several works have noted that this condition is non-trivial and difficult to verify, potentially excluding important classes of distributions (e.g., [14], [21]).

Furthermore, it is worth noting that the dependence of the bound in [17] on the dimension $d$ is quasi-polynomial, whereas the established lower bound for general distributions is exponential ([9], [10]). The diverging interpretations of 3 with this stark contrast in query complexity, naturally raises the following question:

What is the role of 3 in efficient sampling? In particular, could it enable a sampler with polynomial query complexity?

In this work, we answer the above question by proposing a variant of the restricted Gaussian dynamics to sample from $\mu$ under 3 with a query complexity polynomial in $d$. Furthermore, we can directly establish a inequality and a modified log-Sobolev inequality when the target distribution satisfies 3 and stronger moment bounds. Our results demonstrate that 3 indeed plays an important role in enabling efficient sampling. It implicitly captures certain favorable structural properties of the distribution that 1 fails to reflect. Our results are summarized in 1.1.

Technique-wise, our proofs imply that the recursive paradigm designed in [17] is unnecessary. Our analysis of the restricted Gaussian dynamics differs from previous analyses for well-behaved distributions (, [5], [22]–[24]) and is based on the recently developed path-wise technique for analyzing high-dimensional distributions (see [25] for an introduction). The main ingredients of our analysis are the concatenation of localization schemes and the approximate conservation of variance and entropy for the stochastic localization processes introduced and popularized in [26]. Similar techniques or ideas have been used in sampling from discrete distributions, such as the Gibbs distribution of the Ising model and the hardcore model (see , [26], [27]). We will present an overview of our techniques in 1.2.

1.1 Main results↩︎

Our first main result states that any distribution satisfying 2 and 3 can be approximated with an error of $\eps>0$ in total variation distance using polynomially many queries.

Theorem 1 (A simplified version of 8). There exists an algorithm which, for any target distribution $\mu$ satisfying 2 and 3, outputs a sample from a distribution $\tilde{\mu}$ such that $\!{TV}(\tilde{\mu},\mu)\leq \eps$, with expected number of queries bounded by \[N=\wt{\+O}\tp{\ol{L}d\cdot (V(0)-\min V + d^2)}\cdot \tp{\frac{\ol{L}d+M}{\eps^2}}^{\+O(\ol L+1)},\] where $\ol L= \sup_{t\geq 0}L_t^{\!{OU}}$.¹

Without loss of generality, we can regard $V(0)-\min V = \!{poly}(M,\ol{L},d)$. When $\ol L$ is bounded, the query complexity given in 1 is polynomial in $d$. This improves the $\exp\tp{\+O(\ol{L}^3)\cdot \!{polylog}(\ol{L}d+M)}$ bound in [17] by reducing the query complexity from quasi-polynomial to polynomial, which solves an open problem in [10]. We further remark that our analysis readily extends to KL divergence. By tracking entropy rather than variance in the proof of 1, one can establish KL convergence with a comparable query complexity.

Although 1 only bounds the expected query complexity, we can obtain a worst-case query complexity bound of at most $\frac{N}{\eps}$ by imposing a hard cutoff after the $\frac{N}{\eps}$-th query. By a simple application of the Markov inequality, we can demonstrate that the sampler still maintains its accuracy guarantee. Comparing this bound with the $\tp{\frac{LM}{d\eps}}^{\Omega(d)}$ lower bound in [10] — achieving under 2 and 1 — the exponential gap reveals that the additional assumption, 3, which frequently appears in diffusion-based works, is indeed crucial for enabling efficient sampling.

1 shows that distributions satisfying 2 and 3 admit a polynomial-time sampling algorithm. Our next result demonstrates that further strengthening the moment condition to 4 allows us to directly establish a inequality and a modified log-Sobolev inequality for the target distribution.

Assumption 4. With $X\sim \mu$, the distribution of $\|X\|$ is a $\lambda$-sub-Gaussian distribution for some constant $\lambda>0$, i.e., $\E[X\sim \mu]{e^{r^2 \|X\|^2}}\leq e^{r^2 \lambda^2}$ for any $r\in [-1/\lambda, 1/\lambda]$.

Note that 4 is stronger than assuming $X\sim\mu$ to be $\lambda$-sub-Gaussian and weaker than assuming $X$ satisfies $T_1$-transportation inequality with constant $\lambda^2$ (see , [28]).

Theorem 2 (A simplified version of [thm:PI,thm:mLSI]). If 3 and 4 hold, then the distribution satisfies a inequality with constant \[C^{\!{PI}}_{\mu}\leq \min_{s\in \left(0,\frac{\log 2}{4\lambda^2}\right]} \frac{2}{2-e^{4s\lambda^2}}\cdot \tp{\frac{s+1}{s}}^{\ol L +1},\] and satisfies a modified log-Sobolev inequality with constant \[C^{\!{mLSI}}_{\mu}\le \min_{s_0\in \left(0,\frac{1}{12\lambda^2}\right]} \tp{3+\frac{12s_0\lambda^2+1}{2-e^{4s_0\lambda^2}}}\cdot \tp{\frac{s+1}{s}}^{\ol L +1},\] where $\ol L= \sup_{t\geq 0}L_t^{\!{OU}}$.

It is worth noting that 3 plays a crucial role in establishing 2. If it were replaced by the weaker 1, the conclusion would no longer hold. For example, consider the distributions constructed in Section 3 of [10], which satisfies 4 with parameter $\lambda = \+O\tp{\sqrt{M}}$ (we choose $\eps=\+O(1)$ in their setting). Suppose, for the sake of contradiction, that the inequality in 2 still holds under only 1. Then it implies a polynomial-time sampler for those distributions, which contradicts the exponential lower bound in [10]. This indicates that compared to 1, 3 implicitly captures some additional geometric properties of the distribution.

We also apply our method to typical multimodal distributions. Using analytical techniques similar to those in 2, we explicitly compute the modified log-Sobolev constant for a specific class of mixture of strongly log-concave distributions.

Theorem 3. Suppose $\rho$ is an $m$-strongly log-concave and $L$-log-smooth distribution and $\nu$ is supported inside a Euclidean ball with radius $R>0$. The modified log-Sobolev constant of mixture distribution $\mu=\nu*\rho$ satisfies \[C^{\!{mLSI}}_{\mu}\leq \frac{1}{2m}\cdot e^{LR^2}.\]

As a direct corollary, when $\rho$ is the Gaussian distribution $\+N(0,\Sigma)$, 3 recovers the result in [29], which is the best known bound on the modified log-Sobolev constant for this class of mixture distributions. Specifically, letting $\lambda_{\min}(\Sigma)$ be the minimum eigenvalue of $\Sigma$, we have $C^{\!{mLSI}}_\mu\leq \frac{1}{2}\norm{\Sigma}_{\!{op}}\cdot e^{\lambda_{\min}(\Sigma)^{-1}\cdot R^2}$.

Moreover, the concatenation argument (see 1.2 for a brief introduction) used in our proof of [thm:main-PI,thm:main-mix] is of independent interest, and might be extended to establish functional inequalities for certain distributions beyond 4, as long as the evolution of the smoothness along the OU process can be effectively analyzed.

1.2 Technical overview↩︎

Our algorithm is a variant of the restricted Gaussian dynamics, which is also known as the proximal sampler (see [22]). The key step in the convergence analysis is to bound the constant of the restricted Gaussian dynamics. This not only implies the rapid mixing of the algorithm, but also allows us to use a concatenation argument to establish the functional inequalities in [thm:main-PI,thm:main-mix].

1.2.0.1 3 and the covariance bound of the stochastic localization process

Before delving into the details, we first clarify the relationship between the OU process and stochastic localization process, to identify the condition that 3 corresponds to in the stochastic localization framework.

Consider the stochastic differential equation of the OU process \[\require{physics} \dd X^{\!{OU}}(t) = - X^{\!{OU}}(t) \dd t + \sqrt{2} \dd B(t),\;X^{\!{OU}}(0)\sim \mu,\] and the scheme that induces the stochastic localization process \[X(s) = s\cdot X + B(s),\;X\sim \mu.\] Intuitively, the random variables $X^{\!{OU}}(t)$ and $X(s)$ are related through a scaling transformation. Indeed, via direct calculations, we can prove that $X^{\!{OU}}(t)$, and $\sqrt{\frac{1}{s(1+s)}}\cdot X(s)$ with $s = \frac{e^{-2t}}{1-e^{-2t}}$, have the same distribution. Let $\nu_s(\cdot\,|\,z)$ be the conditional law of $X$ given $X(s)=z$, and when the information of $X(s)$ is clear, we may write it as $\nu_s$ for brevity. Building on this correspondence between the two processes, we can examine 3 from the perspective of the stochastic localization process. To be specific, it translates into the following condition on the covariance of $\+T_v \nu_s(\cdot\,|\,z)$, where $\+T_v \nu_s(\cdot\,|\,z)$ is the exponentially tilted distribution with $\+T_v \nu_s(x\,|\,z) \propto e^{\inner{v}{x}}\cdot \nu_s(x\,|\,z)$.

For any $s\in \left[0, \infty \right)$, any $v,z\in \bb R^d$, \[\tp{ \frac{1}{s}-\frac{ L_s}{s(1+s)}}\cdot \!{Id}_d\preceq \cov{\+T_v\nu_s(\cdot\,|\,z)} \preceq \tp{\frac{1}{s} + \frac{ L_s }{s(1+s)}}\cdot \!{Id}_d,\] where $L_s=L^{\!{OU}}_{t}$ with $t=\log\sqrt{\frac{s+1}{s}}$.

1.2.0.2 The challenges to prove [thm:main-ub,thm:main-PI] under [cond:cov]

To prove 1, our target is to bound the constant of the restricted Gaussian dynamics. This is a discrete-time Markov chain $\set{Y_k}_{k\geq 0}$ induced by the stochastic localization process. For a fixed $T>0$, the restricted Gaussian dynamics with transition kernel $\*P^{(T)}$ executes as follows at each iteration $k$:

draw $\hat{Y}_k\sim \+N\tp{T\cdot Y_{k-1}, T\cdot \!{Id}_d}$;
then draw $Y_k\sim \nu_T\tp{\cdot\,|\,\hat{Y}_k}$.

Let $\xi_s$ be the law of $X(s)$. From Proposition [prop:PIofSL], the constant of this chain is \[C^{\!{PI}}_{\mu}\tp{\*P^{(T)}} = \sup_{f\colon \bb R^d\to \bb R} \frac{\Var[\mu]{f}}{\E[X(s)\sim \xi_T]{\Var[\nu_T]{f}}}.\] On the other hand, to prove 2,² we aim to directly bound the constant of the target distribution $\mu$, which satisfies \[\begin{align} C^{\!{PI}}_{\mu} &= \sup_{f:\bb R^d \to \bb R} \frac{\Var[\mu]{f}}{\E[\mu]{\|\grad f\|^2}} = \sup_{f:\bb R^d \to \bb R} \frac{\E[\xi_T]{\Var[\nu_T]{f}}}{\E[\mu]{\|\grad f\|^2}}\cdot \frac{\Var[\mu]{f}}{\E[\xi_T]{\Var[\nu_T]{f}}} \notag \\ &\leq C^{\!{PI}}_{\mu}\tp{\*P^{(T)}}\cdot \sup_{f:\bb R^d \to \bb R} \frac{\E[\xi_T]{\Var[\nu_T]{f}}}{\E[\xi_T]{\E[\nu_T]{\|\grad f\|^2}}}. \label{eq:overview-1} \end{align}\tag{1}\] From the result on the approximate conservation of variance (see 4), given [cond:cov], $\require{physics} C^{\!{PI}}_{\mu}\tp{\*P^{(T)}} \leq \exp\set{\int_0^T \tp{\frac{1}{s} + \frac{ L_s }{s(1+s)}} \dd s}$. However, two key technical challenges remain:

the integral $\require{physics} \int_0^T \tp{\frac{1}{s} + \frac{ L_s }{s(1+s)}} \dd s$ diverges even for small $T$;
one needs to sample from $\nu_T\tp{\cdot\,|\,\hat{Y}_k}$ in the algorithm efficiently (1), or bound the constant for $\nu_T$ (2).

1.2.0.3 Late initialization and three-phase concatenation

To address the two issues discussed above, we analyze the evolvement of the variance along the stochastic processes in three phases. Note that in the stochastic localization process $\set{\nu_s}_{s\geq 0}$, \[\nu_s(x)\propto \mu(x)\cdot \exp\set{-\frac{\norm{X(s) - sx}^2}{2s}}.\] Then we have the following three observations:

$\nu_{s_0}\approx \nu_0$ and $\xi_{s_0} \approx \+N(0,s_0(s_0+1)\!{Id}_d)$ for small enough $s_0$;
$\require{physics} \int_{s_0}^T \tp{\frac{1}{s} + \frac{ L_s }{s(1+s)}} \dd s$ is bounded for any $0<s_0\leq T$;
if $\mu$ satisfies 1, then $\nu_T$ is $(T-L)$-strongly log-concave for $T>L$.

None

Figure 1: The stochastic localization process of $\mu$.

As shown in 1, we divide the stochastic localization process into three phases and analyze $\set{\nu_s}_{s\in [0,s_0)}$, $\set{\nu_s}_{s\in [s_0,T)}$ and $\nu_T$ respectively.

We first explain how to resolve the challenges in the proof of 1. For the sake of clarity, some notation is simplified and full technical details appear in the formal proofs in 4. Note that to sample from $\mu$, it suffices to draw $X(s_0)\sim \xi_{s_0}$ and then sample from $\nu_{s_0}(\cdot\,|\,X(s_0))$. By the first observation, $\xi_{s_0}$ can be approximated by a Gaussian distribution $\+N(0,s_0(s_0+1)\cdot\!{Id}_d)$. Thus, the target is reduced to simulate $\nu_{s_0}$. We call this a late initialization. Then the second observation implies that, although bounding the constant of the restricted Gaussian dynamics with respect to $\mu$ might be difficult, it is possible to control the constant of the dynamics associated with the new target $\nu_{s_0}$ as the integral $\require{physics} \int_{s_0}^T \tp{\frac{1}{s} + \frac{ L_s }{s(1+s)}} \dd s$ is bounded. Of course, implementing this restricted Gaussian dynamics with respect to $\nu_{s_0}$ again involves the issue of sampling from $\nu_T$. By the third observation, with large $T$, $\nu_T$ becomes strongly log-concave, allowing efficient sampling using algorithms like rejection sampling. Combining all these, we can prove the rapid mixing of the restricted Gaussian dynamics with this late initialization scheme.

For the difficulty in the proof of 2, we handle it in a similar way. We view the constant of $\mu$ as the result of a three-segment concatenation: \[\begin{align} C^{\!{PI}}_{\mu}&= \sup_{f:\bb R^d \to \bb R} \underbrace{\frac{\Var[\mu]{f}}{\E[\xi_{s_0}]{\Var[\nu_{s_0}]{f}}}}_{(\uppercase{\romannumeral 1})} \cdot \underbrace{\frac{\E[\xi_{s_0}]{\Var[\nu_{s_0}]{f}}}{\E[\xi_T]{\Var[\nu_T]{f}}}}_{(\uppercase{\romannumeral 2})} \cdot \underbrace{\frac{\E[\xi_T]{\Var[\nu_T]{f}}}{\E[\mu]{\|\grad f\|^2}}}_{(\uppercase{\romannumeral 3})}. \end{align}\] For part $(\uppercase{\romannumeral 1})$, as $s_0$ is small, we can derive an explicit bound of this ratio under 4. For part $(\uppercase{\romannumeral 2})$, the second observation ensures that the integral $\require{physics} \int_{s_0}^T \tp{\frac{1}{s} + \frac{ L_s }{s(1+s)}} \dd s$ is bounded, which allows us to control this term accordingly. For part $(\uppercase{\romannumeral 3})$, the third observation implies that $\nu_T$ is $(T-L)$-strongly log-concave. As a result, its constant is bounded almost surely by $\frac{1}{T-L}$ (see , [30]), which provides a direct upper bound for $(\uppercase{\romannumeral 3})$. Finally, we can derive the desired bound on the constant $C^{\!{PI}}_{\mu}$ by concatenate the three parts. We remark that the bound in part $(\uppercase{\romannumeral 1})$ is trivial in some other localization schemes such as the one associated to the field dynamics for sampling from hardcore model as well as the Föllmer process for sampling from the Ising model ([27]) since an $\+O(\sqrt{d})\cdot \!{Id}_d$ upper bound for the covariances in that part always holds (see also [31]). However, in our case, a uniform upper bound (over every $y$) for $\cov{\nu_s(\cdot\,|\, y)}$ does not exist and therefore our special treatment of the first phase is necessary.

Finally, we prove 3 by applying the same concatenation argument to the mixture of strongly log-concave distributions. In order to obtain an upper bound for the covariance of distributions along the stochastic localization process, we again relate the quantity to smoothness of the potential function along the OU process, which can be bounded under the conditions in 3.

1.3 Organization↩︎

We begin by introducing some preliminaries in 2. In 3, we establish a connection between the stochastic localization process and the OU process, which allows us to derive [cond:cov] from 3. Building on this foundation, we present our main algorithm and its analysis in 4 to prove 1. Finally, we prove the functional inequalities stated in 2 and 3 in 5.

2 Preliminaries↩︎

2.1 Notations↩︎

Throughout this paper, all distributions are assumed to be absolutely continuous with respect to the Lebesgue measure. For simplicity, we slightly abuse the notation and use the same symbol to denote both the distribution and its density. For random variables $X\in\bb R^d$ and $Y\in\bb R^d$, we use $p_X$ to denote the distribution of $X$, $p_{X,Y}$ to denote the joint distribution and $p_{X|Y}(\cdot |y)$ to represent the conditional distribution of $X$ given $Y=y$. Given a distribution $\mu$, we define $\m{\mu} = \E[X\sim \mu]{X}$, $\var{\mu} = \Var[X\sim \mu]{X}$ (or $\cov{\mu}=\Cov[X\sim \mu]{X}$ in high-dimensional cases) to denote its expectation and variance (or covariance) respectively.

For a measure $\mu$ over $\bb R^d$ and a vector $v\in \bb R^d$, define the exponentially tilted distribution $\+T_v \mu$ as \[\forall x\in \bb R^d,\;\+T_v \mu(x) \propto e^{\inner{v}{x}} \mu(x).\]

We use $\+N(u, \Sigma)$ to denote the multivariate Gaussian distribution with mean $u\in \bb R^d$ and covariance $\Sigma\in \bb R^{d\times d}$. The notation $\+N(x; u, \Sigma)$ represents the density of $\+N(u, \Sigma)$ at $x$. Denote the Poisson distribution with mean $\lambda$ as $\!{Pois}(\lambda)$.

In this paper, $\log$ refers to the natural logarithm with base $e$. For two distributions $\mu_1$ and $\mu_2$ over $\bb R^d$, their total variation distance is $\require{physics} \!{TV}(\mu_1,\mu_2) = \tfrac{1}{2}\cdot \int_{\bb R^d} \abs{\mu_1(x)-\mu_2(x)} \dd x$. Assuming $\mu_1 \ll \mu_2$, the Kullback—Leibler divergence (KL divergence), $\chi^2$ divergence and divergence with parameter $q> 1$ are respectively defined as

$\require{physics} \!{KL}\tp{\mu_1\,\|\,\mu_2} = \int_{\bb R^d} \mu_1(x)\log \frac{\mu_1(x)}{\mu_2(x)} \dd x$;
$\require{physics} \chi^2(\mu_1\,\|\,\mu_2) = \int_{\bb R^d} \frac{\tp{\mu_1(x)-\mu_2(x)}^2}{\mu_2(x)} \dd x$;
$\require{physics} \+R_q (\mu_1\,\|\,\mu_2) = \frac{1}{q-1}\log \tp{\int_{\bb R^d} \tp{\frac{\mu_1(x)}{\mu_2(x)}}^{q} \mu_2(x) \dd x}$.

Specifically, $\+R_\infty (\mu_1\|\mu_2) = \log\tp{\sup_{x\in \bb R^d} \frac{\mu_1(x)}{\mu_2(x)}}$. By definition, $\+R_2 (\mu_1\|\mu_2) = \log\tp{1+\chi^2(\mu_1\|\mu_2)}$. For any $p\geq q>1$, $\+R_q (\mu_1\|\mu_2) \leq \+R_p (\mu_1\|\mu_2)$.

For a matrix $A\in \bb R^{d\times d}$, its operator norm $\|A\|_{\!{op}}$ is defined as $\|A\|_{\!{op}} = \sup_{y\in \bb R^d\atop \|y\|=1} \|Ay\|_2$.

2.2 The Markov chain, inequality and modified log-Sobolev inequality↩︎

Consider a Markov chain with state space $\bb R^d$, transition kernel $\*P$ and stationary distribution $\mu$. In this work, we only consider those distributions that admit strictly positive densities with respect to the Lebesgue measure. Therefore, we slightly abuse the notation by using $\*P(x,y)$ to denote the probability density function corresponding to the transition kernel $\require{physics} \*P(x, \dd y)$. Then we say $\*P$ is reversible with regard to $\mu$ if for all $x,y\in \bb R^d$, \[\mu(x)\cdot \*P(x,y) = \mu(y)\cdot \*P(y,x).\] Define the Dirichlet form \[\require{physics} \+E_{\*P}(f,g) = \frac{1}{2}\cdot \int_{\Omega\times \Omega} \tp{f(x)-f(y)}\tp{g(x)-g(y)} \mu(x)\*P(x,\dd y) \dd x .\] We say $\mu$ satisfies a inequality (PI) with regard to the Markov chain $\*P$ with constant $C$ if for all functions $f:\bb R^d \to \bb R$ with $\+E_{\*P}(f,f)\neq 0$, \[\Var[\mu]{f}\leq C \cdot \+E_{\*P}(f,f).\]

Similarly, $\mu$ is said to satisfy a modified log-Sobolev inequality (mLSI) with regard to $\*P$ with constant $C'$ if for all positive functions $f:\bb R^d \to \bb R_{> 0}$ with $\+E_{\*P}(f,\log f)\neq 0$, \[\Ent[\mu]{f}\leq C' \cdot \+E_{\*P}(f,\log f),\] where the entropy \[\Ent[\mu]{f} \defeq \E[\mu]{f\log f} - \E[\mu]{f}\cdot \log \E[\mu]{f}.\]

Denote the constant and modified log-Sobolev constant as $C^{\!{PI}}_{\mu}\tp{\*P} \defeq \sup_{f\colon \bb R^d\to \bb R} \frac{\Var[\mu]{f}}{\+E_{\*P}(f,f)}$ and $C^{\!{mLSI}}_{\mu}\tp{\*P} \defeq \sup_{f\colon \bb R^d\to \bb R_{> 0}} \frac{\Ent[\mu]{f}}{\+E_{\*P}(f,\log f)}$ respectively. Specifically, when the Markov chain is the Langevin dynamics with trajectory $\require{physics} \dd X(t) = - \grad V(X(t))\dd t + \sqrt{2}\dd B(t)$, it recovers the classical inequality: \[\Var[\mu]{f}\leq C \cdot \E[\mu]{\norm{\grad f}^2} \label{eq:PI}\tag{2}\] and the classical modified log-Sobolev inequality: \[\Ent[\mu]{f}\leq C'\cdot \E[\mu]{\inner{\grad f}{\grad\log f}} = C' \cdot \E[\mu]{f^{-1}\norm{\grad f}^2}. \label{eq:mLSI}\tag{3}\]

In this work, when the Markov chain is not explicitly specified, the terms inequality and modified log-Sobolev inequality refer to [eq:PI,eq:mLSI]. Define $C^{\!{PI}}_{\mu} \defeq \sup_{f\colon \bb R^d\to \bb R} \frac{\Var[\mu]{f}}{\E[\mu]{\norm{\grad f}^2}}$ and $C^{\!{mLSI}}_{\mu} \defeq \sup_{f\colon \bb R^d\to \bb R_{>0}} \frac{\Ent[\mu]{f}}{\E[\mu]{f^{-1}\norm{\grad f}^2}}$.

2.3 The stochastic localization process↩︎

Let \[X(s) = s\cdot X + B(s),\;X\sim \mu \label{eq:SL}\tag{4}\] with $\set{B(s)}_{s\geq 0}$ being a standard Brownian motion. Let $\xi_s$ be the law of $X(s)$ and $\nu_s(\cdot\,|\,y)$ be the conditional distribution of $X$ given $X(s)=y$. When the information of $y$ is clear, we will omit $y$ and use $\nu_s$ for simplicity. We can regard $\nu_s$ as a random distribution due to the randomness of $X(s)$. When $s=0$, $\nu_0=\mu$ and when $s=\infty$, $\nu_{\infty}$ is the Dirac distribution $\delta_{X(s)}$. The process $\set{\nu_s}_{s\geq 0}$ is the well-known stochastic localization process (SL process).

For each $T\geq 0$, the SL process induces a natural discrete-time Markov chain $\set{Y_k}_{k\geq 0}$ with transition kernel $\*P^{(T)}$, named as the restricted Gaussian dynamics. The transition kernel is defined as follows. In the $k$-th iteration,

(down-walk) draw $\hat{Y}_k\sim \+N\tp{T\cdot Y_{k-1}, T\cdot \!{Id}_d}$;
(up-walk) then draw $Y_k\sim \nu_T$ with $X(T)=\hat{Y}_k$.

The walk can be pleasantly interpreted as the down-up walk along the SL process. The down-step walks from $\nu_\infty$ to $\nu_T$ by drawing $\hat{Y}_k\sim p_{X(T)\,|\,X(\infty)}(\cdot\,|\,Y_{k-1})$; and the up-step is simply its adjoint operator, or equivalently drawing $Y_k\sim p_{X(\infty)\,|\,X(T)}(\cdot\,|\,\hat{Y}_k)$.

From direct calculation, we know for any $x\in \bb R^d$ and any Borel set $A\subseteq \bb R^d$, \[\*P^{(T)}(x,A) = \E[X(T)\sim \xi_T]{\frac{\nu_T(x)\cdot \nu_T(A)}{\mu(x)}}. \label{eq:MC}\tag{5}\]

The propositions and theorem below are well-known results for localization schemes.

The Markov chain with transition kernel $\*P^{(T)}$ is a reversible Markov chain with stationary measure $\mu$.

The distribution $\mu$ satisfies a inequality with regard to the Markov chain $\*P^{(T)}$ with constant $C^{\!{PI}}_{\mu}\tp{\*P^{(T)}} = \sup_{f\colon \bb R^d\to \bb R} \frac{\Var[\mu]{f}}{\E[X(T)\sim \xi_T]{\Var[\nu_T]{f}}}$.

The following theorem is a direct result in Sec 3.1.1 of [26]. For the completeness of this paper, we also provide the proof in 9.1.

Theorem 4 (Consequence of approximate conservation of variance for SL process). Suppose for any $s\in[0,T]$, there exists some fixed $\theta_s>0$ such that $\|\cov{\nu_s}\|_{\!{op}} \leq \theta_s$ holds almost surely. Then \[C^{\!{PI}}_{\mu}\tp{\*P^{(T)}} \leq e^{\int_0^T \theta_s \d s}.\]

Similar results also hold for the mLSI constant. The proof of the following proposition is provided in 9.1.

The distribution $\mu$ satisfies a modified log-Sobolev inequality with regard to the Markov chain $\*P^{(T)}$ with constant $C^{\!{mLSI}}_{\mu}\tp{\*P^{(T)}} \leq \sup_{f\colon \bb R^d\to \bb R_{>0}} \frac{\Ent[\mu]{f}}{\E[X(T)\sim \xi_T]{\Ent[\nu_T]{f}}}$.

The following result is a direct corollary of Proposition 3.19 and Lemma 3.20 in [26].

Theorem 5 (Consequence of approximate conservation of entropy for SL process). Suppose for any $s\in[0,T]$, there exists some fixed $\theta_s>0$ such that for any $v\in \bb R^d$, $\|\cov{\+T_v \nu_s}\|_{\!{op}} \leq \theta_s$ holds almost surely. Then \[\sup_{f\colon \bb R^d\to \bb R_{>0}} \frac{\Ent[\mu]{f}}{\E[X(T)\sim \xi_T]{\Ent[\nu_T]{f}}} \leq e^{\int_0^T \theta_s \d s}.\]

2.4 The Ornstein-Uhlenbeck process↩︎

The Ornstein-Uhlenbeck process (OU process) is a continuous-time stochastic process $\set{X^{\!{OU}}(t)}_{t\geq 0}$ with the following trajectory: \[\require{physics} \label{eq:OU} \dd X^{\!{OU}}(t) = - X^{\!{OU}}(t) \dd t + \sqrt{2} \dd B(t).\tag{6}\] For any $t\geq 0$, $X^{\!{OU}}(t)$ equals $e^{-t} X_{\!{OU}}(0) + \sqrt{1-e^{-2t}}\zeta$ in distribution, where $\zeta\sim \+N(0,\!{Id}_d)$ is independent with $X^{\!{OU}}(0)$. Assume the process start at $X^{\!{OU}}(0)\sim \mu$. Let $\xi^{\!{OU}}_t$ be the law of $X^{\!{OU}}(t)$ and $\nu^{\!{OU}}_t(\cdot |y)$ be the conditional distribution of $X^{\!{OU}}(0)$ given $X^{\!{OU}}(t)=y$. When the information of $y$ is clear, we will omit $y$ and use $\nu^{\!{OU}}_t$ for simplicity.

2.5 Restricted Gaussian oracle↩︎

For some fixed $y\in \bb R^d$, $\sigma^2\in \bb R$, let $\mu_{y,\sigma^2}$ be the distribution with density $\propto \exp\set{-V(x) - \frac{\norm{x-y}^2}{2\sigma^2}}$. The restricted Gaussian oracle (RGO) $\!{RGO}(y,\sigma^2)$ takes as input a point $y\in \bb R^d$, a variance parameter $\sigma^2\in \bb R$. It outputs sample from $\mu_{y,\sigma^2}$.

A widely used method to implement the RGO is simply rejection sampling. In this work, we directly apply the rejection sampling algorithm and use the following result in [23] as a black box. The details of the algorithm is provided in 8.

Theorem 6 (A corollary of Propositions 3.2, 3.4 and D.4 in [23]). Assume 1 holds and $\sigma^2 \leq \frac{1}{Ld}$. For any $y\in \bb R^d$, there exists an algorithm that generates a sample from $\mu_{y,\sigma^2}$ with $\wt{\+O}(1)$ queries to $V$ and $\grad V$ in expectation.

3 The covariance of SL processes↩︎

We already mentioned that the stochastic localization (SL) process is simply a rescaling of the reversed Ornstein-Uhlenbeck (OU) process. We will use the SL scaling in most our proofs. In this section, we clarify the relationship between the SL scaling and OU scaling, and particularly, we translate the smoothness assumption 3 to the covariance condition [cond:cov] in the context of the SL process.

Recall the definition of the SL process $\set{\nu_s}_{s\geq 0}$ where $\nu_s$ is the conditional distribution of $X$ given $X(s)=s\cdot X + B(s)$, and the definition of the OU process $\set{X^{\!{OU}}(t)}_{t\geq 0}$ where $\require{physics} \dd X^{\!{OU}}(t) = - X^{\!{OU}}(t) \dd t + \sqrt{2} \dd B(t)$.

The following lemma gives the connection between the two processes and its proof is given in 9.2.

Lemma 1. Define $s = \frac{e^{-2t}}{1-e^{-2t}}$. With $X\sim \mu$ and $X^{\!{OU}}(0)\sim \mu$,

the distributions of $X^{\!{OU}}(t)$ and $\sqrt{\frac{1}{s(1+s)}}\cdot X(s)$ are the same for any $t>0$;
the law of $X^{\!{OU}}(0)$ given $X^{\!{OU}}(t) = y$ is equal to the law of $X$ given $X(s) = \sqrt{s(1+s)}\cdot y$ for any $y\in \bb R^d$.

The main result of this section is the following lemma stating that 3 in the context of the OU process implies [cond:cov] in the context of the SL process.

Lemma 2. 3 implies [cond:cov]. More specifically, for an OU process $\tp{\xi^{\!{OU}}_t}_{t\ge 0}$ starting from $\xi^{\!{OU}}_0=\mu$, if $-\grad \log\xi^{\!{OU}}_t$ is $L^{\!{OU}}_t$-Lipschitz for any $t\in [0,\infty)$, then for an SL process $(\nu_s)_{s\ge 0}$ with $\nu_0=\mu$, it holds that for any $s\in \left[0, \infty \right)$, any $v,z\in \bb R^d$, \[\frac{1+s - L_s}{s(1+s)}\cdot \!{Id}_d\mle \cov{\+T_v \nu_s(\cdot\,|\,z)} \mle \frac{1+s + L_s }{s(1+s)}\cdot \!{Id}_d,\] where $L_s=L^{\!{OU}}_{t}$ with $t=\log\sqrt{\frac{s+1}{s}}$.

The proof of Lemma 2 is in 3.2. Before that, we establish a few useful identities for SL processes.

3.1 Some useful lemmas about score functions↩︎

In this section, we derive a few useful identities for the density function $p_{X_s}(x)$ of the stochastic localization process \[\forall s\ge 0,\; X(s) = s\cdot X+B(s), \; X\sim\mu.\] We remark that similar calculations have been carried out in several places such as in the study of diffusion models (, [14]) in the context of OU process, and as the properties of logarithmic Laplace transform (see , [25]).

Lemma 3. $\grad_y\log p_{X_s}(y) = \E[p_{X|X_s}(\cdot\,|\,y)]{X-y/s}.$

This identity is known as Tweedie’s formula (see, e.g. [32]). Its proof is given in 9.2. The first-order derivative of $\log p_{X_s}(y)$ gives the expectation of $p_{X|X_s}(\cdot | y)$. Alike, the second-order derivative reveals its covariance.

Lemma 4. $\grad^2_y \log p_{X_s}(y) = \cov{p_{X|X_s}(\cdot|y)} - \frac{\!{Id}_d}{s}.$

3.2 Proof of Lemma 2 ↩︎

By Lemma 4, we know that \[\cov{\nu_s(\cdot |z)} = \grad_z^2 \log p_{X_s}(z) + \frac{\!{Id}_d}{s}.\] From Lemma 1, we know that \[p_{X_s}(z) = \left(\frac{1}{\sqrt{s(1+s)}} \right)^d \cdot p_{X_{t}^{\!{OU}}}\tp{\frac{z}{\sqrt{s(1+s)}}}.\] Thus \[\grad_{z}^2 \log p_{X_s}(z) = \frac{1}{s(1+s)}\grad_{z}^2 \log p_{X_{t}^{\!{OU}}}\tp{\frac{z}{\sqrt{s(1+s)}}}.\] So \[-\frac{L_t^{\!{OU}}}{s(1+s)} \mle \grad_{z}^2 \log p_{X_s}(z) \mle \frac{L_t^{\!{OU}}}{s(1+s)}.\] Since $L_t^{\!{OU}} = L_s$, $\cov{\nu_s(\cdot |z)} = \grad_z^2 \log p_{X_s}(z) + \frac{\!{Id}_d}{s}$. Thus, for any $z\in \bb R^d$, \[\frac{1+s - L_s}{s(1+s)}\cdot \!{Id}_d\mle \cov{\nu_s(\cdot |z)} \mle \frac{1+s + L_s }{s(1+s)}\cdot \!{Id}_d.\] Note that \[\+T_v \nu_s(x\,|\,z) \propto \mu(x)\cdot \exp\set{-\frac{\|sx-z\|^2}{2s} + \inner{v}{x}} \propto\nu_s(x\,|\,z+v).\] This completes the proof of Lemma 2.

4 The restricted Gaussian dynamics with late initialization↩︎

In this section, we prove 1 by introducing and analyzing the underlying algorithm. We first analyze an ideal continuous-time restricted Gaussian dynamics in 4.1 and analyze its convergence. Our algorithm for proving 1 will be an approximate version of this ideal restricted Gaussian dynamics, described in 4.2 and analyzed in 4.3.

4.1 The convergence of the ideal restricted Gaussian dynamics↩︎

We first prove the convergence of the restricted Gaussian dynamics introduced in 2.3. For the ease of analysis, we will consider a continuous-time restricted Gaussian dynamics.

Recall that each iteration of the restricted Gaussian dynamics with transition kernel $\*P^{(T)}$ includes two steps:

(down-walk) draw $\hat{Y}_k\sim \+N\tp{T\cdot Y_{k-1}, T\cdot \!{Id}_d}$;
(up-walk) then draw $Y_k\sim \nu_T\tp{\cdot \,|\,\hat{Y}_k}$.

The first step, which is also called the down-walk step, is to sample from a Gaussian distribution and is straightforward to implement. For the second step, or the up-walk step, the target distribution $\nu_T\tp{\cdot\,|\,\hat{Y}_k}$ has the density function \[\nu_T\tp{x \,|\,\hat{Y}_k} \propto \mu(x) \cdot \exp\set{-\frac{\norm{Tx-\hat{Y}_k}^2}{2T}} \propto \exp\set{-V(x) - \frac{\norm{Tx-\hat{Y}_k}^2}{2T}}.\] That is, the up-walk step requires the implementation of an exact RGO, which is $\!{RGO}\tp{\frac{\hat{Y}_k}{T},\frac{1}{T}}$.

We consider a continuous-time restricted Gaussian dynamics with heat kernel $\*H_t$ in a duration of $t$. The continuous-time process is constructed by involving a Poisson process with rate $1$. The heat kernel $\*H_t(x,\cdot)$ stands for the distribution of the particle at time $t$ by running the process starting from $x$. To be specific, \[\require{physics} \forall t\geq 0, \forall x,y\in \bb R^d,\,\*H_t(x,\dd y) = \sum_{k=0}^{\infty} \Pr{K_t=k}\cdot \tp{\*P^{(T)}}^k(x, \dd y), \label{eq:transition}\tag{7}\] where $K_t\sim \!{Pois}(t)$.

If the discrete-time chain $\*P^{(T)}$ has a bounded constant $C^{\!{PI}}_{\mu}\tp{\*P^{(T)}}$, then the convergence of the corresponding continuous-time process with heat kernel $\*H_t$ is also guaranteed (see 6 for details).

The implementation of the continuous-time restricted Gaussian dynamics is given in 2. To bound the worst case iteration complexity, we set a hard upper bound $K$ for the total number of iterations. We run the continuous-time Markov process for $t=\frac{K}{2}$ time and once the number of iterations exceeds $K$, we force the algorithm to terminate and output.

Figure 2: The continuous-time restricted Gaussian dynamics

7 below summarizes the rate of convergence of 2 and is proved in 6.

Theorem 7 (Convergence of 2). Assume the constant of $\mu$ with regard to the Markov chain $\*P^{(T)}$ is $C^{\!{PI}}_{\mu}\tp{\*P^{(T)}}$. Denote the output distribution of 2 as $p_{Y_{\+K}}$. Then \[\!{TV}(p_{Y_{\+K}}\,\|\,\mu) \leq \tfrac12 \cdot e^{-K/{C^{\!{PI}}_{\mu}\tp{\*P^{(T)}}}} \cdot \sqrt{\chi^2(\mu_0\| \mu)} + 2e^{-{K}/{8}}\] for any $K\geq 6$. The iteration complexity of this algorithm is at most $K$.

4.2 The practical algorithm with late initialization↩︎

Recall that $\xi_s$ is the distribution of $X(s)$ in 4 and $\nu_s$ is the law of $X$ given $X(s)$. According to 4, if $\cov{\nu_s}$ is suitably bounded almost surely for all $s\in [0, T]$, then the constant of the restricted Gaussian dynamics with transition kernel $\*P^{(T)}$ can be controlled. However, under [cond:cov] alone, we can only obtain the bound $\norm{\cov{\nu_s}}_{\!{op}}\leq \frac{1}{s} + \frac{L_s}{s(1+s)}$ and therefore the integration $\require{physics} \int_0^T \tp{\frac{1}{s} + \frac{L_s}{s(1+s)}} \dd s$ diverges, preventing us from directly concluding the convergence of the restricted Gaussian dynamics solely via conservation of variance. Observe that this divergence arises from the fact that $\frac{1}{s}$ becomes unbounded and is not locally integrable near zero.

To address this, we need a late initialization scheme to skip the segment $[0,s_0)$ for some small $s_0$, whose value is to be determined later. The algorithm is given in 3. Let us explain its main differences compared to 2.

Figure 3: The restricted Gaussian dynamics with late initialization

4.2.0.1 The late initialization

The first difference is the late initialization mentioned above. In 3, we first draw $X_{s_0}\sim \xi_{s_0}$, and then use restricted Gaussian dynamics to generate a sample from the conditional distribution $\nu_{s_0}\tp{\cdot \,|\,X_{s_0}}$. Since we do not have direct access to $\xi_{s_0}$, we use $\+N\tp{0, s_0(1+s_0)\cdot\!{Id}_d}$ to approximate $\xi_{s_0}$ instead as an approximation. In other words, we will consider the restricted Gaussian dynamics induced by the stochastic process \[Z(s) = s\cdot Z + B(s),\;Z\sim \nu_{s_0}\tp{\cdot \,|\,X_{s_0}}. \label{eq:modifiedSL}\tag{8}\] For a fixed $X_{s_0}$, we let $\xi'_s$ and $\nu'_t(\cdot |y)$ denote the distribution of $Z(s)$ and the distribution of $Z$ given $Z(s)=y$. Denote $\*Q^{(T)}$ as the transition kernel of this restricted Gaussian dynamics. The constant of this Markov chain is proved in the next lemma.

Lemma 5. Assume [cond:cov] holds. Given $X_{s_0}\in \bb R^d$, the restricted Gaussian dynamics induced by 8 satisfies $C^{\!{PI}}_{\nu_{s_0}}\tp{\*Q^{(T)}} \leq \frac{s_0+T}{s_0}\cdot \exp\set{ \int_{s_0}^{T+s_0} \frac{L_{s}}{s(1+s)} \d s}$.

Proof. According to Lemma 6, under [cond:cov], we have \[\norm{\cov{\nu'_s}}_{\!{op}} \leq \frac{1+s_0+s +L_{s+s_0}}{\tp{1+s_0+s}(s_0+s)} \label{eq:condition}\tag{9}\] almost surely. Then from 4 and 9 , \[\require{physics} \begin{align} C^{\!{PI}}_{\nu_{s_0}}\tp{\*Q^{(T)}} &\leq \exp\set{ \int_0^T \frac{1+s_0+s + L_{s+s_0}}{\tp{1+s_0+s}(s_0+s)} \d s} \\ &= \exp\set{ \int_0^T \tp{ \frac{1}{s_0+s} + \frac{L_{s+s_0}}{(s_0+s)(1+s_0+s)}} \d s} \\ &\leq \exp\set{\eval{\log(s_0+s)}_0^T + \int_0^T \frac{L_{s+s_0}}{(s_0+s)(1+s_0+s)} \d s} \\ &\leq \frac{s_0+T}{s_0}\cdot \exp\set{ \int_{s_0}^{T+s_0} \frac{L_{s}}{s(1+s)} \d s}. \end{align}\] ◻

4.2.0.2 Different implementation of the RGO

The second difference is the implementation of the RGO. Since the target distribution of the restricted Gaussian dynamics is $\nu_{s_0}\tp{\cdot\mid X_{s_0}}$ rather than $\mu$, we need to sample from a distribution with density \[p_{Z|Z(T)}(x\,|\,\hat{Y}_k) \propto \nu_{s_0}\tp{x\,|\,X_{s_0}}\cdot \exp\set{-\frac{\norm{\hat{Y}_k - T x}^2}{2T}} \label{eq:conditional}\tag{10}\] in the up-walk step. The next result indicates that this can be achieved via $\!{RGO}\tp{\frac{\hat{Y}_k + X_{s_0}}{T+s_0},\frac{1}{T+s_0}}$.

Lemma 6. For any $x,x_{s_0},x_T\in \bb R^d$, $\nu_{T+s_0}(x\,|\,x_T + x_{s_0}) = \nu'_T(x\,|\,x_T)$.

Proof. By the definition of conditional probability, \[\begin{align} \nu_{T+s_0}(x\,|\,x_T + x_{s_0}) &= \frac{p_{X,X(T+s_0)}(x, x_T + x_{s_0})}{\xi_{T+s_0}(x_T + x_{s_0})}\\ &\propto \mu(x)\cdot p_{X(T+s_0)|X}(x_T + x_{s_0}|x)\\ &\propto \mu(x)\cdot \exp\set{- \frac{\norm{x_T + x_{s_0} - (T+s_0)x}^2}{2(T+s_0)}} \\ &\propto \mu(x)\cdot \exp\set{ - \frac{(T+s_0)\|x\|^2}{2} + \inner{x_T + x_{s_0}}{x}}. \end{align}\] Similarly, \[\begin{align} \nu'_T\tp{x\mid x_T} &= \frac{p_{Z,Z(T)}\tp{x, x_T}}{\xi'_T(x_T)} \\ &\propto p_{Z}(x)\cdot p_{Z(T)|Z}\tp{ x_T \mid x} \\ \mr{definition of Z}&= \nu_{s_0}(x\,|\,x_{s_0}) \cdot p_{Z(T)|Z}\tp{ x_T \mid x} \\ &\propto \mu(x)\cdot p_{ X(s_0) |X}(x_{s_0}\,|\,x) \cdot p_{Z(T)|Z}\tp{ x_T \mid x}\\ &\propto \mu(x)\cdot \exp\set{-\frac{\norm{x_{s_0}-s_0\cdot x}^2}{2s_0}} \cdot \exp\set{-\frac{\norm{x_T - T\cdot x}^2}{2T}} \\ &\propto \mu(x)\cdot \exp\set{ - \frac{(T+s_0)\|x\|^2}{2} + \inner{x_T+x_{s_0}}{x}}. \end{align}\] Therefore, the two conditional distributions are the same. ◻

For any $y\in \bb R^d$, define the function $U_y(x) = V(x) + \frac{\norm{y - s_0\cdot x}^2}{2s_0}$. For the restricted Gaussian dynamics to converge, from 7, it is enough to set $K$ as \[\max\set{C^{\!{PI}}_{\mu}\tp{\*Q^{(T)}} \cdot \log \frac{2\sqrt{\chi^2\tp{\mu_0\|\nu_{s_0}(\cdot |X_{s_0})}}}{\eps}, 8\log \frac{8}{\eps}}\] From Lemmas 5 and 17, the following $K_{X_{s_0}}$ is an upper bound of the above equation. \[\require{physics} \begin{align} K_{X_{s_0}} &= \max\set{ 8\log \frac{8}{\eps}, \frac{s_0+T}{2s_0}\cdot \exp\set{ \int_{s_0}^{T+s_0} \frac{L_{t}}{t(1+t)} \dd t}\cdot \left(\log(2e) + V(0) - \min V \right.\right. \notag \\ &\left. \left. \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad + \frac{d}{2}\log \tp{(L+s_0)\cdot 16e^2M} + \frac{(2d+1)\norm{X_{s_0}}^2}{2s_0} + \log \frac{4}{\eps^2}\right)} \label{eq:complexity} \end{align}\tag{11}\]

4.3 The convergence of 3 ↩︎

In this section, we give the accuracy analysis and derive an expected query complexity bound of 3. The following result is a corollary of 11 and 7.

Corollary 1. Assume [cond:cov] holds. In 3, for any $y\in \bb R^d$, \[\!{TV}(p_{Y_{\+K}\,|\,X_{s_0}}(\cdot\,|\,y),\nu_{s_0}(\cdot\,|\,y)) \leq \frac{\eps}{2}.\]

The next lemma indicates that it is reasonable to use $\+N\tp{0, s_0(1+s_0)\cdot \!{Id}_d}$ to approximate $\xi_{s_0}$. Its proof is given in 9.3.

Lemma 7. Let $s_0 = \frac{\tp{\frac{\eps^2}{2(Ld+M)}}^4}{ 1- \tp{\frac{\eps^2}{2(Ld+M)}}^4}$ for some $\eps\in (0,1)$. Then $\!{TV}\tp{\xi_{s_0}, \+N\tp{0, s_0(1+s_0)\!{Id}_d}}\leq \frac{\eps}{2}$.

Now we are ready to prove 1.

Theorem 8. With $s_0 = \frac{\tp{\frac{\eps^2}{2(Ld+M)}}^4}{ 1- \tp{\frac{\eps^2}{2(Ld+M)}}^4}$ and $T=2Ld$, the output of 3 satisfies $\!{TV}\tp{p_{Y_{\+K}}, \mu}\leq \eps$. The expected query complexity is bounded by \[\wt{\+O}\tp{Ld\cdot (V(0)-\min V + d^2)}\cdot\frac{1}{s_0}\cdot \exp\set{ \int_{s_0}^{T+s_0} \frac{L_{s}}{s(1+s)} \d s}.\] In particular, letting $\ol L=\sup_{t\geq s_0} L_t$, the query complexity is at most \[\wt{\+O}\tp{Ld\cdot (V(0)-\min V + d^2)}\cdot \tp{\frac{Ld+M}{\eps^2}}^{\+O(\ol L+1)}.\]

Proof. Note that \[p_{Y_{\+K}}(x) = \int_{\bb R^d} p_{X_{s_0}}(z) \cdot p_{Y_{\+K}|X_{s_0}}(x\,|\,z) \d z\] and \[\mu(x) = \int_{\bb R^d} \xi_{s_0}(z)\cdot \nu_{s_0}(x\,|\,z) \d z.\] Therefore, \[\begin{align} \!{TV}\tp{p_{Y_{\+K}}, \mu} &= \tfrac{1}{2}\int_{\bb R^d} \abs{p_{Y_{\+K}}(x) - \mu(x)} \d x \\ &= \tfrac{1}{2}\int_{\bb R^d} \abs{\int_{\bb R^d} p_{X_{s_0}}(z) \cdot p_{Y_{\+K}|X_{s_0}}(x\,|\,z) \d z - \int_{\bb R^d} \xi_{s_0}(z)\cdot \nu_{s_0}(x\,|\,z) \d z} \d x \\ \mr{triangle inequality} &\leq \tfrac{1}{2}\int_{\bb R^d} \abs{\int_{\bb R^d} p_{X_{s_0}}(z) \cdot p_{Y_{\+K}|X_{s_0}}(x\,|\,z) \d z - \int_{\bb R^d} \xi_{s_0}(z)\cdot p_{Y_{\+K}|X_{s_0}}(x\,|\,z) \d z} \d x \\ &\quad + \tfrac{1}{2}\int_{\bb R^d} \abs{\int_{\bb R^d} \xi_{s_0}(z) \cdot p_{Y_{\+K}|X_{s_0}}(x\,|\,z) \d z - \int_{\bb R^d} \xi_{s_0}(z)\cdot \nu_{s_0}(x\,|\,z) \d z} \d x. \end{align}\] By Jensen’s inequality, we can bound the above by \[\begin{align} &\tfrac{1}{2}\int_{\bb R^{d}\times \bb R^{d}} \abs{ p_{X_{s_0}}(z) - \xi_{s_0}(z) }\cdot p_{Y_{\+K}|X_{s_0}}(x\,|\,z)\d z \d x + \tfrac{1}{2}\int_{\bb R^{d}\times \bb R^{d}} \abs{ p_{Y_{\+K}|X_{s_0}}(x\,|\,z) - \nu_{s_0}(x\,|\,z) }\cdot \xi_{s_0}(z)\d z \d x \\ &\quad= \!{TV}\tp{\xi_{s_0}, \+N\tp{0, s_0(1+s_0)\cdot\!{Id}_d}} + \int_{\bb R^{d}} \!{TV}(p_{Y_{\+K}|X_{s_0}}(\cdot\,|\,z),\nu_{s_0}(\cdot\,|\,z))\cdot \xi_{s_0}(z)\d z, \end{align}\] which is at most $\eps$ by Corollary 1 and Lemma 7.

With $T=2Ld$, according to 6, the implementation of $\!{RGO}\tp{\frac{\hat{Y}_k + X_{s_0}}{T+s_0},\frac{1}{T+s_0}}$ needs $\wt{\+O}(1)$ queries in expectation. From 11 , the expected query complexity can be bounded by \[\begin{align} &\phantom{{}={}}\E[X_{s_0}\sim \+N\tp{0, s_0(1+s_0)\cdot\!{Id}_d}]{K_{X_{s_0}}}\\ &= \wt{\+O}\tp{ \frac{s_0+T}{s_0}\cdot \exp\set{ \int_{s_0}^{T+s_0} \frac{L_{s}}{s(1+s)} \d s} \cdot \tp{V(0)-\min V + d\log(LM) + d^2 + \log\frac{4}{\eps^2}} } \\ &= \wt{\+O}\tp{Ld\cdot (V(0)-\min V + d^2)}\cdot \frac{1}{s_0}\cdot \exp\set{ \int_{s_0}^{T+s_0} \frac{L_{s}}{s(1+s)} \d s}. \end{align}\] This can be further bounded by \[\wt{\+O}\tp{Ld\cdot (V(0)-\min V + d^2)}\cdot \frac{1}{s_0}\cdot \tp{\frac{(T+s_0)(1+s_0)}{s_0(1+T+s_0)}}^{\ol L},\] and can be simplified to \[\wt{\+O}\tp{Ld\cdot (V(0)-\min V + d^2)}\cdot \tp{\frac{Ld+M}{\eps^2}}^{\+O(\ol L+1)}.\] ◻

5 The bound on the constant and modified log-Sobolev constant↩︎

In this section, we introduce the concatenation of the constant and modified log-Sobolev constant under [cond:cov] in [sec:concate-PI,sec:concate-mLSI], and apply these methods to prove the two parts of 2 in [sec:sub-G-PI,sec:sub-G-mLSI] respectively. Finally, in 5.5, we derive the modified log-Sobolev constant bound of the mixture of strongly log-concave distributions.

We first introduce a technical lemma. The next lemma is indeed a tower rule for conditional expectations with appropriate random variables along the SL trajectory. We leave the formal verification of Lemma 8 in 9.4.

Lemma 8. For any $0\leq s<T$, we have

$\E[\xi_T]{\Var[\nu_T]{f}} = \E[\xi_{s}]{\E[\xi'_{T-s}]{\Var[\nu'_{T-s}]{f}}}$;
$\E[\xi_T]{\Ent[\nu_T]{f}} = \E[\xi_{s}]{\E[\xi'_{T-s}]{\Ent[\nu'_{T-s}]{f}}}$.

5.1 The concatenation of the constant↩︎

Recall that $\*P^{(s_0)}$ is the transition kernel of the restricted Gaussian dynamics with target distribution $\mu$ at time $s_0$.

Theorem 9. Assume 1 and [cond:cov] hold and assume $C^{\!{PI}}_{\mu}\tp{\*P^{(s_0)}}<\infty$ for some $0\leq s_0\leq T=2L$. Then $\mu$ satisfies the inequality with constant \[\require{physics} C^{\!{PI}}_{\mu}\leq C^{\!{PI}}_{\mu}\tp{\*P^{(s_0)}}\cdot \frac{2}{s_0}\cdot \exp\set{ \int_{s_0}^{2L} \frac{L_{s}}{s(1+s)} \dd s}.\]

Proof. For any $T>s_0$, by the definition of the inequality, we know \[\begin{align} C^{\!{PI}}_{\mu} &= \sup_{f:\bb R^d \to \bb R} \frac{\Var[\mu]{f}}{\E[\mu]{\|\grad f\|^2}} \\ &= \sup_{f:\bb R^d \to \bb R} \frac{\E[\xi_T]{\Var[\nu_T]{f}}}{\E[\mu]{\|\grad f\|^2}}\cdot \frac{\E[\xi_{s_0}]{\Var[\nu_{s_0}]{f}}}{\E[\xi_T]{\Var[\nu_T]{f}}} \cdot \frac{\Var[\mu]{f}}{\E[\xi_{s_0}]{\Var[\nu_{s_0}]{f}}} \\ &\leq \underbrace{\tp{\sup_{f:\bb R^d \to \bb R} \frac{\E[\xi_T]{\Var[\nu_T]{f}}}{\E[\mu]{\|\grad f\|^2}}}}_{\!{(A)}}\cdot \underbrace{\tp{\sup_{f:\bb R^d \to \bb R} \frac{\E[\xi_{s_0}]{\Var[\nu_{s_0}]{f}}}{\E[\xi_T]{\Var[\nu_T]{f}}}}}_{\!{(B)}}\cdot \underbrace{\tp{\sup_{f:\bb R^d \to \bb R} \frac{\Var[\mu]{f}}{\E[\xi_{s_0}]{\Var[\nu_{s_0}]{f}}}}}_{\!{(C)}}. \end{align}\] Now we bound each term separately. For the term $\!{(C)}$, it is exactly $C^{\!{PI}}_{\mu}\tp{\*P^{(s_0)}}$ by Proposition [prop:PIofSL].

Note that when 1 holds, by choosing $T=2L$, $\nu_T$ is $L$-strongly log-concave. By a well-known consequence of the Bakry-Émery criterion (see , [30]), it satisfies inequality with constant $\frac{1}{L}$ almost surely. Therefore, \[\!{(A)}= \sup_{f:\bb R^d \to \bb R} \frac{\E[\xi_T]{\Var[\nu_T]{f}}}{\E[\xi_T]{\E[\nu_T]{\|\grad f\|^2}}} \leq \frac{1}{L}.\] From Lemma 5 and Lemma 8, \[\require{physics} \begin{align} \!{(B)}= \sup_{f:\bb R^d \to \bb R} \frac{\E[\xi_{s_0}]{\Var[\nu_{s_0}]{f}}}{\E[\xi_{s_0}]{\E[\xi'_{T-s_0}]{\Var[\nu'_{T-s_0}]{f}}}} \leq \frac{T}{s_0}\cdot \exp\set{ \int_{s_0}^{T} \frac{L_{s}}{s(1+s)} \dd s}. \end{align}\] Combining all above, we have \[C^{\!{PI}}_{\mu} \leq C^{\!{PI}}_{\mu}\tp{\*P^{(s_0)}}\cdot \frac{2}{s_0}\cdot \exp\set{ \int_{s_0}^{2L} \frac{L_{s}}{s(1+s)} \d s }.\] ◻

5.2 The concatenation of the modified log-Sobolev constant↩︎

Analogous to 5.1, this section analyzes the concatenation of the modified log-Sobolev constant.

Theorem 10. Assume 1 and [cond:cov] hold and assume $\sup_{f:\bb R^d \to \bb R_{>0}} \frac{\Ent[\mu]{f}}{\E[\xi_{s_0}]{\Ent[\nu_{s_0}]{f}}}<\infty$ for some $0\leq s_0\leq T=2L$. Then $\mu$ satisfies the modified log-Sobolev inequality with constant \[\require{physics} C^{\!{mLSI}}_{\mu}\leq \sup_{f:\bb R^d \to \bb R_{>0}} \frac{\Ent[\mu]{f}}{\E[\xi_{s_0}]{\Ent[\nu_{s_0}]{f}}}\cdot \frac{1}{s_0}\cdot \exp\set{ \int_{s_0}^{2L} \frac{L_{s}}{s(1+s)} \dd s}.\]

Proof. For any $T>s_0$, by the definition of the modified log-Sobolev constant, we know \[\begin{align} C^{\!{mLSI}}_{\mu} &= \sup_{f:\bb R^d \to \bb R_{>0}} \frac{\Ent[\mu]{f}}{\E[\mu]{f^{-1}\|\grad f\|^2}} \\ &= \sup_{f:\bb R^d \to \bb R_{>0}} \frac{\E[\xi_T]{\Ent[\nu_T]{f}}}{\E[\mu]{f^{-1}\|\grad f\|^2}}\cdot \frac{\E[\xi_{s_0}]{\Ent[\nu_{s_0}]{f}}}{\E[\xi_T]{\Ent[\nu_T]{f}}} \cdot \frac{\Ent[\mu]{f}}{\E[\xi_{s_0}]{\Ent[\nu_{s_0}]{f}}} \\ &\leq \underbrace{\tp{\sup_{f:\bb R^d \to \bb R_{>0}} \frac{\E[\xi_T]{\Ent[\nu_T]{f}}}{\E[\mu]{f^{-1}\|\grad f\|^2}}}}_{\!{(A)}}\cdot \underbrace{\tp{\sup_{f:\bb R^d \to \bb R_{>0}} \frac{\E[\xi_{s_0}]{\Ent[\nu_{s_0}]{f}}}{\E[\xi_T]{\Ent[\nu_T]{f}}}}}_{\!{(B)}}\cdot \underbrace{\tp{\sup_{f:\bb R^d \to \bb R_{>0}} \frac{\Ent[\mu]{f}}{\E[\xi_{s_0}]{\Ent[\nu_{s_0}]{f}}}}}_{\!{(C)}}. \end{align}\]

Note that when 1 holds, by choosing $T=2L$, $\nu_T$ is $L$-strongly log-concave. By a well-known consequence of the Bakry-Émery criterion (see , [30]), it satisfies modified log-Sobolev inequality with constant $\frac{1}{2L}$ almost surely. Therefore, for the term $\!{(A)}$, we have \[\!{(A)} = \sup_{f:\bb R^d \to \bb R_{>0}} \frac{\E[\xi_T]{\Ent[\nu_T]{f}}}{\E[\xi_T]{\E[\nu_T]{f^{-1}\|\grad f\|^2}}} \leq \frac{1}{2L}.\]

From Lemma 8, \[\!{(B)} = \sup_{f:\bb R^d \to \bb R_{>0}} \frac{\E[\xi_{s_0}]{\Ent[\nu_{s_0}]{f}}}{\E[\xi_{s_0}]{\E[\xi'_{T-s_0}]{\Ent[\nu'_{T-s_0}]{f}}}}.\] Consider the Markov chain induced by 8 . According to Lemma 6, under [cond:cov], for any $v\in \bb R^d$, \[\norm{\cov{\+T_v \nu'_s}}_{\!{op}} \leq \frac{1+s_0+s +L_{s+s_0}}{\tp{1+s_0+s}(s_0+s)}\] From 5, we have \[\require{physics} \begin{align} \sup_{f:\bb R^d \to \bb R_{>0}} \frac{\Ent[\nu_{s_0}]{f}}{\E[\xi'_{T-s_0}]{\Ent[\nu'_{T-s_0}]{f}}} &\leq \exp\set{\int_0^{T-s_0} \frac{1+s_0+s +L_{s+s_0}}{\tp{1+s_0+s}(s_0+s)} \dd s}\\ &= \exp\set{ \int_0^{T-s_0} \tp{ \frac{1}{s_0+s} + \frac{L_{s+s_0}}{(s_0+s)(1+s_0+s)}} \d s} \\ &\leq \frac{T}{s_0}\cdot \exp\set{ \int_{s_0}^{T} \frac{L_{s}}{s(1+s)} \d s}, \end{align}\] and consequently, \[\!{(B)} \leq \frac{2L}{s_0}\cdot \exp\set{ \int_{s_0}^{2L} \frac{L_{s}}{s(1+s)} \d s}.\] Combining all these together, the proof is finished. ◻

Note that in [thm:concatenation,thm:concate-mLSI], we establish integral-form upper bounds for the and mLSI constants of $\mu$ under [cond:cov] (derived from 3). Analogous bounds can be derived using Lipschitz transport maps. Specifically, Lemma 3 of [29] implies similar integral bounds via the Kim-Milman flow map ([33]) under 3. However, a limitation of their result is that the upper limit of integration is $\infty$. This corresponds to setting $s_0=0$ in our framework. Crucially, under only 3, this integral diverges, rendering the bound vacuous.

A key advantage in our work is the explicit truncation at a small $s_0 > 0$. On the one hand, this allows us to bound the PI and mLSI constants under specific settings, such as the stronger moment conditions discussed in subsequent sections. We believe similar truncation can be applied in the transport map approach to establishing functional inequalities. However, on the other hand, our approach directly implies efficient sampling via the late initialization technique in 4, even when the integral diverges and standard functional inequalities fail.

5.3 Bounding the constant under stronger moment conditions↩︎

Then we show that $C^{\!{PI}}_{\mu}\tp{\*P^{(s)}}$ can be bounded under the stronger moment bound 4.

Lemma 9. Under 4, we have $C^{\!{PI}}_{\mu}\tp{\*P^{(s)}}\leq \frac{1}{2-e^{4s\lambda^2}}$ for any $0\leq s\leq \frac{\log 2}{4\lambda^2}$.

Proof. By the law of total variance, for any $f: \bb R^d\to \bb R$, \[\Var[\mu]{f} = \E[ \xi_{s }]{\Var[\nu_{s}]{f}} + \Var[\xi_{s }]{\E[\nu_{s }]{f}}.\] Therefore, \[\frac{\Var[\mu]{f}}{\E[\xi_s]{\Var[\nu_s]{f}}} = \frac{1}{1 - \frac{\Var[\xi_{s}]{\E[\nu_{s}]{f}}}{\Var[\mu]{f}}}, \label{eq:initialPI-1}\tag{12}\] and it is sufficient to prove an upper bound for $\frac{\Var[\xi_{s}]{\E[\nu_{s}]{f}}}{\Var[\mu]{f}}$. We assume without loss of generality that $\E[\mu]{f}=0$. Note that \[\begin{align} \Var[\xi_s]{\E[\nu_s]{f}} &= \int \tp{\int f(x) \nu_s(x|y) \d x}^2 \xi_s(y)\d y\\ &=\int \tp{\int f(x)\cdot \mu(x)\cdot \frac{p_{X(s)|X}(y|x)}{ \xi_s(y)}\d x}^2 \xi_s(y) \d y\\ \mr{\E[\mu]{f}=0}&=\int \tp{\int f(x)\cdot \mu(x)\cdot \frac{p_{X(s)|X}(y|x)}{ \xi_s(y)}\d x - \int f(x)\cdot \mu(x) \d x}^2 \xi_s(y) \d y\\ &=\int \tp{\int f(x)\cdot \mu(x)\cdot \tp{\frac{p_{X(s)|X}(y|x)}{ \xi_s(y)}-1}\d x }^2 \xi_s(y) \d y\\ \mr{Cauchy-Schwarz inequality} &\le \int \tp{\int f(x)^2 \mu(x) \d x}\tp{\int \tp{\frac{p_{X(s)|X}(y|x)}{ \xi_s(y)} - 1}^2 \mu(x) \d x} \xi_s(y) \d y \\ &=\Var[\mu]{f} \cdot \int \tp{\int \tp{\frac{p_{X(s)|X}(y|x)}{ \xi_s(y)} - 1}^2 \mu(x) \d x} \xi_s(y) \d y. \end{align}\]

Therefore, $\frac{\Var[\xi_s]{\E[\nu_s]{f}}}{\Var[\mu]{f}}$ can be upper bounded by \[\begin{align} \int \tp{\int \tp{\frac{p_{X(s)|X}(y|x)}{\xi_s(y)} - 1}^2 \mu(x) \d x} \xi_s(y) \d y &= \int \tp{\int \tp{\frac{p_{X(s)|X}(y|x)}{\xi_s(y)} - 1}^2 \xi_s(y) \d y} \mu(x) \d x. \label{eq:6} \end{align}\tag{13}\] We remark that the above quantity can be written as $\chi^2\tp{p_{X,X(s)}\,\|\,p_X\otimes p_{X(s)}}$, which is known as the $\chi^2$-mutual information between $X$ and $X(s)$. Note that \[\require{physics} \xi_s(y) = \int_{z\in \bb R^d} \mu(z)\cdot \+N\tp{y; sz, s\cdot I_d} \dd z = \E[Z\sim \mu]{ \+N\tp{y; sZ, s\cdot I_d}}.\] Then for any fixed $x\in \bb R^d$, \[\require{physics} \begin{align} \int \tp{\frac{p_{X(s)|X}(y|x)}{\xi_s(y)} - 1}^2 \xi_s(y) \d y &= \int \frac{\+N\tp{y;sx, s\cdot I_d}^2}{\xi_s(y)} \dd y -1\\ &= \int \frac{\+N\tp{y;sx, s\cdot I_d}^2}{\E[Z\sim \mu]{ \+N\tp{y; sZ, s\cdot I_d}}} \dd y -1\\ \mr{Jensen inequality} &\leq \mathlarger{\int} \+N\tp{y;sx, s\cdot I_d}^2\cdot \E[Z\sim \mu]{\frac{1}{ \+N\tp{y; sZ, s\cdot I_d}}} \dd y -1 \\ &= \E[Z\sim \mu]{\int \frac{\+N\tp{y;sx, s\cdot I_d}^2}{ \+N\tp{y; sZ, s\cdot I_d}} \dd y - 1}\\ &= \E[Z\sim \mu]{ \chi^2\tp{\+N\tp{sx, s\cdot I_d}\,\|\,\+N\tp{sZ, s\cdot I_d} }}. \end{align}\] From Lemma 23, $\chi^2\tp{\+N\tp{sx, s\cdot I_d}\,\|\,\+N\tp{sz, s\cdot I_d} } = e^{s\norm{x-z}^2}-1$. Bringing these into 13 , we have \[\begin{align} \frac{\Var[Y_s\sim\xi_s]{\E[\nu_s]{f}}}{\Var[\mu]{f}} &\leq \E[X,Z\sim \mu]{e^{s\|X-Z\|^2}} -1\\ &\leq \E[X,Z\sim \mu]{e^{2s\|X\|^2 + 2s\|Z\|^2}} -1 \\ &= \E[X\sim \mu]{e^{2s\|X\|^2}}^2 -1\\ \mr{\Cref{assump:momentplus}}&\leq e^{4s\lambda^2} -1. \end{align}\] When $0\leq s<\frac{\log 2}{4\lambda^2}$, the above value is smaller than $1$ and the final result can be derived via plugging this bound into 12 . ◻

Then the inequality is a direct corollary of 9 and Lemma 9.

Theorem 11. If a distribution satisfies 1, 3 and 4, then \[C^{\!{PI}}_{\mu}\leq \min_{s_0\in \left(0,\frac{\log 2}{4\lambda^2}\right]} \frac{1}{2-e^{4s_0\lambda^2}}\cdot \frac{2}{s_0}\cdot \exp\set{ \int_{s_0}^{2L} \frac{L_{s}}{s(1+s)} \d s},\] where $L_s = L_t^{\!{OU}}$ with $t = \log\sqrt{\frac{s+1}{s}}$.

5.4 Bounding the modified log-Sobolev constant under stronger moment conditions↩︎

We first prove a defective modified log-Sobolev inequality in 5.4.1. Then we sketch how to boost it to a standard modified log-Sobolev inequality in 5.4.2. Our approach is inspired by the proof of Theorem 1 in [34].

5.4.1 A Defective modified log-Sobolev inequality↩︎

In order to prove a defective modified log-Sobolev inequality for $\*P^{(s_0)}$, we will use the following lemmas.

Lemma 10 (Lemma 1 in [34]). Let $\pi$ and $\rho$ be probability distributions. For any positive function $f$, \[\E[\pi]f \log \frac{\E[\pi]f}{\E[\rho]f}\le \Ent[\pi]f+\E[\pi]f \log(1+\chi^2(\pi\|\rho)).\]

Lemma 11 (Variational formula for entropy, a corollary of Lemma 3.15 in [28]). For any random variable $Z$ satisfying $\E{\exp(Z)}\le 1$, $\E{YZ}\le \Ent{Y}$.

Then we are ready to prove a defective modified log-Sobolev inequality for $\*P^{(s_0)}$.

Under 4, for any $0\le s\le \frac{1}{12\lambda^2}$ and $f:\bb R^d \to \bb R_{>0}$, \[\Ent[\mu]f\le 3\cdot\E[\xi_s]{\Ent[\nu_s]f}+24s\lambda^2\cdot \E[\mu]f.\]

Proof. By Lemma 10, \[\begin{align} \Ent[\xi_s]{\E[\nu_s]f}=\E[\xi_s]{\E[\nu_s]f \log\frac{\E[\nu_s]f}{\E[\mu]f}}\le \E[\xi_s]{\Ent[\nu_s]f+\E[\nu_s]f\log(1+\chi^2(\nu_s\|\mu))}.\label{eq:mls1} \end{align}\tag{14}\] Now we upper bound $\E[\xi_s]{(1+\chi^2(\nu_s\|\mu))^2}$ . \[\begin{align} \E[\xi_s]{(1+\chi^2(\nu_s\|\mu))^2} &= \int \tp{\int\tp{\frac{\nu_s(x|y)}{\mu(x)}}^2\mu(x)\d x}^2\xi_s(y)\d y\\ \mr{Jensen inequality} &\le \int \tp{\int \tp{\frac{\nu_s(x|y)}{\mu(x)}}^4\mu(x)\d x}\xi_s(y)\d y\\ &= \int \tp{\int \tp{\frac{p_{X(s)|X}(y|x)}{\xi_s(y)}}^4\mu(x)\d x}\xi_s(y)\d y\\ &= \int \tp{\int \tp{\frac{p_{X(s)|X}(y|x)}{\xi_s(y)}}^4\xi_s(y)\d y}\mu(x)\d x. \end{align}\] Note that $p_{X(s)|X}(y|x)=\+N(y;sx,s\cdot \!{Id}_d)$ and $\xi_s(y)=\E[Z\sim\mu]{\+N(y;sZ,s\cdot\!{Id}_d)}$. Then for any fixed $x\in \bb R^d$, \[\begin{align} \int \tp{\frac{p_{X(s)|X}(y|x)}{\xi_s(y)}}^4\xi_s(y)\d y &= \int \frac{\+N(y;sx,s\cdot\!{Id}_d)^4}{\xi_s(y)^3}\d y\\ &= \int \frac{\+N(y;sx,s\cdot\!{Id}_d)^4}{\E[Z\sim\mu]{\+N(y;sZ,s\cdot\!{Id}_d)}^3}\d y\\ \mr{Jensen inequality} &\le \int \+N(y;sx,s\cdot\!{Id}_d)^4\cdot{\E[Z\sim\mu]{\+N(y;sZ,s\cdot\!{Id}_d)^{-3}}}\d y\\ &= \E[Z\sim\mu]{\int \frac{\+N(y;sx,s\cdot\!{Id}_d)^4}{\+N(y;sZ,s\cdot\!{Id}_d)^3}\d y}. \end{align}\] We have \[\begin{align} \E[\xi_s]{(1+\chi^2(\nu_s\|\mu))^2}&\le \int \E[Z\sim\mu]{\int \frac{\+N(y;sx,s\cdot\!{Id}_d)^4}{\+N(y;sZ,s\cdot\!{Id}_d)^3}\d y}\mu(x)\d x\\ &= \E[X,Z\sim\mu]{\int \frac{\+N(y;sX,s\cdot\!{Id}_d)^4}{\+N(y;sZ,s\cdot\!{Id}_d)^3}\d y}\\ \mr{Lemma~\ref{lem:chi4ofGaussian}} &= \E[X,Z\sim\mu]{e^{6s\|X-Z\|^2}}\\ &\le \E[X,Z\sim\mu]{e^{12s\|X\|^2+12s\|Z\|^2}}\\ &= \E[X\sim\mu]{e^{12s\|X\|^2}}^2\\ \mr{\Cref{assump:momentplus}} &\le e^{24s\lambda^2}. \end{align}\] Therefore $\E[\xi_s]{\exp(2\log(1+\chi^2(\nu_s\|\mu))-24s\lambda^2)}\le 1$, by Lemma 11, \[\E[\xi_s]{\tfrac 12\cdot\E[\nu_s]f \cdot (2\log(1+\chi^2(\nu_s\|\mu))-24s\lambda^2)}\le \Ent[\xi_s]{\tfrac 12\cdot\E[\nu_s]f}=\tfrac 12\cdot\Ent[\xi_s]{\E[\nu_s]f}.\] Bringing this into 14 , \[\begin{align} \Ent[\xi_s]{\E[\nu_s]f}\le \E[\xi_s]{\Ent[\nu_s]f}+\tfrac 12\cdot\Ent[\xi_s]{\E[\nu_s]f}+12s\lambda^2\cdot \E[\mu]f.\label{eq:mls2} \end{align}\tag{15}\] By the law of total entropy, for any $f: \bb R^d\to \bb R_{>0}$, \[\Ent[\mu]{f}=\E[\xi_s]{\Ent[\nu_s]{f}}+\Ent[\xi_s]{\E[\nu_s]{f}}.\] The final result can be derived via plugging this into 15 . ◻

5.4.2 From defective to standard modified log-Sobolev inequality↩︎

Combining the above defective modified log-Sobolev inequality for $\*P^{(s_0)}$ and similar arguments in the proof of 10, we obtain defective classical modified log-Sobolev inequality for $\mu$.

Corollary 2. Under 4, for any $0\le s_0\le \frac{1}{12\lambda^2}$ and $f:\bb R^d \to \bb R_{>0}$, \[\Ent[\mu]f\le \frac{3}{s_0}\cdot \exp\set{\int_{s_0}^{2L}\frac{L_s}{s(1+s)}\d s}\cdot\E[\mu]{f^{-1}\|\grad f\|^2}+24s_0\lambda^2\cdot \E[\mu]f.\]

On the other hand, we know that $\mu$ satisfies inequality. By a standard tightening argument, a defective mLSI together with inequality implies mLSI.

If a distribution $\mu$ over $\bb R^d$ satisfies classical inequality with constant $C^{\!{PI}}_\mu$ and a defective mLSI $\Ent[\mu]f \le A\cdot \E[\mu]{f^{-1}\|\grad f\|^2}+B\cdot \E[\mu]f$ for any $f:\bb R^d\to \bb R_{>0}$, then \[C^{\!{mLSI}}_{\mu}\le A+\frac{B+2}{4} C^{\!{PI}}_\mu.\]

Then the modified log-Sobolev inequality is a direct corollary of 11, Corollary 2 and Proposition [prop:tighten].

Theorem 12. If a distribution satisfies 1, 3 and 4, then \[C^{\!{mLSI}}_{\mu}\le \min_{s_0\in \left(0,\frac{1}{12\lambda^2}\right]}\frac{1}{s_0}\tp{3+\frac{12s_0\lambda^2+1}{2-e^{4s_0\lambda^2}}}\cdot \exp\set{\int_{s_0}^{2L}\frac{L_s}{s(1+s)}\d s}\] where $L_s = L_t^{\!{OU}}$ with $t = \log\sqrt{\frac{s+1}{s}}$.

5.5 The modified log-Sobolev constant of the mixture of strongly log-concave and log-smooth distributions↩︎

In this section, we apply our method to study the modified log-Sobolev constant of a mixture of strongly log-concave and log-smooth distributions.

To be precise, let $\rho$ denote a probability distribution over $\bb R^d$ with density $\propto e^{-U}$. Assume its potential function $U:\bb R^d\to \bb R$ is twice differentiable, $m$-strongly convex and $L$-smooth. The convolution $\mu = \nu * \rho$, with density $\mu(y) = \int_{\bb R^d} \rho(y-x)\nu(\d x)$, is a mixture of translations of $m$-strongly log-concave and $L$-log-smooth distribution $\rho$. When $\rho$ is the Gaussian distribution $\+N(0,\Sigma)$, $\mu$ is a mixture of Gaussian distributions with the same covariance. In the following part, we define $\+B_R = \set{x\in \bb R^d\cmid \|x\|\leq R}$ as the $d$-dimensional ball with radius $R$, and for a vector $v\in \bb R^d$, define $v^{\otimes 2} = vv^{\top}$. We will consider the case where $\nu$ is supported inside $\+B_R$ for some $R>0$.

Consider two distributions $\xi$ and $\pi$ where $\require{physics} \xi(y) \propto \int_{\bb R^d} \pi(x)\cdot e^{-f(x,y)}\dd x$ for some function $f:\bb R^{2d}\to \bb R$. Let $\nu_y$ be the distribution with density $\nu_y(x)\propto \pi(x)\cdot e^{-f(x,y)}$. The next lemma is a generalization of Lemma 4 and its proof is provided in 9.4.

Lemma 12. $-\grad^2_y \log \xi(y) = \E[X\sim \nu_y]{\grad^2_y f(X,y)} - \Cov[X\sim \nu_y]{\grad_y f(X,y)}$ for any $y\in\bb R^d$.

Equipped with this lemma, we can bound the log-smoothness of the mixture distribution.

Lemma 13. Suppose $\rho$ is an $m$-strongly log-concave and $L$-log-smooth distribution and $\nu$ is supported inside $\+B_R$. The distribution $\mu = \nu * \rho$ satisfies $-\grad^2_y \log \mu(y)\mge (m-L^2R^2)\cdot\!{Id}_d$ for any $y\in\bb R^d$.

Proof. For any fixed $y\in\bb R^d$ , choosing $f(x,y)=U(y-x)$ and $\pi=\nu$ in Lemma 12, we have \[-\grad^2_y \log \mu(y) = \E[X\sim \nu_y]{\grad^2 U(y-X)} - \Cov[X\sim \nu_y]{\grad U(y-X)}.\] Since $U$ is $m$-strongly convex, $\grad^2 U(x)\mge m\cdot\!{Id}_d$ for all $x\in\bb R^d$. For the covariance term, \[\begin{align} \norm{\Cov[X\sim \nu_y]{\grad U(y-X)}}_{\!{op}} &= \sup_{v\in\bb R^d,\|v\|=1} v^{\top}\Cov[X\sim \nu_y]{\grad U(y-X)}v \\ &= \sup_{v\in\bb R^d,\|v\|=1} \E[X\sim \nu_y]{v^{\top}\tp{\grad U(y-X)-\E[X'\sim\nu_y]{\grad U(y-X')}}^{\otimes 2}v}\\ &= \sup_{v\in\bb R^d,\|v\|=1} \Var[X\sim \nu_y]{v^{\top}\grad U(y-X)}\\ \mr{define g(x)=v^{\top}\grad U(y-x)}&= \sup_{v\in\bb R^d,\|v\|=1} \frac{1}{2}\cdot\E[X,X'\sim \nu_y]{\tp{g(X)-g(X')}^2}\\ \mr{g(x) is L-Lipschitz}&\le \sup_{v\in\bb R^d,\|v\|=1} \frac{L^2}{2}\cdot\E[X,X'\sim \nu_y]{\|X-X'\|^2}\\ &=L^2\cdot \tp{\E[X\sim \nu_y]{\|X\|^2}-\norm{\E[X\sim \nu_y]{X}}^2}\\ \mr{\nu_y is supported on \+B_R}&\le L^2R^2. \end{align}\] Therefore, \[-\grad^2_y \log \mu(y)\mge m\cdot\!{Id}_d-L^2R^2\cdot\!{Id}_d=(m-L^2R^2)\cdot\!{Id}_d.\] ◻

5.5.1 The convolution of OU process↩︎

Consider the OU process $\set{X^{\!{OU}}(t)}_{t\geq 0}$ starting from $\mu=\nu * \rho$. Recall that we use $\xi^{\!{OU}}_t$ to denote the law of $X^{\!{OU}}(t)$. We now analyze the convolution of $\xi^{\!{OU}}_t$. Let $W\sim\nu$, $Z\sim\rho$ and $\zeta\sim\+N(0,\!{Id}_d)$ be mutually independent. Then $X^{\!{OU}}(t)$ equals $e^{-t}(W+Z)+\sqrt{1-e^{-2t}}\cdot\zeta$ in distribution. Note that this can be viewed as $e^{-t}W+(e^{-t}Z+\sqrt{1-e^{-2t}}\cdot\zeta)$. Let $\nu_t$ be the law of $e^{-t}W$ and $\rho_t$ be the law of $(e^{-t}Z+\sqrt{1-e^{-2t}}\cdot\zeta)$. Then $\xi^{\!{OU}}_t=\nu_t * \rho_t$. By the assumption on $\nu$, $\nu_t$ is supported on $\+B_{e^{-t}R}$. The following lemma establishes bounds on the strong log-concavity and log-smoothness of $\rho_t$.

Lemma 14 (Lemma 28 in [35]). Suppose $\pi$ is a distribution on $\bb R^d$ such that $\forall x\in\bb R^d,M_{1}^{-1} \preceq -\grad^2 \log \pi(x) \preceq M_2^{-1}$ for some $M_1,M_2\in \bb R^{d\times d},M_1,M_2\succ 0$. Let $\xi$ be the mixture distribution $\pi*\+N(0,M)$. Then for any $x\in \bb R^d$, \[(M_1+M)^{-1} \preceq -\grad^2 \log \xi(x) \preceq (M_2+M)^{-1}.\]

Corollary 3. The distribution $\rho_t$ satisfies \[\frac{m}{e^{-2t}+(1-e^{-2t})m}\cdot\!{Id}_d\mle -\grad^2 \log \rho_t(x)\mle \frac{L}{e^{-2t}+(1-e^{-2t})L}\cdot\!{Id}_d\] for any $t\ge 0$ and $x\in\bb R^d$.

Proof. Recall that $Z\sim\rho$ where $\rho$ is $m$-strongly log-concave and $L$-log-smooth. Therefore for any fixed $t\ge 0$, $e^{2t}m \mle-\nabla^2 \log p_{e^{-t}Z}(x)\mle e^{2t}L$ for any $x\in \bb R^d$. From Lemma 14, with $M_1=e^{-2t}m^{-1}\cdot\!{Id}_d$, $M_2=e^{-2t}L^{-1}\cdot\!{Id}_d$ and $M=(1-e^{-2t})\!{Id}_d$ , we have \[\frac{m}{e^{-2t}+(1-e^{-2t})m}\cdot\!{Id}_d\mle -\grad^2 \log \rho_t(x)\mle \frac{L}{e^{-2t}+(1-e^{-2t})L}\cdot\!{Id}_d\] for any $x\in \bb R^d$. ◻

5.5.2 The bound on the mLSI constant via concatenation↩︎

Now we are ready to prove the modified log-Sobolev constant of the mixture of strongly log-concave and log-smooth distributions.

Theorem 13. Suppose $\rho$ is an $m$-strongly log-concave and $L$-log-smooth distribution and $\nu$ is supported inside $\+B_R$. The modified log-Sobolev constant of mixture distribution $\mu=\nu*\rho$ satisfies \[C^{\!{mLSI}}_{\mu}\leq \frac{1}{2m}\cdot e^{LR^2}.\]

Proof. Fix any $t\ge 0$. Recall that $\xi^{\!{OU}}_t=\nu_t * \rho_t$ and $\nu_t$ is supported on $\+B_{R'}$ where $R'\defeq e^{-t}R$. By Corollary 3, define $m'\defeq \frac{m}{e^{-2t}+(1-e^{-2t})m}$ and $L'\defeq \frac{L}{e^{-2t}+(1-e^{-2t})L}$, then $\rho_t$ is $m'$-strongly log-concave and $L'$-log-smooth. From Lemma 13, for any $y\in\bb R^d$, \[-\grad^2_y \log \xi_t^{\!{OU}}(y)\mge (m'-L'^2R'^2)\cdot\!{Id}_d=\tp{\frac{m}{e^{-2t}+(1-e^{-2t})m}-\tp{\frac{L}{e^{-2t}+(1-e^{-2t})L}}^2\tp{e^{-t}R}^2}\cdot\!{Id}_d.\] Therefore, $\mu$ satisfies 3 with $L^{\!{OU}}_t=-\frac{m}{e^{-2t}+(1-e^{-2t})m}+\tp{\frac{L}{e^{-2t}+(1-e^{-2t})L}}^2\tp{e^{-t}R}^2$. By Lemma 2, for any $s\ge 0$ and $v\in\bb R^d$, \[\norm{\cov{\+T_v \nu_s}}_{\!{op}}\le \frac{1}{s}+\frac{L_s}{s(1+s)}=\frac{1}{s+m}+\frac{L^2R^2}{(s+L)^2},\] where $L_s=L^{\!{OU}}_t$ with $t=\log\sqrt{\frac{s+1}{s}}$. From 5, for any $T>0$, \[\sup_{f:\bb R^d \to \bb R_{>0}} \frac{\Ent[\mu]{f}}{\E[\xi_T]{\Ent[\nu_T]{f}}} \leq \exp\set{\int_0^T \tp{\frac{1}{s+m}+\frac{L^2R^2}{(s+L)^2}} \d s}=\frac{T+m}{m}\cdot\exp\tp{\frac{LT}{L+T}R^2}.\] For the classical modified log-Sobolev inequality, we have \[\begin{align} C^{\!{mLSI}}_{\mu} &= \sup_{f:\bb R^d \to \bb R_{>0}} \frac{\Ent[\mu]{f}}{\E[\mu]{f^{-1}\|\grad f\|^2}} \\ &= \sup_{f:\bb R^d \to \bb R_{>0}} \frac{\E[\xi_T]{\Ent[\nu_T]{f}}}{\E[\mu]{f^{-1}\|\grad f\|^2}}\cdot \frac{\Ent[\mu]{f}}{\E[\xi_T]{\Ent[\nu_T]{f}}} \\ &\leq \tp{\sup_{f:\bb R^d \to \bb R_{>0}} \frac{\E[\xi_T]{\Ent[\nu_T]{f}}}{\E[\xi_T]{\E[\nu_T]{f^{-1}\|\grad f\|^2}}}}\cdot \tp{\sup_{f:\bb R^d \to \bb R_{>0}} \frac{\Ent[\mu]{f}}{\E[\xi_T]{\Ent[\nu_T]{f}}}}. \end{align}\] For any $T>\max\set{0,L^2R^2-m}$, $\nu_T$ is $(T+m-L^2R^2)$-strongly log-concave almost surely. By a well-known consequence of the Bakry-Émery criterion (see , [30]), it satisfies modified log-Sobolev inequality with constant $\tfrac 12\cdot(T+m-L^2R^2)^{-1}$ almost surely. Therefore, \[C^{\!{mLSI}}_{\mu}\leq \inf_{T>\max\set{0,L^2R^2-m}} \frac{T+m}{2m(T+m-L^2R^2)}\cdot\exp\tp{\frac{LT}{L+T}R^2}\le \frac{1}{2m}\cdot e^{LR^2}.\] ◻

As a special case, our 13 naturally recovers and generalizes the previous results for mixture of Gaussians in [29]. Let $\rho$ be the Gaussian distribution $\+N(0,\Sigma)$. Recall that $\lambda_{\min}(\Sigma)$ denotes the minimum eigenvalue of $\Sigma$. The Gaussian $\+N(0,\Sigma)$ is $\norm{\Sigma}_{\!{op}}^{-1}$-strongly log-concave and $\lambda_{\min}(\Sigma)^{-1}$-log-smooth.

Corollary 4. Suppose $\nu$ is supported on $\+B_R$ and $\mu = \nu * \+N(0, \Sigma)$. We have $C^{\!{mLSI}}_\mu\leq \frac{1}{2}\norm{\Sigma}_{\!{op}}\cdot e^{\lambda_{\min}(\Sigma)^{-1}\cdot R^2}$.

6 The convergence of the continuous-time Gaussian dynamics↩︎

We first prove the convergence of the continuous-time Gaussian dynamics with the heat kernel $\*H_t$. The following lemma is proved in [36] for chains with a countable space. We generalize their proof to space $\bb R^d$.

Assume $\*P^{(T)}$ is a reversible and irreducible Markov chain, and the stationary distribution $\mu$ satisfies a inequality with regard to $\*P^{(T)}$ with constant $C$. Then for any bounded measurable $f:\bb R^d\to \bb R$ with $\+E_{\*P^{(T)}}(f)\neq 0$ and $\E[\mu]{f}=0$, \[\|\*H_t f\|^2_{\mu} \leq e^{-\frac{2t}{C}} \cdot \Var[\mu]{f}.\]

Proof. Recall the definition of $\*H_t$ in 7 , $\forall t\geq 0, \forall x,y\in \bb R^d$, the density \[\begin{align} \*H_t(x,y) &= \sum_{k=0}^{\infty} \Pr{K_t=k}\cdot \tp{\*P^{(T)}}^k(x, y)\\ &= \sum_{k=0}^{\infty} \frac{e^{-t}t^k}{k!}\cdot \tp{\*P^{(T)}}^k(x, y). \end{align}\] Then \[\require{physics} \begin{align} \frac{\dd }{\dd t} \*H_t(x,y) &= \sum_{k=1}^{\infty} \frac{e^{-t}t^{k-1}}{(k-1)!}\cdot \tp{\*P^{(T)}}^k(x, y) - \sum_{k=0}^{\infty} \frac{e^{-t}t^k}{k!}\cdot \tp{\*P^{(T)}}^k(x, y) \\ &= \int_{\bb R^d} \*P^{(T)}(x,z)\cdot \*H_t(z,y) \dd z - \*H_t(x,y), \end{align}\] and \[\require{physics} \begin{align} \frac{\dd }{\dd t} \*H_t f(x) &= \int_{\bb R^d} \*P^{(T)}(x,z)\cdot \*H_t f(z) \dd z - \*H_t f(x) \notag \\ &= \tp{\*P^{(T)} - I}(\*H_t f)(x).\label{eq:Ht-1} \end{align}\tag{16}\] Define the function $g(t) = \|\*H_t f\|^2_{\mu}$. From 16 , \[\require{physics} \begin{align} g'(t) &= \int_{\bb R^d} 2 \*H_t f(x)\cdot \frac{\dd }{\dd t} \*H_t f(x) \cdot \mu(x) \dd x\\ &= \int_{\bb R^d} 2 \*H_t f(x)\cdot \tp{\*P^{(T)} - I}(\*H_t f)(x) \cdot \mu(x) \dd x\\ &= 2\int_{\bb R^d \times \bb R^d} \*H_t f(x) \mu(x) \cdot \*H_t f(y) \*P^{(T)}(x,y) \dd y \dd x - 2\int_{\bb R^d} \*H_t f(x)^2 \cdot \mu(x) \dd x\\ &= -\int_{\bb R^d \times \bb R^d} \tp{\*H_t f(x)-\*H_t f(y)}^2 \mu(x)\*P^{(T)}(x,y) \dd y \dd x \\ &= -2\+E_{\*P^{(T)}}(\*H_t f). \end{align}\] Due to the reversibility of $\*H_t$, \[\require{physics} \E[\mu]{\*H_t f} = \int_{\bb R^d\times \bb R^d} f(y)\*H_t(x,y)\mu(x)\dd x \dd y = \int_{\bb R^d\times \bb R^d} f(y)\*H_t(y,x)\mu(y)\dd x \dd y = \E[\mu]{f}=0.\] Since $\mu$ satisfies a inequality with regard to $\*P^{(T)}$ with constant $C$, \[\+E_{\*P^{(T)}}(\*H_t f) \geq \frac{\Var[\mu]{\*H_t f}}{C} = \frac{\|\*H_t f\|^2_{\mu}}{C}.\] Therefore, $g'(t)\leq -\frac{2}{C} g(t)$. Consequently, \[\|\*H_t f\|^2_{\mu}=g(t)\leq e^{-\frac{2t}{C}} \cdot g(0) = e^{-\frac{2t}{C}}\cdot \Var[\mu]{f}.\] ◻

Let $\mu_t$ be the distribution induced by running the continuous-time restricted Gaussian dynamics with heat kernel $\*H_t$ starting from $\mu_0$. Lemma 15 gives the convergence rate of this Markov process in $\chi^2$ divergence and total variation distance.

Lemma 15. Assume $\*P^{(T)}$ is a reversible and irreducible Markov chain, and the stationary distribution $\mu$ satisfies a inequality with regard to $\*P^{(T)}$ with constant $C$. Then $\chi^2(\mu_t\,\|\, \mu) \leq e^{-\frac{2 t}{C}} \cdot \chi^2(\mu_0\,\|\, \mu)$, and consequently, $\!{TV}(\mu_t,\mu)\leq \tfrac{1}{2}\cdot e^{-\frac{t}{C}}\cdot \sqrt{\chi^2(\mu_0\,\|\, \mu)}$.

Proof. Define the bounded and measurable function $f = \frac{\mu_0}{\mu} -1$. Then \[\require{physics} \Var[\mu]{f} = \mathlarger{\int}_{\bb R^d} \tp{\frac{\mu_0(x)}{\mu(x)} -1}^2 \mu(x) \dd x = \chi^2(\mu_0\,\|\, \mu),\] and \[\require{physics} \begin{align} \*H_t f(x) &= \mathlarger{\int}_{\bb R^d} \tp{\frac{\mu_0(y)}{\mu(y)} -1} \*H_t(x,\dd y) \\ &= \mathlarger{\int}_{\bb R^d} \frac{\mu_0(y)}{\mu(x)}\cdot \frac{\mu(x)\*H_t(x,y)}{\mu(y)} \dd y - 1 \\ \mr{reversibility} &= \mathlarger{\int}_{\bb R^d} \frac{\mu_0(y)}{\mu(x)}\cdot \frac{\mu(y)\*H_t(y, x)}{\mu(y) }\dd y - 1 \\ &= \frac{\mu_t(x)}{\mu(x)} - 1. \end{align}\] From Proposition [prop:Ht], we have $\chi^2(\mu_t\,\|\, \mu) \leq e^{-\frac{2t}{C}} \cdot \chi^2(\mu_0\,\|\, \mu)$.

From the Cauchy-Schwarz inequality, \[\require{physics} \!{TV}(\mu_t,\mu) = \frac{1}{2}\mathlarger{\int}_{\bb R^d} \abs{\mu_t(x)-\mu(x)} \frac{\sqrt{\mu(x)}}{\sqrt{\mu(x)}} \dd x \leq \frac{1}{2} \sqrt{\mathlarger{\int}_{\bb R^d} \frac{\tp{\mu_t(x)-\mu(x)}^2}{\mu(x)} \dd x} = \frac{\sqrt{\chi^2(\mu_t\,\|\, \mu)}}{2}.\] This yields the second conclusion. ◻

Then we are ready to prove 7.

Proof of 7. In the continuous-time Markov process with heat kernel $\set{\*H_t}$, let $\tau\geq 0$ be the time that the $K$-th transition happens. Then $p_{Y_{\+K}}$ is exactly $\mu_{t\wedge \tau}$ with $t=\frac{K}{2}$. According to Lemma 22, \[\Pr{\tau\leq t} = \Pr{K'\geq K} \leq e^{-\frac{t^2}{2K}} \leq e^{-\frac{K}{8}}. \label{eq:GD-1}\tag{17}\] Let $\mu_t^{(>)}$ and $\mu_t^{(\leq)}$ be the distribution $\mu_t$ conditioned on $\tau> t$ and $\tau\leq t$ respectively. Then for any $x\in \bb R^d$, $\mu_t(x) = \Pr{\tau> t}\cdot \mu_t^{(>)}(x) + \Pr{\tau\leq t}\cdot \mu_t^{(\leq)}(x)$. Note that \[\require{physics} \begin{align} \!{TV}(\mu_t,\mu) &= \frac{1}{2}\int_{\bb R^d} \abs{\mu_t(x)-\mu(x)} \dd x\\ \mr{triangle inequality}&\geq \Pr{\tau> t}\cdot \!{TV}\tp{\mu_t^{(>)}, \mu} - \Pr{\tau\leq t}\cdot \!{TV}\tp{\mu_t^{(\leq)}, \mu} \\ \mr{\Cref{eq:GD-1}} &\geq \Pr{\tau> t}\cdot \!{TV}\tp{\mu_t^{(>)}, \mu} - e^{-\frac{K}{8}}. \end{align}\] From Lemma 15, $\!{TV}(\mu_t,\mu)\leq \frac{e^{-\frac{K}{C^{\!{PI}}_{\mu}\tp{\*P^{(T)}}}} }{2}\cdot \sqrt{\chi^2(\mu_0\,\|\, \mu)}$. This yields \[\Pr{\tau> t}\cdot \!{TV}\tp{\mu_t^{(>)}, \mu} \leq \frac{e^{-\frac{K}{C^{\!{PI}}_{\mu}\tp{\*P^{(T)}}}}}{2} \cdot \sqrt{\chi^2(\mu_0\,\|\, \mu)} + e^{-\frac{K}{8}}. \label{eq:GD-2}\tag{18}\] Combining [eq:GD-1,eq:GD-2], \[\begin{align} \!{TV}\tp{p_{Y_{\+K}}, \mu} &= \!{TV}\tp{\mu_{t\wedge \tau}, \mu} \\ \mr{triangle inequality}&\leq \Pr{\tau >t}\cdot \!{TV}\tp{\mu_t^{(>)}, \mu} + \Pr{\tau \leq t}\\ \mr{\Cref{eq:GD-1}}&\leq \Pr{\tau >t}\cdot \!{TV}\tp{\mu_t^{(>)}, \mu} + e^{-\frac{K}{8}} \\ \mr{\Cref{eq:GD-2}}&\leq \frac{e^{-\frac{K}{C^{\!{PI}}_\mu\tp{\*P^{(T)}}}}}{2} \cdot \sqrt{\chi^2(\mu_0\,\|\, \mu)} + 2e^{-\frac{K}{8}}. \end{align}\] ◻

7 The initialization bound in 3 ↩︎

In this section, we derive an explicit bound of the term $\log \chi^2\tp{\mu_0\,\|\,\nu_{s_0}(\cdot\,|\,X_{s_0})}$.

We begin by bounding the first moment of $\nu_{s_0}(\cdot\,|\,y)$.

Lemma 16. For any $y\in \bb R^d$, $\E[X\sim \nu_{s_0}(\cdot\,|\,y)]{\norm{X}}\leq 2\sqrt{M}\cdot e^{\frac{\norm{y}^2}{s_0}+1}$.

Proof. By definition, \[\require{physics} \begin{align} \E[X\sim \nu_{s_0}(\cdot\,|\,y)]{\norm{X}} &= \frac{\mathlarger{\int}_{\bb R^d} \|x\| \cdot \exp\set{-V(x) - \frac{\norm{s_0\cdot x - y}^2}{2s_0}} \dd x}{\mathlarger{\int}_{\bb R^d} \exp\set{-V(x) - \frac{\norm{s_0\cdot x - y}^2}{2s_0}} \dd x}\\ &\leq \frac{\mathlarger{\int}_{\bb R^d} \|x\| \cdot e^{-V(x)} \dd x}{\mathlarger{\int}_{\bb R^d} \exp\set{-V(x) - \frac{\norm{s_0\cdot x }^2 + \norm{y}^2}{s_0}} \dd x}\\ &\leq \E[X\sim \mu]{\norm{X}}\cdot \frac{e^{\frac{\norm{y}^2}{s_0}}\cdot \mathlarger{\int}_{\bb R^d} e^{-V(x)} \dd x}{\mathlarger{\int}_{\bb R^d} \exp\set{-V(x) - \frac{\norm{s_0\cdot x }^2 }{s_0}} \dd x}\\ &= \E[X\sim \mu]{\norm{X}}\cdot e^{\frac{\norm{y}^2}{s_0}} \cdot \frac{1}{\E[X\sim \mu]{e^{-s_0\norm{x}^2}}}. \end{align}\] From 2 and the Jensen inequality, \[\E[X\sim \mu]{\norm{X}} \leq \sqrt{\E[X\sim \mu]{\norm{X}^2}} \leq \sqrt{M}.\] Using 2 again and together with the Markov’s inequality, we have \[\Pr[X\sim \mu]{\norm{X}^2 \geq \frac{1}{s_0}} \leq s_0\cdot M <\frac{1}{2}\] and therefore, \[\E[X\sim \mu]{e^{-s_0\norm{x}^2}} \geq \Pr[X\sim \mu]{\norm{X}^2 < \frac{1}{s_0}} \cdot e^{-1} > \frac{1}{2e}.\] Combining all these together, we have \[\E[X\sim \nu_{s_0}(\cdot\,|\,y)]{\norm{X}} < 2\sqrt{M}\cdot e^{\frac{\norm{y}^2}{s_0}+1}.\] ◻

Then we can use the next lemma to bound the initial $\chi^2$ divergence. The proof of Lemma 17 follows the approach of Lemma 32 in [8].

Lemma 17. Define the function $U_y(x) = V(x) + \frac{\norm{y - s_0\cdot x}^2}{2s_0}$. For $\mu_0=\+N\tp{-\frac{\grad U_y(0)}{2(L+s_0)},\frac{I_d}{2(L+s_0)}}$, \[\log \chi^2\tp{\mu_0\,\|\,\nu_{s_0}(\cdot\,|\,y)} \leq \log(2e) + V(0) - \min V + \frac{d}{2}\log \tp{(L+s_0)\cdot 16e^2M} + \frac{(2d+1)\norm{y}^2}{2s_0}.\]

Proof. By the definition of $\chi^2$ divergence, we know \[\log \chi^2\tp{\mu_0\,\|\,\nu_{s_0}(\cdot\,|\,y)} \leq \+R_2\tp{\mu_0\,\|\,\nu_{s_0}(\cdot\,|\,y)} \leq \+R_{\infty}\tp{\mu_0\,\|\,\nu_{s_0}(\cdot\,|\,y)}.\] It only needs to bound \[\require{physics} \begin{align} \+R_{\infty}\tp{\mu_0\,\|\,\nu_{s_0}(\cdot\,|\,y)} &= \log\tp{\sup_{x\in \bb R^d} \frac{\mu_0(x)}{\nu_{s_0}(x|y)}}\\ &= \log\tp{\sup_{x\in \bb R^d} \frac{\exp\set{-(L+s_0)\cdot \norm{x + \frac{\grad U_y(0)}{2(L+s_0)}}^2 + U_y(x)}}{\tp{\frac{\pi}{L+s_0}}^{\frac{d}{2}}} \cdot \int_{\bb R^d} e^{-U_y(z)} \dd z}. \end{align}\]

Recall that \[\nu_{s_0}(x\,|\,y) \propto \mu(x)\cdot \exp\set{-\frac{\norm{y - s_0\cdot x}^2}{2s_0}}.\] Under 1, $\nu_{s_0}(\cdot\,|\,y)$ is $(L+s_0)$-log-smooth. Then for any $x\in \bb R^d$, there exists some $\lambda\in [0,1]$ such that \[\begin{align} U_y(x) - U_y(0) &= \inner{\grad U_y(\lambda x)}{x} \leq \inner{\grad U_y(0)}{x} + \norm{\inner{\grad U_y(\lambda x) - \grad U_y(0)}{x}}\\ \mr{smoothness}&\leq \inner{\grad U_y(0)}{x} + (L+s_0)\|x\|^2. \end{align}\] Therefore, \[\begin{align} -(L+s_0)\cdot \norm{x + \frac{\grad U_y(0)}{2(L+s_0)}}^2 + U_y(x) &\leq U_y(0) + \inner{\grad U_y(0)}{x} + (L+s_0)\|x\|^2 -(L+s_0)\cdot \norm{x + \frac{\grad U_y(0)}{2(L+s_0)}}^2 \notag \\ &= U_y(0) - \frac{\norm{\grad U_y(0)}^2}{4(L+s_0)}\\ &= V(0) + \frac{\norm{y}^2}{2s_0} - \frac{\norm{\grad V(0) - y}^2}{4(L+s_0)}. \label{eq:init-1} \end{align}\tag{19}\] Then we calculate $\require{physics} \frac{\int_{\bb R^d} e^{-U_y(z)} \dd z}{\tp{\frac{\pi}{L+s_0}}^{\frac{d}{2}}}$. Let $r = \E[X\sim \nu_{s_0}(\cdot\,|\,y)]{\norm{X}}$. From Lemma 16, $r\leq 2\sqrt{M}\cdot e^{\frac{\norm{y}^2}{s_0}+1}$. For any $\delta>0$, from the Markov’s inequality, \[\require{physics} \begin{align} \frac{\int_{\bb R^d} e^{-U_y(z) - \delta\cdot \|z\|^2} \dd z}{\int_{\bb R^d} e^{-U_y(z)} \dd z} &= \E[Z\sim \nu_{s_0}(\cdot\,|\,y)]{e^{- \delta\cdot \|Z\|^2}} \notag \\ &\geq \exp\set{-4\delta \cdot r^2}\cdot \Pr[Z\sim \nu_{s_0}(\cdot\,|\,y)]{\|Z\| \leq 2r} \notag \\ &\geq \frac{1}{2}\exp\set{-4\delta \cdot r^2}. \label{eq:init-2} \end{align}\tag{20}\] We also have \[\require{physics} \begin{align} \frac{\int_{\bb R^d} e^{-U_y(z) - \delta\cdot \|z\|^2} \dd z}{\tp{\frac{\pi}{L+s_0}}^{\frac{d}{2}}} &\leq \frac{e^{-\min U_y}\cdot \int_{\bb R^d} e^{ - \delta\cdot \|z\|^2} \dd z}{\tp{\frac{\pi}{L+s_0}}^{\frac{d}{2}}} \notag \\ &\leq e^{-\min U_y} \cdot \tp{\frac{L+s_0}{\delta}}^{\frac{d}{2}} \notag \\ &\leq e^{-\min V} \cdot \tp{\frac{L+s_0}{\delta}}^{\frac{d}{2}}. \label{eq:init-3} \end{align}\tag{21}\] Combining [eq:init-1,eq:init-2,eq:init-3] and choosing $\delta = \frac{1}{4r^2}$, we have \[\begin{align} \+R_{\infty}\tp{\mu_0\,\|\,\nu_{s_0}(\cdot\,|\,y)} &\leq V(0) + \frac{\norm{y}^2}{2s_0} - \frac{\norm{\grad V(0) - y}^2}{4(L+s_0)} + \log(2e) - \min V \\ &\quad + \frac{d}{2}\log \tp{(L+s_0)\cdot 16M\cdot e^{\frac{2\norm{y}^2}{s_0}+2}}\\ &\leq \log(2e) + V(0) - \min V + \frac{d}{2}\log \tp{(L+s_0)\cdot 16e^2M} + \frac{(2d+1)\norm{y}^2}{2s_0}. \end{align}\] ◻

8 The implementation of RGO↩︎

In this section, we provide the details of the rejection sampling algorithm in [23] for the completeness of the paper. Let $V_y^\sigma(x):= V(x) + \frac{1}{2\sigma^2}\|x-y\|^2$. Recall that our target is to generate a sample from the distribution $\mu_{y,\sigma^2}$ with density $\propto \exp\set{-V_y^\sigma(x)}$ under 1.

To implementation the rejection sampling algorithm, we first need to find an approximate minimizer of $V_y^\sigma$. This can be achieved via the accelerated gradient algorithm in [23].

Lemma 18 (A corollary of Proposition 3.2 in [23]). Assume $V$ is $L$-smooth and $\sigma^2\le \frac{1}{2Ld}$. For any fixed $y\in \bb R^d$, Algorithm 4 outputs a point $w\in \bb R^d$ such that \[\norm{\grad V(w) + \frac{1}{\sigma^2} (w-y)} \le \sqrt{L d}\] within $\wt{\+O}(1)$ iterations in expectation.

The following lemma gives the convergence bound of the rejection sampling algorithm and 6 is then a direct corollary.

Lemma 19 (A corollary of Lemma 18 and Proposition 3.4 in [23]). Assume $V$ is $L$-smooth. Then the random variable generated by Algorithm 5 follows the distribution with density $\propto \exp\set{-V_y^\sigma(x)}$. Moreover, if$\sigma^2 \le \frac{1}{2Ld}$, then the expected number of rejection steps in Algorithm 5 is $\wt{\+O}(1)$. ³

9 Omitted proofs↩︎

9.1 The proofs in 2 ↩︎

Proof of Proposition [prop:mLSIofSL]. By definition, \[\require{physics} \begin{align} \+E_{\*P^{(T)}}(f,\log f) &= \frac{1}{2}\cdot \int_{\bb R^d\times \bb R^d} \tp{f(x)-f(y)}\tp{\log f(x)-\log f(y)} \mu(x)\*P^{(T)}(x,\dd y) \dd x \\ \mr{\Cref{eq:MC}}&= \frac{1}{2} \E[X(T)\sim \xi_T]{\int_{\bb R^d} \int_{\bb R^d}(f(x)-f(y))(\log f(x)-\log f(y))\nu_T(x)\nu_T(y) \d x \d y}\\ &=\E[X(T)\sim \xi_T]{ \int_{\bb R^d} f(x) \log f(x) \nu_T(x) \d x - \E[\nu_T]{f}\E[\nu_T]{\log f}}\\ \mr{Jensen's inequality}&\geq \E[X(T)\sim \xi_T]{ \E[\nu_T]{f\log f} - \E[\nu_T]{f}\log\E[\nu_T]{ f}}\\ &= \E[X(T)\sim \xi_T]{\Ent[\nu_T]{f}}. \end{align}\] Therefore, \[\begin{align} C^{\!{mLSI}}_{\mu}\tp{\*P^{(T)}} &= \sup_{f\colon \bb R^d\to \bb R_{> 0}} \frac{\Ent[\mu]{f}}{\+E_{\*P^{(T)}}(f,\log f)} \leq \sup_{f\colon \bb R^d\to \bb R_{>0}} \frac{\Ent[\mu]{f}}{\E[X(T)\sim \xi_T]{\Ent[\nu_T]{f}}}. \end{align}\] ◻

To prove 4, we need the fact that the stochastic localization scheme is a linear-tilt scheme.

Lemma 20 (Theorem 2 in [37]). Write $L_x$ for the likelihood ratio process of $\nu_s$ with respect to $\mu$ at $x$, i.e., $\require{physics} L_s(x)\defeq \frac{\dd \nu_s}{\dd \mu}(x)$. Then there exists a Brownian motion $\set{W(s)}_{s\geq 0}$ adapted to the filtration generated by $\set{X(s)}_{s\geq 0}$, such that for all $x\in \bb R^d$, $s\geq 0$, \[\require{physics} \dd L_s(x) = L_s(x)\cdot \inner{x-\m{\nu_s}}{\dd W(s)}, \;L_0(x)=1,\] where $\require{physics} \dd L_s(x)$ denotes the time differential of $L_s(x)$.

Proof of 4. In the following proof, all the differential notations refer to time derivatives. From Lemma 20, for any $f:\bb R^d\to \bb R$, \[\require{physics} \begin{align} \dd \Var[\nu_s]{f} &= \int_{\bb R^d} f(x)^2 \cdot \dd \nu_s(x) \dd x - \dd \tp{\int_{\bb R^d} f(x) \nu_s(x) \dd x}^2\\ \mr{Ito's Lemma}&= \int_{\bb R^d} f(x)^2 \cdot \nu_s(x)\cdot \inner{x-\m{\nu_s}}{\dd W(s)} \dd x \\ &\quad - 2 \tp{\int_{\bb R^d} f(x) \nu_s(x) \dd x}\cdot \tp{\int_{\bb R^d} f(x) \cdot \nu_s(x)\cdot \inner{x-\m{\nu_s}}{\dd W(s)} \dd x }\\ &\quad - \tp{\int_{\bb R^d} f(x) \cdot \nu_s(x)\cdot \inner{x-\m{\nu_s}}{\dd W(s)} \dd x}^2. \end{align}\] Let $\set{\+F_s}_{s\geq 0}$ be the filtration generated by $\set{X(s)}_{s\geq 0}$. Then $\E{\d W(s)\mid \+F_s} = 0$ and \[\require{physics} \begin{align} \E{\dd \Var[\nu_s]{f}\mid \+F_s} &= - \E{ \tp{\int_{\bb R^d} f(x) \cdot \nu_s(x)\cdot \inner{x-\m{\nu_s}}{\dd W(s)} \dd x}^2 \mid \+F_s }\\ &= - \Var{\inner{\int_{\bb R^d} f(x) \cdot \nu_s(x)\cdot (x-\m{\nu_s}) \dd x}{\dd W(s)} \mid \+F_s }. \end{align}\] Note that for any vector $v\in \bb R^n$ and any random vector $X$, \[\begin{align} \Var{\inner{v}{X}} & = \E{\inner{v}{X-\E{X}}^2}\\ &= \sum_{1\leq i\leq n\atop 1\leq j\leq n} \E{v_iv_j\cdot (X_i-\E{X_i})(X_j-\E{X_j})}\\ &= \inner{\!{Cov}(X)v}{v}. \end{align}\] Therefore, \[\require{physics} \begin{align} \E{\dd \Var[\nu_s]{f}\mid \+F_s} &= - \norm{\int_{\bb R^d} f(x) \cdot \nu_s(x)\cdot (x-\m{\nu_s}) \dd x}^2 \dd s\\ &=-\sup_{\theta\in \bb R^n\atop \|\theta\|=1} \tp{\int_{\bb R^d} f(x) \cdot \nu_s(x)\cdot \inner{x-\m{\nu_s}}{\theta} \dd x}^2 \dd s\\ &=-\sup_{\theta\in \bb R^n\atop \|\theta\|=1} \tp{\int_{\bb R^d} \tp{f(x) - \E[\nu_s]{f}} \cdot \nu_s(x)\cdot \inner{x-\m{\nu_s}}{\theta} \dd x}^2 \dd s\\ \mr{Cauchy-Schwarz inequality}&\geq -\Var[\nu_s]{f}\cdot \sup_{\theta\in \bb R^n\atop \|\theta\|=1} \int_{\bb R^d}\inner{x-\m{\nu_s}}{\theta}^2 \nu_s(x)\dd x \dd s\\ &= -\Var[\nu_s]{f}\cdot \sup_{\theta\in \bb R^n\atop \|\theta\|=1} \Var[\nu_s]{\inner{\theta}{X-\m{\nu_s}}} \dd s\\ &= -\Var[\nu_s]{f}\cdot \sup_{\theta\in \bb R^n\atop \|\theta\|=1} \inner{\cov{\nu_s}\theta}{\theta}\dd s\\ &=-\Var[\nu_s]{f}\cdot \norm{\cov{\nu_s}}_{\!{op}} \dd s. \end{align}\] Consequently, we have \[\require{physics} \begin{align} \dd \E{ \Var[\nu_s]{f}} &= \E{ \dd \Var[\nu_s]{f}} \geq - \theta_s\cdot \E{\Var[\nu_s]{f}} \dd s, \end{align}\] and \[\require{physics} \dd \log \E{ \Var[\nu_s]{f}} \geq -\theta_s \dd s.\] Integrating both sides from $0$ to $T$, \[\require{physics} \log \tp{\frac{\E{\Var[\nu_T]{f}}}{\Var[\mu]{f}}} \geq -\int_0^T \theta_s \dd s.\]

Then according to Proposition [prop:PIofSL], \[\require{physics} \begin{align} C^{\!{PI}}_\mu\tp{\*P^{(T)}} &= \sup_{f\colon \bb R^d\to \bb R} \frac{\Var[\mu]{f}}{\E[X(s)\sim \xi_T]{\Var[\nu_T]{f}}} \leq e^{\int_0^T \theta_s \dd s}. \end{align}\] ◻

9.2 The proof in 3 ↩︎

Proof of Lemma 1. From 6 , we know that $X^{\!{OU}}(t)$ equals $e^{-t}\cdot X^{\!{OU}}(0) + \sqrt{1-e^{-2t}}\cdot\zeta$ in distribution, where $\zeta\sim \+N(0,\!{Id}_d)$ is independent with $X^{\!{OU}}(0)$. For $X(s)$ defined in 4 , \[\sqrt{\frac{1}{s(1+s)}}\cdot X(s) = \sqrt{\frac{s}{(1+s)}} \cdot X + \sqrt{\frac{1}{s(1+s)}}\cdot B(s)\] Since $\sqrt{\frac{s}{(1+s)}} = \sqrt{\frac{\frac{e^{-2t}}{1-e^{-2t}}}{1+\frac{e^{-2t}}{1-e^{-2t}}}} = e^{-t}$,$\frac{1}{\sqrt{1+s}} = \frac{1}{\sqrt{1+ \frac{e^{-2t}}{1-e^{-2t}}}} = \sqrt{1-e^{-2t}}$, the distributions of $X^{\!{OU}}(t)$ and $\sqrt{\frac{1}{s(1+s)}}\cdot X(s)$ are the same for any $t>0$.

Recall that $\nu^{\!{OU}}_t(\cdot\,|\,y)$ is the distribution of $X^{\!{OU}}(0)$ given $X^{\!{OU}}(t) = y$,then \[\nu^{\!{OU}}_t(x\,|\,y) \propto \mu(x) \cdot \exp\set{-\frac{1}{2(1-e^{-2t})}\norm{e^{-t}x - y}^2}.\] On the other hand, in the stochastic localization process, for any $s>0$ and $z\in \bb R^d$, \[\begin{align} \nu_s(x\,|\,z) &\propto \mu(x)\cdot \exp\set{-\frac{\|sx-z\|^2}{2s}}\\ \mr{z=\sqrt{s(1+s)}y} &= \mu(x)\cdot \exp\set{-\frac{\|sx-\sqrt{s(1+s)}y\|^2}{2s}} \\ \mr{s = \frac{e^{-2t}}{1-e^{-2t}} } &= \mu(x)\cdot \exp\set{-\frac{1}{2(1-e^{-2t})}\norm{e^{-t}x - y}^2}. \end{align}\] Therefore, $\nu_s(x\,|\,z) = \nu^{\!{OU}}_t(x\,|\,y)$. ◻

Proof of Lemma 3. In this proof, we may abbreviate $p_{X_s}$ as $p_s$. Note that \[\begin{align} p_s(y) = s^{-\frac{d}{2}}\int_{\bb R^d} \phi\tp{-\frac{\norm{y-sx}^2}{2s}}\cdot \mu(x) \d x = (2\pi \cdot s)^{-\frac{d}{2}} \int_{\bb R^d} \exp\tp{-\frac{\norm{y-sx}^2}{2s}}\mu(x)\d x. \end{align}\] We let $q_s(x,y)\defeq \exp\tp{-\frac{\norm{y-sx}^2}{2s}}\mu(x)$ and have that \[\require{physics} \begin{align} \grad_y p_s(y) &= (2\pi\cdot s)^{-\frac{d}{2}}\int_{\bb R^d} \exp\tp{-\frac{\norm{y-sx}^2}{2s}} \mu(x) \cdot \tp{x-y/s} \dd x\\ &= (2\pi\cdot s)^{-\frac{d}{2}}\int_{\bb R^d} q_s(x,y) \cdot \tp{x-y/s} \dd x. \end{align}\] It follows from Bayes’ rule that $p_{X|X_s}(x|y) \propto q_s(x,y)$. Then we have \[\begin{align} \grad_y\log p_{s}(y) = \frac{\grad_y p_{s}(y)}{p_{s}(y)} &=\frac{\int_{\bb R^d} q_s(x,y)\cdot (x-y/s) \d x}{\int_{\bb R^d} q_s(x,y)\d x}\\ \mr{p_{X|X_s}(x|y) = \frac{q_s(x,y)}{\int_{\bb R^d} q_s(x,y)\d x}} &= \E[p_{X|X_s}(\cdot\,|\,y)]{X-y/s}. \end{align}\] ◻

Proof of Lemma 4. In this proof we may also abbreviate $p_{X_s}$ as $p_s$. It follows from Lemma 3 that $\grad_y \log p_s(y) = \E[p_{X|X_s}(\cdot\,|\,y)]{X} - y/s$. Let $Z_s(y)\defeq \int_{\bb R^d}q_s(x,y)\d x$, we have \[\begin{align} \grad_y^2 \log p_s(y) &= \grad_y \tp{Z_s(y)^{-1}\int_{\bb R^d} x\cdot q_s(x,y) \d x - y/s}\notag\\ &=\int_{\bb R^d}x\cdot \grad_y\tp{\frac{q_s(x,y)}{Z_s(y)} }^\top\d x - \frac{\!{Id}_d}{s}.\label{eq:hessian} \end{align}\tag{22}\] Direct calculations show that \[\begin{align} \grad_y\tp{\frac{q_s(x,y)}{Z_s(y)}} &= \frac{1}{Z_s(y)}\cdot \grad_y q_s(x,y) - \frac{q_s(x,y)}{Z_s(y)^2}\cdot \grad_y Z_s(y)\\ \mr{\grad_y q_s(x,y) = q_s(x,y) (x-y/s)} &=\frac{q_s(x,y)}{Z_s(y)}\cdot \tp{x-y/s-\frac{\grad_y Z_s(y)}{Z_s(y)}}\\ \mr{\frac{\grad_y Z_s(y)}{Z_s(y)} = \E[p_{X|X_s=y}(\cdot|y)]{X}-y/s} &= \frac{q_s(x,y)}{Z_s(y)}\cdot \tp{x - \E[p_{X|X_s}(\cdot|y)]{X}}. \end{align}\] Plugging this into 22 , we immediately have \[\grad_y^2\log p_s(y) = \cov{p_{X|X_s}(\cdot|y)} - \frac{\!{Id}_d}{s}.\] ◻

9.3 The proofs in 4 ↩︎

Before proving Lemma 7, we first prove the convergence of the OU process in Proposition [prop:OUconvergence], which is a commonly known result (see, e.g., [6], [17], [30]).

Suppose $\mu$ satisfies Assumption 1 and 2. Then \[\!{KL}\tp{\xi^{\!{OU}}_t\,\|\,\+N(0,\!{Id}_d)} \leq e^{-2t}\cdot (Ld+M).\]

Proof of Proposition [prop:OUconvergence]. Without loss of generality, we assume $\int e^{-V(x)}dx = 1$ for brevity in the following proof. From Lemma 21, \[\begin{align} \!{KL}\tp{\mu\,\|\,\+N\tp{0, \!{Id}_d}} & \le \frac{1}{2} \int e^{-V(x)} \cdot \norm{\grad \log \frac{e^{-V(x)}}{\frac{1}{(2\pi)^{d/2}} e^{-\frac{\norm{x}^2}{2}}}}^2 dx \\ &=\frac{1}{2} \int e^{-V(x)} \cdot \norm{\grad V(x) +x }^2 dx \\ &\le \int e^{-V(x)} \norm{\grad V(x)}^2 dx + \int e^{-V(x)} \norm{x}^2 dx \end{align}\] For a matrix $A\in \bb R^{d\times d}$, let $\text{Tr}(A)$ denote its trace. Then for the first term, \[\begin{align} \int e^{-V(x)} \norm{\grad V(x)}^2 dx &= \int e^{-V(x)}\cdot \grad\cdot \grad V(x) dx \\ &= \int e^{-V(x)} \Delta V(x) dx \\ &=\int e^{-V(x)} \cdot \text{Tr}(\grad^2 V(x)) dx \\ \mr{\Cref{assump:smooth}}&\le Ld \end{align}\] For the second term, $\int e^{-V(x)} \norm{x}^2 dx = \E[X \sim \mu]{\norm{x}^2} \le M$. Thus \[\!{KL}\tp{\mu\,\|\,\+N\tp{0, \!{Id}_d}} \le Ld + M.\]

According to the Fokker-Planck equation of the OU process, \[\partial_t \xi^{\!OU}_t(x) = \grad \cdot (\xi^{\!OU}_t(x) x ) + \Delta \xi^{\!OU}_t(x) = \grad \cdot \left (\xi^{\!OU}_t(x) \grad \log{\frac{\xi^{\!OU}_t(x)}{\frac{1}{(2\pi)^{d/2}}\exp \set{-\frac{1}{2}\norm{x}^2}}}\right). \label{eq:OU-1}\tag{23}\] Therefore \[\require{physics} \begin{align} \frac{\dd}{\dd t} \!{KL}\tp{\xi_{t}^{\!OU}\,\|\,\+N\tp{0, \!{Id}_d}} &= \frac{\dd}{\dd t} \int \xi^{\!OU}_t(x) \log{\frac{ \xi^{\!OU}_t(x)}{\frac{1}{(2\pi)^{d/2}} \exp\set{-\frac{1}{2}\norm{x}^2}}} dx\\ &= \int \partial_t \left( \xi^{\!OU}_t(x) \log{\frac{ \xi^{\!OU}_t(x)}{\frac{1}{(2\pi)^{d/2}} \exp \set{-\frac{1}{2}\norm{x}^2}}}\right)dx \\ &= \int \partial_t \xi^{\!OU}_t(x)\cdot \log{\frac{ \xi^{\!OU}_t(x)}{\frac{1}{(2\pi)^{d/2}} \exp \set{-\frac{1}{2}\norm{x}^2}}} dx + \int \partial_t \xi^{\!OU}_t(x) \dd x\\ \mr{\Cref{eq:OU-1}}&= \int \left( \grad \cdot \left ( \xi^{\!OU}_t(x) \grad \log{\frac{ \xi^{\!OU}_t(x)}{\frac{1}{(2\pi)^{d/2}}\exp \set{-\frac{1}{2}\norm{x}^2}}}\right) \right)\cdot \log{\frac{ \xi^{\!OU}_t(x)}{\frac{1}{(2\pi)^{d/2}} \exp\set{-\frac{1}{2}\norm{x}^2}}} dx \\ \mr{integration by parts} &= - \int \xi^{\!OU}_t(x) \cdot \norm{\grad \log \frac{ \xi^{\!OU}_t(x)}{\frac{1}{(2\pi)^{d/2}} \exp\set{-\frac{1}{2}\norm{x}^2}}}^2 dx \\ \mr{Lemma~\ref{lem:sobolev}} &\le -2 \!{KL}\tp{\xi_{t}^{\!OU}\,\|\,\+N\tp{0, \!{Id}_d}}, \end{align}\] and consequently, \[\require{physics} \frac{\dd }{\dd t} \log{\!{KL}\tp{\xi_{t}^{\!OU}\,\|\,\+N\tp{0, \!{Id}_d}}} \le -2.\] Integrating the two sides of the above equation from $0$ to $t$, we get the result directly. ◻

Then Lemma 7 is a corollary of Proposition [prop:OUconvergence].

Proof of Lemma 7. From Lemma 1, $\xi_{s_0}(x) = \tp{s_0(1+s_0)}^{-\frac{d}{2}}\cdot \xi^{\!{OU}}_{t_0}(y)$ for $t_0=\log\sqrt{\frac{1+s_0}{s_0}}= \frac{1}{2}\log\frac{2(Ld+M)}{\eps^2}$ and $y= \frac{1}{\sqrt{s_0(1+s_0)}}x$. By definition, \[\require{physics} \begin{align} \!{KL}\tp{\xi_{s_0}\,\|\,\+N\tp{0, s_0(1+s_0)\!{Id}_d}} &= \int_{\bb R^d} \xi_{s_0}(x) \cdot \log\tp{\frac{\xi_{s_0}(x)}{\tp{2\pi\cdot s_0(1+s_0)}^{-\frac{d}{2}} \cdot e^{-\frac{\|x\|^2}{2s_0(1+s_0)}}}} \dd x \\ \mr{ y= \frac{1}{\sqrt{s_0(1+s_0)}}x }&= \int_{\bb R^d} \xi^{\!{OU}}_{t_0}(y)\cdot \log \frac{\xi^{\!{OU}}_{t_0}(y)}{\tp{2\pi}^{-\frac{d}{2}} \cdot e^{-\frac{\|y\|^2}{2}}}\dd y \\ &= \!{KL}\tp{\xi^{\!{OU}}_{t_0}\,\|\,\+N\tp{0, \!{Id}_d}}\\ \mr{Proposition~\ref{prop:OUconvergence}}&\leq \frac{\eps^2}{2}. \end{align}\] The result then follows from the Pinsker’s inequality. ◻

9.4 The proofs in 5 ↩︎

Proof of Lemma 8. We slightly abuse the notation by letting $\xi'_s(\cdot\,|\, y)$ be the distribution of $Z(s)$ in 8 given $X_{s_0}=y$. We first prove that for any $w\in \bb R^d$, $\require{physics} \xi_{T}(w) = \int_{\bb R^d} \xi_{s}(y)\cdot \xi'_{T-s}(w-y\,|\,y) \dd y$. By the definition of $\xi'_{T-s}$, \[\require{physics} \begin{align} &\phantom{{}={}}\int_{\bb R^d} \xi_{s}(y)\cdot \xi'_{T-s}(w-y\,|\,y) \dd y \notag \\ &= \int_{\bb R^d} \xi_{s}(y)\cdot \int_{\bb R^d} \nu_s(x\,|\,y) \cdot \frac{\exp\set{-\frac{\norm{w-y-(T-s)x}^2}{2(T-s)}}}{\tp{2\pi (T-s)}^{\frac{d}{2}}} \dd x\dd y \notag \\ &=\int_{\bb R^{d}\times \bb R^{d}} \mu(x)\cdot \frac{\exp\set{-\frac{\norm{y-sx}^2}{2s}}}{(2\pi s)^{\frac{d}{2}}}\cdot \frac{\exp\set{-\frac{\norm{w-y-(T-s)x}^2}{2(T-s)}}}{\tp{2\pi (T-s)}^{\frac{d}{2}}} \dd x \dd y \notag \\ &=\int_{\bb R^{d}\times \bb R^{d}} \frac{\mu(x)}{\tp{2\pi s \cdot 2\pi (T-s)}^{\frac{d}{2}}} \cdot \exp\set{ \frac{s(T-s)}{2T}\cdot \norm{x+\frac{w-(T-s)x}{T-s}}^2 -\frac{s\|x\|^2}{2} - \frac{\norm{w-(T-s)x}^2}{2(T-s)} \right. \notag \\ &\qquad \qquad \qquad \qquad \left. - \frac{T}{2s(T-s)}\cdot \norm{y - \frac{s(T-s)\cdot\tp{x+\frac{w-(T-s)x}{T-s}}}{T}}^2} \dd x \dd y \notag \\ &= \int_{\bb R^{d}\times \bb R^{d}} \frac{\mu(x)}{\tp{2\pi T}^{\frac{d}{2}}} \cdot \exp\set{ \frac{s(T-s)}{2T}\cdot \norm{x+\frac{w-(T-s)x}{T-s}}^2 -\frac{s\|x\|^2}{2} - \frac{\norm{w-(T-s)x}^2}{2(T-s)}} \dd x \notag \\ & = \int_{\bb R^{d}\times \bb R^{d}} \frac{\mu(x)}{\tp{2\pi T}^{\frac{d}{2}}} \cdot \exp\set{-\frac{\|w-Tx\|^2}{2T}} \dd x \notag \\ &= \xi_{T}(w). \label{eq:beforeconcate-1} \end{align}\tag{24}\] Then from Lemma 6, \[\require{physics} \begin{align} \E[\xi_s]{\E[\xi'_{T-s}]{\Var[\nu'_{T-s}]{f}}} &= \int_{\bb R^d\times \bb R^d} \xi_s(y)\cdot \xi'_{T-s}(z\,|\,y)\cdot \Var[\nu_{T}( \cdot\,|\,y+z)]{f} \dd z \dd y\\ \mr{z=w-y} &= \int_{\bb R^d\times \bb R^d} \xi_s(y)\cdot \xi'_{T-s}(w-y\,|\,y)\cdot \Var[\nu_{T}( \cdot\,|\,w)]{f} \dd w \dd y \\ \mr{\Cref{eq:beforeconcate-1}}&= \int_{\bb R^d} \xi_T(w) \cdot \Var[\nu_{T}( \cdot\,|\,w)]{f} \dd w \\ &= \E[\xi_T]{\Var[\nu_T]{f}}. \end{align}\] The proof of the entropy case is similar. ◻

Proof of Lemma 12. Let $q_s(x,y) = \pi(x)\cdot e^{-f(x,y)}$. Then $\require{physics} \xi(y) \propto \int_{\bb R^d} q_s(x,y) \dd x$ and \[\require{physics} -\grad_y \log \xi(y) = \frac{\int_{\bb R^d}\grad_y f(x,y)\cdot q_s(x,y) \dd x}{\int_{\bb R^d} q_s(x,y) \dd x}.\] Therefore, \[\require{physics} \begin{align} -\grad^2_y \log \xi(y) &= \frac{\int_{\bb R^d}\tp{\grad^2_y f(x,y) - \grad_y f(x,y)^{\otimes 2}}\cdot q_s(x,y) \dd x}{\int_{\bb R^d} q_s(x,y) \dd x} \\ &\quad + \frac{\tp{\int_{\bb R^d}\grad_y f(x,y)\cdot q_s(x,y) \dd x}^{\otimes 2}}{\tp{\int_{\bb R^d} q_s(x,y) \dd x}^2}\\ &= \E[X\sim \nu_y]{\grad^2_y f(X,y) - \grad_y f(X,y)^{\otimes 2}} + \E[X\sim \nu_y]{\grad_y f(X,y)}^{\otimes 2}\\ &= \E[X\sim \nu_y]{\grad^2_y f(X,y)} - \Cov[X\sim \nu_y]{\grad_y f(X,y)}. \end{align}\] ◻

10 Technical lemmas↩︎

Lemma 21 (Lemma F.4 in [17]). Consider an $m$-strongly log-concave distribution $\pi$. For any distribution $\zeta$, we have \[\!{KL}\tp{\zeta\,\|\,\pi} \le \frac{1}{2m} \int \zeta(x) \norm{\grad \log{\frac{\zeta(x)}{\pi(x)}}}^2 dx\]

Lemma 22 (Concentration of Poisson distribution). Let $X\sim \!{Pois}(\lambda)$. Then for any $s>0$, $\Pr{X\geq \lambda +s}\leq e^{-\frac{s^2}{2(\lambda + s)}}$.

Proof. From the Markov’s inequality, for some fixed $\theta>0$ \[\Pr{X\geq \lambda +s} = \Pr{e^{\theta X}\geq e^{\theta(\lambda +s)}} \leq \E{e^{\theta X}} \cdot e^{-\theta(\lambda +s)}.\] It is a standard result that the moment generating function of $X$ is $\E{e^{\theta X}} = e^{\lambda\tp{e^{\theta}-1}}$. Choosing $\theta = \log \tp{1+\frac{s}{\lambda}}$, we have \[\Pr{X\geq \lambda +s}\leq e^{\lambda\tp{e^{\theta}-1} - \theta(\lambda +s)} = e^{s - (\lambda +s)\log \tp{1+\frac{s}{\lambda}}} = e^{-\frac{s^2}{2\lambda}\cdot 2\tp{\tp{\frac{1}{u^2} + \frac{1}{u}}\log (1+u) - \frac{1}{u}}},\] where $u=\frac{s}{\lambda}$. It remains to prove $2\tp{\tp{\frac{1}{u^2} + \frac{1}{u}}\log (1+u) - \frac{1}{u}} \geq \frac{1}{1+u}$. Let \[g(u) = 2(u+1)\cdot \tp{\tp{\frac{1}{u^2} + \frac{1}{u}}\log (1+u) - \frac{1}{u}}.\] Note that \[\begin{align} g(u) &= 2(u+1)\cdot \frac{(1+u)\cdot \log (1+u) - u}{u^2} \\ &= 2(u+1)\cdot \frac{(1+u)\cdot \tp{u - u^2/2 + o(u^2)} - u}{u^2}\\ &\overset{u\to 0}{\longrightarrow} 1, \end{align}\] and for any $u\in (0,\infty)$, \[\begin{align} g'(u) &= 2\tp{\tp{\frac{1}{u^2} + \frac{1}{u}}\log (1+u) - \frac{1}{u}} + 2(u+1)\cdot \tp{\tp{\frac{1}{u^2} + \frac{1}{u}}\cdot \frac{1}{u+1} - \tp{\frac{2}{u^3} + \frac{1}{u^2}}\cdot \log (1+u) + \frac{1}{u^2}}\\ &= 2\tp{ -\tp{\frac{2}{u^3} + \frac{2}{u^2}}\cdot \log (1+u) + \frac{2}{u^2} + \frac{1}{u}} \\ &= \frac{2}{u^3}\cdot \tp{2u+u^2 - 2(1+u)\log (1+u)}. \end{align}\] Let $h(u) = 2u+u^2 - 2(1+u)\log (1+u)$. We have $h(0)=0$ and $h'(u) = 2u - 2\log(1+u)\geq 0$. Therefore, $g'(u)>0$ for any $u>0$.

Therefore, we have $g(u)>1$ for all $u>0$ and \[\Pr{X\geq \lambda +s} \leq \exp\set{-\frac{s^2}{2\lambda}\cdot \frac{1}{1+\frac{s}{\lambda}}\cdot g(u)} \leq e^{-\frac{s^2}{2(\lambda + s)}}.\] ◻

Lemma 23 (The $\chi^2$ divergence between Gaussians). Consider two multi-variate Gaussian distribution $\mu_1=\+N(x,\sigma^2\cdot\!{Id}_d)$ and $\mu_2=\+N(y,\sigma^2\cdot\!{Id}_d)$. Then $\chi^2(\mu_1\,\|\,\mu_2) = e^{\frac{\|x-y\|^2}{\sigma^2}} -1$.

Proof. By the definition of $\chi^2$ divergence, we have \[\require{physics} \begin{align} \chi^2(\mu_1\,\|\,\mu_2) &= \int_{\bb R^d} \frac{\mu_1(z)^2}{\mu_2(z)} \dd z -1\\ &= \frac{1}{(2\pi\sigma^2)^{\frac{d}{2}}}\cdot \int_{\bb R^d} \exp\set{-\frac{\norm{z-x}^2}{\sigma^2} + \frac{\norm{z-y}^2}{2\sigma^2} } \dd z -1 \\ &= \frac{1}{(2\pi\sigma^2)^{\frac{d}{2}}}\cdot \int_{\bb R^d} \exp\set{- \frac{\norm{z-(2x-y)}^2}{2\sigma^2} - \frac{\|x\|^2}{\sigma^2} + \frac{\|y\|^2}{2\sigma^2} + \frac{\|2x-y\|^2}{2\sigma^2}} \dd z -1 \\ &= e^{\frac{\|x-y\|^2}{\sigma^2}} -1. \end{align}\] ◻

Lemma 24. For any $x,y\in \bb R^d$, \[\int \frac{\+N(z;x,\sigma^2\cdot\!{Id}_d)^4}{\+N(z;y,\sigma^2\cdot\!{Id}_d)^3}\d z=e^{\frac{6\|x-y\|^2}{\sigma^2}}.\]

Proof. We have \[\begin{align} \int \frac{\+N(z;x,\sigma^2\cdot\!{Id}_d)^4}{\+N(z;y,\sigma^2\cdot\!{Id}_d)^3}\d z &= \frac{1}{(2\pi\sigma^2)^{\frac{d}{2}}}\int_{\bb R^d} \exp\set{-\frac{2\|z-x\|^2}{\sigma^2}+\frac{3\|z-y\|^2}{2\sigma^2}}\d z\\ &= \frac{1}{(2\pi\sigma^2)^{\frac{d}{2}}}\int_{\bb R^d} \exp\set{-\frac{\|z-(4x-3y)\|^2}{2\sigma^2}+\frac{6\|x-y\|^2}{\sigma^2}}\d z\\ &= e^{\frac{6\|x-y\|^2}{\sigma^2}}. \end{align}\] ◻

References↩︎

[1]

S. Chewi, Available at https://chewisinho.github.io/main.pdf“Log-concave sampling,” 2025.

[2]

X. Cheng and P. Bartlett, “Convergence of Langevin MCMC in KL-divergence,” in Proceedings of algorithmic learning theory, 2018, vol. 83, pp. 186–211.

[3]

R. Shen and Y. T. Lee, “The randomized midpoint method for log-concave sampling,” in Advances in neural information processing systems, 2019, vol. 32, pp. 2098–2109.

[4]

S. Zhang, S. Chewi, M. Li, K. Balasubramanian, and M. A. Erdogdu, “Improved discretization analysis for underdamped Langevin Monte Carlo,” in The thirty sixth annual conference on learning theory, 2023, vol. 195, pp. 36–71.

[5]

Y. Chen, S. Chewi, A. Salim, and A. Wibisono, “Improved analysis for a proximal algorithm for sampling,” in The thirty fifth annual conference on learning theory, 2022, pp. 2984–3014.

[6]

S. Vempala and A. Wibisono, “Rapid convergence of the unadjusted Langevin algorithm: Isoperimetry suffices,” Advances in Neural Information Processing Systems, vol. 32, 2019.

[7]

A. Mousavi-Hosseini, T. K. Farghly, Y. He, K. Balasubramanian, and M. A. Erdogdu, “Towards a complete analysis of Langevin Monte Carlo: Beyond Poincaré inequality,” in The thirty sixth annual conference on learning theory, 2023, vol. 195, pp. 1–35.

[8]

S. Chewi, M. A. Erdogdu, M. Li, R. Shen, and M. S. Zhang, “Analysis of Langevin Monte Carlo from Poincaré to log-Sobolev,” Foundations of Computational Mathematics, pp. 1–51, 2024.

[9]

H. Lee, A. Risteski, and R. Ge, “Beyond log-concavity: Provable guarantees for sampling multi-modal distributions using simulated tempering Langevin Monte Carlo,” in Advances in neural information processing systems, 2018, vol. 31.

[10]

Y. He and C. Zhang, “On the query complexity of sampling from non-log-concave distributions (extended abstract),” in The thirty eighth annual conference on learning theory, 30-4 july 2025, lyon, france, 2025, pp. 2786–2787.

[11]

W. Guo, M. Tao, and Y. Chen, “Provable benefit of annealed Langevin Monte Carlo for non-log-concave sampling,” in The thirteenth international conference on learning representations, 2025.

[12]

S. Chen, S. Chewi, J. Li, Y. Li, A. Salim, and A. R. Zhang, “Sampling is as easy as learning the score: Theory for diffusion models with minimal data assumptions,” in The eleventh international conference on learning representations, 2023.

[13]

S. Chen, S. Chewi, H. Lee, Y. Li, J. Lu, and A. Salim, “The probability flow ODE is provably fast,” in Advances in neural information processing systems, 2023, vol. 36, pp. 68552–68575.

[14]

H. Chen, H. Lee, and J. Lu, “Improved analysis of score-based generative modeling: User-friendly bounds under minimal smoothness assumptions,” in International conference on machine learning, 2023, pp. 4735–4763.

[15]

S. Gupta, L. Cai, and S. Chen, “Faster diffusion-based sampling with randomized midpoints: Sequential and parallel,” CoRR, vol. abs/2406.00924, 2024.

[16]

X. Huang, H. Dong, Y. HAO, Y. Ma, and T. Zhang, “Reverse diffusion Monte Carlo,” in The twelfth international conference on learning representations, 2024.

[17]

X. Huang, D. Zou, H. Dong, Y.-A. Ma, and T. Zhang, “Faster sampling without isoperimetry via diffusion-based Monte Carlo,” in The thirty seventh annual conference on learning theory, 2024, pp. 2438–2493.

[18]

Y. He, K. Rojas, and M. Tao, “Zeroth-order sampling methods for non-log-concave distributions: Alleviating metastability by denoising diffusion,” in Advances in neural information processing systems, 2024, vol. 37, pp. 71122–71161.

[19]

H. Lee, J. Lu, and Y. Tan, “Convergence of score-based generative modeling for general data distributions,” in Proceedings of algorithmic learning theory, 2023, vol. 201, pp. 946–985.

[20]

S. Chen, G. Daras, and A. Dimakis, “Restoration-degradation beyond linear diffusions: A non-asymptotic analysis for DDIM-type samplers,” in International conference on machine learning, 2023, pp. 4462–4484.

[21]

J. Benton, V. D. Bortoli, A. Doucet, and G. Deligiannidis, “Nearly $d$-linear convergence bounds for diffusion models via stochastic localization,” in The twelfth international conference on learning representations, 2024.

[22]

Y. T. Lee, R. Shen, and K. Tian, “Structured logconcave sampling with a restricted Gaussian oracle,” in The thirty fourth annual conference on learning theory, 2021, pp. 2993–3050.

[23]

J. Liang and Y. Chen, “A proximal algorithm for sampling,” Transactions on Machine Learning Research, 2023.

[24]

S. Mitra and A. Wibisono, “Fast convergence of $\Phi$-divergence along the unadjusted Langevin algorithm and proximal sampler,” in Proceedings of algorithmic learning theory, 2025.

[25]

R. Eldan, “Analysis of high-dimensional distributions using pathwise methods,” in Proc. Int. Cong. math, 2022, vol. 6, pp. 4246–4270.

[26]

Y. Chen and R. Eldan, “Localization schemes: A framework for proving mixing bounds for Markov chains,” Duke Mathematical Journal, vol. 174, no. 8, pp. 1431–1510, 2025.

[27]

X. Chen, Z. Chen, Y. Yin, and X. Zhang, “Rapid mixing at the uniqueness threshold,” in Proceedings of the 57th annual ACM symposium on theory of computing, 2025, pp. 879–890.

[28]

R. Van Handel, Available at https://web.math.princeton.edu/~rvan/APC550.pdf“Probability in high dimension,” 2016.

[29]

D. Mikulincer and Y. Shenfeld, “On the lipschitz properties of transportation along heat flows,” in Geometric aspects of functional analysis: Israel seminar (GAFA) 2020-2022, 2023, pp. 269–290.

[30]

D. Bakry, I. Gentil, and M. Ledoux, Analysis and geometry of markov diffusion operators, vol. 348. Springer, 2014.

[31]

Z. Chen and T. Jiang, “Improved mixing of critical hardcore model,” To appear in RANDOM 2025, available at arXiv preprint arXiv:2502.07515, 2025.

[32]

B. Efron, “Tweedie’s formula and selection bias,” Journal of the American Statistical Association, vol. 106, no. 496, pp. 1602–1614, 2011.

[33]

Y.-H. Kim and E. Milman, “A generalization of caffarelli’s contraction theorem via (reverse) heat flow,” Mathematische Annalen, vol. 354, no. 3, pp. 827–862, 2012.

[34]

H.-B. Chen, S. Chewi, and J. Niles-Weed, “Dimension-free log-sobolev inequalities for mixture distributions,” Journal of Functional Analysis, vol. 281, no. 11, p. 109236, 2021.

[35]

H. Lee, C. Pabbaraju, A. P. Sevekari, and A. Risteski, “Universal approximation using well-conditioned normalizing flows,” Advances in Neural Information Processing Systems, vol. 34, pp. 12700–12711, 2021.

[36]

D. A. Levin and Y. Peres, Markov chains and mixing times, vol. 107. American Mathematical Soc., 2017.

[37]

A. El Alaoui and A. Montanari, “An information-theoretic view of stochastic localization,” IEEE Transactions on Information Theory, vol. 68, no. 11, pp. 7423–7426, 2022.

Here the notation $\wt{\+O}$ subsumes some negligible logarithmic terms with regard to $\ol L,d,M, \eps^{-1}$ and the locations of particles appearing in the implementation of RGO. Further discussion on the dependence of the particles in RGO can be found in 8 and the discussions in Appendix A of [22].↩︎
For the sake of brevity, we only illustrate the proof strategy for the inequality in 2 in this section. The modified log-Sobolev inequality can be derived via a parallel framework. See 5 for details.↩︎
The notation $\wt{\+O}$ subsumes a logarithmic term with regard to $L,d$ and $x^*_y = \arg\min_{x\in \bb R^d} V_y^{\sigma}(x)$, which is generated due to the call of 4.↩︎

Improved sampling algorithms and functional inequalities for non-log-concave distributions