Complexity Analysis of Normalizing Constant Estimation: from Jarzynski Equality to Annealed Importance Sampling and beyond
Authors: Wei Guo
Molei Tao
Yongxin Chen
Venue: ICLR 2026 Poster (2026)
Keywords: normalizing constant
free energy
Jarzynski equality
annealed importance sampling
reverse diffusion samplers
Primary area: probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
TL;DR: We established a framework for analyzing the complexity of normalizing constant (free energy) estimation through Jarzynski equality and annealed importance sampling.

Abstract: Given an unnormalized probability density $\pi\propto\mathrm{e}^{-V}$, estimating its normalizing constant $Z=\int_{\mathbb{R}^d}\mathrm{e}^{-V(x)}\mathrm{d}x$ or free energy $F=-\log Z$ is a crucial problem in Bayesian statistics, statistical mechanics, and machine learning. It is challenging especially in high dimensions or when $\pi$ is multimodal. To mitigate the high variance of conventional importance sampling estimators, annealing-based methods such as Jarzynski equality and annealed importance sampling are commonly adopted, yet their quantitative complexity guarantees remain largely unexplored. We take a first step toward a non-asymptotic analysis of annealed importance sampling. In particular, we derive an oracle complexity of $\widetilde{O}\left(\frac{d\beta^2{\mathcal{A}}^2}{\varepsilon^4}\right)$ for estimating $Z$ within $\varepsilon$ relative error with high probability, where $\beta$ is the smoothness of $V$ and $\mathcal{A}$ denotes the action of a curve of probability measures interpolating $\pi$ and a tractable reference distribution. Our analysis, leveraging Girsanov's theorem and optimal transport, does not explicitly require isoperimetric assumptions on the target distribution. Finally, to tackle the large action of the widely used geometric interpolation, we propose a new algorithm based on reverse diffusion samplers, establish a framework for analyzing its complexity, and empirically demonstrate its efficiency in tackling multimodality.

Published as a conference paper at ICLR 2026
COMPLEXITY ANALYSIS OF NORMALIZING CONSTANT ESTIMATION: FROM JARZYNSKI EQUALITY TO AN- NEALED IMPORTANCE SAMPLING AND BEYOND
Wei Guo, Molei Tao, Yongxin Chen Georgia Institute of Technology {wei. gue, mtao, yongchen| @egatech. edu
ABSTRACT
Given an unnormalized probability density æ x c estimating its normalizing constant Z = SR. e - or free energy F = - -oog Z is a crucial problem in Bayesian statistics, statistical mechanics, and machine learning. It is challenging especially high dimensions or when π is multimodal. To mitigate the high variance of conventional importance sampling estimators, annealing- based meth- ods such as Jarzynski equality and annealed importance sampling are commonly adopted, yet their quantitative complexity guarantees remain largely unexplored. We take a first step toward a non-asymptotic analysis of annealed importance sam- pling. In particular, we derive an oracle complexity of Ō dg 222
for estimating Z within relative error with high probability, where is the smoothness of V and A denotes the action of a curve of probability measures interpolating æ and tractable reference distribution. Our analysis, leveraging Girsanov's 's theorem and optimal transport, does not explicitly require isoperimetric assumptions on the target distribution. Finally, tackle the large action of the widely used geometric interpolation, we propose new algorithm based on reverse diffusion samplers, establish a framework for analyzing its complexity, and empirically demonstrate its efficiency in tackling multimodality.
INTRODUCTION
We study the problem of estimating the normalizing constant Z Z= Jqu ( (z))d of an unnormalized probability density function (p.d.f.) π म e Rd, that (<x) R(x) The normalizing constant appears in various fields: in Bayesian statistics, when 7 is the product of likelihood and prior, Z is also referred as the marginal likelihood or evidence (Gelman et al.) 2013); in statistical mechanics, when V is the Hamiltonian| Z is known as the partition function, and F := log Z is called the free energy (Chipot Pohorille 2007 2007 Lelièvre et al.) 2010 Pohorille al. 2010). The task of normalizing constant estimation has numerous applications, including computing log- logelioelssoods in probabilistic models (Sohl-Dickstein & Culpepper] 2012). estimating free energy differences (Lelièvre et al. 2010), and training energy-based models in generative modeling (Song & Kingma
2021 Carbone et al. 2023 Sander et al. 2025).
Estimating normalizing constants is challenging in high dimensions when π is multimodal (i.c.. V has a complex landscape). Conventional approaches based on importance sampling (Meng & Wong 1996) are widely adopted tackle this problem, but they suffer from high variance due to the mismatch between the proposal and the target when π is complicated (Chatterjee & Diaconis 2018). To alleviate this issue, the technique of annealing tries constructing sequence of intermediate distributions that bridge these two distributions, which motivates several popular methods including path sampling (Chen & Shao 1997; Gelman & Meng 1998), annealed importance sampling (AIS, Neal 2).1)). and sequential Monte Carlo (SMC, Doucet et al. (2000); Del Moral et al. (2006); Syed al. 2024g) in statistics literature, as well as thermodynamic integration (TI. Kirkwood (1935) and
'Up to a multiplicative constant 7 known as the thermodynamic beta, where kp is the Boltzmann constant and T is the temperature. When borrowing physical terminologies, we ignore this for simplicity.

---

Published as a conference paper at ICLR 2026
Jarzynski equality (JE, Jarzynski [1997); Ge & Jiang 2008 Hartmann et al. (019 in statistical
mechanics literature. In particular, JE points out the connection between the free energy difference between two states and the work done over series of trajectories linking these two states, while AIS constructs a sequence of intermediate distributions and estimates the normalizing constant by importance sampling over these distributions. These two methods our primary focus in this paper.
Despite the empirical success of annealing based methods (Ma et al. 2013 Krause et al. 2020
Mazzanti & Romero 2020] Yasuda & Takahashi 2022; Chen & Ying 2024 Schönle al. 2025).
the theoretical understanding of their performance is still limited. Existing works for importance
sampling mainly focus on the asymptotic bias and variance of the estimator (Meng & Wong 1996]
Gelman & Meng [998). while works on JE usually simplify the problem by assuming the work follows simple distributions (e.g., Gaussian or gamma) (Echeverria & Amzel 2012 Arrar al. 2019).
Moreover, only analyses asymptotic in the number of particles derived from central limit theorem exist (Lelièvre al., 2010 Sec. 4.1). This paper aims to establish a rigorous non-asymptotic analysis of estimators based on JE and AIS, while introducing minimal assumptions the target distribution. We also propose a new algorithm based on reverse diffusion samplers to tackle a shortcoming of AIS.
Contributions. Our key technical contributions are summarized as follows.
We discover a novel strategy for analyzing the complexity of normalizing constant estimation, applicable to a wide range of target distributions (Assumps. and 2 that may not satisfy isoperimetric conditions such as log-concavity.
2. In Sec. 3 we study JE and prove an upper bound on the time required for running the annealed Langevin dynamics to estimate the normalizing constant within e relative error with high probability, The final bound depends on the action (the integral of the squared metric derivative in Wasserstein-2 distance) of the curve.
3. Building the insights from this analysis of the continuous dynamics, in Sec. 4
we establish the first non-asymptotic oracle complexity bound for AIS, representing the first analysis of normalizing constant estimation algorithms without assuming a log-concave target distribution.
4. Finally, in Sec. 5]
we first point out a potential limitation of the commonly used geometric interpolation, which provides quantitative explanation of the mass teleportation phenomenon. We then propose a series of new algorithms based on reverse diffusion samplers and formalize a framework for analyzing its oracle complexity. Our experimental results demonstrate the superiority of the proposed algorithm over AIS in overcoming multimodality.
Related Works. Below, we summarize the related works in four aspects.
I. Methods for normalizing constant estimation. We mainly discuss two classes of methods here. First, the equilibrium methods, such as TI (Kirkwood 1935) and its variants (Brosse et al., [2018] Ge et al. 2020) Chehab et al., 22033 Kook & Vempala 2025), which involve sampling sequentially from a series of equilibrium Markov transition kernels. Second, the non-equilibrium methods, such as AIS [Nal 2001), which samples from non-equilibrimm stochastic process that gradually evolves from a prior distribution to the target distributions. In App. H.I we show that TI is a special case of AIS using the "perfect" transition kernels. Recent years have also witnessed the emergence of learning-based non-equilibrium methods, which are typically byproducts of neural samplers (Nüsken & Richter |021 [hang & Chen 2022; Máté & Fleuret (2023) Richter & Berner 2024| Sun et al. 2024] Vargas et al. 2024; Máté et al. 2024] Albergo & Vanden-Eijnden, 2025 2025 Blessing et al. 2025 Chen al. 2025 Havens et al. 2025 Du al.] 2025). Finally, there also methods based on
particle filtering (Kostov& & Whiteley 2017: et al. 2018 Ruzayqat et al. 2022).
II. Variance reduction in JE and AIS. Our proof methodology focuses on the discrepancy between the sampling path measure and the reference path measure, which is related to the variance reduction technique in applying JE and AIS. For example, Vaikuntanathan & Jarzynski (2008) introduced the idea of escorted simulation, Hartmann Hartmmnnn et al. (2017) proposed method for learning the optimal control protocol in JE through the variational characterization of free energy, and Doucet al. (2022) leveraged score-based generative model to learn the optimal backward kernel. Quantifying the discrepancy between path measures is the core of our analysis.
III. Complexity analysis for normalizing constant estimation. Chehab et al. (0233 studied the asymptotic statistical efficiency of the curve for TI measured by the asymptotic mean-squared error,
2

---

Published as a conference paper at ICLR 2026
and highlighted the advantage of the geometric interpolation. In terms of non non-asymptotic analysis. existing works mainly rely on the isoperimetry of the target distribution. For instance, Andrieu et al.) (2016) derived bounds of bias and variance for TI under Poincaré inequality (PI), Brosse et al. (2018) provided complexity guarantees for Tl under both strong and weak log-concavity conditions, while Ge et al. (2020) improved the complexity under strong log-concavity using multilevel Monte Carlo.
IV. Complexity analysis of sampling beyond isoperimetry. Our analysis of estimating normalizing constants of non-log-coneave distributions is also closely related the study of sampling beyond log-concavity, In general, such problems are NP hard (Ge et al. 2018 He & Zhang 2025). Existing works providing convergence guarantees have leveraged more general isoperimetric inequalities such as weak PI (Mousavi-Hossee (Balasubramanian et al.] [ et al. 2023). ) or utilized denoising diffusion models (Huang et 20224 [e et al., (024). We highlight Guo et al. (2025) that this paper mainly draws inspiration from, which introduced the action of a curve quantifying the convergence of annealed sampling. While they focused sampling and presented cases where annealing works, extend the analysis to a conceptually different task, and further establish lower bounds on the action the commonly used geometric interpolation, motivating new algorithm based on reverse diffusion samplers.
et al., 22023), tried to establish convergence in weaker notions
Notations and Definitions. For a, b E R. let [a, b] := |a, b) Zz a b == min b), and a V b == max(a, b). For a, b 0, the notations S 6, b 2 a, a O(6). 6 = Ma)) indicate that I Cb for some universal absolute constant C > 0, and the notations a = b, a = (b)) stand for a S b S a. (-)) ē hide logarithmic dependence in O(.), 0()) A function U E (RR) is a(> -t-strongly- convex if V = al, and 3(> 0)-smooth if -11 3 2 3 3I. We do not distinguish probability measures on I from their Lebesgue densities. For two probability measures μe, v, the total-variation (TV) distance is TV //) = suP A Im(A) v(4)]. and the Kullback-eein (KL) divergence is (L(pIIp) (p|[p) = f log du duu. Finally, a function IRd x Rd + [0, +oo) is a transition kernel if for any x. T(x, .) p.d.f. Throughout this paper, (B.) and (W,) represent
du
standard Brownian motions (BM) on IRd.
Preliminaries. For brevity, integrate the required background information into the main text, with a detailed exposition available in App. A
PRELIMINARIES AND PROBLEM SETTING
To motivate the study of normalizing constant estimation, we first present several examples.
Example 1. [Free energy difference.] In many statistical physics problems (Lelièvre al., 2010). given two energy functions Uo. U1 (possibly linked through some thermodynamic process), one is often interested in estimating the free energy difference AF == - log( e
BU' dx/ - el),) which is related with the normalizing constant of the distributions ग, -BU.
Example 2. [Likelihood in latent variable models.] latent variable models such as variational autoencoders (Kingma& & Welling 2013). common evaluation metric is the marginal likelihood of data point x, (z) = Po 2 (p(2)dz) This is nothing but the normalizing constant of the posterior distribution of the latent variable given data x. (2(1)) X= =))))))((>)
Example 3. [Volume of convex bodies.) In theoretical computer science, a classical problem is to estimate the volume of convex body K. (Dyer et al. 1991 Cousins & Vempala 2018. Kook et al. 2024). which is equivalent to the normalizing constant of the uniform distribution on X., π x Ix.
Building on prior theoretical results (Brosse al.
2018 Ge et al. 2020), we study the oracle
complexity of estimating the normalizing constant of a density under the following criterion:
Aim: Given a density и x := e on Rd, bound the complexity of obtaining an estimator 2 of Z Sga (())dr such that with constant probability, the relative error is within e(< 1):
7 Z
3
Pr
4
Remark 1.
We make two remarks regarding
(1)
First, similar to how taking the mean of i.i.d.
estimates reduces variance, we show in Lem. 10 that the probability above can be boosted to 1 Ç.
3

---

Published as a conference paper at ICLR 2026
VÇ E (0. using the median trick: obtaining O (log à) i..d. estimates satisfying and taking their median. Therefore, focus the task of obtaining single estimate satisfying hereafter. Second, (1) also allows us to quantify the complexity of estimating the free energy
log Z, which is often of greater interest stafistical mechanics than the partition function Z. We show in
App. G that estimating Z with O(=) relative error and estimating F with (E)) absolute error share the same complexity up constants. Further discussion of this guarantee, including literature review and the comparison with bias and variance, is deferred to App. G
straightforward method for estimating Z is through importance sampling, i.e., Z = for some tractable proposal distribution To. yet its variance can be large due to the mismatch between To and æ. The rationale behind annealing involves a gradual transition from To to х. Throughout this paper, we consider curve of probability measures denoted as
mn
1
ee V/
T
Ze
0E|0,1]
where V1 V is the potential of π, and Z1 = what we need to estimate. We do not specify the exact form of this curve now, but only introduce the following mild regularity assumption on the curve, as assumed classical textbooks such as (Ambrosio et al. (2008) 202I); [Santambrogio (2015): Assumption 1. The potential [0, 1] x Rd 3 (0,x) + Vo(x) E R is jointly C², and the curve (Ta)eE is absolute continuous with finite action A = fo | do.
Here, | == lims-50 Wa(3o=sa31)) is the Wasserstein-2 (W2) metric derivative of the curve - [8]
(0 at 0, which measures the "speed" of the curve in the space of probability distributions, and absolute continuity means the above limit exists and is finite for all 0 E j0, 1]. A curve having finite action is weaker condition than requiring each Te to satisfy isoperimetric inequalities (e.g., Poincaré or log-Sobolev). We refer readers to App. A.2 for details of optimal transport (OT), and in particular, we highlight the connection between the metric derivative and the continuity equation (Lem. 4), which will serve key tool in analysis.
For the purpose of non- -sympttpptoicc analysis, we further introduce the following mild assumption: Assumption 2. V is smooth,h (V) and m := /E,, || +-0..
Remark One can always find stationary point x, of (possibly non-convex) V using optimization methods within negligible cost compared with the complexity for estimating Z. By considering the translated distribution 7.- - I.), we assume 0 is a stationary point without loss of generality.
Equipped with this fundamental setup, we now proceed to introduce the JE and AIS, and establish an analysis for their complexity.
ANALYSIS OF THE JARZYNSKI EQUALITY
To elucidate how annealing works in the task of normalizing constant estimation, first consider annealed Langevin diffusion (ALD), which runs Langevin diffusion (LD) with a dynamically changing target distribution. Recall that the LD with target distribution is the stochastic differential equation (SDE) d.X, V log (X,) dt + V2dB,, which converges to as t oc. To define ALD, we introduce a reparameterized curve (+, = <1/T)<E for some large time duration 7 to be determined later, and consider the following SDE:
dX,- V log 7H dXt + V2dB, t [0,T]; Xo No.
The following Jarzynski equality provides connection between the work functional and the free energy difference, which naturally yields an estimator of normalizing constant.
Theorem (Jarzynski equality (Jarzynski 1997)). ). Let Tp be the path measure of work functional W and the free energy difference AF have the following relation:
(2) Then the
1 l'' Os Volo== (Xi)dt and AF == log
Zn
Ep- -A AF
where W(X) =
Zo
4

---

Published as a conference paper at ICLR 2026
Below, we sketch the proof from Vargas et al. 22024 Prop. 3.3), which offers a crucial aspect for our analysis: the forward and backward SDEs. See App. A. for a detailed introduction.
Sketch of Proof Let P be the path measure of the following backward SDE with time-reversed
Brownian motion (BM) )ET0,11 (i.e., (t + ( is a standard BM, see Def. 1b:
dx,- = - Vog Ry (X;)dt + v2dBF. & [0, 2]; XT mT.
(3)
Intuitively, this is running the ALD backward in time from T to 0, targeting distribution ग. at time Leveraging the Girsanov's theorem (Lem. I) and Itô's formula, one can establish the following identity of the Radon-Nikodye (RN) derivative between the forward and backward path measures, known as the Crooks fluctuation theorem (Crooks 1998: 1999
dF dF (X) - (x)=-S( (0, log (X,) W(X) - AF, a.s. X
log
(4)
which implies JE by the identity Ep-
dP ar- = 1. Complete proof can be found in App. C.I
Under the ideal setting where (i) Zo is known, (ii) the ALD in (2) can be simulated exactly, and (iii) the work functional W (XX) can be computed precisely. Thm. provides an unbiased estimator
2 = Zoe-Wo -X() for Z = Zoe AF Despite its dominant use (Chipot & Pohorille, 2007 Lelièvre jet al. 2010), the statistical efficiency of this estimator is not well understood. While is known that the variance of Z can be large, non-asymptotic analyses quantifying its efficiency is lacking. We address this gap by establishing an upper bound on the time T required for the ALD to satisfy the accuracy criterion ( in the following theorem, whose proof is detailed in App. C.2
Theorem 2. Under Assump. suffices to choose 32,A g²
obtain Pr 2 - SE)
2
3 4
We first observe that our bound aligns with the decay rate of the variance of the work in Mazonka & Jarzynski] (1999) (see also Lelievre et al.) (2010) Chap. 4.1.4)), which considered a special case
To -N (OL, k.). They showed that W N (Br, 2Br) with By- 4- (1 (1- (1-e KT)
and
2 Br is asymptotically 0 ( as T - co. Our
hence the normalized variance Varp-+
2
bound, under a different criterion (1) O (+) for all T > 0.
To illustrate the proof idea of Thm. 2 note that while the ALD (2) targets the distribution म. at time
there is always lag between ne and the actual law of X, Similarly, the same lag exists in the backward ALD (3) This lag turns out be the source of the error in the estimator Z.
In practice, to alleviate the issue of high variance in estimating free energy differences, Vaikuntanathan & Jarzynski (2008) proposed adding a compensatory drift term un (X,) to the ALD (2) Ideally, the optimal choice would eliminate the lag entirely, ensuring X, ~ T. for all t E [o, TJ. Inspired by this, we compare the path measure of ALDD IP+ to the SDE having the perfect compensatory drift term, whose path measure IP has marginal distribution T. at time t. To make possible the perfect match, it turns out that 2e must satisfy the Bokker-Plancke equation with 7.. The Girsanov's theorem (Lem. 1 enables the computation of (LPPIIIPP)) and KL(P)IP*). ), which are related to ||u: 1 Finally, among all admissible drift terms Ut: Lem. 4 suggests an optimal choice of of to minimize this norm, thereby leading to the metric derivative [i]e and the action A. This way avoids the explicit dependence of isoperimetric assumptions in our bound.
similar connection between free energy and action integral was discovered in stochastic thermody- namies (Sekimoto) 2010) Seifert 2012). one paradigm for non-equilibrium thermodynamics. By the second law of thermodynamies, the averaged dissipated work, defined as the averaged work minus the free energy difference, i.c., Waiss := W - AF := Ep- W AF, is non-negative. When the underlying process is modeled by an overdamped LD. Waiss can be quantified by an action integral divided by the time duration (Aurell al. 2011 Chen al. 2020). This follows from the observation that Waiss = (IP [P=) and then a similar argument to that above. This connection provides a finer description of the second law of thermodynamies (Aurell et al. 2012) over finite time horizon.
Finally, we place Thm. 2 within the broader theme of sampling v.s. normalizing constant estimation by comparing Thm. 2 with the complexity of non-log-concave sampling. Guo et al. (2025) proved
5

---

Published as a conference paper at ICLR 2026
that under the same assumptions, the ALD (2) draw a sample within e--error in (L( with the same order of time T x 1.2 While the classical work Jerrum et al. 1986) proved the existence of polynomial-tie algorithm for sampling and a polynomal- algorithm for estimating normalizing constant imply each other in the discrete settings, establish similar quantitative connection between the complexities these two tasks the continuous settings without log- eegeoccavity, opening avenue of research understanding their relationship. Though reaching similar results, the proof strategies are different: (uo et al. (2025) is a direct application of Girsanov's 's theorem between p= and P. while Thm. involves more complicated backward SDE arguments.
4 ANALYSIS OF THE ANNEALED IMPORTANCE SAMPLING
In practice, it is not feasible to simulate the ALD precisely, nor is it possible to evaluate the exact value the work ( Therefore, discretization and approximation are required. To address this, we first outline the following annealed importance sampling (AIS) equality akin to JE.
Theorem (Annealed importance sampling equality (Neal 2001)). Suppose have probability distributions 4. E M] and transition kernels Fe(z,-), & E [1, MM. and assume that each We an invariant distribution of Fe, E [I, Define the path measure
M
( =To(zo) II Fe(
(5)
Then the same relation between the work corkfunction W and free energy difference AF holds:
M-1
Se(we) fe41(1))
and AF == - loo ZM
Ep- e -- =e where W (ZO:M) == log
II 6=
Zo
Proof. Since ny is invariant for Fr, the following backward transition kernels are well-defined:
Be(s, x/) Te(2')
Fo x)), E [].
xx(x)
By applying these backward transition kernels sequentially, we define the backward path measure
p (No.M) = (M((M) II Be(xe, #1-1)-
It can be easily demonstrated, as in (4) that log dF (Fo:M) W (woo:)) - AF, Consequently, the
identity Ex d=" f implies the desired equality.
While the frameworks of JE and AIS hold for general curves of interpolation, for the study of non-asymptotic complexity guarantees, we focus a widely used curve in theoretical analysis
(Brosse et al. 2018 Ge et al. 2020), which we refer to as the geometric interpolation
T
Zo fo
Zo
exp (-v
A(0)
IP)
0 [0,
(7)
where X(-) is decreasing function with x(O) = 233 and X(1) O, referred to as the annealing schedule. With this choice of X(0), by Assump. 2, the potential mo is B-strongly-convex, and 33-smooth, making sampling and normalizing constant estimation relatively easy. To estimate Zo. we use the thermodynamic integration (TT) algorithm from Ge et al. (2020), which requires N/B
gradient oracle calls. In a nutshell, TI an equilibrium method that constructs series
of intermediate distributions and estimates adjacent normalizing constant ratios via expectation under these intermediate distributions, realized through MCMC sampling from each intermediate distribution. As TI is peripheral to primary focus, defer its full description, including the choice of hyperparameters and complexity bound, to App. H.l
(7) differs slightly from a widely used curve in applications (Gelman & Meng 1998 Neal 2001 : Te xc
(9) where is prior distribution (typically Gaussian). We refer both geometric interpolation.

---

Published as a conference paper at ICLR 2026
Given we introduce time points 0 80 81 ... 80 11 to be specified later, and adopt the
fe to correspond to ne, = Je. albeit with slight framework outlined in Thm. by setting γy = Zt
abuse of notation. To estimate the normalizing constant, need sample from the forward path measure IP- and compute the work function along the trajectory. Since To, must be an invariant distribution of the transition kernel Fe in PP', define F/ via running LD targeting no, for short time T2, i.e., Fz(x,) :) is given by the law of X1, in the following SDE initialized at Xy = x
dx,- V log mo, (Xt)dt + Vdd., I [0, Tcl.
(8)
In this setting, AIS can be interpreted as a discretization of JE (elièvre et al. 2010, Rmk. 4.5). However, in practice, exact samples from mn often unavailable, and the simulation of LDD cannot be performed perfectly To capture these considerations, we define the following path measure:
P (To.M) #o(o)) II ((E
where Ro is the law of an approximate sample from To. and the transition kernel F3 a discretization of the I.D in Fe, defined as running one step of annealed Langevin Monte Carlo (ALMC) using the
exponential integrator discretization scheme (Zhang & Chen [023 Zhang et al. 2023b a) with step
size Tg. Formally, Fx .) is the law of Xx, in the following SDE initialized at X, = x:
dX, = -------EE (V()) + (0L- (c-1 _ 01-1) Xe dt v2dB, t [0, (10)
Here, instead of simply setting Fe as step of LMC targeting Te,, the dynamically changing X(-) helps reduce the discretization error, as will be shown in our proof. Furthermore, with sufficiently small step size, the overall discretization update step in each transition kernel.
also be minimized, motivating apply just one
We refer readers Alg. in App. B for summary of the detailed implementation of our proposed AIS algorithm, including the TI procedure and the update rules in (10) The following theorem
delineates the oracle complexity of the algorithm required to obtain an estimate meeting the desired accuracy criterion [I]] whose detailed proof can be located in App. D The required values of hyperparameters M, and T3 can be found at the end of the proof.
i.e., Ž = Zne - ((zo.)) where Zo is estimated by Tl and Jo.M P Under Assumps. and 2 consider the annealing schedule x(0) = 23(1 0)" for some 1 S. S 1. Use A, to denote the action of (Te (T9))c((o11) to emphasize the dependence on r. Then, the oracle complexity for obtaining an estimate Ž that satisfies
Theorem 4. Let Z be the AIS estimator described in Alg.
is
d 2
mBA7
A3
(11)
22
We present high-level proof sketch using Fig. The continuous dynamics, comprising the for- ward path P the backward path IP=, and the reference path I. are depicted as three black curves. To address discretization error, the ć-th red (purple) arrow proceeding from left to right represents the transition kernel Fe (Bt), whose composition forms p (I=)).
(I) Analogously to the analysis of JE Thm. 2 define the reference path measure IP with transi- tion kernels F such that øy Te.- Given the sampling path measure بー, define P the Figure I: Ilustratiion of the proof idea for Thm. version of - without the initialization error, i.e., by replacing To with To in (9)
Recall that need Fe to have invariant distribution me Thm.

---

Published as a conference paper at ICLR 2026
(II) Show that it suffices obtain an accurate estimate Zo and initialization distribution No. together with sufficiently small KL divergences (L(PIIPT) and (L[P ) which quantify the closeness between the continuous dynamics and the discretization error in implementation, respectively.
(III) Using the chain rule, decompose (L(PI|PF)) into the sum of KL divergences between each pair of transition kernels F& and F (i.e., green "distances"). As in TTmm 2 1 a transition kernel from _ to , is realized by ALD with compensatory vector field, ensuring the SDE exactly follows the trajectory (Te)) 0.] Similarly, by applying the chain rule and Girsanov's 's theorem, we can
express [L[P))P
the sum of the blue "distances", allowing for similar analysis.
(IV) Finally, derive three necessary conditions on the time steps 0g to control both (L(P) and (L|PIP ) Choosing a proper schedule yields the desired complexity bound.
Our proposed algorithm consists of two phases: first, estimating Zo by TI, which is provably efficient for well-conditioned distributions, and second, estimating Z by AIS, which is better suited for handling non-log -onccceevve distributions. The three terms in (11) arise from (i) ensuring the accuracy of Zo. (ii) controlling (L(PIIIP) and (iii) controlling (LPIPP ), respectively, as discussed in (II) above. Due to the con-log-concavity of т, the action A is typically large, making (iii), the cost for controlling the discretization error, the dominant complexity. The e-dependence can be interpreted as the total duration T = O ( ( required for the continuous dynamics to converge (as in Thm. 2
divided by the step size 6(=²) to control the discretization error. Finally, we remark that although Thm. 4 is only proved for geometric interpolation, the proof strategy can be generalized to any curve of distributions [T))) satisfying weak regularity conditions, and possibly with an additional compensatory drift term, as long we know the expression of the score V log To, and also the Lipschitz constants of the score and the drift term for controlling the discretization error.
5 NORMALIZING CONSTANT ESTIMATION VIA DENOISING DIFFUSION
Disadvantage of Geometrie Interpolation. From the analysis of JE and AIS TTmss. 2 and 4. the choice of the interpolation curve (TT0) is crucial for the complexity. The geometric interpolation (7) is widely adopted due to the availability of closed-form scores of the intermediate distributions me, and for certain structured non-log-concave distributions, the associated action is polynomially large, enabling efficient AIS. For instance, Guo et al. 2025) Ex 2) analyzed a Gaussian mixture target distribution with identical covariance, means having the same norm, and arbitrary weights. However, for general target distributions, the action of the related curve can grow prohibitively large. We now establish exponential lower bound on the action of a curve starting from a Gaussian mixture, highlighting the potential inefficiency of AIS under geometric interpolation.
Proposition 1. Consider the Gaussian mixture target distribution = = (0,1)) 1NN (m, 1) on R for some sufficiently large m Z 1, whose potential is m² 2 -smooth. Under the setting in AIS (Thm. 4).
define (o(r)) (x)) x 0 E [0, 1), where X(0) m²² 0l" for some 1. Then, the action of the curve (TT))e Ar, is lower bounded by A, Z m प0.
The full proof is App. E.I The key technical tool is a closed-form expression of the W₂ distance in IR expressed by the inverse cumulative distribution functions (c.d.f.s) of the involved distributions, and we lower bound the metric derivative near the target distribution, where the curve changes the most drastically. This observation provides a novel perspective on the quantitative description of the mass teleportation or mode switching phenomenon (Woodard et al. 2009 Tawn al.. 2020) Syed et al.] 2021 Chemseddine et al. 2025), motivating to explore alternative curves that can potentially yield smaller action, thereby enhancing the efficiency of normalizing constant estimation. Intuitively, during the annealing process, the probability mass needs to be transported from mode of the distribution to another well-separated mode in a short period of time (c.g., through the change of weights in both modes), which leads to torpid mixing for many samplers.
Reverse Diffusion Samplers. Inspired by score- based generative models (Song et al. 2021 ), recent advancements have led to the development of multimodal samplers based on reversing the Omsttenn Uhlenbeck (OU) process, such as reverse diffusion Monte Carlo (RDMC, Huang et al. (2024a)) recursive score diffusion-based Monte Carlo (RSDMC, Huang et al. (2024b)), zeroth-order diffusion
8

---

Published as a conference paper at ICLR 2026
Monte Carlo (ZODMC, He et al. (2024)), and self-normalize diffusion Monte Carle (SNDMC. Vacher et al. (2025) ) We collectively refer to these methods as the reverse diffusion samplers (RDS). The key idea is to simulate the time reversal of the following OU process, which transforms
any target distribution ग into Φ = N (0. 1) as T + co:
dy; = dtt + v2dB, t E [0, Yo n.
(12)
Let Y, ~ nT. The time-reversal (Y," := Yr ग (0.TT satisfies the SDE
dY; = (Y 2V -Y, ) v2dW,, t E [0; Y (T( Φ).
(13)
Hence, to draw samples Y n, it suffices to approximate the scores log I., and discretize (13)
which can be implemented in various learning-free (non-parametric) ways in the literature of RDS mentioned above. App. E.5 a detailed review.
RDS-based Normalizing Constant Estimation. We now propose to leverage (TT- in AIS. To support this idea, we first present the following proposition. We remark that the result can be generalized to bound on the Wasserstein gradient flow for the KL divergence to any target distribution with weak regularity condition, not necessary the standard normal distribution. See the proof in App. E.2 for details.
Proposition 2. Define Fe as the law of Y, in the OU process (12) initialized from Yo ~ x x where V 3-smooth. Let m² == Ex
cc. Then, Jo
क | S d3 + m
Prop. 2 shows that under fairly weak conditions on the target distribution, the action of the curve along the OU process, (00.7)) behaves much better than (7) Hence, our analysis JE (Thm. 2 suggests that this curve is likely to yield more efficient normalizing constant estimation. Furthermore, recall that in our earlier proof, we introduced a compensatory drift term Vy to eliminate the lag in JE. The same principle applies here: ensuring X₁ precisely following the reference trajectory is advantageous, which results in the time-reversal of OU process (13) Building on this insight, we propose RDS-based algorithm for normalizing constant estimation, and establish framework for analyzing its oracle complexity. See[App E.3 for the proof.
Theorem 5. Assume a total time duration T, an early stopping time ò 2 and discrete time points T - 5 < T. For t. E T 5), ler t. denote ta if f E [FA, fx+1). Let = V log म. be a score estimator, and Φ = N (0, I). Consider the following two SDES on [0, T representing the sampling trajectory and the time-reversed OU process, respectively:
0 lo < t <... < ix = T
Q dx,- = (X, + 2sT (X, ))dl + 2dB.,
Xo ~ 05
(14)
Q dx,- (X+ 2V log nT - (x,))) V2dB
Xo TT-
Let e WXX), X ~ Qi be the estimator of Z, where the functional + (X) is defined as
T- (IST (X. )I (2 (Xe ).dB:))
log ((X)) + 88) (T - 5)d
Then, to ensure Ž satisfies suffices that (L(QI) S e² and TV( To) S.c.
For detailed implementation of the update rule in (14) and the computation of W W(X), see Alg. 2 To determine the overall complexity, we can leverage existing results for RDS to derive the oracle complexity achieve Q') S s². When early stopping is needed (i.e., 8 > 0), we prove in
Lem. 7 that choosing x z2ga suffices to ensure e-closeness in TV distance between Ty and æ, under weak assumptions similar to Assump. 2 For RDMC, RSDMC, ZODMC, and SNDMC, the total
complexities are, respectively, O (poly (d. exp (2) O(n) exp (83 log poly (B. d, m² 1
5
exp (o(d) log 3 log :) and O ((
(86m"va) ((stm
O(d)
The full analysis can be found in App. E.5
As discussed, RDS can be viewed as an optimally compensated ALD using the OU process as the trajectory. We conclude this section by contrasting these two approaches. On the one hand,
"This name introduced by us as the original paper did not provide name for the proposed algorithm. 'In RDMC, one assumes there exists O such that Vr > 0, V + r|] 1|2 is convex for all ||z||| 2 f In RDMC and RSDMC, is the probability threshold that the estimator may fail to achieve the desired accuracy e.
9

---

Published as a conference paper at ICLR 2026
maalytically-tractabe curves such as the geometric interpolation offer closed-fomm drift terms at all time points, but may exhibit poor action properties (Prop. I) or bad isoperimetric constants (Chehab) et al., 2025), making annealed sampling challenging. On the other hand, alternative curves like the OU process may have better properties in action and isoperimetric constants, but their drift terms, often related the scores of the intermediate distributions, lack closed-form expressions, and estimating these terms is also non-trivial. This highlights a fundamental trade-off between the complexity of the drift term estimation and the property of the interpolation curve.
Experiments. We now compare the performance of the methods of normalizing constant estimation for non-log-concent concave distributions that have been discussed in the paper. including TI, AIS, and the four RDS- based methods. We consider two multimodal target distributions: modified Müller Brown (MMB) distribution and Gaussian mixture (GM) with components, both in R.. The quantitative results are summarized in Tab. where we report the relative error of 2 and, for GM, the maximum mean discrepancy (MMD) and Wz distance between the generated samples ssamp and ground truth samples from x. All constant and high quality samples, while TI and AIS (based geometric annealing) produce seriously biased estimates due to lack of mode coverage. Further details are presented in App. I| and the codes for the experiments are available at NormConstEstt
methods provide accurate estimates of the normalizing
Table 1: Quantitative results of normalizing constant estimation (mean + std), best in bold.
Target
Metric
II
AIS
RDMC
RSDMC
Z0DMC
SNDMC
MMB
2/2
0.7527
0.0086
2.9740 :: 7.67U6
0.9829 = 0.2116
1,2885 + 12.7843
0.9878 : 0.1164
1.0053 =: 0.1192
2/2
0.2427
0.0016
0.0008
0.0001
0. 0.0850
0.8202
1.0276
037766
0.2835
0.033
MMIXR R)
2.5407
0.0281
224618
0.0270
0.3581
+ 0.0366
0.3124
0.0895
0.2501 + 0.0381
0.1576 - 0.0279
WatRamp x)
10.5602 + 0.0794
10.4892 + 0.0661
7,0242 = 0.9104
2.6012 + 0.2482
2,4506 + 0.2963
1.5494 =: 0 6820
6 CONCLUSION, LIMITATIONS, AND FUTURE DIRECTIONS
This paper investigates the complexity of normalizing constant estimation using JE, AIS, and RDS, and takes a first step in establishing non-asymptotic convergence guarantees based on insights from continuous- time analysis. Our analysis of JE Thm. 2) applies to general interpolations without explicit dependence of isoperimetry, thereby substantially extending prior work limited to log-concave distributions. Several limitations remain: the tightness of our upper bounds (Thms. 2 and 4 are unknown; the lower bound on the action in Prop. does not directly imply that JE needs exponentially long time to converge; though the action provides a clean analysis of the statistical efficiency of annealing-which isoperimetric inequalities cannot deal with-its practical interpretability is not well understood. Finally, we conjecture that our proof techniques can extend to samplers beyond overdamped LD (e.g.. Hamiltonian or underdamped LD (Sokl-Dickstein Culpepper 2012), parallel samplers (Anari et al. [2024) Zhou et al., 2025 Zhou & Sugiyama 2225a b)). and may also apply to estimating normalizing constants of compactly supported distributions on Rd (e.g., convex bodies volume estimation (Cousins & Vempala| 2018)) or discrete distributions (e.g., Ising model and
restricted Boltzmann machines (Huber 20155] Krause et al. ) via the Poisson stochastic integral framework (Ren al. 2025a b). which we leave a direction for future research.
ACKNOWLEDGMENTS
WG thanks Omar Chehab and Huanjian Zhou for insightful discussions. We also thank Jannis Chemseddine for pointing out the paper HuperrChemssdding et al. (2025) after we initially submitted our work to arXiv. WG and YC acknowledge supports from NSF Grants ECCS- 1942523, DMS-220655 and AFOSR Grant FA9550-25-15 1-0199. MT is thankful for partial supports by NSF Grants DMS- 1847802, DMS- 2518-2551399, 3699, DOE Grants NA0004261, SC0026274, and Richard Duke Fellowship.
REFERENCES
Michael Samuel Albergo and Eric Vanden- NETS: A non-equilibrium transport sam-
pler. In Forty-second International Conference on Machine Learning, 2025. URL https //openrevi eww wwwp:/toootomdooonnooeeoaeoe
10

---

Published as a conference paper at ICLR 2026
Luigi Ambrosio, Nicola Gigli, and Giuseppe Savaré. Gradient Flows: In Metric Spaces and in the Space of Probability Measures. Lectures in Mathematics. ETH Zürich. Birkhäuser Basel, edition, 2008. doi:
Luigi Ambrosio, Elia Brué, and Daniele Semola. Lectures on optimal transport, volume 130 of UNITEXT. Springer Cham, 2021. doi: 10. 00000077978---00--2212222 URL httph:http:/nnnt
springer www/book//0/ .pr.nnger.com//ooo//D 100.
030-72162-6
Nima Anari, Sinho Chewi, and Thuy-Duong Vuong. Fast parallel sampling under isoperimetry. In Shipra Agrawal and Aaron Roth (eds.), Proceedings of Thirty Seventh Conference on Learning
Theory, volume 247 of Proceedings of Machine Learning Research, pp. 161-185, PMLR, 30 URL
Jun 03 Jul 2024.
mmm.mmmr:.. press wttppp/////////aa2222222..
Brian D.O. Anderson. Reverse-time diffusion equation models. Stochastic Processes and their Applications, 12(3):31--326, 1982. ISSN 0304-4149. doi: 10.101600304-4149(8))
90051-5. URL https:/ /www sci enced rect. com scce///tccc//ttii////.iii
080441498290055
Christophe Andrieu, James Ridgway, and Nick Whiteley. Sampling normalizing constants high dimensions using inhomogeneous diffusions. arXiv preprini arXiv:/6/2.0755: 2016.
Mehrnoosh Arrar, Fernando Martín Boubeta, Maria Eugenia Szretter, Mariela Sued, Leonardo Boechi, and Danicla Rodriguez. On the accurate estimation of free energies using the Jarzynski equality. Journal of Computational Chemistry, (004))6888669))) 2019. doi: 10. 10.1002/jcc.25754 wttp://wwwlle.cccoo//oaa///a///e 10wp://cc.....//cce.c.ooooo 25754
Erik Aurell, Carlos Mejia-Monasterd and Paolo Muratore-Ginannesee Optimal protocols and optimal transport in stochastic thermodynamics. Phys. Rev. Lett., 106:250601, Jun 2011. doi: 10.1 1e1110//PhssReee..e...1622222000 PhysRevvLett.16..55000
URL bttps://link.. aps wtt.:/k..ppp..oooooo/011.1111...
Erik Aurell, Krzysztof Gawędzki, Carlos Mejia-Monasterio, Roya Mohayaee, and Paolo Muratore- Ginanneschi. Refined second law of thermodynamics for fast random processes. Journal of statistical physics, 147:487-505, 2012.
doi: 10.1007//-09555-0224478-.x
Dominique Bakry, Ivan Gentil, and Michel Ledoux. Analysis and geometry of Markov diffusion operators, volume 103 of Grundlehren der mathematischen Wissenschaften. Springer Cham, 1 edition, 2014. doi: 10. 11100/978-3331--002277
Krishna Balasubramanian, Sinho Chewi, Murat A Erdogdu, Adil Salim, and Shunshi Zhang. To- wards a theory of non-log-concave sampling: First-order stationarity guarantees for Langevin Monte Carlo. In Po-Ling Loh and Maxim Raginsky (eds.). Proceedings of Thirty Fifth Con- ference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pp. 2896 2923. PMLR, 02 05 Jul 2022. URL https::/prrceedingg mlr. www.ppressvvs... balasubramanian222.. html
Denis Blessing, Julius Berner, Lorenz Richter, and Gerhard Neumann. Underdamped diffusion bridges with applications sampling. In The Thirteenth International Conference on Learning Representations, 2025, hhttts:://ppenreiiert net forum
? - 2ttp://oommmmmoo010000mmmmmm m
Nicolas Brosse, Alain Durmus, and Éric Moulines. Normalizing constants of log- concave densities. Electronic Journal of Statistics, 12(1):851 8899 2018. doi: 10.1214/18-EIST EJS URL https
//doi.org/// 1211/111111 1811181111111
Davide Carbone, Mengjian Hua, Simon Coste, and Eric Vanden- -ijnden. Efficient training of energy-based models using Jarzynski equality. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (eds.), Advances in Neural In- formation Processing Systems, volume 36, pp. 52583-52614. Curran Associates. Inc..
2023. URL
neurips. co/paper files/ tatles/ppper/22233 E Ftte://4cbbsssaaBacccccaaaaaaaa3
Sourav Chatterjee and Persi Diaconis. The sample size required in importance sampling. The Annals of Applied Probability, 1899):1099 1135, 2018. doi: 10.1214/1-AAPP326. URL http::///0oi.000111111111

---

Published as a conference paper at ICLR 2026
Omar Chehab, Aapo Hyvärinen, and Andrej Risteski. Provable benefits of annealing for
timating normalizing constants: Importance sampling, noise-contrastive estimation, and be- yond. In Thirty-sevnnte Conference Neural Information Processing Systems, 2023. URL ht.tps:/ htttps::/spenneviee..r www.rrrrwwwweeeeooummmmmm forum? dd= ( WGCONsq91
Omar Chehab, Anna Korba, Austin J Stromme, and Adrien Vacher. Provable convergence and
limitations of geometric tempering for Langevin dynamics. The Thirteenth International Conference on Learning Representations, 2025. BtLhhttss:/// htttps://opennev.ew.coooo hwtee/wwwwwweeeeeeeeeeeeeeeeeeee forum?
id=DZemz 9w001
Jannis Chemseddine, Christian Wald, Richard Duong, and Gabriele Steidl. Neural sampling from Boltzmann densities: Fisher-Rao curves in the Wasserstein geometry. In The Thirteenth Interna- tional Conference on Learning Representations, 2025. URL
Haoxuan Chen and Lexing Ying. Ensemble-based annealed importance sampling. arXiv preprint arXiv:2401.15645, 2024.
Junhua Chen, Lorenz Richter, Julius Berner, Denis Blessing, Gerhard Neumann, and Anima Anand- kumar. Sequential controlled Langevin Diffusions. The Thirteenth International Confer- Learning Representations, 2025. http:t /ttp//ppeeeveeeeeeeeeeeeeeeeeeee net./ tent/forumt forum?id di
d dImD2sqy86
Ming-Hul Hui Chen and Qi- Shao. On Monte Carlo methods for estimating ratios of normalizing constants. The Annals of Statistics, 25(4):1563 1594, 1997. doi: 10.1214/ao/10311594722. URL
https: 10t.:///...1111////111111111111
Sitan Chen, Sinho Chewi, Jerry Li, Yuanzhi Li, Adil Salim, and Anru Zhang. Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions. In The Eleventh International Conference Learning Representations, 2023. URL hattps://operreviee
Yongxin Chen, Tryphon T Georgiou, and Michele Pavon. On the relation between optimal transport and Schrödinger bridges: A stochastic control viewpoint. Journal of Optimization Theory and Applications, (69:671-691, 2016. doi: 10. 10.1007/110957-015-000000
Yongxin Chen, Tryphon Т. Georgiou, and Allen Tannenbaum. Stochastic control and nonequilibrium thermodynamics: Fundamental limits. IEEE Transactions on Automatic Control, 65(7):297--299,, 2020. doi: 10.1099TAA.22019229996.
Yongxin Chen, Tryphon T. Georgiou, and Michele Pavon. Stochastic control liaisons: Richard Sinkhorn meets Gaspard Monge on a Schrödinger bridge. SIAM Review, 63(2):249-313, 2021. doi: 1..11377/0MM13399222 URL /ttp://////0.0.000011111111/////
Xiang Cheng, Niladri S. Chatterji. Peter L. Bartlett, and Michael Jordan. Underdamped Langevin MCMC: A non-asymptotic analysis. In Sébastien Bubeck, Vianney Perchet, and Philippe Rigollet (eds.), Proceedings of the 31st Conference On Learning Theory, volume 75 of Proceedings of Machine Learning Research, pp. 300-323, PMLR, 06-09 Jul 2018. URL https://proceediin mlr. walrrppesss v 75 wT5l wwt.c html
Xiang Cheng, Bohan Wang, Jingzhao Zhang, and Yusong Zhu. Fast conditional mix- ing of MCMC algorithms for non-log-concave distributions. In A. Oh, T. Neumann. A. Globerson, K. Saenko, M. Hardt, and S. Levine (eds.), Advances in Neural In- formation Processing Systems, volume 36, pp- 13394.13394. Curran Associates, Inc..
2023. URL httpps://proceeediiiiii/ neurips catpsper..p.peeeeeeeeeeeee files//paprr/222/ fi file e htt.:200003333l00fffffa4a4aa2223 Serereeeeeeectcaeeeeeeeeeeeeeeee .df pdf.
Paper Conference.cccccooccooccccooooee
Sinho Chewi. Log- Ca-caoC Sampling. Book draft, in preparation, 2022.
URL https
7/chewishe sinho. wit..
12

---

Published as a conference paper at ICLR 2026
Sinho Chewi, Murat A Erdogdu, Mufan Li, Ruoqi Shen, and Shunshi Zhang. Analysis of Langevin Monte Carlo from Poincaré to log Sobolev. In Po-Ling Loh and Maxim Ragin- sky (eds.). Proceedings of Thirty Fifth Conference ceedings of Machine Learning Research, pp- 1-2. PMIR, 02-05 Jul 2022. URL. https
Learning Theory, volume 178 of Pro-
//proceedings.. www.:saww.ppprrrrrmmmmm /vress/vv78// chew 22a html
Christophe Chipot and Andrew Pohorille (eds.). Free Energy Calculations: Theory and Applications in Chemistry and Biology. Springer Series in Chemical Physics. Springer Berlin, Heidelberg, 2007.
doi: 01007/978-3550--333
Giovanni Conforti and Luca Tamanini. A formula for the time derivative of the entropic cost and applications. Journal of Functional Analysis, 280(11): 2021. ISSN 0022-1236. doi: 2f.
URL http::/:/wwwww.ie.nee....e.. rect ctm. wwt.:/ccw/cccccceeeeeeeecc..eeee
artticle/A1150022222220000
Ben Cousins and Santosh Vempala. Gaussian cooling and O (n²) algorithms for volume and Gaussian volume. SIAM Journal on Computing, 4233)11237-127,,, 2018. doi: 10.1137/15M1054250 URL
https://doi. , wrw.or..............o..o. wtt.:/0..113//1511..... 11377/15111554255
Gavin E. Crooks. Nonequilibrium measurements of free energy differences for microscopically
reversible Markovian systems. Journal of Statistical Physics, 90:1481-1487, 1998. doi: 10.10///A: 1023208217925.
Gavin E. Crooks. Entropy production fluctuation theorem and the nonequilibrium work relation for free energy differences. Phys. Rev. E, (0002222122226 Sep 1999. doi: 10. htt.100//yyseeE....222 URL
ott. ortp://...pp..oooo/o///oo http://:......//hy/eeeeee 60.260.2222 20.221
Pierre Del Moral, Arnaud Doucet, and Ajay Jasra. Sequential Monte Carlo samplers. Journal of the Royal Statistical Society Series B: Statistical Methodology, 68(3):41 1-436, 5 2006.
Arnaud Doucet, Simon Godsill, and Christophe Andrieu. On sequential Monte Carlo sampling methods for bayesian filtering. Statistics and computing, 10: 10:1997208, 2000. doi: 10.1023/A: 1008935410038.
Arnaud Doucet, Will Grathwohl, Alexander G Matthews, and Heiko Strathmann. Score- based diffusion meets annealed importance sampling. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh (eds.), Advances in Neural Infor- mation Processing Systems, volume 35, pp. 21482-21499 Curran Associates, Inc., 2022. URL htttpa::/prooeeeinngge nwwrieuurucooo wwtppppr.cpppppp.pppppppppp....e httpp///eeeeepa/////222222 Sonpredeeeeeppppeeeeeoeeeeeeeeee
Yuanqi Du, Jiajun He, Francisco Vargas, Yuanqing Wang, Carla P Gomes, José Miguel Hernández- Lobato, and Eric Vanden-Eijnden. FEAT: Free energy estimators with adaptive transport. In The nhith Anmual Conference on Neural Information Processing Systems, 2025. URL
net forum http://wwww.eeeooooueeeeeee-eee 1tt.eummmeidxXXXGGGXGGGG
Martin Dyer, Alan Frieze, and Ravi Kannan. A random polynomial time algorithm for approximating the volume of convex bodies. J. ACM, 38(1):1-111, January 1991 ISSN 0004-5411. doi: 10. 102782.102783. URL
ctg/ 1145/1022 127782 102783
Ignacia Echeverria and L. Mario Amzel. Estimation of free-energy differences from computed work distributions: An application Jarzynski's equality. The Journal of Physical Chemistry B, 116 (36):10977-11396 2012. doi: 10. 10110////30/
Rémi Flamary, Nicolas Courty, Alexandre Gramfort, Mokhtar Z. Alaya, Aurélie Boisbunon, Stanislas Chambon, Lactitia Chapel, Adrien Corenflos, Kilian Fatras, Nemo Fournier, Léo Gautheron, Nathalie T.H. Gayraud, Hicham Janati, Alain Rakotomamonjy, levgen Redko, Antoine Rolet, Antony Schutz, Vivien Seguy, Danica Sutherland, Romain Tavenard, Alexander Tong, and Titouan Vayer. POT: Python optimal transport. Journal of Machine Learning Research, 22(78): 1-8, 2021. URL WtRLhttp:/// //jtp: org wwtp:oppppppppppppppppe.ee
451 html
Hao Ge and Da- Da-Quan Jiang. Generalized Jarzynski's equanit of inhomogeneous multidimensional diffusion processes. Journal of Statistical Physics, 131:675-688 3 2008. ISSN 1572-9613, doi: 10.10077/100555-00--9522
13

---

Published as a conference paper at ICLR 2026
Rong Ge, Holden Lee, and Andrej Risteski. Beyond log-concavity: Provable guarantees for sampling multi multi-modal distributions using simulated tempering Langevin Monte Carlo. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Gar- nett (eds.), Advances in Neural Information Processing Systems, volume 31. Curran Asso- ciates, Inc., 2018. URL 2018 htt.e//eeeeeeeeeeeeeeeee/e00aae.
neurips cacc/pppr_fileeeee files/paper
Rong Ge, Holden Lee, and Jianfeng Lu. Estimating normalizing constants for log-concave dis- tributions: Algorithms and lower bounds. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, pp. 579-586, New York. NY, USA, 2020. doi: 10.1145/357713.3884555
Association for Computing Machinery, ISBN 9781450369794,
URL htt.htttp:/o/oooo http:///o...or111111111133/33/11
10.....1115133111 211444433337773333343333 3384289
Andrew Gelman and Xiao-Li Meng. Simulating normalizing constants: from importance sampling to bridge sampling to path sampling. Statistical Science, 13(2):133 185, 1998. doi: 10.1214/ss/ 1028905934.
/t..gg/o..1244. 1214 ss 028905934
Andrew Gelman, John B. Carlin, Hal S. Stern, and Donald B. Rubin. Bayesian data analysis. Chapman and Hall/CRC, edition, 2013.
Wei Guo, Molei Tao, and Yongxin Chen. Provable benefit of annealed Langevin Monte Carlo for non- log-concave sampling. In The Thirteenth International Conference on Learning Representations, 2025. URL http:::::///peeeeii.ee
Carsten Hartmann and Lorenz Richter. Nonasymptotic bounds for suboptimal importance sam- pling. SIAM/ASA Journal Uncertainty Quantification, 12(2):309-346, 2024. doi: 10.1137/
21M14277.0. httpts::: http:::::///o...o////..1//////1/ 1117:/210.1137/111111 427760
Carsten Hartmann, Lorenz Richter, Christof Schütte, and Wei Zhang. Variational characterization of free energy: Theory and algorithms. Entropy, 19(1)) 2017. ISSN 1099-4300. doi: 10.3390/
e19110626. URL ht wwwpi.pp...o com/ 1090-1990000 wttp:/0000000/01111/1111// /010//3000///////
Carsten Hartmann, Christof Schütte, and Wei Zhang. Jarzynski's equality, fluctuation theorems, and variance reduction: Mathematical analysis and numerical algorithmss Journal of Staristical Physics, 175:1214-1261 2019. doi: 10. 01177//1105--09-2285600 10. 11100///0055-01---000
URL battps://do. org/
Aaron J Havens, Benjamin Kurt Miller, Bing Yan, Carles Domingo-Enrichh Anuroop Sriram, Daniel S. Levine, Brandon M Wood, Bin Hu, Brandon Amos, Brian Karrer, Xiang Fu, Guan- Horng Liu, and Ricky T. Q. Chen. Adjoint sampling: Highly scalable diffusion samplers via adjoint matching. In Forty-second International Conference on Machine Learning, 2025. URL https://cpenrevier net forum?idd 5Eg1OrHmm Hngg
Ye He, Kevin Rojas, and Molei Tao. Zeroth-order sampling methods for non-log-coneave distributions: Alleviating metastability by denoising diffusion. In The Thirty- Annual Conference on Neural Information Processing Systems, 2024. URLpttts:///peent http:///ppeeevveieee www.ieew..eeeeeee...m...ee..ee.e forum?
1d=X3A julljllsls 5w5
Yuchen He and Chihao Zhang. On the query complexity of sampling from non-log- non-log-concave concave distri- butions (extended abstract). In Nika Haghtalab and Ankur Moitra (eds.), Proceedings of Thirty Eighth Conference on Learning Theory, volume 291 of Proceedings of Machine Learning Research, pp. 2786-2787. PMLR, 30 Jun-04 Jul 2025. URL RtlLhhtts::/// htttose/pproeed/ ngs. ml press/ v291 2tee5aahmmll..
Xunpeng Huang, Hanze Dong, Yifan Hao, Yian Ma, and Tong Zhang. Reverse diffusion Monte Carlo. The Twelfth International Conference on Learning Representutions, 2024a. URL
hittps://epe /ttp::s//ppeeeeieww .et Eorum? www.:/ommmmiiiitttsss...
Xunpeng Huang, Difan Zou, Hanze Dong, Yi-An Ma, and Tong Zhang. Faster sampling with- out isoperimetry via diffusion- Monte Carlo. In Shipra Agrawal and Aaron Roth (eds.), Proceedings of Thirty Seventh Conference Learning Theory, volume 247 of Proceedings of Machine Learning Research, pp. 2438-2493. PMLR, 30 Jun-03 Jul 2024b. URL https .tmml
7/proceed igg. ml press
14

---

Published as a conference paper at ICLR 2026
Mark Huber. Approximation algorithms for the normalizing constant of Gibbs distributions. The Annals of Applied Probability, 25(2):974 985, 2015. doi: 10.1214/14AAAP00S.. htthttps
//doi. 1214:40.121444-A-5
Christopher Jarzynski. Nonequilibrium equality for free energy differences. Phys. Rev. Lett. 78: 2690-2693, 1997. doi: 10.1 10.100//yyReeeLet.7..... (tt.eeeeeet....6900.0 78.2690. URL httph: aps org/
do1/10.1103/PPH co./100:106/PP.seeevleettt 7a.tt.78.2555 78.2690
Ajay Jasra, Kengo Kamatani, Prince Peprah Osei, and Yan Zhou. Multilevel particle filters: normalizing constant estimation. Statistics and Computing, 28:47-60, 2018. doi: 10.
s11222-016-9715.5.
Mark R. Jerrum, Leslie G. Valiant, and Vijay V. Vazirani. Random generation of combinatorial structures from a uniform distribution. Theoretical Computer Science, 43:169-188, 1986. ISSN 0304-3975. doi: 10. 101 1011660004-39755869991111177
URL htt.hhttss//// www.eeicccncccrrrctttttt.....c..
com/ /tall///ceeooeeereeeeee///////30
Ioannis Karatzas and Steven E. Shreve. Brownian Motion and Stochastic Calculus. Graduate Texts in Mathematics. Springer New York, NY, 2 edition, 1991. doi: 10. 10.10079988-1-4612--99999
Diederik P Kingma and Max Welling, arXiv:1312.61 14,661114000 2013.
Auto-encoding variational Bayes.
arXiv preprint
John G. Kirkwood. Statistical mechanics of fluid mixtures. The Journal of Chemical Physics, 3(5): 300-313, 05 1935. ISSN 0021-9606. doi: 10.1063/1.1749657, URL httppp:///oi.ooot 01633/.174966
Yunbum Kook and Santosh S. Vempala. Sampling and integration of logconcave functions by algorithmic diffusion. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC '25, pp. 924-932, New York, NY. USA, 2025. Association for Computing Machinery. ISBN 10998000715005. doi: 10.1145/3711883337188000 URL 371 0717823.20 371.3071800 1802
Yunbum Kook, Santosh Vempala, and Matthew Shunshi Zhang. In-and-Out: Algorithmic diffusion for sampling convex bodies. In The Thirth- Anmual Conference on Neural Information Processing Systems, 2024. URL /ttpss:///peeeeeeei wwt.rriwwww.teeo.nn.n.e.. idd aNOWRHyh15
Svetoslav Kostov and Nick Whiteley. An algorithm for approximating the second moment of the normalizing constant estimate from a particle filter. Methodology and Computing in Applied Probability, 19:799-818, 818, 2017. doi: 1009007/110000-01-9999
Oswin Krause, Asja Fischer, and Christian Igel. Algorithms for estimating the partition function of restricted Boltzmann machines. Artificial Intelligence, 278: 103195, 2020. ISSN 0004-3702. doi: 10. 10.1016/j.attin..2111... 103199. URL (tt.tttss //ww://wwww//. sc encedi rect com..ccoo/eeee Aaticole//1//000477722900999999
C. Le Bris and P.-L. Lions. Existence and uniqueness of solutions to Tokker-Plande type equa- tions with irregular coefficients. Communications in Partial Differential Equations, 33(7): 1272-1317, 2008 doi: 10. (0800036003300801970995
URL wtt.ooi.ooro..ooo 000
0.0005530001970995
Holden Lee, Jianfeng Lu, and Yixin Tan. Convergence of score-based generative modeling for general data distributions. In Shipra Agrawal and Francesco Orabona (eds.), Proceedings of The 34th International Conference on Algorithmic Learning Theory, volume 201 of Proceedings Machine Learning Research, pp. 946-985, PMLR, 20 Feb-23 Feb 2023, URRppttss////ooeeeee
mlr. 2at..eesssvv211eee22... html
Tony Lelièvre, Mathias Rousset, and Gabriel Stoltz. Free Energy Computations: Mathernatiaa Perspective. Imperial College Press, 2010. doi: 10. 10.1142/p579.
Christian Léonard. A survey of the Schrödinger problem and some of its connections with optimal transport. Discrete and Contimuous Dynamical Systems Series A, 34(4):1533-1574 2014. URL
https: //hha sci eecieeceeccc hal scc.enccehhl--00849993
15

---

Published as a conference paper at ICLR 2026
Jianzhu Ma, Jin Peng, Sheng Wang, and Jinbo Xu. Estimating the partition function of graphical models using langevin importance sampling. In Carlos M. Carvalho and Pradeep Ravikumar (eds.), Proceedings of the Sixteenth International Conference
Artificial Intelligence and Statistics, volume 31 of Proceedings of Machine Learning Research, pp. 433-441, Scottsdale, Arizona, USA, 29 Apr-01 May 2013. PMLR. URL.https: htt./tttts///proeediiiiii poppooeeeings... ml wtt..........s/11//e.m 13a html
Bälint Máté and François Flcuret. Learning interpolations between Boltzmann densities. Transactions on Machine Learning Research, 2023, ISSN 2835-8856. /ttptttt/////eeeee..ee..
Forum?1G=TH6Y
Bálint Máté, François Fleuret, and Tristan Bereau. Neural thermodynamic integration: Free energies
from energy- based diffusion models. The Journal of Physical Chemistry Letters, 15(45):11395. 11404, 2024. doi: 10. 10.10///acs..pp wpwpssjepeeettt11199..
jpclett. 4c01958
PMID: 39503734.
O Mazonka and C Jarzynski. Exactly solvable model illustrating far-from-equilibriiu predictions. arXiv preprint cond-mat/991211 1999.
Ferran Mazzanti and Enrique Romero. Efficient evaluation of the partition function of RBMs with annealed importance sampling. arXiv preprint arXiv:2007. 1926, 2020.
Xiao-Li Meng and Wing Hung Wong. Simulating ratios of normalizing constants via a simple identity: theoretical exploration. Statistica Sinica, 6(4):831-860, 1996. ISSN 10170405, 19968507. URL http://www. jsw.rrsoooo............... wttp://////taaeeeeeeeeooo.
Alireza Mousavi-Hosseinni, Tyler K. Farghly, Ye He, Krishna Balasubramanian, and Murat A. Erdogdu. Towards a complete analysis of Langevin Monte Carlo: Beyond Poincaré inequality. In Gergely Neu and Lorenzo Rosasco (eds.), Proceedings of Thirty Sixth Conference on Learning Theory, volume 195 of Proceedings of Machine Learning Research, pp. 1-35, PMLR, 12-15 Jul 2023, URL http:/ps//ppocceeeinnggeoo mml..ngssm...r....mm......m..mlm mlr wwt.mm..ppreeeleemmmmm htwp://///ooaoaaoooooooeeaaaaaa.
Radford M. Neal. Annealed importance sampling, Statistics and Computing, 11(2): April 2001. ISSN 1573-1375.
doi: 10.1023/A:100882231155
URL httpps://66i..rr//10
1023 A. 10l::23009222000
Edward Nelson. Dynamical Theories of Brownian Motion. Princeton University Press, 1967. ISBN 9780691079509. URL http::///// www. http://ttt...rrr/aaaaa////./.tt.
Nikolas Nüsken and Lorenz Richter. Solving high-dimensional Hamiton--Acobi-Bellna PDEs using neural networks: perspectives from the theory of controlled diffusions and measures on path space. Partial differential equations and applications. 2(4):48, 2021. doi: 10.1007/
s42985-021-00102-x.
Andrew Pohorille, Christopher Jarzynski, and Christophe Chipot. Good practices in free-energy calculations. The Journal of Physical Chemistry B, 114(32):10235--0023 2010. ISSN 1520-6106. doi: 10.1021/jp102971x. URL
Yinuo Ren, Haoxuan Chen, Grant M. Rotskoff, and Lexing Ying. How discrete and continuous diffusion meet: Comprehensive analysis of discrete diffusion models via stochastic integral framework. In The Thirteenth International Conference on Learning Representations, 2025a. URL
https::/openrevvew httpl/ewwweeeeeeeeeeeeeeeeeeeeee www./eeetouuiee cerormmiidee 6awxwQBI82
Yinuo Ren, Haoxuan Chen, Yuchen Zhu, Wei Guo, Yongxin Chen, Grant M. Rotskoff, Molei Tao, and Lexing Ying. Fast solvers for discrete diffusion models: Theory and applications of high-order algorithms. In The Thithy-ninth Annual Conference Neural Information P Processing Systems, 2025b. /tttittss:///peneeeeee
/ttp:s////peeeeiieeeeee net forum? wwwwoooidooouuoooooooooooooo id=iidd=llaaa L60330
Lorenz Richter and Julius Berner. Improved sampling via learned diffusions. In The Twelfth International Conference on Learning Representations, 2024, URL http::::: :ecttps://pprnee //operevview hett/Forum2iooMMqMRRoooo
16

---

Published as a conference paper at ICLR 2026
Herbert E. Robbins. An Empirical Bayes Approach to Statistics, pp. 388-394, Springer New York, New York, NY, 1992. ISBN 978-144612-011-55. doi: 10. 1-11///8----112-99---53 URL
http://......ooo......0002116111 26"
Hamza Ruzayqat, Neil K Chada, and Ajay Jasra. Multilevel estimation of normalization constants using ensemble Kalman-Buu Bucy filters. Statistics and Computing, 32(3):38, 2022. doi: 10.1007/
111222-022 10094--..
Michael Eli Sander, Vincent Roulet, Tianlin Liu, and Mathieu Blondel. Joint learning of energy- based models and their partition function. In Forty-second International Conference on Machine Learning, 2025. httt:s:::: htt.ts:::/ppeeeeieeeeeeee net for.//oormmm fege: d=
Filippo Santambrogio. Optimal Transport for Applied Mathematicians. Birkhäuser Cham, 2015. doi: 1111007/978-3311-20000
Christoph Schönle, Marylou Gabrié, Tony Lelièvre, and Gabriel Stoltz. Sampling metastable systems using collective variables and Jarzynski- Crooks paths. Journal of Computational Physics, 527: 113806, 2025. ISSN 0021-9999.. doi:
13880. URL https
7/www. www.sscceece...c rect com httpa///ooaao./ooaaaaoo/oooaaaaa
Udo Seifert. Stochastic thermodynamics, fluctuation theorems and molccular machines. Reports
Progress in Physics, 75(12):126001, nov 2012. doi: 10010080000444555///12200000 URL
https://dx. do1 http:/xd.oo....gg//.oo/oo 1ttp:///.10111001343143330 111////00000-66555//111/1111/110
Ken Sckimoto. Stochastic Energetics. Lecture Notes in Physics. Springer, 1 edition, 2010. doi:
00.1007/978-3-642-454111
Jascha Sohl-Dickstein and Benjamin Culpepper. Hamiltonian annealed importance sampling for partition function estimation. Technical report, Redwood Technical Report, 2012. URL
http://arxiv www./ogg.......o......e abwaabss..... 1925
Yang Song and Diederik P Kingma. How to train your energy-based models. arXiv:2/01.03288, 2021.
arXiv preprint
Yang Song, Jascha Sohl-Dicksteei, Diederik P Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole. Score-based generative modeling through stochastic differential equations. In International Conference on Learning Representations, 2021. URL
formm??
(G=PXTIG12RRHS
Jingtong Sun, Julius Berner, Lorenz Richter, Marius Zeinhofer, Johannes Müller, Kamyar Aziz- zadenesheli, and Anima Anandkumar. Dynamical measure transport and neural PDE solvers for sampling. arXiv preprint arXiv:2407.07873 2024.
Saifuddin Syed, Alexandre Bouchard-Côté. George Deligiannidis, and Amaud Doucet. Non- reversible parallel tempering: A scalable highly parallel MCMC scheme. Journal of the Royal Staristical Society Series B: Statistical Methodology, 84(2):321 350, 12 2021. ISSN 1369-7412. doi: 10. 1/rssb. 12464.
org. wtt.///.///...11/............... 111.11111/ssss 12464
Saifuddin Syed, Alexandre Bouchard-CSS -ôtéé, Kevin Chern, and Araad Doucet. Optimised annealed sequential Monte Carlo samplers. arXiv preprinl arXiv:2408. 12057, 2024.
Nicholas G Tawn, Gareth O Roberts, and Jeffrey Rosenthal. Statistics and Computing, 30(1):27-41 41, 2020. doi: 10.10077s112222-11--993
simulated tempering.
Ali Süleyman Üstünel and Moshe Zakai. Transformation of Measure Wiener Space. Springer Monographs in Mathematics. Springer Berlin, Heidelberg, edition, 2013. doi: 10.1007/
13225-8.
Adrien Vacher, Omar Chehab, and Anna Korba. Sampling from multi-modal distributions with polynomial query complexity in fixed dimension via reverse diffusion. In The Thirty-ninth Annual Conference on Neural Information Processing Systems, 2025, URL httttss://opeeeeiiieee net/for d= 20t.rmmmmmoxxx72200ea
17

---

Published as a conference paper at ICLR 2026
Suriyanarayanan Vaikuntanathan and Christopher Jarzynski. Escorted free energy simulations:
Improving convergence by reducing dissipation. Phys. Rev. Lett. 100:190601, May 2008. doi: 10.1105/PhysRevvett.. 10.. 100.10000...... URL httpp:://inkk........ http://iw..aaaa.oooo/////////.//
PhysReviett. 100. 90601
Francisco Vargas, Shreyas Padhy, Denis Blessing, and Nikolas Nüsken. Transport meets variational inference: Controlled Monte Carlo diffusions. In The Twelfth International Conference on Learning Representations, 2024. URL JRtps:::://ppeneeeee net http://wwww......rrooooooo-oooo.
Cédric Villani. Topics in optimal transportation, volume 58. American Mathematical Society, 2003.
Cédric Villani. Optimal Transport:
Old and New. Grundlehren der mathemattschhn Wissenschaften.
Springer Berlin, Heidelberg, 1 edition, 2008. doi: 10. 10110007978-335550-00000- URL https
Dawn Woodard, Scott Schmidler, and Mark Huber. Sufficient conditions for torpid mixing of parallel and simulated tempering. Electronic Journal of Probability, 14(mone):780) 804, 2009. doi: 1tt.:////....111112..2.22.2
10.1214/EJP.v14663.
Muneki Yasuda and Chako Takahashi. Free energy evaluation using marginalized annealed importance sampling. Phys. Rev. E, 106:024127, Aug 2022. doi: 10.1 1ww.oo//hyy.e......222..... URL
024.27
Qinsheng Zhang and Yongxin Chen. Path integral sampler: stochastic control approach for sampling. In International Conference on Learning Representations, 2022. URL https://
openreview net forum?id uCb2ynRu7y
Qinsheng Zhang and Yongxin Chen. Fast sampling of diffusion models with exponential integrator.
In The Eleventh International Conference on Learning Representations, 2023. URL https
net. 7openrevvie httpe//ieeweeee///ereteeeeeeee Forum?1dFFloek7httb
Qinsheng Zhang, Jiaming Song, and Yongxin Chen. Improved order analysis and design of exponen- tial integrator for diffusion models sampling. arXiv preprint arXivv2308.02157, 2023a.
Qinsheng Zhang, Molei Tao, and Yongxin Chen. gDDIM: Generalized denoising diffusion implicit models. In The Eleventh International Conference on Learning Representations, 2023b. URL
net /ttts:://ppenre wtw.://wwwweeeeteeeeeeeeoeoee Forummiddihhesqpp
Huanjian Zhou and Masashi Sugiyama. Parallel simulation for log-concave sampling and score-based diffusion models. In Forty-second International Conference on Machine Learning, 2025a. URL
https://cpenrevieet net net wdtp:oommmmmmtttxxxxxxyaxxxa
Huanjian Zhou and Masashi Sugiyama. The adaptive complexity of minimizing relative fisher
information. In The Thirty-ninth Annual Conference on Neural Information Processing Systems, 2025b. URL https: h
Huanjian Zhou, Baoxiang Wang, and Masashi Sugiyama. The adaptive complexity parallelized log- concave sampling, 2025. URL /tattt:://ppeereeee
wwt.forrute wid wttdddeeglppppalaeeee kP
Daniel M. Zuckerman and Thomas B. Woolf. Theory of systematic computational error in free
energy differences. Phys. Rev. Lett., 89:180602, Oct 2002. doi: 10. 10.
URL https:
aps org/ http:p//.......oooo////////11111
.8. 19.00 180602
Daniel M. Zuckerman and Thomas B. Woolf. Systematic finite-sampling inaccuracy in free energy differences and other nonlinear quantities. Journal of Statistical Physics, 114: 114:1303-1323, 3 2004.
doi: 10.1023/B:JOSS. :000///:SSS.00000033330 84866.0..
18

---

Published as a conference paper at ICLR 2026
CONTENTS
Introduction
Preliminaries and Problem Setting
Analysis of the Jarzynski Equality
Analysis of the Annealed Importance Sampling
Normalizing Constant Estimation via Denoising Diffusion
6
Conclusion, Limitations, and Future Directions
10
Preliminaries
A.I I
Stochastic Analysis: Forward-backward SDEs and Girsanov's 's Theorem
21
Optimal'Tansponn Transport: Wasserstein Geometry and Metric Derivative
24
Pseudo-codes of the Algorithms
24
Proofs for 3
24
A Complete Proof of lmm.
24
Proof of
25
D Proof Thm. 4
27
Proofs for Sec. 5
33
E.1 Proof of Prop.
33
Proof of Prop.
36
Proof of Thm.
36
E,4
4 An Upper Bound of the TV Distance along the OU Process
37
E.5 Discussion on the Overall Complexity of RDS
38
Supplementary Lemmas
39
Review and Discussion on the Error Guarantee (1)
41
Literature Review of Existing Bounds
G.2
Equivalence in Complexities for Estimating Z and
42
is Weaker than Bias and Variance
42
G.4
Upper Bound on the Normalized Variance of Z in Jarzynski Equality
42
H
Related Works
43
Thermodynamic Integration
43
H.2
Path Integral Sampler and Controlled Monte Carlo Diffusion
45
19

---

Published as a conference paper at ICLR 2026
I
Details of Experimental Results
46
Modified Müller Brown distribution
46
Gaussian Mixture Distribution
47
I.3
Implementation Details
47
20

---

Published as a conference paper at ICLR 2026
A PRELIMINARIES
A.1 STOCHASTIC ANALYSIS: FORWARD-BACKWARK SDES AND GIRSANOV'S THEOREM
For stochastic differential equation (SDE) X (ex)) defined on Q C(O,, 7); 1+). the distribution of over called the path measure X, defined by IPx; measurable
Ω +
Pr(X E A). The following lemma, as a corollary of the Girsanov's theorem (Üstünel & Zakai 2013 Prop. 2.3.1 Cor. 2.3.1), provides a method for computing the Radon-Nikodým (RN) derivative and KL divergence between two path measures, which serves as a key technical tool in proof.
Lemma 1. Assume we have the following two SDEs with t E []:
dX; (Xx))tt + adB,, Xo ~ ic dY, b, (Y,)dt + odBı, Yo ~.V.
Denote the path measures of X and Y as ppx and Ipx, respectively. Then,oor any trajectory & E Q
dp-x du
0² /," (ar(Es) - b,(S)) 2/2 1,"
log dPy (E) log (5o) +
dv
202
In particular, plugging in & + X ~ pxx we can compute the KL divergence:
20 (- Epx [|x,(X,) - dx.
KL(PXIPP') KL(uIIP) +
Remark The Girsanov's theorem requires a technical condition ensuring that local martingale is a true martingale, typically verified via the Novikov condition (Karatzas & Shreve 1991 Chap. 3, Cor. 5.13), which can be challenging to establish. However, when only an upper bound of the KL divergence is needed, the approximation argument from Chen et al. (2023 App. B.2) circumvents the verification of the Novikov condition. For additional context, see Chewi 2002 Sec. 3.2). this puper, we omit these technical details and always assume that the Novikov condition holds.
We now present the theory of backward stochastic integral and the Girsanov's theorem, which adapted from Vargas al. (024).. Here, include relevant results and proofs to ensure self-contained presentation.
The backward SDE be perceived as the time-reversal of forward SDE:
Definition 1 (Backward SDE). Given a BM (Be) let its time-reversal be (Br
- We say that process (XE))) satisfies the backward SDE
dxx- = ox dt + odB,, t T); X+ ~ v
its time-reversal (X, x7-1)s;00,1 [. satisfies the following forward SDE:
dX, -ur < + odBr, LE [O Xo ~00
Remark 4. Intuitively, one understand the backward SDE through the following Faler-Maruyama discretization: with At. > 0:
X X N Xt
XT R XT - -B
where B B ~ NO, ATT) and independent of (X; )
The forward and backward SDEs are related through the following Nelson's relation: Lemma 2 (Nelson's 's relation Nelson 1967 Anderson 1982)) Given BM (Bi)eejoTT) and its
rime-seversal (B, = Br -)) the following two SDEs
dx, = a (X,)dt + odB,, No ~ Po; and dY, = d. + odB, Yr ~
have the same path measure if and only if
Pr: and be = az 2d logpe, VI E [0,T],
where Pt is the p.d.f. of Xt.
21

---

Published as a conference paper at ICLR 2026
Proof. The proof is by verifying the Fokker-Planck equation. For X, we have
O.p: = V (aept)) + a² 2 Apt-
Let xf= == xT- Then p. satisfies
2 Arp - ((-aE + o 2²v log Dpi + o²
Owv = V (az Pt
App
2
which means (Xt)) )uu (.2] has the same path measure as the following SDE:
dz. = (a - log Pt (Z,)dt + adB,, Z. ~ Pt On the other hand, by definition, (X1 )eEo,17) satisfies the forward SDE
d'," -,, (V, )tt + odB,, Yo ~ 9.
and thus the claim is evident.
We now introduce the concept of backward stochastic integral, which allows us represent the RN derivative between path measures of forward and backward SDEs.
Definition (Backward stochastic integral). For two continuous stochastic processes X and Y on C(O0, )),, the backward stochastic integral of Y with respect to X is defined
[. (Y,, xdX.) = Pr- lim
n- X (Yan,
Xt.)
where = (0= to <t < <t, T3 is a partition of [0, TV ||]|| max (t++1 -4), and
sE[1,x]
the convergence is in the probability sense. When both X and Y are continuous semi-martingales, one can equivalently define
Ln (Y,, (X,.dx)) ( (X., +
(15)
where [X,Y Y). is the cross quadratic variation proces: of the local martingale parts of X and Y. Remark Although rarely used in practice, the backward stochastic integral is sometimes referved as the Hänggi- Klimontovich integral in the literature. Recall that the Itô integral is defined as the limit of Riemann sums when the leftmost point of each interval is used, while the Stratonovich integral based on the midpoint and the backward integral uses the rightmost point. The equivalence in (15) can be justified in Karatzas & Shreve (1991) Chap. 3.3).
Lemma (Continuation of Lem. T}. 1. If we replace the SDEs in Lem. with
dX,- = arl (X,)d + odB; X ~ ps
dy, = by,))d + odB,, Yr ~ v,
while keeping other assumptions and notations unchanged, then for any trajectory & Ω
x log dpr (5) = log dv
du
(Ex) + 0² (" (ar(E)) - b,(E,), #dE,)
1
202
and consequently.
1
/" Epx (x,((x)-b(xx))) (x.))
KL(P*IP' KL(U|lo) + 20
2. Define the following SIESS from 0 to T:
dx, (d.)))t adB,, No ~ pn;
dy, = b((Y))dt + odB,, Yr ~ N.
Denote the path measures of X and Y as xax and PY, respectively. Then for any trajectory & E Q
x log dey (E) = log
(((En) v(Er) 0² (."' ((ar(E)). - (br(E)), *dE,)) 20t L' (Ila,(5)))P [lb((E))l))dt.
'The notation used in Karatzas & Shreve 1991 is (s,).. We use square brackets here to avoid conffict with the notation for inner product.
22

---

Published as a conference paper at ICLR 2026
Proof. 1. Only in the proof of this theorem, the notation +1- #T-- to represent the time reversal. We know that
dxt= -a (X; odB,, X μ4
d bb (Y, dt + odB,, Yo
Let pxx and pp= be the path measures of X and y+, respectively, From Lem. 1
we know that
dpxx* log dpr- (E) log
du dv (50)
02 (' (a) (E.), dEi)
1
! (Ila) (E:)1 1|65 (E=)ll)ddt 20
1
Since p (dE) = Pr(X* E dg) Pr(X E de*)) Px (df we obtain
dlpx
dipx*
log
dPY (E) log dPY (5*)
1
[ (at (Et - -5 (5t d.
1'" (1aa (E 1, (5E )ll))t
= log dy
(50
d²
20
dy dv
1
T
{' ((lar(E))12 (E))l
T
log
(Er)
(ar(E)) - by(E)), +dE,)
o²
202
To justify the last equality, if 5, 17 are two continuous stochastic processes, then by definition,
L (5T onl
Pr
lim
- Th -
Pr lim
(ET (5- -T- - -1-1-
[|T]|-
Pr lim
(: // - -1)-
||
1=0
['' (Ee, adn))
(16)
On the other hand,
S 5 dt dt {-" T fr-
[" Eidt.
Therefore, the equality of RN derivative holds. Plugging in & X, we have
dpx
du du (xx)+ = /-" (ar(X,)- b,(X,), =dB, BB + 202 / b(x)))
1
log
dpy (X) = log
To obtain the KL. divergence, it suffices to show the expectation of the second term is zero. Let
-1a))-bya M, M, = J. (a.((x))666xx)), br(X,), >dB,),
t [o,T].
By (16) we have
M M-=- =-
1/ (a (x,5 (x,
Since dXt = -aa + odB,, we conclude that M is a (forward) martingale, and thus M is backward martingale with E M, E MF_ O. 2. We present a formal proof by considering the process dZ, = adB; and Zu ~ X, the Lebesgue measure. As result, formally Z, ~ X for all so it can also be written dZ, odB; ZT X. The result follows by applying Lem. 1 to X and Z and 1. to Y and Z.
23

---

Published as a conference paper at ICLR 2026
A.2 OPTIMAL TRANSPORT: WASSERSTEIN GEOMETRY AND METRIC DERIVATIVE
We provide a concise overview of essential concepts in optimal transport (OT) that will be used in the paper. See standard textbooks (Villani 2003 2008 Ambrosio et al. 2008 2021 for details.
For two probability measures J4, on IRd with finite second-order moments (i.e., By || 112,1EE,, EE, || I1 < -00,, the Wasserstein-2 (W2) distance between μ and V/ is defined as W2(H,
inf m(a.))) [f ydz dy)) where [1(,,)) is the set of all couplings of (H.v). The Brenier's ss theorem states that when l has a Lebesgue density, then there exists unique coupling (id x xT j that reaches the infimum. Here, stands for the push- nush-forward of measure (deňned by (-)(-) = ı((w T(w) E .)), and Tn->v is known as the OT map from μ to v, which can be written the gradient of a convex function.
Given a vector field v = (ex (e))) and a curve probability measures p = (pt) with finite second-order moment on IR, we say that generates if the continuity equation V = 0, t E [a, holds in the weak sense. The metric derivative of p at E (a, b] is defined as
W2 W2 Pt)
lpl: := lim
[8]
which can be interpreted as the speed of this curve. We say P is absolutely continuous if lél exists and is finite for Lebesgue-a.e, E (a, b). The metric derivative and the continuity equation are related through the following fact (Ambrosio et al. [2008] Thm. 8.3.1 & Prop. 8.4.5):
Lemma 4. For an absolutely continuous curve of probability measures (Pe)sE(a,b), any vector field (v))) that generates (pe (Pe)sE(o,b) satisfies lple S ||vx ((Pe)) for Lebesgue-a.e. E [a, Moreover, there exists an a.s. unique vector field (vy E ((()))) that generates (pt)sEja,s) and satisfies
Tpl Toi-pe45 -ld
lple ||o7 ()))))))) for Lebesgue-a.e. t [a, b), which is of -iims-0
Finally, we define the action of an absolutely continuous curve of probability measures (p+)LE(a,M) as
Ie dr] which plays key role in characterizing the efficiency of curve for normalizing constant estimation. For basic properties of the action and its relation isoperimetric inequalities such as log-Sobolev and Poincaré inequalities (see definitions below), we refer the reader to Guo et al. (2025) Lem. 3 & Ex. 1).
Definition 3 (Isoperimetric inequalities). A probability measure π on Rd satisfies Poincaré in- equality (PI) with constant C, C-PI, for all f C (RR),
Var f E, ||
It satisfies a log-Sobolev inequality (LSI) with constant C, or C-LSI, if all 0 # f C (Rd).
f2
Ex fo
E, f2 S 2C |V
Furthermore, a-strong-log--oomavvit implies &
LLSI, and C-LSI implies C-PI Bakry et al. 2014).
B PSEUDO-CODES OF THE ALGORITHMS
See Algs.
and for the detailed implementation of the AIS and RDS algorithms, respectively.
C PROOFS FOR SEC.
C.1 A COMPLETE PROOF OF [HM.
Proof. By Girsanov's theorem Lem. 3) have
dP
To(Ev) (r(Er)
(' ((Vlog de) + (V log (Et) *dE.)).
log dlp
(E) log
2
We first prove the following result (Vargas et al. 2024 Eq. (15)): dz, = (x + Vdd, then
S'" (ae( adxx) = //" (ar(ar), dra) +2 tr (X))x.
24

---

Published as a conference paper at ICLR 2026
Algorithm 1: Normalizing constant estimation via AIS.
Input: The target distribution x e-V, smoothness parameter B, total time T: TI number of intermediate distributions K, annealing schedule Ag > >> Ax 0, number of particles N: AIS steps M, annealing schedule X(-) with X(0) 23, time points
0= 0g < < ONr = 1.
Output: Z, an estimation of Sn e V(x)dx.
Phase 1: estimate Zo via TI.
Define Vo + A1| 11 Pke :x exp (-Vo 1 11 113). and 9k exp (A / || 1P)). for
& [0, K 1]:
Initialize Zn - exp - (0)
2x
203+ 2(3++oo)
3,+
for k = to K do
(K) Obtain N i.i.d. approximate samples 21 .... N sampler);
(k)
from Pk (e.g., using LMC or proximal
Update Zo + NN En Zo:
end
// Phase 2: estimate Z via AIS.
Approximately sample zo from To (c.g., using LMC or proximal sampler); 10 Initialize W +- - (A(Og) ((6=))
11 for to 1 do
Sample independent & -0 (a,
13 Define A(I) So > (0 + t (0p 02-1)) dr, where Ty T(0; -0--):;
Update
If f ---e-Aci (ee-ATT))g--
-- (V(xe-1)+ (2 (-2(4(1))-
see Lem. 11 for the derivation.
Update W +W } (A(02) x00=1)))1=e13
end
17 return 2 = -
Proof. Due to (15) it suffices to calculate [a(X), By Itō's formula, we have
(x, = (0, + (Va, a (xx)) + (x;))) add
and hence
[a(X),X] 11, (2Va / v2dB,
tr L' 2V)((z
Therefore, for X P', we have
log d dip (X) = log (o(No) T (xT)) + /'''
+ A l,,g
On the other hand, by Ité's formula, we have
lo ग (X,) = 0 lo (X.) + (V 7 (X,). dx,) + A log (X)
Taking the integral, we immediately obtain (4) and the proof is complete.
C.2 PROOF OF HHM.
Proof. The proof builds on the techniques developed in Guo et al. (2025 Thm. 1), yet with new components including backward SDE and the corresponding version of the Girsanov's theorem.
25

---

Published as a conference paper at ICLR 2026
Algorithm 2: Normalizing constant estimation via RDS.
Input: The target distribution & e total time duration T, early stopping time 8 2 0, time points
to < l < ... < it
8; non-parametre score estimator
.,()) = V log (-) based {RDMC, RSDMC, ZODMC, or SNDMC) algorithms.
Output: Z, an estimation of Z f ee dr.
Sample X N (0, I), and initialize W
x2ll
log22;; 2T:;
for k 0 to N 1 do
Sample an independent pair of
E1 E2
~ N (o. (1)
011 where the correlation is Ph
1
and @ stands for the Kronecker product;
I/ this can be
211k11 (2) 1)(+=11-1))
done by sampling &1, E2
1.d.
~ N (0, 1) and setting &2 = pλEi + v RE5
Update Xtx11 < ela+1-le Xre 2(e - 14 (Xt,)) + Ve2(te)1-ta) 16i; see
Lem. for the derivation
Update W <- W (lx+1 - [T]] 112 2((+++ (x) (ST- (X Eo): see
Lem. for the derivation
end
Update W <- W ((ttn) - -T
return 7 -
We define IP as the path measure of the following SDE:
dx,
(V log मे + (X.)d + V2dB,, 1 E [0; Xo ~ no;
(17)
where the vector field (ei)ee r is chosen such that X2 ~ 7. under P for all t E T) According to the Fokker-Planne equation (v))LE(O,T] must satisfy the PDE
0, =
( log ग. + v:)) + Ar, V (Fr..), L [0,
which means that (2)) generates (F.)) The Nelson's 's relation Lem. 2 implies an equivalent definition of IP the path measure of the following backward SDE with an independent time-reversed BM (B, )
dx. (- V log + (x))d + 22d LE [0, T) Xr नr.
Now bound the probability of relative error:
7
e-w
-
Pr
Z
E
p
c
AF
2 =
dP 26
1
dpt
2 TV(P= ,P+)
Ep-
8
dF
&
2
(TV +V(P,
22 (VKI /KL(PIIP-))
(18)
In the second line above, we apply Markov inequality along with equivalent definition of the TV de
distance: TV v) = 1 ʃ aA dx dA, where À is a measure that dominates both μ and v. The third line follows from the triangle inequality for TV distance, while the final line is consequence of Pinsker's inequality KL 2 2
We assume the existence of unique curve of probability measures solving the Fokker-Planck equation given the drift and diffusion terms, guaranteed under mild regularity conditions (L.c Hris & Lions] 2008).
26

---

Published as a conference paper at ICLR 2026
By Girsanov's theorem Lemss.
andd B).
it straightforward that
KT((P)PP*> KL((PIPT)) Ep /"
1 4
(x,)
|1 (a)) dr.
Leveraging the relation between metric derivative and continuity equation (Lem. 4). among all vector
fields (v+)tE(o.T] that generate (Te))e(o,T)) we can choose the one that minimizes | [ulll thereby
making [ |// the metric derivative. With the reparameterization
Ft/T, have
the following relation by chain rule:
W2(T Te)
W2( M1/H)) 1 T #l/rr.
lim 6-+
lim 8-50
[8]
T/8/T|
Employing the change-of- variiabll formula leads to
A
KL(PIIF")) KL(PIPP
P.P. 47 + 11000
47
Therefore, suffices to choose T 32A to make the r.h.s. of (18) less than 1
D PROOF OF THM. 4
With the forward and backward path measures P- and p defined in (5) and (6) we further define the reference path measure
M II
P(OO.)) = (x0)
F7 (IC-1,
(19)
where Fj can be an arbitrary transition kernel transporting _o.-, to nB ie., satisfies
ne, (1) = / (x, ( Vy E Rd = xs ~ Tee Vl [].
Define the backward transition kernel of F7
By (1r, T8,_, (x')
(a', .)), l [1,M],
To, (x)
which transports no, to no,-,- Equivalently,
write
M
B (1,, 12-1) P(ra.)) = (x II
t=1
Straightforward calculations yield
M
KL(PIP
E ET (me-1) (L)-F((20-1))))
KL(PP PT
E (xr)) KL,(B Be((zt,
M
KL( (F+- (at
(20)
M
KL + KL KL(
(21)
Also, recall that the sampling path measure po- defined in (9) starts at u. the distribution of an approximate sample of To. For convenience, we define the following path measure, which differs from - only from the initial distribution:
M
(ru.as)) = To(2o) II
(22)
8=1
27

---

Published as a conference paper at ICLR 2026
Equipped with these definitions, we first prove lemma about necessary condition for the estimator
7 to satisfy the desired accuracy (1)
Lemma 5. Define the estimator 2 Zoc W(ma.s)) where To:M ~ , and Zo is independent of
E.:M. To make Z satisfy the criterion (1)
it suffices to meet the following four conditions:
%
e
Pr
2
(23)
Zo
8
8
TV (mo To) x 1,
(24)
(L(PI|P S =
(25)
[PP S 1.
(26)
Proof. Recall that Z
Zoe AF, Using Lem.
we have
2
Zo
Pr
1
2
1 Pr
log
2
Pr xou
log
+ +log
2
Z
Z
Zu
e e-AF
2
20
log e W
< Pr
log
2
8
+ -
Zo
4
e e-AF AF
e W
$ Pr
Zu
1
+ P
- e
c
AF
2
The first term is < the triangle inequality, we have
if (23) holds. To bound the second term, using the definition of TV distance and
(
e W
E
P-AF
8
(1
W
< TV PP) + p-
(
dF dP-
STV
TVPP" ,P) TV(P,P")+P
Recall that by definition (9) and (22)
the distributions of TT:M conditional on Ty are the same under
-- and p.. Hence, TV(P- P
TV To). Applying Pinsker's inequality and leveraging
(88 we have
e OF
8
P + /KL(P KL(P|P-)) + [K[(P] P+
$ TV To)
Note that from (21) we know that KL(PI|P") < KL so (24) to (26) small enough absolute constants,
hold up to some and therefore
achieve श
oF
Pr 1
Remark 6. As the TV distance is always upper bounded by 1, one in fact write (24) more precise way: TV To) < 2-5, (II(P) < 232 and (L[PP] <
(26) in
Next, we study how to satisfy the conditions (25) and (26) while minimizing oracle complexity. Given that we already have an approximate sample from mo and an accurate estimate of Zo. we proceed to the next step of the AIS algorithm. Since each transition kernel requires one call to the oracle of VV, and by plugging in fe +- V + x(0) ||- 1 in AIS (Thm. 3), the work function W W(zu.M) is independent of V, it follows that the remaining oracle complexity is M. The result is formalized in the following lemma.
28

---

Published as a conference paper at ICLR 2026
Lemma 6. To minimize the oracle complexity, it suffices to find the minimal M such that there exists a sequence 0 = Bu < 01 <
< 0M satisfying the following three constraints:
M
81
6
(A(0) - A(0=)) S
(27)
m².
E
Σ (0 0c-1)²
(28)
A3
E²
max EE[L,
(Or 08-1) 2
(29)
3A
Proof. We break down the argument into two steps.
Step 1. We first consider (25)
Note that when defining the reference path measure IP, the only requirement for the transition kernel Fi is that it should transport TT to T&. Our aim is to find the "optimal" FŽ's 's in order to minimize the sum of KL divergences, which can be viewed static Schrödinger bridge problem (Léonard 2014 Chen et al. 2016 202I). By data- inequality,
C₁ : inf KL(TT, (Z (x2-1, #x)] no, (ve-
S inf (LPPP((Q')) p
where the infimum is taken among all path measures from 0 to Tp with the marginal constraints P/J = - and Pf, Te,; Q' is the path measure of (8) (i.e., LD with target distribution тT, initialized at Xo TT
For each & E [1, M], define the following interpolation between _ and no,
1 = 700-10 + (0. 02-1)) L 70.
Let P be the path measure of ax, (V log (X,)dt + V2dB, t E [0, Tel: No ~ T8--1
where the vector field (uf)eeoo,r)) is chosen such that Xt uy under Pt, and in particular, the marginal distributions at 0 and T' are Tb._, and Toe. respectively. By verifying the Fokker-Plance equation, the following PDE needs to be satisfied:
0.1 - (V log + ut)) + Auf - -v -v-fu() L [e).
meaning that (uf) generates (4f) Similar to the proof of JE Thm. 2). using the relation
between metric derivative and continuity equation (Lm. 4), among all vector fields generating (pt (pi)eeoorTa) we choose (uî (uf)) to be the a.s. a.s.-umique vector field that satisfies || = j for Lebesgue-a.. & [0, Tt). which implies (using the chain rule)
h/ llu Tu (i = S/d
To litt
To 02-1 | | 1 + (9c- (o--0 )² di 1-" (0--p=
2
02 - o2-1
1%) 1=/3000.
Or
Tt
By Lem. we can equivalently write Pc as the path measure of the following backward SDE:
dX, (-V log of + (X,)dt + V2dB.. E [o] XT mea
Recall that Q is the path measure of (8) initialized at Xo Te so X, ~ Te, for all E [0, T2. By Nelson's relation [Lem. 2b. we can equivalently write Q' as the path measure of
dX.- -V no, (X.)dI V2dB, E [0, Tel; Xr, 5u
29

---

Published as a conference paper at ICLR 2026
The purpose of writing these two path measures in the way of backward SDEs is to avoid the extra term of the KL divergence between the initialization distributions Te,-, and Te, at time when calculating ( To see this, by Girsanov's s theorem Lem. 3). the triangle inequality, and the Change-of-variable formula, we have
1
14 dt
Ce & KL
Q4))
u
V log
4
(P(N))
|
(2(tt)
dt
log
M4
Te
(P(H))
02 Oe-1
01
T
9,
| a0
V log
d0. 0e (m)))
Te
J0
02
02
D--1
Remark 7. Our bound above is based on a specific interpolation between To and no, along the curve (T0) This approach is inspired by, yet slightly differs from, Conforti & Tamanini (2027) Theorem 1.6), where the interpolation is based on the Wasserstein geodesic. As we will demonstrate shortly, our formulation simplifies the analysis the second term (the Fisher divergence). making it more straightforvard to bound.
Now, summing over all E [1, M]. we can see that order to ensure KL(PIIP")) S EM Ce S E2, only need the following two conditions to hold:
M
0,
O2
| 2d0 < s²
(30)
Te
E=1
M
Σ
Ti
log
TB
d0 5 6².
(31)
02
O2
1--1
T00
117(00))
Since Σ Ex=1 1 |+Bd0 = A, it suffices choose
Te
A
0, 0,-1 = T vl E [1. M]
(32)
to make the lh..s of (30)
(s²2. Notably, T is the summation over all Tr's, which has the same order the total time T for running JE (2) in the continuous scenario, in Thm. I Plugging this T2 into the second summation, and noticing that by (7) and Lem. 14]
log W
Eynnn (I((()) x(0'))= (X(0) -x(0')²mm²
we conclude that (27) implies (31)
Step 2.
Now consider the other constraint (26) By chain rule and data- titta-prccesinn inequality,
M
KL(P|[F")>
< KL(P'IQ')
where p6 is the previously defined path measure of the SDE
dx; = log +
+ V2dB,
(0: 1)-)) X. + ux(x)) dt+ V2dB,, E Te): Xo no.-17
VV(X)) > 02-1+ T₁
and Qf is the path measure of (10) initialized at Xo To.,,, ie.
dx, = (VVV(X)) - - 2> -1(0 L (O) 01-1) Xx dt + V2dBi, t (0,Te)] Xo no.-1-
Ti
30

---

Published as a conference paper at ICLR 2026
By Lem.1
triangle inequality, and the smoothness of V, we have
KI.(P")Q'))
Epc IVV((X)) - VV(X)) - uf(x))l
T2
Epr
[IVV VV(x6)11 + |lu dt
Epe |X, Xoll2de + /-' [
S 82
To bound the first part, note that under P we have
X, - Xo / (VVlog log + (x)(X,)dr + vēB.
Thanks to the fact that X 1b, under Pe.
Ep ||x, - Xoll² x Ep 1 (Vlogg + (x-)) +BI12B.11
2 1 / Epr |(V log + + (xx())) dt
$ 1 / Iog ((( + ll (12 dr + di
T $ Te /"' (IV 1f I|u, (B= dr dTe, Vi [0, Tr].
where the second inequality follows from Jensen's inequality (Cheng al. 2018 Sec. 4):
11. S
12 Unitto)) fz11 s 12 B.-unitoo |1/ = L |5 dr.
Therefore,
KL(P*1Q1 )
/ Te
Epr ||, - xoll + (" (t) I
$ 82
< T /. ("'
[IV of (12) (BºT²) +1)+11///1 1" || 1uf + d32T?
1 To 1% 91
O2 08-1
(
|V log To ( d0 (321? 1)
1+Bd0 + d321?
02-1 so
Te
Je.
Recall that the potential of Ty is (8 X(0)) smooth. By Lem. 13 and the monotonicity of X(-).
V log Toll T do <
d(B + x()))d0 d(O, 0x-1) + X(Ge-1)).
8
0,-1
Thus,
M
0g - 0 (+:
KL P
P
<
+1) 8 (x) +
|2 + d
Tí
Pt-1
F=1
0:-1
yt
X (T) +1) (87T7 +1)
|
31

---

Published as a conference paper at ICLR 2026
Assume m [M. Te - 3. i.e. (29) can further simplify the above expression to
m [I, Te(B A(Be-1)) 2 1, due X(1) S 23. We
01 - - f"t
KL
Bdl?
|
SBd
Σ T
t
Tt
8=1
81-1
/=1
M
A2 M
= 3 2T
Σ t=1
(02 - 0;-1)² + 8² 2
32
Σ
00 02-1) +E²
g8
So (29) implies that the r.h.s. of the above equation is O().
Finally, we have arrived at the last step of proving Thm. 4 that is to decide the schedule of 0g 's
Define 02 1 0e & E M]. We consider the annealing schedule x(0) 2 - 8Y" for some 1 S r $ 1, and to emphasize the dependence on r, we use A, to represent the action of (To [00)00) The lh..s. of (27) is
Pc (A(0) x(0=)) <
Σ
(02 (28)(1000-11)) --001-81---------11000707---- -3)1-0))
f=1
(0-1 (2,02 2,30722
M
S 8
(ie-1 - 01) 07)2
M
8
(U 0
B²
(0 0z)3
> 8=1
where the last inequality comes from
Lem. 9 So to satisfy (27) it suffices to ensure
M
(0) (0--1- 0z)² 0z) Σ
m2 2 A
t=1
while (28) and (29) are equivalent to
M
E²
(1)1 2 d3
(0z-1- -0))--0)) ()){ S EE[LM
max
BA,
Since we are minimizing the total number of oracle calls M, the Hölder's inequality implies that the optimal schedule of 0z's 's is arithmetic sequence, i.e., the 1 M
We need to ensure
1
22
M
m2
B
AP
M
So it suffices to choose
1
A
which implies the oracle complexity
mBA.
m3AF M
d3
2²
g4
A
and the hyperparameter Te is thus Tg
according to (32)
A,
Remark 8. The work Guo et al. 2025 used similar methodologies to prove Ō
A/ oracle
complexity for obtaining sample that is e-close in KI. divergence to the target distribution. While
32

---

Published as a conference paper at ICLR 2026
assumptions mostly the same with Guo al. (2025) except for some insignificant technical ones, and both proofs involve the standard discretization analysis through Girsanov's theorem, the improvement of the e-dependency in Thm. 4 is due the fact that Guo al. (2023) requires
KL(PIIP S e² for sampling, which results in a ((=") step size in Guo al. (2025), while our proof
only needs (L(PI I and (L(PI|P*)) S =² for normalizing constant estimation, resulting in an improved (s²2) step size.
E PROOFS FOR SEC. 5
E. PROOF OF PROP.
Proof. The claim of smoothness follows from Guo et al. 2025 Lem. 7). A similar approach for
proving the lower bound of metric derivative was used independently Chemseddine al. (2025 App. B).
Throughout this proof, let ó and & denote the p.d.f. and c.d.f. of the standard normal distribution N (0, 1), respectively. Unless otherwise specified, the integration ranges are assumed to be (-o0, oo).
Note that
T <xr)
22 f0² x le
te
(x-m)2
e $2²
2m3
2 (x- 241 )²
2(++I
Am?
(
x x
1
e
2(++1)
Am? N {
(x
1
N
x
+ e
1te IJ
Define S(0) I+m=[1 1 0yr and let
[x) :0 (2) 1/- ((s) + -w(s)) (alssm, 8),
where
e (1 smmm 12m²² 2 /2 (1 + (1 x)m=m 12)2
w(s) 1 e (1 (1- 5m
w'(s)
By definition, IS(0)- The p.d.f. of
I. If is
fa(z) = w(s) ④
x
1 w(s)
1 sm
[8
and the c.d.f. of I, is
I + +(1
w()))
I sm
V
We now derive a formula for calculating the metric derivative. From Villani 2003 Thm. 2.18), W2(,, f. (z) F. 2 where Fu, Fb stand for the c.d.fss of μ. Assuming regularity conditions hold, we have
Io45)
F Fotb(o) (v) dy =
[' (0,F, .0
lim 8-+0
lim 8 8-40
82
Consider change of variable y Fs(x), then dy fa(x). As x Fg), (F-1)(y))
dx dy
dr
1
Taking the derivative of s on both sides of the equation (F,((x)) yields
F.(zJ.
1 O. O.F.(x).
0 0 O. O= (F, ((EG)))) 0,F, + fx(x)
33

---

Published as a conference paper at ICLR 2026
Therefore,
J. (v)) = / (o.Fela) f.(r)d== = / (0, (0,F2(x)) dx.
fz(
fz(z)
Consider the interval x E 2
0.1, mh + +.1]] and fix the range of to be [0.9, 0.99). We have
w(s) 1+
Vm 2 1
(1-44)m+y21
-(--))m² m2
w'(s)
Vm Vm21 1
-ifflt-jmm samt-/mmm/pp 1232
et -jm
First consider upper bounding (a)). We have the following two bounds:
((s)
(m/220.1)2 2x0.99
Se
Vm 2
8
1 n0())
8m x
(am=a)² 2x
1
(sm - x)²
+ (1 s)m² s)m²)
e (115)m²² =2
exp
2
The term in the square brackets above is
(sm - x²)
+ (1 ssmm²=
2
1
8m
m
0.1
2
+ (1 s)m?
8
2
m
1
0.01
0.2
m +
4s
2s
m
m 2
0.1m
0.1 2
Vm 2 1.
4 0.99
Hence, we conclude that fz) S Next, we consider lower bounding the term (z)F) Note that
8
-0,F,(z) ww((s)
②
x
+
Σ 8m
V
x
I sm
x
m
+ ws)
+
(1 -
w (s))
+
2s
25
28
As [m 0.1, ~ 0.1 and s [0.9, 0.99), all these three terms are positive, We only focus on the first term. Note the following two bounds:
0.1 -01) 2 3
Vm ž 1
R77L V
<
Φb
m/240.1 1-am V
< +b + 0.1) < 5 Vm 2 1.
Therefore, we have
2
O,Fs(z) 2
e
(1=
To summarize, we derive the following lower bound on the metric derivative:
(0)F.(x))
+001
(0.F,(x))
|+
dr
dr
fz(z)
fa(x)
-011
+0.1
m te m (1-s)m²
e e da
m1 0.11
2 m e 3)m²
2 m m² 20
Vs E [0.9. 0.99..
Finally, recall that S(0) = (1-0rr and To = s( Hence, by chain rule of derivative, |i| = | (0)) Let
1/0.99 - 1 17 m²
1/0.9-10 - ,1
θ = 10 E [0 S(0) E [0.9,0.99]] =
m
34

---

Published as a conference paper at ICLR 2026
We have
A, L 1
/
1 s
(0))
|
(0)
20
0.99
min E
(0) | (0))
min 80
[s(
0o.9
For any 0 O,
m²r (1/0.99-1 m
1-1/r
m²r(1 - 0) [S'(0) = (1 0)))2
m 3/1 (0119999)))-////
1-1-
2 2/r 2 1,
1
+ m2
[1/09-1]
(1/0.9)2
1-
where in the first "2" we used the inequality proof is complete.
that holds for all r 2 1. Thus, the
99
Remark 9. In the above theorem, established exponential lower bound on the metric derivative of the W2 distance, given by limæ_ Eata) In OT, another useful distance, the Wasserstein-1 [o|
(W,) distance, defined as WI(H,v) inf || - (dz, dy), is lower bound of the Wz distance. Below, we present surprising result regarding the metric derivative of W distance on the same curve of probability distributions. This result reveals an exponentially large gap between the W and W2 metric derivatives on the same curve, which is of independent interest.
Theorem 6. Define the probability distributions Is as in the proof of Prop. for some large enough m Z 1. Then, for all E [0.9, 0.99), we have
W1 [I Io45)
lim
S 1.
Proof. Since Wi v)= / [x) Fa(r)ddr Viillani 2003 Thm. 2.18), by assuming regularity
conditions, we have
W1 (H,, To+8)
lim 6-0
10.Fa(x))do
0
$ / w/ (8)
x sm
dr
V
/
(0))
x
dx
Vs)
/ (1 w()))
x
sm
m
dæ.
8
28
28
To bound the first term, notice that for any > 0,
2
sme
2 X;
x
sm
V8
+
8
/mmc 27
< ->;
otherwise.
(()) < g x² the first term is bounded by
Therefore, using Gaussian tail bound
m2
12vs> sm + sm (A)) + (-
cl 3/ 1
m²
2 (m
m
A + m
+
e(l-o)m772 = o(1).
e(1-2)m212
35

---

Published as a conference paper at ICLR 2026
The second term is bounded by Finally, the third term is bounded by
/
Φ
x
lx|da = 8 (W)lullu $ 1.
vs
1 e 32m²
I - sm Φ
V8 (-)
(|x) + m)dr
((w)((u) + ma)d x ell e(1-s)m²/2 = o(1).
m
ell el1-s)m²12
E.2 PROOF OF PROP.
Proof. We first prove a more general result with á being any distribution with weak regularity condition, and then focus on the special case where & N (0, 7).
Note that the LD with target distribution Φ,
dY, = log (Y,)dl + V2dB,, Y, ~ Tt,
can be perceived as the Wasserstein gradient flow of KT.(-Il)). H, satisfies the Fokker-Planck equation
log Tr / Hence, the vector field (12 == - - log En rE(0,00)
0,5, = V ह V
generates ( (e)
and each tú be written gradient field of potential function. Thus, by the uniqueness result in Leme 4] we conclude that
1
V
log
T
(l = - 0, KL(F.l)o
Fldt = (L(T])
(2(0)))))
where Fl is the Fisher divergence.
For the special case where & = N (0, 1). using the log-Sobolev equality (Def. 3 the smoothness of V. and Lem. 13 we can further bound the KL divergence follows:
1
(L(T|))) 2
FI(=]())
Ex(x) (v + x|| s E. IVVI E. 112 s d3 m
E.3 PROOF OF TIM. 5
Proof. By Nelson's 's relation Lem. 2 Q equivalent to the path measure of the following SDE:
dx,- = X,dt + v 22B, t E [0, T - 8); Xx ~ nz-
Leveraging Girsanov's theorem Lem. 3), know that for X Q!:
log dQ' aQ
((Xo)
1 T-88 ((x, 28T (X, (x,)), - (X,, xdX,)
(X) log
T& (XT 8)
2 2
1 T-
(I + 28T (X, (ipp-IIxpp (|x,| dt.
4 /
Note that for X Qt, J T- (X,, xxx,) -o (x,, ,x,) X and XXXXT=>
[v2B, 22 r- = 2(T 8)d. Some simple calculations yield
d@t
((X,)
(T - 5jd L-' T-
log
(X) = log
(1 v2 (X
dQ
3 (XT-
= log & + ((X) + log di
(Xr-s).
d
36

---

Published as a conference paper at ICLR 2026
Thus, the equation Eg aQ
dQ 1 implies
Z (x) W(X) d
(Xr-s) v Rot(x) e w(() = R
dm
Since
2
dQ
(X)
(Xr-8), we have
x = aQ
dig
2
= Prx-Q1 (1
dQ aQQ
dm
Pr
2
(X)
(XT -6) - -2 28)
dTts
dQ
dm d
< Prx-Qt
(X) - 1 _3 + Prxp0t
(XT - _
dQQ
The inequality is due to the fact that lab 1 2 implies |a 1| or
1 1-
for [0, 1]. It
suffices to make both terms above (1)). To bound the first term, we use the similar approach as in the proof of (18) in Thm.
(1
26 20)= 22) =Q¹
dQ a (X)
[100
T)(Q.Q) VLLQQIQ)
Prx-er
2
aor
Hence, it suffices to let (V Q1) & KL(QIQQ) S². To bound the second term, we have
d Prxwar (1 (XT-o) -1 26) $ Pix~o ( | (|drr (XT-8) -1 1| 22) + +TV(Q.Q')
dm
x + +TV(Q.Q)
T38
dmo
TV (T
+
8
Therefore, it suffices to make TV T) Se.
E.4 AN UPPER BOUND OF THE TV DISTANCE ALONG THE OU PROCESS
Lemma Assume that the target distribution a ix eV satisfies scttsfies/Assump 2) Let Ta be the distribution of Y8 in the OU process (12) initialized at Yo n, for some ō S 1. Then,
TV(2, S 5(3m² + d + 3d) + dd Bm.
Remark 10. Consider a simplified case where 2 and m² d. Then it suffices to choose
S Fal in order to guarantee [VT Se.
Proof. Our proof is inspired by Lee al. 2023 Lem. 6.4), which addresses the case where V is Lipschitz.
Without loss of generality, suppose v Let o be the p.d.f. of (0, I), and define o² 26 x 6. We will use the following inequality: lee - eb < (e + ea)la bl. which is due to the
1 1- 26
convexity of the exponential function. By the smoothness of V. [VV = [[VV(=) VV)) < |||z|||
Define <xxx) edo (efxx) and thus (x) ff <' ou)o(u)du. Using triangle inequality, we bound TV R') and [V's,, RTs) separately. First,
TV(T, 2
(o-v()) - v(e'=)+
-
5 + ( V(x)) dr.
37

---

Published as a conference paper at ICLR 2026
By the smoothness,
+ 8 2(0² -c- 1)
-(ce))-((xx))
2
|| + | 2 1
= TV(", 8 (अ( X (3)) + d)dr.
Note that f (x) + d)dr 3m3 + d. Since E, 4 En sple -eeo..)), )),, we also have
/ <x)) + d)dr e- Bm + d - 3m3 + d.
We thus conclude that
( +d).
Next,
TV m8) - 2 / /
dz
25 // -
2 // (1 - v) (ouu)dddd..
Again, by smoothness,
((e'(x - V(62x) < [V |u|| + 20 |u1l
3
2
x 3 |ul||| ||ul| + 30
$ || + 381|u|1?
Therefore,
TV ,.) S 36
[|<T(o= ou) + (+)[||=]] of (f
Note that, first,
lʃ n' [<)(a(([llll]|]| + + $ Ex || ||d +8d I mdt + 8+d;
second,
|| <'xx + (10]lllal (
/ʃ < oull 5 |||| ) (u)dudy
$ /f <(00ll]lll + 0² ull ) ) duddy S mad + 5 d.
Therefore, TV(T', S d (m + d...). The proof is complete.
E.5 DISCUSSION ON THE OVERALL COMPLEXITY OF RDS
In RDS, accurate score estimate V log नं is critical for the algorithmic efficiency. Existing methods estimate scores through different ways. Here, we review the existing methods and their complexity guarantees for sampling, and leverage Thm. 5)to derive the complexity of normalizing constant estimation. Throughout this section, we always assume that the target distribution и oc satisfies m² = E, || l| co and that V is 3-smooth.
38

---

Published as a conference paper at ICLR 2026
(I) Reverse diffusion Monte Carlo.
The seminal work directly leveraged the following Tweedie's
formula (Robbins
1992) to estimate the score:
V log (x) (xol2))
(33)
1 - e
where
1100 - e'2011² 2( - 1)
(o)(()) Xao exp - -V(xx))
(34)
the posterior distribution of Yo conditional on Y; to sample from a LMC and estimate the score via empirical mean, which has provably
the OU process (12) The paper proposed
better LSI constant than the target distribution л (see Huang et al. (2024a) Lem. 2)). They show
that if the scores V log म uniformly 3-Lipschitz. and assume that there exists some >> 0 and
c n > such that for any r > 0, V + r|| I|2 is convex for ||>||| 2 p.r then w.p. 2 Ç. the overall complexity for guaranteeing ( S is is
O(z)
o poly (a.2) exp
1
which is also the complexity of obtaining Z satisfying (1)
(II) Recursive score diffusion- Monte Carlo. A second work Huang al. (2024b) proposed to estimate the scores in a recursive scheme. Assuming the scores V log H. are uniformly B-Liscchit they established complexity
g log poly (,d, m² '))
cxp
in order guarantee (L((I)Q") S w.p. -
(III) Zeroth-order diffusion Monte Carlo. The following work He et al. (2024) proposed zeroth-order method that leverages rejection sampling sample from (-)))) When V 8- smooth, they showed that with small early stopping time 8, the overall complexity for guaranteeing KL((Q|Q()) e²
exp (o(d) log 3 log &
(IV) Self-normalized estimator. scores in a different approach:
Finally, recent work Vacher et al. (2025) proposed to estimate
1
El ((e((x-))) {)) Ele- (1o
V log (x(x)=
where & ~ N (1-
Assume that V is 8-smooth, and the distributions along the OU process starting from e-V and n' x e e2 have potentials whose Hessians are uniformly 2 -BI, then the complexity for guaranteeing E (
3(m v d) Old)
F SUPPLEMENTARY LEMMAS
Lemma 8. For x > 0 and E (0, 2), define zo := log x| and 21 := |x - 1). Then x; 2 implies -1-1 5, and I, implies T1 S 2s, for both 0.
This follows from the standard calculus approximation log 2 x - when so 1. The proof is straightforward and left as exercise for the reader.
Lemma 9. For any b < and r 2 1, b' a" S r(b a).
39

---

Published as a conference paper at ICLR 2026
Proof. This is immediate from the decreasing property of the function (p(x) == x² r2, [0, 11.
since of (x) = -r(x"=1 11 - 1) Σ O.
Lemma 10 (The median trick (Jerrum et al. 1986)). Let Zi,... ZN be N(2 3) ii.d random variables satisfying
Zn
3
Pr
8
Vn [1, 2
and let Z. be the median of Zi.... ZN. Then
7,
Pr
1 E
2 1 c
Z
In particular, for any < (0, 2 choosing N = 72log { the probability is at least 1 1-5.
Proof. Let An = 1122 2 - 1 > E). which are iid. events happening w.p. p S
4 If
2
1
2
then there are at least
2 An, 's happening, i.e., SN == Σn 1A, 2 [/1 Then,
N 2
N 2
Pr
>
< Pr
SN z
Pr
8N -y--SS
p.V
Z
< Pr SN - E ESN N
N
I #
12
where the first inequality on the second line follows from the fact that N 2 3, and the last inequality is due to the Hoeffding's ss inequality.
2
N-1
for all
2
3
Lemma 11. The update rule of ( is:
(1,6 T' e --(ACT)-A(00)
VV(X))+ + (2) Tt --21a00)-((111d)) 2 /2/"
7/
XT, = A(T))
E,
where A(I) - So 1000111 7,(0 -e--eee) dr, and ~ N (0, is independent of Xo-
Proof. By ItO's formula, we have d(oA())x; X.) = (0)) (d'())x,d) + = (-VV)((()))) 22)
Integrating overt E [0, Te). we obtain
((TT) XT. XT. Xo - (1% T3 eswodat VV(Xx) + V2 1"r edWld...
ju
= Xr. = - - (1, e --(M(T)) MODAL VV(Xo) + V2 1'' To
e (A((()))AA()
and 2 10 e (ACTA)-A()) ~ N (0. (2.5%* e -(21 1) by Itō isometry.
Lemma 12. The update rule of the RDS [14] is
Xtat1 1 Xx, + 2(0 - 1) (Xtx) Ek,
where
Ex== [( 1++1 V20- (t-tee ~ N (o2 1)7)
and the correlation matrix between Eg and Bexts Big is
(5(c -1) I.
Corr(E Bi Bi.)= ((22(te11-44) 1)(t - tx)
40

---

Published as a conference paper at ICLR 2026
Proof. By applying Itô's formula to (14) for t [tt, tx+1], we have
=
+ dx,)) =
)dt +V 2v2d))
1 ddB.
buti
= e e- Xtut1 - e th Xt, = 2(e - e SST (X(,))
Big is The covariance between two zero-mean Gaussian random variables En and Bie
Cov(E,, Bizti Bd,) (B -Be)"]
(1rmm dB:
T
V2e (2e-0d-
= E
dat1
11- I=
I= v2((e - -II..
Finally, Corr(u, v) = diag Cov u) Cov(u, v) (ovagCCv yields the correlation.
Lemma 13 (Chewi 2022 Lemma 4.E.1)). Consider probubility measure μ e on Rd
V č aT for some a > 0 and x. is the global minimizer U, then Eyg || -xx 1|2 S a.
If V 3 BI for some > O, then E, /UII? S Bd.
Lemma 14. Define x x exp (-V 211 113) X2 0. Then under Assump. 2 Ea, |l 11 S m² for all X 2 O.
Proof. Let Vx == V |1 31|-110 112, and ZA= ʃ -Vide, so 7A
- -Vo- 2x, We have
Vv
d
7,4
/ Vi
1
log Zy =
2 Exg 11.11?
yp
d
d
1
log TT
-V-
log Z>
(Bra 11 - |1 11-11))
Yp
yd
2
d
E3 ||- 112=
||
1|2
d
log A
(EEs || 11-113)2 Ex l1 11-11)) So.
yd
G REVIEW AND DISCUSSION ON THE ERROR GUARANTEE
G.1 LITERATURE REVIEW OF EXISTING BOUNDS
Estimation of Z. Traditionally, the statistical properties of an estimator are typically analyzed through its bias and variance. However, deriving closed-form expressions of the variance of and F in JE remains challenging. Recall that the estimator 2 = (iee-(()) X IP+ for 2 Zye AF and that JE implies Bias 2 0. For general (sub-optimally) controlled SDEs, Hartmann & Richter (024) established both upper and lower bounds of the relative error of the importance sampling estimator, yet bounds tailored for JE are not well-studied. Inspired by this, we establish an upper
bound on the normalized variance Var 2 in Prop. 3 at the end of this section using techniques in Rényi divergence. However, we remark that connecting this upper bound the properties of the curve (c.g., action) is non-trivial, which we leave for future work.
Estimation of F. Turning the estimator F -log Z for F = log 7, we have
Bias F = Ep- W AF = W A Waiss-
Bounding the average dissipated work Waiss KL((P P mains challenging as well, as the law of X, under P is unknown, thus complicatngg the bounding of the expectation. To the best of our knowledge, Chen et al. (2020) established lower bound in terms
Ep- f (Ō, log क, (X,) re-
41

---

Published as a conference paper at ICLR 2026
of WT Ti) via the Wasserstein gradient flow, but upper bound remains elusive. Furthermore, 12 Ep (x) (log Zo- (X)) 2 is similarly intractable to analyze.
For multiple estimators, i.e., Fx log Zo 1 M Σx= ((X(()) where X X(),..., ((K iid P.,
Zuckerman & Woolf 2002 2004 (see also Lelièvre et al. (2010 Sec. 4.1.5)) derived approximate asymptotic bounds Bias Fx and Var Fix via the delta method (or equivalently, the central limit theorem and Taylor expansions). Precise and non-asymptotic bounds remain elusive to date.
G.2 EQUIVALENCE IN COMPLEXITIES FOR ESTIMATING Z AND F
We prove the claim in Rmk. that estimating Z with Oe)) relative error and estimating F with (s) absolute error share the same complexity up to absolute constants. This follows directly from Lem. 8 for any E E (0. 2
Pr (IE-FE
2
3 and
Pr
F
FI
S
2 3
2 4
G.3
1 WEAKER THAN BIAS AND VARIANCE
We demonstrate that is weaker criterion than controlling bias and variance, which is an immediate result from the Chebyshev inequality:
2
2
Bias² 5 Var Z
Pr
14
1
Z
Z
5²
B(F
F)2
Bias F + Var F
Pr f
F1
82
On the other hand, suppose one has established bound in the following form:
2
Pr
2E SPlE),
for some p [0, oc) [0, 1],
and assume that 2 is unbiased. Then this implies
2
2 E
2
2
2 28 de S ( pl p(VE)de.
Var
1
Pr
7
G.4 AN UPPER BOUND THE NORMALIZED VARIANCE OF Ž IN JARZYNSKI EQUALITY
Proposition 3. Under the setting of JE (Thm. TV. let (Ne)eEjoTT) be any vector field that generates (T.)eEjo.T), and define P as the path measure of (17). Then.
2 < Var
Ep exp 14 ' [[,( ) -1.
Proof. The proof is inspired by Chewi et al. (002h). Note that
2
1 = Ep- (e (e- (-W(X)+AF)2 2 -1 Ep-+
dd+ dp- - 1,
Var =
7
7
which is the x2 divergence from P- p Recall the <(> R)-Rényi divergence defined as
(u(l)) - log E,, du and that x² (P IP~) R2 (PP)) 1. By the weak triangle
inequality of Rényi divergence (Chwi 2022 Lem. 6.2.5):
(P | < 2
( PP) + Rg PP
42

---

Published as a conference paper at ICLR 2026
We now bound Ep
dP dP
for any R. By Girsanov's theorem Lem.
dIP
(X) = /'"
(- V2
(or (x,) dB.) 1
(l.((X)))F()) a.s. ~ P.
log
dp
Therefore,
dP
Ep
dP
7 (lx
Ep cxp
V2
= Ep exp
-o² (-
q
(mr(X))
dBB)
d²
(1.)(
+ // (o² - [la(x))))aa
T
V2
2
P - (-v2g
<
Er exp
- o ((
(v--g) 9) [1a((xx)))) (xlxx()))aaaa)
Ep exp
where the last line is by the Cauchy- Cauchy-Schwarz inequality, Let M, := -V2g So (u,, dB,), be continuous martingale with quadratic variation [M]; ft 2 (x,)) (x.) By Karatzas
& Shreve 1991 Chap. 3.5.D), the process + e is super martingale, and hence E Ee M| < L. Thus, have
dF dP
9
(0- 2) L. Il,, ll,,
Ep
Ep Exp exp
From Girsanov's 's theorem (Lem. 3), we can similarly obtain the following RN derivative:
dp
(- 1 (e, (X,) (x.X))))BB 11 (x.)
log
a.s. X
dP
and use the same argument show that Ep (d has exactly the same upper bound Ep (PP))² ) In particular, we can use the same martingale argument, whereas now the backward continuous martingale is defined M/ == -v2g Se" (x,),,,, *dB;", X P. with quadratic variation [M''; = J:" 2q 11, (X,,) Therefore, we conclude that
14 %/' [lve(X.))
+ log E& exp 5 (3)
R2(PF* ||P-*) < 4
log Ep exp
14 ("
< 2
log Ep exp
[lue(X,))
H RELATED WORKS
H.1 THERMODYNAMIC INTEGRATION
(I) Review TI. We first briefly review the thermodynamic integration (TT) algorithm. Its essence to write the free-energy difference an integral of the derivative of free energy. Consider the general curve of probability measures (ne (T0)og(o.1) defined in (7) Then,
/
log Zo
Vo(x) 8y Vo(x)dd= En, Oo Vo
log
Er, do Vode. (35)
d0
Zo
Zo
J
43

---

Published as a conference paper at ICLR 2026
One may choose time points 0 Bu <... < AM and approximate by Riemann sum:
Z Zo
M
log
00+1 0e) Ex Oola=o.
(36)
where the expectation under each To, can be estimated by sampling from ne. Nevertheless, there is way of writing the exact equality instead of the approximation in (36) since
log
Z0z+1
log /
1 c
(Vorts (W (x)-V,,
dz Emo (Vo -Voe).
7:;
7:8.
by summing over O,... M 1, we have
M-1 log E Exo e (Voc+4 Voe))
Z
log
(37)
Zo
2=
which constitutes the estimation framework used in Brosse et al. (2018); Ge et al. (2020); Chehab ct al. (2023); Kook & Vempala 2025). Hence, we also use TI to name this algorithm.
(II) TI as a special case AIS. We follow the notations used in Thm. to demonstrate the following claim: T7 (37) is special case of AIS with every transition kernel Fe(x, .) chosen as the perfect proposal ne.-
Proof. In AIS, with Fe(x..) = To, in the forward path P-, we have ( = N To, (zz). In this special case,
M-1
(xe)
W(ra.) = log
II
Volei (we)
t=
and hence the AIS equality becomes the following identity, exactly the same as (35)
EE
Ex, e -Voe4+ -o,,)
(38)
Z
(III The distinction between equilibrium and non-equilibrium methods. In AIS framework, the distinction lies in the choice the transition kernels Fe(x, :) within the AIS framework.
In equilibrium methods, the transition kernels are ideally set the perfect proposal πe.- However, in practice, exact sampling from næ, is generally infeasible. Instead, one can apply multiple MCMC iterations targeting TT, leveraging the mixing properties of MCMC algorithms to gradually approach the desired distribution Te., Nonetheless, unless using exact sampling methods such as rejection sampling which is exponentially expensive in high dimensions the resulting sample distribution inevitably remains biased with finite number of MCMC iterations.
In contrast, non-equilibrium methods employ transition kernels specifically designed transport m toward nı, often following a curve of probability measures. This distinguishes them as inherently non-equilibrium. key advantage of this approach over the equilibrium one its ability to provide unbiased estimates, as demonstrated in JE and AIS.
(IV) Complexity bounds for TI. For the TI algorithm in Alg. used to estimate Zu f V-ll-Il dz, the analysis Ge et al. (020)) indicates that it suffices to choose K θ(vd) particles with multilevel estimation, which leads to
intermediate distributions and N θ
total complexity of Ô 4
to achieve the requirement in (23) (note that the condition number of
the potential 3| is O()))
44

---

Published as a conference paper at ICLR 2026
H.2 PATH INTEGRAL SAMPLER AND CONTROLLED MONTE CARLO DIFFUSION
In this section, we briefly discuss Iwo learning-bast bbaeed samplers used for normalizing constant estima- tion and refer readers to the original papers for detailed derivations. The path integral sampler (PIS) shares structural similarities with the RDS framework discussed in TTTm 3J using the time-reversal of universal noising process that transforms any distribution into prior such as the OU process in RDS that converges to the standard normal or the Brownian bridge in PIS that converges to the delta distribution at zero. contrast, the controlled Monte Carlo diffusion (CMCD) extends the JE framework from Sec. 3] focusing on learning the compensatory drift term along arbitrary interpolating curve (TH ( as long as the density of each intermediate distribution Te is known up to constant.
Path integral sampler (PIS, Zhang & Chen (2022)). The PIS learns the drift term of a reference SDE that interpolates the delta distribution at 0 and the target distribution π, which is closely connected with the Brownian bridge and the Föllmer drift (Chewi 2022).
Fix time horizon T > 0. For any drift term (u,) let Q" be the path measure of the following SDE:
dx, (X.)d) dB., / E [0, 7]: Xo a.s. 0.
In particular, when u = O, the marginal distribution of XT under Q" is N (0,T)) =: Ør. Define another path measure Q* by
dm
2 (d) = - (d = 2 (d((o.r)) der
(ET), Vg E C(OO
and consider the problem
argmin KL( Q*)
Q = Q¹
One can calculate the KL divergence between these path measures via Girsanov's ' theorem Lem.
dQ
log
do (x) = ("(X) + log Z, a.s. ~ Q", where
(x) = 1² (x,) dBe) + /" I |/ (x.) ||
d log 2T
+
V(X))
2T
2
which implies Z = Egu c W" and (L( = Eq W + log Z. On the other hand, directly applying[enm Lem. gives
KL(O")12)> 1 T 2/ Ee (X,, ui (Xt))
In Zhang & Chen (2022
Theorem 3), the authors considered the effective sample size (ESS) defined the convergence criterion, and stated that ESS 1 long as
by ESS 1 Eq-
do a
suPrejo.T] |/ue ull 2 < f. However, this condition is generally hard to verify since the closed-
form expression of u" is unknown, and the _ bound might be too strong. Using the criterion (T) and the same methodology proving the convergence of JE (Thm. 2), we can establish an improved result on the convergence guarantee of this estimator, relating the relative error to the training loss of u, which is defined as
min L(u)= = Eo.
1 L' [lw.(X))][ae
| 2T
+ +V(XT)
-L(2"112') 2+ log 2T
Proposition 4. Consider the estimator 2 == (x),, X Q" for Z. To achieve both
KL(Q" (T) S c² (with Q¹ representing the law of Xy in the sampled trajectory X ~ Q²) and
Pr 7 5s) 2 3. it suffices to choose u that satisfies
L(w) - -log Z + d
log 2 + +(E2).
2
45

---

Published as a conference paper at ICLR 2026
Proof.
2 Z
= = Q" (
dQ' dQ"
TV(Q".07 2
KL 2*)
Pr
2
Therefore, ensuring ( 2*) x 8² up to some sufficiently small constant guarantees that the above probability remains bounded by 1. Furthermore, by the pata-psoessiing inequality. (L( ([) z (I((2"I S
Controlled Monte Carlo Diffusion (CMCD, Vargas et al. 2024)). We borrow the notations from Sec. 3 due to its similarity with JE.
Given (=t) and the ALD (2) know from the proof of Thm. 1 that to make X, Te for all 4
the compensatory drift term (c, (0. must generate (#g) Now, consider the task of learning such vector field (w)) by matching the following forward and backward SDEs:
p= : dX,- = (V log के + (x) + v2dB, Xo ~ Tu.
p== dX,- (- V log न.. + (X,) v2dB X1 Tr,
where the loss is KL(P-IPP*) discretized in training. Obviously, when trained to optimality, both p and p share the marginal distribution म, at every time t. By Girsanov's theorem (Lem. 3). one
can prove the following identity for a.s. X ~ p log dp- (X) W(X) Cx(X) AF, where A P and (XX) are defined as in Thm. 1 and
C²(X) = ['" ((u)(X)), Vlog VXogm( + V d((X)))tt.
We refer readers to Vargas al. 2024 Prop. 3.3) for the detailed derivation. By Ep- dP-
dp
we know that Ep e (X-WX (X) = e-AF As the paper has not established inference-time performance guarantee given the training loss, we prove the following result characterizing the relationship between the training loss and the accuracy of the sampled distribution as well as the estimated normalizing constant.
Proposition 5. Lei 7 = Zne (-----(X--C0 X~pP~ be an unbiased estimator of 2 = Zoe AF Then, to achieve both KT.(P, (t)
e2 (where PT is the law of Xx in the sampled trajectory
X P~) and Pr ( - & 3. it suffices choose that satisfies [P
Proof. The proof of this theorem follows the same reasoning that of Prop. 4 For normalizing constant estimation,
(
(1 28 TV(P',P*
dp
KL
p
Pr
-
18
1
28 1222=11
=
S 1.
Z
For sampling, the result is an immediate corollary of the data-processing inequality.
I DETAILS OF EXPERIMENTAL RESULTS
1.1 MODIFIED MÜLLER BROWN DISTRIBUTION
The Müller Brown potential energy surface is canonical example of potential surface used in molecular dynamics. Here, we consider a modified version of this distribution as defined in He et al. 2024 App. D.5). For (2) E R2, the target distribution is T (x)) 1/ exp(-0.1(V,
r )), where
(x( = 35.0136(z) + 0.033923) 59.8399 0.465694)2.
Vin (x) Σ
A exp(a, X,)² + ( Xx) Y)) + c -Y,)))
46

---

Published as a conference paper at ICLR 2026
In the above equations, 21 0.2(22 -22-122-20----------222-22___1--
(-1,- -, -6.5,66.00 0.7), = (0,0.11,0.6), c = (-1100,-11,
= (1,0, -1),
(0, 0.5, 1.5, 1). The ground truth value of the normalizing constant computed by numerical integral (scipy- integrate....................e.t dbl quad) is 7 02340099833 with estimated absolute error 0.0001.
We each method with approximately the same oracle complexity. Aside from the quantitative results in Tab. we also visualize the samples drawn from each method against the level curves of the potential in Fig. 2 is clear from the table and figure that TI and AIS fail provide accurate estimates of the normalizing constant or sample from the target distribution due to the deficiency of the exploration of different modes. All four RDS-based methods provide accurate estimates of the normalizing constant, with SNDMC and ZODMC being the two best methods.
A5
IDDC
ISDNC
ZORMM
SNIMC
ce
en
-43
-25
45
22
-1
25
-04
-0
42
Figure 2: Visualization of the samples from the modified Müller Brown distribution. The generated samples are displayed on top of the level curves of the potential energy surface (darker color corresponds to lower potential energy, i.e., higher probability density).
I.2 GAUSSIAN MIXTURE DISTRIBUTION
We now consider Gaussian mixture distribution in IR2 with 4 components, having weights
0.1, 0.2, 0.3, 0.4, means
9
11
11
9
)
0
and covariances
0.5 0.))
1
0.5)
( -0.2
-0.2)
(
0.3
1.2
-1
0.3
0.3
1 (-1
1.2
As the p.d.f. is available in closed form, the ground truth value of the normalizing constant is Z = 1. Due to the separation of the modes and the imbalance of the weights, this distribution is more challenging sample from. In the quantitative results shown in Tab. I] we report the mean and standard deviation of 2 as well as two metrics for the quality of the samples: maximum mean discrepancy (MMD) and Wasserstein-2 distance (W2) between the generated samples Reamp and ground truth samples from æ. The visualization of the samples is shown in Fig. 3 Again, TI and AIS are confined mode at zero where the initial samples are located, and fail to provide accurate estimates of the normalizing constant. All based methods provide accurate estimates of the normalizing constant and high quality samples.
A5
HOMC
RSSML
Z00RK
SNOM:
10
11
Figure 3: Visualization of the samples from the Gaussian mixture distribution. The generated samples displayed on top of the level curves of the potential (darker color corresponds to lower potential, i.e. higher probability density).
I.3 IMPLEMENTATION DETAILS
General implementation details. For both experiments, we run each method for 1024 rounds and output the mean and standard deviation of all 1024 estimates of 3. In each round, parallelly
47

---

Published as a conference paper at ICLR 2026
1024 i..d. trajectories, which produces 1024 i.id. samples from and 1024 ii.d. estimates of the normalizing constant, and we treat the average of the estimates as the final estimate of that round. We record the oracle complexity of each algorithm and tune the hyperparameters to make sure that the oracle complexity for producing each sample from a is between 50000 and 60000 for fair comparison. For TI, choose A 100, A 1+1/Va A until X; S 2vd and N 32 i.i.d.
1.45
samples. For AIS, we choose A 100, MM = 60000 steps, and ALMC step size T. = 0.01. For all RDS-based methods, we choose the total time duration T 5, early stopping time
0.005, and N = 50 uniformly spaced time points i, = N (T 5). Specifically, for RDMC, we use 64 samples from Toje( (-Ix) to estimate the score log Fe (2),, and run LMC for steps with step size 0.01, initialized by importance sampling from (-je(-1z)
e eev() N (-le',, - 1)1) with proposal N (e'zz, (e 1) for RSDMC, we choose the number of recursive steps 2, use 16 samples from ( to estimate the score V log (z), and run LMC for 10 steps with step size 0.01 using the same initialization based on importance sampling; finally, for both ZODMC and SNDMC, we use 1024 samples from (-(r)) to estimate the score V log (I))
Evaluation metrics for sampling. In the experiment of Gaussian mixture distribution, in each round, draw 1024 samples from both the algorithm and the target distribution, and compute the following two metrics to evaluate the quality of the samples. For two sets of samples X {x; 1 and y { the MMD is defined as
MMD(X,))
Σ ISif'sn
k(x;,
2 nm ISSmAISIS
Σ
k(I, vi) +
1
Σ ISid'sm
k(y;,U));
m²
where k(x,)) Σ K
exp
is multiscale radial basis function (RBF) kernel. Fol-
2x
lowing the implementation in He al. 2024)) Second, the W2 distance is computed by ot..eeee (a, b, M) ** 0.5 using the Python Optimal Transport (POT) package (Flamary et al. 2021). where
K 10 and {a:)10 110 {-4, -2, ..., 12, 14).
11,, b 11 m. and
([|=; - y I SSSm. In represents the vector of all ones with length n.
48


Reviews:
[{"review_id": "yXa04qYmz1", "reviewer": "Reviewer_J6xT", "summary": "The work proposes a scheme for normalizing constant estimation based on the annealed Langevin framework. It shows, via a relatively novel annealing scheme, that one can achieve multiplicative accuracy with number of queries depending polynomially on the action of the curve, defined as the integrated norm of the metric derivative (in a Wasserstein sense).", "questions": "(2) and (3) do not seem to be time reversals of each other? Or is ``backward’’ meant in a more pedestrian sense?\n\n23: Girsanov theorem -> Girsanov’s theorem\n\n111: denoising diffusion model -> denoising diffusion models\n\n136: estimating normalizing constant -> estimating the normalizing constant\n\n287: for the study non-asymptotic -> for the study of non-asymptotic\n\n390: full proof is in -> The full proof is in\n\n463: biased estimate -> biased estimates", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "I think this is an interesting and useful result, providing a principled means of normalizing constant estimation with interpretable guarantees. I concur with the authors that this is an important problem in computational statistics.\n\nThe connections between this and annealed sampling algorithms are elegant and nicely parallel the connection in discrete settings. This fact is also noticed by the authors.\n\nThe connections to statistical mechanics are always nice to see.", "weaknesses": "I find the action of a curve to be a somewhat inscrutable quantity from the perspective of algorithm design. The authors do a good job of trying to make this quantity accessible to unfamiliar readers but it certainly merits further investigation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "J80T2f9w4I", "reviewer": "Reviewer_TbKt", "summary": "The authors show query complexity bounds for normalization constant estimation using annealing-based methods including Jarzynski equality for SDE's and annealed importance sampling. The details for JE and AIS are different (being continuous/discrete), but they share a similar analysis framework. \n\nThe bounds are in terms of the \"action\", or total squared metric derivative through the annealing sequence. The authors give an example where this is exponentially large in a situation with mass teleportation, and use this to motivate applying JE to reverse diffusion samplers through a polynomial bound on the action only under smoothness and 2nd moment.", "questions": "In Theorem 4, the authors interpolate from a log-concave distribution, with the partition function for the log-concave distribution estimated separately via TI. However, one could also attempt to use JE through the entire sequence from the Gaussian approximation. How would these compare theoretically or experimentally? Is there a reason to prefer one or the other besides convenience of theoretical analysis?\n\nThe statement of Lemma 6 is a bit confusing, since what is meant is that the conditions are to be satisfied for small enough constants, not arbitrary constants. Please clarify this in the lemma statement (right now this is only in Remark 5).", "limitations": "", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "This is a very timely topic given the increasing presence of these algorithmic methods (especially Jarzynski's equality which has been adapted for sampling with flow-based neural network models) and the limited theory for them. Normalizing constant estimation is a fundamental problem in ML and statistics, and the authors do a good job of giving examples of applications. The paper is technically well-written, and I especially appreciate the careful treatment of the forward/backwards SDE's. I expect the theory developed in this paper will be useful for future analyses on this and similar algorithms.\n\nThe application to reverse diffusion samplers is an especially nice result. This shows that efficient normalizing constant estimation follows from general conditions given an accurate score estimate.", "weaknesses": "The proof is written just for geometric interpolation, though it would be better to have a general bound that works for an arbitrary annealing sequence and added drift, as this flexibility is often important in the literature, especially in approaches that depend on learning the annealing sequence and drift (e.g. Máté and Fleuret, 2023; Albergo and Vanden-Eijnden, 2025). Would a similar proof work, or is the proof specialized to the annealing sequence? What changes are necessary? Relatedly, would this framework apply to give guarantees for sampling?\n\nThe main downside is the polynomial dependence in all bounds on the \"action.\" While this is weaker than isoperimetry, it's not clear whether this matches other bounds for annealing/tempering-type methods. In fact, I doubt this covers many cases where we'd want to use annealing-based methods: The authors show a lower bound for the action in the case of a mixture of 2 (1-D) gaussians using power tempering. It seems this analysis can also be adapted to show a lower bound in any case with well-separated modes where their relative weights change, a situation which some other analyses of tempering-based methods are able to tackle; this would mean that in multimodal settings, the bounds in the paper are only effiicient when the relative weights don't change. Can the authors please clarify when they expect the action to be polynomial, and how this assumption relates to other \"beyond isoperimetry\" assumptions in the literature (e.g. multimodal/mixture settings)? Under what settings do we expect the action to be reasonable? (The reverse diffusion sampler is an example where this is nice, which I appreciate.)\n\nI would be happy to increase my score if these points are satisfactorily addressed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "V9tC8tMlgz", "reviewer": "Reviewer_s4rX", "summary": "The paper uses a novel method to analyze and bound the non-asymptotic estimation error of the normalization constant for an energy functions in terms of smoothness of the potential and the action of annealing curve. \nThe method relies on conditions that are less restrictive than the commonly used isoperimetric constraints for this type of analysis and applies to non-log-concave distributions. The analysis sheds light on the increased complexity of estimation with geometric interpolation in comparison to OU reversal.", "questions": "1 - It feels counter intuitive that a nested linear ($\\theta$ in Eq. 10) and exponential (line 317 for $\\lambda$) discretization of the schedule would reduces the overall estimation error in comparison to purely linear or exponential schedule (line 324). Since the proof of THM4 bounds the error with $r = 1$, I don't see the motivation for the exponential $\\lambda$. Can you provide some examples that show how the cost (11) depends on $r$? What are the conditions for it to improve with $r > 1$? Is there a benefit of exponential cascading of $\\lambda$?\n\n2 - As the main issue with multimodal distributions arises in high dimensions, is there any explanation on how the action depends on $d$ in PROP1?\n\n3 - Can you give a brief explanation of mass teleportation an mode switching phenomenom (line 394)?\n\n4 - The order of OU sampling error (reversing the noising process) is known to be independent of $d$ and similar to the OU process accuracy [De Bortoli - NeurIPS2021]. Where does the dependence on $d$ come from in your derivation in line 444?\n\n5 - Can the authors detail how they incorporate Alg. 2 in the mentioned algorithms to get new results?\n\n6 - Alg. 2 seems like a typical diffusion sampler weight update, e.g. similar to that of PIS [Zhang & Chen 2022]. Is the difference with PIS in decomposition of the Brownian motion?\n\nMinor comments:\nTypo: line 316 ALMC -> LMC", "limitations": "", "rating": 2, "confidence": 4, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "I believe the main contribution of the paper, according to itself, is the non-asymptotic analysis (in the number of path samples) for TI and AIS (LMC) which is presented in THM2 and 4. THM2 proves constant probability bound on the error of the normalization factor estimation ratio in the path integral of Thermodynamic integration. THM4 proves an upper bound on the number of oracle calls $M$ in AIS (LMC, Alg. 1).", "weaknesses": "1 - Some important recent literature is missing from the work. How do you compare your method to Adjoint sampler or methods approximating the Kantorovich potential of the RDS.\n\n2 - Organization of the paper is very synthetic. The paper is super technical, lacks a properly structured background section and multiple theoretical results are presented without a straight forward relevance to each other. The notations are not clearly defined in the text ($B_t$ and $B_t^\\leftarrow$ in Eq 2 and 4, $n$ in line 444) and abbreviations are missing (TI, RN, SDE). Navigating through the paper is very difficult. I don't think the inclusion of Lem1 or THM1 and THM3 and their proofs are necessary for the text - this context can be built in a less technical and more cohesive manner. I recommend the authors restructure the paper and this is the main reason I'm in favor of rejecting this version. In the following I provide a list of modifications that are going to influence my decision.\n\n3 - Use uniform notation across different theorems, sections and appendix as much as possible. For instance, $k$ and $l$ for step indices, forward and backward SDEs in proof of THM2 reuse the same notation.\n\n4 - Simplify the representation of the Theorems \n\n4.1 - The use of scaling $t/T$ in THM2 is not necessary. It appears that the action $\\mathcal A = \\int_0^1 |\\dot \\pi_t|^2dt$ is proportional to $T$ which is used for scaling $t$. Therefore, the last line of proof implies a constant upper bound on the path integral for any speed and not just the specified $T$ (see proof of THM2). \n\n4.2 - Prop1 and Prop2 and THM6 seem out of place with respect to the rest of the paper. Is there a corollary missing? It might be the case that sample complexity bound depends on the action, but the relations are only derived for the geometric interpolation (Eq 7) in THM4. It is not enough to suggest that the lower bound on action in geometric and upper bound in RDS translates directly to better upper bound for RDS sample complexity. \n\n4.3 - In THM5 what is the use of $\\delta$ in practice? This Theorem is adapted from previous work with the addition of $delta$ for which I'm not able to see the motivation.\n\n4.4 - Appendix E.5 doesn't provide any analysis on the sample complexity of the mentioned algorithms, only references. Are the orders taken from the references? If so should be stated like that in the paper as opposed to analysis (line 445). \n\n5 - Throughout the paper different units of complexity are used to compare different algorithms. It would be helpful to write down the dependence of all complexity bounds in terms of the action, bounding the action, and with the median trick in a table for clarity.\n\n6 - I'm not certain how Alg. 2 is used in \"the series of new algorithms based on reverse diffusion samplers\". I'm also assuming the experiment section somehow incorporates Alg. 2. But RDMC, RSDMC, ZODMC, SNDMC all are reference algorithms with their own state update steps and importance weight computation. It is not clear how Alg. 2's state and weight update is incorporated in the reference algorithms to get new results. \n\n7 - Experiments in $\\mathbb R^2$ tend to be too simple and lead to overlapping results (confidence bounds) from RDS based algorithms. Results in more complex setups could prove more interesting.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "59pqqXfyH8", "reviewer": "Reviewer_8vBo", "summary": "This paper provides a full theoretical analysis of the error in Annealed Importance Sampling (AIS), accounting for both the sampling process that generates particles and the estimator of the normalizing constant computed from these samples. The authors derive a general upper bound on the estimation error as a function of the prescribed probability path that guides the sampling process. Two important path choices are examined: the standard geometric interpolation path, which is shown to lead to exponential complexity in the difficulty of the problem, and the reverse diffusion path, which achieves only polynomial complexity—provided oracle access to score functions (otherwise, an additional approximation error appears). The difficulty of the problem is quantified in terms of the between-mode distance of the target distribution.", "questions": "Q1. Theorem 4 is particular to the geometric interpolation path? Is it normal that the number of samples $N$, the number of SMC iterations $M$, and the discretization of the Langevin process, do not appear in the error bound (Eq 11)?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 4, "strengths": "This is a welcome analysis. There is a long literature that analyzes the error of Annealed Importance Sampling, but it usually:\n- makes strong assumptions: assuming equilibrium sampling, using the asymptotic regime where the number of samples is big, etc.\n- is not very interpretable: the formula of the error does not clearly tell the user how to design the prescribed probability path\n\nIt has been a goal in that literature to produce a general formula of the error that is interpretable enough to inform the design choice of the probability path. To my knowledge, this is the first such analysis.", "weaknesses": "The writing could be clearer in some parts, but overall the paper is clear.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)