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*)) )helr) 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)= = -2 -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 Rd, 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
wx(x) (x) S / /00 Equations (2) and (3)
suggest to estimate the integral f (())) by TNEO (ʃ) N- ΣLEZ (xx)))(((((X())
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
(6)
7x
X
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((TTlp)))) +
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 ((rr)) 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 π (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 hVU 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
IL(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 EA| 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--2 2) and KN = 1 1-EN. Then, for any y E Bdd and k E N. (V, R T| S Key and [P T =||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(x, x') = (xx;; ax, (²(1 - a²) Idg). More generally, we can use a Metropolis- Hastiigs kernel with invariant distribution p. In this case, rn (1(,,, ..t.
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,, xx))
(15)
Since m is reversible with respect to P. for all i, E [N], p(x*)r (e,"),((") (
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 X 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- 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 P 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, = (..,,....., 0J with j,j E (-2, ..]
(2) Funnel distribution (Fun) π(z) = N(x;; 0, a²) IT N(;;; 0, 2br1 ) with d E {10, 20, 45}. N(O, Ida) with 0² =5
a 1, and 6 = 0.5. In both case, the proposal is
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
16
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 http:eaww..cooooooeeeeeeeee htt.g//wwwww.oooeeeee/eoetttttta izing_flose. Implementation available at https://github. ctt.:l..com////eeeeeeeeeeee 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 po (z
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- (arl2*,22 2 and (b) sampling pe- (2 |z, 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
PPublicly available online, see https: //g thtb cww/ 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 imnooitanemmeeeeeeeeeoo 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": "I6AW-I20Jxo", "reviewer": "Reviewer_n3jg", "summary": "The paper puts forward a new family of algorithms, NEO, for computing normalizing constants and sampling from complex distributions. NEO-IS is an importance sampling estimator of the normalizing constant. NEO-MCMC combines NEO-IS unbiased estimator of the normalizing constant with iterated sampling- importance resampling methods.", "questions": "", "limitations": "", "rating": 9, "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": "This paper proposes a novel framework for sampling from complex distributions and the calculation of normalizing constants, and the contribution is significant. The theoretical analysis is thorough. As mentioned in Remark 1, the extension of NEO to non-homogeneous flows will be important to get a more efficient and scalable sampling tool.\n\nThe major drawback of the paper comes from the experimental comparison. In recent years, many trainable sampling methods are proposed by combining flow/MCMC with variational inference, including stochastic normalizing flows, ergodic inference, variational contrastive divergence, etc. It is worth comparing the proposed method and those methods theoretically and experimentally.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes. The authors adequately addressed the limitations and potential negative societal impact of their work. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "Hlq_h0_XXBn", "reviewer": "Reviewer_8kXR", "summary": "Based on Non-Equilibrium IS (NEIS), the authors propose the new importance sampler NEO-IS.\nThe main advantage of NEO-IS over NEIS seems to be that NEO-IS provides unbiased estimates of the normalization constant. They prove the unbiasedness and also propose an MCMC extension for sampling (which was not provided by NEIS).\nThey empirically show that NEO-IS (and its MCMC variant) can be better that other recent methods for tasks of \n(1) finding the marginal likelihood, (2) Sampling from posterior distribution, (3) Inpaiting.\n", "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": "originality:\nThough NEO-IS is based on NEIS, NEO-IS provides a new type of discretization which does not introduce any bias.\nThe MCMC-extension appears to be mostly building on iterated sampling importance resampling method (SIR), which appears not be the main contribution.\n\nquality:\nThey theoretical and empirically support their claims. \nHowever, the comparison with the original NEIS seems to insufficient.\nI do not understand why the comparison to NEIS is in the supplement material, and not in the main paper.\n\nclarity:\nThe paper is extremely difficult to read.\nOne reason is that the author introduce many new (or relatively new) concepts in one paper.\nI think putting the whole Section 3 (MCMC sampling) into the appendix, and instead explaining Section 2 in more detail might help.\n\nsignificance:\nThe work appears to advance the state of the art for estimating normalization constants (marginal likelihood).\nHowever, I am not sure about the significance of this work for posterior sampling, since a comparison to more recent works \nlike for example [1], for which open source implementations are available [2], is missing.\n\n[1] Deng, Wei, Guang Lin, and Faming Liang. \"A Contour Stochastic Gradient Langevin Dynamics Algorithm for Simulations of Multi-modal Distributions.\" NeurIPS 2020.\n[2] https://github.com/WayneDW/Contour-Stochastic-Gradient-Langevin-Dynamics\n\nQuestions:\nIn line 105, it says that they the use the Cauchy-Schwarz inequality. \nI think it's an application of Jensen's Inequality. Do I misunderstand here something?\n\n---\nThank you for the clarification, and your efforts to compare to one more recent MCMC sampling method (like [1]). \nIt would be good to get a more complete picture which includes a discussion about when your method might not work well.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The issue of total computational costs, and runtime is not addressed in the main paper.\n(Is it addressed somewhere in the supplement material?)", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "CoB47rkx6VY", "reviewer": "Reviewer_btQo", "summary": "The paper introduce two sampling approaches named NEO-IS and NEO-MCMC respectively. The former method aims to estimate normalizing constant for an unnormalized target distribution, and the latter method can be executed to do sampling from unnormalized distribution. Empirical experiments reveal impressive performance for both the approaches on Normalizing Constant Estimation and Sampling tasks.  Exact theoretical analysis, especially convergence guarantees are also given in this paper.\n", "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": "Strengths:\n1. The work extends the idea of Non-Equilibrium Importance Sampling (NEIS)'s continous case to discretized method in a novel way. The proposed NEO-IS method estimates the normalizing constant with an importance sampling (IS) trick on orbits of an invertible transforation T applied on reference samples. Although the ideas from the work and NEIS seem similar, I believe the proposed NEO-IS is novel both in approaches and theoretical guarantees.\n2. The NEO-MCMC is a nice adaptation of IS tricks with sampling importance resampling (SIR) pattern. The work also shows that the reversible and ergodic property of their mcmc methods can be satisfied under wild conditions.\n3. The choice of invertible transformation is also discussed in this paper. The authors choose a Symplectic Euler method to derive T and corresponding weighting coefficient. This brings yet another strength to the work.\n\nWeaknesses:\n1.  The work is mainly inspired by NEIS which utilizes full orbits of samples, so it is supposed the introduction part describe more on this topic, however the author seems introduce too much on Neural IS which may lead to confusion.\n2. It is assumed the sampling methods should be tested on more popular sampling tasks such as Bana-shape distribution, Ising Sping sampling (if discrete case is allowed) and so on.  It would be better to also report the sampling effective sample size (ESS), which is a popular metric for MCMC diagnose, or sample KL divergence to some base sampling procedure.\n3. The choice of Block Gibbs inpainting experiments on CelebA dataset seems a little wired from my point of view, because the trained VAE model may bring performance bias in comparison.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "24"}, "extra_text": {}}, {"review_id": "4rzRzoVkRsa", "reviewer": "Reviewer_DsB6", "summary": "The paper proposes a new family of importance samplers based on iterating an invertible map $T$ forwards and backwards, thus generating orbits that serve as importance samples after proper weighting. If normalized importance weights can be computed, the resulting IS estimate is unbiased. Also a self-normalized version is proposed, which is biased but still converges against the correct expectation for $N\\to\\infty$. Since the map $T$ is not assumed to leave the target invariant, the proposed algorithm is called non-equilibrium orbit importance sampling (NEO-IS). \n\nThe authors propose to use conformal Hamiltonian dynamics as a mapping (standard Hamilton dynamics based on the negative log target plus a friction term). The dissipative friction term allows the authors to control how exhaustively phase space is explored.\n\nThe second main contribution is an MCMC algorithm based on the ideas used in NEO-IS. NEO-MCMC applies iterative Sampling Importance Resampling (SIR) within the NEO-IS framework. NEO-MCMC jumps from one point on an orbit to a point on another orbit. Orbits are sampled according to their importance weight.\n\nThe algorithms are benchmarked on various targets (25 Gaussian mixture, Funnel) and applied to training a VAE. \n", "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": "# Main contributions\n\n* The paper proposes new family of importance samplers and MCMC schemes: NEO-IS and NEO-MCMC\n\n* At the core of both methods is the iterative application of an invertible map $T$ under which the target $\\pi$ is not invariant (non-equilibrium mapping)\n\n* The paper focuses on a discrete-time integrator of a conformal Hamiltonian system for $T$\n\n* NEO-IS can be seen as an improvement of non-equilibrium importance sampling (NEIS) in that 1. Z estimator is unbiased, 2. does not rely on accuracy of the discretization \n\n* NEO-MCMC: massively parallel MCMC algorithm to sample from $\\pi$ (independent samplers that are allowed to interact via a resampling mechanism)\n\n# Originality\n\nAs far as I can tell the paper proposes an innovative class of importance sampling and MCMC schemes\n\n# Quality\n\nThe paper is technically sound and the experiments are instructive. \n\n# Clarity\n\nI find the paper a bit hard to follow. Perhaps the paper could be improved by introducing the estimator of the normalizing constant associated with an orbit early on in the paper, because it appears to be central to both NEO-IS and NEO-MCMC. \n\n# Comments\n\n* Figure 1: It is unclear what's shown here. Please provide more details (axis labels etc., what are the contours?). \n\n* Algorithm 1: In step 2, the index $j$ should probably run from $0$ to $K$ for the weights $w_j$\n\n* In a practical implementation, you have to restrict the number of samples per orbit $K$. How do you choose $K$? \n\n* Can the idea of sampling on orbits be related to elliptical slice sampling? Or Gibbs sampling? \n\n* It seems that NEO-MCMC produces many candidate samples (those on one orbit) that are never picked. This seems to be quite wasteful.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "-", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: 
A conceptually and technically innovative paper which proposes a neat class of importance sampling and MCMC schemes. The reviewers are in consensus that the paper has merits for publication.

Please take account of the reviewers' important comments in preparing the final version, in particular those pertaining to the scope of the experimental section (i.e., comparison to existing methods and additional relevant sampling tasks). 


Decision: Accept (Poster)