Keywords: diffusion models; linear inverse problems; DDIM; posterior sampling

1 Introduction↩︎

Diffusion models [1]–[4] have emerged as one of the most successful paradigms for modern generative modeling, achieving remarkable performance across a wide range of domains, from image synthesis, video generation, to scientific data generation. Beyond sample generation, their ability to capture complex, high-dimensional data distributions makes them particularly well-suited as flexible, expressive, and fully data-driven priors over the signals of interest, offering a versatile framework for Bayesian inference in inverse problems [5]–[11].

1.1 Motivation: inverse problems with diffusion priors↩︎

In an inverse problem, one is asked to infer an unknown random signal \(X_0\in \mathbb{R}^d\) from noisy observations \[\begin{align} Y= \mathcal{A}(X_0)+\varepsilon, \end{align}\] where \(\mathcal{A}: \mathbb{R}^d\to \mathbb{R}^n\) is a known measurement operator, and \(\varepsilon\in \mathbb{R}^n\) represents the measurement noise. Such problems are often ill-posed: even in the absence of noise, the observations \(y\) alone may be insufficient to uniquely determine the underlying signal \(X_0\), particularly when \(n<d\). A principled approach to resolving this ambiguity and improving statistical performance is provided by Bayesian inference, which combines the measurement model with a prior distribution over the unknown signal \(X_0\). Specifically, given a prior \(p_{X_0}\), the central objective of Bayesian inference is to characterize, or sample from, the posterior distribution \(p_{X_0\mid y}\).

The effectiveness of Bayesian inference therefore depends largely on the choice of prior. Classical approaches typically impose hand-crafted priors, such as sparsity or low-rank structure [12]–[23]. While these priors have led to many important advances, they often oversimplify the structure of natural signals. Diffusion models offer a fundamentally different alternative: rather than manually specifying a prior or regularizer, they use a pre-trained generative model as an implicit prior over the signal distribution. This perspective has inspired a rapidly growing line of work on posterior sampling for inverse problems with diffusion priors [5], [7]–[9], [24]–[26]. Moreover, because pre-trained diffusion models can be used as “plug-and-play” priors [24], [27]–[29], they often require no task-specific retraining and readily transfer across sensing modalities and application domains.

Using diffusion models as priors, however, presents a new suite of algorithmic challenges. Rather than assuming access to an explicit, closed-form expression for the prior distribution, the diffusion-prior framework models the prior implicitly through a pre-trained diffusion model that provides score estimates (i.e., estimates of the Stein score functions) for progressively diffused versions of the prior. A central algorithmic challenge is therefore to combine the learned diffusion prior with the measurement model 1 in order to generate samples from the posterior distribution. Existing diffusion-based methods typically address this through heuristic correction steps, projection operators, likelihood-gradient guidance, approximate posterior updates, and so on [6], [8], [30], [31]. Although these methods have demonstrated strong empirical performance, many lack rigorous guarantees that the generated samples converge to the true Bayesian posterior. Furthermore, some require computationally intensive modifications to the underlying sampling procedure. For example, [7], [9] required computing the gradient of the score functions, while the sequential Monte Carlo approach of [32] may require a prohibitively large number of particles. These considerations can limit their practical applicability in settings where both computational efficiency and statistical reliability are important.

These issues highlight the need for diffusion-based inverse problem solvers that achieve rigorous theoretical guarantees and computational efficiency at once. Such properties are particularly important in high-stakes applications such as medical imaging and scientific discovery. At the same time, practical deployment often favors algorithms that preserve the simplicity and efficiency of standard diffusion samplers.

1.2 An overview of our contributions↩︎

In this paper, we make progress towards developing a theoretically principled, and computationally efficient framework for posterior sampling in linear inverse problems with diffusion priors. Specifically, we consider the following noisy linear measurement model: \[\begin{align} Y = A X_0 + \varepsilon, \label{eq:inverse} \end{align}\tag{1}\] where \(X_0\in\mathbb{R}^d\) is the unknown signal (generated randomly from a data distribution \(p_0\)), \(A:\mathbb{R}^d\to\mathbb{R}^n\) represents a linear measurement operator known a priori, and \(\varepsilon \sim \mathcal{N}(0,\sigma^2 I_n)\) stands for Gaussian measurement noise with \(\sigma>0\) the noise standard deviation. Throughout, we assume that the prior distribution of \(X_0\) can be represented implicitly by a pre-trained diffusion model. The objective is to generate samples from the posterior distribution of \(X_0\) conditioned on the observation \(y\).

Our starting point is the observation that, under a linear measurement model, different singular directions of the measurement operator carry different amounts of statistical information. Rather than treating all directions uniformly, we design a DDIM-type posterior sampler, called Posterior-DDIM, that adaptively determines, for each singular direction, whether the update should be based primarily on the learned diffusion prior or the observed data. This results in a simple, lightweight, coordinate-wise modification of the standard DDIM sampler that explicitly exploits the structure of the measurement operator, while preserving the efficiency of DDIM-type sampling. Along directions where the measurements have sufficient signal-to-noise ratio (SNR), the algorithm injects a carefully calibrated noisy version of the observations so that the resulting coordinates have the correct forward-diffusion marginal distribution. In contrast, directions that are either observed with low SNR or entirely unobserved continue to evolve according to the standard DDIM dynamics induced by the prior. Consequently, posterior sampling reduces to a sequence of simple, direction-wise DDIM updates that are both computationally efficient and easy to implement.

Theoretically, our main contribution is to establish posterior consistency of the proposed Posterior-DDIM sampler. Under an exact diffusion prior and a sufficiently fine time discretization, we prove that the sampler converges to the posterior distribution of the unknown signal conditioned on the measurements. This result provides rigorous theoretical support for DDIM-type samplers in linear inverse problems, and suggests a principled approach to integrating measurement information with diffusion priors in noisy, potentially ill-conditioned or rank-deficient settings.

Empirically, we evaluate the proposed sampler on a range of image restoration tasks, including inpainting, super-resolution, Gaussian deblurring, and compressed sensing, using PSNR, SSIM, LPIPS, and FID as evaluation metrics. Across these tasks, our Posterior-DDIM algorithm performs favorably against existing diffusion-based posterior samplers: it achieves the best performance on at least three of the four metrics in most tasks, and on at least two metrics in every task considered.

1.3 Related work↩︎

Despite their significant empirical success, existing diffusion-based inverse solvers still leave room for improvement. One prominent class of methods [3], [6], [8], [30], [31], [33] enforces measurement consistency by incorporating projection steps into unconditional diffusion sampling procedures. While these approaches have demonstrated strong empirical performance, they do not provide theoretical guarantees on the convergence or posterior correctness of the resulting sampling procedures. A second line of work [7], [9], [32], [34], [35] attempted to approximate the (intractable) posterior score and subsequently apply standard diffusion samplers for posterior sampling. Although empirically effective, it remains unclear whether the resulting sampler faithfully yields the true posterior distribution. In addition, [5] proposed ReSample, which promotes measurement consistency by repeatedly optimizing the clean image estimate at intermediate time steps and then re-noising it to continue the reserve diffusion process. Similarly, [36] proposed to iteratively optimize the clean image via gradient descent in the reverse diffusion process. A different perspective was introduced by [37], who formulated inverse problems with diffusion priors as a variational inference problem via direct KL minimization rather than reverse diffusion sampling. Like the aforementioned approaches, these methods currently lack rigorous theoretical guarantees. Another strand of work [32], [38]–[40] combined Sequential Monte Carlo (MC) methods [41] with (unconditional) scores to sample from the correct posterior; in particular, [32], [40] established convergence guarantees as the number of particles tends to infinity. However, these methods incur a prohibitive computational cost. In particular, [42] showed that polynomially many particles are in general insufficient for the above Sequential MC approaches to converge. More recently, [24] proposed an alternating framework that accommodates even nonlinear inverse problems by interleaving two samplers: a proximal consistency sampler based on the likelihood function of the forward model and a denoising diffusion sampler driven by the learned score function of the prior. They also established rigorous theoretical guarantees for the resulting algorithm. In contrast, our proposed method is built almost entirely upon DDIM-type sampling.

Finally, we note that the convergence theory of DDPM-type samplers has been studied extensively in recent years (see, e.g., [43]–[51]), validating the efficacy of DDIM-type sampling and paving the way for more refined theoretical analyses in future work.

2 Preliminaries↩︎

In this section, we briefly review the background on diffusion models and their connections to inverse problems, which will be useful throughout the paper.

2.0.0.1 Diffusion models.

We begin by reviewing the basics of diffusion models. Let \(X_0\sim p_0\) denote a random sample in \(\mathbb{R}^d\) drawn from an underlying data distribution \(p_0\). A diffusion model defines a forward stochastic process \((X_t)_{t\in[0,T]}\) that progressively corrupts \(X_0\) by injecting Gaussian noise according to: \[\begin{align} X_t \overset{\mathrm{d}}{=}\alpha_t X_0 + \sigma_t Z_t, \qquad Z_t\sim \mathcal{N}(0,I_d) \label{eq:forward-process} \end{align}\tag{2}\] for all \(0\leq t\leq T\), where the coefficients \(\alpha_t\geq 0\) and \(\sigma_t\geq 0\) specify the noise schedule. Throughout this paper, we assume that the SNR \(\alpha_t/\sigma_t\) decreasing monotonically and continuously as \(t\) grows, and satisfies \(\alpha_0/\sigma_0 = \infty\) and \(\alpha_\infty/\sigma_\infty = 0\). As \(t\) increases, the signal component gradually diminishes while the noise level increases, so that, under an appropriate noise schedule, the distribution of \(X_t\) transitions smoothly from the data distribution toward an approximately Gaussian distribution. A central goal of a diffusion model is to learn the corresponding reverse process, which starts from a Gaussian sample and progressively removes the injected noise to yield a sample from the data distribution of interest.

2.0.0.2 Score functions.

A fundamental object governing the reverse process is the (Stein) score function \[\begin{align} s_t(x) \mathrel{\vcenter{:}}= \nabla\log p_{X_t}(x), \qquad 0\leq t\leq T, \label{eq:defn-stein-score-function} \end{align} where \(p_{X_t}\) denotes the marginal distribution of \(X_t\). The score function specifies the direction in which the log-density of \(X_t\) increases most rapidly and plays a central role in reversing the forward process \cite{anderson1982reverse,haussmann1986time}. In practice, the score functions are often parameterized through through equivalent prediction targets, such as the \emph{noise predictor} \begin{aligned} \epsilon_t(x) \mathrel{\vcenter{:}}= \mathbb{E}[Z_t \mid X_t=x] \end{aligned} and the {\em data predictor} \begin{align} \mu_t(x) \mathrel{\vcenter{:}}= \mathbb{E}[X_0\mid X_t=x]. \end{align}\tag{3}\] These objects are linked through Tweedie’s formula [52], which yields the identities \[\begin{align} \epsilon_t(x) = -\sigma_t s_t(x) \qquad \text{and} \qquad \mu_t(x) &= \frac{x-\sigma_t\epsilon_t(x)}{\alpha_t}. \label{eq:data-noise-predictor-relation} \end{align}\tag{4}\]

2.0.0.3 Reparameterzed reverse process and DDIM-type sampler.

The forward diffusion process 2 admits a reverse-time stochastic differential equation (SDE), originally characterized by [53], which forms the basis for diffusion-based generative sampling. It is sometimes convenient to reparameterize time \(t\) using the following parameter concerning the log SNR: \[\begin{align} \lambda_t \mathrel{\vcenter{:}}= \log \frac{\alpha_t}{\sigma_t}. \label{eq:connection-lambda-t} \end{align}\tag{5}\] Under this parameterization, the reverse SDE admits the following simple form using the \(\lambda\)-variable (i.e., the log SNR variable) as the “time variable” in place of \(t\): \[\begin{align} \mathrm d \bigg( \frac{X}{\alpha} \bigg) = -2 e^{-\lambda} \epsilon_{\lambda}(X)\,\mathrm d\lambda + \sqrt{2}e^{-\lambda}\,\mathrm d B_{\lambda}, \label{eq:reverse-sde} \end{align}\tag{6}\] where \(B_\lambda\) denotes a standard Brownian motion indexed by \(\lambda\), and we abuse the notation by letting \(\epsilon_{\lambda}\) be a shorthand for \(\epsilon_t\) with \(\lambda = \lambda_t\).

Practical sampling procedures like DDPM-type samplers [2] can be obtained by approximating this reverse SDE 6 through suitable time discretization. More precisely, for a sequence of decreasing time points \[t_0 > t_1 > \cdots > t_M\] with corresponding log SNR values \(\lambda_{t_0},\cdots,\lambda_{t_M}\) (cf. 5 ), a first-order discretization yields the DDPM-type update \[\begin{align} \frac{X_{t_{i+1}}}{\alpha_{t_{i+1}}} &= \frac{X_{t_i}}{\alpha_{t_i}} - 2\big( e^{-\lambda_{t_i}} - e^{-\lambda_{t_{i+1}}} \big) \epsilon_{t_i}(X_{t_i}) + \sqrt{ e^{-2\lambda_{t_i}} - e^{-2\lambda_{t_{i+1}}} }\,Z_{t_i}, \label{eq:ddpm-noise-predictor} \end{align}\tag{7}\] where \(z_{t_i} \overset{\mathrm{i.i.d.}}{\sim}\mathcal{N}(0,I)\). In light of the relation 4 between the noise predictor and the data predictor, the same update can be equivalently expressed in terms of \(\mu_t\). Letting \[\begin{align} \delta_{i+1} \mathrel{\vcenter{:}}= \lambda_{t_i}-\lambda_{t_{i+1}} \label{eq:defn-delta-i} \end{align}\tag{8}\] with \(\lambda_t\) defined in 6 , one obtains the first-order SDE-DPMSolver-1 update [54] \[\begin{align} \frac{X_{t_{i+1}}}{\sigma_{t_{i+1}}} &= e^{-\delta_{i+1}} \frac{X_{t_i}}{\sigma_{t_i}} + e^{\lambda_{t_{i+1}}} \left( 1-e^{-2\delta_{i+1}} \right) \mu_{t_i}(X_{t_i}) + \sqrt{ 1-e^{-2\delta_{i+1}} }\,Z_{t_i}. \label{eq:sde-dpm-solver-1} \end{align}\tag{9}\]

More generally, DDIM-type samplers [55] interpolate between deterministic and stochastic reverse updates. For any given parameter \(0\le\eta\le1\), the (general) DDIM-type update can be written as \[\begin{align} \text{(DDIM)}:\quad \frac{X_{t_{i+1}}}{\sigma_{t_{i+1}}} &= \frac{X_{t_i}}{\sigma_{t_i}} \sqrt{ 1-\eta\big(1-e^{-2\delta_{i+1}}\big) } + e^{\lambda_{t_{i+1}}} \Big( 1 - e^{-\delta_{i+1}} \sqrt{ 1-\eta\big(1-e^{-2\delta_{i+1}}\big) } \Big) \mu_{t_i}(X_{t_i}) \notag\\ &\quad + \sqrt{ \eta\big(1-e^{-2\delta_{i+1}}\big) } \,Z_{t_i}. \label{eq:ddim} \end{align}\tag{10}\] Notably, \(\eta\) controls the stochasticity of the update: the choice \(\eta=0\) yields the deterministic DDIM-type update, while \(\eta=1\) recovers the stochastic SDE-DPMSolver-1 update in 9 .

2.0.0.4 Diffusion priors for inverse problems.

Next, we briefly describe how diffusion models are commonly used as priors for linear inverse problems. Given a pre-trained diffusion model representing the prior distribution of \(X_0\), the aim is to generate samples from the posterior distribution \(p_{X_0 \mid Y=y}\). In analogy with the unconditional case, consider the conditional data predictor \[\begin{align} \mu_{t,y}(x) \mathrel{\vcenter{:}}= \mathbb{E}[X_0\mid X_t=x,\, AX_0+\varepsilon=y]. \label{eq:conditional-data-predictor} \end{align}\tag{11}\] If this conditional predictor were available, then one could simply replace the unconditional predictor \(\mu_t\) by \(\mu_{t,y}\) in the DDIM-type sampler 10 , thereby directly obtaining samples from the posterior distribution \(p_{X_0\mid y}\). Consequently, a central challenge in diffusion-based inverse problems is to approximate the conditional predictor \(\mu_{t,y}\) using only the pre-trained unconditional predictor \(\mu_t\) together with the measurement \(y\).

Many existing methods are built upon this idea. Starting from the unconditional prediction \(\mu_t(x)\), they seek to compute a measurement-compatible data predictor \(\mu\) by balancing two competing objectives: remaining faithful to to the diffusion prior that yields the unconditional data predictor \(\mu_t(\cdot)\), while simultaneously enforcing consistency with the observed measurements. To approximate the conditional data predictor, existing approaches often rely on heuristic approximations. A common strategy is to combine the unconditional predictor \(\mu_t(\cdot)\) and the measurement \(Y\) in a simple — often linear — manner [5], [8], [56], while another is to use \(\mu_t(\cdot)\) directly as a proxy for the unknown signal \(X_0\) [7].

3 Main results↩︎

In this section, we develop a posterior-consistent DDIM-type sampler for noisy linear inverse problems, and establish its theoretical guarantees.

Before proceeding, we find it convenient to introduce notation associated with the singular value decomposition (SVD) of the measurement matrix \(A \in \mathbb{R}^{n\times d}\). Suppose that \(A\) has rank \(r\), and let \[A = U\Sigma V^\top = U_{\mathcal{S}}\Sigma_{\mathcal{S}}V_{\mathcal{S}}^\top \label{eq:A-svd}\tag{12}\] represent the full and compact singular value decompositions (SVDs) of \(A\), where \(U \in \mathbb{R}^{n\times n}\) and \(V \in \mathbb{R}^{d\times d}\) are orthonormal matrices, \(U_{\mathcal{S}} \in \mathbb{R}^{n\times r}\) and \(V_{\mathcal{S}} \in \mathbb{R}^{d\times r}\) consist of the left and right singular vectors associated with the nonzero singular values, and \(\Sigma \in \mathbb{R}^{n\times d}\) and \(\Sigma_{\mathcal{S}} \in \mathbb{R}^{r\times r}\) are the corresponding rectangular diagonal and diagonal matrices of singular values, respectively. We denote by \[\begin{align} \mathcal{S} \mathrel{\vcenter{:}}= \{s \in [\min\{n,d\}] : \Sigma_{ss} > 0\} \end{align}\] the indices of the nonzero singular values, and hence the notation \(U_{\mathcal{S}}, V_{\mathcal{S}}\) and \(\Sigma_{\mathcal{S}}\).We also write \[\begin{align} U_{\mathcal{S}} \mathrel{\vcenter{:}}=[u_s]_{s\in\mathcal{S}} \in \mathbb{R}^{n\times r}, \quad V_{\mathcal{S}} \mathrel{\vcenter{:}}=[v_s]_{s\in\mathcal{S}} \in \mathbb{R}^{d\times r}, \quad \text{and} \quad \Sigma_{\mathcal{S}} \mathrel{\vcenter{:}}=\mathsf{diag}([\Sigma_{ss}]_{s\in\mathcal{S}}) \in \mathbb{R}^{ r\times r}. \end{align}\]

3.1 Motivation: SNR-guided partition of singular directions↩︎

The SVD 12 of the measurement matrix \(A\) naturally decouples the inverse problem into a sequence of scalar inference problems along its singular directions. Indeed, expressing the measurement model \(Y = AX_0 + \varepsilon\) (i.e., 1 ) in the SVD basis yields \[\begin{align} \Sigma_{\mathcal{S}}^{-1}U_{\mathcal{S}}^{\top}Y = V_{\mathcal{S}}^{\top}X_0 + \varepsilon' \qquad \text{with } \varepsilon' \mathrel{\vcenter{:}}=\Sigma_{\mathcal{S}}^{-1}U_{\mathcal{S}}^{\top} \varepsilon \sim \mathcal{N}\big(0, \sigma^2\Sigma_{\mathcal{S}}^{-2}\big); \label{eq:obs-model} \end{align}\tag{13}\] or equivalently, for every \(s\in \mathcal{S}\), \[\begin{align} \Sigma_{ss}^{-1}u_{s}^{\top}Y = v_{s}^{\top}X_0 + \varepsilon_s' \qquad \text{with } \varepsilon_s' \sim \mathcal{N}\bigg(0, \frac{\sigma^2}{\Sigma_{ss}^2}\bigg). \label{eq:obs-model-ss} \end{align}\tag{14}\] Thus, after transforming into the singular-vector basis, the effective observation SNR along the \(s\)-th singular direction is naturally measured by \(\Sigma_{ss}/\sigma\). Meanwhile, projecting the forward diffusion process 2 along the same singular direction gives \[\begin{align} v_s^\top X_t = \alpha_t v_s^\top X_0 + \sigma_t Z_s\qquad \text{with } Z_s \sim \mathcal{N}(0,1), \end{align}\] whose SNR — which we often refer to as diffusion SNR — is given by \(\alpha_t/\sigma_t\). Consequently, the relative magnitudes of these two SNRs dictate whether the posterior update should rely primarily on the measurements or on the diffusion prior.

This comparison naturally leads to a partition of the singular directions. For each diffusion time \(t\), we partition the singular directions according to \[\begin{align} \mathcal{S}_t^{\mathsf{meas}}\mathrel{\vcenter{:}}=\{s\in \mathcal{S}:\alpha_{t}\sigma<\Sigma_{ss}\sigma_{t}\} \qquad \text{and} \qquad \mathcal{S}_t^{\mathsf{prior}}\mathrel{\vcenter{:}}=\mathcal{S}\setminus \mathcal{S}_t^{\mathsf{meas}}. \end{align}\] For each \(s \in \mathcal{S}\), we define the threshold time \(\tau_s \in \mathbb{R}_{\geq 0} \cup \{\infty\}\) such that \[\begin{align} \frac{\alpha_{\tau_s}}{\sigma_{\tau_s}} = \frac{\Sigma_{ss}}{\sigma}, \end{align}\] namely, the diffusion time at which the diffusion SNR matches the observation SNR along the \(s\)-th singular direction. When \(\alpha_t/\sigma_t\) is continuous and strictly decreasing in \(t\), with \(\alpha_0/\sigma_0 = \infty\) and \(\alpha_\infty/\sigma_\infty = 0\), the threshold \(\tau_s\) is well defined. It can be easily verified that \[s\in \mathcal{S}_t^{\mathsf{meas}} \qquad \Longleftrightarrow \qquad t \geq \tau_s. \label{eq:equiv-taus-St}\tag{15}\]

Therefore, at each diffusion time \(t\), it is natural to partition the singular directions into three groups:

• Measurement-dominated directions: \(s\in \mathcal{S}_t^{\mathsf{meas}}\), or equivalently, directions obeying \(t \geq \tau_s\);

• Prior-dominated observed directions: \(s\in \mathcal{S}_t^{\mathsf{prior}}\), or equivalently, directions in \(\mathcal{S}\) obeying \(t < \tau_s\);

• Unobserved directions: \(s\in \mathcal{S}^{\mathrm{c}}\mathrel{\vcenter{:}}= [d]\setminus \mathcal{S}\).

Our sampler treats these three groups differently. As we shall see, each case admits a simple DDIM-type update, resulting in an efficient posterior sampler that adapts to the SNR along each singular direction.

3.2 Algorithm: Posterior-DDIM↩︎

We now describe the proposed sampler, based on the partition of singular directions developed in Section 3.1. The central idea is to exploit the measurements whenever the corresponding observation SNR exceeds the diffusion SNR, and otherwise rely on the learned diffusion prior. This idea gives rise to distinct update rules for the three groups of singular directions, which we describe below. The complete algorithm of the proposed DDIM-based posterior sampler, hereafter referred to as Posterior-DDIM, is summarized in Algorithm [alg:main].

3.2.0.1 Measurement-dominated directions.

For directions \(s\in \mathcal{S}_t^{\mathsf{meas}}\), the measurements are sufficiently informative to be used directly. To this end, consider the auxiliary forward process \[\begin{align} \xi_{t,s} \mathrel{\vcenter{:}}=\alpha_{t} \xi_{0,s} + \sqrt{\sigma_{t}^2 - \alpha_{t}^2\sigma^2\Sigma_{ss}^{-2}} Z_s, \quad Z_s \sim \mathcal{N}(0,1),\label{eq:def-xhat-t} \end{align}\tag{16}\] where \(\xi_{0,s}\) is taken to be \[\begin{align} \label{eq:def-sigmahat-alphahat} \xi_{0,s} \mathrel{\vcenter{:}}=\Sigma_{ss}^{-1}u_s^{\top}Y. \end{align}\tag{17}\] By construction, this auxiliary forward process \(\xi_{t,s}\) has the same marginal distribution as the forward diffusion process \(X_t\) (cf. 2 ) projected onto the direction the \(s\)-th singular direction \(v_s\), namely, \[\begin{align} \xi_{t,s} \overset{\mathrm{d}}{=}v_{s}^\top X_t = v_{s}^\top (\alpha_{t} X_0 + \sigma_{t} Z). \end{align}\] Consequently, sampling \(v_{s}^{\top}\widehat{X}_{t_i}\) at the time point \(t_i\) can be accomplished by generating \[\begin{align} v_{s}^{\top}\widehat{X}_{t_i} & = \alpha_{t_i} \Sigma_{ss}^{-1}u_s^{\top}Y + \sqrt{\sigma_{t_i}^2 - \alpha_{t_i}^2\sigma^2\Sigma_{ss}^{-2}} Z_{t_i} \quad\text{with } Z_{t_i} \sim \mathcal{N}(0,1), \label{eq:DDIM-St} \end{align}\tag{18}\] provided that \(s\in \mathcal{S}_{t_i}^{\mathsf{meas}}\). A formal proof is given in Appendix 7.1.

3.2.0.2 Prior-dominated observed directions.

For directions \(s\in \mathcal{S}_t^{\mathsf{prior}}\), the measurements are less informative than the diffusion prior. Consequently, rather than directly incorporating the observations, we update these directions using the standard DDIM sampler driven primarily by the learned data predictor.

We begin with the special case in which all nonzero singular values of \(A\) are identical. In this setting, for \(s\in\mathcal{S}_{t_{i+1}}^{\mathsf{prior}}\), we update \(v_s^\top \widehat X_{t}\) according to the standard DDIM-type update rule (cf. 19 ) as follows \[\begin{align} \frac{v_s^\top \widehat X_{t_{i+1}}}{\sigma_{t_{i+1}}} &=\frac{v_s^\top \widehat X_{t_i}}{\sigma_{t_i}}\sqrt{1-\eta(1-e^{-2\delta_{i+1}})} +e^{\lambda_{t_{i+1}}} \left(1-e^{-\delta_{i+1}}\sqrt{1-\eta(1-e^{-2\delta_{i+1}})}\right)v_s^\top \mu_{t_i}(\widehat X_{t_i})\notag\\ &\quad+ \sqrt{\eta(1-e^{-2\delta_{i+1}})} \,v_s^\top Z_{t_{i+1}}, \qquad Z_{t_{i+1}}\sim\mathcal{N}(0,I_d), \label{eq:ddim-prior-dominated} \end{align}\tag{19}\] where the stochasticity parameter is set to \(\eta=\eta_0\).

The above update extends naturally to the general setting where \(A\) has arbitrary nonzero singular values. The only modification is the addition of a correction term. Specifically, for \(s\in\mathcal{S}_{t_i}^{\mathsf{prior}}\), we replace 19 with \[\begin{align} \frac{v_s^\top \widehat{X}_{t_{i+1}}}{\sigma_{t_{i+1}}} &=\frac{v_s^\top \widehat{X}_{t_i}}{\sigma_{t_i}}\sqrt{1-\eta(1-e^{-2\delta_{i+1}})} +\sqrt{\eta(1-e^{-2\delta_{i+1}})} \,v_s^\top Z_{t_{i+1}}\notag\\ &\quad+e^{\lambda_{t_{i+1}}} \left(1-e^{-\delta_{i+1}}\sqrt{1-\eta(1-e^{-2\delta_{i+1}})}\right)v_s^\top \Bigg(\mu_{t_i}(\widehat{X}_{t_i}) + \underbrace{\frac{\alpha_{t_i}\widehat{X}_{\tau_s}-\alpha_{\tau_s}\widehat{X}_{t_i}}{\alpha_{\tau_s}\alpha_{t_i}({\rm e}^{2(\lambda_{t_i} - \lambda_{\tau_s})}-1)}}_{\text{correction term}}\Bigg), \label{eq:ddim-prior-dominated-extension} \end{align}\tag{20}\] where \(Z_{t_{i+1}}\sim\mathcal{N}(0,I_d)\). The derivation of this modified update rule is deferred to Appendix 8.

3.2.0.3 Unobserved directions.

For directions \(s\in\mathcal{S}^{\mathsf c}\), the measurements contain no information about \(v_s^\top X_0\). Accordingly, these coordinates should be sampled entirely from the learned diffusion prior, given the coordinates that are observed. As in the prior-dominated observed case, we employ the DDIM update 19 . However, we choose a larger stochasticity parameter \(\eta=\eta_1\) to encourage sufficient exploration of the unobserved subspace. This is important because the posterior uncertainty along \(\mathcal{S}^{\mathsf c}\) is determined entirely by the learned diffusion prior, rather than by the measurement model.

3.2.0.4 Choices of the stochasticity parameters \(\eta_0\) and \(\eta_1\).

We take a moment to discuss the roles of the two DDIM stochasticity parameters \(\eta_0\) and \(\eta_1\). Although both parameters control the amount of randomness injected into the DDIM update, they serve fundamentally different purposes because the target conditional distributions differ across the two subspaces. For directions \(s\in \mathcal{S}_t^{\mathsf{prior}}\), the corresponding coordinates are observed, although the measurements are not yet sufficiently informative to be imposed directly. The update should therefore approximate the conditional reverse transition given the current diffusion state and the measurements. This motivates using a relatively small value of \(\eta_0\), so as to keep the update closer to the deterministic DDIM sampler. In contrast, for directions \(s\in\mathcal{S}^{\mathsf c}\), no measurements are available. These coordinates must be sampled entirely from the learned conditional prior given the observed coordinates. A larger value of \(\eta_1\) makes the DDIM update more Langevin-like, thereby promoting exploration of the unobserved subspace

3.3 Theoretical guarantees: asymptotic posterior correctness↩︎

In this subsection, we establish the posterior correctness of the proposed Posterior-DDIM sampler. We begin with the special case in which all nonzero singular values of the measurement matrix \(A\) are identical, as this setting captures the main ideas while allowing for cleaner algorithm design analysis. Here and throughout, \(\mathsf{TV}(p,q)\) denotes the total-variation (TV) distance between two probability measures \(p\) and \(q\).

In words, Theorem 1 establishes that, under the assumption that all nonzero singular values of \(A\) are identical, the distribution of the output generated by Algorithm [alg:main] converges to the posterior distribution of \(X_0\) conditioned on the measurements. This guarantee is asymptotic and holds in the regime where (i) the terminal time \(t_M\) tends to \(0\), approaching the initial time of the forward diffusion process; (ii) the initial sampling time \(t_0\) is chosen such that \(\alpha_{t_0}\to0\) and \(\sigma_{t_0}\to 1\), ensuring that the SNR at the initialization stage vanishes; and (iii) the maximum gap between the log-SNRs of consecutive time points vanishes, which in particular requires the number of sampling steps \(M\) to tend to infinity. The proof is deferred to Appendix 6.

The restriction that all nonzero singular values of \(A\) are identical is not essential. The proposed approach extends naturally to the general setting with arbitrary nonzero singular values, requiring only a slight modification of the sampling procedure (as already described in 20 ). The corresponding theoretical guarantee is stated below. Compared to Theorem 1, the only additional change is a different choice of \(\eta_0\). The proof of this theorem is postponed to Appendix 8.

4 Experiments↩︎

In this section, we conduct extensive empirical evaluations of the proposed Posterior-DDIM algorithm on a diverse range of image restoration tasks, including inpainting, super-resolution, Gaussian deblurring, and compressed sensing.

We begin by describing the common experimental setup. Unless otherwise stated, the experiments are run with the NFE (number of function evaluations) set to 100, except for DPS, for which we follow [57] and set the NFE to be \(1000\). To justify our default choice, we also investigate the effect of NFE and find that the reconstruction quality largely saturates once the NFE exceeds 80 (see Figure 3). All experiments are conducted on a server equipped with NVIDIA A100-PCIE-40GB GPUs and Intel Xeon (Cascade Lake) CPUs.

4.1 Choices of \(\eta_0\) and \(\eta_1\)↩︎

We evaluate the influence of the hyperparameters \(\eta_0\) and \(\eta_1\) in Posterior-DDIM, which govern the DDIM updates on \(\mathcal{S}^{\mathrm{c}}\) and \(\mathcal{S}_t^{\mathsf{prior}}\), respectively. Experiments are conducted on two image restoration tasks: 50% random inpainting and \(4\times\) super-resolution with average pooling, using the CelebA [58] and ImageNet [59] datasets. We set the noise standard deviation to \(\sigma=0.05\) (doubled when pixels are rescaled to \([-1,1]\)). For ImageNet, we use the pretrained \(256 \times 256\) model without classifier guidance from [60]. For CelebA, we use the pretrained model released with SDEdit [61]. Following [57], [62], we evaluate on the 1K ImageNet sub-test set and the CelebA test set provided by [62]. Performance is measured using PSNR (peak SNR), SSIM [63], LPIPS [64], and FID [65]. For readability, all reported LPIPS values are multiplied by 100.

We vary \(\eta_1\) from \(0\) to \(32\) while fixing \(\eta_0=0\), and vary \(\eta_0\) from \(0\) to \(2\) while fixing \(\eta_1=16\). The results for inpainting and super-resolution are reported in Tables 1 and 2, respectively. For fixed \(\eta_0\), increasing \(\eta_1\) generally improves performance across most evaluation metrics, although the improvement is not strictly monotone and small fluctuations are observed. This overall trend is consistent with our theoretical analysis that requires \(\eta_1\) to be sufficiently large. Turning to the second set of experiments, where \(\eta_1\) is fixed and \(\eta_0\) is varied, we find that fine-tuning \(\eta_0\) can yield additional, albeit modest, performance gains. Empirically, the best empirical performance is attained at \(\eta_0=0\), which corresponds to the deterministic DDIM update.

4.2 Empirical comparisons with reference algorithms↩︎

Next, we compare Posterior-DDIM against several representative diffusion-based image restoration algorithms, including DDRM [8], DDNM+ [62], DPS [7], RED-diff [37], and ProjDiff [57].⁵ As a classical baseline, we also include the least-squares estimator, \(\widehat{X}^{\mathsf{ls}} = A^{\dagger}Y\). In addition to the inpainting and super-resolution tasks considered in Section 4.1, we further evaluate all methods on Gaussian deblurring and compressed sensing. For Gaussian deblurring, we use a one-dimensional Gaussian blur kernel of size \(5\) with standard deviation \(10\). For compressed sensing, we employ a Walsh–Hadamard sampling matrix with a sampling ratio of \(0.5\). Throughout all experiments, the observation noise standard deviation is fixed at \(\sigma=0.05\).

In addition, note that the posterior mean can be approximately computed via Monte Carlo sampling, i.e, \[\mathbb{E}[X_0\,|\,Y] \approx \frac{1}{n}\sum_{i=1}^N \widehat{X}^{(i)},\] where \(\widehat{X}^{(i)}\overset{\mathsf{i.i.d.}}{\sim} p_{X_0\,|\,Y}\). As is well-known, the posterior mean achieves the optimal reconstruction accuracy under the mean squared estimation error metric. Consequently, reconstruction fidelity can be improved by averaging samples generated from independent noise realizations. We observe, however, that this approach may sometimes degrade quality as measured by FID. To illustrate this effect, we report both single-sample results and posterior-mean results, where the latter are obtained by averaging 4 independent trials.

The results are reported in Tables ¿tbl:tab:sr?–¿tbl:tab:cs?. Boldface indicates the best overall result, while underlining indicates the best sampling-based result. Across all tasks and datasets, the proposed Posterior-DDIM method consistently delivers strong performance. For super-resolution, it achieves the best performance on three and two of the four evaluation metrics on CelebA and ImageNet datasets respectively. For inpainting, it outperforms the reference algorithms on all four metrics for CelebA and on two metrics for ImageNet. For Gaussian deblurring, Posterior-DDIM achieves the best performance on three metrics for CelebA and two metrics for ImageNet. For compressed sensing, Posterior-DDIM outperforms DDNM+ across all of the four evaluation metrics. Overall, whereas existing methods typically achieve the best result on only one or two metrics in most settings, our method attains the best performance on at least two evaluation metrics across all tasks and datasets, demonstrating its efficacy and robustness across a diverse range of inverse problems.

Figure 2 shows the performance of Posterior-DDIM, DDNM+, and ProjDiff under different numbers of Monte Carlo samples used to estimate the posterior mean. As discussed previously, increasing the number of samples improves reconstruction fidelity, as reflected by PSNR, SSIM, and LPIPS, but comes at the expense of reduced sample diversity, leading to worse FID scores. Furthermore, among all reference algorithms considered, our method achieves the best trade-off between fidelity and diversity on this task.

Figure 3 illustrates the effect of the NFE on the super-resolution task using the ImageNet dataset. As the NFE increases, the performance improves, and becomes stable once NFE exceeds \(80\), suggesting that our default choice of NFE=100 provides a favorable balance between computational cost and reconstruction quality.

5 Discussion↩︎

In this work, we have proposed a novel DDIM-type posterior sampler for solving linear inverse problems with diffusion priors. In contrast to many existing methods that rely on heuristic projection steps or approximate posterior scores, our approach follows a different route by treating different singular directions of the measurement operator differently according to the relative strengths of the observation noise and the diffusion noise. This leads to a simple, easy-to-implement, DDIM-type sampling procedure that is both practically effective and theoretically principled. In particular, we have established that, under mild conditions, the proposed Posterior-DDIM sampler converges to the true posterior distribution of the signal given the measurement. Empirically, our experiments on a range of real-world image restoration tasks have shown that the proposed method consistently performs favorably against existing diffusion-based posterior samplers, achieving the best performance on the majority of evaluation metrics across all tasks.

Several directions merit further investigation. For instance, the present work has focused on linear inverse problems, and a fundamentally important next step is to extend the proposed framework to broader nonlinear inverse problems, which naturally arise in wide-ranging real-world applications. In addition, while our theoretical analysis has established asymptotic convergence to the true posterior distribution, it falls short of characterizing the rate of convergence, which would be of interest to quantify. It would also be valuable to understand how the convergence behavior and sampling quality depend on additional factors such as the noise level, the properties of the measurement operator, and the choice of time discretization of the diffusion process.

Acknowledgments↩︎

Y. Chen is supported in part by the Alfred P. Sloan Research Fellowship, the ONR grant N00014-25-1-2344, the NSF grants 2221009 and 2218773, the Wharton AI & Analytics Initiative’s AI Research Fund, and the Amazon Research Award. G. Li is supported in part by the Chinese University of Hong Kong Direct Grant for Research and the Hong Kong Research Grants Council ECS 24305724 and GRF 14307525. C. Cai is supported in part by the NSF grants CAREER award CCF-2541600 and DMS-2515333.

6 Proof of Theorem 1↩︎

For convenience, we introduce the following notations: for any vector \(X_{t_i}\in\mathbb{R}^d\), denote \[X_{t_i}^{\mathsf{st}}\mathrel{\vcenter{:}}= V_{\mathcal{S}_{t_i}^{\mathsf{meas}}}^{\top}{X}_{t_i},\qquad {X}_{t_i}^{\mathsf{sc}}\mathrel{\vcenter{:}}= V_{\mathcal{S}_{t_i}^{\mathsf{prior}}}^{\top}X_{t_i},\qquad X_{t_i}^{\mathsf{c}}\mathrel{\vcenter{:}}= V_{\mathcal{S}^{\mathsf{c}}}^{\top}X_{t_i},\qquad X_{t_i}^{\mathsf{s}}\mathrel{\vcenter{:}}= V_{\mathcal{S}}^{\top}X_{t_i},\] the projection of observation \(\overline{Y}_{t_i}\mathrel{\vcenter{:}}= \Sigma_{\mathcal{S}_{t_i}^{\mathsf{meas}}}^{-1}U_{\mathcal{S}_{t_i}^{\mathsf{meas}}}^{\top} Y\), and the noise \(\overline{Z}_{t_i}\mathrel{\vcenter{:}}= [Z_s]_{s\in {\mathcal{S}_{t_i}^{\mathsf{meas}}}}\) used to update \(V_{\mathcal{S}_{t_i}^{\mathsf{meas}}}^{\top}\widehat{X}_{t_i}\). Additionally, throughout this paper, we denote by \(\mathsf{KL}(p \,\Vert\, q)\) the Kullback-Leibler (KL) divergence between two probability measures \(p\) and \(q\).

We intend to establish the following stronger conclusion than Theorem 1: for any \(t_i\), conditioned on \(V_{\mathcal{S}_{t_i}^{\mathsf{meas}}}^{\top}\widehat{X}_{t_i}\) and \(v_{s}^{\top}\widehat{X}_{\tau_s}\)for all \(\tau_s> t_i\), we have \[\begin{align} \mathsf{TV}\big(p_{\widehat{X}_{t_i}\mid V_{\mathcal{S}_{t_i}^{\mathsf{meas}}}^{\top}\widehat{X}_{t_i}=V_{\mathcal{S}_{t_i}^{\mathsf{meas}}}^{\top}x_{t_i}, v_{s}^{\top}\widehat{X}_{\tau_s}=v_s^{\top}x_{\tau_s}}, p_{X_{t_i} \mid V_{\mathcal{S}_{t_i}^{\mathsf{meas}}}^{\top}X_{t_i} = V_{\mathcal{S}_{t_i}^{\mathsf{meas}}}^{\top}x_{t_i}, v_{s}^{\top}X_{\tau_s} = v_{s}^{\top}x_{\tau_s}}) \to 0. \end{align}\] When \(t_M\) is sufficiently close to \(0\), the set \(\mathcal{S}_{t_M}^{\mathsf{meas}}\) becomes empty, and we obtain \[\begin{align} \mathsf{TV}\big(p_{\widehat{X}_{t_M}\mid v_{s}^{\top}\widehat{X}_{\tau_s}=v_s^{\top}x_{\tau_s}}, p_{X_{t_M} \mid v_{s}^{\top}X_{\tau_s} = v_{s}^{\top}x_{\tau_s}}) \to 0. \end{align}\] Moreover, noticing that \(v_{s}^{\top}\widehat{X}_{\tau_s}=\Sigma_{ss}^{-1}u_s^{\top}Y\), and \((X_{t_M},v_s^{\top}X_{\tau_s})\) have the same joint distribution as \((X_{t_M},\Sigma_{ss}^{-1}u_s^{\top}Y)\), we can complete the proof of Theorem 1.

6.0.0.1 Step 1. construct auxiliary sequences.

We begin with introducing some auxiliary sequences. Note that \(\sum_{i=1}^{M-1}\delta_{i}=\Theta(1)\). Denote \[\begin{align} \label{eq:def-plambd} \gamma_i \mathrel{\vcenter{:}}= \frac{\eta_1(1-{\rm e}^{-2\delta_{i+1}})}{2}\sigma_{t_{i+1}}^2,\qquad p_{\lambda_i}(\cdot,\cdot) \mathrel{\vcenter{:}}= p_{X_{t_i}^{\mathsf{c}},X_{t_i}^{\mathsf{sc}}|X_{t_i}^{\mathsf{st}}}(\cdot,\cdot|\alpha_{t_{i}}\overline{Y}_{t_{i}} + \widehat{\sigma}_{t_{i}}\overline{Z}_{t_{i}}), \end{align}\tag{21}\] where \(\widehat{\sigma}_{t_i}\) is defined in 16 . We have for \(\delta_{i+1}\le 1/2\), \[\begin{align} \label{eq:proof-bound-gamma} \frac{1}{2}\eta_1\delta_{i+1}\sigma_{t_{i+1}}^2 = \frac{\eta_1 \delta_{i+1}}{2}\sigma_{t_{i+1}}^2 \le \gamma_i \le \frac{\eta_1 \cdot 2\delta_{i+1}}{2} \sigma_{t_{i+1}}^2 =\eta_1\delta_{i+1}\sigma_{t_{i+1}}^2. \end{align}\tag{22}\]

An auxiliary sequence \(\widetilde{X}_{k}\) with initialization \(\widetilde{X}_0 = \widehat{X}_{t_0}\) is iteratively defined as \[\label{eq:def-auxiliary-sequence} \begin{align} \widetilde{X}_{k+1}^{\mathsf{st}} &=\alpha_{t_{k+1}}\overline{Y}_{t_{k+1}} + \widehat{\sigma}_{t_{k+1}}\overline{Z}_{t_{k+1}},\notag\\ \widetilde{X}_{k+1}^{\mathsf{sc}} &= \frac{\alpha_{t_{k+1}}}{\alpha_{t_k}}\widetilde{X}_{t_{k}}^{\mathsf{sc}} + \frac{\alpha_{t_{k+1}}\sigma_{t_k}^2}{\alpha_{t_{k}}}\left(1-{\rm e}^{-2\delta_{k+1}}\right)\nabla_{\widetilde{X}_{k}^{\mathsf{sc}}} \log p_{\lambda_k}(\widetilde{X}_{k}^{\mathsf{c}},\widetilde{X}_{k}^{\mathsf{sc}}) + \sigma_{t_{k+1}}\sqrt{1 - e^{-2\delta_{k+1}}} Z_{k}^{\mathsf{sc}},\notag\\ \widetilde{X}_{k+1}^{\mathsf{c}} &= \widetilde{X}_{k}^{\mathsf{c}} + \gamma_k \nabla_{\widetilde{X}_k^{\mathsf{c}}} \log p_{\lambda_{k+1}}(\widetilde{X}_{k}^{\mathsf{c}},\widetilde{X}_{k+1}^{\mathsf{sc}}) + \sqrt{2\gamma_k} Z_k^{\mathsf{c}}, \end{align}\tag{23}\] where \(Z_k^{\mathsf{sc}}\) and \(Z_k^{\mathsf{c}}\) are independent Gaussian random processes. Another auxiliary sequence is defined as \[\begin{align} \label{eq:def-auxiliary-sequence-bar} \overline{X}_{k+1}^{\mathsf{st}} &=\alpha_{t_{k+1}}\overline{Y}_{t_{k+1}} + \widehat{\sigma}_{t_{k+1}}\overline{Z}_{t_{k+1}},\quad \overline{X}_{k+1}^{\mathsf{sc}} \sim p_{X_{k+1}^{\mathsf{sc}}\mid X_k}(\cdot\mid \overline{X}_{k}),\quad \overline{X}_{k+1}^{\mathsf{c}} \sim p_{X_{k+1}^{\mathsf{c}}\mid X_{k+1}^{\mathsf{s}}}(\cdot\mid \overline{X}_{k+1}^{\mathsf{s}}). \end{align}\tag{24}\] Based on these sequences, we have the following lemma, whose proof is postponed to Section 7.3.

This lemma tells us that the marginal distribution \(\mathsf{TV}\big(p_{\widetilde{X}_{k}\,|\,Y,Z}, p_{\widehat{X}_{k}\,|\,Y,Z}\big) \to 0\). Denote \(\overline{Z}_{t_i}^{\mathsf{c}} = [Z_s]_{s\in\mathcal{S}_{t_i}^{\mathsf{prior}}}\). The convergence of marginal distribution leads to \[\begin{align} \label{eq:proof-thm-1} &\mathsf{TV}\big(p_{\widetilde{X}_{k}\,|\,V_{\mathcal{S}_{t_k}^{\mathsf{meas}}}^{\top}\widetilde{X}_{k}, v_{s}^{\top}\widetilde{X}_{\tau_s}}(\cdot,x^{\mathsf{st}},v_{s}^{\top}{x}_{\tau_s}), p_{\widehat{X}_{t_k}\,|\,V_{\mathcal{S}_{t_k}^{\mathsf{meas}}}^{\top}\widehat{X}_{t_k}, v_{s}^{\top}\widehat{X}_{\tau_s}}(\cdot,x^{\mathsf{st}},v_{s}^{\top}{x}_{\tau_s})\big)\notag\\ &\quad \le \mathbb{E}_{\overline{Y}_{t_k},\overline{Z}_{t_k}^{\mathsf{c}}\mid V_{\mathcal{S}_{t_k}^{\mathsf{meas}}}^{\top}\widetilde{X}_{k}}[\mathsf{TV}\big(p_{\widetilde{X}_{k}\,|\,V_{\mathcal{S}_{t_k}^{\mathsf{meas}}}^{\top}\widetilde{X}_{k}, v_{s}^{\top}\widetilde{X}_{\tau_s},\overline{Y}_{t_k},\overline{Z}_{t_k}^{\mathsf{c}}}(\cdot\,|\,x^{\mathsf{st}},v_{s}^{\top}{x}_{\tau_s},\overline{y}_{t_k},\widehat{z}), \notag\\ &\qquad \qquad \qquad \qquad p_{\widehat{X}_{t_k}\,|\,V_{\mathcal{S}_{t_k}^{\mathsf{meas}}}^{\top}\widehat{X}_{t_k}, v_{s}^{\top}\widehat{X}_{\tau_s},\overline{Y}_{t_k},\overline{Z}_{t_k}^{\mathsf{c}}}(\cdot\,|\,x^{\mathsf{st}},v_{s}^{\top}{x}_{\tau_s},\overline{y}_{t_k},\widehat{z})\big)]\notag\\ &\quad = \mathbb{E}_{\overline{Y}_{t_k},\overline{Z}_{t_k}^{\mathsf{c}}\mid V_{\mathcal{S}_{t_k}^{\mathsf{meas}}}^{\top}\widetilde{X}_{k}}[\mathsf{TV}\big(p_{\widetilde{X}_{k}\,|\,Y,Z}(\cdot\,|\,y,z), p_{\widehat{X}_{t_k}\,|\,Y,Z}(\cdot\,|\,y,z)\big)]\to 0, \end{align}\tag{25}\] where \(v_s^{\top}x_{\tau_s} = \Sigma_{ss}^{-1}u_s^{\top}y\), \(\overline{z}_{t_k} = \widehat{\sigma}_{t_k}^{-1}(x^{\mathsf{st}} - \alpha_{t_k}\overline{y}_{t_k})\), and the last equation holds since \(p_{\widetilde{X}_{k}\,|\,V_{\mathcal{S}_{t_k}^{\mathsf{meas}}}^{\top}\widetilde{X}_{k}, v_{s}^{\top}\widetilde{X}_{\tau_s},\overline{Y}_{t_k},\overline{Z}_{t_k}^{\mathsf{c}}} = p_{\widetilde{X}_{k}\,|\,Y,Z}\) and \(p_{\widehat{X}_{k}\,|\,V_{\mathcal{S}_{t_k}^{\mathsf{meas}}}^{\top}\widehat{X}_{t_k}, v_{s}^{\top}\widehat{X}_{\tau_s},\overline{Y}_{t_k},\overline{Z}_{t_k}^{\mathsf{c}}} = p_{\widehat{X}_{t_k}\,|\,Y,Z}\). Based on Lemma 1 and 25 , it suffices to prove that for any \(x^{\mathsf{st}}\) and \(x_{\tau_s}\), \[\begin{align} \mathsf{TV}\big(p_{\widetilde{X}_k\,|\,\widetilde{X}_{k}^{\mathsf{st}}, v_{s}^{\top}\widetilde{X}_{\tau_s}}(\cdot\,|\,x^{\mathsf{st}}, v_{s}^{\top}x_{\tau_s}),p_{\overline{X}_{t_k}\,|\,\overline{X}_{t_k}^{\mathsf{st}}, v_{s}^{\top}\overline{X}_{\tau_s}}(\cdot\,|\,x^{\mathsf{st}}, v_{s}^{\top}x_{\tau_s})\big)\to 0. \end{align}\] By a similar argument as in 25 , it suffices to prove that for any \(y\), \(z\), \[\begin{align} \mathsf{TV}\big(p_{\widetilde{X}_k\,|\,Y,Z}(\cdot\,|\,y,z),p_{\overline{X}_{t_k}\,|\,Y,Z}(\cdot\,|\,y,z)\big)\to 0. \end{align}\]

6.0.0.2 Step 2. transform to the analysis of auxiliary sequences.

We begin with the decomposition that \[\begin{align} p_{\widetilde{X}_k\,|\,Y, Z}(x|y,z) &= p_{\widetilde{X}_k^{\mathsf{c}}\,|\,\widetilde{X}_k^{\mathsf{s}},Y,Z}(x^{\mathsf{c}}|x^{\mathsf{s}},y,z) p_{\widetilde{X}_k^{\mathsf{sc}}\,|\,Y,Z}(x^{\mathsf{sc}}|y,z),\notag\\ p_{\overline{X}_{k}\,|\,Y, Z}(x\,|\,y,z) &= p_{\overline{X}_{k}^{\mathsf{c}}\,|\,\overline{X}_{k}^{\mathsf{s}},Y,Z}(x^{\mathsf{c}}\,|\,x^{\mathsf{s}},y,z)p_{\overline{X}_{k}^{\mathsf{sc}}\,|\,Y,Z}(x^{\mathsf{sc}}\,|\,y,z) \end{align}\] Then the total variation distance can be decomposed by \[\begin{align} \label{eq:proof-24} &\mathsf{TV}\Big(p_{\widetilde{X}_k\,|\,Y,Z}, p_{\overline{X}_{k}\,|\,Y,Z}\Big) \le \mathsf{TV}\Big( p_{\widetilde{X}_{k}^{\mathsf{sc}}\,|\,Y,Z}, p_{\overline{X}_{k}^{\mathsf{sc}}\,|\,Y,Z}\Big) \notag\\ &\qquad\qquad +\mathbb{E}_{x^{\mathsf{sc}}\sim p_{\widetilde{X}_{k}^{\mathsf{sc}}\,|\,Y,Z}}\bigg[\mathsf{TV}\bigg(p_{\widetilde{X}_{k}^{\mathsf{c}}\,|\,\widetilde{X}_{k}^{\mathsf{s}},Y,Z}(\cdot|x^{\mathsf{s}},y,z), p_{\overline{X}_{k}^{\mathsf{c}}\,|\,\overline{X}_{k}^{\mathsf{s}},Y,Z}(\cdot|x^{\mathsf{s}},y,z)\bigg)\bigg]. \end{align}\tag{26}\] The convergence of the second terms comes from the following lemma:

The proof is postponed to Appendix 7.4. Here we use a more strong conclusion than Lemma 2, i.e., for any \(y\), \(z\), \[\begin{align} \label{eq:distri-xc} \mathbb{E}_{x^{\mathsf{sc}}\sim\widetilde{X}_k^{\mathsf{sc}}\,|\,Y,Z}\big[\mathsf{TV}\left(p_{\widetilde{X}_{k}^{\mathsf{c}} \mid \widetilde{X}_{k}^{\mathsf{s}}, Y,Z}(\cdot\mid x^{\mathsf{s}}, y,z), p_{X_{t_k}^{\mathsf{c}} \mid X_{t_k}^{\mathsf{s}}}(\cdot\mid x^{\mathsf{s}})\right)\big]\to 0. \end{align}\tag{27}\] The proof is postponed to Section 7.4 (cf. 48 ). Then the second term goes to zero: \[\begin{align} \label{eq:proof-25} &\mathbb{E}_{x^{\mathsf{sc}}\sim p_{\widetilde{X}_{k}^{\mathsf{sc}}\,|\,Y,Z}}\bigg[\mathsf{TV}\bigg(p_{\widetilde{X}_{k}^{\mathsf{c}}\,|\,\widetilde{X}_{k}^{\mathsf{s}},Y,Z}(\cdot|x^{\mathsf{s}},y,z), p_{\overline{X}_{k}^{\mathsf{c}}\,|\,\overline{X}_{k}^{\mathsf{s}},Y,Z}(\cdot|x^{\mathsf{s}},y,z)\bigg)\bigg] \notag\\ &\quad \overset{\text{(i)}}{=} \mathbb{E}_{x^{\mathsf{sc}}\sim p_{\widetilde{X}_{k}^{\mathsf{sc}}\,|\,Y,Z}}\bigg[\mathsf{TV}\bigg(p_{\widetilde{X}_{k}^{\mathsf{c}}\,|\,\widetilde{X}_{k}^{\mathsf{s}},Y,Z}(\cdot|x^{\mathsf{s}},y,z), p_{{X}_{t_k}^{\mathsf{c}}\,|\,{X}_{t_k}^{\mathsf{s}}}(\cdot|x^{\mathsf{s}})\bigg)\bigg]\to 0, \end{align}\tag{28}\] where (i) arises from the fact that \(p_{\overline{X}_{k}^{\mathsf{c}}\,|\,\overline{X}_{k}^{\mathsf{s}},Y,Z} = p_{{X}_{k}^{\mathsf{c}}\,|\,{X}_{k}^{\mathsf{s}}}\). It suffices to prove the first term goes to zero, i.e., \[\begin{align} \label{eq:proof-thm-4} \mathsf{TV}\big(p_{\widetilde{X}_k^{\mathsf{sc}}\,|\,Y,Z}, p_{\overline{X}_{k}^{\mathsf{sc}}\,|\,Y,Z}\big)\to 0. \end{align}\tag{29}\]

6.0.0.3 Step 3. decompose the error terms.

By virtue of Pinsker’s inequality, we further decompose the total variation distance as \[\begin{align} \label{eq:proof-20} &\mathsf{TV}\big(p_{\widetilde{X}_k^{\mathsf{sc}}\,|\,Y,Z}, p_{\overline{X}_{k}^{\mathsf{sc}}\,|\,Y,Z}\big)^2 \notag\\ &\le \mathsf{KL}\bigg(p_{\widetilde{X}_k^{\mathsf{sc}}\,|\,Y,Z}\,\Vert\, p_{\overline{X}_{k}^{\mathsf{sc}}\,|\,Y,Z}\bigg)\notag\\ &\le \sum_{i=1}^k\mathbb{E}_{x_{i-1}^{\mathsf{sc}}\sim p_{\widetilde{X}_{i-1}^{\mathsf{sc}}}\,|\,Y,Z}\bigg[\mathsf{KL}\bigg(p_{\widetilde{X}_{i}^{\mathsf{sc}}\,|\,\widetilde{X}_{i-1}^{\mathsf{s}},Y,Z}(\cdot\,|\,x_{i-1}^{\mathsf{s}},y,z) \,\Vert\, p_{\overline{X}_i^{\mathsf{sc}}\,|\,\overline{X}_{i-1}^{\mathsf{s}},Y,Z}(\cdot\,|\,x_{i-1}^{\mathsf{s}},y,z)\bigg)\bigg]+ \mathsf{KL}(p_{\widetilde{X}_{0}^{\mathsf{sc}}}\,\Vert\, p_{\overline{X}_{0}^{\mathsf{sc}}})\notag\\ &= \sum_{i=1}^k\mathbb{E}_{x_{i-1}^{\mathsf{sc}}\sim p_{\widetilde{X}_{i-1}^{\mathsf{sc}}}\,|\,Y,Z}\bigg[\mathsf{KL}\bigg( p_{\widetilde{X}_{i}^{\mathsf{sc}}\,|\,\widetilde{X}_{i-1}^{\mathsf{s}},Y,Z}(\cdot|x_{i-1}^{\mathsf{s}},y,z)\Vert p_{\overline{X}_i^{\mathsf{sc}}\,|\,\overline{X}_{i-1}^{\mathsf{s}}}(\cdot|x_{i-1}^{\mathsf{s}})\bigg)\bigg] + \mathsf{KL}(p_{\widetilde{X}_{0}^{\mathsf{sc}}}\,\Vert\, p_{\overline{X}_{0}^{\mathsf{sc}}}), \end{align}\tag{30}\] where \(x_{i-1}^{\mathsf{s}}\) satisfies \(x_{i-1}^{\mathsf{st}} = \alpha_{t_{i-1}}\Sigma_{\mathcal{S}_{t_{i-1}}}^{-1}U_{\mathcal{S}_{t_{i-1}}}^{\top}y + \widehat{\sigma}_{t_{i-1}}[Z_s]_{s\in\mathcal{S}_{t_{i-1}}}\), and the last line holds since \(p_{\overline{X}_{i}^{\mathsf{sc}}\,|\,\overline{X}_{i-1}^{\mathsf{s}},Y,Z} = p_{\overline{X}_{i}^{\mathsf{sc}}\,|\,\overline{X}_{i-1}^{\mathsf{s}}}\). According to the definition of \(\overline{X}_i\), we further have \[\begin{align} \label{eq:proof-thm-2} &\mathsf{KL}\bigg( p_{\widetilde{X}_{i}^{\mathsf{sc}}\,|\,\widetilde{X}_{i-1}^{\mathsf{s}},Y,Z}(\cdot|x_{i-1}^{\mathsf{s}},y,z)\,\Vert\, p_{\overline{X}_i^{\mathsf{sc}}\,|\,\overline{X}_{i-1}^{\mathsf{s}}}(\cdot|x_{i-1}^{\mathsf{s}})\bigg)\notag\\ &\quad \overset{\text{(i)}}{=} \mathsf{KL}\bigg( p_{\widetilde{X}_{i}^{\mathsf{sc}}\,|\,\widetilde{X}_{i-1}^{\mathsf{s}},Y,Z}(\cdot|x_{i-1}^{\mathsf{s}},y,z) \,\Vert\,p_{{X}_{t_i}^{\mathsf{sc}}\,|\,{X}_{t_{i-1}}^{\mathsf{s}}}(\cdot|x_{i-1}^{\mathsf{s}})\bigg)\notag\\ &\quad =\int \log \frac{p_{\widetilde{X}_{i}^{\mathsf{sc}}\,|\,\widetilde{X}_{i-1}^{\mathsf{s}},Y,Z}(x_i^{\mathsf{sc}}\,|\,x_{i-1}^{\mathsf{s}},y,z)}{p_{{X}_{t_i}^{\mathsf{sc}}\,|\,{X}_{t_{i-1}}^{\mathsf{s}}}(x_i^{\mathsf{sc}}\,|\,x_{i-1}^{\mathsf{s}})} p_{\widetilde{X}_{i}^{\mathsf{sc}}\,|\,\widetilde{X}_{i-1}^{\mathsf{s}},Y,Z}(x_i^{\mathsf{sc}}\,|\,x_{i-1}^{\mathsf{s}},y,z)\mathrm{d} {x}_i^{\mathsf{sc}}, \end{align}\tag{31}\] where (i) holds since \[\begin{align} p_{\overline{X}_{i}^{\mathsf{sc}}\,|\,\overline{X}_{i-1}^{\mathsf{s}}}(x_i^{\mathsf{sc}}\,|\,x_{i-1}^{\mathsf{s}}) &= \int p_{\overline{X}_{i}^{\mathsf{sc}}\,|\,\overline{X}_{i-1}}(x_i^{\mathsf{sc}}\,|\,x_{i-1})p_{\overline{X}_{i-1}^{\mathsf{c}}\,|\,\overline{X}_{i-1}^{\mathsf{s}}}(x_{i-1}^{\mathsf{c}}\,|\,x_{i-1}^{\mathsf{s}}) \mathrm{d}{x}_{i-1}^{\mathsf{c}}\notag\\ &= \int p_{{X}_{t_i}^{\mathsf{sc}}\,|\,{X}_{t_{i-1}}}(x_i^{\mathsf{sc}}\,|\,x_{i-1})p_{{X}_{t_{i-1}}^{\mathsf{c}}\,|\,{X}_{t_{i-1}}^{\mathsf{s}}}(x_{i-1}^{\mathsf{c}}\,|\,x_{i-1}^{\mathsf{s}}) \mathrm{d}{x}_{i-1}^{\mathsf{c}} = p_{{X}_{t_i}^{\mathsf{sc}}\,|\,{X}_{t_{i-1}}^{\mathsf{s}}}(x_i^{\mathsf{sc}}\,|\,x_{i-1}^{\mathsf{s}}) . \end{align}\] We further decompose the KL divergence in 31 as \[\begin{align} \label{eq:proof-21} &\mathsf{KL}\bigg( p_{\widetilde{X}_{i}^{\mathsf{sc}}\,|\,\widetilde{X}_{i-1}^{\mathsf{s}},Y,Z}(\cdot|x_{i-1}^{\mathsf{s}},y,z)\,\Vert\, p_{\overline{X}_i^{\mathsf{sc}}\,|\,\overline{X}_{i-1}^{\mathsf{s}}}(\cdot|x_{i-1}^{\mathsf{s}})\bigg)\notag\\ &\quad = \int \log \frac{\int p_{\widetilde{X}_i^{\mathsf{sc}}\,|\,\widetilde{X}_{i-1},Y,Z}({x}_{i}^{\mathsf{sc}}\,|\,{x}_{i-1},y,z)p_{\widetilde{X}_{i-1}^{\mathsf{c}}\,|\,\widetilde{X}_{i-1}^{\mathsf{s}},Y,Z}({x}_{i-1}^{\mathsf{c}}\,|\,{x}_{i-1}^{\mathsf{s}},y,z) \mathrm{d}{x}_{i-1}^{\mathsf{c}}}{\int p_{{X}_{t_i}^{\mathsf{sc}}\,|\,{X}_{t_{i-1}}}({x}_{i}^{\mathsf{sc}}\,|\,{x}_{i-1})p_{{X}_{t_{i-1}}^{\mathsf{c}}\,|\,{X}_{t_{i-1}}^{\mathsf{s}}}({x}_{i-1}^{\mathsf{c}}\,|\,{x}_{i-1}^{\mathsf{s}}) \mathrm{d}{x}_{i-1}^{\mathsf{c}}} p_{\widetilde{X}_{i}^{\mathsf{sc}}\,|\,\widetilde{X}_{{i-1}}^{\mathsf{s}},Y,Z}({x}_i^{\mathsf{sc}}\,|\,{x}_{i-1}^{\mathsf{s}},y,z)\mathrm{d} {x}_i^{\mathsf{sc}}\notag\\ &\quad=\int \log \frac{\int p_{\widetilde{X}_{i}^{\mathsf{sc}}\,|\,\widetilde{X}_{{i-1}},Y,Z}({x}_{i}^{\mathsf{sc}}\,|\,{x}_{i-1},y,z)p_{{X}_{t_{i-1}}^{\mathsf{c}}\,|\,{X}_{t_{i-1}}^{\mathsf{s}}}({x}_{i-1}^{\mathsf{c}}\,|\,{x}_{i-1}^{\mathsf{s}}) \mathrm{d}{x}_{i-1}^{\mathsf{c}}}{\int p_{{X}_{t_i}^{\mathsf{sc}}\,|\,{X}_{t_{i-1}}}({x}_{i}^{\mathsf{sc}}\,|\,{x}_{i-1})p_{{X}_{t_{i-1}}^{\mathsf{c}}\,|\,{X}_{t_{i-1}}^{\mathsf{s}}}({x}_{i-1}^{\mathsf{c}}\,|\,{x}_{i-1}^{\mathsf{s}}) \mathrm{d}{x}_{i-1}^{\mathsf{c}}} p_{\widetilde{X}_{i}^{\mathsf{sc}}\,|\,\widetilde{X}_{{i-1}}^{\mathsf{s}},Y,Z}({x}_i^{\mathsf{sc}}\,|\,{x}_{i-1}^{\mathsf{s}},y,z)\mathrm{d} {x}_i^{\mathsf{sc}}\notag\\ &\qquad + \int \log \frac{\int p_{\widetilde{X}_{i}^{\mathsf{sc}}\,|\,\widetilde{X}_{i-1},Y,Z}({x}_{i}^{\mathsf{sc}}\,|\,{x}_{i-1},y,z)p_{\widetilde{X}_{i-1}^{\mathsf{c}}\,|\,\widetilde{X}_{i-1}^{\mathsf{s}},Y,Z}({x}_{i-1}^{\mathsf{c}}\,|\,{x}_{i-1}^{\mathsf{s}},y,z) \mathrm{d}{x}_{i-1}^{\mathsf{c}}}{\int p_{\widetilde{X}_{i}^{\mathsf{sc}}\,|\,\widetilde{X}_{i-1},Y,Z}({x}_{i}^{\mathsf{sc}}\,|\,{x}_{i-1},y,z)p_{{X}_{t_{i-1}}^{\mathsf{c}}\,|\,{X}_{t_{i-1}}^{\mathsf{s}}}({x}_{i-1}^{\mathsf{c}}\,|\,{x}_{i-1}^{\mathsf{s}}) \mathrm{d}{x}_{i-1}^{\mathsf{c}}} p_{\widetilde{X}_{i}^{\mathsf{sc}}\,|\,\widetilde{X}_{{i-1}}^{\mathsf{s}},Y,Z}({x}_i^{\mathsf{sc}}\,|\,{x}_{i-1}^{\mathsf{s}},y,z)\mathrm{d} {x}_i^{\mathsf{sc}}. \end{align}\tag{32}\] The first term is further decomposed by \[\begin{align} \label{eq:proof-26} &\int \log \frac{\int p_{\widetilde{X}_{i}^{\mathsf{sc}}\,|\,\widetilde{X}_{{i-1}},Y,Z}({x}_{i}^{\mathsf{sc}}\,|\,{x}_{i-1},y,z)p_{{X}_{t_{i-1}}^{\mathsf{c}}\,|\,{X}_{t_{i-1}}^{\mathsf{s}}}({x}_{i-1}^{\mathsf{c}}\,|\,{x}_{i-1}^{\mathsf{s}}) \mathrm{d}{x}_{i-1}^{\mathsf{c}}}{\int p_{{X}_{t_i}^{\mathsf{sc}}\,|\,{X}_{t_{i-1}}}({x}_{i}^{\mathsf{sc}}\,|\,{x}_{i-1})p_{{X}_{t_{i-1}}^{\mathsf{c}}\,|\,{X}_{t_{i-1}}^{\mathsf{s}}}({x}_{i-1}^{\mathsf{c}}\,|\,{x}_{i-1}^{\mathsf{s}}) \mathrm{d}{x}_{i-1}^{\mathsf{c}}} p_{\widetilde{X}_{i}^{\mathsf{sc}}\,|\,\widetilde{X}_{{i-1}}^{\mathsf{s}},Y,Z}({x}_i^{\mathsf{sc}}\,|\,{x}_{i-1}^{\mathsf{s}},y,z)\mathrm{d} {x}_i^{\mathsf{sc}}\notag\\ &\quad =\int f(x_i^{\mathsf{sc}},x_{i-1}^{\mathsf{s}})\int p_{\widetilde{X}_{i}^{\mathsf{sc}}\,|\,\widetilde{X}_{{i-1}},Y,Z}({x}_{i}^{\mathsf{sc}}\,|\,{x}_{i-1},y,z)p_{{X}_{t_{i-1}}^{\mathsf{c}}\,|\,{X}_{t_{i-1}}^{\mathsf{s}}}({x}_{i-1}^{\mathsf{c}}\,|\,{x}_{i-1}^{\mathsf{s}}) \mathrm{d}{x}_{i-1}^{\mathsf{c}}\mathrm{d} {x}_i^{\mathsf{sc}}\notag\\ &\qquad + \int f(x_i^{\mathsf{sc}},x_{i-1}^{\mathsf{s}})\int p_{\widetilde{X}_{i}^{\mathsf{sc}}\,|\,\widetilde{X}_{{i-1}},Y,Z}({x}_{i}^{\mathsf{sc}}\,|\,{x}_{i-1},y,z)\notag\\ &\qquad \cdot \left(p_{\widetilde{X}_{{i-1}}^{\mathsf{c}}\,|\,\widetilde{X}_{{i-1}}^{\mathsf{s}},Y,Z}({x}_{i-1}^{\mathsf{c}}\,|\,{x}_{i-1}^{\mathsf{s}},y,z)-p_{{X}_{t_{i-1}}^{\mathsf{c}}\,|\,{X}_{t_{i-1}}^{\mathsf{s}}}({x}_{i-1}^{\mathsf{c}}\,|\,{x}_{i-1}^{\mathsf{s}})\right) \mathrm{d}{x}_{i-1}^{\mathsf{c}}\mathrm{d} {x}_i^{\mathsf{sc}}, \end{align}\tag{33}\] where \[f(x_i^{\mathsf{sc}},x_{i-1}^{\mathsf{s}})\mathrel{\vcenter{:}}= \log \frac{\int p_{\widetilde{X}_{i}^{\mathsf{sc}}\,|\,\widetilde{X}_{{i-1}},Y,Z}({x}_{i}^{\mathsf{sc}}\,|\,{x}_{i-1},y,z)p_{{X}_{t_{i-1}}^{\mathsf{c}}\,|\,{X}_{t_{i-1}}^{\mathsf{s}}}({x}_{i-1}^{\mathsf{c}}\,|\,{x}_{i-1}^{\mathsf{s}}) \mathrm{d}{x}_{i-1}^{\mathsf{c}}}{\int p_{{X}_{t_i}^{\mathsf{sc}}\,|\,{X}_{t_{i-1}}}({x}_{i}^{\mathsf{sc}}\,|\,{x}_{i-1})p_{{X}_{t_{i-1}}^{\mathsf{c}}\,|\,{X}_{t_{i-1}}^{\mathsf{s}}}({x}_{i-1}^{\mathsf{c}}\,|\,{x}_{i-1}^{\mathsf{s}}) \mathrm{d}{x}_{i-1}^{\mathsf{c}}}.\] By using 27 , the second term in the right-hand-side of 33 satisfies \[\begin{align} \label{eq:proof-27} &\mathbb{E}_{x_{i-1}^{\mathsf{sc}}\sim p_{\widetilde{X}_{i-1}^{\mathsf{sc}}\,|\,Y,Z}}\Big[\int f(x_i^{\mathsf{sc}},x_{i-1}^{\mathsf{s}})\int p_{\widetilde{X}_{i}^{\mathsf{sc}}\,|\,\widetilde{X}_{{i-1}},Y,Z}({x}_{i}^{\mathsf{sc}}\,|\,{x}_{i-1},y,z)\notag\\ &\qquad\cdot \left(p_{\widetilde{X}_{{i-1}}^{\mathsf{c}}\,|\,\widetilde{X}_{{i-1}}^{\mathsf{s}},Y,Z}({x}_{i-1}^{\mathsf{c}}\,|\,{x}_{i-1}^{\mathsf{s}},y,z)-p_{{X}_{t_{i-1}}^{\mathsf{c}}\,|\,{X}_{t_{i-1}}^{\mathsf{s}}}({x}_{i-1}^{\mathsf{c}}\,|\,{x}_{i-1}^{\mathsf{s}})\right) \mathrm{d}{x}_{i-1}^{\mathsf{c}}\mathrm{d} {x}_i^{\mathsf{sc}}\Big]\notag\\ &\quad=\mathbb{E}_{x_{i-1}^{\mathsf{sc}}\sim p_{\widetilde{X}_{i-1}^{\mathsf{sc}}\,|\,Y,Z}}\Big[\int \left(\int f(x_i^{\mathsf{sc}},x_{i-1}^{\mathsf{s}}) p_{\widetilde{X}_{i}^{\mathsf{sc}}\,|\,\widetilde{X}_{{i-1}},Y,Z}({x}_{i}^{\mathsf{sc}}\,|\,{x}_{i-1},y,z)\mathrm{d} {x}_i^{\mathsf{sc}} \right)\notag\\ &\qquad\quad\cdot \left(p_{\widetilde{X}_{{i-1}}^{\mathsf{c}}\,|\,\widetilde{X}_{{i-1}}^{\mathsf{s}},Y,Z}({x}_{i-1}^{\mathsf{c}}\,|\,{x}_{i-1}^{\mathsf{s}},y,z)-p_{{X}_{t_{i-1}}^{\mathsf{c}}\,|\,{X}_{t_{i-1}}^{\mathsf{s}}}({x}_{i-1}^{\mathsf{c}}\,|\,{x}_{i-1}^{\mathsf{s}})\right) \mathrm{d}{x}_{i-1}^{\mathsf{c}}\Big] \notag\\ &\quad \le \mathbb{E}_{x_{i-1}^{\mathsf{sc}}\sim p_{\widetilde{X}_{i-1}^{\mathsf{sc}}\,|\,Y,Z}}\Big[\int \left(\int f(x_i^{\mathsf{sc}},x_{i-1}^{\mathsf{s}}) p_{\widetilde{X}_{i}^{\mathsf{sc}}\,|\,\widetilde{X}_{{i-1}},Y,Z}({x}_{i}^{\mathsf{sc}}\,|\,{x}_{i-1},y,z)\mathrm{d} {x}_i^{\mathsf{sc}} \right)^2\notag\\ &\qquad\qquad\cdot \left|p_{\widetilde{X}_{{i-1}}^{\mathsf{c}}\,|\,\widetilde{X}_{{i-1}}^{\mathsf{s}},Y,Z}({x}_{i-1}^{\mathsf{c}}\,|\,{x}_{i-1}^{\mathsf{s}},y,z)-p_{{X}_{t_{i-1}}^{\mathsf{c}}\,|\,{X}_{t_{i-1}}^{\mathsf{s}}}({x}_{i-1}^{\mathsf{c}}\,|\,{x}_{i-1}^{\mathsf{s}})\right| \mathrm{d}{x}_{i-1}^{\mathsf{c}}\Big]^{1/2}\notag\\ &\qquad\qquad \cdot\mathbb{E}_{x_{i-1}^{\mathsf{sc}}\sim p_{\widetilde{X}_{i-1}^{\mathsf{sc}}\,|\,Y,Z}}\Big[\int \left|p_{\widetilde{X}_{{i-1}}^{\mathsf{c}}\,|\,\widetilde{X}_{{i-1}}^{\mathsf{s}},Y,Z}({x}_{i-1}^{\mathsf{c}}\,|\,{x}_{i-1}^{\mathsf{s}},y,z)-p_{{X}_{t_{i-1}}^{\mathsf{c}}\,|\,{X}_{t_{i-1}}^{\mathsf{s}}}({x}_{i-1}^{\mathsf{c}}\,|\,{x}_{i-1}^{\mathsf{s}})\right| \mathrm{d}{x}_{i-1}^{\mathsf{c}}\Big]^{1/2} \to 0. \end{align}\tag{34}\] For the first term in the right-hand-side of 33 , note that it is the KL divergence between the marginal distribution of \(x_i^{\mathsf{sc}}\), and it is smaller than the KL divergence of the joint distribution of \(x_i^{\mathsf{sc}}\) and \(x_{i-1}^{\mathsf{c}}\). Therefore we have \[\begin{align} \label{eq:proof-22} &\int \log \frac{\int p_{\widetilde{X}_{i}^{\mathsf{sc}}\,|\,\widetilde{X}_{i-1},Y,Z}({x}_{i}^{\mathsf{sc}}\,|\,{x}_{i-1},y,z)p_{{X}_{t_{i-1}}^{\mathsf{c}}\,|\,{X}_{t_{i-1}}^{\mathsf{s}}}({x}_{i-1}^{\mathsf{c}}\,|\,{x}_{i-1}^{\mathsf{s}}) \mathrm{d}{x}_{i-1}^{\mathsf{c}}}{\int p_{{X}_{t_i}^{\mathsf{sc}}\,|\,{X}_{t_{i-1}}}({x}_{i}^{\mathsf{sc}}\,|\,{x}_{i-1})p_{{X}_{t_{i-1}}^{\mathsf{c}}\,|\,{X}_{t_{i-1}}^{\mathsf{s}}}({x}_{i-1}^{\mathsf{c}}\,|\,{x}_{i-1}^{\mathsf{s}}) \mathrm{d}{x}_{i-1}^{\mathsf{c}}}\notag\\ &\qquad \cdot\int p_{\widetilde{X}_{i}^{\mathsf{sc}}\,|\,\widetilde{X}_{i-1},Y,Z}({x}_{i}^{\mathsf{sc}}\,|\,{x}_{i-1},y,z)p_{{X}_{t_{i-1}}^{\mathsf{c}}\,|\,{X}_{t_{i-1}}^{\mathsf{s}}}({x}_{i-1}^{\mathsf{c}}\,|\,{x}_{i-1}^{\mathsf{s}}) \mathrm{d}{x}_{i-1}^{\mathsf{c}}\mathrm{d} {x}_i^{\mathsf{sc}}\notag\\ &\quad \le \iint \log \frac{p_{\widetilde{X}_{i}^{\mathsf{sc}}\,|\,\widetilde{X}_{{i-1}},Y,Z}({x}_{i}^{\mathsf{sc}}\,|\,{x}_{i-1},y,z)p_{{X}_{t_{i-1}}^{\mathsf{c}}\,|\,{X}_{t_{i-1}}^{\mathsf{s}}}({x}_{i-1}^{\mathsf{c}}\,|\,{x}_{i-1}^{\mathsf{s}})}{p_{{X}_{t_i}^{\mathsf{sc}}\,|\,{X}_{t_{i-1}}}({x}_{i}^{\mathsf{sc}}\,|\,{x}_{i-1})p_{{X}_{t_{i-1}}^{\mathsf{c}}\,|\,{X}_{t_{i-1}}^{\mathsf{s}}}({x}_{i-1}^{\mathsf{c}}\,|\,{x}_{i-1}^{\mathsf{s}}) }\notag\\ &\qquad\qquad\times p_{\widetilde{X}_{i}^{\mathsf{sc}}\,|\,\widetilde{X}_{{i-1}},Y,Z}({x}_{i}^{\mathsf{sc}}\,|\,{x}_{i-1},y,z)p_{{X}_{t_{i-1}}^{\mathsf{c}}\,|\,{X}_{t_{i-1}}^{\mathsf{s}}}({x}_{i-1}^{\mathsf{c}}\,|\,{x}_{i-1}^{\mathsf{s}}) \mathrm{d}{x}_{i-1}^{\mathsf{c}} \mathrm{d} {x}_i^{\mathsf{sc}} \notag\\ &\quad = \mathbb{E}_{{x}_{i-1}^{\mathsf{c}}\sim X_{t_{i-1}}^{\mathsf{c}}\,|\,X_{t_{i-1}}^{\mathsf{s}}}\big[\mathsf{KL}(p_{\widetilde{X}_{i}^{\mathsf{sc}}\,|\,\widetilde{X}_{{i-1}},Y,Z}(\cdot\,|\,{x}_{i-1},y,z)\,\Vert\, p_{{X}_{t_i}^{\mathsf{sc}}\,|\,{X}_{t_{i-1}}}(\cdot\,|\,{x}_{i-1}) )\big]. \end{align}\tag{35}\] Substituting 35 and 34 into 33 , we have \[\begin{align} \label{eq:proof-28} &\int \log \frac{\int p_{\widetilde{X}_{i}^{\mathsf{sc}}\,|\,\widetilde{X}_{{i-1}},Y,Z}({x}_{i}^{\mathsf{sc}}\,|\,{x}_{i-1},y,z)p_{{X}_{t_{i-1}}^{\mathsf{c}}\,|\,{X}_{t_{i-1}}^{\mathsf{s}}}({x}_{i-1}^{\mathsf{c}}\,|\,{x}_{i-1}^{\mathsf{s}}) \mathrm{d}{x}_{i-1}^{\mathsf{c}}}{\int p_{{X}_{t_i}^{\mathsf{sc}}\,|\,{X}_{t_{i-1}},Y,Z}({x}_{i}^{\mathsf{sc}}\,|\,{x}_{i-1})p_{{X}_{t_{i-1}}^{\mathsf{c}}\,|\,{X}_{t_{i-1}}^{\mathsf{s}}}({x}_{i-1}^{\mathsf{c}}\,|\,{x}_{i-1}^{\mathsf{s}}) \mathrm{d}{x}_{i-1}^{\mathsf{c}}} p_{\widetilde{X}_{i}^{\mathsf{sc}}\,|\,\widetilde{X}_{{i-1}}^{\mathsf{s}},Y,Z}({x}_i^{\mathsf{sc}}\,|\,{x}_{i-1}^{\mathsf{s}},y,z)\mathrm{d} {x}_i^{\mathsf{sc}}\notag\\ &\qquad \to \mathbb{E}_{{x}_{i-1}^{\mathsf{c}}\sim X_{t_{i-1}}^{\mathsf{c}}\,|\,X_{t_{i-1}}^{\mathsf{s}}}\big[\mathsf{KL}(p_{\widetilde{X}_{i}^{\mathsf{sc}}\,|\,\widetilde{X}_{{i-1}},Y,Z}(\cdot\,|\,{x}_{i-1},y,z)\,\Vert\, p_{{X}_{t_i}^{\mathsf{sc}}\,|\,{X}_{t_{i-1}}}(\cdot\,|\,{x}_{i-1}) )\big]. \end{align}\tag{36}\] Combining 30 , 32 and 36 , we have \[\begin{align} \label{eq:proof-23} &\lim \mathsf{TV}\bigg( p_{\widetilde{X}_k^{\mathsf{sc}}\,|\,Y,Z}, p_{\overline{X}_{k}^{\mathsf{sc}}\,|\,Y,Z}\bigg)^2 \notag\\ &\quad\le \lim \sum_{i=1}^k\mathbb{E}_{{x}_{i-1}^{\mathsf{s}}\sim \widetilde{X}_{i-1}^{\mathsf{s}}\,|\,Y,Z}\bigg[\mathbb{E}_{{x}_{i-1}^{\mathsf{c}}\sim X_{t_{i-1}}^{\mathsf{c}}\,|\,X_{t_{i-1}}^{\mathsf{s}}}\big[\mathsf{KL}(p_{\widetilde{X}_{i}^{\mathsf{sc}}\,|\,\widetilde{X}_{{i-1}},Y,Z}(\cdot\,|\,{x}_{i-1},y,z)\,\Vert\, p_{{X}_{t_i}^{\mathsf{sc}}\,|\,{X}_{t_{i-1}}}(\cdot\,|\,{x}_{i-1}))\big]\bigg]\notag\\ &\qquad +\lim\sum_{i=1}^k\mathbb{E}_{{x}_{i-1}^{\mathsf{s}}\sim \widetilde{X}_{i-1}^{\mathsf{s}}\,|\,Y,Z}\bigg[\int \log \frac{\int p_{\widetilde{X}_{i}^{\mathsf{sc}}\,|\,\widetilde{X}_{{i-1}},Y,Z}({x}_{i}^{\mathsf{sc}}\,|\,{x}_{i-1},y,z)p_{\widetilde{X}_{i-1}^{\mathsf{c}}\,|\,\widetilde{X}_{{i-1}}^{\mathsf{s}},Y,Z}({x}_{i-1}^{\mathsf{c}}\,|\,{x}_{i-1}^{\mathsf{s}},y,z) \mathrm{d}{x}_{i-1}^{\mathsf{c}}}{\int p_{\widetilde{X}_{i}^{\mathsf{sc}}\,|\,\widetilde{X}_{{i-1}},Y,Z}({x}_{i}^{\mathsf{sc}}\,|\,{x}_{i-1},y,z)p_{{X}_{t_{i-1}}^{\mathsf{c}}\,|\,{X}_{t_{i-1}}^{\mathsf{s}},Y,Z}({x}_{i-1}^{\mathsf{c}}\,|\,{x}_{i-1}^{\mathsf{s}},y,z) \mathrm{d}{x}_{i-1}^{\mathsf{c}}}\notag\\ &\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\times p_{\widetilde{X}_{i}^{\mathsf{sc}}\,|\,\widetilde{X}_{{i-1}}^{\mathsf{s}},Y,Z}({x}_i^{\mathsf{sc}}\,|\,{x}_{i-1}^{\mathsf{s}},y,z)\mathrm{d} {x}_i^{\mathsf{sc}}\bigg]. \end{align}\tag{37}\]

6.0.0.4 Step 4. control error terms.

Particularly, with \(\eta_0 = 1\) which corresponds to DDPM, we have the following result, whose proof is postponed to Appendix 7.5.

By using Lemma 3, and notice that \(\widetilde{X}_{i}^{\mathsf{sc}}\,|\,\widetilde{X}_{i-1},Y,Z\) shares the same transition probability as \(\widehat{X}_{t_i}^{\mathsf{sc}}\,|\,\widehat{X}_{t_{i-1}}\), we have \[\begin{align} \label{eq:proof-19} &\sum_{i=1}^k\mathbb{E}_{{x}_{i-1}^{\mathsf{s}}\sim \widetilde{X}_{i-1}^{\mathsf{s}}\,|\,Y,Z}\bigg[\mathbb{E}_{{x}_{i-1}^{\mathsf{c}}\sim X_{t_{i-1}}^{\mathsf{c}}\,|\,X_{t_{i-1}}^{\mathsf{s}}}\big[\mathsf{KL}(p_{\widetilde{X}_{i}^{\mathsf{sc}}\,|\,\widetilde{X}_{{i-1}},Y,Z}(\cdot\,|\,{x}_{i-1},y,z)\,\Vert\, p_{{X}_{t_i}^{\mathsf{sc}}\,|\,{X}_{t_{i-1}}}(\cdot\,|\,{x}_{i-1}))\big]\bigg]\notag\\ &\quad = \sum_{i=1}^k\mathbb{E}_{{x}_{i-1}^{\mathsf{s}}\sim \widetilde{X}_{i-1}^{\mathsf{s}}\,|\,Y,Z; ~{x}_{i-1}^{\mathsf{c}}\sim X_{t_{i-1}}^{\mathsf{c}}\,|\,X_{t_{i-1}}^{\mathsf{s}}={x}_{i-1}^{\mathsf{s}}}\bigg[\mathsf{KL}(p_{\widehat{X}_{t_i}^{\mathsf{sc}}\,|\,\widehat{X}_{t_{i-1}}}(\cdot\,|\,{x}_{i-1})\,\Vert\, p_{{X}_{t_i}^{\mathsf{sc}}\,|\,{X}_{t_{i-1}}}(\cdot\,|\,{x}_{i-1}))\bigg] \notag\\ &\quad = \sum_{i=1}^k o(\delta_i)\to 0,~\mathrm{as}~ \delta \to 0. \end{align}\tag{38}\] The second term describes the influence of the sampling error of \(x_{i-1}^{\mathsf{c}}\) on the distribution of \(x_i^{\mathsf{sc}}\). It is given by the following lemma, whose proof is postponed to Section 7.6.

Combining 38 and Lemma 4 together with 37 , we have \[\begin{align} \mathsf{TV}\big( p_{\widetilde{X}_k^{\mathsf{sc}}\,|\,Y,Z}, p_{\overline{X}_{k}^{\mathsf{sc}}\,|\,Y,Z}\big) \to 0. \end{align}\] Thus we complete the proof.

7 Proof of auxiliary lemmas and facts↩︎

7.1 Proof of 18↩︎

We first present the conclusion as the following lemma, and then prove it.

7.2 Preliminaries↩︎

Throughout the proof, we redefine \(\eta_1\) as \(\eta\) for ease of notations. We begin with approximating the update rule 19 for \(\widehat{X}_{t_i}^{\mathsf{c}}\). We have \[\begin{align} \label{eq:proof-update-0} \widehat{X}_{t_{i+1}}^{\mathsf{c}} &= \frac{\sigma_{t_{i+1}}}{\sigma_{t_{i}}}\sqrt{1-\eta(1 - e^{-2\delta_{i+1}})}\widehat{X}_{t_{i}}^{\mathsf{c}} + \alpha_{t_{i+1}}\big(1 - e^{-\delta_{i+1}}\sqrt{1-\eta(1 - e^{-2\delta_{i+1}})}\big)\mu_{t_{i}}^{\mathsf{c}}(\widehat{X}_{t_i})\notag\\ &\qquad + \sigma_{t_{i+1}}\sqrt{\eta(1 - e^{-2\delta_{i+1}})} Z_{t_i}^{\mathsf{c}}. \end{align}\tag{40}\] For the first term, we have \[\begin{align} \label{eq:proof-update-1} \frac{\sigma_{t_{i+1}}}{\sigma_{t_{i}}}\sqrt{1-\eta(1 - e^{-2\delta_{i+1}})}\widehat{X}_{t_{i}}^{\mathsf{c}} &= \sqrt{1-\eta(1 - e^{-2\delta_{i+1}})}\widehat{X}_{t_{i}}^{\mathsf{c}} + \left(\frac{\sigma_{t_{i+1}}}{\sigma_{t_{i}}}-1\right)\sqrt{1-\eta(1 - e^{-2\delta_{i+1}})}\widehat{X}_{t_{i}}^{\mathsf{c}}\notag\\ & \eqqcolon \sqrt{1-\eta(1 - e^{-2\delta_{i+1}})}\widehat{X}_{t_{i}}^{\mathsf{c}} + e_{t_i,1}(\widehat{X}_{t_{i}}^{\mathsf{c}} ). \end{align}\tag{41}\] For the second term, we have \[\begin{align} \label{eq:proof-update-2} &\alpha_{t_{i+1}}\big(1 - e^{-\delta_{i+1}}\sqrt{1-\eta(1 - e^{-2\delta_{i+1}})}\big)\mu_{t_{i}}^{\mathsf{c}}(\widehat{X}_{t_i}) \notag\\ &\quad = \alpha_{t_{i}}\big(1 - \sqrt{1-\eta(1 - e^{-2\delta_{i+1}})}\big)\mu_{t_{i}}^{\mathsf{c}}(\widehat{X}_{t_i})\notag\\ &\qquad + \underbrace{\big(\left(\alpha_{t_{i+1}}-\alpha_{t_i}\right) + \left(\alpha_{t_{i+1}}e^{-\delta_{i+1}}-\alpha_{t_i}\right)\sqrt{1-\eta(1 - e^{-2\delta_{i+1}})}\big)\mu_{t_{i}}^{\mathsf{c}}(\widehat{X}_{t_i})}_{e_{t_i,2}(\widehat{X}_{t_{i}} )}\notag\\ &\quad = \big(1 - e^{-\delta_{i+1}}\sqrt{1-\eta(1 - e^{-2\delta_{i+1}})}\big)\left(\widehat{X}_{t_{i}}^{\mathsf{c}} - \sigma_{t_{i}}\epsilon_{t_{i}}^{\mathsf{c}}(\widehat{X}_{t_{i}} )\right) + e_{t_i,2}(\widehat{X}_{t_{i}})\notag\\ &\quad =\big(1 - \sqrt{1-\eta(1 - e^{-2\delta_{i+1}})}\big)\left(\widehat{X}_{t_{i}}^{\mathsf{c}} - \sigma_{t_{i+1}}\epsilon_{t_{i+1}}^{\mathsf{c}}(\widehat{X}_{t_{i+1}}^{\mathsf{est}} )\right) + e_{t_i,2}(\widehat{X}_{t_{i}} ) \notag\\ &\qquad + \underbrace{\big(1 - \sqrt{1-\eta(1 - e^{-2\delta_{i+1}})}\big)\big(\sigma_{t_{i}}\epsilon_{t_{i}}^{\mathsf{c}}(\widehat{X}_{t_{i}} )-\sigma_{t_{i+1}}\epsilon_{t_{i+1}}^{\mathsf{c}}(\widehat{X}_{t_{i+1}}^{\mathsf{est}} )\big)}_{e_{t_i,3}(\widehat{X}_{t_{i}},\widehat{X}_{t_{i+1}}^{\mathsf{s}} )}, \end{align}\tag{42}\] where \(\widehat{X}_{t_{i+1}}^{\mathsf{est}}\) is defined by \(V_{\mathcal{S}^{\mathsf{c}}}^{\top}\widehat{X}_{t_{i+1}}^{\mathsf{est}} = \widehat{X}_{t_{i}}^{\mathsf{c}}\) and \(V_{\mathcal{S}}^{\top}\widehat{X}_{t_{i+1}}^{\mathsf{est}} = \widehat{X}_{t_{i+1}}^{\mathsf{s}}\). Note that \[\begin{align} \label{eq:def-epsc} \epsilon_{t_{i}}^{\mathsf{c}}(x) &\mathrel{\vcenter{:}}= \frac{1}{\sigma_{t_i}}\mathbb{E}[x^{\mathsf{c}}-\alpha_{t_i}X_{0}^{\mathsf{c}}\,|\,X_{t_i}=x] = -\sigma_{t_i}\nabla_{x^{\mathsf{c}}} \log p_{X_{t_i}^{\mathsf{c}}|X_{t_i}^{\mathsf{s}}}(x^{\mathsf{c}}|x^{\mathsf{s}}), \end{align}\tag{43}\] where \(X_{t_i}\overset{\text{d}}{=}\alpha_{t_i} X_0 + \sigma_{t_i}\mathcal{N}(0,I_d)\), and the second equation holds because \[\begin{align} \label{eq:nablap-exp} \nabla_{x^{\mathsf{c}}} \log p_{X_{t_i}^{\mathsf{c}}|X_{t_i}^{\mathsf{s}}}(x^{\mathsf{c}}|x^{\mathsf{s}}) = \nabla_{x^{\mathsf{c}}} \log p_{X_{t_i}}(x) = -\frac{1}{\sigma_{t_i}^2}\mathbb{E}[x^{\mathsf{c}}-\alpha_{t_i}X_{0}^{\mathsf{c}}|X_{t_i}=x]. \end{align}\tag{44}\] Combining 41 and 42 together with 40 , we have \[\begin{align} \label{eq:proof-update-3} \widehat{X}_{t_{i+1}}^{\mathsf{c}} &= \widehat{X}_{t_{i}}^{\mathsf{c}} - \sigma_{t_{i+1}}\big(1 - \sqrt{1-\eta(1 - e^{-2\delta_{i+1}})}\big)\epsilon_{t_{i+1}}^{\mathsf{c}}(\widehat{X}_{t_{i+1}}^{\mathsf{est}} ) + \sigma_{t_{i+1}}\sqrt{\eta(1 - e^{-2\delta_{i+1}})} Z_{t_i}^{\mathsf{c}}\notag\\ &\quad + e_{t_i,1}(\widehat{X}_{t_{i}}^{\mathsf{c}} )+ e_{t_i,2}(\widehat{X}_{t_{i}} )+ e_{t_i,3}(\widehat{X}_{t_{i}},\widehat{X}_{t_{i+1}}^{\mathsf{s}})\notag\\ &\eqqcolon \widehat{X}_{t_{i}}^{\mathsf{c}} - \frac{\eta(1 - e^{-2\delta_{i+1}})}{2}\sigma_{t_{i+1}}\epsilon_{t_{i+1}}^{\mathsf{c}}(\widehat{X}_{t_{i+1}}^{\mathsf{est}})+ \sigma_{t_{i+1}}\sqrt{\eta(1 - e^{-2\delta_{i+1}})} Z_{t_i}^{\mathsf{c}} + e_{t_i}(\widehat{X}_{t_{i}},\widehat{X}_{t_{i+1}}^{\mathsf{s}}) \end{align}\tag{45}\] where \(e_{t_i}(\widehat{X}_{t_{i}},\widehat{X}_{t_{i+1}}^{\mathsf{s}} )\) is defined as \[\begin{align} \label{eq:def-et} e_{t_i}(\widehat{X}_{t_{i}},\widehat{X}_{t_{i+1}}^{\mathsf{s}} ) &\mathrel{\vcenter{:}}= e_{t_i,1}(\widehat{X}_{t_{i}}^{\mathsf{c}} ) + e_{t_i,2}(\widehat{X}_{t_{i}} )+ e_{t_i,3}(\widehat{X}_{t_{i}},\widehat{X}_{t_{i+1}}^{\mathsf{s}} )\notag\\ &\qquad + \Bigg(1 - \sqrt{1-\eta(1 - e^{-2\delta_{i+1}})} - \frac{\eta(1 - e^{-2\delta_{i+1}})}{2}\Bigg)\sigma_{t_{i+1}}\epsilon_{t_{i+1}}^{\mathsf{c}}(\widehat{X}_{t_{i+1}}^{\mathsf{est}}). \end{align}\tag{46}\] We have the following lemma, whose proof is postponed to Appendix 7.7.

Next, we rewrite the update rule 19 for \(\widehat{X}_{t_i}^{\mathsf{sc}}\). When \(\eta_0=1\), it is equivalent to \[\begin{align} \label{eq:proof-alg-xsc} \widehat{X}_{t_{i+1}}^{\mathsf{sc}} &= \frac{\sigma_{t_{i+1}}}{\sigma_{t_{i}}} e^{-\delta_{i+1}} \widehat{X}_{t_{i}}^{\mathsf{sc}}+ \sigma_{t_{i+1}}e^{\lambda_{t_{i+1}}}\big(1 - e^{-2\delta_{i+1}}\big)\mu_{t_{i}}^{\mathsf{sc}}(\widehat{X}_{t_i}) + \sigma_{t_{i+1}}\sqrt{1 - e^{-2\delta_{i+1}}} Z_{t_i}^{\mathsf{sc}}\notag\\ &=\frac{\sigma_{t_{i+1}}}{\sigma_{t_{i}}} e^{-\delta_{i+1}} \widehat{X}_{t_{i}}^{\mathsf{sc}}+ \frac{\alpha_{t_{i+1}}}{\alpha_{t_i}}\big(1 - e^{-2\delta_{i+1}}\big)(\widehat{X}_{t_{i}}^{\mathsf{sc}}-\sigma_{t_i}\epsilon_{t_{i}}^{\mathsf{sc}}) + \sigma_{t_{i+1}}\sqrt{1 - e^{-2\delta_{i+1}}} Z_{t_i}^{\mathsf{sc}}\notag\\ &=\left(\frac{\sigma_{t_{i+1}}}{\sigma_{t_{i}}} e^{-\delta_{i+1}} + \frac{\alpha_{t_{i+1}}}{\alpha_{t_i}} - \frac{\alpha_{t_{i+1}}}{\alpha_{t_i}}e^{-2\delta_{i+1}}\right)\widehat{X}_{t_{i}}^{\mathsf{sc}} - \frac{\alpha_{t_{i+1}}}{\alpha_{t_i}}\big(1 - e^{-2\delta_{i+1}}\big)\sigma_{t_i}\epsilon_{t_{i}}^{\mathsf{sc}} + \sigma_{t_{i+1}}\sqrt{1 - e^{-2\delta_{i+1}}} Z_{t_i}^{\mathsf{sc}}\notag\\ &=\frac{\alpha_{t_{i+1}}}{\alpha_{t_i}}\widehat{X}_{t_{i}}^{\mathsf{sc}} - \alpha_{t_{i+1}}\left({\rm e}^{-\lambda_{t_i}}-{\rm e}^{-2\lambda_{t_{i+1}}+\lambda_{t_{i}}}\right)\epsilon_{t_{i}}^{\mathsf{sc}} + \sigma_{t_{i+1}}\sqrt{1 - e^{-2\delta_{i+1}}} Z_{t_i}^{\mathsf{sc}}\notag\\ &=\frac{\alpha_{t_{i+1}}}{\alpha_{t_i}}\widehat{X}_{t_{i}}^{\mathsf{sc}} - \frac{\alpha_{t_{i+1}}\sigma_{t_i}}{\alpha_{t_i}}\left(1-{\rm e}^{-2\delta_{i+1}}\right)\epsilon_{t_{i}}^{\mathsf{sc}} + \sigma_{t_{i+1}}\sqrt{1 - e^{-2\delta_{i+1}}} Z_{t_i}^{\mathsf{sc}}. \end{align}\tag{47}\]

7.3 Proof of Lemma 1↩︎

Combining 18 , 45 and 47 , the update rule of \(\widehat{X}_{t_k}\) can be rewritten as \[\begin{align} \widehat{X}_{t_{k+1}}^{\mathsf{st}} &=\alpha_{t_{k+1}}\overline{Y}_{t_{k+1}} + \widehat{\sigma}_{t_{k+1}}\overline{Z}_{t_{k+1}},\notag\\ \widehat{X}_{t_{k+1}}^{\mathsf{sc}}&=\frac{\alpha_{t_{k+1}}}{\alpha_{t_k}}\widehat{X}_{t_{k}}^{\mathsf{sc}} + \alpha_{t_{k+1}}\left({\rm e}^{-\lambda_{t_k}}-{\rm e}^{-2\lambda_{t_{k+1}}+\lambda_{t_{k}}}\right)\frac{\nabla_{\widehat{X}_{t_k}^{\mathsf{sc}}} \log p_{\lambda_k}(\widehat{X}_{t_k}^{\mathsf{c}},\widehat{X}_{t_k}^{\mathsf{sc}})}{\sigma_{t_k}} + \sigma_{t_{k+1}}\sqrt{1 - e^{-2\delta_{k+1}}} Z_{t_k}^{\mathsf{sc}},\notag\\ \widehat{X}_{t_{k+1}}^{\mathsf{c}} &= \widehat{X}_{t_{k}}^{\mathsf{c}} +\gamma_k\nabla \log p_{\lambda_{k+1}}(\widehat{X}_{t_k}^{\mathsf{c}},\widehat{X}_{t_{k+1}}^{\mathsf{sc}}) + \sigma_{t_{k+1}}\sqrt{\eta(1 - e^{-2\delta_{k+1}})} Z_{t_k}^{\mathsf{c}} + e_{t_k}(\widehat{X}_{t_{k}},\widehat{X}_{t_{k+1}}^{\mathsf{sc}}). \end{align}\]

The KL divergence between \(\widehat{X}_{t_{0:M}}\) and \(\widetilde{X}_{0:M}\) conditoned on \(Y\) and \(Z\) can be decomposed as \[\begin{align} \mathsf{KL}(p_{\widetilde{X}_{0:M}\,|\,Y,Z}\Vert p_{\widehat{X}_{t_{0:M}}\,|\,Y,Z}) &= \mathsf{KL}(p_{\widetilde{X}_{0}\,|\,Y,Z}\Vert p_{\widehat{X}_{t_{0}}\,|\,Y,Z}) + \sum_{i=0}^{M-1} \mathbb{E}_{x\sim p_{\widetilde{X}_{t_{i}}\,|\,Y,Z}} \mathsf{KL}\big(p_{\widetilde{X}_{i+1}^{\mathsf{sc}}|\widetilde{X}_{i}}(\cdot|x) \Vert p_{\widehat{X}_{t_{i+1}}^{\mathsf{sc}}|\widehat{X}_{t_i}}(\cdot|x)\big)\notag\\ &\quad +\sum_{i=0}^{M-1} \mathbb{E}_{x,x'\sim p_{\widetilde{X}_{i+1}^{\mathsf{sc}},\widetilde{X}_i\,|\,Y,Z}} \mathsf{KL}\big(p_{\widetilde{X}_{i+1}^{\mathsf{c}}|\widetilde{X}_{i+1}^{\mathsf{sc}},\widetilde{X}_{i}}(\cdot|x,x') \Vert p_{\widehat{X}_{t_{i+1}}^{\mathsf{c}}|\widehat{X}_{t_{i+1}}^{\mathsf{sc}},\widehat{X}_{t_i}}(\cdot|x,x')\big)\notag\\ &=\sum_{i=0}^{M-1} \mathbb{E}_{x,x'\sim p_{\widetilde{X}_{i+1}^{\mathsf{sc}},\widetilde{X}_i\,|\,Y,Z}} \mathsf{KL}\big(p_{\widetilde{X}_{i+1}^{\mathsf{c}}|\widetilde{X}_{i+1}^{\mathsf{sc}},\widetilde{X}_{i}}(\cdot|x,x') \Vert p_{\widehat{X}_{t_{i+1}}^{\mathsf{c}}|\widehat{X}_{t_{i+1}}^{\mathsf{sc}},\widehat{X}_{t_i}}(\cdot|x,x')\big). \end{align}\] Note that the both of the above conditional distributions are Gaussian ditributions with variance \(2\gamma_i\) and mean vector \((x')^{\mathsf{c}}+\gamma_i\nabla \log p_{\lambda_{i+1}}((x')^{\mathsf{c}},x^{\mathsf{sc}})+e_{t_i}(x',x^{\mathsf{sc}})\) and \((x')^{\mathsf{c}}+\gamma_i\nabla \log p_{\lambda_{i+1}}((x')^{\mathsf{c}},x^{\mathsf{sc}})\), respectively. Combining with Lemma 6, we finally get \[\begin{align} &\mathbb{E}_{x,x'\sim p_{\widetilde{X}_{i+1}^{\mathsf{sc}},\widetilde{X}_i\,|\,Y,Z}} \big[\mathsf{KL}\big(p_{\widetilde{X}_{i+1}^{\mathsf{c}}|\widetilde{X}_{i+1}^{\mathsf{sc}},\widetilde{X}_{i}}(\cdot|x,x') \Vert p_{\widehat{X}_{t_{i+1}}^{\mathsf{c}}|\widehat{X}_{t_{i+1}}^{\mathsf{sc}},\widehat{X}_{t_i}}(\cdot|x,x')\big)\big]\notag\\ &\quad = \frac{\mathbb{E}_{x,x'\sim p_{\widetilde{X}_{i+1}^{\mathsf{sc}},\widetilde{X}_i}\,|\,Y,Z} \big[\|e_{t_i}(x', x)\|_2^2\big]}{4\gamma_i}\notag\\ &\quad \lesssim \frac{1}{\gamma_i}\left(\mathbb{E}\bigg[\bigg(\|\widetilde{X}_{i}^{\mathsf{c}}\|_2 +\|\widetilde{X}_{i}^{\mathsf{sc}}\|_2 + \|Z\|_2+ 1\bigg)^2\bigg]\right)(\delta_{{i+1}}^2+\gamma_i^4) + \delta_{{i+1}}\gamma_i. \end{align}\] Summarizing from \(i=0\) to \(M-1\) yields \[\begin{align} &\sum_{i=0}^{M-1}\mathbb{E}_{x,x'\sim p_{\widetilde{X}_{i+1}^{\mathsf{sc}},\widetilde{X}_i\,|\,Y,Z}} \big[\mathsf{KL}\big(p_{\widetilde{X}_{i+1}^{\mathsf{c}}|\widetilde{X}_{i+1}^{\mathsf{sc}},\widetilde{X}_{i}}(\cdot|x,x') \Vert p_{\widehat{X}_{t_{i+1}}^{\mathsf{c}}|\widehat{X}_{t_{i+1}}^{\mathsf{sc}},\widehat{X}_{t_i}}(\cdot|x,x')\big)\big]\notag\\ & \quad\overset{\text{(i)}}{\lesssim} \max\frac{\delta_{{i+1}}}{\gamma_i} + \eta \max\gamma_i^2 + \max\gamma_i \overset{\text{(ii)}}{\lesssim} \frac{1}{\eta} + \eta \max\gamma_i^2 + \max\gamma_i\notag\\ &\quad =O\big(\eta^{-1}\big) + O(\eta^3\delta^2) + O(\eta\delta), \end{align}\] where (i) uses \(\sum_{i=0}^{M-1}\delta_{{i+1}} = O(1)\), \(\sum_{i=0}^{M-1}\gamma_{i} = O(\eta)\), and \(\mathbb{E}[\|\widetilde{X}_{i}^{\mathsf{c}}\|_2^2+\|\widetilde{X}_{i}^{\mathsf{sc}}\|_2^2+\|Z\|_2^2]=O(1)\), and (ii) uses 22 . As \(\eta^3\delta^2\to 0\) and \(\eta\to\infty\), which is satisfied by \(\eta=\Theta(\delta^{-7/12})\), we have \(\mathsf{KL}\big(p_{\widetilde{X}_{0:M}\,|\,Y,Z}\Vert p_{\widehat{X}_{t_{0:M}}\,|\,Y,Z}\big)\to 0\) and complete the proof.

Next, we intend to prove that \(p_{\overline{X}_{k} \,|\,V_{\mathcal{S}_{t_k}^{\mathsf{meas}}}^{\top}\overline{X}_{k}, v_{s}^{\top}\overline{X}_{k_{\tau_s}}} = p_{X_{t_k} \,|\,V_{\mathcal{S}_{t_k}^{\mathsf{meas}}}^{\top}X_{t_k}, v_{s}^{\top}X_{\tau_s}}\). When \(\sigma_{t_k}>\alpha_{t_k} \Sigma_{ss}^{-1}\sigma\), we have \(\mathcal{S}_{t_k}^{\mathsf{meas}}=\mathcal{S}\) and \(\mathcal{S}_{t_k}^{\mathsf{prior}}\) is empty. Thus we have \[\begin{align} p_{\overline{X}_{k} \,|\,V_{\mathcal{S}_{t_k}^{\mathsf{meas}}}^{\top}\overline{X}_{k}, v_{s}^{\top}\overline{X}_{k_{\tau_s}}} =p_{\overline{X}_{k} \,|\,V_{\mathcal{S}_{t_k}^{\mathsf{meas}}}^{\top}\overline{X}_{k}} = p_{X_{t_k} \,|\,V_{\mathcal{S}_{t_k}^{\mathsf{meas}}}^{\top}X_{t_k}}=p_{{X}_{t_k} \,|\,V_{\mathcal{S}_{t_k}^{\mathsf{meas}}}^{\top}{X}_{t_k}, v_{s}^{\top}{X}_{{\tau_s}}} , \end{align}\] which makes Lemma 1 hold obviously. In particular, this leads to the following equation when \(t_i=\tau_s\): \[\begin{align} p_{\overline{X}_{k_{\tau_s}} \,|\,V_{\mathcal{S}}^{\top}\overline{X}_{k_{\tau_s}}}= p_{X_{\tau_s} \,|\,V_{\mathcal{S}}^{\top}X_{\tau_s}}. \end{align}\] When \(\sigma_{t_k}\le\alpha_{t_k} \Sigma_{ss}^{-1}\sigma\), we have \(\mathcal{S}_{t_k}^{\mathsf{prior}}=\mathcal{S}\) and \(\mathcal{S}_{t_k}^{\mathsf{meas}}\) is empty. Thus we have \[\begin{align} p_{\overline{X}_{k} \,|\,\overline{X}_{{k-1}}} =p_{\overline{X}_{k}^{\mathsf{c}} \,|\,\overline{X}_{k}^{\mathsf{s}}}p_{\overline{X}_{k}^{\mathsf{s}} \,|\,\overline{X}_{{k-1}}} = p_{{X}_{t_k}^{\mathsf{c}} \,|\,{X}_{t_k}^{\mathsf{s}}}p_{{X}_{t_k}^{\mathsf{s}} \,|\,{X}_{t_{k-1}}} =p_{{X}_{t_k} \,|\,{X}_{t_{k-1}}}. \end{align}\] Therefore we have \[\begin{align} p_{\overline{X}_{k} \,|\,V_{\mathcal{S}_{t_k}^{\mathsf{meas}}}^{\top}\overline{X}_{k}, v_{s}^{\top}\overline{X}_{k_{\tau_s}}}(x_k\,|\,\cdot, x_{\tau_s}^{\mathsf{s}}) &= p_{\overline{X}_{k} \,|\,V_{\mathcal{S}}^{\top}\overline{X}_{k_{\tau_s}}}(x_k\,|\,x_{\tau_s}^{\mathsf{s}}) \notag\\ &= \int \prod_{j=k_{\tau_s}+1}^{k} p_{\overline{X}_{j} \,|\,\overline{X}_{{j-1}}}(x_j\,|\,x_{j-1}) p_{\overline{X}_{k_{\tau_s}} \,|\,V_{\mathcal{S}}^{\top}\overline{X}_{k_{\tau_s}}}(x_{\tau_s}\,|\,x_{\tau_s}^{\mathsf{s}}) \prod_{j=k_{\tau_s}+1}^{k-1}\mathrm{d} x_j\mathrm{d} x_{\tau_s}^{\mathsf{c}}\notag\\ &= \int \prod_{j=k_{\tau_s}+1}^{k} p_{{X}_{t_j} \,|\,{X}_{t_{j-1}}}(x_j\,|\,x_{j-1}) p_{{X}_{\tau_s} \,|\,V_{\mathcal{S}}^{\top}{X}_{\tau_s}}(x_{\tau_s}\,|\,x_{\tau_s}^{\mathsf{s}}) \prod_{j=k_{\tau_s}+1}^{k-1}\mathrm{d} x_j\mathrm{d} x_{\tau_s}^{\mathsf{c}}\notag\\ &=p_{{X}_{t_k} \,|\,V_{\mathcal{S}}^{\top}{X}_{\tau_s}}(x_k\,|\,x_{\tau_s}^{\mathsf{s}})=p_{{X}_{t_k} \,|\,V_{\mathcal{S}_{t_k}^{\mathsf{meas}}}^{\top}{X}_{t_k}, v_{s}^{\top}{X}_{\tau_s}}(x_k\,|\,\cdot, x_{\tau_s}^{\mathsf{s}}). \end{align}\]

7.4 Proof of Lemma 2↩︎

According to Lemma 1, it sufficies to prove that \[\begin{align} \label{eq:proof-lem-distri-sc-5} \mathbb{E}_{V_{\mathcal{S}}^{\top}\widetilde{X}_k\,|\,Y,Z}\big[\mathsf{TV}(p_{V_{\mathcal{S}^{\mathsf{c}}}^{\top}\widetilde{X}_k|V_{\mathcal{S}}^{\top}\widetilde{X}_k,Y,Z},\Vert p_{V_{\mathcal{S}^{\mathsf{c}}}^{\top}{X}_{t_k}|V_{\mathcal{S}}^{\top}{X}_{t_k}} )\big] \to 0\qquad \mathsf{as}\qquad \delta\eta\log\frac{1}{\delta} \to 0\quad \mathrm{and}\quad \frac{\delta\eta^2}{\log\frac{1}{\delta}}\to\infty. \end{align}\tag{48}\] Then by using Lemma 1, we have \[\begin{align} &\mathbb{E}_{x_k^{\mathsf{s}}\sim \widehat{X}_{t_k}^{\mathsf{s}}}\big[\mathsf{TV}(p_{V_{\mathcal{S}^{\mathsf{c}}}^{\top}\widehat{X}_{t_k}|V_{\mathcal{S}}^{\top}\widehat{X}_{t_k}}(\cdot\,|\,x_k^{\mathsf{s}}), p_{V_{\mathcal{S}^{\mathsf{c}}}^{\top}X_{t_k}|V_{\mathcal{S}}^{\top}X_{t_k}}(\cdot\,|\,x_k^{\mathsf{s}}) ) \big]\notag\\ &\quad= \mathbb{E}_{x_k^{\mathsf{s}}\sim \widehat{X}_{t_k}^{\mathsf{s}}}\big[\mathsf{TV}(p_{\widehat{X}_{t_k}^{\mathsf{c}}|\widehat{X}_{t_k}^{\mathsf{s}}}(\cdot\,|\,x_k^{\mathsf{s}}), p_{X_{t_k}^{\mathsf{c}}|X_{t_k}^{\mathsf{s}}}(\cdot\,|\,x_k^{\mathsf{s}}) ) \big]\notag\\ &\quad= \mathbb{E}_{Y,Z}\Big[\mathbb{E}_{x_k^{\mathsf{s}}\sim \widehat{X}_{t_k}^{\mathsf{s}}\,|\,Y,Z}\big[\mathsf{TV}(p_{\widehat{X}_{t_k}^{\mathsf{c}}|\widehat{X}_{t_k}^{\mathsf{s}},Y,Z}(\cdot\,|\,x_k^{\mathsf{s}},y,z), p_{X_{t_k}^{\mathsf{c}}|X_{t_k}^{\mathsf{s}}}(\cdot\,|\,x_k^{\mathsf{s}}) ) \big]\Big]\notag\\ &\quad\le\mathbb{E}_{Y,Z}\Big[\mathbb{E}_{x_k^{\mathsf{s}}\sim \widehat{X}_{t_k}^{\mathsf{s}}\,|\,Y,Z}\big[\mathsf{TV}(p_{\widehat{X}_{t_k}^{\mathsf{c}}|\widehat{X}_{t_k}^{\mathsf{s}},Y,Z}(\cdot\,|\,x_k^{\mathsf{s}},y,z), p_{\widetilde{X}_{k}^{\mathsf{c}}|\widetilde{X}_{k}^{\mathsf{s}},Y,Z}(\cdot\,|\,x_k^{\mathsf{s}},y,z) ) \big]\Big]\notag\\ &\qquad + \mathbb{E}_{Y,Z}\Big[\mathbb{E}_{x_k^{\mathsf{s}}\sim \widehat{X}_{t_k}^{\mathsf{s}}\,|\,Y,Z}\big[\mathsf{TV}(p_{\widetilde{X}_{k}^{\mathsf{c}}|\widetilde{X}_{k}^{\mathsf{s}},Y,Z}(\cdot\,|\,x_k^{\mathsf{s}},y,z), p_{X_{t_k}^{\mathsf{c}}|X_{t_k}^{\mathsf{s}}}(\cdot\,|\,x_k^{\mathsf{s}}) ) \big]\Big]\notag\\ &\quad\le \mathbb{E}_{Y,Z}\Big[\mathsf{TV}(p_{\widehat{X}_{t_k}\,|\,Y,Z}, p_{\widetilde{X}_{k}\,|\,Y,Z} ) + \mathsf{TV}(p_{\widehat{X}_{t_k}^{\mathsf{s}}\,|\,Y,Z}, p_{\widetilde{X}_{k}^{\mathsf{s}}\,|\,Y,Z} )\Big] \notag\\ &\qquad + \mathbb{E}_{Y,Z}\Big[\mathbb{E}_{x_k^{\mathsf{s}}\sim \widehat{X}_{t_k}^{\mathsf{s}}\,|\,Y,Z}\big[\mathsf{TV}(p_{\widetilde{X}_{k}^{\mathsf{c}}|\widetilde{X}_{k}^{\mathsf{s}},Y,Z}(\cdot\,|\,x_k^{\mathsf{s}},y,z), p_{X_{t_k}^{\mathsf{c}}|X_{t_k}^{\mathsf{s}}}(\cdot\,|\,x_k^{\mathsf{s}}) )\big]\Big]\notag\\ &\quad\le \mathbb{E}_{Y,Z}\Big[\mathsf{TV}(p_{\widehat{X}_{t_k}\,|\,Y,Z}, p_{\widetilde{X}_{k}\,|\,Y,Z} ) + 2\mathsf{TV}(p_{\widehat{X}_{t_k}^{\mathsf{s}}\,|\,Y,Z}, p_{\widetilde{X}_{k}^{\mathsf{s}}\,|\,Y,Z} )\Big] \notag\\ &\qquad + \mathbb{E}_{Y,Z}\Big[\mathbb{E}_{x_k^{\mathsf{s}}\sim \widetilde{X}_{k}^{\mathsf{s}}\,|\,Y,Z}\big[\mathsf{TV}(p_{\widetilde{X}_{k}^{\mathsf{c}}|\widetilde{X}_{k}^{\mathsf{s}},Y,Z}(\cdot\,|\,x_k^{\mathsf{s}},y,z), p_{X_{t_k}^{\mathsf{c}}|X_{t_k}^{\mathsf{s}}}(\cdot\,|\,x_k^{\mathsf{s}}) )\big]\Big]\to 0. \end{align}\]

We introduce an auxiliary sequence as below: for \(k-N\le i < k\), with initilization \(\breve{X}_{k-N}\sim p_{\widetilde{X}_{k-N}}\), and iterates as \[\tag{49} \begin{align} \breve{X}_{i+1}^{\mathsf{st}} &=\widetilde{X}_{i+1}^{\mathsf{st}},\\ \breve{X}_{i+1}^{\mathsf{sc}} &= \frac{\alpha_{t_{i+1}}}{\alpha_{t_i}}\breve{X}_{{i}}^{\mathsf{sc}} + \frac{\alpha_{t_{i+1}}\sigma_{t_k}^2}{\alpha_{t_{i}}}\left(1-{\rm e}^{-2\delta_{i+1}}\right)\nabla_{\breve{X}_{i}^{\mathsf{sc}}} \log p_{\lambda_i}(\breve{X}_{i-N}^{\mathsf{c}},\breve{X}_{i}^{\mathsf{sc}}) + \sigma_{t_{i+1}}\sqrt{1 - e^{-2\delta_{i+1}}} Z_{i}^{\mathsf{sc}},\tag{50}\\ \breve{X}_{i+1}^{\mathsf{c}} &= \breve{X}_{i}^{\mathsf{c}} + \gamma_i \nabla_{\breve{X}_i^{\mathsf{c}}} \log p_{\lambda_{i+1}}(\breve{X}_{i}^{\mathsf{c}},\breve{X}_{i+1}^{\mathsf{sc}}) + \sqrt{2\gamma_i} Z_i^{\mathsf{c}}.\tag{51} \end{align}\] We choose \(N\) satisfying \(\sum_{i=k-N}^k \delta_{i+1} = \Theta(\delta^{\frac{1}{2}})\). For any \(y,z\), we have \[\begin{align} \label{eq:proof-breveX-tildeX} \mathsf{TV}(p_{\breve{X}_k\,|\,Y,Z},p_{\widetilde{X}_k\,|\,Y,Z}) \to 0. \end{align}\tag{52}\] The proof is postponed to the end of this subsection. Armed with this auxiliary sequence, we prove 48 via establishing \[\begin{align} \label{eq:proof-lem-distri-sc-6} \mathbb{E}_{\widetilde{X}_k^{\mathsf{s}}\,|\,Y,Z}\big[\mathsf{TV}(p_{\breve{X}_k^{\mathsf{c}}|\breve{X}_k^{\mathsf{s}},Y,Z},\Vert p_{{X}_{t_k}^{\mathsf{c}}|{X}_{t_k}^{\mathsf{s}}} )\big] & \to 0\qquad \mathsf{as}\quad \delta\eta\log\frac{1}{\delta} \to 0\quad \mathrm{and}\quad \frac{\delta\eta^2}{\log\frac{1}{\delta}}\to\infty. \end{align}\tag{53}\] which implies that \[\begin{align} &\mathbb{E}_{x_k^{\mathsf{sc}}\sim \widetilde{X}_k^{\mathsf{sc}}\,|\,Y,Z}[\mathsf{TV}(p_{\widetilde{X}_k^{\mathsf{c}}\,|\,\widetilde{X}_k^{\mathsf{sc}},Y,Z}(\cdot\,|\,x_k^{\mathsf{sc}}, y, z),p_{{X}_{t_k}^{\mathsf{c}}\,|\,{X}_{t_k}^{\mathsf{sc}}}(\cdot\,|\,x_k^{\mathsf{sc}}))]\notag\\ &\quad \le \mathbb{E}_{x_k^{\mathsf{sc}}\sim \widetilde{X}_k^{\mathsf{sc}}\,|\,Y,Z}[\mathsf{TV}(p_{\breve{X}_k^{\mathsf{c}}\,|\,\breve{X}_k^{\mathsf{sc}},Y,Z}(\cdot\,|\,x_k^{\mathsf{sc}}, y, z),p_{{X}_{t_k}^{\mathsf{c}}\,|\,{X}_{t_k}^{\mathsf{sc}}}(\cdot\,|\,x_k^{\mathsf{sc}}))]\notag\\ &\qquad + \mathbb{E}_{x_k^{\mathsf{sc}}\sim \widetilde{X}_k^{\mathsf{sc}}\,|\,Y,Z}[\mathsf{TV}(p_{\breve{X}_k^{\mathsf{c}}\,|\,\breve{X}_k^{\mathsf{sc}},Y,Z}(\cdot\,|\,x_k^{\mathsf{sc}}, y, z),p_{\widetilde{X}_k^{\mathsf{c}}\,|\,\widetilde{X}_k^{\mathsf{sc}},Y,Z}(\cdot\,|\,x_k^{\mathsf{sc}}, y, z))] \notag\\ &\quad \le \mathbb{E}_{x_k^{\mathsf{sc}}\sim \widetilde{X}_k^{\mathsf{sc}}\,|\,Y,Z}[\mathsf{TV}(p_{\breve{X}_k^{\mathsf{c}}\,|\,\breve{X}_k^{\mathsf{sc}},Y,Z}(\cdot\,|\,x_k^{\mathsf{sc}}, y, z),p_{{X}_{t_k}^{\mathsf{c}}\,|\,{X}_{t_k}^{\mathsf{sc}}}(\cdot\,|\,x_k^{\mathsf{sc}}))]\notag\\ &\qquad +\mathsf{TV}(p_{\breve{X}_k\,|\,Y,Z}(\cdot\,|\,y, z),p_{\widetilde{X}_k\,|\,Y,Z}(\cdot\,|\,y, z)) + \mathsf{TV}(p_{\breve{X}_k^{\mathsf{sc}}\,|\,Y,Z}(\cdot\,|\,y, z),p_{\widetilde{X}_k^{\mathsf{sc}}\,|\,Y,Z}(\cdot\,|\,y, z))\to 0. \end{align}\]

To establish 53 , we begin with considering given \(\breve{X}_{1:k}^{\mathsf{sc}}=\breve{x}_{1:k}^{\mathsf{sc}}\), which satisfies \[\begin{align} \label{eq:def-set-E} \mathcal{E}_k\mathrel{\vcenter{:}}=\big\{\|\breve{x}_{i+1}^{\mathsf{sc}}-\breve{x}_{i}^{\mathsf{sc}}\|_2\lesssim \delta_{i+1}\log\frac{1}{\delta},\forall i\le k-1\big\}. \end{align}\tag{54}\] For ease of notation, denote the distribution (pdf) of \(\breve{X}_{k}^{\mathsf{c}}\) under given \(\breve{X}_{1:k}^{\mathsf{s}}=\breve{x}_{1:k}^{\mathsf{sc}}\) as \(\psi_k\). Denote the target conditional distribution \[p_k^{\mathsf{c}}(x)\mathrel{\vcenter{:}}= p_{X_{t_k}^{\mathsf{c}}|X_{t_k}^{\mathsf{s}}}(x|\breve{x}_k^{\mathsf{s}}).\] By deifnition of \(p_{\lambda_k}\), we have \(\nabla_x \log p_{\lambda_k}(x,\breve{x}_k^{\mathsf{sc}}) = \nabla_x \log p_k^{\mathsf{c}}(x)\). Moreover, denote \(P_{\gamma_k}\) as the transition probability of the following SDE from \(t\) to \(t+\gamma_k\): \[\begin{align} \mathrm{d} X(t) = \nabla \log p_k^{\mathsf{c}}(X(t)) \mathrm{d} t + \sqrt{2} \mathrm{d} W_t, \end{align}\] where \(W_t\) denotes the Brownian motion. According to the analysis of Langevin, we have \[\begin{align} \mathsf{KL}(P_{\gamma_k}\psi_{k}\Vert p_{k+1}^{\mathsf{c}}) \le {\rm e}^{-2\kappa\gamma_k}\mathsf{KL}(\psi_{k}\Vert p_{k+1}^{\mathsf{c}}), \end{align}\] where \(\kappa<\infty\) is a constant. Therefore, we have \[\begin{align} \label{eq:proof-13} \mathsf{KL}(\psi_{k+1}\Vert p_{k+1}^{\mathsf{c}}) &= \mathsf{KL}(P_{\gamma_k}\psi_{k}\Vert p_{k+1}^{\mathsf{c}}) +\mathsf{KL}(\psi_{k+1}\Vert p_{k+1}^{\mathsf{c}}) - \mathsf{KL}(P_{\gamma_k}\psi_{k}\Vert p_{k+1}^{\mathsf{c}})\notag\\ &\le {\rm e}^{-2\kappa\gamma_k}\mathsf{KL}(\psi_{k}\Vert p_{k+1}^{\mathsf{c}}) +\mathsf{KL}(\psi_{k+1}\Vert p_{k+1}^{\mathsf{c}}) - \mathsf{KL}(P_{\gamma_k}\psi_{k}\Vert p_{k+1}^{\mathsf{c}})\notag\\ &= {\rm e}^{-2\kappa\gamma_k}\mathsf{KL}(\psi_{k}\Vert p_{k}^{\mathsf{c}}) + {\rm e}^{-2\kappa\gamma_k}\left(\mathsf{KL}(\psi_{k}\Vert p_{k+1}^{\mathsf{c}})-\mathsf{KL}(\psi_{k}\Vert p_{k}^{\mathsf{c}}) \right)\notag\\ &\quad +\mathsf{KL}(\psi_{k+1}\Vert p_{k+1}^{\mathsf{c}}) - \mathsf{KL}(P_{\gamma_k}\psi_{k}\Vert p_{k+1}^{\mathsf{c}}). \end{align}\tag{55}\]

Next, we control the two error terms in the right-hand-side of 55 separately.

• Control the term \(\mathsf{KL}(\psi_{k}\Vert p_{k+1}^{\mathsf{c}})-\mathsf{KL}(\psi_{k}\Vert p_{k}^{\mathsf{c}})\). According to the definition of KL divergence, we have \[\begin{align} \label{eq:proof-10} \mathsf{KL}(\psi_{k}\Vert p_{k+1}^{\mathsf{c}}) - \mathsf{KL}(\psi_{k}\Vert p_{k}^{\mathsf{c}}) &= \int \log\frac{p_{k}^{\mathsf{c}}(x)}{p_{k+1}^{\mathsf{c}}(x)}\psi_{k}(x)\mathrm{d}x. \end{align}\tag{56}\] According to the definition of \(p_{k+1}^{\mathsf{c}}(x)\), we have \[\begin{align} p_{k}^{\mathsf{c}}(x)=\frac{p_{X_{t_k}}(x)}{p_{X_{t_k}^{\mathsf{s}}}(\breve{x}_k^{\mathsf{s}})} \end{align}\] Then we have \[\begin{align} \frac{\partial \log p_{k}^{\mathsf{c}}(x)}{\partial \alpha_{t_i}} & = \frac{\partial \log p_{X_{t_k}}(x)}{\partial \alpha_{t_k}} - \frac{\partial \log p_{X_{t_k}^{\mathsf{s}}}(\breve{x}_k^{\mathsf{s}})}{\partial \alpha_{t_k}}\notag\\ &= \frac{1}{\sigma_{t_k}^2}\mathbb{E}[(x-\alpha_{t_k}X_0^{\mathsf{c}})^{\top}X_0^{\mathsf{c}}+(\breve{x}_k-\alpha_{t_k}X_0^{\mathsf{s}})^{\top}X_0^{\mathsf{s}} |X_{t_k}^{\mathsf{c}}=x,X_{t_k}^{\mathsf{s}}=\breve{x}_k^{\mathsf{s}}] \notag\\ &\quad - \frac{1}{\sigma_{t_k}^2}\mathbb{E}[(\breve{x}_k^{\mathsf{s}}-\alpha_{t_k}X_0^{\mathsf{s}})^{\top}X_0^{\mathsf{s}}|X_{t_k}^{\mathsf{s}}=\breve{x}_k^{\mathsf{s}}]. \end{align}\] Recalling that \(X_0\) is bounded, we further have \[\begin{align} \left|\frac{\partial \log p_{k}^{\mathsf{c}}(x)}{\partial \alpha_{t_k}}\right|\lesssim (\|x\|_2+\|\breve{x}_k^{\mathsf{s}}\|_2+1). \end{align}\] By similar calculation, we have \[\begin{align} \left| \frac{\partial \log p_{k}^{\mathsf{c}}(x)}{\partial \sigma_{t_i}} \right| \lesssim (\|x\|_2^2+\|\breve{x}_k^{\mathsf{s}}\|_2+ 1),\qquad \left\|\nabla_{x^{\mathsf{s}}} \log p_{k}^{\mathsf{c}}(x)\right\|_2\lesssim (\|x\|_2+\|\breve{x}_k^{\mathsf{s}}\|_2+ 1). \end{align}\] Thus we have \[\begin{align} \log \frac{p_{k+1}^{\mathsf{c}}(x)}{p_{k}^{\mathsf{c}}} &= O(|\alpha_{t_{k+1}}-\alpha_{t_{k}}|\notag\\ &\qquad + |\sigma_{t_{k+1}}-\sigma_{t_{k}}|)(\|x\|_2^2+\|\breve{x}_k^{\mathsf{s}}\|_2+1) + O(\|\breve{x}_{k+}^{\mathsf{s}}-\breve{x}_k^{\mathsf{s}}\|_2)(\|x\|_2+\|\breve{x}_k^{\mathsf{s}}\|_2+1)\notag\\ & = (\|x\|_2^2+\|\breve{x}_k^{\mathsf{s}}\|_2+1)O\bigg(\delta_{k+1}+\sqrt{\delta_{k+1}\log\frac{1}{\delta}}\bigg), \end{align}\] where the last line arises from 77 , 74 , and 54 . Based on this observation, we have \[\begin{align} \int \log\frac{p_{k}^{\mathsf{c}}(x)}{p_{k+1}^{\mathsf{c}}(x)}\psi_{k}^{\mathsf{c}}(x)\mathrm{d}x &= -\int \log\frac{p_{k+1}^{\mathsf{c}}(x)}{p_{k}^{\mathsf{c}}(x)}\psi_{k}^{\mathsf{c}}(x)\mathrm{d}x \notag\\ &=O(\sqrt{\delta_{k+1}\log\delta^{-1}})\big(\mathbb{E}[\|\breve{X}_k^{\mathsf{c}}\|_2^2\,|\,\breve{X}_k^{\mathsf{s}}=\breve{x}_{1:k}^{\mathsf{sc}}]+\|\breve{x}_{k}^{\mathsf{sc}}\|_2+1\big)\notag\\ &=O(\sqrt{\delta_{k+1}\log\delta^{-1}}), \end{align}\] where the last line uses \(\mathbb{E}[\|\breve{X}_k^{\mathsf{c}}\|_2^2\,|\,\breve{X}_k^{\mathsf{s}}=\breve{x}_{1:k}^{\mathsf{sc}}]<\infty\). Combining these with 56 yields \[\begin{align} \label{eq:proof-14} \left|\mathsf{KL}(\psi_{k}\Vert p_{k+1}^{\mathsf{c}}) - \mathsf{KL}(\psi_{k}\Vert p_{k+1}^{\mathsf{c}})\right| \lesssim \sqrt{\delta_{k+1}\log\delta^{-1}}. \end{align}\tag{57}\]

• Control the term \(\mathsf{KL}(\psi_{k+1}\Vert p_{k+1}^{\mathsf{c}}) - \mathsf{KL}(P_{\gamma_k}\psi_{k}\Vert p_{k+1}^{\mathsf{c}})\). For any smooth function \(f\), we have \[\begin{align} \label{eq:proof-11} \mathbb{E}_{\breve{X}_{k+1}^{\mathsf{c}}}[f(\breve{X}_{k+1}^{\mathsf{c}})] &= \mathbb{E}_{\breve{X}_{k}^{\mathsf{c}},Z_k^{\mathsf{c}}}\big[f\big(\breve{X}_{k}^{\mathsf{c}}+\gamma_k\nabla\log p_{k+1}^{\mathsf{c}}(\breve{X}_{k}^{\mathsf{c}})+\sqrt{2\gamma_k}Z_k^{\mathsf{c}}\big)\big] \notag\\ &= \mathbb{E}\big[f\big(\breve{X}_{k}^{\mathsf{c}}\big)+\gamma_k\nabla f(\breve{X}_{k}^{\mathsf{c}})^{\top}\nabla\log p_{k+1}^{\mathsf{c}}(\breve{X}_{k}^{\mathsf{c}}) + \gamma_k\Delta f(\breve{X}_{k}^{\mathsf{c}}) + O(\gamma_k^2)\big], \end{align}\tag{58}\] where \(\Delta f(x)\mathrel{\vcenter{:}}= \mathsf{Tr}(\nabla_x^2 f(x))\). In contrast, by using the geneator operator of Langevin proccess \(\mathcal{L} = \nabla\log p_{k+1}^{\top} \nabla + \Delta\), we have \[\begin{align} \label{eq:proof-12} \mathbb{E}_{X\sim P_{\gamma_k}\psi_k}[f(X)] &= \mathbb{E}_{X\sim\psi_k}[f(X)+\gamma_k (\mathcal{L}f)(X)+O(\gamma_k^2)]\notag\\ & =\mathbb{E}_{X\sim\psi_k}[f(X)+\gamma_k\nabla\log p_{k+1}^{\top}(X) \nabla f(X) + \gamma_k\Delta f(X)+O(\gamma_k^2)] \end{align}\tag{59}\] Combining 58 and 59 , we have \[\begin{align} \label{eq:proof-29} \mathbb{E}_{X\sim \psi_{k+1}}[f(X)] -\mathbb{E}_{X\sim P_{\gamma_k}\psi_{k}}[f(X)] =O(\gamma_k^2). \end{align}\tag{60}\] Armed with this, we have \[\begin{align} &\mathsf{KL}(\psi_{k+1}\Vert p_{k+1}^{\mathsf{c}}) - \mathsf{KL}(P_{\gamma_k}\psi_{k}\Vert p_{k+1}^{\mathsf{c}}) \notag\\ &\quad = \mathbb{E}_{X\sim \psi_{k+1}}\Big[\log\frac{\psi_{k+1}(X)}{p_{k+1}^{\mathsf{c}}(X)}\Big] - \mathbb{E}_{X\sim P_{\gamma_k}\psi_{k}}\Big[\log\frac{P_{\gamma_k}\psi_{k}(X)}{p_{k+1}^{\mathsf{c}}(X)}\Big]\notag\\ &\quad =\mathbb{E}_{X\sim \psi_{k+1}}\Big[\log\frac{\psi_{k+1}(X)}{p_{k+1}^{\mathsf{c}}(X)}\Big] - \mathbb{E}_{X\sim P_{\gamma_k}\psi_{k}}\Big[\log\frac{\psi_{k+1}(X)}{p_{k+1}^{\mathsf{c}}(X)}\Big] - \mathbb{E}_{X\sim P_{\gamma_k}\psi_{k}}\Big[\log\frac{P_{\gamma_k}\psi_k(X)}{\psi_{k+1}(X)}\Big]. \end{align}\] Notice that as the KL divergence between \(P_{\gamma_k}\psi_{k}\) and \(\psi_{k+1}\) is non-negative, i.e., \[\begin{align} \mathbb{E}_{X\sim P_{\gamma_k}\psi_{k}}\Big[\log\frac{P_{\gamma_k}\psi_k(X)}{\psi_{k+1}(X)}\Big]\ge 0. \end{align}\] By using 60 , we have \[\begin{align} \label{eq:proof-15} \mathsf{KL}(\psi_{k+1}\Vert p_{k+1}^{\mathsf{c}}) - \mathsf{KL}(P_{\gamma_k}\psi_{k}\Vert p_{k+1}^{\mathsf{c}}) &\le \mathbb{E}_{X\sim \psi_{k+1}}\Big[\log\frac{\psi_{k+1}(X)}{p_{k+1}^{\mathsf{c}}(X)}\Big] - \mathbb{E}_{X\sim P_{\gamma_k}\psi_{k}}\Big[\log\frac{\psi_{k+1}(X)}{p_{k+1}^{\mathsf{c}}(X)}\Big]\notag\\ & = O(\gamma_k^2). \end{align}\tag{61}\]

Substituting 57 and 61 into 55 , we have \[\begin{align} \label{eq:proof-lem-distri-xsc-1} \mathsf{KL}(\psi_{k+1}\Vert p_{k+1}^{\mathsf{c}})&\le {\rm e}^{-2\kappa\gamma_k}\mathsf{KL}(\psi_{k}\Vert p_k^{\mathsf{c}}) + O\big(\sqrt{\delta_{k+1}\log\delta^{-1}}\big) + O(\gamma_k^2)\notag\\ &\le {\rm e}^{-2\kappa\sum_{i=k-N}^k{\gamma_i}}\mathsf{KL}(\psi_{k-N}\Vert p_{k-N}^{\mathsf{c}}) + O\Big(\frac{\sqrt{\delta}\log\delta^{-1}}{\delta\eta}\Big) + O(\max_k \gamma_k)\notag\\ &\lesssim {\rm e}^{-2\Theta( \sqrt{\delta})\eta} + \frac{\log\delta^{-1}}{\sqrt{\delta}\eta} + \max_k \gamma_k\to0,\qquad\mathrm{as}\quad \frac{\delta\eta^2}{\log\delta^{-1}}\to\infty,\quad \delta\eta\to 0, \end{align}\tag{62}\] where we have used the assumption that \(\sum_{i=k-N}^k\gamma_i\asymp \sqrt{\delta}\eta \to \infty\). Futhermore, notice that \[\begin{align} \mathbb{P}(\mathcal{E}_k^{\mathsf{c}}) \le\sum_{i=1}^{k+1}\mathbb{P}\left(O(\delta_{i+1})+\sqrt{\delta_{i+1}}\|Z_{t_i}^{\mathsf{sc}}\|_2\le O(\sqrt{\delta_{i+1}}\log\delta^{-1})\right) \le \delta^{10}\to 0,\qquad \mathrm{as} \quad \delta \to 0. \end{align}\] We have \[\begin{align} &\mathsf{TV}(p_{\breve{X}_{k}^{\mathsf{c}}|\breve{X}_{k}^{\mathsf{s}}}(\cdot\,|\,\breve{x}_{k}^{\mathsf{s}}), p_{X_{t_k}^{\mathsf{c}}|X_{t_k}^{\mathsf{s}}}(\cdot\,|\,\breve{x}_k^{\mathsf{s}}) ) \notag\\ &\quad \le \mathbb{E}_{\breve{x}_{1:k-1}^{\mathsf{s}}\sim \breve{X}_{1:k-1}^{\mathsf{s}}\,|\,\breve{X}_{k}^{\mathsf{s}}}\big[\mathsf{TV}(p_{\breve{X}_{k}^{\mathsf{c}}|\breve{X}_{1:k}^{\mathsf{s}}}(\cdot\,|\,\breve{x}_{1:k}^{\mathsf{s}}), p_{X_{t_k}^{\mathsf{c}}|X_{t_k}^{\mathsf{s}}}(\cdot\,|\,x_k^{\mathsf{s}}) ) \big]\notag\\ &\quad \le \mathbb{E}_{\breve{x}_{1:k-1}^{\mathsf{s}}\sim \breve{X}_{1:k-1}^{\mathsf{s}}\,|\,\breve{X}_{k}^{\mathsf{s}},\breve{x}_{1:k-1}^{\mathsf{s}}\in\mathcal{E}_k}\big[\mathsf{TV}(p_{\breve{X}_{k}^{\mathsf{c}}|\breve{X}_{1:k}^{\mathsf{s}}}(\cdot\,|\,\breve{x}_{1:k}^{\mathsf{s}}), p_{X_{t_k}^{\mathsf{c}}|X_{t_k}^{\mathsf{s}}}(\cdot\,|\,x_k^{\mathsf{s}}) ) \big] + \mathbb{P}(\mathcal{E}_k^{\mathsf{c}}) \to 0. \end{align}\] We complete the proof.

7.4.0.1 Proof of 52 .

By Pinsker’s inequality, we have \[\begin{align} &\quad \mathsf{TV}(p_{\breve{X}_k\,|\,Y,Z},p_{\widetilde{X}_k\,|\,Y,Z})^2 \le \mathsf{KL}(p_{\widetilde{X}_k\,|\,Y,Z} \Vert p_{\breve{X}_k\,|\,Y,Z}) \notag\\ &\le \sum_{i=k-N}^{k-1} \mathbb{E}_{x_i^{\mathsf{sc}}\sim\widetilde{X}_i^{\mathsf{sc}},x_i^{\mathsf{c}}\sim\widetilde{X}_i^{\mathsf{c}},x_{i-N}^{\mathsf{c}}\sim\widetilde{X}_{i-N}^{\mathsf{c}}}\left[\mathsf{KL}(p_{\widetilde{X}_{i+1}^{\mathsf{sc}}\,|\,\widetilde{X}_{i}^{\mathsf{sc}},\widetilde{X}_{i}^{\mathsf{c}}}(\cdot\,|\,x_i^{\mathsf{sc}},x_i^{\mathsf{c}}) \Vert p_{\breve{X}_{i+1}^{\mathsf{sc}}\,|\,\breve{X}_{i}^{\mathsf{sc}},\breve{X}_{i-N}^{\mathsf{c}}}(\cdot\,|\,x_i^{\mathsf{sc}},x_{i-N}^{\mathsf{c}})) \right]\notag\\ &\qquad + \sum_{i=k-N}^{k-1} \mathbb{E}_{x_{i}^{\mathsf{c}}\sim\widetilde{X}_{i}^{\mathsf{c}},x_{i+1}^{\mathsf{sc}}\sim\widetilde{X}_{i+1}^{\mathsf{sc}}}\left[\mathsf{KL}(p_{\widetilde{X}_{i+1}^{\mathsf{c}}\,|\,\widetilde{X}_{i}^{\mathsf{c}},\widetilde{X}_{i+1}^{\mathsf{sc}}}(\cdot\,|\,x_i^{\mathsf{c}},x_{i+1}^{\mathsf{sc}}) \Vert p_{\breve{X}_{i+1}^{\mathsf{c}}\,|\,\breve{X}_{i}^{\mathsf{c}},\breve{X}_{i+1}^{\mathsf{sc}}}(\cdot\,|\,x_i^{\mathsf{c}},x_{i+1}^{\mathsf{sc}})) \right]\notag\\ &= \sum_{i=k-N}^{k-1} \mathbb{E}_{x_i^{\mathsf{sc}}\sim\widetilde{X}_i^{\mathsf{sc}},x_i^{\mathsf{c}}\sim\widetilde{X}_i^{\mathsf{c}},x_{i-N}^{\mathsf{c}}\sim\widetilde{X}_{i-N}^{\mathsf{c}}}\left[\mathsf{KL}(p_{\widetilde{X}_{i+1}^{\mathsf{sc}}\,|\,\widetilde{X}_{i}^{\mathsf{sc}},\widetilde{X}_{i}^{\mathsf{c}}}(\cdot\,|\,x_i^{\mathsf{sc}},x_i^{\mathsf{c}}) \Vert p_{\breve{X}_{i+1}^{\mathsf{sc}}\,|\,\breve{X}_{i}^{\mathsf{sc}},\breve{X}_{i-N}^{\mathsf{c}}}(\cdot\,|\,x_i^{\mathsf{sc}},x_{i-N}^{\mathsf{c}})) \right], \end{align}\] where the last equation holds since \(p_{\widetilde{X}_{i+1}^{\mathsf{c}}\,|\,\widetilde{X}_{i}^{\mathsf{c}},\widetilde{X}_{i+1}^{\mathsf{sc}}}(\cdot\,|\,x_i^{\mathsf{c}},x_{i+1}^{\mathsf{sc}}) =p_{\breve{X}_{i+1}^{\mathsf{c}}\,|\,\breve{X}_{i}^{\mathsf{c}},\breve{X}_{i+1}^{\mathsf{sc}}}(\cdot\,|\,x_i^{\mathsf{c}},x_{i+1}^{\mathsf{sc}})\) by 51 . According to 50 , both \(p_{\widetilde{X}_{i+1}^{\mathsf{s}}\,|\,\widetilde{X}_{i}^{\mathsf{s}},\widetilde{X}_{i}^{\mathsf{c}}}(\cdot\,|\,x_i^{\mathsf{s}},x_i^{\mathsf{c}})\) and \(p_{\breve{X}_{i+1}^{\mathsf{sc}}\,|\,\breve{X}_{i}^{\mathsf{sc}},\breve{X}_{i-N}^{\mathsf{c}}}(\cdot\,|\,x_i^{\mathsf{s}},x_{i-N}^{\mathsf{c}})\) are Gaussian distributions with the same variance \(\sigma_{t_{i+1}}^2(1-{\rm e}^{-2\delta_{i+1}})I_d\) and different mean vectors. We have \[\begin{align} &\mathsf{KL}\left( p_{\widetilde{X}_{i+1}^{\mathsf{s}}\,|\,\widetilde{X}_{i}^{\mathsf{s}},\widetilde{X}_{i}^{\mathsf{c}}}(\cdot\,|\,x_i^{\mathsf{s}},x_i^{\mathsf{c}})\Vert p_{\breve{X}_{i+1}^{\mathsf{sc}}\,|\,\breve{X}_{i}^{\mathsf{sc}},\breve{X}_{i-N}^{\mathsf{c}}}(\cdot\,|\,x_i^{\mathsf{s}},x_{i-N}^{\mathsf{c}}) \right)\notag\\ &\quad = \frac{\alpha_{t_{i+1}}^2\sigma_{t_i}^4(1-{\rm e}^{-2\delta_{i+1}})^2}{2\alpha_{t_i}^2\sigma_{t_{i+1}}^2(1-{\rm e}^{-2\delta_{i+1}})}\left\|\nabla_{x_{i}^{\mathsf{sc}}} \log p_{\lambda_i}(x_{i-N}^{\mathsf{c}},x_{i}^{\mathsf{sc}})-\nabla_{x_{i}^{\mathsf{sc}}} \log p_{\lambda_i}(x_{i}^{\mathsf{c}},x_{i}^{\mathsf{sc}})\right\|_2^2\notag\\ &\quad \lesssim \delta_{i+1}\left\|\nabla_{x_{i}^{\mathsf{sc}}} \log p_{\lambda_i}(x_{i-N}^{\mathsf{c}},x_{i}^{\mathsf{sc}})-\nabla_{x_{i}^{\mathsf{sc}}} \log p_{\lambda_i}(x_{i}^{\mathsf{c}},x_{i}^{\mathsf{sc}})\right\|_2^2. \end{align}\] Therefore, we have \[\begin{align} \mathsf{TV}(p_{\breve{X}_k\,|\,Y,Z},p_{\widetilde{X}_k\,|\,Y,Z})^2 &\lesssim \sum_{i=k-N}^{k-1} \delta_{i+1}\mathbb{E}_{x_i^{\mathsf{sc}}\sim\widetilde{X}_i^{\mathsf{sc}},x_i^{\mathsf{c}}\sim\widetilde{X}_i^{\mathsf{c}},x_{i-N}^{\mathsf{c}}\sim\widetilde{X}_{i-N}^{\mathsf{c}}}\left[\left\|\nabla_{x_{i}^{\mathsf{sc}}} \log p_{\lambda_i}(x_{i-N}^{\mathsf{c}},x_{i}^{\mathsf{sc}})-\nabla_{x_{i}^{\mathsf{sc}}} \log p_{\lambda_i}(x_{i}^{\mathsf{c}},x_{i}^{\mathsf{sc}})\right\|_2^2 \right]\notag\\ &\lesssim \sum_{i=k-N}^{k-1}\delta_{i+1} \asymp \delta^{1/2} \to 0,\qquad \mathrm{as}\quad \delta\to 0. \end{align}\] Thus we complete the proof.

7.5 Proof of Lemma 3↩︎

It suffices to prove that \[\begin{align} \mathsf{KL}(p_{\widehat{X}_{t_i}^{\mathsf{sc}}\,|\,\widehat{X}_{t_{i-1}}}\Vert p_{X_{t_i}^{\mathsf{sc}}\,|\,{X}_{t_{i-1}}}) = o(\delta_{i}). \end{align}\] According to the update rule, \(p_{\widehat{X}_{t_i}^{\mathsf{sc}}|\widehat{X}_{t_{i-1}}}\) is a Gaussian distribution. We consider the following density function: \[\begin{align} \label{eq:proof-lem-dsitri-xsc-4} \widehat{p}_i(x_i|x_{i-1}) \mathrel{\vcenter{:}}= (2\pi\varrho^2)^{-d/2}\exp\left(-\frac{1}{2\varrho^2}\|x_i-\mu_0-\Delta\|_2^2\right), \end{align}\tag{63}\] where variance \(\varrho^2=\sigma_{t_{i}}^2(1-{\rm e}^{-2\delta_{i}})\) and the mean vecotr \(\mu_0+\Delta\) is given by \[\begin{align} \mu_0 = \frac{\alpha_{t_{i}}}{\alpha_{t_{i-1}}}\widehat{X}_{t_{i-1}},\qquad \Delta = \alpha_{t_{i}}\sigma_{t_{i-1}}\left({\rm e}^{-\lambda_{t_{i-1}}}-{\rm e}^{-2\lambda_{t_{i}}+\lambda_{t_{i-1}}}\right)\nabla_{{x}_{i-1}} \log p_{X_{t_{i-1}}}({x}_{i-1}). \end{align}\] By noticing that \(V_{\mathcal{S}_{t_i}^{\mathsf{prior}}}^{\top}\nabla_{{x}_{i-1}} \log p_{X_{t_{i-1}}}({x}_{i-1}) = \nabla_{{x}_{i-1}^{\mathsf{sc}}} \log p_{\lambda_{i-1}}({x}_{i-1}^{\mathsf{sc}},{x}_{i-1}^{\mathsf{c}})\), we conclude that \(\widehat{p}_i(x_i|x_{i-1})\) has the same marginal distribution on directions \(\mathcal{S}_{t_i}^{\mathsf{prior}}\) as \(p_{\widehat{X}_{t_i}^{\mathsf{sc}}|\widehat{X}_{t_{i-1}}}\). It suffices to prove that \[\begin{align} \label{eq:proof-lem-distri-xsc-9} \mathsf{KL}(p_{\widehat{X}_{t_i}^{\mathsf{sc}}\,|\,\widehat{X}_{t_{i-1}}}\Vert p_{X_{t_i}^{\mathsf{sc}}\,|\,{X}_{t_{i-1}}}) \le \mathsf{KL}( \widehat{p}_{i}\Vert p_{X_{t_i}\,|\,{X}_{t_{i-1}}}) = o(\delta_{i}). \end{align}\tag{64}\]

Towards this, we decompose \(\widehat{p}_i\) and \(p_{X_{t_i}\,|\,{X}_{t_{i-1}}}\) seperately.

• Decomposition of \(\widehat{p}_i(x_i|x_{i-1})\). Expanding the exponent expression in 63 yields \[\begin{align} \label{eq:proof-lem-dsitri-xsc-5} \widehat{p}_i(x_i|x_{i-1}) =(2\pi\varrho^2)^{-d/2}\exp\left(-\frac{1}{2\varrho^2}\|x_i-\mu_0\|_2^2 + \frac{1}{\varrho^2}\Delta^{\top}(x_i-\mu_0) + \frac{1}{2\varrho^2}\|\Delta\|_2^2\right). \end{align}\tag{65}\] Note that \[\begin{align} \frac{1}{\varrho^2}\Delta^{\top}(x_i-\mu_0) &= \frac{1}{\varrho^2}\alpha_{t_{i}}\sigma_{t_{i-1}}\left({\rm e}^{-\lambda_{t_{i-1}}}-{\rm e}^{-2\lambda_{t_{i}}+\lambda_{t_{i-1}}}\right)\nabla_{{x}_{i-1}} \log p_{X_{t_{i-1}}}({x}_{i-1})^{\top}(x_i-\mu_0)\notag\\ &= \frac{1}{\varrho^2}\alpha_{t_{i}}\sigma_{t_{i-1}}{\rm e}^{-\lambda_{t_{i-1}}}\left(1-{\rm e}^{-2\delta_{i}}\right)\nabla_{{x}_{i-1}} \log p_{X_{t_{i-1}}}({x}_{i-1})^{\top}(x_i-\mu_0)\notag\\ &= \frac{1}{\varrho^2}\frac{\alpha_{t_{i}}^2\sigma_{t_{i-1}}^2}{\alpha_{t_{i-1}}^2}\left(1-{\rm e}^{-2\delta_{i}}\right)\nabla_{{x}_{i-1}} \log p_{X_{t_{i-1}}}({x}_{i-1})^{\top}\big(\frac{\alpha_{t_{i-1}}}{\alpha_{t_{i}}}x_i-\widehat{X}_{t_{i-1}}\big)\notag\\ &={\rm e}^{2\delta_i}\nabla_{{x}_{i-1}} \log p_{X_{t_{i-1}}}({x}_{i-1})^{\top}\big(\frac{\alpha_{t_{i-1}}}{\alpha_{t_{i}}}x_i-\widehat{X}_{t_{i-1}}\big). \end{align}\] By denoting \(\widehat{x}_{i}=\alpha_{t_{i-1}}x_i/\alpha_{t_i}\), and noticing that \(\|\Delta\|_2 = O(\delta_i)\), we have \[\begin{align} \label{eq:proof-lem-dsitri-xsc-6} \widehat{p}_i(x_i|x_{i-1}) =(2\pi\varrho^2)^{-d/2}\exp\left(-\frac{1}{2\varrho^2}\|x_i-\mu_0\|_2^2 + {\rm e}^{2\delta_i}\nabla_{{x}_{i-1}} \log p_{X_{t_{i-1}}}({x}_{i-1})^{\top}\big(\widehat{x}_{i}-\widehat{X}_{t_{i-1}} \big)+ O(\delta_i)\right) \end{align}\tag{66}\]

• Decomposition of \(p_{X_{t_i}\,|\,{X}_{t_{i-1}}}(x_i|x_{i-1})\). \[\begin{align} \label{eq:proof-lem-distri-sc-3} p_{X_{t_i}\,|\,{X}_{t_{i-1}}}(x_i|x_{i-1}) = p_{X_{t_{i-1}}\,|\,{X}_{t_{i}}}(x_{i-1}|x_{i})\frac{p_{X_{t_{i}}}(x_{i})}{p_{X_{t_{i-1}}}(x_{i-1})}. \end{align}\tag{67}\] Furthermore, according to the forward process \[\begin{align} X_{t_{i-1}} &= \frac{\alpha_{t_{i-1}}}{\alpha_{t_{i}}} X_{t_{i}} + \left(\sigma_{t_{i-1}}^2-\frac{\alpha_{t_{i-1}}}{\alpha_{t_{i}}}\sigma_{t_{i}}^2\right)\mathcal{N}(0,I_d) = \frac{\alpha_{t_{i-1}}}{\alpha_{t_{i}}} X_{t_{i}} + \sigma_{t_{i-1}}\left(1-{\rm e}^{-2\delta_i}\right)^{1/2}\mathcal{N}(0,I_d)\notag\\ &= \frac{\alpha_{t_{i-1}}}{\alpha_{t_{i}}} X_{t_{i}} + \frac{\sigma_{t_{i-1}}}{\sigma_{t_i}}\varrho\mathcal{N}(0,I_d), \end{align}\] we have \[\begin{align} \label{eq:proof-lem-distri-sc-2} p_{X_{t_{i-1}}\,|\,{X}_{t_{i}}}(x_{i-1}|x_{i}) &= (2\pi\varrho^2)^{-d/2}\left(\frac{\sigma_{t_{i}}}{\sigma_{t_{i-1}}}\right)^{d}\exp\left(-\frac{\sigma_{t_{i}}^2}{2\varrho^2\sigma_{t_{i-1}}^2}\big\|\widehat{X}_{t_{i-1}}-\frac{\alpha_{t_{i-1}}}{\alpha_{t_{i}}} \widehat{X}_{t_{i}}\big\|_2^2\right)\notag\\ &=(2\pi\varrho^2)^{-d/2}\left(\frac{\sigma_{t_{i}}}{\sigma_{t_{i-1}}}\right)^{d}\exp\left(-\frac{\sigma_{t_{i}}^2\alpha_{t_{i-1}}^2}{2\varrho^2\sigma_{t_{i-1}}^2\alpha_{t_{i}}^2} \big\|\frac{\alpha_{t_{i}}}{\alpha_{t_{i-1}}} \widehat{X}_{t_{i-1}}-\widehat{X}_{t_{i}}\big\|_2^2\right)\notag\\ &=(2\pi\varrho^2)^{-d/2}\left(\frac{\sigma_{t_{i}}}{\sigma_{t_{i-1}}}\right)^{d}\exp\left(-\frac{{\rm e}^{-2\delta_{i}}}{2\varrho^2} \big\|\widehat{X}_{t_{i}}-\mu_0\big\|_2^2\right). \end{align}\tag{68}\] For the ratio \(\frac{p_{X_{t_{i}}}(x_{i})}{p_{X_{t_{i-1}}}(x_{i-1})}\), we have \[\begin{align} \label{eq:proof-lem-distri-sc-1} \frac{p_{X_{t_{i}}}(x_{i})}{p_{X_{t_{i-1}}}(x_{i-1})} &= \frac{p_{X_{t_{i}}}(x_{i})}{p_{X_{t_{i-1}}}(\widehat{x}_{i})} \frac{p_{X_{t_{i-1}}}(\widehat{x}_{i})}{p_{X_{t_{i-1}}}(x_{i-1})} = \frac{p_{X_{t_{i}}}(x_{i})}{p_{X_{t_{i-1}}}(\widehat{x}_{i})}\exp\left(\log p_{X_{t_{i-1}}}(\widehat{x}_{i}) - \log p_{X_{t_{i-1}}}(x_{i-1}) \right) \notag\\ &=\frac{p_{X_{t_{i}}}(x_{i})}{p_{X_{t_{i-1}}}(\widehat{x}_{i})}\exp\left(\nabla \log p_{X_{t_{i-1}}}(x_{i-1})^{\top}(\widehat{x}_{i}-x_{i-1}) \right). \end{align}\tag{69}\] Furthermore, we have \[\begin{align} &\quad\frac{p_{X_{t_{i}}}(x_{i})}{p_{X_{t_{i-1}}}(\widehat{x}_{i})} \notag\\ &= \left(\frac{\sigma_{t_{i-1}}}{\sigma_{t_i}}\right)^{d}\frac{\int p_{X_0}(x_0)\exp\left(-\frac{1}{2\sigma_{t_i}^2}\|x_i-\alpha_{t_i}x_0\|_2^2\right)\mathrm{d} x_0}{\int p_{X_0}(x_0)\exp\left(-\frac{{\rm e}^{-2\delta_i}}{2\sigma_{t_i}^2}\|x_i-\alpha_{t_i}x_0\|_2^2\right)\mathrm{d} x_0}\notag\\ &=\left(\frac{\sigma_{t_{i-1}}}{\sigma_{t_i}}\right)^{d}\frac{\int p_{X_0}(x_0)\exp\left(-\frac{{\rm e}^{-2\delta_i}}{2\sigma_{t_i}^2}\|x_i-\alpha_{t_i}x_0\|_2^2\right)\left(1-\frac{(1-{\rm e}^{-2\delta_i})}{2\sigma_{t_i}^2}\|x_i-\alpha_{t_i}x_0\|_2^2 + O(\delta_i^2)\right)\mathrm{d} x_0}{\int p_{X_0}(x_0)\exp\left(-\frac{{\rm e}^{-2\delta_i}}{2\sigma_{t_i}^2}\|x_i-\alpha_{t_i}x_0\|_2^2\right)\mathrm{d} x_0}, \end{align}\] where the first equation comes from \[\begin{align} p_{X_{t_{i}}}(x_{i}) &= (2\pi\sigma_{t_i}^2)^{-d/2}\int p_{X_0}(x_0)\exp\left(-\frac{1}{2\sigma_{t_i}^2}\|x_i-\alpha_{t_i}x_0\|_2^2\right)\mathrm{d} x_0\notag\\ p_{X_{t_{i-1}}}(\widehat{x}_{i})&=(2\pi\sigma_{t_{i-1}}^2)^{-d/2}\int p_{X_0}(x_0)\exp\left(-\frac{1}{2\sigma_{t_{i-1}}^2}\big\|\frac{\alpha_{t_{i-1}}}{\alpha_{t_{i}}}x_{i}-\alpha_{t_{i-1}}x_0\big\|_2^2\right)\mathrm{d} x_0\notag\\ &=(2\pi\sigma_{t_{i-1}}^2)^{-d/2}\int p_{X_0}(x_0)\exp\left(-\frac{\alpha_{t_{i-1}}^2}{2\sigma_{t_{i-1}}^2\alpha_{t_{i}}^2}\big\|x_{i-1}-\alpha_{t_{i}}x_0\big\|_2^2\right)\mathrm{d} x_0\notag\\ &=(2\pi\sigma_{t_{i-1}}^2)^{-d/2}\int p_{X_0}(x_0)\exp\left(-\frac{{\rm e}^{-2\delta_i}}{2\sigma_{t_{i}}^2}\big\|x_{i}-\alpha_{t_{i}}x_0\big\|_2^2\right)\mathrm{d} x_0. \end{align}\] Thus we have \[\begin{align} &\quad\left|\left(\frac{\sigma_{t_{i-1}}}{\sigma_{t_i}}\right)^{-d}\frac{p_{X_{t_{i}}}(x_{i})}{p_{X_{t_{i-1}}}(\widehat{x}_{i})} - 1\right|\notag\\ &\le \frac{\int p_{X_0}(x_0)\exp\left(-\frac{{\rm e}^{-2\delta_i}}{2\sigma_{t_i}^2}\|x_i-\alpha_{t_i}x_0\|_2^2\right)\left(\frac{2\delta_i}{2\sigma_{t_i}^2}\|x_i-\alpha_{t_i}x_0\|_2^2 + O(\delta_i^2)\right)\mathrm{d} x_0}{\int p_{X_0}(x_0)\exp\left(-\frac{{\rm e}^{-2\delta_i}}{2\sigma_{t_i}^2}\|x_i-\alpha_{t_i}x_0\|_2^2\right)\mathrm{d} x_0} \notag\\ &= O(\delta_i)(\|x_i\|_2^2+1). \end{align}\] Instituting into 69 , we have \[\begin{align} \label{eq:proof-lem-distri-sc-4} \frac{p_{X_{t_{i}}}(x_{i})}{p_{X_{t_{i-1}}}(x_{i-1})} &= \left(\frac{\sigma_{t_{i-1}}}{\sigma_{t_i}}\right)^{-d}\exp\left(\nabla \log p_{X_{t_{i-1}}}(x_{i-1})^{\top}(\widehat{x}_{i}-x_{i-1}) \right)\left(1+O(\delta_i)(1+\|x_i\|_2^2)\right) \end{align}\tag{70}\] Combining this with 68 and 67 yields \[\begin{align} \label{eq:proof-lem-dsitri-xsc-7} p_{X_{t_i}\,|\,{X}_{t_{i-1}}}(x_i|x_{i-1}) &=(2\pi\varrho^2)^{-d/2}\exp\left(-\frac{{\rm e}^{-2\delta_{i}}}{2\varrho^2} \big\|\widehat{X}_{t_{i}}-\mu_0\big\|_2^2\right)\notag\\ &\quad \cdot\exp\left(\nabla \log p_{X_{t_{i-1}}}(x_{i-1})^{\top}(\widehat{x}_{i}-x_{i-1}) \right)\left(1+O(\delta_i)(1+\|x_i\|_2^2)\right)\notag\\ &=(2\pi\varrho^2)^{-d/2}\exp\left(-\frac{{\rm e}^{-2\delta_{i}}}{2\varrho^2} \big\|\widehat{X}_{t_{i}}-\mu_0\big\|_2^2+\nabla \log p_{X_{t_{i-1}}}(x_{i-1})^{\top}(\widehat{x}_{i}-x_{i-1}) \right)\notag\\ &\quad \cdot\left(1+O(\delta_i)(1+\|x_i\|_2^2)\right) \end{align}\tag{71}\]

Combining 66 and 71 leads to \[\begin{align} \frac{p_{X_{t_i}\,|\,{X}_{t_{i-1}}}(x_i|x_{i-1})}{\widehat{p}_i(x_i|x_{i-1})} &= \exp\left(\frac{(1-{\rm e}^{-2\delta_{i}})}{2\varrho^2} \big\|x_{i}-\mu_0\big\|_2^2-({\rm e}^{2\delta_{i}}-1)\nabla \log p_{X_{t_{i-1}}}(x_{i-1})^{\top}(\widehat{x}_{i}-x_{i-1})+O(\delta_i)\right)\notag\\ &\qquad \cdot(1+O(\delta_i)(1+\|x_i\|_2^2)) \end{align}\] and \[\begin{align} \frac{p_{X_{t_i}\,|\,{X}_{t_{i-1}}}(x_i|x_{i-1})}{\widehat{p}_i(x_i|x_{i-1})} - 1 = O(\delta_i)\frac{\|x_i-\mu_0\|_2^2}{\varrho^2} + O(\delta_i)\|\widehat{x}_i-x_{i-1}\|_2 + O(\delta_i)\|x_i\|^2 + O(\delta_i). \end{align}\] By using the definition of KL divergence, we have \[\begin{align} \mathsf{KL}(\widehat{p}_{i}\Vert p_{X_{t_i}\,|\,{X}_{t_{i-1}}}) &= \int \log \frac{\widehat{p}_{i}(x_i|x_{i-1})}{p_{X_{t_i}\,|\,{X}_{t_{i-1}}}(x_i|x_{i-1})} \widehat{p}_{i}(x_i|x_{i-1}) \mathrm{d} x_i\notag\\ &=-\int \log \frac{p_{X_{t_i}\,|\,{X}_{t_{i-1}}}(x_i|x_{i-1})}{\widehat{p}_{i}(x_i|x_{i-1})} \widehat{p}_{i}(x_i|x_{i-1}) \mathrm{d} x_i\notag\\ &=-\int \left(\frac{p_{X_{t_i}\,|\,{X}_{t_{i-1}}}(x_i|x_{i-1})}{\widehat{p}_{i}(x_i|x_{i-1})} -1\right)\widehat{p}_{i}(x_i|x_{i-1}) \mathrm{d} x_i \notag\\ &\quad + \frac{1}{2}\int \left(\frac{p_{X_{t_i}\,|\,{X}_{t_{i-1}}}(x_i|x_{i-1})}{\widehat{p}_{i}(x_i|x_{i-1})} -1\right)^2\widehat{p}_{i}(x_i|x_{i-1}) \mathrm{d} x_i\notag\\ &=\frac{1}{2}\int \left(\frac{p_{X_{t_i}\,|\,{X}_{t_{i-1}}}(x_i|x_{i-1})}{\widehat{p}_{i}(x_i|x_{i-1})} -1\right)^2\widehat{p}_{i}(x_i|x_{i-1}) \mathrm{d} x_i\notag\\ &=O(\delta_i^2)\mathbb{E}_{x_i\sim \widehat{p}_i(\cdot\,|\,x_{i-1})}\Bigg[\frac{\|x_i-\mu_0\|_2^2}{\varrho^2} + \|\widehat{x}_i-x_{i-1}\|_2 + \|x_i\|^2+1\Bigg] = O(\delta_i^2), \end{align}\] where the last equation holds since by 63 , \[\frac{\|x_i-\mu_0\|_2^2}{\varrho^2} = \frac{\|\Delta\|_2^2 + \varrho^2}{\varrho^2} = O(1).\] Combining with 64 , we complete the proof.

7.6 Proof of Lemma 4↩︎

We start from the observation that \(p_{\widetilde{X}_i^{\mathsf{sc}}\,|\,\widetilde{X}_{i-1}}({x}_{i}^{\mathsf{sc}}\,|\,{x}_{i-1})\) is a Gaussian distribution and \(x_{i-1}^{\mathsf{c}}\) influences the mean vector: \[\begin{align} p_{\widetilde{X}_i^{\mathsf{sc}}\,|\,\widetilde{X}_{i-1}}({x}_{i}^{\mathsf{sc}}\,|\,{x}_{i-1}) = \phi({x}_{i}^{\mathsf{sc}}; \mu_0 + \Delta(x_{i-1}^{\mathsf{c}}),\sigma_{t_{i}}^2(1-{\rm e}^{-2\delta_{i}})), \end{align}\] where \(\phi(\cdot;\mu,\sigma^2)\) denotes the density function of Gaussian distribution with mean vector \(\mu\) and variance \(\sigma^2\), and \[\begin{align} \mu_0&\mathrel{\vcenter{:}}= \frac{\alpha_{t_i}}{\alpha_{t_{i-1}}} x_{i-1}^{\mathsf{sc}},\notag\\ \Delta(x_{i-1}^{\mathsf{c}}) &\mathrel{\vcenter{:}}= \alpha_{t_{i}}\sigma_{t_{i-1}}\left({\rm e}^{-\lambda_{t_{i-1}}}-{\rm e}^{-2\lambda_{t_{i}}+\lambda_{t_{i-1}}}\right)\nabla_{{x}_{i-1}^{\mathsf{sc}}} \log p_{\lambda_{i-1}}({x}_{i-1}^{\mathsf{c}},{x}_{i-1}^{\mathsf{sc}}). \end{align}\] It can be immediately check that \[\begin{align} \|\Delta(x_{i-1}^{\mathsf{c}})\|_2 \lesssim O(\delta). \end{align}\] By Taylor expansion and denoting the variance as \(\varrho^2=\sigma_{t_{i}}^2(1-{\rm e}^{-2\delta_{i}})\), we have \[\begin{align} p_{\widetilde{X}_i^{\mathsf{sc}}\,|\,\widetilde{X}_{i-1}}({x}_{i}^{\mathsf{sc}}\,|\,{x}_{i-1}) &= \phi({x}_{i}^{\mathsf{sc}}; \mu_0,\varrho^2)\left(1 + \frac{({x}_{i}^{\mathsf{sc}}-\mu_0)^{\top}\Delta(x_{i-1}^{\mathsf{c}})}{\varrho^2} - \frac{\|\Delta(x_{i-1}^{\mathsf{c}})\|_2^2}{\varrho^2} + \frac{(({x}_{i}^{\mathsf{sc}}-\mu_0)^{\top}\Delta(x_{i-1}^{\mathsf{c}}))^2}{\varrho^2}\right)\notag\\ &\quad + O(\|\Delta(x_{i-1}^{\mathsf{c}})\|_2^3). \end{align}\] Thus we have \[\begin{align} &\int p_{\widetilde{X}_i^{\mathsf{sc}}\,|\,\widetilde{X}_{i-1}}({x}_{i}^{\mathsf{sc}}\,|\,{x}_{i-1})p_{{X}_{t_i}^{\mathsf{sc}}\,|\,{X}_{t_{i-1}}}({x}_{i-1}^{\mathsf{c}}\,|\,{x}_{i-1}^{\mathsf{s}}) \mathrm{d}{x}_{i-1}^{\mathsf{c}} \notag\\ &\quad= \int \phi({x}_{i}^{\mathsf{sc}}; \mu_0,\varrho^2)\left(1 + \frac{({x}_{i}^{\mathsf{sc}}-\mu_0)^{\top}\Delta(x_{i-1}^{\mathsf{c}})}{\varrho^2} - \frac{\|\Delta(x_{i-1}^{\mathsf{c}})\|_2^2}{\varrho^2} + \frac{(({x}_{i}^{\mathsf{sc}}-\mu_0)^{\top}\Delta(x_{i-1}^{\mathsf{c}}))^2}{\varrho^2}\right)\notag\\ &\qquad \cdot p_{{X}_{t_{i-1}}^{\mathsf{c}}\,|\,{X}_{t_{i-1}}^{\mathsf{s}}}({x}_{i-1}^{\mathsf{c}}\,|\,{x}_{i-1}^{\mathsf{s}}) \mathrm{d}{x}_{i-1}^{\mathsf{c}}\notag\\ &\qquad + O(\mathbb{E}_{{X}_{t_{i-1}}^{\mathsf{c}}\,|\,{X}_{t_{i-1}}^{\mathsf{s}}}[\|\Delta({X}_{t_{i-1}}^{\mathsf{c}})\|_2^3])\notag\\ &\quad= \phi({x}_{i}^{\mathsf{sc}}; \mu_0,\varrho^2)\bigg(1 + \varrho^{-2}({x}_{i}^{\mathsf{sc}}-\mu_0)^{\top}\mathbb{E}_{{X}_{t_{i-1}}^{\mathsf{c}}\,|\,{X}_{t_{i-1}}^{\mathsf{s}}}[\Delta({X}_{t_{i-1}}^{\mathsf{c}})] - \varrho^{-2}\mathbb{E}_{{X}_{t_{i-1}}^{\mathsf{c}}\,|\,{X}_{t_{i-1}}^{\mathsf{s}}}[\|\Delta({X}_{t_{i-1}}^{\mathsf{c}})\|_2^2]\notag\\ &\qquad\qquad\qquad + \varrho^{-2}\mathbb{E}_{{X}_{t_{i-1}}^{\mathsf{c}}\,|\,{X}_{t_{i-1}}^{\mathsf{s}}}[(({x}_{i}^{\mathsf{sc}}-\mu_0)^{\top}\Delta({X}_{t_{i-1}}^{\mathsf{c}}))^2]\bigg) + O(\mathbb{E}_{{X}_{t_{i-1}}^{\mathsf{c}}\,|\,{X}_{t_{i-1}}^{\mathsf{s}}}[\|\Delta({X}_{t_{i-1}}^{\mathsf{c}})\|_2^3]). \end{align}\] Similarly, we have \[\begin{align} &\int p_{\widetilde{X}_i^{\mathsf{sc}}\,|\,\widetilde{X}_{i-1}}({x}_{i}^{\mathsf{sc}}\,|\,{x}_{i-1})p_{\widetilde{X}_{i-1}^{\mathsf{c}}\,|\,\widetilde{X}_{i-1}^{\mathsf{s}}}({x}_{i-1}^{\mathsf{c}}\,|\,{x}_{i-1}^{\mathsf{s}}) \mathrm{d}{x}_{i-1}^{\mathsf{c}} \notag\\ &\quad= \phi({x}_{i}^{\mathsf{sc}}; \mu_0,\varrho^2)\bigg(1 + \varrho^{-2}({x}_{i}^{\mathsf{sc}}-\mu_0)^{\top}\mathbb{E}_{\widetilde{X}_{i-1}^{\mathsf{c}}\,|\,\widetilde{X}_{i-1}^{\mathsf{s}}}[\Delta(\widetilde{X}_{i-1}^{\mathsf{c}})] - \varrho^{-2}\mathbb{E}_{\widetilde{X}_{i-1}^{\mathsf{c}}\,|\,\widetilde{X}_{i-1}^{\mathsf{s}}}[\|\Delta(\widetilde{X}_{i-1}^{\mathsf{c}})\|_2^2]\notag\\ &\qquad\qquad\qquad\qquad\qquad + \varrho^{-2}\mathbb{E}_{\widetilde{X}_{i-1}^{\mathsf{c}}\,|\,\widetilde{X}_{i-1}^{\mathsf{s}}}[(({x}_{i}^{\mathsf{sc}}-\mu_0)^{\top}\Delta(\widetilde{X}_{i-1}^{\mathsf{c}}))^2]\bigg) + O(\mathbb{E}_{\widetilde{X}_{i-1}^{\mathsf{c}}\,|\,\widetilde{X}_{i-1}^{\mathsf{s}}}[\|\Delta(\widetilde{X}_{i-1}^{\mathsf{c}})\|_2^3]). \end{align}\] These lead to \[\begin{align} &\log \frac{\int p_{\widetilde{X}_i^{\mathsf{sc}}\,|\,\widetilde{X}_{i-1}}({x}_{i}^{\mathsf{sc}}\,|\,{x}_{i-1}) p_{\widetilde{X}_{i-1}^{\mathsf{c}}\,|\,\widetilde{X}_{i-1}^{\mathsf{s}},Y,Z}({x}_{i-1}^{\mathsf{c}}\,|\,{x}_{i-1}^{\mathsf{s}},y,z)\mathrm{d}{x}_{i-1}^{\mathsf{c}}}{\int p_{\widetilde{X}_i^{\mathsf{sc}}\,|\,\widetilde{X}_{i-1}}({x}_{i}^{\mathsf{sc}}\,|\,{x}_{i-1})p_{{X}_{t_{i-1}}^{\mathsf{c}}\,|\,{X}_{t_{i-1}}^{\mathsf{s}}}({x}_{i-1}^{\mathsf{c}}\,|\,{x}_{i-1}^{\mathsf{s}}) \mathrm{d}{x}_{i-1}^{\mathsf{c}}} \notag\\ &\quad = \log \frac{1 + \varrho^{-2}({x}_{i}^{\mathsf{sc}}-\mu_0)^{\top}\mathbb{E}[\Delta(\widetilde{X}_{i-1}^{\mathsf{c}})] - \varrho^{-2}\mathbb{E}[\|\Delta(\widetilde{X}_{i-1}^{\mathsf{c}})\|_2^2]+ \varrho^{-2}\mathbb{E}[(({x}_{i}^{\mathsf{sc}}-\mu_0)^{\top}\Delta(\widetilde{X}_{i-1}^{\mathsf{c}}))^2]}{1 + \varrho^{-2}({x}_{i}^{\mathsf{sc}}-\mu_0)^{\top}\mathbb{E}[\Delta(X_{t_{i-1}}^{\mathsf{c}})] - \varrho^{-2}\mathbb{E}[\|\Delta(X_{t_{i-1}}^{\mathsf{c}})\|_2^2]+ \varrho^{-2}\mathbb{E}[(({x}_{i}^{\mathsf{sc}}-\mu_0)^{\top}\Delta(X_{t_{i-1}}^{\mathsf{c}}))^2]} + O(\delta^3)\notag\\ &\quad \le \frac{\varrho^{-2}({x}_{i}^{\mathsf{sc}}-\mu_0)^{\top}\big(\mathbb{E}[\Delta(\widetilde{X}_{{i-1}}^{\mathsf{c}})-\Delta(X_{t_{i-1}}^{\mathsf{c}})]\big) - \varrho^{-2}\big(\mathbb{E}[\|\Delta(\widetilde{X}_{{i-1}}^{\mathsf{c}})\|_2^2-\|\Delta(X_{t_{i-1}}^{\mathsf{c}})\|_2^2]\big)}{1 + \varrho^{-2}({x}_{i}^{\mathsf{sc}}-\mu_0)^{\top}\mathbb{E}[\Delta(X_{t_{i-1}}^{\mathsf{c}})] - \varrho^{-2}\mathbb{E}[\|\Delta(X_{t_{i-1}}^{\mathsf{c}})\|_2^2]+ \varrho^{-2}\mathbb{E}[(({x}_{i}^{\mathsf{sc}}-\mu_0)^{\top}\Delta(X_{t_{i-1}}^{\mathsf{c}}))^2]}\notag\\ &\qquad + \frac{\varrho^{-2}\mathbb{E}[(({x}_{i}^{\mathsf{sc}}-\mu_0)^{\top}\Delta(\widetilde{X}_{{i-1}}^{\mathsf{c}}))^2-(({x}_{i}^{\mathsf{sc}}-\mu_0)^{\top}\Delta(X_{t_{i-1}}^{\mathsf{c}}))^2]}{1 + \varrho^{-2}({x}_{i}^{\mathsf{sc}}-\mu_0)^{\top}\mathbb{E}[\Delta(X_{t_{i-1}}^{\mathsf{c}})] - \varrho^{-2}\mathbb{E}[\|\Delta(X_{t_{i-1}}^{\mathsf{c}})\|_2^2]+ \varrho^{-2}\mathbb{E}[(({x}_{i}^{\mathsf{sc}}-\mu_0)^{\top}\Delta(X_{t_{i-1}}^{\mathsf{c}}))^2]}. \end{align}\] Therefore, the term considered in ?? is bounded by \[\begin{align} \label{eq:proof-17} &\int \log \frac{\int p_{\widetilde{X}_i^{\mathsf{sc}}\,|\,\widetilde{X}_{i-1}}({x}_{i}^{\mathsf{sc}}\,|\,{x}_{i-1}) p_{\widetilde{X}_{i-1}^{\mathsf{c}}\,|\,\widetilde{X}_{i-1}^{\mathsf{s}},Y,Z}({x}_{i-1}^{\mathsf{c}}\,|\,{x}_{i-1}^{\mathsf{s}},y,z) \mathrm{d}{x}_{i-1}^{\mathsf{c}}}{\int p_{\widetilde{X}_i^{\mathsf{sc}}\,|\,\widetilde{X}_{i-1}}({x}_{i}^{\mathsf{sc}}\,|\,{x}_{i-1})p_{{X}_{t_{i-1}}^{\mathsf{c}}\,|\,{X}_{t_{i-1}}^{\mathsf{s}}}({x}_{i-1}^{\mathsf{c}}\,|\,{x}_{i-1}^{\mathsf{s}})\mathrm{d}{x}_{i-1}^{\mathsf{c}}} p_{\widetilde{X}_{i}^{\mathsf{sc}}\,|\,\widetilde{X}_{{i-1}}^{\mathsf{s}},Y,Z}({x}_i^{\mathsf{sc}}\,|\,{x}_{i-1}^{\mathsf{s}},y,z)\mathrm{d} {x}_i^{\mathsf{sc}} \notag\\ &\lesssim \int \Big(\varrho^{-2}({x}_{i}^{\mathsf{sc}}-\mu_0)^{\top}\big(\mathbb{E}[\Delta(\widetilde{X}_{{i-1}}^{\mathsf{c}})-\Delta(X_{t_{i-1}}^{\mathsf{c}})]\big) - \varrho^{-2}\big(\mathbb{E}[\|\Delta(\widetilde{X}_{{i-1}}^{\mathsf{c}})\|_2^2-\|\Delta(X_{t_{i-1}}^{\mathsf{c}})\|_2^2]\big) \notag\\ &\qquad +\varrho^{-2}\mathbb{E}[(({x}_{i}^{\mathsf{sc}}-\mu_0)^{\top}\Delta(\widetilde{X}_{{i-1}}^{\mathsf{c}}))^2-(({x}_{i}^{\mathsf{sc}}-\mu_0)^{\top}\Delta(X_{t_{i-1}}^{\mathsf{c}}))^2]\Big)p_{\widetilde{X}_{i}^{\mathsf{sc}}\,|\,\widetilde{X}_{{i-1}}^{\mathsf{s}}}({x}_i^{\mathsf{sc}}\,|\,{x}_{i-1}^{\mathsf{s}})\mathrm{d} {x}_i^{\mathsf{sc}}\notag\\ &\le \varrho^{-2}\|\mathbb{E}[{x}_{i}^{\mathsf{sc}}-\mu_0]\|_2^{\top}\|\mathbb{E}[\Delta(X_{t_{i-1}}^{\mathsf{c}})-\Delta(\widetilde{X}_{{i-1}}^{\mathsf{c}})]\|_2 + \varrho^{-2}\big|\mathbb{E}[\|\Delta(X_{t_{i-1}}^{\mathsf{c}})\|_2^2-\|\Delta(\widetilde{X}_{{i-1}}^{\mathsf{c}})\|_2^2]\big|\notag\\ &\quad + \varrho^{-2}\mathbb{E}[\|{x}_{i}^{\mathsf{sc}}-\mu_0\|_2^2]\big\|\mathbb{E}[\Delta(X_{t_{i-1}}^{\mathsf{c}})\Delta(X_{t_{i-1}}^{\mathsf{c}})^{\top}-\Delta(\widetilde{X}_{i-1}^{\mathsf{c}})\Delta(\widetilde{X}_{i-1}^{\mathsf{c}})^{\top}]\big\|_{\mathsf{op}}. \end{align}\tag{72}\] According to the update rule of \(\widetilde{X}_i^{\mathsf{sc}}\), the expectation of \(\widetilde{X}_{i}^{\mathsf{sc}}-\mu_0\) conditioned on \(\widetilde{X}_{i-1}^{\mathsf{s}} = {x}_{i-1}^{\mathsf{s}}\) is bounded by \[\begin{align} \varrho^{-2}\|\mathbb{E}[\widetilde{x}_{i}^{\mathsf{sc}}-\mu_0]\|_2 &= \varrho^{-2}\|\mathbb{E}[\Delta(\widetilde{X}_{i-1}^{\mathsf{c}})\,|\,\widetilde{X}_{i-1}^{\mathsf{s}} = {x}_{i-1}^{\mathsf{s}}] \|_2\notag\\ &=\frac{\alpha_{t_i}\sigma_{t_{i-1}}{\rm e}^{-\lambda_{t_{i-1}}}(1-{\rm e}^{-2\delta_{i}})}{\sigma_{t_i}^2(1-{\rm e}^{-2\delta_{i}})} \|\mathbb{E}[\nabla_{{x}_{i-1}^{\mathsf{sc}}} \log p_{\lambda_{i-1}}(\widetilde{X}_{i-1}^{\mathsf{c}},{x}_{i-1}^{\mathsf{sc}})\,|\,\widetilde{X}_{i-1}^{\mathsf{s}} = {x}_{i-1}^{\mathsf{s}}] \|_2 = O(1). \end{align}\] Similarly, we have \[\begin{align} \varrho^{-2}\mathbb{E}[\|{x}_{i}^{\mathsf{sc}}-\mu_0\|_2^2] =\frac{\alpha_{t_i}^2\sigma_{t_{i-1}}^2{\rm e}^{-2\lambda_{t_{i-1}}}(1-{\rm e}^{-2\delta_{i}})^2}{\sigma_{t_i}^2(1-{\rm e}^{-2\delta_{i}})} \mathbb{E}[\|\nabla_{{x}_{i-1}^{\mathsf{sc}}} \log p_{\lambda_{i-1}}(\widetilde{X}_{i-1}^{\mathsf{c}},{x}_{i-1}^{\mathsf{sc}})\|_2^2\,|\,\widetilde{X}_{i-1}^{\mathsf{s}} = {x}_{i-1}^{\mathsf{s}}] +d =O(1). \end{align}\] Morever, define \[\overline{\Delta}({x}_{i-1}^{\mathsf{c}}) \mathrel{\vcenter{:}}= \delta_i^{-1}\Delta({x}_{i-1}^{\mathsf{c}}).\] We have \(\mathbb{E}[\|\overline{\Delta}({X}_{t_{i-1}}^{\mathsf{c}})\|_2]<\infty\) and \(\mathbb{E}[\|\overline{\Delta}(\widetilde{X}_{i-1}^{\mathsf{c}})\|_2]<\infty\). Instituting into 72 , we have \[\begin{align} \label{eq:proof-18} &\int \log \frac{\int p_{\widetilde{X}_i^{\mathsf{sc}}\,|\,\widetilde{X}_{i-1}}({x}_{i}^{\mathsf{sc}}\,|\,{x}_{i-1}) p_{\widetilde{X}_{i-1}^{\mathsf{c}}\,|\,\widetilde{X}_{i-1}^{\mathsf{s}},Y,Z}({x}_{i-1}^{\mathsf{c}}\,|\,{x}_{i-1}^{\mathsf{s}},y,z)\mathrm{d}{x}_{i-1}^{\mathsf{c}}}{\int p_{\widetilde{X}_i^{\mathsf{sc}}\,|\,\widetilde{X}_{i-1}}({x}_{i}^{\mathsf{sc}}\,|\,{x}_{i-1})p_{{X}_{t_{i-1}}^{\mathsf{c}}\,|\,{X}_{t_{i-1}}^{\mathsf{s}}}({x}_{i-1}^{\mathsf{c}}\,|\,{x}_{i-1}^{\mathsf{s}}) \mathrm{d}{x}_{i-1}^{\mathsf{c}}} p_{\widetilde{X}_{i}^{\mathsf{sc}}\,|\,\widetilde{X}_{{i-1}}^{\mathsf{s}},Y,Z}({x}_i^{\mathsf{sc}}\,|\,{x}_{i-1}^{\mathsf{s}},y,z)\mathrm{d} {x}_i^{\mathsf{sc}} \notag\\ &\quad\lesssim \delta_i\|\mathbb{E}[\overline{\Delta}({X}_{t_{i-1}}^{\mathsf{c}})-\overline{\Delta}(\widetilde{X}_{{i-1}}^{\mathsf{c}})]\|_2 + \delta_i|\mathbb{E}[\|\overline{\Delta}(X_{t_{i-1}}^{\mathsf{c}})\|_2^2-\|\overline{\Delta}(\widetilde{X}_{i-1}^{\mathsf{c}})\|_2^2]|\notag\\ &\qquad + \delta_i^2 \|\mathbb{E}[\overline{\Delta}({X}_{t_{i-1}}^{\mathsf{c}})\overline{\Delta}({X}_{t_{i-1}}^{\mathsf{c}})^{\top}-\overline{\Delta}(\widetilde{X}_{{i-1}}^{\mathsf{c}})\overline{\Delta}(\widetilde{X}_{{i-1}}^{\mathsf{c}})^{\top}]\|_{\mathsf{op}}. \end{align}\tag{73}\] Thus we have \[\begin{align} &\quad \sum_{i=1}^k\mathbb{E}_{{x}_{i-1}^{\mathsf{s}}\sim \widetilde{X}_{i-1}^{\mathsf{s}}\,|\,Y,Z}\bigg[\int \log \frac{\int p_{\widetilde{X}_i^{\mathsf{sc}}\,|\,\widetilde{X}_{i-1}}({x}_{i}^{\mathsf{sc}}\,|\,{x}_{i-1}) p_{\widetilde{X}_{i-1}^{\mathsf{c}}\,|\,\widetilde{X}_{i-1}^{\mathsf{s}},Y,Z}({x}_{i-1}^{\mathsf{c}}\,|\,{x}_{i-1}^{\mathsf{s}},y,z)\mathrm{d}{x}_{i-1}^{\mathsf{c}}}{\int p_{\widetilde{X}_i^{\mathsf{sc}}\,|\,\widetilde{X}_{i-1}}({x}_{i}^{\mathsf{sc}}\,|\,{x}_{i-1})p_{{X}_{t_{i-1}}^{\mathsf{c}}\,|\,{X}_{t_{i-1}}^{\mathsf{s}}}({x}_{i-1}^{\mathsf{c}}\,|\,{x}_{i-1}^{\mathsf{s}}) \mathrm{d}{x}_{i-1}^{\mathsf{c}}}\notag\\ &\qquad\qquad\qquad\qquad\qquad\cdot p_{\widetilde{X}_{i}^{\mathsf{sc}}\,|\,\widetilde{X}_{{i-1}}^{\mathsf{s}}}({x}_i^{\mathsf{sc}}\,|\,{x}_{i-1}^{\mathsf{s}},y,z)\mathrm{d} {x}_i^{\mathsf{sc}}\bigg]\notag\\ &\lesssim \max_i\mathbb{E}_{x_{i-1}^{\mathsf{sc}}\sim p_{\widetilde{X}_{i-1}^{\mathsf{sc}}\,|\,Y,Z}}\big[\|\mathbb{E}[\overline{\Delta}({X}_{t_{i-1}}^{\mathsf{c}})-\overline{\Delta}(\widetilde{X}_{{i-1}}^{\mathsf{c}})\,|\,\widetilde{X}_{i-1}^{\mathsf{sc}}=X_{t_{i-1}}^{\mathsf{sc}}=x_{i-1}^{\mathsf{sc}}]\|_2\big]\notag\\ &\quad + \max_i\mathbb{E}_{x_{i-1}^{\mathsf{sc}}\sim p_{\widetilde{X}_{i-1}^{\mathsf{sc}}\,|\,Y,Z}}\big[|\mathbb{E}[\|\overline{\Delta}(X_{t_{i-1}}^{\mathsf{c}})\|_2^2-\|\overline{\Delta}(\widetilde{X}_{i-1}^{\mathsf{c}})\|_2^2\,|\,\widetilde{X}_{i-1}^{\mathsf{sc}}=X_{t_{i-1}}^{\mathsf{sc}}=x_{i-1}^{\mathsf{sc}}]|\big]\notag\\ &\qquad + \delta\max_i \mathbb{E}_{x_{i-1}^{\mathsf{sc}}\sim p_{\widetilde{X}_{i-1}^{\mathsf{sc}}\,|\,Y,Z}}\big[\|\mathbb{E}[\overline{\Delta}({X}_{t_{i-1}}^{\mathsf{c}})\overline{\Delta}({X}_{t_{i-1}}^{\mathsf{c}})^{\top}-\overline{\Delta}(\widetilde{X}_{{i-1}}^{\mathsf{c}})\overline{\Delta}(\widetilde{X}_{{i-1}}^{\mathsf{c}})^{\top}\,|\,\widetilde{X}_{i-1}^{\mathsf{sc}}=X_{t_{i-1}}^{\mathsf{sc}}=x_{i-1}^{\mathsf{sc}}]\|_{\mathsf{op}}\big] \to 0, \end{align}\] as Lemma 2 implies that the following limit holds for any function \(f\) with finite expectation: \[\mathbb{E}_{x_{i-1}^{\mathsf{sc}}\sim p_{\widetilde{X}_{i-1}^{\mathsf{sc}}\,|\,Y,Z}}\big[\mathbb{E}[f(X_{t_{i-1}}^{\mathsf{c}})-f(\widetilde{X}_{{i-1}}^{\mathsf{c}})\,|\,\widetilde{X}_{i-1}^{\mathsf{sc}}=X_{t_{i-1}}^{\mathsf{sc}}=x_{i-1}^{\mathsf{sc}}]\big]\to 0.\]

7.7 Proof of Lemma 6↩︎

We will bound the norm of \(\|e_{t_i,j}\|_2\) for \(j=1,2,3\) separately. We start from \(\|e_{t_i,1}\|_2\), which is controlled by \(|\frac{\sigma_{t_{i+1}}}{\sigma_{t_i}}-1|\|\widehat{X}_{t_i}^{\mathsf{c}}\|_2\) according to its definition. Note that \(\sigma_{t_{i+1}}\le \sigma_{t_{i}}\) and \(\alpha_{t_{i+1}}\ge \alpha_{t_i}\). Thus we have \[\begin{align} \label{eq:proof-diff-sigma} \big|\frac{\sigma_{t_{i+1}}}{\sigma_{t_i}}-1\big| = 1-\frac{\sigma_{t_{i+1}}}{\sigma_{t_i}} \le 1-\frac{\alpha_{t_i}}{\alpha_{t_{i+1}}}\frac{\sigma_{t_{i+1}}}{\sigma_{t_i}} = 1 - \frac{{\rm e}^{-\lambda_{t_{i+1}}}}{{\rm e}^{-\lambda_{t_i}}} = 1 - {\rm e}^{-\delta_{{i+1}}}\le \delta_{{i+1}}. \end{align}\tag{74}\] Thus we have \[\begin{align} \label{eq:proof-lem-boundet-1} \|e_{t_i,1}({x}_{t_i}^{\mathsf{c}})\|_2^2=\Big\|\left(\frac{\sigma_{t_{i+1}}}{\sigma_{t_{i}}}-1\right)\sqrt{1-\eta(1 - e^{-2\delta_{i+1}})}{x}_{t_{i}}^{\mathsf{c}}\Big\|_2^2 \le \delta_{{i+1}}^2 \|{x}_{t_i}^{\mathsf{c}}\|_2^2. \end{align}\tag{75}\]

For the error term \(\|e_{t_i,2}\|_2\), recalling that \(x_0\) is bounded, which implies that \(\mu_{t_i}^{\mathsf{c}}\) is also bounded by some constant \(B\) as it is a conditional expectation of \(x_0\). Thus we have \[\begin{align} \label{eq:proof-1} \|e_{t_i,2}({x}_{t_i}^{\mathsf{c}})\|_2 &=\Big\|\big(\left(\alpha_{t_{i+1}}-\alpha_{t_i}\right) + \left(\alpha_{t_{i+1}}e^{-\delta_{i+1}}-\alpha_{t_i}\right)\sqrt{1-\eta(1 - e^{-2\delta_{i+1}})}\big)\mu_{t_{i}}^{\mathsf{c}}({x}_{t_i})\Big\|_2\notag\\ & \le B\left(\alpha_{t_{i+1}} - \alpha_{t_i} + |\alpha_{t_{i+1}}{\rm e}^{-\delta_{{i+1}}} - \alpha_{t_i}|\right) \le B\left(2\alpha_{t_{i+1}} - 2\alpha_{t_i} + \alpha_{t_{i+1}}(1-{\rm e}^{-\delta_{{i+1}}})\right). \end{align}\tag{76}\] Note that \[\begin{align} \label{eq:proof-diff-alpha} \alpha_{t_{i+1}} - \alpha_{t_i} = \alpha_{t_{i+1}}\left(1 - \frac{\alpha_{t_i}}{\alpha_{t_{i+1}}}\right) \le \alpha_{t_{i+1}}\left(1 - \frac{\sigma_{t_{i+1}}}{\sigma_{t_i}}\frac{\alpha_{t_i}}{\alpha_{t_{i+1}}}\right) = \alpha_{t_{i+1}}\left(1-{\rm e}^{-\delta_{{i+1}}}\right) \le \alpha_{t_{i+1}} \delta_{{i+1}}. \end{align}\tag{77}\] Inserting into 76 , we have \[\begin{align} \label{eq:proof-lem-boundet-2} \|e_{t_i,2}({x}_{t_i}^{\mathsf{c}})\|_2^2\le B^2\alpha_{t_{i+1}}^2\left(2\delta_{{i+1}} + \delta_{{i+1}}\right)^2 = O(\delta_{{i+1}}^2). \end{align}\tag{78}\]

For the error term \(\|e_{t_i,3}\|_2\), we have \[\begin{align} \|e_{t_i,3}({x}_{t_i},{x}_{t_{i+1}}^{\mathsf{s}})\|_2 &=\Big\|\big(1 - \sqrt{1-\eta(1 - e^{-2\delta_{i+1}})}\big)\big(\sigma_{t_{i}}\epsilon_{t_{i}}^{\mathsf{c}}({X}_{t_{i}} )-\sigma_{t_{i+1}}\epsilon_{t_{i+1}}^{\mathsf{c}}({x}_{t_{i+1}}^{\mathsf{est}} )\big)\Big\|_2\notag\\ &\overset{\text{(i)}}{\le} \sigma_{t_{i+1}}^{-2}\gamma_i\left\|\sigma_{t_{i}}\epsilon_{t_{i}}^{\mathsf{c}}-\sigma_{t_{i+1}}\epsilon_{t_{i+1}}^{\mathsf{c}}\right\|_2 \notag\\ &=\sigma_{t_{i+1}}^{-2}\gamma_i \Big\|\sigma_{t_i}^2\nabla \log p_{X_{t_i}^{\mathsf{c}},X_{t_i}^{\mathsf{sc}}|X_{t_i}^{\mathsf{s}}}({x}_{t_i}^{\mathsf{c}},{x}_{t_i}^{\mathsf{sc}}|\alpha_{t_i}\overline{Y}_{t_i} + \hat{\sigma}_{t_i}\overline{Z}_{t_i}) \notag\\ &\qquad \qquad - \sigma_{t_{i+1}}^2\nabla \log p_{X_{t_{i+1}}^{\mathsf{c}},X_{t_{i+1}}^{\mathsf{sc}}|x_{t_{i+1}}^{\mathsf{s}}}({x}_{t_i}^{\mathsf{c}},{x}_{t_{i+1}}^{\mathsf{sc}}|\alpha_{t_{i+1}}\overline{Y}_{t_i} + \hat{\sigma}_{t_{i+1}}\overline{Z}_{t_i})\Big\|, \end{align}\] where \({x}_{t_{i+1}}^{\mathsf{est}}\) is defined by \(V_{\mathcal{S}^{\mathsf{c}}}^{\top}{x}_{t_{i+1}}^{\mathsf{est}} = {x}_{t_{i}}^{\mathsf{c}}\) and \(V_{\mathcal{S}}^{\top}{x}_{t_{i+1}}^{\mathsf{est}} = {x}_{t_{i+1}}^{\mathsf{s}}\), (i) arises from \[\begin{align} 1-\sqrt{1-\eta(1-{\rm e}^{-2\delta_{{i+1}}})} \le \eta(1-{\rm e}^{-2\delta_{{i+1}}}) = \sigma_{t_{i+1}}^{-2}\gamma_{i}. \end{align}\] and the last equation comes from 43 . Combining with 44 , we have \[\begin{align} \label{eq:proof-6} &\quad\|e_{t_i,3}({x}_{t_i},{x}_{t_{i+1}}^{\mathsf{s}})\|_2 \notag\\ &\le\sigma_{t_{i+1}}^{-2}\gamma_i\Big\|\mathbb{E}_{X_{0}^{\mathsf{c}}}[{x}_{t_i}^{\mathsf{c}}-\alpha_{t_i}X_{0}^{\mathsf{c}}|X_{t_i}^{\mathsf{c}}={x}_{t_i}^{\mathsf{c}},X_{t_i}^{\mathsf{sc}}={x}_{t_i}^{\mathsf{sc}}, X_{t_i}^{\mathsf{s}}=\alpha_{t_i}\overline{Y}_{t_i} + \hat{\sigma}_{t_i}\overline{Z}_{t_i}] \notag\\ &\qquad \quad - \mathbb{E}_{X_{0}^{\mathsf{c}}}[{x}_{t_i}^{\mathsf{c}}-\alpha_{t_{i+1}}X_{0}^{\mathsf{c}}|X_{t_{i+1}}^{\mathsf{c}}={x}_{t_i}^{\mathsf{c}},X_{t_{i+1}}^{\mathsf{sc}}={x}_{t_{i+1}}^{\mathsf{sc}}, X_{t_{i+1}}^{\mathsf{s}}=\alpha_{t_{i+1}}\overline{Y}_{t_{i+1}} + \hat{\sigma}_{t_{i+1}}\overline{Z}_{t_{i+1}}]\Big\|_2\notag\\ &= \sigma_{t_{i+1}}^{-2}\gamma_i\Big\|\mathbb{E}_{X_{0}^{\mathsf{c}}}[\alpha_{t_i}X_{0}^{\mathsf{c}}|X_{t_i}^{\mathsf{c}}={x}_{t_i}^{\mathsf{c}},X_{t_i}^{\mathsf{sc}}={x}_{t_i}^{\mathsf{sc}}, X_{t_i}^{\mathsf{s}}=\alpha_{t_i}\overline{Y}_{t_i} + \hat{\sigma}_{t_i}\overline{Z}_{t_i}] \notag\\ &\qquad \quad - \mathbb{E}_{X_{0}^{\mathsf{c}}}[\alpha_{t_{i+1}}X_{0}^{\mathsf{c}}|X_{t_{i+1}}^{\mathsf{c}}={x}_{t_i}^{\mathsf{c}},X_{t_{i+1}}^{\mathsf{sc}}={x}_{t_{i+1}}^{\mathsf{sc}}, X_{t_{i+1}}^{\mathsf{s}}=\alpha_{t_{i+1}}\overline{Y}_{t_{i+1}} + \hat{\sigma}_{t_{i+1}}\overline{Z}_{t_{i+1}}]\Big\|_2\notag\\ &\le\sigma_{t_{i+1}}^{-2}\gamma_i (\alpha_{t_{i+1}}-\alpha_{t_{i}})\Big\|\mathbb{E}_{X_{0}^{\mathsf{c}}}[X_{0}^{\mathsf{c}}|X_{t_i}^{\mathsf{c}}={x}_{t_i}^{\mathsf{c}},X_{t_i}^{\mathsf{sc}}={x}_{t_i}^{\mathsf{sc}}, X_{t_i}^{\mathsf{s}}=\alpha_{t_i}\overline{Y}_{t_i} + \hat{\sigma}_{t_i}\overline{Z}_{t_i}]\Big\|_2 \notag\\ &\qquad \quad +\sigma_{t_{i+1}}^{-2}\gamma_i\alpha_{t_{i+1}}\Big\|\mathbb{E}_{X_{0}^{\mathsf{c}}}[X_{0}^{\mathsf{c}}|X_{t_i}^{\mathsf{c}}=x_{t_i}^{\mathsf{c}},X_{t_i}^{\mathsf{sc}}=x_{t_i}^{\mathsf{sc}}, X_{t_i}^{\mathsf{s}}=\alpha_{t_i}\overline{Y}_{t_i} + \hat{\sigma}_{t_i}\overline{Z}_{t_i}] \notag\\ &\qquad \quad - \mathbb{E}_{X_{0}^{\mathsf{c}}}[X_{0}^{\mathsf{c}}|X_{t_{i+1}}^{\mathsf{c}}=x_{t_i}^{\mathsf{c}},X_{t_{i+1}}^{\mathsf{sc}}=x_{t_{i+1}}^{\mathsf{sc}}, X_{t_{i+1}}^{\mathsf{s}}=\alpha_{t_{i+1}}\overline{Y}_{t_{i+1}} + \hat{\sigma}_{t_{i+1}}\overline{Z}_{t_{i+1}}]\Big\|_2. \end{align}\tag{79}\] Recall that \(X_0\) is bounded. By using 77 , the first term is bounded by \[\begin{align} \label{eq:proof-5} (\alpha_{t_{i+1}}-\alpha_{t_{i}})\Big\|\mathbb{E}_{X_{0}^{\mathsf{c}}}[X_{0}^{\mathsf{c}}|X_{t_i}^{\mathsf{c}}={x}_{t_i}^{\mathsf{c}},X_{t_i}^{\mathsf{sc}}={x}_{t_i}^{\mathsf{sc}}, X_{t_i}^{\mathsf{s}}=\alpha_{t_i}\overline{Y}_{t_i} + \hat{\sigma}_{t_i}\overline{Z}_{t_i}]\Big\|_2 = O(\delta_{{i+1}}). \end{align}\tag{80}\] We claim that the second term is bounded by the following inequality, whose proof is postponed to the end of this section. \[\begin{align} \label{eq:proof-4} &\Big\|\mathbb{E}_{X_{0}^{\mathsf{c}}}[X_{0}^{\mathsf{c}}|X_{t_i}^{\mathsf{c}}=x_{t_i}^{\mathsf{c}},X_{t_i}^{\mathsf{sc}}=x_{t_i}^{\mathsf{sc}}, X_{t_i}^{\mathsf{s}}=\alpha_{t_i}\overline{Y}_{t_i} + \hat{\sigma}_{t_i}\overline{Z}_{t_i}]\notag\\ &\quad - \mathbb{E}_{X_{0}^{\mathsf{c}}}[X_{0}^{\mathsf{c}}|X_{t_{i+1}}^{\mathsf{c}}=x_{t_i}^{\mathsf{c}},X_{t_{i+1}}^{\mathsf{sc}}=x_{t_{i+1}}^{\mathsf{sc}}, X_{t_{i+1}}^{\mathsf{st}}=\alpha_{t_{i+1}}\overline{Y}_{t_{i+1}} + \hat{\sigma}_{t_{i+1}}\overline{Z}_{t_{i+1}}]\Big\|_2\notag\\ &\qquad \lesssim \bigg(\|x_{t_i}^{\mathsf{c}}\|_2 +\|x_{t_i}^{\mathsf{sc}}\|_2 + \|Z\|_2+ 1\bigg)\delta_{{i+1}} + \|x_{t_{i+1}}^{\mathsf{sc}}-x_{t_i}^{\mathsf{sc}}\|_2. \end{align}\tag{81}\] Combining 81 and 80 together with 79 , we have \[\begin{align} \label{eq:proof-lem-boundet-3} \|e_{t_{i,3}}({x}_{t_i},{x}_{t_{i+1}}^{\mathsf{s}})\|_2\lesssim \bigg(\|x_{t_i}^{\mathsf{c}}\|_2 +\|x_{t_i}^{\mathsf{sc}}\|_2 + \|Z\|_2+ 1\bigg)\delta_{{i+1}}\gamma_i + \gamma_i\|x_{t_{i+1}}^{\mathsf{sc}}-x_{t_i}^{\mathsf{sc}}\|_2. \end{align}\tag{82}\]

For the last term in the right-hand-side of 46 , we have \[\begin{align} \label{eq:proof-lem-boundet-4} &\quad\left\|\Bigg(1 - \sqrt{1-\eta(1 - e^{-2\delta_{i+1}})} - \frac{\eta(1 - e^{-2\delta_{i+1}})}{2}\Bigg)\sigma_{t_{i+1}}\epsilon_{t_{i+1}}^{\mathsf{c}}\right\|_2 \notag\\ &\le \Bigg|1 - \sqrt{1-\eta(1 - e^{-2\delta_{i+1}})} - \frac{\eta(1 - e^{-2\delta_{i+1}})}{2}\Bigg|\sigma_{t_{i+1}}\|\epsilon_{t_{i+1}}^{\mathsf{c}}\|_2\notag\\ &\lesssim \gamma_i^2\frac{\|\epsilon_{t_{i+1}}^{\mathsf{c}}\|_2}{\sigma_{t_{i+1}}^3} \le \frac{\gamma_i^2}{\sigma_{t_{i+1}}^4}(\|x_{t_i}^{\mathsf{c}}\|_2 + \alpha_{t_i}B). \end{align}\tag{83}\]

Combining 75 , 78 , 82 , and 83 , we have \[\begin{align} \|e_{t_i}(x_{t_i},x_{t_{i+1}}^{\mathsf{s}})\|_2^2 &\lesssim \bigg(\|x_{t_i}^{\mathsf{c}}\|_2 +\|x_{t_i}^{\mathsf{sc}}\|_2 + \|Z\|_2+ 1\bigg)^2\delta_{{i+1}}^2+ (\|x_{t_i}^{\mathsf{c}}\|_2^2+1)\gamma_i^4+\gamma_i^2\|x_{t_{i+1}}^{\mathsf{sc}}-x_{t_i}^{\mathsf{sc}}\|_2^2. \end{align}\] It suffices to prove that \[\begin{align} \mathbb{E}_{\widehat{X}_{t_{i+1}}^{\mathsf{sc}}|\widehat{X}_{t_i}=x_{t_i}}[\|\widehat{X}_{t_{i+1}}^{\mathsf{sc}}-\widehat{X}_{t_i}^{\mathsf{sc}}\|_2^2] =O(\delta_{{i+1}}^2)(\|x_{t_i}\|_2^2+1) + O(\delta_{i}). \end{align}\] According to the update rule of \(\widehat{X}_{t_{i+1}}^{\mathsf{sc}}\), we have \[\begin{align} \mathbb{E}_{\widehat{X}_{t_{i+1}}^{\mathsf{sc}}|\widehat{X}_{t_i}=x_{t_i}}[\|\widehat{X}_{t_{i+1}}^{\mathsf{sc}}-\widehat{X}_{t_i}^{\mathsf{sc}}\|_2^2] &\lesssim \bigg(\frac{\sigma_{t_{i+1}}}{\sigma_{t_i}}{\rm e}^{-\delta_{i+1}}-1\bigg)^2\|x_{t_i}^{\mathsf{sc}}\|_2^2 + \delta_{{i+1}}^2 + \delta_{i+1}\mathbb{E}[\|z_{t_i}^{\mathsf{sc}}\|_2^2]\notag\\ & = \delta_{{i+1}}^2(\|x_{t_i}^{\mathsf{sc}}\|_2^2+1). \end{align}\] and complete the proof.

7.7.0.1 Proof of 81 .

For the second term, we introduce the following notation \(q_{\lambda_{i}}(x_0|x')\) to simplify the expression: \[\begin{align} q_{\lambda_{i}}(x_0|x') &\mathrel{\vcenter{:}}= p_{X_{0}|X_{t_i}}(x_0|x') = \frac{\phi(x'|\alpha_{t_i}x_0,\sigma_{t_i})p_{X_0}(x_0)}{p_{X_{t_i}}(x')}, \end{align}\] where \(\phi(\cdot|\mu,\sigma)\) denotes the Gaussian density functon with mean vector \(\mu\) and covariance matrix \(\sigma^2I\). Armed with this notation, we can control the second term as \[\begin{align} \label{eq:proof-2} &\Big\|\mathbb{E}_{X_{0}^{\mathsf{c}}}[X_{0}^{\mathsf{c}}|X_{t_i}^{\mathsf{c}}=x_{t_i}^{\mathsf{c}},X_{t_i}^{\mathsf{sc}}=x_{t_i}^{\mathsf{sc}}, X_{t_i}^{\mathsf{s}}=\alpha_{t_i}\overline{Y}_{t_i} + \hat{\sigma}_{t_i}\overline{Z}_{t_i}]\notag\\ &\quad - \mathbb{E}_{X_{0}^{\mathsf{c}}}[X_{0}^{\mathsf{c}}|X_{t_{i+1}}^{\mathsf{c}}=x_{t_i}^{\mathsf{c}},X_{t_{i+1}}^{\mathsf{sc}}=x_{t_{i+1}}^{\mathsf{sc}}, X_{t_{i+1}}^{\mathsf{s}}=\alpha_{t_{i+1}}\overline{Y}_{t_{i+1}} + \hat{\sigma}_{t_{i+1}}\overline{Z}_{t_{i+1}}]\Big\|_2\notag\\ &\quad=\left\|\int x_0 \left(q_{\lambda_{i}}(x_0|\tilde{x}_{t_i}) - q_{\lambda_{i+1}}(x_0|\tilde{x}_{t_{i+1}})\right)\mathrm{d} x_0\right\|_2 \le B\int |q_{\lambda_{i}}(x_0|\tilde{x}_{t_i}) - q_{\lambda_{i+1}}(x_0|\tilde{x}_{t_{i+1}})|\mathrm{d} x_0, \end{align}\tag{84}\] where \(\tilde{x}_{t_i}\mathrel{\vcenter{:}}= [x_{t_i}^{\mathsf{c}},x_{t_i}^{\mathsf{sc}},\alpha_{t_{i}}\overline{Y}_{t_{i}}+\hat{\sigma}_{t_{i}}\overline{Z}_{t_{i}}]\) and \(\tilde{x}_{t_{i+1}}\mathrel{\vcenter{:}}= [x_{t_i}^{\mathsf{c}},x_{t_{i+1}}^{\mathsf{sc}},\alpha_{t_{i+1}}\overline{Y}_{t_{i+1}}+\hat{\sigma}_{t_{i+1}}\overline{Z}_{t_{i+1}}]\). According to the definition of \(q_{\lambda_i}\), we have \[\begin{align} \label{eq:proof-7} \frac{1}{q_{\lambda_i}(x|x')}\left|\frac{\partial q_{\lambda_i}(x|x')}{\partial \alpha_{t_i}}\right| &= \frac{\partial \log q_{\lambda_i}(x|x')}{\partial \alpha_{t_i}} = \frac{\partial \log \phi(x'|\alpha_{t_i}x,\sigma_{t_i})}{\partial \alpha_{t_i}} - \frac{\partial \log p_{X_{t_i}}(x')}{\partial \alpha_{t_i}}\notag\\ &=-\frac{1}{2}\frac{\partial}{\partial \alpha_{t_i}}\frac{1}{\sigma_{t_i}^2}\|x'-\alpha_{t_i}x\|_2^2 - \frac{\partial \log p_{X_{t_i}}(x')}{\partial \alpha_{t_i}}. \end{align}\tag{85}\] Moreover, we have \[\begin{align} \left|\frac{\partial \log p_{X_{t_i}}(x')}{\partial \alpha_{t_i}}\right| &= \frac{1}{2\sigma_{t_i}^2}\left|\int \frac{\partial}{\partial \alpha_{t_i}}\|x'-\alpha_{t_i}x\|_2^2\frac{\phi(x'|\alpha_{t_i}x,\sigma_{t_i})p_{X_0}(x)}{p_{X_{t_i}}(x')} \mathrm{d} x\right|\notag\\ &= \frac{1}{\sigma_{t_i}^2}\left|\int (x'-\alpha_{t_i}x)^{\top}x \frac{\phi(x'|\alpha_{t_i}x,\sigma_{t_i})p_{X_0}(x)}{p_{X_{t_i}}(x')} \mathrm{d} x\right|\notag\\ &= \frac{1}{\sigma_{t_i}^2}\left|\int (x'-\alpha_{t_i}x)^{\top}x q_{\lambda_i}(x|x') \mathrm{d} x\right|\notag\\ &\lesssim O(\|x'\|_2+1). \end{align}\] Substituting into 85 , we have \[\begin{align} \frac{1}{q_{\lambda_i}(x|x')}\left|\frac{\partial q_{\lambda_i}(x|x')}{\partial \alpha_{t_i}}\right| &\lesssim O(\|x'\|_2 + 1). \end{align}\]

Furthermore, we have the following inequality in a similar way \[\begin{align} \label{eq:proof-8} \frac{1}{q_{\lambda_i}(x|x')}\frac{\partial q_{\lambda_i}(x|x')}{\partial \sigma_{t_i}} &=-\frac{1}{2}\frac{\partial}{\partial \sigma_{t_i}}\frac{1}{\sigma_{t_i}^2}\|x'-\alpha_{t_i}x\|_2^2 -\frac{d}{\sigma_{t_i}}- \frac{\partial \log p_{X_{t_i}}(x')}{\partial \sigma_{t_i}} \notag\\ &\overset{\text{(i)}}{=} \sigma_{t_i}^{-3}\|x'-\alpha_{t_i}x\|_2^2-\int \sigma_{t_i}^{-3}\|x'-\alpha_{t_i}x\|_2^2 q_{\lambda_i}(x|x') \mathrm{d} x, \end{align}\tag{86}\] where (i) comes from \[\begin{align} \frac{\partial \log p_{X_{t_i}}(x')}{\partial \sigma_{t_i}} &= \int \sigma_{t_i}^{-3}\|x'-\alpha_{t_i}x\|_2^2 q_{\lambda_i}(x|x') \mathrm{d} x - \frac{d}{\sigma_{t_i}}. \end{align}\] By using the bounded property of \(X_0\) again, we have \[\begin{align} \left|\frac{1}{q_{\lambda_i}(x|x')}\frac{\partial q_{\lambda_i}(x|x')}{\partial \sigma_{t_i}} \right| =O(\|x'\|_2+1). \end{align}\] In addition, we have \[\begin{align} \nabla_{x'} \log q_{\lambda_i}(x|x') &= -\nabla_{x'} \frac{1}{2\sigma_{t_i}^2}\|x'-\alpha_{t_i}x\|_2^2 - \nabla_{x'} \log p_{X_{t_i}}(x') \notag\\ &= -\frac{1}{\sigma_{t_i}^2}(x'-\alpha_{t_i}x) + \frac{1}{\sigma_{t_i}^2}\mathbb{E}[x'-\alpha_{t_i}X_0|X_{t_i}=x'],\notag\\ \|\nabla_{x'} \log q_{\lambda_i}(x|x')\|_2&=O(\|x'\|_2). \end{align}\] Moreover, we have \[\begin{align} \|\tilde{x}_{t_{i+1}} - \tilde{x}_{t_{i}}\|_2 \le (\alpha_{t_{i+1}} - \alpha_{t_i})\|\overline{y}_{t_i}\|_2 + (\sigma_{t_{i+1}} - \sigma_{t_i})\|\overline{Z}_{t_i}\|_2 + \|x_{t_{i+1}}^{\mathsf{sc}}-x_{t_i}^{\mathsf{sc}}\|_2. \end{align}\] Combining these together, we have \[\begin{align} &\quad|q_{\lambda_{i}}(x|\tilde{x}_{t_i}) - q_{\lambda_{i+1}}(x|\tilde{x}_{t_{i+1}})|\notag\\ &\lesssim q_{\lambda_{i}}(x|\tilde{x}_{t_i})(\|x_{t_i}^{\mathsf{c}}\|_2 +\|x_{t_i}^{\mathsf{sc}}\|_2 + \|Z\|_2+ 1) (|\alpha_{t_i}-\alpha_{t_{i+1}}| + |\sigma_{t_i} -\sigma_{t_{i+1}}|) \notag\\ &\quad +q_{\lambda_{i}}(x|\tilde{x}_{t_i})\|x_{t_{i+1}}^{\mathsf{sc}}-x_{t_i}^{\mathsf{sc}}\|_2+ O((|\alpha_{t_i}-\alpha_{t_{i+1}}| + |\sigma_{t_i} -\sigma_{t_{i+1}}|)^2) + O(\|x_{t_{i+1}}^{\mathsf{sc}}-x_{t_i}^{\mathsf{sc}}\|_2^2) \end{align}\] According to 77 and 74 , we have \(|\alpha_{t_i}-\alpha_{t_{i+1}}|=O(\delta_{{i+1}})\) and \(|\sigma_{t_i} -\sigma_{t_{i+1}}|=O(\delta_{{i+1}})\), and thus \[\begin{align} \label{eq:proof-3} |q_{\lambda_{i}}(x|\tilde{x}_{t_i}) - q_{\lambda_{i+1}}(x|\tilde{x}_{t_{i+1}})| &\lesssim q_{\lambda_{i}}(x|\tilde{x}_{t_i})\bigg(\|x_{t_i}^{\mathsf{c}}\|_2 +\|x_{t_i}^{\mathsf{sc}}\|_2 + \|Z\|_2+ 1\bigg)\delta_{{i+1}} \notag\\ &\quad +q_{\lambda_{i}}(x|\tilde{x}_{t_i})\|x_{t_{i+1}}^{\mathsf{sc}}-x_{t_i}^{\mathsf{sc}}\|_2 + O(\delta_{{i+1}}^2) + O(\|x_{t_{i+1}}^{\mathsf{sc}}-x_{t_i}^{\mathsf{sc}}\|_2^2). \end{align}\tag{87}\] Substituting 87 into 84 , we complete the proof.

8 Extension to general \(A\)↩︎

For \(V_{\mathcal{S}^{\mathsf{c}}}^{\top} x_{t_i}, V_{\mathcal{S}_{t_i}^{\mathsf{prior}}}^{\top} x_{t_i}\), we aim to approximately generate them according to the following conditional distribution: \[\begin{align} V_{\mathcal{S}^{\mathsf{c}}}^{\top} \widehat{X}_{t_i}, V_{\mathcal{S}_{t_i}^{\mathsf{prior}}}^{\top} \widehat{X}_{t_i} \,|\,V_{\mathcal{S}_{t_i}^{\mathsf{meas}}}^{\top} \widehat{X}_{t_i}, V_{\mathcal{S}_{t_i}^{\mathsf{prior}}}^{\top} \widehat{X}_{\tau}\sim p_{V_{\mathcal{S}^{\mathsf{c}}}^{\top} X_{t_i}, V_{\mathcal{S}_{t_i}^{\mathsf{prior}}}^{\top} X_{t_i} \,|\,V_{\mathcal{S}_{t_i}^{\mathsf{meas}}}^{\top} X_{t_i}, V_{\mathcal{S}_{t_i}^{\mathsf{prior}}}^{\top} X_{\tau}} \end{align}\] Towards this, we need to calculate the score function, i.e., the log gradient of the above conditional density with respect to \(V_{\mathcal{S}^{\mathsf{c}}}^{\top} x_{t_i}\) and \(V_{\mathcal{S}_{t_i}^{\mathsf{prior}}}^{\top} x_{t_i}\). In particular, the gradient with respect to \(V_{\mathcal{S}^{\mathsf{c}}}^{\top} x_{t_i}\) is given by \[\begin{align} &\nabla_{V_{\mathcal{S}^{\mathsf{c}}}^{\top} x_{t_i}}\log p_{V_{\mathcal{S}^{\mathsf{c}}}^{\top} X_{t_i}, V_{\mathcal{S}_{t_i}^{\mathsf{prior}}}^{\top} X_{t_i} \,|\,V_{\mathcal{S}_{t_i}^{\mathsf{meas}}}^{\top} X_{t_i}, V_{\mathcal{S}_{t_i}^{\mathsf{prior}}}^{\top} X_{\tau}}(V_{\mathcal{S}^{\mathsf{c}}}^{\top} x_{t_i}, V_{\mathcal{S}_{t_i}^{\mathsf{prior}}}^{\top} x_{t_i} \,|\,V_{\mathcal{S}_{t_i}^{\mathsf{meas}}}^{\top} x_{t_i}, V_{\mathcal{S}_{t_i}^{\mathsf{prior}}}^{\top} x_{\tau})\notag\\ &\quad =\nabla_{V_{\mathcal{S}^{\mathsf{c}}}^{\top} x_{t_i}}\log p_{V_{\mathcal{S}^{\mathsf{c}}}^{\top} X_{t_i}, V_{\mathcal{S}_{t_i}^{\mathsf{prior}}}^{\top} X_{t_i}, V_{\mathcal{S}_{t_i}^{\mathsf{meas}}}^{\top} X_{t_i}}(V_{\mathcal{S}^{\mathsf{c}}}^{\top} x_{t_i}, V_{\mathcal{S}_{t_i}^{\mathsf{prior}}}^{\top} x_{t_i}, V_{\mathcal{S}_{t_i}^{\mathsf{meas}}}^{\top} x_{t_i}) = -\frac{1}{\sigma_{t_i}}V_{\mathcal{S}^{\mathsf{c}}}^{\top}\epsilon_{t_i}(x_{t_i}), \end{align}\] which is the same as previously used score function defined in 11 . the gradient with respect to \(V_{\mathcal{S}_{t_i}^{\mathsf{prior}}}^{\top} x_{t_i}\) is given by \[\begin{align} &\nabla_{V_{\mathcal{S}_{t_i}^{\mathsf{prior}}}^{\top} x_{t_i}}\log p_{V_{\mathcal{S}^{\mathsf{c}}}^{\top} X_{t_i}, V_{\mathcal{S}_{t_i}^{\mathsf{prior}}}^{\top} X_{t_i} \,|\,V_{\mathcal{S}_{t_i}^{\mathsf{meas}}}^{\top} X_{t_i}, V_{\mathcal{S}_{t_i}^{\mathsf{prior}}}^{\top} X_{\tau}}(V_{\mathcal{S}^{\mathsf{c}}}^{\top} x_{t_i}, V_{\mathcal{S}_{t_i}^{\mathsf{prior}}}^{\top} x_{t_i} \,|\,V_{\mathcal{S}_{t_i}^{\mathsf{meas}}}^{\top} x_{t_i}, V_{\mathcal{S}_{t_i}^{\mathsf{prior}}}^{\top} x_{\tau})\notag\\ &\quad =\nabla_{V_{\mathcal{S}_{t_i}^{\mathsf{prior}}}^{\top} x_{t_i}}\log p_{V_{\mathcal{S}^{\mathsf{c}}}^{\top} X_{t_i}, V_{\mathcal{S}_{t_i}^{\mathsf{prior}}}^{\top} X_{t_i}, V_{\mathcal{S}_{t_i}^{\mathsf{meas}}}^{\top} X_{t_i}}(V_{\mathcal{S}^{\mathsf{c}}}^{\top} x_{t_i}, V_{\mathcal{S}_{t_i}^{\mathsf{prior}}}^{\top} x_{t_i}, V_{\mathcal{S}_{t_i}^{\mathsf{meas}}}^{\top} x_{t_i}) \notag\\ &\qquad + \nabla_{V_{\mathcal{S}_{t_i}^{\mathsf{prior}}}^{\top} x_{t_{i}}} \log p_{V_{\mathcal{S}_{t_i}^{\mathsf{prior}}}^{\top} X_{\tau}\,|\,V_{\mathcal{S}_{t_i}^{\mathsf{prior}}}^{\top} X_{t_{i}}}(V_{\mathcal{S}_{t_i}^{\mathsf{meas}}}^{\top} x_{\tau},V_{\mathcal{S}_{t_i}^{\mathsf{meas}}}^{\top} x_{t_i})\notag\\ &\quad =-\frac{1}{\sigma_{t_i}}V_{\mathcal{S}_{t_i}^{\mathsf{prior}}}^{\top}\epsilon_{t_i}(x_{t_i}) +\frac{1}{\sigma_{t_i}^2({\rm e}^{2(\lambda_{t_i}-\lambda_{\tau})}-1)}\left(\frac{\alpha_{t_i}}{\alpha_{\tau}} V_{\mathcal{S}_{t_i}^{\mathsf{prior}}}^{\top} x_{\tau}- V_{\mathcal{S}_{t_i}^{\mathsf{prior}}}^{\top} x_{t_i}\right). \end{align}\] Compared to previously used score function, an additional term is introduced to capture the condition information between \(V_{\mathcal{S}_{t_i}^{\mathsf{prior}}}^{\top}\widehat{X}_{t_i}\) and \(V_{\mathcal{S}_{t_i}^{\mathsf{prior}}}^{\top}\widehat{X}_{\tau}\). Inserting this score function into the DDIM update rule yields the update formula in 20 .

8.1 Proof of Theorem 2↩︎

Akin to the proof of Theorem 1, we first construct the following auxiliary sequence: \[\tag{88} \begin{align} \overline{X}_{k+1}^{\mathsf{st}} &=\alpha_{t_{k+1}}\overline{Y}_{t_{k+1}} + \widehat{\sigma}_{t_{k+1}}\overline{Z}_{t_{k+1}},\quad \overline{X}_{k+1}^{\mathsf{sc}},\overline{X}_{k+1}^{\mathsf{c}} \sim p_{X_{k+1}^{\mathsf{sc}},X_{k+1}^{\mathsf{c}}\mid X_{k+1}^{\mathsf{st}},X_{\tau_s}^{\mathsf{sc},t_{k+1}}}(\cdot,\cdot\mid \overline{X}_{k+1}^{\mathsf{st}},\overline{X}_{k_{\tau_s}}^{\mathsf{sc},t_{k+1}}),\tag{89}\\ \widetilde{X}_{k+1}^{\mathsf{st}} &=\alpha_{t_{k+1}}\overline{Y}_{t_{k+1}} + \widehat{\sigma}_{t_{k+1}}\overline{Z}_{t_{k+1}},\\ \widetilde{X}_{k+1}^{\mathsf{sc}} &= \widetilde{X}_{k}^{\mathsf{sc}} + \gamma_k \nabla_{\widetilde{X}_k^{\mathsf{sc}}} \log q_{\lambda_{k+1}}(\widetilde{X}_{k}^{\mathsf{c}},\widetilde{X}_{k}^{\mathsf{sc}},\widetilde{X}_{k+1}^{\mathsf{st}}) + \sqrt{2\gamma_k} Z_k^{\mathsf{sc}},\tag{90}\\ \widetilde{X}_{k+1}^{\mathsf{c}} &= \widetilde{X}_{k}^{\mathsf{c}} + \gamma_k \nabla_{\widetilde{X}_k^{\mathsf{c}}} \log q_{\lambda_{k+1}}(\widetilde{X}_{k}^{\mathsf{c}},\widetilde{X}_{k}^{\mathsf{sc}},\widetilde{X}_{k+1}^{\mathsf{st}}) + \sqrt{2\gamma_k} Z_k^{\mathsf{c}},\tag{91} \end{align}\] where \(q_{\lambda_k}(x_{k}^{\mathsf{c}},x_{k}^{\mathsf{sc}},x_{k+1}^{\mathsf{st}})\) is defined as \[\begin{align} q_{\lambda_{k+1}}(x_{k}^{\mathsf{c}},x_{k}^{\mathsf{sc}},x_{k}^{\mathsf{st}})\mathrel{\vcenter{:}}= p_{X_{t_{k+1}}^{\mathsf{sc}},X_{t_{k+1}}^{\mathsf{c}}\,|\,X_{t_{k+1}}^{\mathsf{st}},X_{\tau_s}^{\mathsf{sc},t_{k+1}}}(x_{k}^{\mathsf{c}},x_{k}^{\mathsf{sc}}\,|\,x_{k+1}^{\mathsf{st}},x_{k_{\tau_s}}^{\mathsf{sc},t_{k+1}}), \end{align}\] and \(X_{\tau_s}^{\mathsf{sc},t_{k+1}} = \{v_s^{\top}X_{\tau_s}\}_{s\in\mathcal{S}_{t_{k+1}}^{\mathsf{c}}}\), \(\overline{X}_{k_{\tau_s}}^{\mathsf{sc},t_{k+1}} = \{v_s^{\top}\overline{X}_{k_{\tau_s}}\}_{s\in\mathcal{S}_{t_{k+1}}^{\mathsf{c}}}\) By a similar argument with Lemma 1, we have \[\begin{align} \mathsf{KL}(p_{\widetilde{X}_{0:M}\,|\,Y,Z}\Vert p_{\widehat{X}_{t_{0:M}}\,|\,Y,Z})\to 0,\qquad \mathrm{as}\quad \eta^3\delta^2\to 0, \quad \mathrm{and}\quad \eta\to\infty. \end{align}\] Moreover, the sequence defined in 24 satisfies \(p_{\overline{X}_k \,|\,V_{\mathcal{S}_{t_k}}^{\top}\overline{X}_{k}, v_{s}^{\top}\overline{X}_{k_{\tau_s}}} = p_{X_{t_k} \,|\,V_{\mathcal{S}_{t_k}}^{\top}X_{t_k}, v_{s}^{\top}X_{\tau_s}}\). By a similar argument as in 25 , it suffices to prove that for any \(y\), \(z\), \[\begin{align} \mathsf{TV}\big(p_{\widetilde{X}_k\,|\,Y,Z}(\cdot\,|\,y,z),p_{\overline{X}_{k}\,|\,Y,Z}(\cdot\,|\,y,z)\big)\to 0. \end{align}\] By decomposition, we have \[\begin{align} \mathsf{TV}\big(p_{\widetilde{X}_k\,|\,Y,Z}(\cdot\,|\,y,z),p_{\overline{X}_{k}\,|\,Y,Z}(\cdot\,|\,y,z)\big) &\le \mathsf{TV}\big(p_{\widetilde{X}_k^{\mathsf{st}},\widetilde{X}_{k_{\tau_s}}^{\mathsf{sc},t_{k}}\,|\,Y,Z}(\cdot\,|\,y,z),p_{\overline{X}_{k}^{\mathsf{st}},\overline{X}_{k_{\tau_s}}^{\mathsf{sc},t_{k}}\,|\,Y,Z}(\cdot\,|\,y,z)\big) \notag\\ &\qquad + \mathsf{TV}\big(p_{\widetilde{X}_k\,|\,\widetilde{X}_{k}^{\mathsf{st}},\widetilde{X}_{k_{\tau_s}}^{\mathsf{sc},t_{k}},Y,Z}(\cdot\,|\,x_k^{\mathsf{st}},x_{\tau},y,z),p_{\overline{X}_{k}\,|\,\overline{X}_{k}^{\mathsf{st}},\overline{X}_{k_{\tau_s}}^{\mathsf{sc},t_k},Y,Z}(\cdot\,|\,x_k^{\mathsf{st}},x_{\tau},y,z)\big)\notag\\ &=\mathsf{TV}\big(p_{\widetilde{X}_k\,|\,\widetilde{X}_{k}^{\mathsf{st}},\widetilde{X}_{k_{\tau_s}}^{\mathsf{sc},t_{k}},Y,Z}(\cdot\,|\,x_k^{\mathsf{st}},x_{\tau},y,z),p_{{X}_{t_k}\,|\,{X}_{t_k}^{\mathsf{st}},{X}_{\tau_s}^{\mathsf{sc},t_{k}}}(\cdot\,|\,x_k^{\mathsf{st}},x_{\tau})\big), \end{align}\] where \(x_k^\mathsf{st} = \alpha_{t_k}y + \widehat{\sigma}_{t_k}z\), and the last equation uses \(p_{\overline{X}_{k}\,|\,\overline{X}_{k}^{\mathsf{st}},\overline{X}_{k_{\tau_s}}^{\mathsf{sc},t_k},Y,Z}(\cdot\,|\,x_k^{\mathsf{st}},x_{\tau},y,z) = p_{{X}_{t_k}\,|\,{X}_{t_k}^{\mathsf{st}},{X}_{\tau_s}^{\mathsf{sc},t_{k}}}(\cdot\,|\,x_k^{\mathsf{st}},x_{\tau})\). The remaining proof is similar to the proof of Lemma 2. Specificially, we define a new random variable \(\widetilde{X}_k^{\mathsf{stc}} \mathrel{\vcenter{:}}= [\widetilde{X}_k^{\mathsf{sc}},\widetilde{X}_k^{\mathsf{c}}]\) and \({X}_{t_k}^{\mathsf{stc}} \mathrel{\vcenter{:}}= [{X}_{t_k}^{\mathsf{sc}},{X}_{t_k}^{\mathsf{c}}]\). Then the update rule in 90 - 91 can be integrated as \[\begin{align} \widetilde{X}_{k+1}^{\mathsf{stc}} &= \widetilde{X}_{k}^{\mathsf{stc}} + \gamma_k \nabla_{\widetilde{X}_k^{\mathsf{stc}}} \log q_{\lambda_{k+1}}(\widetilde{X}_{k}^{\mathsf{c}},\widetilde{X}_{k}^{\mathsf{sc}},\widetilde{X}_{k+1}^{\mathsf{st}}) + \sqrt{2\gamma_k} [Z_k^{\mathsf{sc}},Z_k^{\mathsf{c}}]. \end{align}\] For convenience, denote distributions \[p_k^{\mathsf{stc}}({x}_{t_k}^{\mathsf{stc}})\mathrel{\vcenter{:}}= p_{{X}_{t_k}^{\mathsf{stc}}\,|\,{X}_{t_k}^{\mathsf{st}}}({x}_{t_k}^{\mathsf{stc}}\,|\,{x}_{t_k}^{\mathsf{st}}),\qquad \psi_k({x}_{t_k}^{\mathsf{stc}})\mathrel{\vcenter{:}}= p_{\widetilde{X}_{k}^{\mathsf{stc}}\,|\,\widetilde{X}_{k}^{\mathsf{st}},\widetilde{X}_{k_{\tau_s}}^{\mathsf{sc},t_{k}},Y,Z}({x}_{t_k}^{\mathsf{stc}}\,|\,x_k^{\mathsf{st}},x_{\tau},y,z)\] and denote \(P_{\gamma_k}\) as the transition probability of the following SDE from \(t\) to \(t+\gamma_k\): \[\begin{align} \mathrm{d} X(t) = \nabla \log p_{k+1}^{\mathsf{stc}}(X(t)) \mathrm{d} t + \sqrt{2} \mathrm{d} W_t, \end{align}\] where \(W_t\) denotes the Brownian motion. According to the analysis of Langevin, we have \[\begin{align} \mathsf{KL}(\psi_{k+1}\Vert p_{k+1}^{\mathsf{stc}}) &\le \mathsf{KL}(P_{\gamma_k}\psi_{k}\Vert p_{k+1}^{\mathsf{stc}}) + \mathsf{KL}(\psi_{k+1}\Vert p_{k+1}^{\mathsf{stc}}) - \mathsf{KL}(P_{\gamma_k}\psi_{k}\Vert p_{k+1}^{\mathsf{stc}})\notag\\ &\le {\rm e}^{-2\kappa\gamma_k}\mathsf{KL}(\psi_{k}\Vert p_{k}^{\mathsf{stc}}) + {\rm e}^{-2\kappa\gamma_k}\left(\mathsf{KL}(\psi_{k}\Vert p_{k+1}^{\mathsf{stc}})-\mathsf{KL}(\psi_{k}\Vert p_{k}^{\mathsf{stc}}) \right)\notag\\ &\quad +\mathsf{KL}(\psi_{k+1}\Vert p_{k+1}^{\mathsf{stc}}) - \mathsf{KL}(P_{\gamma_k}\psi_{k}\Vert p_{k+1}^{\mathsf{stc}}) \end{align}\] where \(\kappa<\infty\) is a constant. We claim that \[\begin{align} \label{eq:proof-cor-main-1} \mathsf{KL}(\psi_{k}\Vert p_{k+1}^{\mathsf{stc}})-\mathsf{KL}(\psi_{k}\Vert p_{k}^{\mathsf{stc}}) = O(\delta_{k+1}). \end{align}\tag{92}\] By similar argument as in 58 - 61 , we have \[\begin{align} \mathsf{KL}(\psi_{k+1}\Vert p_{k+1}^{\mathsf{stc}}) - \mathsf{KL}(P_{\gamma_k}\psi_{k}\Vert p_{k+1}^{\mathsf{stc}}) = O(\gamma_k^2). \end{align}\] Therefore, we have \[\begin{align} \mathsf{KL}(\psi_{k+1}\Vert p_{k+1}^{\mathsf{stc}}) & \le {\rm e}^{-2\kappa\gamma_k}\mathsf{KL}(\psi_{k}\Vert p_{k}^{\mathsf{stc}}) + O(\delta_{k+1} + \gamma_k^2) &\lesssim \frac{1}{\eta} + \max_k \gamma_k \to 0,\qquad \mathrm{as}\quad \eta\to\infty, \delta\eta \to 0. \end{align}\] Finally applying Pinsker’s inequality, we complete the proof.

8.1.0.1 Proof of 92 .

According to the definition of KL divergence, we have \[\begin{align} \mathsf{KL}(\psi_k\Vert p_{k+1}^{\mathsf{stc}}) - \mathsf{KL}(\psi_k\Vert p_{k}^{\mathsf{stc}}) = \int \log \frac{p_{k}^{\mathsf{stc}}(x)}{p_{k+1}^{\mathsf{stc}}(x)}\psi_{k+1}(x)\mathrm{d} x. \end{align}\] It suffices to prove that \[\log p_{k}^{\mathsf{stc}}(x) - \log p_{k+1}^{\mathsf{stc}}(x) = O(\delta_{k+1}),\] which is implied by \[\begin{align} \left|\frac{\partial}{\partial\alpha_k}\log p_{k}^{\mathsf{stc}}(x)\right| &= O(\|x\|_2+1),\qquad \left|\frac{\partial}{\partial\sigma_k}\log p_{k}^{\mathsf{stc}}(x)\right| = O(\|x\|_2+1),\notag\\ \|\nabla_{{x}_{t_k}^{\mathsf{st}}}\log p_{{X}_{t_k}^{\mathsf{stc}}\,|\,{X}_{t_k}^{\mathsf{st}}}({x}_{t_k}^{\mathsf{stc}}\,|\,{x}_{t_k}^{\mathsf{st}})\|_2 &= O(\|{x}_{t_k}^{\mathsf{st}}\|_2+1). \end{align}\] To this end, by the definition of \(p_{k}^{\mathsf{stc}}(x)\), we have \[\begin{align} \left|\frac{\partial}{\partial\alpha_{t_k}}\log p_{k}^{\mathsf{stc}}(x)\right| &\le \left|\frac{\partial}{\partial\alpha_k}\log p_{{X}_{t_k}^{\mathsf{stc}}, {X}_{t_k}^{\mathsf{st}}}({x}^{\mathsf{stc}}, {x}^{\mathsf{st}})\right| + \left|\frac{\partial}{\partial\alpha_k}\log p_{{X}_{t_k}^{\mathsf{st}}}( {x}^{\mathsf{st}})\right| \notag\\ &= \frac{\big|\mathbb{E}[(x^{\mathsf{stc}}-\alpha_{t_k}X_0^{\mathsf{stc}})^{\top}X_0^{\mathsf{stc}}\,|\,X_{t_k}=x]\big|}{\sigma_{t_k}^2} + \frac{\big|\mathbb{E}[(x^{\mathsf{st}}-\alpha_{t_k}X_0^{\mathsf{st}})^{\top}X_0^{\mathsf{st}}\,|\,X_{t_k}=x]\big|}{\sigma_{t_k}^2}\notag\\ &\qquad + \frac{\big|\mathbb{E}[(x^{\mathsf{st}}-\alpha_{t_k}X_0^{\mathsf{st}})^{\top}X_0^{\mathsf{st}}\,|\,X_{t_k}^{\mathsf{st}}=x^{\mathsf{st}}]\big|}{\sigma_{t_k}^2}\notag\\ \left|\frac{\partial}{\partial\sigma_{t_k}}\log p_{k}^{\mathsf{stc}}(x)\right| &\le \frac{\mathbb{E}[\|x^{\mathsf{stc}}-\alpha_{t_k}X_0^{\mathsf{stc}}\|_2^2\,|\,X_{t_k}=x]}{\sigma_{t_k}^3} + \frac{\mathbb{E}[\|x^{\mathsf{st}}-\alpha_{t_k}X_0^{\mathsf{st}}\|_2^2\,|\,X_{t_k}=x]}{\sigma_{t_k}^3}\notag\\ &\qquad + \frac{\mathbb{E}[\|x^{\mathsf{st}}-\alpha_{t_k}X_0^{\mathsf{st}}\|_2^2\,|\,X_{t_k}^{\mathsf{st}}=x^{\mathsf{st}}]}{\sigma_{t_k}^3} - \frac{|\mathcal{S}_t^{\mathsf{c}}\cup \mathcal{S}^{\mathsf{c}}|}{\sigma_{t_k}},\notag\\ \|\nabla_{{x}_{t_k}^{\mathsf{st}}}\log p_{{X}_{t_k}^{\mathsf{stc}}\,|\,{X}_{t_k}^{\mathsf{st}}}({x}_{t_k}^{\mathsf{stc}}\,|\,{x}_{t_k}^{\mathsf{st}})\|_2& \le \|\nabla_{{x}_{t_k}^{\mathsf{st}}}\log p_{{X}_{t_k}^{\mathsf{stc}}, {X}_{t_k}^{\mathsf{st}}}({x}_{t_k}^{\mathsf{stc}},{x}_{t_k}^{\mathsf{st}})\|_2+ \|\nabla_{{x}_{t_k}^{\mathsf{st}}}\log p_{{X}_{t_k}^{\mathsf{st}}}( {x}_{t_k}^{\mathsf{st}})\|_2\notag\\ &\le \frac{\mathbb{E}[\|x^{\mathsf{st}}-\alpha_{t_k}X_0^{\mathsf{st}}\|_2\,|\,X_{t_k}=x]}{\sigma_{t_k}^2} + \frac{\mathbb{E}[\|x^{\mathsf{st}}-\alpha_{t_k}X_0^{\mathsf{st}}\|_2\,|\,X_{t_k}^{\mathsf{st}}=x^{\mathsf{st}}]}{\sigma_{t_k}^2}. \end{align}\] Therefore, we complete the proof.

References↩︎

---

1. The authors contributed equally. Corresponding author: Gen Li.↩︎

2. Department of Statistics and Data Science, Chinese University of Hong Kong, Hong Kong↩︎

3. Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, USA↩︎

4. Department of Statistics and Data Science, the Wharton School, University of Pennsylvania, PA, USA↩︎

5. In addition to our algorithm, we also implement ProjDiff and DDNM+. The remaining results reported in this section are taken from [57].↩︎