BR-SNIS: Bias Reduced Self-Normalized Importance Sampling
Authors: Gabriel Cardoso
Sergey Samsonov
Achille Thin
Eric Moulines
Jimmy Olsson
Venue: NeurIPS 2022 Accept (2022)
Keywords: Importance Sampling
Self Normalized Importance Sampling
Monte Carlo
Markov Chain Monte Carlo

Abstract: Importance Sampling (IS) is a method for approximating expectations with respect to a target distribution using independent samples from a proposal distribution and the associated to importance weights. In many cases, the target distribution is known up to a normalization constant and self-normalized IS (SNIS) is then used. While the use of self-normalization can have a positive effect on the dispersion of the estimator, it introduces bias. In this work, we propose a new method BR-SNIS whose complexity is essentially the same as SNIS and which significantly reduces bias. This method is a wrapper, in the sense that it uses the same proposal samples and importance weights but makes a clever use of iterated sampling-importance-resampling (i-SIR) to form a bias-reduced version of the estimator. We derive the proposed algorithm with rigorous theoretical results, including novel bias, variance, and high-probability bounds. We illustrate our findings with numerical examples.

BR-SNIS: Bias Reduced Self-Normalized Importance Sampling
Gabriel Cardoso
Centre de Mathématiques appliquées, Ecole polytechnique, IHU Liryc, fondation Bordeaux Université, Univ Bordeaux, CRCTB U4045, INSERM,
Sergey Samsonov HSE University
Achille Thin
UMR MIA, AgroParisTech. Eric Moulines
Centre de Mathématiques appliquées, Ecole polytechnique,
Jimmy Olsson
Department of Mathematics,
KTH Royal Institute of Technology.
Abstract
Importance Sampling (IS) is a method for approximating expectations under a target distribution using independent samples from proposal distribution and the associated importance weights. In many applications, the target distribution is known only up to normalization constant, in which case self-normalized IS (SNIS) can be used. While the use of self-normalization can have positive effect the dispersion of the estimator, it introduces bias. In this work, we propose new method, BR-SNIS, whose complexity is essentially the same as that of SNIS and which significantly reduces bias without increasing the variance. This method a wrapper in the sense that it uses the same proposal samples and importance weights SNIS. but makes clever use of iterated sampling importance resampling (i-SIR) to form a bias-reduced version of the estimator. We furnish the proposed algorithm with rigorous theoretical results, including new bias, variance and high- nigh-probability bounds, and these are illustrated by numerical examples.
campling-importance
1 Introduction
Background and previous work: Importance sampling [17 11 (IS) is a classical Monte Carlo technique for estimating expectations under some given probability distribution (the target) on the basis of sample of draws from different distribution (the proposal). In the modern of artificial intelligence and statistical machine learning, characterized by large computational resources and Bayesian inference, IS technologies survey. The method not only relevant to situations where sampling from the target is intractable; also be used to achieve variance reduction 24]. When the proposal is dominating the target- in the sense that the support of the latter is contained in the support of the commer-unbiased estimation can be achieved by assigning each draw an importance weight given by the likelihood ratio between the target and the proposal. In the very common case where the target is known only
enjoying revival; see, e.g., [37 23 and [T] for recent
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

up to normalizing constant, consistent estimation can still be achieved by simply normalizing each importance weight by the total weight of the sample; however, since such self-normalized importance sampling (SNIS) involves ratios of random variables, the procedure can only be implemented at the cost of bias, which can be significant in some applications.
More precisely, let (M,, X)) be some state space and π (dxx) x w(x) {((x)) given target probability distribution, where w and À are positive weight function and a proposal probability distribution on (X, 2), respectively, such that the normalizing constant X(w) = w(x) (r))) (this will be our
generic notation for Lebesgue integrals) of i is finite. The SNIS estimator is given by
IM = -EiM wh (X*),
whr = w(= w(X w(x)
(I)
where X (x),.. ...... XM) are independent draws from X, and can be used to approximate (f) = f(x))(dr) for any test function f such that T((fl) < 0o. The estimator ( can be
calculated without knowledge of the normalizing constant X(w), which is intractable in general.
The SNIS estimator is known to be biased; provided that X(w2) < oc, the bias and mean-squared error (MSE) of the SNIS estimator (I over bounded test functions f satisfying Il/ S 1 are given respectively (see [1 Theorem 2.1 by
E f M )1 - x(f) & (12/M)E(T, A].
xf)) & (4/M)K(T, A], (2)
Although is primarily intended to approximate integrals in the form TT rTf). it can also be used to generate unweighted samples being approximately distributed according to æ. In this paper, we consider iterated sampling importance rexampling (i-SIR), proposed in [46]; see [4 [27 51. The i-SIR can be seen an iterative application of the sampling importance resampling (SISR) algorithm proposed by [40]; the k-th iteration is defined as follows. Given a state Ys E X. (i) set X k++1 = Y& and draw X independently from the proposal distribution X; (ii) com- pute, for i E (1,...,N)) N). the normalized importance weights w'y,+11 = w(Xx+1)/ Σ> w(X (iii) select Ys41 from the set k+1 by choosing X141 with probability w In the following, Yk+1 and X will be referred to as the state and the candidate pool, respectively. Following [46) (see Section 2. i-SIR may be viewed (up to an irrelevant permutation of the samples) as two-stage Gibbs sampler targeting an extended probability distribution y on an enlarged state space including the state well as the candidate pool. As this extended distribution allows π marginal with respect to the state, one can expect the marginal distribution of the generated states (Yr),eN, forming themselves a Markov chain, to approach the target π of interest as k tends to infinity.
where k|πT, >] /
2==1
This paper: In i-SIR, the only function of the candidate pool is guide the states selected at stage (iii) towards the target. Thus, since all rejected candidates are discarded, the approach results generally in large waste of computational work. Thus, in the present paper we propose to recycle all the generated samples by incorporating all the proposed candidates X into the estimator rather than only the selected candidate Ys. We proceed in three steps. First, we show that under the stationary distribution PN by of the process (Y,, X|:N kEN generated by i-SIR, the expectation of II ff f(X::N) I (given by (1) equals (f) for every valid test function f (see Theorem 2). Second, we establish that since i-SIR is nothing but a systematic-seat
Gibbs sampler, the two processes (X I:N )eEN and (YK)REN are interleaving (see Theorem 5) thus, if (Yx)eeN is uniformly geometrically ergodic, so is (XF-M >>ee with the same mixing rate KN. Third, as the main result of the present paper, we establish a novel Onc /N) bound on the bias of the estimator I ((X (see Theorem 3). where the exponentially diminishing factor rcly indicates a drastic bias reduction vis-â-vis the standard IS estimator ①1) based on i.i.d. samples. As consequence, approximating T(f) by the average of where the "burn-in" period ko should be chosen proportionally to the mixing
(Xx (::N time of the process, yields an estimator whose bias can be furnished with a bound which is, roughly, proportional to x²t and inversely proportional to the total number M = k: of samples generated in the algorithm (see Theorem 4 To complete the theoretical analysis of these estimators, we also equip the same with variance bounds. The procedure of recycling, as described above, all the samples generated in the i-SIR and to incorporate, at negligible computational cost, the same into the final estimator, will from now on be referred as BR-SNIS. Finally, we test numerically the proposed estimators and illustrate how a significant bias reduction relatively to the standard i-SIR can be obtained at basically no cost.
D) )))
To sum up, contribution is twofold, since we
2

---

propose new algorithm, BR-SNIS, which makes better use of the available computational resources by recycling the candidate pool generated at each iteration i-SIR.
furnish the proposed algorithm with rigorous theoretical results, including novel bias, variance, and high-probability bounds which support our claim that sample recyeling may lead to drastic bias reduction without impairing the variance.
2
Main results
2.1 Statements
The i-SIR algorithm can be interpreted as a systematic-scan two-stage Gibbs sampler, alternately sampling from the full conditions of an extended target 4P on the product space of states and candidate pools. Once the extended target V is properly defined, these full conditionals can be In order to define N,,, we retrieved from a dual representation of y presented in Theorem [ introduce the Markov kernel (see Appendix A..I for comments)
A N (y, dxl N Σe (g(dx') [[dx")][z I1 M(xx))
on X x x which describes probabilistically the sampling operation (i) in i-SIR. Using the kernel AN we may now define properly the extended target N as the probability law
n (d(y,, x):N) = π rdyy) AN (y, dr.::) = N ΣN m(dy)o (dx=)))),d()) I1 A(dz))
on (X (XI+1, ()(+))) Note that since for every A E X' (x(xxxx=) ((A). the target π coincides with the marginal of y with respect to the state. Moreover, it is easily seen that A N provides the conditional distribution, under PN,, of the candidate pool given the state. Defining the kernels
(N INN ,dy) = -N -N w(x")) (dy), [x dyy (N /dlyTTxlxxx'1 (3)
on X x ToN the marginal distribution N of PN with respect to 1: is given by
T (dx::: = ~T I (x II A(dz))
(4)
interesting to note that the marginal nN has a probability density function, proportional to Tvly (x = Ei= w(x')/,, with respect to the product measure A A Using (4) we immedi- ately obtain the following result.
Theorem (duality of extended target). For every N N
(du, :: (dy) A N dx n Idx
L:N NT (a .dy).
Note that the second identity of the dual representation 5 provides also the conditional distribution, under v.,, of the state given the candidates. Consequently, i-SIR a systematic scan two-stage Gibbs sampler which generates Markov chain (Xx, Ya)keN with time-homogeneous Markov kemel
P PN (yre, 2R - dl(k+ xf = (N da x
(###1, dyx+1)
on X N+1 x (N+++)), Note that the law P (Jte = 1:N does not depend on zi which means
that only the state Y₁ needs to be stored from one iteration to the other. Thus, (Yt)keN is Markov chain with Markov transition kernel
P (ik, dyk+1) = A (yk. da I:N II I:N dy = IN (yk, dyk-1)
(6)
(where integration is w.r.t. .rl:N on x X. The kernel (6) was analyzed in S Given some proba-
bility distribution on (X I (N++)) we denote by Pg the law of the canonical Markov chain (Xg, Y KEE with kernel Pa and initial distribution g. Our first results establishes the unbiasedness of the estimator 11 (X I:N) under Pp
Theorem 2. For every N No and π r-integrable function f.
[Ilfs(2 N (dx (f))
The proof Theorem postponed to Appendix A.3
Next, we present theoretical bounds on discrepancy, in terms of bias, MSE and covariance, between IT / (XI:N) and TJ)), for bounded target functions f. when the i-SIR chain initialized according to an arbitrary distribution &. We will work under the following assumption.
3

---

A1. It holds that w = /ollcc//(uu < cc.
Under A1 the state and candidate-pool Markov chains (Yz)aen and (X!:*) JAEN can be shown to be uniformly geometrically ergodic with mixing rate and mixing-time time upper bound
KN (2w (2w + N - 2), Tmix, = [- In 4/ In ky
(7)
respectively; see Theorem beloo for details. Here the mixing time Tmix.N grows logarithmically with the sample size N. The exact value of T is likely to be grossly pessimistie, but we conjecture that the logarithmic dependence in the minibatch size holds true. In addition, under AT we define the constants
bius
[N1(T, Al ++++
(8)
muse ( + (1+ (1,)(1)))),
= = bias (5 mue )2/2 E {0,
With these definitions, the following holds true.
Theorem 3. Assume A
Then for every initial distribution & on (0++,,99((1)) bounded measurable function on (X, X) such that || I N 2 and (k, {) (N*)²
(i) [E I (X
T()] S bias (N - 1)- KN k-1
(i) f
{{})} S Ei S muse (N- - 1) 11-1-1/2
(iii) [ (IW
xff)||| S SKN
1-1 Ei= (N 13--1111/211
where constants are given in 7 and
is worth noting that the bias decreases inversely with the number of candidates and exponentially with the number of iterations (the mixing time of the chain also depends on N). The MSE is also inversely proportional to the number of candidates N. In the light of the previous results, it is natural consider an estimator formed by an average across the IS estimators f(X] ))en associated with the candidate pools generated at the different i-SIR iterations. To mitigate the bias, we remove "burn-in" period whose length kn should be chosen proportional to the mixing time T of the Markov chain (Yx) KEN (which turns out to coincide with that or the chain (X I: )kEN; see Section 2.2 This yields the estimator
I(Ro.)).NN() =
+1=ko+1 IN
of rf). The total number of samples (generated by the proposal X) underlying this estimator is M (N - 1)k. Importantly, all the importance weights included the estimators are obtained as by-product of the i-SIR schedule; thus, it is, for given budget of simulations (i.e., under the constraint that (k: - Ng)NN is constant), possible to compute II (t) for different values of ky, and N with a negligible computational cost. We denote by u (k kn)/k the ratio of the number of candidate pools used in the estimator to the total number of sampled such pools. Note that this type of estimator was already suggested by [47] and also appears in [42].
(9) as well as high-probabillity bound for the same. Define hiis 4Tmix, bias /3, C. ((+1)AA2 (0.22 (i)
Our final main result provides bounds on the bias and the MSE of the estimator
mase
(8/3) Tmix. NS E 1,0,,2), 2m (4/M)<(n IT, X], see
zmse
mise ( 1N 1/4 + 2zme LN 1N and MSE =
Theorem 4. Assume A Then the following holds true for every initial distribution & on (X N+1, (N bounded measurable function on (X, X) such that [I I 1, and N 2
(i) (ko. - S
x(f)
b (UM) -4-ko// T
mixx,
(i) (EI(
{ MSE + ("MC(MM -1 IN 1)
(iii) For every (0, 1), [II (Ao. π (f)l < And (v:MM))/((((((488) with probability
at least 1 6, 8, where Apd = 664w.
As established in Theorem 4 the bias of the BR-SNIS estimator decreases exponentially with the burn-in period Kg, leading to potentially significant bias reduction with respect to SNIS. Still, using a large kn done at price of increased overall MSE (mainly through the term MSE in Theorem 4 (i), which is directly related to kn via v). A natural way reduce the variance is to use
Bootstrap:

---

bootstrap. More precisely, we first apply random permutation to the samples and re- re-comuute BR- SNIS on the basis of the bootstrapped samples. After this, we produce final estimator by averaging over the bootstrapped BR-SNIS replicates. In most applications, the major computational bottleneck consists of sampling from À and evaluating w and f at the samples; thus, the additional operations that this bootstrap approach entails are computationally cheap. Therefore, in our experiments, we use bootstrap in combination with the choice Ko = - (in order to minimize the bound in Theorem
2.2 Elements of proof'
The systematic scan two-stage Gibbs sampler is well-studied MCMC algorithmic structure, and we summarize its most important properties in Theorem 5 beloo see 30 3 and [39] Chapter 9] as well as the references therein. In particular, as shown in [0), the
Ergodic properties of i-SIR:
state and candidate-pool Markov chains (Y+)Ren and (X X )KEN satisfy a duality property referred to as interleaving (Theorem 5 iii)).
Theorem 5. Assume that for every x E X, w(x)= > O, X(w) < oc and that there exists a set C E X such that X(C) > 0 and supzec wxx)/\(w) < CO. Then,
(i) the Markov kernel Px is Harris recurrent and ergodic with unique invariant distribution PN (ii) the Markov kernel PN is n-reversible, Harris recurrent and ergodic.
(iii) the two Markov chains (YK)een and (Xt: )kEN are conjugate of each other with the interleav- ing property, i.e., for every initial distribution and & N, under Fe..
(a) X and X X1:N
1441 are conditionally independent given Yg,
(b) YE and Vs+1 are conditionally independent given XI:N- k+1
(c) moreover, under P Puxx (Yk, X and (Yk, X are identically distributed.
The ergodic behavior of the i-SIR algorithm has been studied in many works; see 26 28 in particular. The analysis is particularly simple under the assumption that the importance weight function w is bounded, imposed by A Recall that the total variation-distance between two probability measures & and g on (X, X²) is given by d7v(E.E") =
( (g)),,, where osc(g) = (uP(a.2")xx> (g(x)) 9(=') denotes the oscillator norm of a measurable function g. The following result establishes the uniform geometric ergodicity of the state chain (Yx)aeN.
(((()) -
Theorem 6. Assume Then for every N 2 2, y E X and k E N. dy (. Kly, where KN is given in 7
The proof is given in 28 5. but we provide it in Appendix A.5 for completeness. For uniformly ergodic Markov chains, it is often more appropriate to work with the mixing time
min E N: supyex dny(P)) (v, m) S 1/4] S Tmiix,
(where T is given in 7)). i.e., the number of time steps required for the distribution of the chain to be within certain total variation distance from its stationary distribution 15). An interesting consequence of the interleaving property is that if the Markov chain (Yt)aen is (geometrically) ergodic, then the Markov chain (X!:&) )EEN is (geometrically) ergodic as well with the same mixing time; see (39 Corollary 9.14)).
Bias of the BR-SNIS estimator: As the BR-SNIS estimator II fXX (where I1 is defined in (3) made up by a ratio of the two unnormalized estimators I'N ((X and I'y (XE=N), a key ingredient in the proof of Theorem is to bound the bias and the ndh order moments of statisties defined as ratios of sums of random variables that are not necessarily independent. The basic idea is to reduce the study of these relations to the analysis of the moments of the numerator and the denominator of these statistics and to exploit their concentration around the respective (conditional and unconditional) means. The main results that we will use in the rest of the paper are summarized in Appendix B
Lemma 7. For every initial distribution & on N+1+1, x((NN))) A E N and bounded measurable function f :: X + R, it holds that
(i) for every E X. ANINf(y) = 1/N)) + (1/N)
(i) EE |
= -AN-x/(Y--), Pe-as.
(ii)) Eg (TNI((X) - ANDx Yι-1 = (N (1/ -
5

---

We now have all the elements that allow us to determine the first important result of this work, namely the bias and the MSE of the estimator N ( of π (f)).
Proof of Theorem 3 We establish the bias bound in (i) and postpone the proof of the bounds on the MSE and the covariance in (ii) and (iii) to the supplement. Define the measure {(A) = {(AxX), e X, and the kernel Px = A x lI X x X. Consequently, Pv Pxf((r-i)) and A AyT x f(x Eg [T n J( (X Y Y
EE v [XX Y J. IP eaa... Since (Y&) is, under g,g, Markov chain with initial distribution and Markov kernel N (see (6) it holds that
[( = E& Ex(PNf(Y = E3 E ( Yoll = '
Consequently, the proof is concluded by establishing that for every h E N",
IPN - T(f) 1 hias k k-1 (NN - 1)-1
(10)
On the other hand, since by Theorem 2 π xP () = π (f), we may use Theorem 6
obtain the bound
I - ((f) |<P PN T(P S N osc(PN
Finally, we establish (10) by ossnd
osc(P f). Note that
osc(Px.)) I 2 Pf - ANTxs/(ANTx/
2 ANT \s
where, for every y E X, using Theorem
II
PNS(U) (WDD:/AAAA////AATwww//a/
< 2
Now, since ANT'N1x(1) 2 (1 1/N)A(w), we get, using Lemma 7
AN PNJ
(2(N 1)) (M(r)) + 33((1 -3M((=-(ww)3))
AsTxIx
2NN
(11)
On the other hand, using the elementary inequality a/b c/ a(d- (a c)/d, we get, as
(f) = Xww))/(w),
AnTxf(t) +() = (L/N)
ANTxf()) {1 - + A(wf)/AU
AxTx1x(0)
AxTxIx(2)
Finally, the bound (10) established by noting that
|AnTx//(ATTxix> -<()) s S2N 22-111110 ( w(y)/(w)) 2N +
(12)
2.3
Related works
The first use of the method, then as variance reduction technique, dates back the '50s; see [3 [22 and the references therein. Today, the renewed interest in IS parallels the flurry of activity in the probabilistic MI. community and its ever-increasing computational demands; thus, is impossible to fully present the literature. We therefore limit ourselves to describing results that have inspired our work, and refer the readers to the recent reviews [ for additional references.
There is clearly plethora of modern ML applications where the standard SNIS estimator may be substantially improved using the BR-SNIS method. To mention just a selection of examples, SNIS plays a key role for robust off- off-cooicy selection strategy BY problems (see, e.g., [ Section 31). Bayesian transfer learning [88 31, variational autoencoders
23 (extending 43 32 )) Bayesian
[9] inference of based models (25), patch- based image restoration [37] and many more. In stochastii-approoximatio procedures, where a statistical estimator or algorithm is employed repeatedly to produce mean-field estimates, controlling its bias becomes critical 44
19 Thus, it is
natural aim at minimizing the bias for a given computational budget, provided that the variance does not explode. For this reason, bias reduction (or unbiasedness) in stochastic simulation has been

---

the subject of extensive research during the last decades; see 12 16 The present paper contributes to this line of research.
interest in SNIS, there are only few theoretical results. For example, 1 Theorem 2.1] provides bounds on the bias and variance of SNIS, results that we extend to BR-SNIS in Theorem 3 Moreover, [32] Proposition D.3] provides a suboptimal variance bound based on a bound for the second-order moment. This result can be compared to the sophisticated sub-Gaussian concentration bound for BR-SNIS obtained in Theorem (a result that can be obtained for SNIS using the same proof mechanism; see Appendix A.8) Finally, [23 obtains a semi-empirical sub- Gaussian concentration inequality using the Efron- Stein estimate of variance and the Harris inequality.
Despite
As MCMC sampling method, the i-RIR algorithm that has been applied successfully in many situations. It was recently used-under the alternative name conditional importance sampling--a 34 for Markovian score climbing. In the same work, it is mentioned that it is possible to "Rao- Blackwellize" the gradient of the score using the proposed candidates, which is in line with the recycling argument underpinning the estimator suggested by us, but without theoretical justifications. In its most basic form, the i-SIR algorithm appeared in the pioneering work of [46]. The same idea played key role in the development of the particle Gibbs sampler 4 351, which extends i-SIR principles to sequential Monte Carlo methods. An approach very similar to BR-SNIS can be taken also in this context; however, casting BR-SNIS into the framework of particle Gibbs methods is a non-trivial problem which is the subject of ongoing work.
Experimental results
In this section we compare numerically the performances of BR-SNIS and SNIS in three different settings: mixture of Gaussians, Bayesian logistic regression and variational autoencoders (VAB). We leave to the supplementary material (Appendix C.T the detailed numerical verification of the bounds established in Section 2
Mixture of Gaussian distributions: We start with an example where the target distribution π is
a mixture of two Gaussian distributions of dimension d = 7, as shown in Figure 2a The proposal distribution is a Student distribution with v = 3 degrees of freedom. The test function is f = 1 n- where A and B are a d-dimensional rectangle intersecting each of the modes of π (see Appendix T. for precise definitions). We verify the positive effect of bootstrap in Figures La and bb computing the bias and the MSE over 1000 chains for N = 129 for several k. The purple, green, and red curves correspond to a number of bootstrap rounds of 1, 21, and 201, respectively. We illustrate the decay of the mean Sliced Wasserstein distance (according to 77) with is for different values of N (N = 8 purple, N = 32 green, .N- = 64 orange, and N = 128 red) in Figure Ic The decay of the Wassertein distance is directly linked to the mixing time of the i-SIR kernel (see 77), and hence allows us to represent the effective mixing time of the chain. Moreover, we represent the theoretical slopes as dashed lines. This illustrates that the effective value of Tmir.N is smaller than its theoretical bound. The bias and MSE for SNIS with M 25600 shown in black dashed lines.
We compare the bias (Figure 2b and MSE (Figure 2c of BR-SNIS and SNIS for a fixed budget with a total number of M 16384 samples. We run the experiments 10s times; we compute the bias and MSE over batches of 10 replications using the true value of Tff) computed above (the boxplots in Figure 2 are therefore obtained over 100 replications). For the algorithm BR-SNIS
used N E { {129, 513). J. kig = kimaxx - 1 and kmax = M//N 1) bootstrap rounds. As can be seen from Figure 2b BR-SNIS significantly reduces bias (by factor of almost 10) w.r.t. standard SNIS for both configurations, while MSE increases only slightly (at around 20%), as can be seen in Figure 2c The code used for this experiment is available at [1] We also show in Appendix | ko 0.625 can lead to about 3 times less bias w.r.t. standard SNIS while only augmenting the MSE of 10%. We have also compared in BR-SNIS to zero bias estimators based on SNIS such 33 in shown in Appendix
the results
Bayesian Logistic regression: We consider posterior inference in a Bayesian logistic regression model. Let D Dinin (x,; yt) be dataset, where each x; ddd is vector of covariates and V: E 1) is binary response. Let p(y: xx; {1 exp(->ı 3 x, 0)} be the probability of the ith observation at 0 E θ C IRd and (d0) be prior distribution for 0. The Bayesian posterior is
hungs://gthubbcoomm/aabbbdbbbbbn
7

---

135
3329
10:50
3335
10m
0.33
725
100
(a) MSE
(b) Bias in log scale
(c) Sliced Wasserstein
Figure 1
163
3122
300
3135
129
SNIS
(a) 2d projection
(b) Bias
(c) MSE
Figure 2: Comparison between SNIS and BR-SNIS for the same budget. In each boxplot the dotted
line represents the mean value of the samples.
given
(d0) = Z Z To(d0) (0), (r( In plys x,;0), Z Z= ) (e))(((()))
the heart failure clinical records (d 13, T 299), breast cancer detection (d = 30, T = 569), and Covertype (d = 55, 7 4 10 datasets from the UCI machine learning repository. For Covertype,
For numerical illustration,
use Cover type 1 (Spruce/Fir) and Cover type (Lodgepole Pine) classes to define a binary classification problem. As prior, we use Gaussian distribution N(O, - 2I) with 72 5 10-2 The importance distribution À is Gaussian with mean and diagonal covariance learned by variational inference; see Appendix C.2 for details. The boxplots for bias Figure were constructed the same way as those in Figure
We compare two test
CoverType
Breast
Heart 0.00023 +/- 7.24e-5
SNIS, M = 32
0.0028 +/- 0.0012
0,00011 +/- 6,04e-5
BR-SNIS, M= 32
0.0014 +/- 0.0003
7.9c-5 +/- 5.5e-5
0,00012 +/- 6. 6.7c-5
SNIS, M 512
0.0026 +/- 0.0017
4.3e-5 +/- 3.3e-5
7.8e-5 +/- 6.8e-5
BR-SNIS. 512
0.0013 +/- 0.0003
3.5e-5 +/- 2.2e-5
4.9e-5 +/- 5.2e-5
Table I: Comparison of the TV distance between the posteriors (Lower better).
functions, f(0) corresponding to evaluation of the posterior mean, and f(0) p(y x, 0). where (x, 3)) E DDesz- This last function allows us to compute a TV distance for the predictive distribution. Indeed, in classification context, one can compute the TV distance between any two predictive distributions and P
= = Σ. E| pply = X,, D Drriin) - p(y = Xi, Drroia)s
where we compare predictive distribution p(y x, Dimin) f ply x. (0)d0 and 0 is estimation of this quantity, provided in the experiments by SNIS BR-SNIS. From Figure 3 we can see that for each dataset we have constant decrease in bias, while the variance increases only slightly. We plot the bias in other components of 0 and provide further numerical details in Appendix

---

302
2004
2218
1294
$227
2210
R212
(a) Hcart
(b) Breast 11
(c) Covertype
Figure 3: Visualization of the distribution for each datasets. Each boxplot is grouped by budget, the left one represent SNIS and the right represent BR-SNIS.
Latent dimension (d)
VAE
IWAE
BR-IWAE (k: 8)
10
87.40 + 0.14
86.44 + 0.10
-86.29 - 0.09
20
83.55 + 0.10
-81.81 + 0.06
81.66 - 0.12
40
82.90 I 0.07
-81.05 + 0.09
-81.01 = 0.05
Table 2: Comparison of the mean log likelihood over the MNIST validation set (Higher is better).
Generative Model; We now extend our methodology to the more complex deep latent generative models (DLGM). A DLGM defines a family of probability densities po over an observation space RR by introducing latent variable (with respect to Lebesgue measure) and aiming to find a parameter 0 maximizing the marginal log- likelihood of the model pe (x) = po(xx, 2)d2. Under simple technical assumptions, by Fisher's identity,
Rd defining the joint density function pe (xr
V logog (o)
Ve pe(z, z)po(z 2)d2,
(13)
In most cases, the conditional density Po x>) (1, 2)/po(<)) is intractable and only be sampled. The variational autoencoder [1 is based on the introduction of an additional parameter ø and family of variational distributions 2o (z x)). The joint parameters (0,0) are then inferred by maximizing the evidence lower bound (ELBO) defined by
C(O,0) v) log (L ()) |l po x)) S (o))
This basic setup has been further developed and improved in many directions. Here we consider the importance weighted autoencoder (IWAE) [8], which relies on SNIS to design a tighter ELBO on the log- ligliikel The objective of the IWAE is given by
(0. Φ) log (M- EM wo. II (6(2 x))2;
where we, (v).a.((=) pr( 2)/ (z (= denote the importance weights. However, writing, following 8 Eq. (13)).
VoL (0, = S wold. V log o. I
go(ze æ)dze,
where w/)0 wg.0. wp. (2:) E/ M
(z;) are normalized importance weights, yields an expres-
sion of the gradient that corresponds exactly to the biased SNIS approximation of (13). Thus, the
optimization problem will suffer from bias. We hence propose use BR-SNIS for learning IWAE. The proposed algorithm proceeds in two steps, which are repeated during the optimization (details are given in Appendix
First, update the parameter & as in the IWAR algorithm (using the reparameterization trick and following the methodology of (8] according to o(++1) (()) 7, Las (B(1), ((()).
Second, update the parameter 8 by estimating 13 using BR-SNIS for T(2) p0 2). f(2)
V, log Po (z, 2) and A(z) 9o z).
We refer to this model as BR-IWAF. As illustration, we train the model using the binarized MNIST
dataset [1], where E {0, 791 are binarized digits images dimension 784. For both for the encoder de and the decoder Pe,
convolutional neural network (more details are given in

---

Appendix C.3
For comparison, we estimate the log- -oglliikl using the VAE, IWAE and BR-IWAE approaches, and the result reported in Table All models are run for 100 epochs, using the Adam optimizer (20) and learning rate of 10 Thee complete experimental details are given in Appendix
Conclusion
In this paper, have introduced novel method, BR-SNIS, which improves over SNIS when it comes to producing close to unbiased estimates of expectations taken w.r.t. to distributions known only up normalizing constant, ubiquitous problem in machine learning and statistics. The high performance of BR-SNIS is supported theoretically by non-asymptotic bias, variance and high-probabilityy bounds. We illustrate method on various examples, which show the practical advantages of BR-SNIS over SNIS. Finally, BR-SNIS is naturally adapted to other IS based methods, for example [45] which use Hamiltonian (gradient-basedd transform [36] part of the IS proposal.
The extension of BR-SNIS to 45 would produce an Hamiltonian based sampler able to recycle
all samples, contrarily to other classical Hamiltonian- methods [36 [4]. BR-SNIS can also be extended to Particle Markov chain Monte Carlo methods such as Particle Gibbs with Ancestor sampling [29]
Acknowledgement
The work of G. Cardoso is supported through the Investment of the Future grant, ANR-10-IAHU- 04. from the government of France through the Agence National la Recherche. The work of 1------N------IIAA
and within the framework of the HSE University Basic Research Program. Part of this work has been carried out under the auspice of the Lagrange Center in Mathematics and Computing. The work of J. Olsson is supported by the Swedish Research Council, Grant 2018-05230. The work of E. Moulines is supported by ANR CHIA 002 SCAI.
S. Samsonov was supported by SCAI
10

---

References
[1] S. Agapiou, O. Papaspiliopooloss D. Sanz-Alonso, and A. M. Stuart. Importance sampling: Intrinsic dimension and computational cost. Statistical Science, 32(3):405-431, 2017.
[2] D. Aldous, L.. Lovász, and P. Winkler. Mixing times for uniformly ergodic markov chains. Stochastic Processes and their Applications, 71(2):665-188, 1997.
[3] C. Andrieu. On random-and systematic-scan samplers. Biometrika, 103(3):719-726, 2016
[4] C. Andrieu, A. Doucet, and R. Holenstein. Particle Markov chain Monte Carlo methods. Journal of the Royal Statistical Society: Series B, 72(3):269 -4222226622222 2010.
[5] C. Andrieu, A. Lee, and M. Vihola. Uniform ergodicity of the iterated conditional sme and geometric ergodicity of particle gibbs samplers. Bernoulli, 24(2):842 872, 2018.
[6] D. M. Blei, A. Kucukelbir, and J. D. McAuliffe. Variational inference: A review for statisticians. Journal of the American statistical Association, 112(518):859-877) 2017.
[7] N. Bonneel, J. Rabin, G. Peyré, and H. Pfister. Sliced and Radon Wasserstein Barycenters of Measures. Journal of Mathematical Imaging and Vision, 1(51):22 04.:222-55,222 2015.
[8] Y. Burda, R. Grosse, and R. Salakhutdinov. Importance weighted autoencoders. arXiv preprint arXiv:1509.005: 2015.
[9] J. Chen, D. Lian, B. Jin, X. Huang. K. Zheng, and E. Chen. Fast variational autoencoder with inverted multi-index for collaborative filtering. In Proceedings of the ACM Web Conference 2022, pages 1944-1954, 2022.
[10] R. Douc, E. Moulines, P. Priouret, and P. Soulier. Markov chains. Springer Series in Operations Research and Financial Engineering. Springer, Cham, 2018
[11] V. Elvira and L. Martino. Advances in importance sampling. arXiv preprint wrXiv:2102.05400 2021.
[12] W. Glynn and C.-H. Rhee, Exact estimation for markov chain equilibrium expectations. Journal of Applied Probability, 51(A)3377-389, 2014.
[13] T. Hesterberg. Weighted average importance sampling and defensive mixture distributions. Technometrics, 37(2):185-194, 1995.
[14] M. D. Hoffman, A. Gelman, al. The no- U--Un sampler: adaptively setting path lengths in Hamiltonian Monte Carlo. J. Mach. Learn. Res., 15(1):1593-1623, 2014.
[15] D. Hsu, A. Kontorovich, D. A. Levin, Y. Peres, C. Szepesvári, and G. Wolfer. Mixing time estimation in reversible markov chains from single sample path. The Annals of Applied Probability, 29(4):2439-22 22002240,,880 2019.
[16] P. E. Jacob, J. O'Lerry and Y. F. Atchadé. Unbiased markov chain monte carlo methods with couplings. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 82(3):543-600, 2020.
[17] H. Kahn and A. W. Marshall. Methods reducing sample size in monte carlo computations. Journal of the Operations Research Society of America, 1(5):263-278, 1953.
[18] A. Karbalayghareh, X. Qian, and R. Dougherty. Optimal bayesian transfer learning. IEEE Transactions on Signal Processing, 66(14))3724-377) 3739, 2018.
[19] B. Karimi, B. Miasojedow, F. Moulines, and H.-T. Wai. Non-asymptotic analysis of biased stochastic approximation scheme. In A. Beygelzimer and D. Hsu, editors, Proceedings of the Teirtt-Second Conference Learning Theory, volume 99 of Proceedings of Machine Learning Research, pages 1944-1974. PMLR, 25-28 Jun 2019.
[20] D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. In ICLR 2015, 2015.

---

[21] D. P. Kingma and M. Welling, Stochastic gradient vb and the variational auto-encoder. In Second International Conference on Learning Representations, ICLR, volume 19, page 121. 2014.
[22] D. P. Kroese and Y. Rubinstein. Monte carlo methods. Wiley Interdisciplioary Reviews: Computational Statistics, 4(1))48-58, 2012.
[23] I. Kuzborskij. C. Vernade, A. Gyorgy, and C. Szepesvári. Confident off-policy evaluation and selection through self-normalizee importance weighting. In International Conference Artificial Intelligence and Statistics, pages 640-648, PMLR, 2021.
[24) R. Lamberti, Y. Petetin, F. Septier, and F. Deshouvries. A double proposal normalized impor- tance sampling estimator, In 2018 IEEE Statistical Signal Processing Workshop (SSP), pages 238 248. IEEE, 2018
[25] J. Lawson, G. Tucker, B. Dai, and R. Ranganath. Energy-insping models: Learning with sampler-induced distributions. Advances in Neural Information Processing Systems, 32, 2019.
[26] A. Lee. On auxiliary variables and many-core architectures in computational statistics. PhD thesis, University of Oxford, 2011.
[27] A. Lee, C. Yau, M. B. Giles, A. Doucet, and C. C. Holmes. On the utility of graphics cards to perform massively parallel simulation of advanced Monte Carlo methods. Journal of computational and graphical statistics, 19(4):769-789 2010.
[28] Lindsten, R. Douc, and E. Moulines. Uniform ergodicity of the particle gibbs sampler. Scandinavian Journal of Statistics, 42(3):755-77,201 2015.
[29] Lindsten, M. I. Jordan, and B. Schön. Particle gibbs with ancestor sampling. 2014.
[30] J. S. Liu, W. H. Wong, and A. Kong. Covariance structure of the gibbs sampler with applications to the comparisons of estimators and augmentation schemes. Biometrika, 81(1):27-40, 1994.
[31] O. Maddouri, X. Qian, F. J. Alexander, R. Dougherty, and B.-J. Yoon. Robust importance sampling for error estimation in the context of optimal bayesian transfer learning. Patterns, page 100428, 2022.
[32] A. M. Metelli, M. Papini, F. Faccio, and M. Restelli. Policy optimization via importance sampling. Advances Neural Information Processing Systems, 31, 2018.
[33] L. Middleton, G. Deligiannidis, A. Doucet, and P. E. Jacob. Unbiased smoothing using particle independent peetropolis-hastingg In K. Chaudhuri and M. Sugiyama, editors, Proceedings of the Twenty-Second International Conference Artificial Intelligence and Statistics, volume 89 of Proceedings of Machine Learning Research, pages 338-2337. PMIR, 16-18 Apr 2019.
[34] C. Naesseth, F. Lindsten, and D. Blei. Markovian score climbing: Variational inference with kl
(pll q). Advances in Neural Information Processing Systems, 33:15499-15510, 2020.
[35] C. A. Naesseth, F. Lindsten, T. B. Schön, et al. Elements of sequential monte carlo. Foundations and Trends@ in Machine Learning, 12(3)307-392, 2019.
[36] R. M. Neal al. Meme using hamiltonian dynamics. Handbook of markov chain monte carlo, 2(1 1)12) 2011.
[37] M. Niknejad, Bioucas-Dias, and M. A. Figueiredo. External patch- image restoration using importance sampling. IEEE Transactions on Image Processing, 28(9):4460-4470, 2019.
[38] D. Paulin. Concentration inequalities for markov chains by marton couplings and spectral methods. Electronic Journal of Probability, 20:1-32, 2015.
[39] C. Robert and G. Casella, Monte Corlo statistical methods. Springer Science & Business Media, 2013.
12

---

[40] D. B. Rubin. Comment: A noniterative Sampling/Importane Resampling alternative to the data augmentation algorithm for creating a few imputations when fractions of missing information are modest: The SIR algorithm. Journal of the American Statistical Association, 82(398):542-543, 1987.
[41] R. Salakhutdinov and I. Murray. On the quantitative analysis of deep belief networks. In Proceedings of the 25th international conference Machine learning, pages 872 879, 2008.
[42] T. Schwedes and B. Calderhead. Rao-blackwellised parallel meme. In A. Banerjee and K. Fuku- mizu, editors, Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Leurning Research, pages 3448-3456 PMLR, 13-15 Apr 2021.
[43] A. Swaminathan and T. Joachims. The self- normalized estimator for counterfactual learning. advances neural information processing systems, 28, 2015.
[44] V. B. Tadić and A. Doucet. Asymptotic bias of stochastic gradient search. The Annals of Applied Probability, 27(6):3255 3304, 2017.
[45] A. Thin, Y. Janati EI Idrissi, S. Le Corff, C. Ollion, E. Moulines, A. Doucet, A. Durmus, and C. X. Robert. Neo: Non equilibrium sampling on the orbits of a deterministic transform. Advances in Neural Information Processing Systems, 34:1 14:17060-17077 2021.
[46] H. Tjelmeland. Using all Massings proposals to estimate mean values. Technical report, 2004.
[47] H. Tjelmeland. Using all metropolis- proposals to estimate mean values. 2004.
[48] R. Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47, Cambridge university press, 2018
[49] M. Wainwright. High-dimensionns statistics: A non-asymptotic viewpoint, volume 48. Cambridge University Press, 2019.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [No] Our work of theoretical and methodological nature.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yss]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proof' of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material URI.)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (c.g., with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g.. type of GPUs, internal cluster, cloud provider)? [Yes]
4. If you using existing assets (e.g., code, data, models) curating/releusing assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any assets either in the supplemental material URL? [Yes] Code added to the supplementary material.
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A] Not applicable
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A] Not applicable
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A] Not applicable
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A] Not applicable
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A] Not applicable
14


Reviews:
[{"review_id": "xhjej3dZayO", "reviewer": "Reviewer_9JEd", "summary": "This work analysis a well-known multiple-proposal MCMC kernel known as i-SIR. The main contributions are \n\n1. Theorem 3, which bounds the rate at which the bias/error decays with the number of iterations or number of particles.\n2. Theorems 4, which gives bias, mean-square error, and high-probability bounds for a Rao--Blackwellised estimator (9) which re-cycles (almost) all generated samples.", "questions": "In  Line 241, it is stated that \"An approach very similar to BR-SNIS can be taken also in [the particle Gibbs] context\". What does this refer to? Do you mean one could use a similar Rao--Blackwellisation or similar strategy of analysis?", "limitations": "Yes", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. Novel bias/error bounds for the i-SIR algorithm and for the \"Rao--Blackwellised\" estimator from (9) (as well as a high-probability bound for the latter).\n\nWeaknesses:\n\n1. I was slightly disappointed after reading the paper because the title suggests a way to reduce the bias in self-normalised importance sampling (SNIS) but the analysed method is an MCMC algorithm. And the iterative nature of this MCMC algorithm may render it inapplicable in some settings in which \"standard\" SNIS is employed.\n\n2. Theorems 1 and 2 are well known in the literature on particle MCMC methods. It might worth mentioning this somewhere on Page 3 to avoid the false impression that these are novel.\n\n3. From reading the manuscript, it is not 100% clear to me whether the Rao--Blackwellised estimator in Equation 9 is claimed to be a novel contribution (Page 2 makes it sound as if it is). Just in case, it might be worth adding a reference to at least the first of the following sources where this Rao-Blackwellised estimator has been previously suggested (albeit without any theoretical analysis):\n\n* Tjelmeland, H. (2004). Using all Metropolis–Hastings proposals to estimate mean values (No. NTNU-S-2004-4).\n\n* Yang, S., Chen, Y., Bernton, E., & Liu, J. S. (2018). On parallelizable Markov chain Monte Carlo algorithms with waste-recycling. Statistics and Computing, 28(5), 1073-1081.\n\n* Schwedes, T., & Calderhead, B. (2021, March). Rao-blackwellised parallel MCMC. In International Conference on Artificial Intelligence and Statistics (pp. 3448-3456). PMLR.\n\n* Schwedes, T. (2019). Parallel Markov chain quasi-Monte Carlo methods. PhD thesis.\n\n\n\n\nTypos et al:\n\n- define $\\mathbb{N}^*$\n- $n$ -> $N$ in Theorem 4", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "e5urouJ0bep", "reviewer": "Reviewer_nbwq", "summary": "The authors describe and analyze an iterated importance sampling resampling scheme  and a possible bias-reduction technique.", "questions": "The paper contains very interesting material, in my opinion. I believe that the degree of novelty is mainly in the bias reduction idea. However, I have also some concerns. See below.\n\n- However, the relationships and connections  with MCMC methods with multiple candidates schemes such as the Ensemble MCMC algorithms in\n\nR. Neal, MCMC using ensembles of states for problems with fast and slow variables such as Gaussian process regression, arXiv:1101.0387, 2011.\n\nB. Calderhead, A general construction for parallelizing Metropolis-Hastings algorithms, Proceedings of the National Academy of Sciences of the United States of America (PNAS) 111 (49) (2014) 17408–17413.\n\nE. Bernton, S. Yang, Y. Chen, N. Shephard, J. S. Liu, Locally weighted Markov Chain Monte Carlo, arXiv:1506.08852 (2015) 1–14.\n\nshould be discussed. An interesting summary and review of these techniques is given in Section 4.4 of\n\nL. Martino, \"A Review of Multiple Try MCMC algorithms for Signal Processing\", Digital Signal Processing, Volume 75, Pages: 134-152, 2018.\n\nThese techniques are very similar, in my opinion, to the method you are describing, hence this is an important discussion for your work. ", "limitations": "The true main limitation of the proposed technique is mainly in its \"degree of novelty\", in the sense that similar ideas has been already proposed in the literature.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The idea is interesting, in my opinion. The main weakness is that the paper is difficult to read in some part.\nMoreover, some relationships and connections  with other methods in the literature should be discussed.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "0rtg_rI1XL8", "reviewer": "Reviewer_hWyK", "summary": "The iterated sampling importance resampling (i-SIR) is an iterative IS estimator that at each iteration a pool of candidate particles consists of one resample particle from the previous iteration and particles generated from an importance function. The paper suggests to average estimators over k-iterations instead of taking an estimator at the last iteration to reduce the bias of estimator and make better use of the available computational resources. Then theoretical properties were studied and simulation studies are given in comparison to a naïve self-normalized IS. ", "questions": "Please see Strengths and Weakness section. ", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Most of literature tend to focus on an importance function to make a better estimator. In that sense the study on i-SNR is interesting. Without too much difficulty, it is easy to see that averaging independent multiple IS estimates will reduce the bias compared to an estimate from a single iteration. Although the i-SNR is slight different to independent ISs, the novelty in methodology seem to be not big.\n\nThe evidence supporting the efficient computation does not look sufficient and I feel the method is needed to be fully investigated both theoretically and numerically in general. \n\na) The expectation error bound in Theorem 4 looks increasing with k (number of iterations). The burn-in k0 is likely to depend on various things like the deviation of an importance function to the target distribution and a number of samples per iteration. It sounds strange. \nb) How do you find the burn-in k0? \nc) In the experiment, k0=k-1. This mean that an estimate from the last iteration is taken and this against the claim that the new approach makes better use of computation by recycling all candidates.\nd) Given the computation budget, there will be some trade-off between a number of samples N and k (iterations). Some investigation will be good.\ne) Numerical comparison with other similar estimator (iterative IS estimator) will make the comparison more fair and useful. For example, Population Monte Carlo method. \nCappe, O., Guillin, A., Marin, J. M> and Robert, C. P. (2004) Population Monte Carlo, Journal of Computational and Graphical Statistics. 13(4) 907-929. \nf) For simulation study with logistic regressions, what are the computing  budget M and k? \n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "-5y87WueO2I", "reviewer": "Reviewer_1FgZ", "summary": "The paper proposes an MCMC-based extension of self-normalized importance sampling which can be seen as an iterated SIR algorithm or as a single-time-step analogue of particle MCMC. The interest in the current setting is to use a \"waste recycling\" variant of the iSIR algorithm in the SNIS context in order to provide a variance reduction.\n\nA thorough theoretical analysis is presented which it is claimed support the idea that this approach may lead to \"drastic bias reduction without impairing the variance\".", "questions": "1. I've been unable to reconcile the claim in the abstract that the proposed method reduces bias without increasing variance with the numerical results shown in Figure 2. MSE = bias^2 + variance and the proposed method seemingly increases the MSE relative to the basic SNIS method which would be consistent with it increasing the variance by somewhat more than the reduction in (squared) bias. Is that the case? If so the abstract is a little misleading, if not some explanation seems necessary.\n\n2. Does the reduction in bias lead to meaningful improvements in practical problems that the authors have seen?\n\n3. Is the work of Frenkel or Andrieu et al. on \"waste recycling\" relevant prior art from a methodological perspective or is there a reason that it is not?", "limitations": "The authors indicated that their work is of a theoretical/methodological nature and hence did not consider societal impact. I think that is reasonable.\n\n", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I like the attempt to improve on a basic algorithm using a simple \"plug-in\" strategy which should give the proposed method wide applicability. The main strengths of the paper are probably casting this problem in a framework which should allow practitioners to readily adapt existing SNIS implementations to make use of the proposed approach and the rigorous theoretical treatment of the method which provides some confidence in the performance of the approach.\n\nIn terms of weaknesses, there seem to me to be two:\n\n1. The claimed novelty seems to me to be overly broad.\n2. It is not immediately clear that one obtains the \"drastic\" improvements that are reapeatedly claimed in a way which leads to any practical benefit.\n\nIn terms of novelty, I was surprised to see it suggested that the idea of recycling \"rejected\" samples in this setting was somehow an innovation as it's an idea I've seen discussed regularly at conferences. Indeed, looking at Section 4.6 of [Andrieu, Doucet and HOlenstein. Particle Markov chain monte Carlo methods. Journal of the Royal Statistical Society Series B, 72(3):269--342 2010] or [Frenkel, D. (2006) Waste-recycling Monte Carlo. Lect. Notes Phys., 703, 127–138.] demonstrate that this is something which has been reasonably well known and in the literature for some time -- and with some formal justification.\n\nIn terms of improvement, there are two issues which the manuscript doesn't presently do justice to in my mind. These are:\n1. Is there really a reduction in variance at no cost; seemingly, the variance increases by more than the squared bias falls in all of the empirical results and the theoretical results seem to provide a bound on the amount by which the MSE can increase rather than establishing as claimed in the abstract that there is no increase.\n2. Does the reduction in bias make meaningful practical differences? The last numerical example seems to come closest to showing that it leads to an improvement in a widely used figure of merit but it stops short of showing improved, say, predictive performance. Although it might seem obvious that reducing the bias would improve performance it seems to me not to be so largely because bias in SNIS vanishes at the same rate of variance and hence typically makes negligible contribution to MSE for even modest numbers of samples and the MSE estimates shown for the proposed algorithm seem marginally worse than those for SNIS.\nThese are both important questions in assessing how relevant the work is to the NeurIPS community.\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept