NEO: Non Equilibrium Sampling on the Orbits of a Deterministic Transform
Authors: Achille Thin
Yazid Janati El Idrissi
Sylvain Le Corff
Charles Ollion
Eric Moulines
Arnaud Doucet
Alain Durmus
Christian P Robert
Venue: NeurIPS 2021 Poster (2021)
Keywords: Importance Sampling
Monte Carlo
Markov chain Monte Carlo

Abstract: Sampling from a complex distribution $\pi$ and approximating its intractable normalizing constant $\mathrm{Z}$ are challenging problems. 
In this paper, a novel family of importance samplers (IS) and Markov chain Monte Carlo (MCMC) samplers is derived. 
Given an invertible map $\mathrm{T}$, these schemes combine (with weights) elements from the forward and backward Orbits   through points sampled from a proposal distribution $\rho$. The map $\mathrm{T}$ does not leave the target $\pi$ invariant, hence the name NEO, standing for Non-Equilibrium Orbits. 
NEO-IS provides unbiased estimators of the normalizing constant and self-normalized IS estimators of expectations under $\pi$ while NEO-MCMC combines multiple NEO-IS estimates of the normalizing constant and an iterated sampling-importance resampling mechanism to sample from $\pi$. 
For $\mathrm{T}$ chosen as a discrete-time integrator of a conformal Hamiltonian system, NEO-IS achieves state-of-the art performance on difficult benchmarks and NEO-MCMC is able to explore highly multimodal targets. Additionally, we provide detailed theoretical results for both methods. In particular, we show that NEO-MCMC is uniformly geometrically ergodic and establish explicit mixing time estimates under mild conditions.


NEO: Non Equilibrium Sampling on the Orbit of a Deterministic Transform
Achille Thin
Centre de Mathématiques Appliquées
École polytechnique
Palaiseau, France
achille. htw.eeechhhooollleeeeiiuuuu edu
Yazid Janati
Sylvain Le Corff
Samovar
Samovar
Télécom SudParis, Département CITI
Télécom SudParis, Département CITI Palaiseau, France
Palaiseau, France
Charles Ollion
Arnaud Doucet
Centre de Mathématiques Appliquées
Department of Statistics, University of Oxford, UK
École polytechnique, Palaiseau, France
Alain Durmus
Eric Moulines
Université Paris-Saclay, ENS Paris-Saclay, CNRS, Centre Borelli, F-91 190 Gif-sur-Yvette, France
Centre de Mathématiques Appliquées École polytechnique, Palaiseau, France
Christian Robert
Ceremade, Université Paris-Dauphine, France & Department of Statistics, Warwick University, UK
Abstract
Sampling from a complex distribution æ and approximating its intractable nor- malizing constant importance samplers (IS) and Markov chain Monte Carlo (MCMC) samplers is de- rived. Given an invertible map T, these schemes combine (with weights) elements from the forward and backward Orbits through points sampled from a proposal distribution p. The map does leave the target æ invariant, hence the name NEO, standing for Non-Equiling -on-Equiiirrimm Orbits. NEO-IS provides unbiased estimators of the normalizing constant and self gelf-nermllized IS estimators of expectations under v while NEO-MCMC combines multiple NEO-IS estimates of the normalizing constant and an iterated from For T chosen discrete-time integrator of conformal Hamiltonian system, NEO-IS achieves statc-of-the art performance on difficult benchmarks and NEO-MCMC is able to explore highly multimodal targets. Additionally, we provide detailed theoretical results for both methods. particular, we show that NEO-MCME is uniformly geometrically ergodic and establish explicit mixing time estimates under mild conditions.
challenging problems. In this paper, novel family of
resampling mechanism to sample
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Introduction
Consider a target distribution of the form (<) x p(x))[(x)) where is a probability density function (pdf) on IR and L is a nonnegative function. Typically, in a Bayesian setting, т is a posterior distribution associated with prior distribution p and a likelihood function L. Another situation of interest is generative modeling where π is the distribution implicitly defined by a Generative Adversarial Networks (GAN) peteriminnato-geeeerttt pair where is the distribution of the generator and L is derived from the discriminator [31, 6]. In a Variational Auto Encoder (VAE) context [14, 5], ग could be the true posterior distribution, P the approximate posterior distribution output by the encoder and I. an importance weight between the true posterior and approximate posterior distributions. We are interested in this paper in sampling from and approximating its intractable normalizing constant Z = (z) These problems arise in many applications in statistics, molecular dynamies or machine learning, and remain challenging.
Many approaches to compute normalizing constants are based on Importance Sampling (IS) see [1, 2] and the references therein and its variations, among others, Annealed Importance Sampling (AIS) [19, 34, 10] and Sequential Monte Carlo (SMC) [9]. More recently, Neural Is has also become very popular in machine learning; see e.g. [11, 18, 21, 22, 32, 33). Neural IS is adaptive IS which relies on an importance function obtained by applying a normalizing flow to a reference distribution. The parameters of this normalizing flow are chosen by minimizing a divergence between the proposal and the target (such as the Kullback-Leibler [18] or the X²-divergence [1]). Recent work on the subject proposes add stochastic moves in order to enhance the performance of the normalizing flows| [33]. More recently, the Non-Equilibrium IS (NEIS) method has been introduced by [23] as alternative from a
to these approaches. Similar to Neural IS, NEIS consists in transporting samples {X*} fi=1 /
reference distribution using family of deterministic mappings. For NEIS, this family is chosen to be an homogeneous differential flow (Ør) In contrast to Neural IS, for any E [N., the sample
X is propagated both forward and backward in time along the orbits associated with (ox )eeR until stopping conditions are met. Moreover, the resulting estimator of the normalizing constant is obtained by computing weighted averages of the whole orbit (øx(X*)) )eelr) where T+, T-, the resulting stopping times, and not only the endpoints 2.+,. (X'), (X'). In [23], the authors provide an application of NEIS with (Øt)ER associated with a conformal Hamiltonian dynamics, and reports impressive numerical results on difficult normalizing constants estimation problems, in particular for high-dimensional multimodal distributions.
We propose in this work NEO-IS which alleviates the shortcomings of NEIS. Similar to NEIS, samples are drawn from a reference distribution, typically set to p. and propagated under the forward and backward orbits of a discrete-time dynamical system associated with an invertible transform T. An estimator of the normalizing constant is obtained by reweighting all the points on the whole orbits using the IS rule. Contrary to NEIS, the NEO-IS estimator of Z is unbiased under assumptions that mild and easy verify. It is more flexible than NEIS because does not rely on the accuracy of the discretization of a continuous-time dynamical system.
We then show how it is possible to leverage the unbiased estimator of Z defined by NEO-IS to obtain NEO-MCMC, a novel massively parallel MCMC algorithm to sample from म. In a nutshell, NEO- MCMC relies on parallel walkers which each estimates the normalizing constant but are allowed to interact through a resampling mechanism.
Our contributions can be summarized as follows.
(i) We present a novel class of IS estimators of the normalizing constant Z referred to as NEO-IS. More broadly, a small modification of this algorithm also allows to estimate integrals with respect to æ. Both finite sample and asymptotic guarantees are provided for these two methodologies.
(ii) We develop a new massively parallel MCMC method, NEO-MCMC. NEO-MCMC com- bines NEO-IS unbiased estimator of the normalizing constant with iterated sampling- importance resampling methods. We prove that it is --reversible and ergodic under very general conditions. We derive also conditions which imply that NEO-MCMC is uniformly geometrically ergodic (with an explicit expression of the mixing time).

---

iii) We illustrate our findings using numerical benchmarks which show that both NEO-IS and NEO-MCMC outperform state-of-the-an (SOTA) methods in difficult settings.
2 NEO-IS algorithm
In this section, we derive the NEO-IS algorithm. The two key ingredients for this algorithm are (1) the reference distribution p and (2) transformation T assumed to C'-diffeomorphhis with inverse T Write, for k E N = N {0), T = To ToT=1 - = Ipl and similarly T = T T (k-1), For any & E 2, denote by Ph Rd - R2+ the pushforward of p by T defined for x E R by Pa(x) = ( (2))" of + R + Rd evaluated at æ. In line with multiple importance sampling à la Owen and Zhou [20],
(x)))--((>) (<))))=(((<))))>>><<<>>>>> where Jæ (a) E R+ is the absolute value of the Jacobian determinant
we introduce the proposal density
pr(x)= = S2-11111 -2----E KEZ (x))
kez Wk. Note that we assume in the sequel that the support of the weight sequence defined {Ki & we # 0} is finite. Thus, the mixture distribution in (1) is finite mixture. Given pT (x) is function of the forward and backward orbit of T through x.
where (wktee is a nonnegative sequence and Ω -kkg
For any nonnegative function f. the definition of pr implies that f f(y) = Ω Etez (TT Assuming that wo O, the ratio p(x)//r( S wo
w ' < co is
bounded. We can therefore apply the IS principle which allows to write the identity
J [1W)tt)a / (Il)
p(y) pr(v)) pr(y)dy / Σ (I) kEZ
where the weights are given by (see Appendix A.2 for detailed derivation),
wx(x) =xP(T (x)) (x))) =xp-x(x) / Eiez @k+iP(()
(3)
We assume in the sequel that wo > 0. In particular, note that under this condition, the weights wa
also upper bounded uniformly in æ: for any æ E Rdd wy suggest to estimate the integral f (())) by TNEO (ʃ) N- ΣLEZ (xx)))(((((X())
wx(x) (x) S / /00 Equations (2) and (3)
iid where [X are i.i.d. samples from the proposal p. which is denoted by X1:N ~
This estimator is obtained by weighted combination of the ele- ments of the independent forward and backward orbits (T*(X)) with X1:N iid This estimator is referred to as NEO-IS. Choosing f = pro- vides the NEO-IS estimator of the nor- malizing constant of π:
Algorithm 1 NEO-IS Sampler
1. Sample X ~ p i [N].
2. For E [N], compute the path (T")))) and weights (x0
IOTO (f) = DN EkEz (X
- - (X))xx))) ExIN = NZ'
(4)
We now study the performance of the NEO-IS estimator. The following two quantities play fundamental role the analysis:
FT = Ex-p [ we
MT SuppERd ΣLEZ uh u/ (T)LLTT((()))) (x))/7 (5)
Theorem 1. 7.Y is an unbiased estimator of 7. FT < xc, then, E 7 2 =
N (EF - 1). If MT < oo, then, for any 8 E 10, with probability 1 -- VN
7 Z N
Z Z-1
<
M / (og(2/6)/2.
The (elementary) proof is postponed to Appendix A.3. ET plays the role of the second-order moment of the importance weights Ex~p (X)( which is key to the performance of IS algorithms
3

---

[1, In addition, since the NEO-IS estimator Z is unbiased, the Cauchy-Schwarz inequality implies that Ex~el (Ekez wx(X)L(T* (x))))
(x))) 2 zz and hence that ET 1. Note that if
||]| sup L(x) < co, then since the weights are uniformly bounded by 12 we have MF S || 2
Using the NEO-IS estimate X of the normalizing constant, we can construct a self-normalized IS estimate of (z))
N
Z
L(T (X'))xxXX)) (x*),
JN (f) = N
Xi X
(6)
7x
kEZ
referred to as NEO-SNIS estimator. This expression may seem unnecessarily compli- cated but highlights the hierarchical structure of the estimator. We combine estimators (xx))-EEs L(TT (X))) (X (x')) evaluated on the forward and backward orbits through the points { Jiz estimator is unbiased, the NEO-SNIS is in general biased. However, for bounded functions, both the bias and the variance of the NEO-SNIS estimator O(N-1), with constants proportional to E.P. For a π r-integrable function, we set (g) = J (x))x(
using the normalized weights (Zx:/XxIN) J Ji=1 Although the NEO-IS
Theorem 2. Assume that ET- < co. Then, for any function 9 satisfying suPRERd [g(x)) S on Rd and N E N
[|J (g) r()))8 S N ET
X
E
[ (g) x[9)] 2 N
(8)
If MF < xc, then d E (0, 11. with probability at least 1 6,
VN O, (g) T(g) s ll MT 32 loog(//))))
(9)
The proof is postponed to Appendix A.4. These results extend to NEO-SNIS estimators the results known for nofmmloral IS estimators; see e.g., [1, 2] and the references therein. The upper bounds stated in this result suggest it is good practice to keep ET /N small in order to obtain sensible approximations. For two pdfs and on Rd denote by Dx² (p, q) = [(p(z)/q(z)) - 1)29(( (())dz the x" -i-divergence between p and q. Lemma 3. For any nonnegative sequence (#x)kEz have ET S (x((TTllr))) +
The proof is postponed to Appendix A.5. Lemma 3 suggests that accurate sampling requires N to scale linearly with the x2 diveereee between the target ıT and the extended proposal Pr-
Remark 1. We can extend NEO to non homogeneous flows, replacing the family (T*: k E ž} with a collection of mappings (T k E Z). This would allow us to consider further flexible classes of transformations such as normalizing flows; see e.g. [21]. The -ivveeegee Dy² (T ((Tr)) provides a natural criterion for learning the transformation. We leave this extension to future work.
Conformal Hamiltonian transform The efficiency of NEO relies heavily on the choice of T. Intuitively, sensible choice of T requires that (i) ET is small, i.e. Pr should be close to æ by Lemma 3 (see (5)), (ii) the inverse T-1 and the Jacobian of T are easy to compute. Following [23]. we use for T discretization of a conformal Hamiltonian dynamics. Assume that U(.)
log x(.) is
K K()) on 2d where g the position, p is the momentum, and K (p) = p" "M 111pp/2 / is the kinetic energy, with M positive definite mass matrix. By construction, the marginal distribution of the momentum under is the target pdf N (q) = क #(q. p)dp. The conformal Hamiltonian ODE associated with is defined by
continuously differentiable. We consider the augmented distribution ă ( p) x exp(-
dg:/dl V H Pt) = M-
(10)
dp./dl: - V V.H((p.pP)) - TP: = - -U - 7P:
where H(g. p) = U() + K(p), and 7 > 0s a damping constant. Any solution (4t, (t) of (10) satisfies setting H, (g),)))) dHt//t = -27/ M- S O. Hence, all orbits converge to fixed points that satisfy (U(g) 0 and p 0; see e.g. [12, 17].

---

0.0
y-
-15
-25
Figure Left: E (K) vs E
(red) in -sale as a function of the length of trajectories K (the lower the better). Second left to right: Four examples of orbits with the same random seed for different values of (from left right, ? 1,
In the applications below, consider the conformal version of the symplectic Euler (SE) method of (10), see [12]. This integrator can be constructed as splitting of the two conformal and conservative parts of the system (10). When composing a dissipative with a symplectic operator, we set for all (g.p) R², [g. p) (q + AM- {c= fe---/---hhh "p (V)(())) e h-
hVU())), where h 0 is discretization stepsize. This transformation can be connected with classical momentum optimization schemes, see [12, Section 4]. By [12, Section 3]. for any h > 0 Tn, is C'-diffeomorphism on add with Jacobian given by Jr, (q. = e e- In addition, its inverse is Th (q. p) = (g
hM-1p, ehth ctc {p- hV hM (p))). Therefore, the weight (3) of the NEO estimator is given by
(9. nkhd
wx(g. p)
Σ Ejez Wk+jP(T, (
where p) p(g)e K(p), Figure displays for different values of y log-scale the bound E |jx appearing in Theorem as function of K, here we use the sequence of weights (#*)kez = (A))xEz (i.e. only the + 1 first elements of the forward orbits are used and equally weighted). For comparison, averaging K + independent IS estimates, ( - = (K + 1 Figure shows that there is trade-off in the choice of ? which controls the exploration of the state space by the Hamiltonian dynamics since the higher y, the faster the orbits converge towards the
also present the same plot the bounds achieved by
Interestingly,
modes. This fast convergence prevents "good" exploration of the space; e.g. [a.kk is smaller for 1.0 than for y = 2.0 when K > 7.
NEO-MCMC algorithm
We now derive MCMC method to sample from based on the NEO-IS estimator. A natural idea consists in adapting the Sampling Importance Resampling procedure (SIR) (see for example [24, 27]) the NEO framework.
The SIR method to sample NEO (see (6)) consists of steps.
II:N (SIR-1) Draw independently x I:N p and compute the associated forward and backward orbits (T* (X"*) of the point.
(SIR-2) Compute the normalizing constants associated with each orbit (Zx
(SIR-3) Sample an orbit index 1 E [N] with probability (Zxx/ / j=1 2x IN
(SIR-4) Draw the iteration index K= the
NN orbit
with probability
[L(T"(X!" (x 3/ZxiN JREZ-
The resulting draw is denoted by UN = TKK (XI*). By construction, for any bounded function
f. we get that E (((UN)]E X INN ] 3 EKeE wx(X,>) (LT (X,x)) )) which implies [F(UM)|XI:N
NEO (f) (see (6)). Using Theorem 2, we therefore obtain [EE](U
(=)))( < 10' - showing that the law of the random variable μN NNw(UN) converges in total variation to π as N Dc,
||N - - sup ( =()) 10
(11)
11
5

---

Algorithm NEO-MCMC Sampler
Based on [3], we now derive the NEO- MCMC procedure, which in nutshell con- sists in iterating the SIR procedure while keeping a conditioning point (or equíva- lently, orbit); see Appendix C. The conver- gence of NEO-MCMC does not rely on letting N + co: the NEO-MCMC works as soon as N 2 2, although as we will see below the mixing time decreases N increases.
At step E N", given the conditioning orbit point Yn-1- Step 1: Update the conditioning point
1. Set X = Yn-1 and for any E (2....,N} N) sample X lid p.
2. Sample the orbit index I, with probability proportional to (Zx: )iE(M) (4). (4).
3. Set Y,, X
This procedure is summarized in Algo- rithm 2. The NEOO-MMC procedure is
Step 2: Output sample
4. Sample index K,, with probability propor- tional to {ur (u.,(Y..I..TT (Y.)).TT()))))///)))))))))) (K,)) JREZ
an iterated algorithm which produces a
sequence {(Y,, Fen of points in Rd. The n-th iteration of the NEO-MCMC al- gorithm consists in two main steps: 1) up- dating the conditioning point - Yn 2) sampling Un by selecting point in the orbit (T" (Yn) of the conditioning point. Com- pared to SIR, only the generation of the points (step (SIR-1)) is modified: we set X,, Yn-1 (the
5. Output U, = TK (Y,).
conditioning point), and then draw X2:N üid
~ p.
= The sequence (Ya) mEN defined by Algorithm 2 a Markov chain: P(Y, E E/ Yon---11) (Y, A 11) P(Yn,A) A) where
/
N
N Σ
lA(x') VER" AEB(R). __d
A)y,A) = 6, (dx') II p(x))dd 3=2
(12)
Note that this Markov kernel describes the way, at stage + 1, the conditioning point Yn41 1 is selected given Yn. which depends only on the estimator of the normalizing constants associated with each orbit, but not on the sample Un selected on the conditioning orbit. In addition, given the conditioning point Y, at the n-th iteration. the conditional distribution of the output sample U, is I, X X1:N) IP (Un, E B Y,) = Q(Y,, B) where
P (Un E B
wx wx(v) (v)) (B(TT())) y VER' BE BEB(R")
Q B)
(13)
kez
With these notations, if the Markov chain is started at Y, = y. then for any E N, the law of the n-th conditioning point is IP (Y, E A = y) pa (y. A) and the law of the n-th sample is P (U,, B (w B). Define क the pdf given for y E Rdd by
(v)) p(v) Z
wK (x(T)L(T (0)) = p(y)
(14)
Z
REZ
The following theorem shows that, for any initial condition y E Rdd, the distribution of the variable Yn converges in total variation to स and that the distribution of U,, converges to π.
Theorem 4. The Markov kernel P is reversible with respect the distribution म, ergodic and Harris positive, i.e., for all E Rd lim (p. - = O. In addition, π = #Q and limm-+00 (P*((y,)) k||rv = O. Moreover, for any bounded function g and any E R&. lim n E1 g(U.) = π (g), P-almost surely, where {Uihee is defined in Algorithm 2 with Yo = y.
The proof is postponed to Appendix A.6.
Remark 2. We may provide another sampling procedure of (Ya)nes. Define the pdf the extended space [N] x RdN by #(i, I:: = - II;""" II p(x)). Consider a Gibbs sampler targeting से consisting in (a) sampling X1=N\
I1: (f.-) (In-1, Xn-1) ~ II p(x)), ), (b) sampling
I, | ~ Cat E/=, 2x I and (c) set Y, = X This algorithm is Gibbs sampler on म and casily verify that the distribution of (Y, (Yn) men is the same Algorithm 2.

---

The next theorem provides non asymptotic quantitative bounds on the convergence in total variation. The main interest of NEO-MCMC algorithm motivated empirically from observed behaviour: the mixing time of the corresponding Markov chain improves as N increases. This behaviour is quantified theoretically in the next theorem. Moreover, this improvement obtained with little extra computational overhead, since sampling N points from the proposal distribution computing the forward and backward orbits of the points and evaluating the normalizing constants {2x; J.W can be performed in parallel.
Theorem 5. Assume that MF < CO, see (5). Serex (N - 11)((2F +N N-N2 2) and KN = 1 1-EN. Then, for any y E Bdd and k E N. (V, R T| S Key and [P =||TV S n
Instead of sampling the new points X2.N independently from (Step in Algorithm 2). it is possible to draw the proposals X!!NN conditional the current point - see [29, 8, 26, 25] for related works. Following [25], we use a reversible Markov kernel with respect to the proposal , x)) assuming for simplicity that this kernel has density m(x, x'). If p = N(0, of Ida). an appropriate choice is an autoregressive kernel m(xx x') = (xx;; ax, (²(1 - a²) Idg). More generally, we can use a Metropolis- Hastiigs kernel with invariant distribution p. In this case, rn (1(x", (It, .I:N(11)
i... such that p()))m(() x') = p(a' ((a")m(x';
1== m(x'=1, .x) and for each E [2 N).
i-1 II j=1
N πI j=i+1
ri(',, x (M)
m m +1
m(x²=1,,d xx))
(15)
Since m is reversible with respect to P. for all i, E [N], p( (
p(a))); (xr, 221) where (= (00)) defines the the conditional distribution of X1:NM0 given X x². The only modification in Algorithm Un E [N] uniformly, set x²= = Y and sample Xn y1: TU. (Xu",)) The validity of this procedure is established in Appendix A.6.
Step 1, which replaced by: Draw
4 Continuous-time version of NEO and NEIS
The NEO framework can be thought of as an extension of NEIS introduced in [23]. NEIS focuses on normalizing constant estimation and should be therefore compared with NEO-IS. [23], the authors do not consider possible extensions of these ideas to sampling problems. We consider here how NEO could be adapted to continuous-time dynamical system. Proofs of the statements and detailed technical conditions are postponed to Appendix B.
Consider the Ordinary Differential Equation (ODE) à, 6(xx), where b: Ed + RR is a smooth vector field. Denote by (Øt)EeR the flow of this ODE (assumed to be well-behaved), Under appropriate regularity condition Jo, (z) exp(_' v (z)s())) see Lemma S5. Let F R, be nonnegative smooth function with finite support, with Ω _ (t)dtt. The continuous-tin time counterpart of the proposal distribution (1) is (x) ( (x)) (z)dt, which is continuous mixture of the pushforward of the proposal p by the flow of (db.) Assuming for simplicity that p(x) > 0 for all æ E IR, then (x) > 0 for all x E Rd, and using again the IS formula, for any nonnegative function f.
I [w0)ooo)d / [(x))
p(x) (1(()) of (f(()do=
V (( p(x)dxx
(16)
L ((s t) ()(()()))))))) (x)ds.
uf(x) = =()))(((=))
(17)
These relations are the continuous- counterparts of (2). Eqs. (16)-(17) define a version of NEIS [23], with a finite support weight function w; see Appendices B.2 and B.3 for weight functions with infinite support. This identity of thcoretical interest but must be discretized to obtain computationally tractable estimator. For h > 0, denote by Ty, an integrator with stepsize h >> 0 of the ODE ă = b(x). We may construct NEO-IS and NEO-SNIS estimators based on the transform T + Ta and weights wa + (kh). We might show that for any bounded function f and for any x e Rd lima Σtez (x(x))(T((x)) w (((=))(( where we omitted here the
7

---

dependency in h of wi. Therefore, taking h 4. 0*, the NEO-IS converges to the continuous-version (16)-(17). There is however an important difference between NEO and the NEIS method in [23] which stems from the way (16)-(17) are discretized. Compared to NEIS, NEO-IS using T f- TT and weights wa +- (kh) unbiased for any stepsize O. NEIS uses an approach inspired by the nested-sampling approach, which amounts to discretizing the integral in (16) also in the state-variable x; see [28, 7J. This discretization is biased which prevents the use of this approach to develop MCMC sampling algorithm; see Appendix B.
Experiments and Applications
Normalizing constant estimation The performance of NEO-IS is assessed different normaliz- ing constant estimation benchmarks; see [13]. We focus on two challenging examples. Additional experiments and discussion hyperparameter choice are given in the supplementary material, see Appendix D.I.
(1) Mixture of Gaussian (MG25): π(x) = P 1=1 N(rj Da), where d E {10,20,44 45), Da = diag(0.01, 0.0.,..1,.....................,. 0.1,..., 0.11) and |4, = (..,,.....,
P
0J with j,j E (-2, ..]
a 1, and 6 = 0.5. In both case, the proposal is a
(2) Funnel distribution (Fun) π(z) = N(x;; 0, a²) II N(;;; 0, 2br1 ) with d E {10, 20, 45}. N(O, Ida) with 0² =5
The NEO-IS estimator is compared with (i) the IS estimator using the proposal p. (ii) the Adaptive Importance Sampling (AIS) estimator of [30], (iii) Stochastic Normalizing Flows (SNF) and (iv) the Neural Importance Sampling (NIS)² For NEO-IS,
w 1 (k) with K 10 (ten steps on the forward orbit), and conformal Hamiltonian dynamics y = I, M = 5 Id2 for dimensions d {10, 20), and 7 = 2.5 for d 45 (where 7 is the damping factor, M the mass matrix, h is the stepsize of the integrator). The parameters of AIS are set to obtain a complexity comparable to NEOIIS; Appendix 1. For NIS, we use the default parameters and for SNF used the same architectures as in [33]. In Fun, we set = 0.2, K 10, M = 5 Idg, and h = 0.3. The IS estimator was based on 5 10 samples, and NIS, NEO-IS and AIS were computed with 5 10a samples. Figure 2 shows that NEO-IS consistently outperforms the competing methods.
30
30
30
26
16
16
10
10
10
6
25
25
25
14
20
20
20
16
15
15
NEO
IS SNF
NIS
NEO
IS SNF
NIS
AIS
NEO
SNF
NIS
AIS
Figure 2: Boxplots of 500 independent estimations of the normalizing constant in dimension
{10, 20,,20,4400 45) (from left to right) for MG25 (top) and Fun (bottom). The true value is given by the red line. The figure displays the median (solid lines), the interquartile range, and the mean (dashed lines) over the 500 runs
IImplementation available at hwt.:aaww..cooooooeeeeeeeee htt.g//wwwww.oooeeeee/eootttttta izing_flose. Implementation available at https://github. ctt.:l..com///eeeeeeeeeeeee hwwpa//o.....ootttteee/ee/iiiaaa

---

Sampling NEO-MCMC is assessed for the distributions (MG25) (d = 40) and Fun (d = 20). NEO-MCMC sampler compared with (i) the No-U-Tum Sampler Pyro library [4] - and (ii) i-SIR algorithm [25]. The proposal distribution is N(0, o Ida) with of 5. Dependent proposals are used (see (15)) with m(x, x²) N(a'; az, of a²) Ida) with a 0.99. For NUTS, the default parameters are used. For i-SIR, we use the same number of proposals N = 10, proposal distribution and dependent proposal for NEO-MCMC. To perform a fair comparison, time for all three algorithms. The number of iterations for correlated i-SIR, NEO-MCMC, and NUTS are 4- 10%, 4. 10 and 5 100, respectively. Figure 3 displays the empirical
the same clock
Figure 3: Empirical 2-D histogram of the samples of different algorithms targeting MG25 (top) and Fun (bottom). Left to right: samples from the target distribution, correlated i-SIR, NUTS, NEO-MCMC.
two-dimensional histograms of the two first coordinates of samples from the ground truth, i-SIR, NUTS and NEO-MCMC sampler. It is worthwhile note that NEO-MCMC algorithm performs much better for MG25 which is a very challenging distribution, even for SOTA algorithm such as NUTS, which struggles to eross energy barriers between modes. For Fun, NEO-MCMC performs favourably with respect to NUTS, which is well adapted for this type of distributions.
Block Gibbs Inpainting with Deep Generative models and NEO-MCMC We apply NEO- MCMC to the task of sampling the posterior of a deep latent variable model. To be consistent with the rest of the paper, we use non-standard notation here with x being the latent variable and the obser- vation. More precisely, we assume that x ~ N(0, Ida) and a conditional distribution p(z x) which generates an image 2 = (2 (a'..... 2 =D) E D Given family of parametric decoders {a + Po x). M training involves finding the MLE 0" = arg maxage Pa (D). As pa (z) = po(2 x) w))(zx)ck (dr, the likelihood is intractable and to alleviate this problem, [14] pro- posed to train jointly an approximate posterior go (zr[z) that maximizes a tractable lower-bound on the log-likeliin nggliiklihood:: ELBO( 0, x) [Ex=gs(-le) [log Pe (z, X)/9s go (X|=)) S Pe (z), where (x | z) is tractable conditional distribution with parameters & E 4b It is assumed in the sequel that conditional to the latent variable x, the coordinates are independent, i.e. po x) 11 (o
0 E )). and training set D } j=1i==
Note that it is possible to train VAE with the NEO algorithm, using the unbiased estimate of the normalizing constant to construct an ELBO. This approach is described in the supplement Appendix E. We do not focus on this approach here and assume that the VAE has been trained and we are only interested in the sampling problem. In our experiment, 3 [16]. We consider the Block Gibbs inpainting task introduced in [15, Scction 5.2.2]. Given an image 2, denote by 2²] the top and the bottom half pixels. Assume only 2 is observed, then we are interested in in-painting the bottom of an image by the posterior distribution of z given =t. This is achieved using Block Gibbs sampling. A two-stage Gibbs sampler amounts to (a) sampling pa- (ar)2*,22 2 and (b) sampling pe- [2"|r, 2t) = pe- (2*(2:) (since 2 and 2' are independent conditional on rt). Given 2k (2|, ={), we sample at each step 24 pg- (x =x) and then
a VAE trained on CelebA dataset
PPblicly available online, see https: //g thtb. cwm/ cotm:/aanDuus/aiseetttaooo results/betail_cel/

---

Figure 4: Two examples for the Gibbs inpainting task for CelebA dataset. From top to bottom (twice) i-SIR, HMC and NEO-MCMC: From left to right, original image, blurred image to reconstruct, and output every 5 iterations of the Markov chain. Last line: a forward orbit used in NEO-MCMC for the second example.
2441 pg- (2 xR). We then set 26+1 (zi, zl+1). Stage (b) is elementary but stage (a) is challenging. We use an MCMC-within-Gibb scheme using different samplers. We use the following decomposition of pa- (I 2) x (xx) for p(z) x L (z 2) and L(z) Pe- (x, 2)/4 (z 2) with 3 E (0, 1). It is possible sample from p(x) do (x 2) is Gaussian. In experiments with CelebA and the chosen trained VAE, we have E IR 10 (recall that æ is our latent variable here), E R 12288 and use 3 0.1. We then compare i-SIR, HMC and NEO-MCMC sampler in stage (a), with the same computational complexity (N 10, K 12, 0.2 for NEO-MCMC, N = 120 for i-SIR, and HMC run with K = 20 leap-frog steps). Again, NEO-MCMC and i-SIR use dependent proposals, with m Random Walk Metropolis kernel with stepsize 0.1. For each algorithm, 10 steps are performed. Figure displays the evolution of the resulting Markov chains. The samples clearly illustrate that NEO-MCMC mixes better than i-SIR and HMC. More details and examples are presented in the supplementary.
Conclusion
In this paper, have proposed new family of algorithms, NEO, for computing normalizing constants and sampling from complex distributions. This methodology comes with asymptotic and non-asymptotic convergence guarantees. For normalizing constant estimation, NEO-IS compares favorably to state-of-the-art algorithms on difficult benchmarks. NEO-MCMC is also able to sample some complex distributions: it is particularly well-adapted to sampling multimodal distributions, thanks to its proposal mechanism which avoids being trapped in local modes. There are numerous potential extensions to this work. For example, would be interesting to consider deterministic transformations other than conformal Hamiltonian dynamics integrators. These transformations could be trained, as for Neural IS, using a variation lower bound. would also be interesting to further investigate the influence of the mixture weights { heez on the efficiency of NEO.
Sampling from complex target distributions and computing their normalizing constants has numerous applications. Our work proposes novel methods to address such problems and has thus potential applications in many areas. This work does not present any foreseeable societal consequence.
Broader impact:
10

---

Acknowledgments and Disclosure of Funding
Arnaud Doucet is partly supported by the EPSRC grant EP/R034710/1. He also acknowledges support of the UK Defence Science and Technology Laboratory (DSTL) and EPSRC under grant EP/R013616/ This part of the collaboration between US DOD, UK MOD and UK EPSRC under the Multidisciplinary University Research Initiative. Alain Durmus and Eric Moulines acknowledge support of the Lagrange Mathematical and Computing Research Center.
Bibliography
[1] Agapiou, S., Papaspiliopoulos, O., Sanz-Alonso, D., and Stuart, A. Importance sampling: Intrinsic dimension and computational cost. Statistical Science, pp. 405-431, 2017.
[2] Akyildiz, Ó. D. and Míguez, J. Convergence rates for optimised adaptive importance samplers. Statistics and Computing, 31(2):1-17, 2021.
[3] Andrieu, C., Doucet, A., and Holenstein, R. Particle Markov chain Monte Carlo methods. Journal of the Royal Statistical Society: Series B, 7263):26--34,, 2010.
[4] Bingham, E., Chen, J. P., Jankowiak, M.. Obermeyer, F,, Pradhan, N., Karaletsos, T., Singh, R., Szerlip, Horsfall, and Goodman, N. D. Pyro: Deep universal probabilistic programming. Journal of Machine Learning Research, 20(1):973-99) 978, 2019.
[5] Burda, Y., Grosse, R., and Salakhutdinov, R. Importance weighted autoencoders. In The 4th International Conference on Learning Representations (ICLR), 2016.
[6] Che, T., Zhang, R., Sohl-Dickstein, J., Larochelle, H., Paull, L., Cao, Y., and Bengio, Y. Your GAN is secretly an energy- based model and you should use discriminator driven latent sampling. arXiv preprint arXiv:2003.06060 2020.
[7] Chopin, N. and Robert, P. Properties nested sampling. Biometrika, 97(3):741-755, 2010.
[8] Craiu, R. V. and Lemieux, C. Acceleration of the multiple-try Metropolis algorithm using antithetic and stratified sampling. Statistics and Computing, 17(2):109, 2007.
[9] Del Moral. P., Doucet, A., and Jasra, A. Sequential Monte Carlo samplers. Journal of the Royal Statistical Society: Series B, 68(3):411-433 2006.
[10] Ding, X. and Freedman, D. J. Learning deep generative models with annealed importance sampling. arXiv preprint arXiv: ar 1906.04904, 2019.
[11] El Moselhy, T. A. and Marzouk, Y. M. Bayesian inference with optimal maps. Journal of Computational Physics, 23 231(2))77155-780, 2012.
[12] Franca, G., Sulam, J., Robinson, D. P., and Vidal, R. Conformal symplectic and relativistic optimization. Journal of Statistical Mechanics: Theory and Experiment, (:20(12)122000))) 2020.
[13] Jia, H. and Seljak, U. Normalizing constant estimation with Gaussianized bridge sampling. In Symposium on Advances in Approximate Bayesian Inference, pp. 1-14. PMLR, 2020.
[14] Kingma, D. and Welling, M. Auto-encoding variational Bayes. In International Conference Learning Representations, 2014.
[15] Levy, D., Hoffman, M. D., and Sohl-Dickstein, J. Generalizing Hamiltonian Monte Carlo with neural networks. In International Conference on Learning Representations, 2018.
[16] Liu, 7.,, Luo, P., Wang, X., and Tang, X. Large-scale celebfaces attributes (celeba) dataset. Retrieved August, (22018):1, 2018.
[17] Maddison, C. J., Paulin, D., Teh, W., O'Donoghue, B., and Doucet, A. Hamiltonian descent methods. arXiv preprint MrXiv:1809000044 2018.

---

[18]
Müller, T., McWilliams, B., Rousselle, F., Gross, M., and Novák, J. Neural importance sampling. ACM Transactions on Graphics, 38(145), 2019.
[19] Neal, R. M. Annealed importance sampling. Statistics and Computing, 11:125-139, 2001.
[20] Owen, A. and Zhou, Y. Safe and effective importance sampling. Journal of the American Statistical Association, 95(449):135-143 2000.
[21] Papamakarios, G., Nalisnick, E.,, Rezende, D. J., Mohamed, S., and Lakshminnaayanan, B. Normalizing flows for probabilistic modeling and inference. arXiv preprint arXiv: 191.0022) 2019.
[22] Prangle, Distilling importance sampling. arXiv preprint arXiv:1910.000 2019.
[23] Rotskoff, G. and Gonden-Eijndess E. Dynamical computation the density states and Bayes factors using nonequilibrium importance sampling. Physical Review Letters, 122(15))150602, 2019.
[24] Rubin, D. B. Comment: A noniterative sampling/imporrtnce resampling alternative to the data augmentation algorithm for creating few imputations when fractions of missing information are modest: The SIR algorithm. Journal of the American Statistical Association, 82(398): 542-543, 1987.
[25] Ruiz, F. J., Titsias, M. K., Cemgil, T., and Doucet, A. Unbiased gradient estimation for variational auto-encoders using coupled Markov chains. In Uncertainty in Artificial Intelligence, 2021.
[26] Shestopaloff, A. Y., Neal, R. M., al. Sampling latent states for high-dimensional non-linear state space models with the embedded hmm method. Bayesian Analysis, 13(3):797-822, 2018.
[27] Skare, Ø., Bolviken, E., and Holden, L. Improved sampling imnooitanemme resampling and reduced bias importance sampling. Scandinavian Journal of Statistics, 30(4):719-737, 2003.
[28] Skilling, J. Nested sampling for general Bayesian computation. 833-859, 2006.
Bayesian Analysis, 1(4):
[29] So, M. K. Bayesian analysis of nonlinear and non-Gaussian state space models via multiple-try sampling methods. Statistics and Computing, 16(2):125-144 2006.
[30] Tokdar, S. T. and Kass, R. E. Importance sampling: review. Wiley Interdisciplinary Reviews: Computational Statistics, 2(1):54 60. 2010.
[31] Turner, R., Hung. J., Frank, E., Saatchi, Y., and Yosinski, J. Metropolis Hasttolls-HHasiinss generative adversarial networks. In International Conference Machine Learning. pp. 6345-6353. PMLR. 2019.
[32] Wirnsberger, P., Ballard, A. J., Papamakarios, G., Abercrombie, S., Racanière, S., Pritzel, A., Jimenez Rezende, D., and Blundell, C. Targeted free energy estimation via learned mappings. The Journal of Chemical Physics, 153(14):144)) 12, 2020.
[33] Wu, H., Köhler, J., and Noe, F. Stochastic normalizing flows. In Advances in Neural Information Processing Systems, volume 33, 2020.
[34] Wu, Y., Burda, Y., Salakhutdinov, R., and Grosse, R. On the quantitative analysis decoder- based generative models. arXiv preprint arXiv: 2016.
12


Reviews:
[{"review_id": "qwdhwyXZ7A_", "reviewer": "Reviewer_JCRj", "summary": "This paper proposes an algorithm that estimates the normalizing constant of a distribution of the form $\\pi(x)\\propto\\rho(x)L(x)$ given samples from $\\rho(x)$. It further extends the algorithm to a sampling algorithm on the distribution. ", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The normalizing constant estimating algorithm NEO-IS is based on the idea of NEIS, introduced in a previous work. NEIS can suffer from bias when the discretization step is not small enough. NEO-IS reduces the bias of NEIS by using a proposal density in a discrete sum form. While the discrete proposal density reduces the bias, does it make it harder to find a $\\rho_T$ that approximates $\\pi$? Does it increase $\\mathbb{E}_T^{\\varpi}$?\n\nAnother contribution of the paper is a new sampling algorithm, NEO-MCMC. The authors of NEIS did not extend it to a sampling algorithm. \n\nNEO-IS and NEO-MCMC are evaluated experimentally in sec 5. For NEO-IS, experiments on NEO vs. NEIS are only performed on low dimensional MG25 and are only presented in the appendix, while experiments on NEO vs. other algorithms are performed on higher dimensional MG25 and a few other distributions. How does NEO-IS compare with NEIS on sampling from other distributions? \n\nThis paper, especially the mathematical part of it, is not easy to follow. It would be much easier for the readers if when introducing new math equations, the authors could discuss more about their motivation and intuition. \n\nSome typo: In line 85, should it be Appendix A.2?\n\nOverall, I think this paper brings some interesting new ideas, but it needs more work on presentation and comparison with previous works. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Sec 6 discusses some potential future work, but there is not much discussion on limitations. There is no foreseeable potential negative societal impact.  ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "qMdnKp-CnIQ", "reviewer": "Reviewer_2Bce", "summary": "The paper consider IS estimator along the path of the dynamical system", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The idea is natural and technically sounds. However, still I don't understand what is difference with [23], as only given example is conformal Hamiltonian. Possibly, I miss one, will be happy to adjust score in this case. Other concern is relation to the Orbital MCMC https://arxiv.org/abs/2010.08047 Specially, Section 3.3 of it gives the recipes to construct discrete functions with orbits, which I believe is crucial drawback of this work.\n\n----\nUpd. 6->7.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "None", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "jlSL09-275V", "reviewer": "Reviewer_ckCN", "summary": "This paper proposes NEO which extends Non-Equilibrium Importance Sampling (NEIS) to use discrete orbit and extra weights.\nThe probability distribution and sampling process is derived based on the Jacobian determinant.\nThis method could be applied to estimate the partition function and a biased estimation called self-normalized IS is proposed based on estimated partition function.\nThis paper also derive upper bound for the bias and MSE.\nA damped Hamiltonian system is adopted to equip the original system with extra momentum and provide orbit trajectory for NEO.\nNEO is also combined to Sampling Importance Resampling to derive the NEO-MCMC procedure.\nThe authors present reasonable experiments to evaluate their methods.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Compared with NEIS, NEO not only adopt discrete orbit but also introduce an extra weight which could be of practical interest.\nThe paper itself is mostly clear, however certain proof in supplement is hard to follow.\n\nQuestions:\n1. It seems the kernel in eq.15 doesn't satisfy condition in line 225-226. Is it just a typo?\n2. Is there any efficiency guarantee for general NEO-IS estimator defined in Algorithm 1?\n\nTypos:\n1. Line 173: $\\mathbb{E}\\left[f\\left(U^{N}\\right) \\mid X^{1: N}, I^{N}\\right]=J_{\\varpi, N}^{\\mathrm{NEO}}(f)$ to $\n\\mathbb{E}\\left[f\\left(U^{N}\\right)\\right]=J_{\\varpi, N}^{\\mathrm{NEO}}(f)\n$\n2. Line 188: $\n\\mathbb{P}\\left(Y_{n} \\in \\mathrm{A} \\mid Y_{n-1}\\right)=P\\left(Y_{n}, \\mathcal{A}\\right)\n$ to $\n\\mathbb{P}\\left(Y_{n} \\in \\mathrm{A} \\mid Y_{n-1}\\right)=P\\left(Y_{n-1}, \\mathcal{A}\\right)\n$\n\nUpdate after discussion: I thank the authors for answering my questions and I decided to keep my score.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This article clearly describes the assumptions needed for each theoretical result.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1 day"}, "extra_text": {}}, {"review_id": "TkwcxaEjTWe", "reviewer": "Reviewer_dfab", "summary": "This paper studies the problem of sampling from a complicate distribution and approximating the partition function. The authors derive a novel family of importance samplers and MCMC samplers.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper studies the problem of generating samples from a complicated distribution of the form pi(x) promotional to p(x)L(x) and computing the normalizing constant of this distribution. For example, in Bayesian inference p is the prior distribution, pi is the posterior distribution, and L corresponds to the likelihood function. Previous approaches for this task are based on importance sampling, including annealed importance sampling, sequential Monte Carlo, and neural importance sampling. More recently, [23] proposed the non-equilibrium importance sampling (NEIS) which transporting the samples from the reference distribution p using an homogeneous differential flow, and the estimator of the normalizing constant is the integral over the whole orbit instead of only the endpoints. \n\nThe authors propose an improved algorithm (NEO-IS) than NEIS. The samples from the reference distribution are propagated under a discrete-time dynamical system, and the estimator of the normalizing constant is obtained as a reweighed integral over the whole orbit using the importance sampling rule. This estimator is unbiased in contrast to NEIS. Building upon NEO-IS for computing the normalizing constant, the authors also propose NEO-MCMC for approximate sampling. Both theoretical guarantees and numerical experiments are provided to show the outstanding performance of these methods.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "As a minor suggestion, it would be nice to have more discussions on the differences and improvements of NEO-IS over NEIS in the introduction section. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper develops a new, normalizing constant estimation method which is unbiased, and leverages this to achieve improved sampling methods for the same family of distributions. From a technical perspective the insights are definitely above the bar. The main concern that the reviewers and I shared is the presentation of the paper and the lack of intuition provided for some of the more technical aspects of it. While I understand that space is limited, I encourage the authors to expand upon the exposition in Section 2 in particular. Additionally, the experimental evaluation was lacking, however, in the discussions, the authors provided additional experiments and context which I think will improve the paper substantially. 
Decision: Accept (Poster)