Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This work analysis a well-known multiple-proposal MCMC kernel known as i-SIR. The main contributions are 

1. Theorem 3, which bounds the rate at which the bias/error decays with the number of iterations or number of particles.
2. 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.
strengths_and_weaknesses: Strengths:

1. 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).

Weaknesses:

1. 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.

2. 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.

3. 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):

* Tjelmeland, H. (2004). Using all Metropolis–Hastings proposals to estimate mean values (No. NTNU-S-2004-4).

* 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.

* Schwedes, T., & Calderhead, B. (2021, March). Rao-blackwellised parallel MCMC. In International Conference on Artificial Intelligence and Statistics (pp. 3448-3456). PMLR.

* Schwedes, T. (2019). Parallel Markov chain quasi-Monte Carlo methods. PhD thesis.




Typos et al:

- define $\mathbb{N}^*$
- $n$ -> $N$ in Theorem 4
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
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The authors describe and analyze an iterated importance sampling resampling scheme  and a possible bias-reduction technique.
strengths_and_weaknesses: The idea is interesting, in my opinion. The main weakness is that the paper is difficult to read in some part.
Moreover, some relationships and connections  with other methods in the literature should be discussed.
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.

- However, the relationships and connections  with MCMC methods with multiple candidates schemes such as the Ensemble MCMC algorithms in

R. Neal, MCMC using ensembles of states for problems with fast and slow variables such as Gaussian process regression, arXiv:1101.0387, 2011.

B. 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.

E. Bernton, S. Yang, Y. Chen, N. Shephard, J. S. Liu, Locally weighted Markov Chain Monte Carlo, arXiv:1506.08852 (2015) 1–14.

should be discussed. An interesting summary and review of these techniques is given in Section 4.4 of

L. Martino, "A Review of Multiple Try MCMC algorithms for Signal Processing", Digital Signal Processing, Volume 75, Pages: 134-152, 2018.

These 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.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: 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.

A 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".
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.

In terms of weaknesses, there seem to me to be two:

1. The claimed novelty seems to me to be overly broad.
2. It is not immediately clear that one obtains the "drastic" improvements that are reapeatedly claimed in a way which leads to any practical benefit.

In 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.

In terms of improvement, there are two issues which the manuscript doesn't presently do justice to in my mind. These are:
1. 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.
2. 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.
These are both important questions in assessing how relevant the work is to the NeurIPS community.

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.

2. Does the reduction in bias lead to meaningful improvements in practical problems that the authors have seen?

3. 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.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: 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. 
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.

The 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. 

a) 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. 
b) How do you find the burn-in k0? 
c) 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.
d) Given the computation budget, there will be some trade-off between a number of samples N and k (iterations). Some investigation will be good.
e) Numerical comparison with other similar estimator (iterative IS estimator) will make the comparison more fair and useful. For example, Population Monte Carlo method. 
Cappe, O., Guillin, A., Marin, J. M> and Robert, C. P. (2004) Population Monte Carlo, Journal of Computational and Graphical Statistics. 13(4) 907-929. 
f) For simulation study with logistic regressions, what are the computing  budget M and k? 

questions: Please see Strengths and Weakness section. 
limitations: yes
review_title: null

Meta-review: metareview: Importance sampling requires the knowledge of the normalization constant of the distribution to be sampled from. SNIS (Self-Normalized Importance Sampling) does not, but is biased. The authors study methods to reduce the bias in SNIS: BR-SNIS. They prove error bounds for this method (Theorems 3 and 4).

The reviewers agreed that BR-SNIS does a nice job in practice, and that the theoretical analysis is novel and sound [especially Reviewers 9JEd, 1FgZ].

However, they also all pointed out that the paper is overstating the novelty of BR-SNIS. Some identified BR-SNIS to the exising i-SIR/multiple proposal MCMC [9JEc]. Other reviewers wrote that they are not exactly the same but that BR-SNIS is strongly based on i-SIR and that this is not emphasized enough by the authors [nbwq, 1FgZ]. They all required that the author to make it clear that i-SIR is an existing method, that BR-SNIS is strongly based on it, to discuss the connection to multiple proposal MCMC thoroughly and to add many references. Overall, "the novelty in methodology seem to be not big" [hWyK], so the authors should make it clear that their main contribution is the analysis of the method (Theorems 3 and 4). One of them also required to clarify the novelty of the Rao-Blackwellised estimator [9JEd]. Finally, while they agree that Theorems 1 and 2 are necessary to understand BR-SNIS, it should also be stressed that these results are "classical results", on the contrary to Theorems 3 and 4 [9JEd].

The authors acknowledged this, and promised to fix the paper accordingly. During the discussion, the reviewers agreed that the theoretical analysis in the paper is interesting enough to justify its acceptation. I will therefore recommend to accept the paper. I will ask the authors to carefully include in the paper all the discussion on i-SIR and multiple proposal MCMC and on the novelty of BR-SNIS in general (and of course Rao-Blackwellised estimator // Theorems 1 and 2). There was also some potential computational problem pointed out by [hWyK], who was finally addressed by the authors reply: please implement the corresponding corrections in the paper if necessary.
confidence: Less certain
Decision: Accept