Provable benefits of annealing for estimating normalizing constants: Importance Sampling, Noise-Contrastive Estimation, and beyond
Authors: Omar Chehab
Aapo Hyvarinen
Andrej Risteski
Venue: NeurIPS 2023 spotlight (2023)
Keywords: noise-contrastive estimation
annealed importance sampling

Abstract: Recent research has developed several Monte Carlo methods for estimating the normalization constant (partition function) based on the idea of annealing. This means sampling successively from a path of distributions which interpolate between a tractable "proposal" distribution and the unnormalized "target" distribution. Prominent estimators in this family include annealed importance sampling and annealed noise-contrastive estimation (NCE). Such methods hinge on a number of design choices: which estimator to use, which path of distributions to use and whether to use a path at all; so far, there is no definitive theory on which choices are efficient. Here, we evaluate each design choice by the asymptotic estimation error it produces. First, we show that using NCE is more efficient than the importance sampling estimator, but in the limit of infinitesimal path steps, the difference vanishes. Second, we find that using the geometric path brings down the estimation error from an exponential to a polynomial function of the parameter distance between the target and proposal distributions. Third, we find that the arithmetic path, while rarely used, can offer optimality properties over the universally-used geometric path. In fact, in a particular limit, the optimal path is arithmetic. Based on this theory, we finally propose a two-step estimator to approximate the optimal path in an efficient way.

Provable benefits of annealing for estimating normalizing constants: Importance Sampling, Noise-Contrastive Estimation, and beyond
Omar Chehab
Aapo Hyvärinen Department of Computer Science University of Helsinki Helsinki, Finland aapo www..hyyrrinennoolsnninii .1i
Université Paris-Saclay, Inria, CEA Palaiseau, France
--emir--- emmar wwwhabeinria.ff....
Andrej Risteski
Department of Machine Learning
MarneiieMMellon University Pittsburgh, USA aristesk@andres cmu edu
Abstract
Recent research has developed several Monte Carlo methods for estimating the normalization constant (partition function) based on the idea of annealing. This means sampling successively from a path of distributions that interpolate between a tractable "proposal" distribution and the unnormalized "target" distribution. Promi- nent estimators this family include annealed importance sampling and annealed coise-contrastive estimation (NCE). Such methods hinge on number of design choices: which estimator to use, which path distributions to use and whether use path at all; so far, there is no definitive theory on which choices are efficient. Here, we evaluate each design choice by the asymptotic estimation error produces. First, show that using NCE is more efficient than the importance sampling esti- mator, but in the limit of intinitesimal path steps, the difference vanishes. Second, we find that using the geometric path brings down the estimation error from an exponential to a polynomial function the parameter distance between the target and proposal distributions. Third, find that the arithmetic path, while rarely used, can offer optimality properties over the universally fact, in particular limit, the optimal path is arithmetic. Based this theory, we finally propose two-step estimator to approximate the optimal path an efficient way.
geometric path.
Introduction
Recent progress in generative modeling has sparked renewed interest in models of data that defined by unnormalized distribution. A prominent example is energy-based models, which are increasingly used in deep learning [. and for which there are variety of parameter estimation procedures (. Another example comes from Bayesian statistics, where the posterior model of parameters given data is frequently known only up proportionality constant. Such models can be evaluated and compared by the probability they assign dataset, yet this requires computing their normalization constants (partition functions) which are typically high-dimensional, intractable integrals.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Kionte-Carlo techniques have been successful at computing these integrals using sampling meth- ods [6. The most common is importance sampling [ which draws sample from a tractable, "proposal" distribution to integrate the unnormalized "targer" density. conte-conteestive estimation (NCE) 3 uses a sample from both the proposal and the target, to compute the integral. Yet such methods suffer from high variance, especially when the "gap" between the proposal and target densities is large [7H2]. This has motivated various approaches to gradually bridge the gap with inter- mediate distributions, which is loosely referred to as "annealing". Among them, annealed importance sampling (AIS) [0 is widely adopted: has been used to compute the normalization constants of deep stochastic models [3] 14 or to motivate lower-bound for learning objectives [1]] To integrate the unnormalized "target" density, it draws a sample from an entire path of distributions between the proposal and the target. While annealed importance sampling has been shown to be effective empirically, its theoretical understanding remains limited [17 [8] it is yet unclear when annealing is effective, for which annealing paths, and whether AIS is statistically efficient way to do it.
In this paper, we define family of annealed Bregman estimators (ABE) for the normalization constant. We show that it is general enough to recover many classical estimators as a special case, including importance sampling, noise-contrastive estimation, umbrella sampling [19], bridge sampling [20] and annealed importance sampling. We provide a statistical analysis of its hyperparameters such as the choice of paths, and show the following:
1. First, we establish that using NCE is more asymptotically statistically efficient - in the sense of how many samples from the intermediate distribution need to be generated than the importance sampling estimator, but in the limit of infinitesimal path steps, the difference vanishes.
2. Second, we find that the near-universally used geometric path brings down the estimation error from an exponential to a polynomial function of the parameter distance between the target and proposal distributions.
3. Third, we find that using the recently introduced arithmetic path 21 is exponentially inefficient in its basic form, yet it can be reparameterized to be in some sense optimal. Based on this optimality result, we finally propose a two-stage estimation procedure which first finds an approximation of the optimal (arithmetic) path, then uses it estimate the normalization constant.
2 Background
Importance sampling and NCE The problem considered here is computing the normalization constant i.e. the integral of some unnormalized density fi (α) called "target".
Importance sampling and noise-contrastive estimation are two common estimators for that integral which use a random sample drawn from a tractable density po (2) called "proposal" ((Taals column 3). In fact, they are part of a larger family of Monte-Carlo estimators which can be interpreted as solving binary classification task, aiming to distinguish between a sample drawn from the proposal and another from the target (22). These estimators are summarized in Table I Each estimator is obtained by minimizing specific binary classification loss that is identified by a convex function ((x). For example, minimizing the classification loss identified by d1s(x)
log yields the importance sampling estimator. Similarly, Φnevis (x) = - log x leads to the reverse importance sampling estimator 233, and ÓNCE (2) x llog (1 + x)) log((1 + x))2) to the noise-contrastive estimator.
Annealed estimators Annealing extends the above "binary" setup, by introducing sequence of K + 1 distributions from the proposal to the target (included). The idea will be to draw sample from all these distributions to estimate the integral of the target (ar).
These intermediate distributions are obtained from a path (ft)cejo.) 1). defined by interpolating between the proposal po and unnormalized target fi: this path is therefore unnormalized. Different interpo- lation schemes can be chosen. A general one, explained in Figure 1, is to take the q-mean of the
in this paper we also say we "estimate" the normalization constant, though in classical statistics it is more traditional to use "estimation" when referring to parameters of a statistical model

---

Name
Loss identified by ((x:)
Estimator 21
MSE
IS
x log
Po f
1t PP2(11P0)) oN
RevIS
log
(Epi R
1+ D Dpu P1)
NCE
x log (1 + x)) log( 1+x)
implicit
[1+2) Puaa(P1
v. 1 Dum
Table I: Some estimators of the normalization obtained by minimizing classification loss, and their For details and definitions, see Appendix
estimation error in terms of well-known divergences [22].
General (q E|O, 1))
f((x:) = ((1 (2)())) + ())())))
Geometric (g 0) fr fx)) Po(x)) I- (zx)
Arithmetic (q = (x) (1 - ()) (s)
Figure I: q-mean paths between the proposal and target distributions, The geometric and arithmetic paths are obtained limit cases. Here, the proposal (red) is a standard Gaussian. The target (blue) Gaussian mixture with two modes, and same first and second moments as the proposal. The path of distributions interpolates between blue and red.
proposal and target [21]. Two values of are of particular interest: - O defines a ncar-universal path [18) obtained by taking the geometric mean of the target and proposal, while q defines path obtained by the arithmetic mean.
Once a path is chosen, it can be uniformly discretized into a sequence of K + unnormalized densities, denoted by (fk/K x ]e(o,,K] with corresponding normalizations (Zk/ [e practice, samples are drawn from the corresponding normalized densities (Pk/K ) jo.k] using Markov Chain Monte Carlo (MCMC). This sampling step incurs a computational cost, which is paid in the hope of reducing the variance of the estimation. It is common the literature 17 to assume perfect sampling, meaning the MCMC has converged and produced exact and independent samples from the distributions along the path, which simplifies the analysis.
Estimation error measure of "quality" is required to compare different estimation choices, such as whether to anneal and which path to use. Such measure is given by the Mean Squared Error (MSE), which is generally tractable when written at the first order in the asymptotic limit of large sample size (24 Eq. 5.20J. These expressions have been derived for estimators obtained by minimimizing a classification loss [22] and are included Table I They measure the "gap" between the proposal and target distributions using statistical divergences. Note also that the estimation error depends on the normalized target density (column 4), while the estimators are computed using the unnormalized target density (column 3). Further details available in Appendix A
3 Annealed Bregman Estimators of the normalization constant
The question that we try to answer in this paper is: How should we choose the K distributions in annealing (the target is fixed), and how are their samples best used? To answer this, we will study the error produced by different estimation choices. But first we define the set of estimators for which the analysis done.
Definition of Annealed Bregman Estimators We now define a new family of estimators, which we call annealed Bregman estimators (ABE); the motivation for this terminology will become clear in the coming paragraphs. We will show that this is general class of estimators for computing the normalization using sample drawn from the sequence of K - distributions. For ABE, the log
other discretization schemes can be equivalently achieved by re- parameterizing the path 17
3

---

normalization log 21 is estimated additively along the sequence of distributions
K
((x+1)/K
log 21
log
+ log Zo
(I)
Zz/K
Defining the estimation in log- is analytically convenient, as it is easier to analyze sum of estimators than a product. Exponentiating the result leads to an estimator Z1. We naturally extend the binary setup (K 1) of Chehab al. [22] and propose to compute each of the intermediate log-ratios, by solving a classification task between samples drawn from their corresponding densities Pa/K and 1(K+1)/K- Each binary classification loss is now identified by convex function (x)) and defined as
(3x))) == E (r Bx)) x rae Ba) (rx EE-PAIII (ra Bx))
(2)
where the regression function (x; 9&) is parameterized by the unknown log-ratio Bk
Tk (x B&)) = exp( f(++ 1) fx///(/
(3)
For the true 8 it holds 37 (o /Z/Kk) and Ta (z:
((++))/(()/pp) (x)pp/)//)))))))))(>)/)>)))))(
The convex functions (ot) - which identify the classification losses are called "Bregman" generators, hence ABE. As mentioned above, we assume perfect sampling and allocate the total sample size N equally among the K estimators in the sum.
Hyperparameters The annealed Bregman estimator depends on the following hyperparameters: (1) the choice of path q: (2) the number of distributions along that path K + (including the proposal and the target); (3) the classification losses identified by the convex functions (ox))e(U,K-
Different combinations of these hyperparameters recover several common estimators of the log- partition function. In binary case of K this includes importance sampling, reverse importance sampling, and poise-contrastive estimation, each obtained for different choice of the classification loss [22]. To build intuition, consider К 2 so that we add single intermediate distribution p1/2 to the sequence. Using the importance sampling loss (øn = x log x) for the first ratio, and reverse importance sampling (Φ) = - log æ)) for the second ratio, recovers the bridge sampling estimator as special case [20]
f1/2 + log Zo f1/2 + log Epo log Z1 -og log Ep,
fi
So
Alternatively, we can use these classification losses in reverse order: reverse importance sampling (go l) for the first ratio, and importance sampling (d1 log x:) for the second ratio, and recover the umbrella sampling estimator
[19] also known as the ratio sampling estimator (25)
fi
fo
log 21 log E p1/2 f1/2
log E Ep/2
log Zo
(5)
J1/2
Another option yet, is to use the same classification loss for all ratios. With importance sampling (Øt = x x, Vk [0, K I]), we recover the annealed importance sampling estimator [2
fR
log Zi
log Ex-pp
(az)
log Zo
(6)
The family of annealed Bregman estimators is visibly large enough to include many existing esti- mators, obtained for different hyperparmeter choices. This raises the fundamental question of how these hyperparameters should be chosen, in particular in the challenging case where the target and proposal have little overlap and the data is high dimensional. To answer this question, we will study the estimation error produced by different hyperparameter choices.
4 Statistical analysis of the hyperparameters
We consider fixed data budget N and investigate how the remaining hyperparameters are best chosen for statistical efficiency. The starting point for the analysis is that as ABE estimates the

---

normalization in lpgcs,ace, the estimator is obtained by sum of independent and asympiotically unbiased estimators [66 given in Eq. [a thus the mean squared errors written table[[ additive. (Recall, the independence of these estimators is because new samples are drawn for each estimation task.) Each individual error actually measures an overlap between two consecutive distributions along the path, and annealing integrates these overlaps.
4.1 Classification losses,
Given the popularity of annealed importance sampling, we should first ask if the importance sampling loss really an acceptable default. We recall an important limitation of importance sampling: its estimation error is notoriously sensitive to distribution tails (27]. Without annealing, it is infinite when the target pl has a heavier tail than the proposal po- When annealing with a geometric path, for example between two Gaussians with different covariances po = =N Id) and pl (O, 2 Id), the geometric path produces Gaussians with increasing variances Σ, = - t/2) Id and therefore increasing tails. Hence, the same tail mismatch holds along the path. Note that this concern is a realistic one for natural image data, as the target distribution over images is typically super- Gaussian 28 while the proposal is usually chosen as Gaussian.
This warrants better choice for the loss: the binary setup (K = 1). the NCE loss optimal (20 22 and its error can be orders of magnitude less than importance sampling (20]. This optimality result has been extended to a sequence distributions > [29] eq. 16]. We further show that in the limit of continuous path, the gap between annealed IS and annealed NCE is closed and we provide their estimation error:
Theorem (Estimation error and the Fisher-Rao path length) For a finite value of K, the optimal loss is NCE:
MSE(po, Pliq, K, ONCE) S MSE(po, Pri K,), Vq, K, N,
In the limit of K + Do (such that K2 K²/N + 0), NCE, IS, and revIS converge to the same estimation error, given by the Fisher-Rac path length from the proposal to the target:
1 N 1.. I(t)dt + of (T o
K22 N
MSE(po. PIg K,
Vó E {dNNER Øis, dRRviss (8)
| is defined as the Fisher information where the Fisher-Rao metric I(f) := Em-p(an,) |[ de log (x))) over the path, using time as the parameter.
This is proven in Appendix B. Note that in this theorem, take limits successively in N co then in K + oo, we assume that N grows at least as fast as K22 While the NCE estimator requires solving (potentially non-convex) scalar optimization problem in Eq. and IS does not, this the price to pay for statistical optimality, In the following, we will keep the optimal NCE loss and will indicate the dependency of the estimation error on ONCE with a subscript, instead. We highlight that our theorems in this paper apply to the MSE in the limit of K + oc: their results hold the same for the IS and RevIS losses by virtue of theorem [ Just as the binary case, while the estimator is computed with the unnormalized path of densities (Eq. 2). the estimation error depends on the normalized path of densities (Eq. ().
4.2 Number of distributions, K +
It is known that estimating the normalization constant using plain importance sampling (K 1) can produce a statistical error that is exponential in the distance between the target and the proposal [30]. We show that in the binary case, NCE also suffers from an estimation error that scales exponentially with the parameter-distance between the target and proposal dimension.
In the following, we consider proposal po and target Pt that are in an exponential family with sufficient statistics (xx). Note that exponential families have a rich history in statistical literature: they classic parametric families of distributions [3] and certain of them have universal approximation
capabilities 32 33). An exponential family is defined as
pl [x; 0) == exp((e (0, t(x)) log Z(0))
5

---

where ( = / /exp( (01, ((x))) is the partition function. We will consider that the (unnormalized) target density fi what we call a simply unnormalized model defined as
fz = exp((0, t(x)))
(10)
Note that in general, a pdf can be unnormalized in many ways: one can multiply an unnormalized density by any positive function of 0 and it will still be unnormalized. However, the simple and intuitive case defined above is what we base the analysis below on.
For exponential families, the log-normalization log Z()) is a convex function ("log-sum-exp") of the parameter 0 (34], which implies V log (0).. In our theorems, we use the further assumptions of strong convexity with constant M, and/or smoothness with constant L (gradient is L-Liptschitz);
V log (0) > M Id
(11)
V log (0) < Ld
(12)
For exponential families, the derivatives of the log partition function yield moments of the sufficient statistics, and the hessian V3 log ())) = Cov [xx)] is in fact the Fisher matrix. We can interpret our two assumptions: Eq. 11 can be seen as a form of "strong identifiability". Namely, positive- definiteness is required of the Fisher matrix, for the Maximun-Likelihood loss to have a unique minimum: we further assume lower-bound on the smallest eigenvalue, which can be viewed as strong identifiability condition. Eq. 12 can be interpreted as a bound on the second-order moments of the distribution p(æ; 0), which is equivalent to the variance in every direction being bounded, which will be the case for parameters in bounded domain 0 E O An example along with the proofs the following Theorems and 3 are provided in Appendix B
Theorem 2 (Exponential error of binary NCE) Assume the proposal po is from the normalized exponential family, while the (unnormalized) target f1 is from the simply unnormalized exponential family (Eq. I0). The log- nog-partition function log Z (0) is assumed to be strongly convex (Eq. [T..
Then in the binary case K = 1, the estimation error of NCE is (at least) exponential in the parameter- distance between the proposal and the target:
MSENCE (po. P1; q, K. N)
4
exp
( (g M10; 101l01-0ul'3
Bull
11
1 N
when K =1 (13)
N
where M is the strong convexity constant of log Z(0).
Annealing the importance sampling estimator (increasing K) was proposed in the hope that we can trade the statistical cost in the dimension for computational cost (number of classification tasks) which could be considered more acceptable. Yet, there is no definitive theory on the ability of annealing to reduce the statistical cost in general setup [8] 21. For both importance sampling and noise-contrastive estimation, we next prove that annealing with the near-universally used geometric path brings down the estimation error, from exponential to polynomial in the parameter-distant between the proposal and target. Given that we expect ||0 - 0oll2 to scale as vD with the dimension, using these paths effectively makes annealed estimation amenable to high-dimensional problems. This corroborates empirical (51 and theoretical [17] results which suggested in simple cases that annealing with an appropriate path can reduce the estimator error up several orders of magnitude.
Theorem 3 (Polynomial error of annealed NCE with a geometric path) Assume the proposal po is from the normalized exponential family, while the (unnormalized) target fa is from the simply unnormalized exponential family (Eq. 10). The log-partition function log Z0) is assumed to be strongly convex and smooth (Eq. 17, 12).
Then in the annealing limit of a continuous path + oc, the estimation error of annealed NCE with the geometric puth is (at most) polynomial in the parameter-distance between the proposal and the target:
L
K² N
MSENCE P1: 91: K,N)
MN 10, 0011
+
(N)
+
when q =
(14)
where M and L are respectively the strong convexity and smoothness constants of log (()).
To our knowledge, this is the first result building on Gelman and Meng 17 Table 1] and Grosse et al.
18] which showcases the benefits of annealed estimation for a general target distribution.
We conclude that annealing with the near-universally used geometric path provably benefits noise- contrastive estimation, as well as importance sampling and reverse importance sampling, when the proposal and target distributions have little overlap.

---

4.3 Path parameter, geometric vs, arithmetic
Despite the near-universal popularity of the geometric path (q - 0), it is worth asking if there are other simple paths that are more optimal. Interpolating moments of exponential families was shown to outperform the geometric path by Grosse et al. [88] yet building such path requires knowing the exponential family of the target. Other paths based on the arithmetic mean (and generalization) of the target and proposal, were proposed in Masrani et al. [21], without a definitive theory of the estimation error.
Next, we analyze the error of the arithmetic path. We prove that the arithmetic path (g 1) does not exhibit the same benefits as the geometric path: in general. its estimation error grows exponentially in the parameter-distance between the target and proposal distributions. However, in the case where an oracle gives us the normalization Z1 to be used only in the construction of the path (we will discuss what this means in practice below), the arithmetic path can be reparameterized as bring down the estimation error to polynomial, even constant, in the -iitneter-distncee. We start by the negative result.
Theorem 4 (Exponential error of annealed NCE with an arithmetic path) Assume the proposal po is from the normalized exponential family, while the (unnormalized) target fa is from the simply unnormalized exponential family (Eq. 10p. The log-partition function log 70) assumed to be strongly convex (Eq. [7--
Consider the annealing limit of a continuous path K path and far-away target with large enough |10, - -00l > O. For estimating the log normalization of the (unnrrmalized) target density fú the estimation error of annealed NCE with the arithmetic path is (at least) exponential in the parameter-distance between the proposal and the target:
C N
M $10--0011 +
(1) (
1
K2 N
USSENCE(PoPPi.g K..
exp
+
wheng = (15)
where C. is constant defined in Appendix B.3
We suggest an intuitive explanation for this negative result. We begin with the observation that the estimation error (Eq. () depends the normalized path of densities. Suppose the target model is rescaled by a constant 100, so that the new unnormalized target density is (ar) x 100 and its new normalization is Zi 100. Looking at table 2 this rescaling does not modify the geometric path of normalized densities, while does the arithmetic path of normalized densities. Because the estimation error depends path of normalized densities, this makes the arithmetic choice sensitive to target normalization, even more so as the parameter distance grows and the log-normalization with it, strongly convex function of (Appendix, Eq. 94). This suggests making the arithmetic path of normalized distributions "robust" to the choice of Z1. We will show this can be achieved by re- ee-parameterizing the path in terms of Z1.
We next prove that certain reparameterizations can bring down the error to a polynomial and even constant function of the parameter-distanc between the target and proposal. The following theorems may seem purely theoretical, as if necessitating an oracle for Z1, but they will actually lead to an efficient estimation algorithm later.
Theorem 5 (Polynomial error of annealed NCE with an arithmetic path and oracle) Assume the same as in Theorem 4 replacing the strong convexity of the log-partition by smoothness (Eq. [2 Addition- ally, suppose an oracle gives the normalization constant Z1 to be used only in the reparameterization of the arithmetic path with t - 142,(1-1) (see Table 2 This brings down the estimation error of annealed NCE to (at most) polynomial in the parameter-distanee
(2 LI - 00.12) o (1)) +
K2
MSE (Po.P K, K)N) S N
when q = (16)
where I. is the smoothness constant of log 7())
In fact, supposing we have (oracle) access to the normalizing constant Z,, the arithmetic path can even be reparameterized such that it is the optimal path in a certain limit. We next prove such optimality in the limits of a continuous path K + co and "far-away" target and proposal [17]:
Theorem 6 (Constant error of annealed NCE with an arithmetic path and oracle) Consider the limits of continuous annealing path K + oc, and of target distribution whose overlap with the proposal
7

---

Path name
Unnormalized density
Normalized density
Error
Geometric
ft(x) = -pooo) -p0( ((())*
pr(x) x po po
"pi(a (x))
poly
Arithmetic
ft(x:) = (1 (0))p + (x)1(x)
Pr Pr(x) (1
Wz po (cx) (1))
vanilla
We =t
ū (1-1)+12)
121
exp
oracle
Wt 8+21(1-1)
ú; t
poly
sin
oracle-trig
Wtt sin?
0 sin? (
const
Zz cos?
Table 2: Geometric and arithmetic paths, defined in the space of unnormalized densities (second column); "oracle" and "oracle-trig" are reparameterizations of the arithmetic path which depend on the true normalization Z1. The corresponding normalized densities (third column) produce an estimation error (fourth column) which quantify.
goes to zero. Namely, consider the quantities:
= f c(xx)da
é' (x)) VPo(z))p
(17)
pracle (x) (ar)
/ I:' (((x)
(Oip (0 ddda
é' (x))
a 6= 220
Pt
oracle trig (2x)
Pt
oracle tris
(
(18)
e" (x) + 0,E e, + 0, and consider the distributions Assume s ex(x) - O, WERD arith-trt trig and preacl as defined Table 2
Pt
Then, the optimal annealing path convergences pointwise to an arithmetic path reparameterized trigonometrically with t (f (1((())((((()))) and the estimation error tends to the optimal estimation error (which is constant with respect to the parameter-distancee
1 =² + + co(=te)) ( N
K2 N
MSENCE(Po. PI:9.
+
when =1 (19)
N
N
By way of remarks, we note that the assumptions that the quantities sup ('z). sup d (z), c. c" go to O are mutually incomparable (i.e. none of them implies the others). For example, suPnERD e e((x) and going 0 require that the function / (x)))))p (ar) goes O in the Tox and In sense, respectively and these two norms are not equivalent in the Lebesgue measure.
Two-step estimation Thus, see that, perhaps unsurprisingly, the "optimal" mixture weights in the space of unnormalized densities depends on the true Z,: however, this dependency is simple. We propose two-step estimation method: first, Z1 is pre-estimated, for example using the geometric path; second, the estimate of Zı is plugged into the "oracle" or "oracle-trig" weight of the arithmetic path (table [ column 2), and which is used obtain second estimation of Z1. Note that pre- estimating problematic (haper)parammter, here Z1, has proved beneficial to reduce the estimation error of NCE in related context (36)
5 Numerical results
We now present numerical evidence for our theory and validate our two-step estimators. Importantly, we do not claim achieve state the in terms of practical evaluation of the normalization constants; our goal is to support our theoretical analysis. We follow the evaluation methods of importance sampling literature [18] and evaluate our methods on synthetic Gaussians. This setup is specially convenient for validating our theory: the optimal estimation error can conveniently be computed in closed-form, so too can the geometric and arithmetic paths which avoids sampling error from MCMC algorithms. These derivations are included in the Appendix B We specifically consider the high-dimensional setting, where the computation of the determinant of high-dimensional (covariance) matrix which appears in the normalization of a Gaussian, can in fact be challenging [37]

---

Numerical Methods
The proposal distribution is always a standard Gaussian, while the target
((0,0.25 Id) in Figure 3b and pi (0, x² Id) in Figure 3a where the target variance decreases as (i) = i-1 so that the (natural) parameter distance grows linearly [34 Part I1-4]. We use a sample size of N = 50000
differs by the second moment: 21 (0, 2 in Figure 2 Pi
points, and, unless otherwise mentioned, K + 1 = 10 distributions from the annealing paths and the dimensionality is 50. To compute an estimator of the normalization constant using the non-convex NCE loss, we used a non-linear conjugate gradient scheme implemented in Scipy [38]. We chose the sunjugate-gradise algorithm as it is deterministic (no residual variance like SGD). The empirical Mean-Squared Error was computed over 100 random seeds, parallelized over 100 CPUs. The longest experiment was for Figure 3b and took 7 wall-clock hours to complete. For the two-step estimators ("two-step" and "two-step (trig)"), a pre-estimate of the normalization was first computed using the geometric path with 10 distributions. Then, this estimate was used to to re-parameterize an arithmetic path with 10 distributions which produced the second estimate.
Results Sauuriiumriially supports the optimality of the NCE loss for a finite K (here, = 2 so three distributions are used) proven in Theorem [ note that the proposal distribution was normalized for this experiment, so that the log normalizing constant is zero. Figure 3 validates our main results for annealing paths. It shows how the estimation error scales with the proposal and target distributions growing apart, either with the parameter-distance in Figure Sa or with the dimensionality in Figure (bb] Using no annealing path (K 1) produces an estimation error which grows linearly in log space; this numerically supports the exponential growth predicted by Theorem 2 Meanwhile, annealing (K + oo) sets the estimation error on different trends, depending on the choice of path. Choosing the geometric path brings the growth down to sub-exponential, as predicted by Theorem 3 while choosing the (basic) arithmetic path does not as in Theorem 4 To alleviate this, our two-step estimation methods consist in reparameterizing the arithmetic path so that it actually does bring down the estimation error. In fact, our two-step estimators in table 2 empirically approach the optimal estimation error in Figure 3 While this requires more computation, it has the appeal of making the estimation error constant with respect to the parameter-distance between the target and proposal distributions. Practically, this means that in Figure 3a regular Doise-Contrastive Estimation (black, full line) fails when the parameter-din disttnee- between the target and proposal distributions is higher than 20, while our two-step estimators remain optimal.
We next explain interesting observations in Figure [ which are actually coherent with our theory. First, in Figure Ba] the "two-step (trig)" estimator is only optimal when the parameter-distame between the target and proposal distributions is larger than 10. This is because the optimality of this two-step estimator was derived in Theorem condiiiion on non-overlapping distributions, here achieved by a large parameter-distanee estimator empirically achieves the optimal estimation error that was predicted for the "two-step (trig)" estimator. This suggests our polynomial upper bound from Theorem [ may be loose in certain cases. This further explains why, in Figure Ba| the arithmetic path is near-optimal for single value of the parameter-distance At this value of 20, the partition function happens to be equal to one ((0)) = 1, so that the arithmetic path is effectively the same the "two-step" estimator.
Second, in both Figures [a and [bb the "two-step"
IS
RevIS- NCE
-0.2
0.0
0.2
Estimates
Figure 2: Optimality of the NCE loss, using the geometric path with K 2. NCE has the smallest deviation from zero, the true value of the log normalizing constant.
Related work and Limitations
which is a special case of our annealed Bregman estimator. They have evaluated the merits of different paths empirically, using approximation of the estimation error called Effective Sample Size (ESS) and the consistency-
Previous work has mainly focused on annealed importance sampling [88 39

---

0.0
no path
0.0
no path
MSE (log10)
optimal
MSE (log10)
optimal
geometric
geometric
-2.5
2.5
arithmetic
arithmetic
two-step
two-step
-5.0
two-step (trig)
-5.0
two-step (trig)
20
50 Dimension
100
Parameter distance
(a) MSE against parameter distance.
(b) MSE against dimensionality.
Figure 3: Estimation error as the target and proposal distributions grow apart. Without annealing, the error is exponential in the parameter distance (diagonal in log-scale), Annealing with the geometric path and our two-step methods brings down the error slower growth, as predicted by our theorems.
gap. In our analysis, we consider consistent estimators and derive and optimize the exact estimation error of the optimal Conse-Contraetive Estimation. Liu et al. [27] considered the NCE estimate for Z (not log Z) with the name "discriminance sampling". and annealed the estimator using extended state-space construction similar to Neal [TO]. Their analysis of the estimation error is relevant but does not deal with hyperparameters other than the classification loss. Other annealed estimators also
include annealed NCE as special case but with little theory on its estimation error 11 40 29
We made the common assumption of perfect sampling 11 18 41 42 in order to make the estimation error tractable and obtain practical guidelines to reduce it. We note however, that this leaves a gap to bridge with practical setup where the sampling error cannot be ignored; in fact, annealed importance sampling [TO] was originally proposed such that the samples can be obtained from a Markov Chain that has not converged. In this original formulation, AIS is a special case of larger framework called Sequential Monte Carlo (SMC) [43] in which the path of distributions is implicitly defined (by Markov transitions), sometimes even "on the go" 42]. Yet even within that theory, it seems that analyzing the estimation error for an inexplicit path of distributions is challenging 44 Eq. 38). In particular, samples from MCMC will typically follow marginal distributions that are not analytically tractable, thus the stronger assumption of "erffect sampling" is often used to make estimation error depend explicitly on the path of distributions [45] Eq. 3.2]. Even then, results on how the estimation error scales with dimensionality are heuristic [10] or limited by assumptions such as an essentially log-concave path of distributions or factorial target distribution
45
might also be argued that the limit of almost no overlap between proposal and target, which we use lot, is unrealistic. To why it can be realistic, consider the case of natural image data. A typical proposal is Gaussian, since nothing much more sophisticated is tractable in high dimensions. However, there is almost overlap between Gaussian data and natural images, which is seen in the fact that a human observer can effortlessly discriminate between the two.
More generally, many methods based on "annealing" were developed to deal with sampling issues. In fact, the path costs for two such methods, parallel tempering [46] eq. 17] and tempered transitions [47 eq. 18], can be written with sum of f-divergences which in the limit of a continuous path is the same cost function as our Theorem T This suggests our results may apply to these methods as well.
7 Conclusion
We defined class of estimators of the normalization constant, annealed Bregman estimation (ABE), which relies on a sampling phase from a path of distributions, and an estimation phase where these samples are used to estimate the log- oggnommalizttion of the target distribution. Our results suggest number of simple recommendations regarding hyperparameter choices in annealing. First, if the path has very few intermediate distributions, is better to choose NCE due its statistical optimality (Theorem Tp. If however, the path has many intermediate distributions and approaches the annealing limit, then TS enjoys the same statistical optimality as NCE but has the advantage of its computational simplicity. Annealing can always provide substantial benefits (Theorem 2). Moreover, if we have a reasonable a priori estimate of Z,, the arithmetic path achieves very low error (Theorem 5 sometimes even approaching optimality (Theorem 6). On the other hand, even absent an initial estimate of Z1, the geometric path can exponentially reduce the estimation error compared with no annealing (Thcorems 2 and
10

---

This work was supported by the French ANR-20- 20-CHIA-0016. Aapo Hyväri- nen was supported by funding from the Academy of Finland and a Fellowship from CIFAR. Andrej Risteski was supported in part by NSF awards IIS-221 1907, CCF-2238523, and an Amazon Research Award.
Acknowledgements
References
[1] Y. Song, S. Sohl-Dickstein, D.P. Kingma, A. Kumar, S. Ermon, and B. Poole. Score-based generative modeling through stochastic differential equations. International Conference on Learning Representations (ICLR), 2021.
[2] A. Hyvärinen. Estimation of non-normalized statistical models by score matching. Journal of Machine Learning Research, 6(24):695-709 2005.
[3] M. Gutmann and A. Hyvärinen. Noise-contrastive estimation of unnormalized statistical models, with applications to natural image statistics. Journal of Machine Learning Research, 13(11): 307-361, 2012.
[4] G.E. Hinton. Training products of experts by minimizing contrastive divergence. Neural Computation, 14(8):1771-1800, 2002.
[5] R. Gao, E. Nijkamp, D.P. Kingma, Z. Xu, A.M. Dai, and Y. Nian Wu. Flow contrastive estimation of energy-based models. 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 7515-7525, 2020.
[6] A.B. Owen. Monte Carlo theory, methods and examples. https://artowen: su. domains/ mc/ 2013.
[7] B. Liu, Rosenfeld, P. Ravikumar, and A. Risteski. Analyzing and improving the opti- mization landscape of noise-contrastive estimation. In International Conference on Learning Representations (ICLR), 2022.
[8] H. Lee, C. Pabbaraju, A.P. Sevekari, and A. Risteski. Pitfalls of gaussians as a noise distribution in NCE. In International Conference Learning Representations (ICI.), 2023.
[9] O. Chehab, A. Gramfort, and A. Hyvärinen. The optimal noise in noise-contrastive learning is not what you think. In Conference on Uncertainty in Artificial Intelligence (UAI), volume 180, pages 307-316. PMLR, 2022.
[10] R.M. Neal. Annealed importance sampling. Statistics and Computing, 11:125-139, 1998.
[11] C. Jarzynski. Nonequilibrium equality for free energy differences. Physical Review Letters, 78: 2693,, 1996.
[12] C. Jarzynski. Equilibrium free-energy differences from nonequilibrium measurements: A master-equation approach. Physical Review E, 56:501855035, 1997.
[13] R. Salakhutdinov and G. Hinton. Replicated softmax: an undirected topic model. In Neural Information Processing Systems (NIPS), 2009.
[14] Y. Dauphin and Y. Bengio. Stochastic ratio matching rbms for sparse high-dimensional inputs. In Neural Information Processing Systems (NIPS), volume 26. Curran Associates, Inc., 2013.
[15] V. Masrani, T.A. Le, and F.D. Wood. The thermodynamic variational objective. In Neural Information Processing Systems (NeurIPS), 2019.
[16] R. Brekelmans, S. Huang, M. Ghassemi, G. Ver Steeg, R.B. Grosse, and Makhzani. Improv- ing mutual information estimation with annealed and energy-based bounds. In International Conference on Learning Representations (ICLR), 2022.
[17] A. Gelman and X.- Meng. Simulating normalizing constants: From importance sampling to bridge sampling to path sampling. Statistical Science, 13:163-185, 1998.

---

[18] R. Grosse, C. Maddison, and R. Salakhutdinov. Annealing between distributions by averaging moments. Advances in Neural Information Processing Systems (NIPS), volume 26. Curran Associates, Inc., 2013.
[19] G.M. Torrie and J.P. Valleau. Nonphysical sampling distributions in monte carlo free-energy estimation: Umbrella sampling. Journal of Computational Physics, 23(2):187-199, 1977.
[20] X.-L. Meng and W.H. Wong. Simulating ratios of normalizing constants via simple identity: theoretical exploration. Statistica Sinica, pages 831-860, 1996.
[21] V. Masrani, R. Brekelmans, T. Bui, F. Nielsen, A. Galstyan, G. Ver Steeg, and F, Wood. q-paths: Generalizing the geometric annealing path using power means. In Conference on Uncertainty in Artificial Intelligence (UAI), volume 161, pages 1938-1947. PMLR, 27-30 Jul 2021.
[22] O. Chehab, A. Gramfort, and A. Hyvärinen. Optimizing the Noise Self-Supervised Learning: from Importance Sampling to Noise-Contrastive Estimation. ArXiv, 2023. doi: 10.48550/arXiv. 2301.09696.
[23] M.A. Newton and A.E. Raftery. Approximate Bayesian Inference with the Weighted Likelihood Bootstrap. Journal of the Royal Statistical Sociery. Series (Methodological), 56(1):3 48, 1994.
[24] A.W. van der Vaart, Asymptotic Statistics. Asymptotic Statistics. Cambridge University Press, 2000.
[25] M.-H. Chen and Q.-M. Shao. On monte carlo methods for estimating ratios of normalizing constants. The Annals of Statistics, 2564):1563-1554, 1997.
[26] M. Uehara, T. Matsuda, and F. Komaki. Analysis of noise contrastive estimation from the perspective of asymptotic variance. ArXiv, 2018. doi: 10.48550/ARXIV.18000 007983.
[27] Q. Liu, J. Peng, A.T. Ihler, and J.W. Fisher III. Estimating the partition function by discriminance sampling. Uncertainty in Artificial Intelligence (UAI), 2015.
[28] A. Hyvärinen, J. Hurri, and P. O. Hoyer. Natural Image Statistics. Springer- Springer-Verlag, 2009.
[29] O. Krause, A. Fischer, and C. Igel. Algorithms for estimating the partition function of restricted boltzmann machines. Artificial Intelligence, 278: 103195, 2020.
[30] S. Chatterjee and P. Diaconis. The sample size required in importance sampling. arXiv: Probability, 2015.
[31] B. Efron. Exponential Families in Theory and Practice. Institute of Mathematical Statistics Texthooks. Cambridge University Press, 2022. ISBN 9781 108488907.
[32] B. Sriperumbudur, K. Fukumizu, A. Gretton, A. Hyvärinen, and R. Kumar. Density estimation in infinite dimensional exponential families. Journal of Machine Learning Research, 18(57): 1-59, 2017.
[33] O. Krause, A. Fischer, T. Glasmachers, and C. Igel. Approximation properties of dbns with binary hidden units and real-valued visible units. In International Conference on Machine Learning (ICML), 2013.
[34] F. Nielsen and V. Garcia. Statistical exponential families: A digest with flash cards. ArXiv, 2011. doi: 10.48550/anXiv.091 1it.rxxiiii.11666....
[35] X.-L. Meng and S. Schilling. Fitting full-information item factor models and an empirical investigation of bridge sampling. Journal of the American Statistical Association, 91(435):
1254-1267, 1996.
[36] M. Uehara, T. Kanamori, T. Takenouchi, and T. Matsuda. A unified statistically efficient estimation framework for unnormalized models. International Conference on Artificial Intelligence and Statistics (AISTATS), volume 108, pages 809-819 PMLR, 2020.
12

---

[37] L. Ellam, H. Strathmann, M.A. Girolami. and I. Murray. A determinant- method to simulate the parameters large gaussian fields. Stat, 6:271-281, 2017.
[38] Virtanen, R. Gommers, T.E. Oliphant, M. Haberland, T. Reddy, D. Cournapeau, E. Burovski,
P. Peterson, W. Weckesser, J. Bright, S.J. van der Walt, M. Brett, J. Wilson, J.K. Millman, N. Mayorov, A.R.J. Nelson, E. Jones, R. Kern, E. Larson, C.J. Carey, I. Polat, Y. Feng, E. W.W. Moore, J. VanderPlas, D. Laxalde, J. Perktold, R. Cimrman, Henriksen, E.A. Quintero, C.R. Harris, A.M. Archibald, A.H. Ribeiro, F. Pedregosa, P. van Mulbregt, and SciPy 1.0 Contributors. SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nature Methods, 17: 261- 2020.
[39] T. Kiwaki. Variational optimization of annealing schedules. ArXiv, 2015. doi: 10.48550aarXiv 1502.05313.
[40] R. M. Neal. Estimating ratios of normalizing constants using linked importance sampling. ArXiv, 2005. doi: 10.485500arXii.maa//55511 12266.
[41] R. Brekelmans, V. Masrani, F.D. Wood, G. Ver Steeg, and A.G. Galstyan. All in the exponential family: Bregman duality in thermodynamic variational inference. In International Conference on Machine Learning (ICML), 2020.
[42] S. Goshtasbpour, V. Cohen, and F. Perez-Cruz. Adaptive annealed importance sampling with constant rate progress. In International Conference on Machine Learning (ICML). volume 202 of Proceedings of Machine Learning Research, pages 1 11642-11 11688. PMLR, 2023.
[43] N. Chopin and O. Papaspiliopoulos. An Introduction to Sequential Monte Carlo. Springer Series in Statistics. Springer International Publishing, 2020. ISBN 9783030478452.
[44] P. Del Moral and A. Doucet. Sequential monte carlo samplers. Journal of the Royal Stutistical Society: Series (Statisticul Methodology), 68, 2002.
[45] C. Dai, J. Heng, P.E. Jacob, and N. Whiteley, An invitation to sequential monte carlo samplers. Journal of the American Statistical Association, 117:1587-1600, 2020.
[46] S. Syed, V. Romaniello, T. Campbell, and A. Bouchard-Cote Parallel tempering on optimized paths. In International Conference on Machine Learning (ICML), volume 139 of Proceedings of Machine Learning Research, pages 10033-10042. PMLR, 2021.
[47] G. Behrens, N. Friel, and M. Hurn. Tuning tempered transitions. Statistics and Computing, 22: 65-78, 2010.
[48] M. Pihlaja, M. Gutmann, and A. Hyvärinen. A family of computationally efficient and simple estimators for unnormalized statistical models. Uncertainty in Artificial Intelligence (UAI), 2010.
[49] L. Wang, D.E. Jones, and X.-L. Meng. Warp bridge sampling: The next generation. Journal of the American Statistical Association, 1 117(538):85-8511,22 202..
[50] H. Xing. Improving bridge estimators via f-GAN. Statistics and Computing, 32, 2022.
[51] Y. Polyanskiy and Y. Wu. Information Theory: From Coding to Learning. Cambridge University Press, 2022.
[52] S.-L. Amari and H. Nagaoka, Methods of information geometry. AMS, 2000.
13

---

Appendices
In the following, will study the estimation error of annealed Bregman estimation (ABE) in two important setups: the nog-oormalizatin is computed using two distributions (K' = 1), the proposal and the target, or else using path of distributions (K - oc).
The code used for the experiments available at https://github: wtt.g/hhhw...cccooaaaaaehhhhhhaa annealing- wwwiiinnnooomaiaai normalizing- constants
A No annealing, K =
We use 22 Eq.21] for the estimation error of any suitably parameterizzedFllassiiii F(2;; 33 between two distributions P1 and Pu- The estimation error is measured by the asymptotic Mean-Squared Error (MSE)
U, Φ5 N) ++ Lr 2)
1 N
MSE & (pm:
(20)
which depends on the sample sizes N = N1 + No. their ratio v = N1/No. the Bregman classification loss indexed by the convex function (xx), and the asymptotic variance matrix
Σ == [L. (1 m. L
(21)
We suppose the standard technical conditions of van der Vaart (24 Th. 5.23] apply so that the remainder term || - 1 can indeed be written independently of the parameterization, as oNN-)). Here, m (B**) (G*) and (3*)) are the reweighted mean and covariances of the paramete-
gradient of the classifier, also known as the "relative" Fisher score (2;
(G*) Em (x aE; [*)]
(22)
Iu (,8") = Ea- ( (x; 3r) (x;
(23)
(,()) = Ex-pa [2<)) 8*) VzF(z:
(24)
= where the reweighting of data points is by w(x) == i (x)Ø (mm (x)) and by v(x)
w(x)) (() which are all evaluated at the true parameter value 3 (2)
Scalar parameterization
We now consider specific parameterization of the classifier:
f1(())
F(x; B)
log
(25)
where the optimal parameter is the log-ratic of normalizations 3 = log (1 /Zo. Consequently, we have V F x;; (*) -1 and plugging this into the above quantities yields
E Eaaep [w2 (x: (p) (mx)
MSE + v T
(po(#)
(1 ()) + (
Ex-p, (²)
which matches the formula found in (20 Eq 3.21. For different choices of the Bregman classification loss, the estimation error is written using divergence between the two distributions
Name
Loss identified by ((x))
Estimator
MSE, up to o(N-1)
IS
x log
fi log Ep
1 1+2 DegD (pe,p1)))) EN
Fo
RevIS
log x
log Ep, f0
1t D, (po, P1))
NCE
x ælog. x (1 + x)) log( 1+x
implicit
(1+v)² DuM .Po)
1-Duxx(P1.po
IS-RevIS (1 - /2
log Epp To
f log Ep, fo (Ltv)² 1- p.. (1-1 (pa.p.))
'tecnnicall, the formula was derived in 48 3 assuming the classifier was parameterized as F(;;; (9) log pi (æ;
(x:3)/ppo(( /p)ppp((c))))
but the proof to generalize any well-defined parameterization F(x;3)
14

---

where
(p:(Pi:P)) = (ʃ Pi) 1 is the chi-squared divergence
(PI.P)o))) = 1- (f \PPpo) E [0, 1] is the squared Hellinger distance (mpp) (PI( = ( + (1 ) =
1 E
PPp
E [0, 1]
(1-=)pitapo
is the harmonic divergence with weight [0. 1]. Here, the weight π P(Y 0)
Proof of Theorem Exponential error of binary NCE
In the following, we will drop the remainder term in o(N-t) given that no other limits are taken and that we will study the dominant term only. The estimation error of binary NCE is expressed in terms of the harmonic divergence
DHM Po)
MSF
(26)
DHM
which is intractable for general exponential families. Instead, we can lower-bound the estimation erro. To do so, we lower-bound the harmonic divergence using the inequality of means (harmonic vs. geometric)
(HM.PILPO) = - -f
2poP1 21 21- Vpopi = DD (Po. Po + P1
(27)
and therefore
(H=(P1,P)
MSELB = N - D (P1.
(28)
This lower bound expressed in terms of the squared Hellinger distance, that is tractable for exponential families:
/
(p1. :=
"EERD PiPpda
(29)
1 (0: + +00) dx
=1 JUERO Z(0,)
exp
(30)
Z(36: + 110)
(31)
((0))
1 - exp log Z
01 + 2
00
1
log Z(0i) log 2(0o)
(32)
We now wish to lower bound MSE,B. and therefore (H=(PI,PoN Po). by expression which is expo- nential the parameter distance ||0; Ooll. To do so, we note that for exponential families, the log-normalization is convex in the parameters. Here, we further assume strong convexity, that
log z 2 _0o)
1 log Z(O1) + log Z(Oo) M || 0ol
(33)
2
where M is the strong convexity constant. Plugging this back into the squared Hellinger distance, we obtain
DHa(Pi,Po) 2 10--00 -exp ( M 0ull?
(34)
so that the MSE
D DHr(PI,PM) N 1 - He (PI.Po)
N exp L M -0012) -
4
MSE
(35)
grows exponentially with the euclidean distance between the parameters.
15

---

B Annealing limit, K - ac
We now consider annealing paths (Pr)eefo.1) that interpolate between between the proposal po and the target P1.
B.1 Estimation error
We first show the optimality of the NCE loss within the family of Annealed Bregman Estimators, in the sense that it produces the smallest estimation error. We then study the estimation error of different annealed Bregman estimators in the annealing limit of continuous path (K - (O).
Proof of Theorem K 00
1
Optimality of the NCE loss and the estimation error in the annealing limit
Optimality of the NCE loss
Because the annealed Bregman estimator is built by adding independent estimators
K-1
2(x+1)/K
log 71
Σ
log
+ log Zo
(36)
Zu/K
k=0
the total Mean Squared Error (MSE) is the sum of each MSEs for each estimator (indexed by & E [0, II)
MSE(((+))<(oo.n))
Σ (oE+(
(37)
where we highlighted the dependency on the classification losses identified by (dx (ox)keTo.Kg K]
The MSEs follow Eq. 26 It was shown by Meng and Wong (20) that for any of these MSEs, the optimal loss is identified by OR (z) log (1 + x) log( 1+æ) and is in fact the NCE 2
loss 222. Thus the sum of MSES is minimized for the same loss.
Annealed Noise-Contrastive Estimation (NCE)
We are interested in the estimation eπror (asymptotic MSE) obtained for the NCE loss. Based off table written as
4K DinM(Pk/K.PO--D
K
MSE
(38)
N PANM(PE/KPPO---11
N
R=0
4K
K-1
DHN(DPy/KPPHHY/// -
K2
+ 0
(39)
N
DHM (PM/KK/KK P(K+1)/K)
N
k=
where a sample budget of N/K
Ki is used for each estimator that summed. The estimation eтror of balanced (v 1) NCE-JS between two "close" distributions pt and Pt+h. is
(PM (Pe
MSE(Pt, Pt+h) & 1- DHM Pt+k)
(40)
up to the remainder term. The estimation error can be simplified using Taylor expansion.
To do we recall that DHM is an f-divergence generated by Φ(x) = 1 #+(1-a)
49
50
( = here) and its expansion is therefore [3]] Eq. 7.64.
Dum(Pe.Pet P(+h)
h 2 (PMt o(h2)
(41)
1 8" (1))2T(1)++++ o(h)) 11 1121(()) + o(h2)
(42)
2
It follows that
DaM (en.(pePPecc P(+h)
1(t)h² + o(h?)
(43)
1 DHiappe,Pee Peth)
16

---

Summing these estimation errors along the path of distributions with h = 1/K,
4k K-1
+ (k2))
K2
MSE
Σ
[(t)
(44)
N k=0
4
K²
K-1
1
K2
Σ
(tt)
+ 0
+o
(45)
NK k=0
N
N
1 N
K2
I()dt
o
(46)
In the case of a parametric path p(æ (e))) the proof the same, Simply, the second- order term in the Taylor expansion of Eq. 42 is computed using the chain rule
V/MSE(POL)) Po(t+)))
(47)
= O(() PDCC)))) O(t) PoMSE((proo
(48)
=0(() VAMSE(yon,, (()) +0
(49)
((O(t))0()
(50)
Annealed importance sampling (IS)
Similarly, for the choice of the importance sampling base estimator,
K-
2K
K
MSE =
Dx (P(+4))/K.P//K) +
(51)
N
N
k=0
2K
K-1
K2
(52)
N
N
2K
K-1
K22
Drevx (Poxx(PP//.P//-111/ +0 (T)
(53)
N
2K
K2 )) +
11
K2
2 ④ (1)I(t)
+o
(54)
N
K2
N
R=
1
(L))())) + to (
1
K²
(55)
NK
N
N
1
K2
I(I)dt + + 0
(56)
N
N
given that ((x) = - log(z) and therefore & (11 = 1 for the reverse X2 divergence.
Annealed reverse importance sampling (RevIS)
Similarly, for the choice of the reverse importance sampling base estimator,
K-1
2K
K
MSE- Σ
D
+
(
(57)
N
N/
2K
K-1
1
K2
(1)T(()
+ 0
+
(58)
N
K2
R2
N
k=
1
K-1
1
R2
1
/ I(t)dt +
1
K2
I(t)
+
+
+
NK
N
N
N
N
N
0=
(59)
given that 6(x) x log(z) and therefore o"(1) for the x² divergence.
17

---

B.2 Examples of paths
Geometric path The geometric path is defined the space of unnormalized densities by
fi(z) == po po( f1(='* = (((=))""((<)'""" zi o po(=)) 1-t ''i (x))
(60)
so in the space of normalized densities, the path is
Pt po( "p1)''ppppp (x)
(61)
Z₁
where the normalization is
[ (Po(2))
'1 Exorpo
[ po
Pr (ax)
Z: =
po(x))=pp1(a) (1)) = Eoapi
(62)
JaER
P1 (x))
Arithmetic path
The arithmetic path is defined in the space of unnormalized densities by (1 !)po + 1Zipi
fe(x)) :- (1 (a)) + (z(()))
(63)
(1-6) & (1- Po [1 (1- t) t P1
1Z
(64)
so in the space of normalized densities, the path is actually mixture between the target and the proposal, where the weight the mixture is a nonlinear function of the target normalization
tZ
Pt - T + W.PI,
(65)
(1 11-1 + 17
Optimal path
We know (e.g. from Gelman and Meng 17 Eq. 49] that the optimal path is
(a)) (a(t) (a(t))/o(zz) po(x) b(t)) b(t))/ (x)))
(66)
where the coefficients a(t) and b(t)
a(t) cos((2t 1)aH)
sin - 1)aH)
(67)
2 200s((r11)
2 2sin(an)
b(t) = cos((2t (1)ax-
sin((2t 1)ax)
(68)
2 2co((a
2 sin((H))
simple functions of the squared Hellinger distance DH (po, between the proposal and the target
(V
D n² (Po, Pi)
[0, "
06 arctan
(69)
2 D DHr (Po, P1)
The estimation error produced by that optimal path is 11 Eq. 48]
1 N
( [(t)dt
1
MSE
16a
(70)
N
For two Gaussians
Do N(Ho, En)
(71)
Pi = N(ui En)
(72)
the squared Hellinger distance can be written in closed-form
DH=(Po,Pi) pi) = Eo 1 E
exp (- [ m0) T + 21) (m vo)
(73)
E + 1
and plugs into optimal path formula, which is also obtained in closed-form.
'In Gelman and Meng 11 Eq. 49], the Hellinger distance defined such that is in [0, v2). We here instead use the conventional definition of the squared Hellinger distance which is normalized so that it is in [0, 1].
18

---

B.3 Estimation error from taking different paths
Proof of Theorem Polynomial error of annealed NCE with the geometric path
We next study the estimation error produced by the geometric path (Figure 1). In the annealing limit K + oc, the MSE is written
MSE N/ S. T(I)dI + of N
K N
(74)
We recall from Grosse et al. 18] that the geometric path is closed for distributions in the exponential family: all distributions along the path remain in the exponential family. Furthermore, their Fisher information can be written in terms of the terms parameters [18 Eq. 17]: this is based off a result
of exponential families from [52 Section 3.3]
[(t) O(t) T ((O()))(t)) = O(t) (a(t)
(75)
where pa(1) are the generalized moments, defined as p(l)) = (= = Vo log (0). follows,
1 1 L. I(t)dt = N I T(t) (u(t)dt.
(76)
N
The geometric path is defined in parameter space by 0, 10, + (1 - -1)0, therefore
1 / (t) =
1 N (0, 0o)T I' jittdtt N ( - -0) (#1 (40
(77)
N
in 118 Eq. 17]. For exponential families, log (()) is convex in O. Here, further assume strong convexity (with constant M) and smoothness (with constant L) so that
(0 0o) (J11 40) = (01 0o) T (Vo log (6)) - Vo log (0)))
(78)
L
< M
V log (0) Ve log (000)) <
0 - 0oll
(79)
M
so that the MSE
I
K2
MSE
00 - 0ol1 +
+
(80)
MN
N
is polynomial in the euclidean distance between the parameters.
Proof of Theorem 4
Exponential error of annealed NCE with the arithmetic path and "vanilla"
schedule
We now study the estimation error produced by the arithmetic path with "vanilla" schedule (table 2 line 3). Similarly, we start with the formula of the estimation error of NCE in the limit of a continuous path
MSE- N 1. I())d + ( ( +
1 (((10
K² N
(81)
where I(t) Ex-pp(a))) [[ dt log [) is the Fisher information over the path, using time as the parameter. The arithmetic path is Gaussian mixture (see table so we will conveniently use the parametric form of the path to compute the Fisher information
(82) where the parameter here is the weight of the Gaussian mixture i; = /tz ( 11 t). We will need compute two quantities: the Fisher information to that mixture parameter (not the time), and the parameter speed in.
I(t) o I(w,
(
(log Pm. (z)
= Euapss [/5010 Öp:r (z) 2 Pei (x) Sw,
I(w)) = Exappi
(83)
Ori (pi(w) po(
(x)) - p)(
dx
da:
(84)
JEERD
Pio. (x:)
JMEZO (1 Wh (2:) + WiPi (x:)
(pi(x) Po (2
(1
(1))) 2
dx
po(xx)
po(m)
Do(
(85)
WERD
Pu( + p1 (z)
1 (a)
(a)
19

---

which is an f-divergence with generator ó(x) = (1 - 2)2/(1 + x)) that provides t-independent lower bound. This will allow us factor this quantity out of the integral defining the MSE, and simplify computations. We also have
0
1.71
x (1- - o( log 171
12,) ))
01 W1
X
log
1-1)
(86)
1(1 (1-
1
1Z1
(1 (1-t) t)
Z1
(87)
1(1 1) (1 1) + 17 (1 - 1) + 171 ((1 - 1) + 12
where we choose to keep the dependency on t. The intuition is that integrating this quantity will yield function of 71, which will drive the MSE toward high values. We next show this rigorously and finally compute the estimation error.
1 N L I(t)dt N S. (()((())((
1
(88)
1
x DolPI.Po) x *f =(())dtt
2 N
(89)
1
x Do(P1.Po) x 17 x '/¹
5 (t(Z) - 1) + 1) dl
(90)
N
77 + 7 +1
X Dolpi.Po) Po) x 7 x
991)
N
323
x Do Po) (2 + 1 Z1)
(92)
3N
We would like to write Z1 in terms of the parameters. To do so, we now suppose the unnormalized target in simply unnormalized exponential family. Consequently,
Z1 == exp(log Z(0,) - log Z(0)) + log Z(Ou))
(93)
V log Z ((6,) (0, - 0n) + 2 0, 0nll2 + log Z(0b))
M
2 exp
(94)
using the strong convexity of the log-partition function. For large enough 10 0oll > 0, the quadratic term in the exponential is larger than the linear term, and the divergence (P1, po) is
larger than constant. It follows that for large enough ||0, 0 > 0, there exists a constant C' > 0 such that the MSE grows (at least) exponentially with the parameter-distance
C MSE
M 00,
0o 0)1))
+ (
)
K
exp
(NN
(95)
3N
Proof of Theorem 5 schedule
Polynomial error of annealed NCE with the arithmetic path and "oracle" "
We now study the estimation error produced by the arithmetic path with "oracle" schedule (table 2 line 4). Similarly, we start with the formula of the estimation error of NCE annealed over a continuous path
N \.' I(t)dt + o (
1
/''
1 N
K2 N
MSE-
+
(96)
where (tt) = Exe-p(ae,)) 11 nt log p(æ, t)) is the Fisher information over the path, using time & as the parameter. The arithmetic path is the Gaussian mixture (x())) = (pI + (1 - (x) (see table 2h. The Fisher information is therefore
[( (ologri P: (x) ) = Exewps [( Øt
(x( ( ap. Oi (x)) '1
((t) = Ex-re
(97)
(p)(x) (mr
Po (2) dat
(p)(x) - po(2)))2
1) + tp (x) dx
(98)
MERO
WERD
pi (x:)2 + po (2)) dx:
<
(99)
(1 - (2) + tp (x:
ZEED
20

---

where we choose to keep the dependency on f in the bound.
We briefly justify this choice. We had first tried l-independent bound, which led an upper bound of the MSE that was too loose. We share insight as to why: first, recognize that the fraction can be broken in two terms, each of them chi-square divergence between an endpoint of the path (po or P1) and the mixture Each of them admits a t-independent upper bound given by the chi-square divergence between the endpoints po and pt. using lemma I However, the chi-square divergence between two Gaussians, for example, is exponential (not polynomial) in the natural parameters [51] eq 7.41]. In fact, plotting [tt) for univariate Gaussian model revealed that it took high values the endpoints t = O and = 1, and was near zero almost everywhere else in the interval t E [0, 1], which again suggested that dropping the dependency on was unreasonable.
Now we can compute the estimation error, as
N J. (t)dtt S N/ Stal So (I (1- ())o()) + tpi(p1t (x))
1 N
21 + Po (x))
1 N
dtdæ
(J1 + J2).
(100)
Let us try to solve one of these integrals, say J1
J1 / L' (1 - 1-))p())) + 1p1 (x:
pi (x))
(x)))
1
dtdx
JRc (o)
dt do (101)
JRd
1 t(
Pi (0) po(
(xx))
21 log
1
P1 Po
dx 1 1 E
log
1 D Doloo. P1)
Rdd (x(
Bo
Po
Po
(102)
which we rewrote using an f-divergence defined by ((x)
log(w) I-
Similarly, we obtain
J2 1 So (1 ()))( + tp (x))
po(x))²
po pa
dldæ Juc (x)
) )a
di
Po(a) (1
+ t(1
mo(2))
P1 (z)
(103)
po(x))
= 2z Pi (x)
log
Pa P1
dx -1+ 1+
Pio
P1
log
P1
Po
= 1 + Do
P1
Pu
(104)
Putting this together, we get
1
1 L. I(t)dt 5 N (2+ p1) + Dolp,,
(105)
N
How does this divergence depend on the parameter-distance ||0 - 0n|l? Does it bring down the dependency from exponential something lower? We next analyze this:
P1
D (po Pi) + 1 Ep
log
Pa
po
which looks like a Kullhack-Leeibler divergence, where the integrand reweighted by that
Note
20
po( S p1 (z:
Pig (w))
P1 (w))
(106)
po( > pi (x)
2a (w))
which motivates separating the integral over both domains
1 + (aa [(0E3P/o(eesspmte))) Pi (x) log
Pi (a)
=
Po(
po(=)
(107)
(w)
/ pi ( log
P1 (zx
1
(108)
po( 1
(ar)
p1 (1))
Pr (2)
(1( +
Pr (x) log
(109)
(WERD | (x))))
po(
< 11 DKI. (p1.
(110)
21

---

Hence we get
1 N J I(t)d S N (2 (KI.po,P1 pi) (RI,(I,,
1
(111)
We now suppose the proposal and target are distributions in an exponential family. The KL divergence between exponential distributions with parameters 0g and 01, given by the Bregman divergence of the log reg-patiiioon on the swapped parameters [34, Eq. 29]
(PL P1)
D Bregman
(01, 00) log (() log ((0) V log ((0)) 0o)
(112)
log
L
$ 01 0ul1
(113)
Hence
x (2 0| -b0 + of 11 N
K2 N
MSE < N
+
(114)
using the T-smoothhess of the log-partition function log 2(0).
Discussion on the assumptions for theorems 2 3
For these theorems, have supposed that the target and proposal distributions are an exponential family with log partition that verifies
M Id log ( < I.Id
(115)
We now look the validity of this assumption for simple example: the univariate Gaussian, which is in an exponential family. The canonical parameters are its mean and variance (p,, v). Written as an exponential family,
p(x) == exp))= t(z)) log Z()))
(116)
the natural parameters are 0 = (u/U, - 12v)))). associated with the sufficient statistics t(x) The log- partititioo function and its derivatives are
(xc, x²)
07
log Z(0)
log( (200)
(117)
402
V log Z(0) Egup [t(r)] (
01
1
07
(118)
202
20
402
81
- log Z(0) Var z-pp [tx)]
20
1
02
02
2pp
2pv
2
2pm
42²
(119)
02
02
2 02
When the mean is zero, the eigenvalues of the hessian are in fact the diagonal values (v, 20²). and they are bounded if and only if the variance v is bounded.
22

---

Proof of Theorem 6 schedule
Constant error of annealed NCE with the arithmetic path and "oracle-trig"
We now study the estimation error produced by the arithmetic path with "oracle-trig" schedule (table 2 line 5). We write the optimal path of Eq. [66 in the limit when the distributions have little overlap, pointwise (with error ) and on average (with error e):
(pll))p (2) = é (x)
(120)
Po (1) (x))d== (x =
(121)
We briefly note that there exist certain conditions, given by the dominated convergence theorem, where the first error (pointwise) going zero implies the second (on average) going to zero well,
but this is outside the scope of this proof. Now, many relevant quantities involved in the optimal distribution and its estimation error simplify as c (ax) - 0 pointwise and - 0. The notation (+) will hide dependencies on absolute constants only.
Dz= (po, pI) = 1- - f VPOPi
(122)
0H == arctan (V2-
π
+ o(c)
(123)
2 DH (po. p1)
4 2
0r == c2s -1)aH) sin((2t - 1)ah) cos 2sin(an))
xt
(2)
+
E(l
sin
+ oot))
2 2con(
2
(124)
cos( - 1))H))
sin( - 1)a8) sin
πt
b. 2 200s(am)
et cos
(5)
+ o(e)
(125)
2sin(an) sin(an)
2
2
sin((2t 1)aH)
cos((2t - 1)(H))
0,a, = -an
(126)
cos(an)
π sin
nt
nt
+ π (t - 1) cos Tt
)
) + o(e)
+ sin
(127)
2
2
2
2
sin sin (2t 1)aH)
cos( 1)aH)
o,b, = -aH
(128)
cos(ar
sin(an)
π
nt.
π
nt - cos ( + o(e)
Tt
=
cos
+ e
ssin
(129)
2
2
a. x 0.a:= ==
π
sin sin(Tt) +
sin (T) + π
2 (t - 1) cos(TTt) + o(E)
(130)
2
Ot x 0,b, = cos?
2
(
πt
+
(22(1
ạ (1-
- 21) sin(T() + cos(TT) + +1) + o(e)
(131)
2
π
2 nt
(1
1
1
+ sin(TT)((E - 11) + o(e)
1 π
by x 0:a:= ==
sin?
+ E
cos(It)
(132)
2
2
2
2
2 2
b x 0,b; == π
sin(TT) + E
1
sin(mt)
म マーヒ cos( ( + o(e)
(133)
2
This leads to the following simplification of the optimal path
= a(t)) px) := (at (ov/pol)) + =(t b(t)))(())) (((])))pp(()+()))((e)))) + (a(t))(t))(z))
(134)
aat))po(<)) + b(1))p + 2a(t)b(t)) (m:
(135)
= cos? nt. Po (2) + sin
πt
Pr (z) + é' (x:)
(136)
2
+ =
1) pı (z)() +c (1) 21) cos(It) - 1) + o(c)
(137)
arith trig (z) + 0('( (z)) + (z)
(ri)t
(138)
23

---

where we denoted by
arith frith-trig (a:) == cos
at 2 )o(
+ sin?
nt ( P1 (a)
(139)
the arithmetic path with "oracle-trig" schedule defined in table 2 (line 5) the trigonometric weights in evolve slowly at the end points = 0 and t 1. We also define 91 (a) = sin (n)( (po())) (a) - 11 (x))t) which is integrable function. This proves the first part of this theorem, which is that the optimal path popt is close to certain arithmetic path (with trigonometric weights) parich trig, and that closeness is controlled by how little overlap there is between the endpoint distributions po and Pt, average and pointwise.
Similarly, we can control how close these two paths are in terms of estimation errors. The estimation error in Eq. produced by path is
1
[ I(t)dt to ( +
k
MSE: = N
(140)
N
1
|
['" (0e logg Pa (ax +
1
K2
+
(141)
N
RD
N
N
1
1 RD
( Pt ((()dddd + of pr(
1 N
K2
+
(142)
N
We denote by MSEoptimal and MSEarith-trie the estimation errors produced respectively by the optimal path and the arithmetic path with trigonometric weights. The estimation error of the optimal path can be Taylor-exaaneed in terms of the overlap (e and (æ)) as well. We next compute the intermediate quantities that are required to obtain the estimation error.
O.p; opt (x)) = a. ( /o (e
(143)
2(0rar po(x) + 0,b, P1 (2)) po(ar) ())p((0))
(144)
= =2pn(0) (a: x 0,at) + 2p1 (xr) (be x Ocbi)+
(145)
2 po((0)) (xr (Oru: x be + ar x 0,b:)
(146)
= P1 (x) Pu(
cos( / (x))) +e (si((t) att 1) coss((t)) + p1 (2)) sin(nt) nt cos((Tt))
(147)
2
(148)
(1)( (s)n)))))))))(( 21 π + cos(TT) + +3)) + o(E)
(149)
sinn(T)) PI (1) po(x))
O (m)) O(egz(x))
(150)
2
0.p. arith trig (x) + O(e' (x)) + O (x))
(151)
where 92(x) = (=) (in((t)) + ( cos(((t))t + p1 (x) sin(nt) - nt cos(stt) is an integrable
function. It follows,
(0.p)(x))² (d.re arith trig (x) trith + ( (z:) ( (m)))
(152)
(0.p) arith arith- uri (rith-
O (æ)) + (x))(()))
(153)
by expanding and using that a.p.rith- trrith-trii (x) π sin( ( is bounded that O.p. weith-trig (x)) x é (x) = O(e' (x)). Moreover.
Pt (x)
Pt
arith trig (x) + 0('' (m)) + (x)))
Pt
arith
(x:) 1 +
Old (((((x))) (x)) arich tig (x)
(154)
24

---

Denoting by e" (x) := (O(e'(z)) + (egn (x))) arith trig
(xx) (rith
third quantity which we assume
goes zero, we get
OlE (x))
(155)
Pt
opt
(x)
Pr.
arith tris (x)
Pt
arith trig (2)
We now write
(āe lz)) x pr(x)) (OrPo(a)))
(156)
(x))
= (0.p (x))
+ OO' (x)) + ((02((0)) x parith trig (x)
+
O (z:)
(157)
Pt Pr prich-trig(x))
(0.p) arik (x))
Ole' (x+) + (())((z))
(Oep) friich-rriee (z)) ?
arith (x) OiE (x))
(158)
Pt Arith (x)
arith Sritth-riR(an (x)
Pt
Pt
(3:P) trip (m))
+ O(e (z)) (a)) 1+
(d.p,
arith h (sx)) ?
(159)
Pt prithh (x)
arith arith-trig (x)
Pt
by expanding. We can then write
MSEoptimal
(160)
(0e);"((e))' (x))
didx + 0
1 (1) + +o
K2 N
N LD J
(161)
Pt
('¹
arithh (2))
arith (ric dtdx pt prich trish (x)
+0(c" (O(c(())(( (1+
(162)
Jzp
Pt prith-triig (x)
1
+
(163)
N
N
1
{
( O(E" ((E"(z))) (1+ (Oep
arith (ri)) dtdx + o (N) o
K22
MSEarith-trig +
N gD
arith urig (x)
N
(164)
-SSarith- + +
{ N
K² N
+
(165)
Additionally, we assume that the remainder term denoted by
Ole" (1)) [1+ (One
(x)) 2
E 1/1 === O001e
o(c"(=))(
dtdæ
(166)
arich-trig (x)
Pt.
is integrable and also goes zero. On the other hand, the estimation error produced by the optimal path is known 17 Eq. 48] and the result can be Taylor-expanded as well
1
1 N
K²
MSE optimml
N
16a
+0
+
0
N
(167)
1
K2
16
+
+((()
+ 0
+
(168)
N
16
N
N
1
c
K2
+
+
(169)
N"
N
N
N
This means that
2 + 0 (
+ 0 1 ((1
) + (
K22
+ o
E
MSFarith-tre trig
N
N
N
N
(170)
25

---

C Useful Lemma
Lemma 1 Chi-square divergence of between a density and mixture We wish upper bound the chi-square divergence between distribution p(æ) and mixture wp(x) + (1 - w)g(x),, where
11
p(x)²
(p, up + (1 w)q)= = JEERD wp(x) + (1 w)
dx 1
(171)
p(z))
dæ
(172)
(0EEP1p(a)<<((0)) (pp(x) w w)y(ar)
p(x)3
+ (#ERP)o(=)>q(a)) up(x) + (1 w gg( x
de
(173)
p(z)²
dr
(174)
(mERP(p(E)<((()) (p((a) (1 w p( (
p(x)²
+
dx 1
(175)
(WERD (26))(p())>)(2)) wg(x)) (1 w w)q x
p(x)dxx / p(2r)2 dx
$
(176)
.EERD g(x)
WEERD
p(z)2
dx = Dx² 9) +1
(177)
ØER g(x)
26


Reviews:
[{"review_id": "do8l2shm5N", "reviewer": "Reviewer_6Yhf", "summary": "In this work, the authors make a number of contributions to the area of estimating normalization factors using annealing from some \"proposal\" $p_0$ to a \"target\" $p_1$.  \n\nThe authors start off by nicely extending recent works by Chehab et al. (2023) on the relation between importance sampling (IS) and noise-constrastive estimation (NCE) to the scenario involving annealing, introducing the notion of *annealed Bregman estimators (ABE)* in the proces, computing hte intermediate log-ratios by solving a classificiation task between samples drawn from neighboring densities.  \n\nMaking in particular use of the ABE defined by the NCE loss, the authors then obtain a number of asymptotic results (in the number of temperatures $K \\to \\infty$) for the mean-squared error of the estimator of $log Z_1$, i.e. the normalization constant of the target $p_1$.  \n\nIn Theorem 3, they show that in the case of the commonly used geometric path $p_t = p_0^{1 - \\beta} p_1^{\\beta}$, both annealed IS and annealed NCE result in an MSE estimate that polynomial in the parameter distance between $p_0$ and $p_1$. This result is established under assumptions of the exponential family for both the proposal and the target, which is a more general setting than seen in previous works. Moreover, the authors also show in Theorem 2, under almost identical assumptions to Theorem 3, that even with the NCE loss instead of IS, the MSE will still scales exponentially in the distance between the parameters of the proposal and target, as is a well-known fact for the IS-based estimator.  \nCombining these two results, the authors have demonstrated theoretically that *annealing* allows us to move from exponential to polynomial dependence on the parameter distance, effectively bridging the gap between many empirical results from the literature where annealing has been observed to be of much help even in higher dimensions vs. standard importance sampling.  \n\nFurthermore, in Theorem 4, 5, and 6, the authors show that the MSE when using the recently introduced arithmetic path $p_t = (1 - \\beta) p_0 + \\beta p_1$, has exponential, polynomial, and constant dependence on the parameter distance, respectively, under different path-parameterizations. Of course, this path requires the normalization constant in its computation, but the authors use the observation to propose a two-step estimation procedure which they then demonstrate to be useful on a simple toy-problem.  ", "questions": "-   Theorem 6: In Gelman & Meng (1998) in Section 4.3, they make the following comment \"we doubt (51) is achievable as it is bounded above by $\\pi^2 / n$ even if $p_0$ and $p_1$ are infinitely apart\" referring to the continuous-time limit.  \n    This is then slightly sharper than the $2 \\pi^2 / N$ result presented in this work. Can the authors comment on this? Was this just a slightly overly confident statement by Gelman & Meng, i.e. they really meant including the factor of 2?\n", "limitations": "The main limitations of the theoretical analysis are of course the assumptions.  \n\nThe authors assume that both the proposal and the target are in the exponential family, in addition varying assumptions on the normalization constant of the target as a function of the parameters. This is often not the case in practice, but, as mentioned by the authors, the exponential family some universality properties, which one could argue makes this slightly less of an issue.  \n\nAs most other works on annealing, this work also assumes perfect sampling from the intermediate distributions, which is usually not the case in practice. But, as mentioned, this is a very common assumption to make. This is also mentioned by the authors.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "I believe this work to be of excellent standard.  \n\nThe authors are very nicely combining the previous works of Gelman & Meng (1998) and Chehab et al. (2023) to provide both additional theoretical and empirical insights. The theoretical results are, as far as I can tell, both very novel and very relevant. In particular, I find Theorems 2 & 3 to be very pleasing as they give us a clear theoretical motivation for the usage of annealing in higher dimensions, which is a result long sought after. In addition to this, they also bring the work of Chehab et al. (2023) into the annealing setting, and demonstrates its utility both theoretically and empirically (though on toy-problems).  \n\nThe presentation is of very high quality; the text is well-written, the results are presented in a clear and nice manner, illustrations are used to get the intuition across, and tables are used when appropriate to give the reader a quick overview of results.  \n\nAs far as I can tell, the authors also do a good job mentioning previous works and the limitations of their own work.  ", "weaknesses": "There are honestly very few weaknesses to point out when it comes to the paper itself; the only weaknesses I can find are related to limitations of the analysis and the resulting proposed practical methods, which I will leave to the \"Limitations\" section. The one aspect I'd like to raise, though this is slightly related to the aforementioned limitations, is that I would have liked to see slightly more extensive empirical results for the proposed methods. I do agree with the authors in that the empirical results are not the main focus of the work, but still, have a slightly more complex problem would have been nice to see how, for example, the two-step (trig) approach would do in this.  ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive feedback! We also thank the reviewer for spotting the difference between the $2 \\pi^2 / N$ in eq. 17 in our paper and the $\\pi^2 / N$ from [1] which is correct. This is due to an unfortunate typo: in the supplementary material of our paper, eq 112 defines $\\alpha_H = \\pi / 4$, hence in eq 117 we should have $\\alpha_H^2 = \\pi^2 / 16$ which recovers the result of [1]. \n\n[1] Gelman et al. “Simulating normalizing constants: From importance sampling to bridge sampling to path sampling”. Statistical Science, 1998.\n"}, {"review_id": "RQ0VdK6vtl", "reviewer": "Reviewer_EpxH", "summary": "This paper studies annealing schedules used in noise contrastive estimation (NCE). In particular, it conducts rigorous theoretical analyses of existing annealing schedules used in NCE. The paper's framework is general and yields importance sampling, umbrella sampling, and bridge sampling as special cases. The theory suggests that NCE is more efficient in certain scenario compared to annealed importance sampling (AIS).", "questions": "### Major Comments\n* Line 40: As mentioned above, we do have some understanding on how to tune the performance of annealing-based normalizing constant estimation. In fact, although less formal, Neal's paper [2] contains a lengthy discussion on this. Why is this not mentioned?\n* Line 189-190: \"... there is no definitive theory on the ability of annealing to reduce the statistical cost in a general setup.\" Again, I believe [2] provides some theory, and with the backward sampling formalism, further analysis is possible as in [3], which is based on the results of [7].\n* Line 136-137: This is true for importance sampling, but not necessarily for AIS. In fact, this point in the cited reference [27] is shown with only importance sampling. (Thus, the quotation needs to be corrected.) In AIS, with an optimal $L$-kernel, one can achieve the variance of $i.i.d$ samples regardless of the tails, although whether one can obtain an optimal $L$-kernel is something else.\n* Line 65-79: On a similar note, this is a description specific to thermodynamic integration/bridge sampling and is not how newer AIS approaches do things nowadays. In fact, in AIS/SMC, you do not need to choose a path before sampling. You can adaptively determine the sequence based on the estimated quality of samples [6].\n\n### References\nDisclaimer: I am not the author or affiliated with the authors of the papers below.\n* [1] Del Moral, Pierre, Arnaud Doucet, and Ajay Jasra. \"Sequential monte carlo samplers.\" Journal of the Royal Statistical Society Series B: Statistical Methodology 68.3 (2006): 411-436.\n* [2] Neal, Radford M. \"Annealed importance sampling.\" Statistics and computing 11 (2001): 125-139.\n* [3] Bernton, Espen, et al. \"Schr\\\" odinger Bridge Samplers.\" arXiv preprint arXiv:1912.13170 (2019).\n* [4] Doucet, Arnaud, et al. \"Score-based diffusion meets annealed importance sampling.\" Advances in Neural Information Processing Systems 35 (2022): 21482-21494.\n* [5] Chopin, Nicolas, and Omiros Papaspiliopoulos. An introduction to sequential Monte Carlo. Vol. 4. New York: Springer, 2020.\n* [6] Dai, Chenguang, et al. \"An invitation to sequential Monte Carlo samplers.\" Journal of the American Statistical Association 117.539 (2022): 1587-1600.\n* [7] Agapiou, Sergios, et al. \"Importance sampling: Intrinsic dimension and computational cost.\" Statistical Science (2017): 405-431.", "limitations": "Yes.", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "Disclaimer: I am new to noise contrastive estimation, but familiar with the annealed importance sampling literature.\n\n* The paper provides a rigorous analysis of different annealing schedules used in noise contrastive estimation.\n* Previous methods for estimating normalizing constants are obtained as a special case, such as umbrella sampling, ration sampling, and bridge sampling.\n* The paper shows that the popularly used geometric annealing schedule is suboptimal.", "weaknesses": "Given my lack of expertise in terms of NCE, I will focus my comments on the claims about AIS.\n\n* A major concern with the theoretical comparison against AIS is that the specific instance of AIS considered in this paper is known to be suboptimal. The analysis of AIS nowadays involves the \"backward sampling path\" formalism (first thoroughly explored in [1], but also tackled in Neal's paper [2]), where the paper's formulation of AIS corresponds to the \"suboptimal $L$-kernel\" (kernel implicitly used for backward sampling), where the suboptimality is already in the name. There exists attempts to obtain approximately optimal $L$-kernels [3,4].\n* This is a minor point, but the fact that the AIS with the suboptimal $L$-kernel scales poorly (which is what is referred to as AIS in the paper) is already known. See p. 335 in [5], p. 11 in [6].\n* As such, the claimed scope of the paper is way too broad compared to the actual contribution of the paper. I strongly recommend stating that this is a paper focusing exclusively on noise contrastive estimation in the title, abstract, and introduction.\n* Also, I think the paper should be more subtle when comparing performance against importance sampling; with the backward sampling \nformalism, you do not need to \"assume\" perfect sampling; you still have non-asymptotic performance guarantees through [7], and asymptotic guarantees through [1]. So not being able to capture this is theoretically quite critical.\n\n\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their valuable feedback and pointing out the relevance of SMC literature to this problem. As we understand, the reviewer broadly makes two points. First, our analysis assumes “perfect sampling” while SMC acknowledges “imperfect sampling” which is more realistic. Second, relevant results from the SMC literature could be better referenced. In the following, we answer these concerns and hope the reviewer will consider raising their score accordingly. \n\n**Our analysis assumes perfect sampling** (the samples are drawn from the path) **while SMC acknowledges imperfect sampling** (the samples are drawn from an MCMC kernel possibly followed by resampling) **which is more realistic** — this is a good point, and we appreciate the chance to clarify. We would like to note that for inexplicit paths of distributions, analyzing the estimation error of AIS/SMC seems unclear and challenging [Eq 38, 1]. In particular, samples from MCMC will typically follow distributions that are not analytically tractable (since they are not easily describable in closed form), thus stronger assumptions seem needed for analysis. We make the assumption of “perfect sampling” and highlight that **this assumption is fairly standard** in the related literature [4, 5, 6, 7]. \n\nIn fact, **many SMC results referenced by the reviewer also make the “perfect sampling” assumption**. It translates in the SMC literature as:\n- a suboptimal “time reversal” L-kernel (sentence preceding eq 2.5 of [2])\n- the convergence of MCMC steps along the path (assumption 3.1 in [2])\n\nThese assumptions are needed to make the estimation error depend explicitly on the path of distributions as in eq 3.2 of [2]. \n\n\n**We note that even with the “perfect sampling” assumption, existing results on how the estimation error scales with dimensionality are limited:**\n- Section 3.3 of [2] provides an argument that annealing can reduce the statistical complexity to polynomial in the dimension, but that argument is largely heuristic and relies on restrictive assumptions such as an essentially log-concave path of distributions (assumption 3.4 of [2])\n- Section 4 of [3] discusses the benefits of annealing based on a heuristic calculation\n- Other works mentioned at the end of section 3 of [2], assume independent components of the target distribution which is very restrictive or refer to “relevant discussions” for polynomial dependence in the dimensionality without a definite theory. \n\n**We are happy to include a detailed discussion on these results from SMC literature in the camera-ready version**, to complement lines 40 and 189-190 of our paper, and thank the reviewer for the relevant references they pointed out! To complement lines  65-79 of our paper, we will also discuss versions of AIS where the path is not explicitly defined as in thermodynamic integration, but adaptively defined “on the go” as in [7], as suggested by the reviewer. \n\nThe reviewer also mentions some works that do not make the “perfect sampling” assumption. Some of these works target the optimal “backward L-kernel” [8, 9]. We note however that while they report empirical results, they do not theoretically study the estimation error. There are important challenges to a theory that uses Monte Carlo estimates of the optimal “backward L-kernel”: for example, the estimation of the backward kernel (the Stein score in [9]) introduces variance that cannot be ignored and for which the analysis can be quite involved [10].\n\n**Regarding the scope of this paper**, the cost function that we analyze is obtained from seminal AIS literature [4, 5] and we show in our Theorem 1 and this cost function applies just as well to annealed importance sampling, annealed noise-contrastive estimation, and annealed reverse-importance sampling, under the assumption of perfect sampling. We do agree with the reviewer that our analysis of AIS strongly relies on that assumption: we could change the title to something like “Provable benefits of annealing for estimating normalizing constants: IS, NCE and beyond” or “Provable statistical benefits of annealing for estimating normalizing constants”. Hopefully this clarifies that we separate the estimation error of AIS from the uncertainty in the sampling procedure which is “oracled away”. \n\n\n[1] Del Moral. \"Sequential monte carlo samplers.\" Statistical Methodology, 2006. \n\n[2] Dai et al. \"An invitation to sequential Monte Carlo samplers.\" Journal of the American Statistical Association, 2002. \n\n[3] Neal. “Annealed importance sampling”. Statistics and computing, 2001. \n\n[4] Gelman et al. “Simulating normalizing constants: From importance sampling to bridge sampling to path sampling”. Statistical Science, 1998.\n\n[5] Grosse et al. “Annealing between distributions by averaging moments”. NIPS, 2013.\n\n[6] Brekelmans et al. “All in the Exponential Family: Bregman Duality in Thermodynamic Variational Inference”. ICML, 2020. \n\n[7] Goshtasbpour et al. “Adaptive Annealed Importance Sampling with Constant Rate Progress”. ICML, 2023.\n\n[8] Bernton, Espen, et al. \"Schrodinger Bridge Samplers.\" arXiv preprint arXiv:1912.13170 (2019).\n\n[9] Doucet, Arnaud, et al. \"Score-based diffusion meets annealed importance sampling.\" Advances in Neural Information Processing Systems 35 (2022): 21482-21494.\n\n[10] Qin et al. “Fit Like You Sample: Sample-Efficient Generalized Score Matching from Fast Mixing Markov Chains”. Arxiv, 2023.\n"}, {"review_id": "tJpdAGUdUX", "reviewer": "Reviewer_q5r2", "summary": "This paper investigates the benefits of using bridge distributions to estimate the unknown normalizing constant $Z_1$ of a given density $p_1 = f_1 / Z_1$, with $f_1$ known. There are many ways for estimating a normalizing constant, e.g. importance sampling, bridge sampling, umbrella sampling and noise contrastive estimation. For example, in importance sampling an instrumental density $p_0$ from which it is easy to sample is introduced and the normalizing constant is estimated by weighting the samples from $p_0$ according to the ratio $f_1 / p_0$. Naturally, the accuracy of the estimation depends on how far $p_0$ is from $p_1$ (in Rényi 2-divergence for example or KL), and in most practical cases $p_0$ will be in fact very far from $p_1$. A nice idea then consists in introducing bridge distributions that \"simplify\" the estimation; we introduce a sequence of distributions $p_k$ (which themselves have intractable normalizing constants) such that the discrepancy between $p_{k+1}$ and $p_k$ is small and use them to estimate the normalizing constant. There are many ways for choosing such a sequence of distributions including geometric path, arithmetic path.  \nThis paper investigates the effect of each design choice: the estimator (they challenge the default choice of IS) and the sequence of bridging distributions. More specifically, their contributions are the following:  \n- They show that the NCE loss is optimal, whatever the number $K$ of bridging distributions and thus showing that IS is in fact not optimal. This extends the result for $K = 1$.  \n- The performance of IS is known to suffer from exponential dependence on the dimension and this phenomenon is now sharply quantified. In this paper it is shown that this is also the case for NCE at least for the exponential family, which hints that it should be also the case for more complex densities.  \n- The hope of using the bridging distributions was to diminish the effect of the dimensionality. It is shown that in the limit of infinite bridge distributions and with geometric paths, the error is no longer exponential but only polynomial.  \n- Finally, in the presence of an oracle providing the target normalizing constant $Z_1$, they show that the arithmetic path can provide an error independent of the dimension. ", "questions": "If I am not mistaken, the estimator $\\hat{Z}_1$ in the first line of table 1 is not an estimator of $Z_1$ as $f_0$ is not normalized. Also, in eq. 4 and eq. 5 I believe that there should be $+ \\log Z_0$.", "limitations": "See weaknesses", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "I find the theoretical contributions of this paper original, interesting and significant. Indeed, I appreciate that the authors have deeply investigated some a priori knowledge that practitioners have, such as the optimality of IS and the effect of the annealed distributions. Furthermore, I very much appreciate that the theoretical results are validated empirically on toy examples. ", "weaknesses": "The assumptions made in the paper are very strong (perfect sampling for example) and some of the results are only asymptotic in the number of bridge distributions. This makes me doubt about the broad relevance of this paper to the NeurIPS community. Furthermore, although the proposed two step procedure was shown to be numerically optimal, it is not tested numerically in the realistic scenario where one has to resort to MCMC for sampling. I believe that there is no reason why this should not be tested and compared to more traditional methods. Otherwise it is practically useless. \n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their valuable feedback, and we are glad the reviewer finds the paper “original, interesting and significant”. We next address comments point-by-point and hope the reviewer will consider raising their score. \n\n**The assumptions made in the paper are very strong [...]  This makes me doubt about the broad relevance of this paper to the NeurIPS community. —**\nWhile we agree with the reviewer that some of the assumptions we make are quite strong, we would also like to point out that they are fairly standard in the related literature. For example, [2] remark that their “analysis assumes perfect transitions which can be unrealistic in practice because many distributions of interest have separated modes between which mixing is difficult.” The assumptions of “perfect sampling” and of a “continuous path” are commonly made [1, 2, 3, 4] to make the theory tractable to obtain results that can serve as coarse guidelines. This also includes recent works in the NeurIPS and ICML communities [2, 3, 4].  We of course agree that it would be great to further close the gap between theory and practice, and hope that papers like ours will serve as a jumping-off point for such work. \n\n**Typos —** the reviewer is correct about the typo in table 1: f0 should be p0 in order to obtain an estimator of the target normalization. Also, in eqs. 4-5 the plus sign in front of logZ0 vanished. Thank you for picking up on this. \n\n[1] Gelman et al. “Simulating normalizing constants: From importance sampling to bridge sampling to path sampling”. Statistical Science, 1998. \n\n[2] Grosse et al. “Annealing between distributions by averaging moments”. NIPS, 2013.\n\n[3] Brekelmans et al. “All in the Exponential Family: Bregman Duality in Thermodynamic Variational Inference”. ICML, 2020. \n\n[4] Goshtasbpour et al. “Adaptive Annealed Importance Sampling with Constant Rate Progress”. ICML, 2023.\n"}, {"review_id": "hdvPFOAgq2", "reviewer": "Reviewer_peRm", "summary": "The article theoretically bounds the estimation error of NCE depending on the path. The paper first shows that NCE has minimum variance among all estimators using K bridging distributions and then continues by showing that the standard polynomial path can achieve polynomial error in the limit of infinitely many bridging distributions. Then the authors derive first a negative result for the arithmetic path and a positive result on the oracle estimate of the path that uses the unknown normalisation constant. The results are empirically verified.", "questions": "I would suggest to discuss [1] in the article due to its relevance and clear overlap. A few of the references therein might be important as well.\n\nQ1: you stress in the article that your proposed two-step method is not efficient. Do you foresee a way to make it efficient? Is it possible to create a larger experiment on a real estimation task that shows that it can improve on previous estimates?\n\n\n\nFinally, on page 5 line 165 where you quote [29], I would propose to also mention Deep Belief networks as an important model class with universal approximation properties for which estimation the normalisation constant is relevant:\n\nKrause, Oswin, et al. \"Approximation properties of DBNs with binary hidden units and real-valued visible units.\" International conference on machine learning. ICML, 2013.\n\n", "limitations": "yes", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The authors responses clarified the main weaknesses and I am raising my score accordingly.\n--------------------------\n\nThe paper appears to be well written and some of the results appear to be novel, especially the error bounds. I have not checked the math in the appendix.\n\nThe presentation is rather clear and to the point and the experiments nicely validate the theorems.", "weaknesses": "- Some related work is missing. importantly, NCE is a method that got discovered and rediscovered several times, see for example this review that calls the same method BAR (Bennets acceptance ratio): \n\n[1] Krause, Oswin, Asja Fischer, and Christian Igel. \"Algorithms for estimating the partition function of restricted Boltzmann machines.\" Artificial Intelligence 278 (2020): 103195.\n\n- As a result of this, Theorem 1 was already known, as [1] reproduces an earlier proof that shows that NCE is a maximum likelihood estimator. Since MLEs are efficient, their variance is bounded by the variance of the Fisher matrix. In that light, the novelty of Theorem 1 is to produce a bound on the Fisher matrix via the path integral. Similarly, [1] already proposed a framework that included the generalisation of several estimators, similar to the Bregman methodology proposed in this work.\n\n- The practical applicability of the results is questionable. While the work shows that the two step estimator works well given perfect samples, it might be very challenging to obtain good samples for the arithmetic path. This is because the modes that appear are disconnected from each other from the very beginning on, which makes it difficult to discover them using MCMC, unlike for example parallel tempering with the polynomial path (see [1]).\n \n\n\n\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their valuable feedback and pointing out relevant references. In the following, we will answer the reviewer’s comments point-by-point. We hope we address their concerns and hope the reviewer will consider raising their score. \n\n**“I would suggest to discuss [1] in the article due to its relevance and clear overlap. A few of the references therein might be important as well.”  —** The references [1, 2] suggested by the reviewer are indeed relevant, and we will be sure to add them in the camera-ready version of the paper! \n\nWe agree with the reviewer that NCE has been rediscovered under many names, for estimating the normalization constant [3, 4, 5] of an unnormalized model, as pointed out by that reference and some other works [Section 3.2., 6]. Moreover, eq. 5 of [1] uses a similar identity to eq. 1.4 of [7] to generalize importance sampling to a family of estimation methods which includes NCE, also similar to [6].\n\n**“Theorem 1 was already known” —** we agree that a small part of Theorem 1 is known — and we point this out in the paper as well: “In the binary setup [...], the NCE loss is optimal [6, 7] ”. There are several novel parts to Theorem 1 however: (1) we extend the result to a sequence of distributions; (2) we show that the optimality gap between NCE and IS vanishes in the continuous path limit; (3) we provide a closed-form expression of the MSE in that limit. \n\n**“The practical applicability of the results is questionable” —** we agree with the reviewer that bridging the gap between theory and practice is an important challenge; we simply point out that it is an issue for the entire literature. [8] point out that “Due to the difficulty of establishing general results under arbitrary sampling schemes, we shall assume independent draws for theoretical explorations and guidelines”. Similarly, [9] remark that “the [...] analysis assumes perfect transitions which can be unrealistic in practice because many distributions of interest have separated modes between which mixing is difficult.” A number of methods have been developed to deal with sampling issues, including parallel tempering that is mentioned by the reviewer, and tempered transitions. In fact, the path cost for both these methods, parallel tempering [eq. 17, 10] and tempered transitions [eq. 18, 11], are equal (or upper bounded) by a a sum of f-divergences which in the limit of a continuous path is the same cost function as in our Theorem 1. This suggests our results may be applicable to more practical methods in the literature. \n\n**“You stress in the article that your proposed two-step method is not efficient. Do you foresee a way to make it efficient?” —** Our two-step method uses an estimate of the target normalization to reparameterize the arithmetic path. It is not clear how the estimation error of the normalization propagates into an error in the path it reparameterizes. In future work, we hope to look more closely at how our optimality results can be brought to scale. \n\n\n[1] Krause et al. “Algorithms for estimating the partition function of restricted Boltzmann machines.” Artificial Intelligence, 2020.\n\n[2] Krause et al. “Approximation properties of DBNs with binary hidden units and real-valued visible units.” ICML, 2013.\n\n[3] Geyer. “Estimating Normalizing Constants and Reweighting Mixtures”. Technical Report No. 568, School of Statistics University of Minnesota, 1994. \n\n[4] Bennett. “Efficient estimation of free energy differences from Monte Carlo data”. Journal of Computational Physics, 1976.\n\n[5] Gutmann et al. “Noise-Contrastive Estimation of Unnormalized Statistical Models [...]”. Journal of Machine Learning Research, 2012.\n\n[6] Chehab et al., “Optimizing the Noise in Self-Supervised Learning [...]”. Arxiv, 2023. \n\n[7] Meng et al. “Simulating Ratios of Normalizing Constants Via A Simple Identity”. Statistica Sinica, 1996.\n\n[8] Gelman et al. “Simulating normalizing constants: From importance sampling to bridge sampling to path sampling”. Statistical Science, 1998.\n\n[9] Grosse et al. “Annealing between distributions by averaging moments”. NIPS, 2013.\n\n[10] Syed et al. “Parallel tempering on optimized paths”. ICML, 2021. \n\n[11] Behrens et al. “Tuning tempered transitions”. Statistics and Computing, 2012.\n\n"}]

Author rebuttal:
We thank all four reviewers for their feedback, and for suggesting references which we plan to include in a camera-ready version to give further context to our results. In this general reply, we further clarify the relevance of our results and we address specific concerns in detail in the individual replies. 

**Relevance of our results —** annealed importance sampling is a seminal method in statistics and while it is known that the choice of annealing path can greatly impact the estimation error [1], theoretical guarantees on commonly used paths have been elusive. Some prior works have relied on heuristic arguments [2, 3], strong assumptions like gaussianity [3] or essentially log-concavity [2] along the path, or a factorial target [4] to study how the estimation error scales with the dimensionality for a certain choice of path. But in a general setting, no such results exist to our knowledge. **We believe our results are the first to quantify how the geometric path — which has been the standard for more than a decade — actually impacts the estimation error in terms of the dimensionality of the problem**. Our results are also **the first theoretical analysis of the estimation error from an arithmetic path since it was introduced [5]**. We believe these results are relevant to the NeurIPS community, especially as annealing paths are becoming a central component of many recent advances in machine learning [6, 7].





[1] Gelman et al. “Simulating normalizing constants: From importance sampling to bridge sampling to path sampling”. Statistical Science, 1998.

[2] Dai et al. "An invitation to sequential Monte Carlo samplers." Journal of the American Statistical Association, 2002. 

[3] Neal. “Annealed importance sampling”. Statistics and computing, 2001. 

[4] Beskos et al. “On the stability of sequential Monte Carlo methods in high dimensions’. The Annals of Applied Probability, 2014.

[5] Masrani et al. “q-Paths Generalizing the Geometric Annealing Path using Power Means”. UAI, 2021. 

[6] Rhodes et al. “Telescoping Density-Ratio Estimation”. NeurIPS, 2020. 

[7] Song et al. “Score-Based Generative Modeling through Stochastic Differential Equations”. ICLR, 2021. 


Meta-review: The reviewers all agree this is a strong paper that makes a number of significant contributions to our understanding of methods for normalization constant estimation, including providing theoretical support for the good performance of AIS seen in practice.
Decision: Accept (spotlight)