Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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). 

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

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

The algorithms are benchmarked on various targets (25 Gaussian mixture, Funnel) and applied to training a VAE. 

main_review: # Main contributions

* The paper proposes new family of importance samplers and MCMC schemes: NEO-IS and NEO-MCMC

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

* The paper focuses on a discrete-time integrator of a conformal Hamiltonian system for $T$

* 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 

* NEO-MCMC: massively parallel MCMC algorithm to sample from $\pi$ (independent samplers that are allowed to interact via a resampling mechanism)

# Originality

As far as I can tell the paper proposes an innovative class of importance sampling and MCMC schemes

# Quality

The paper is technically sound and the experiments are instructive. 

# Clarity

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

# Comments

* Figure 1: It is unclear what's shown here. Please provide more details (axis labels etc., what are the contours?). 

* Algorithm 1: In step 2, the index $j$ should probably run from $0$ to $K$ for the weights $w_j$

* In a practical implementation, you have to restrict the number of samples per orbit $K$. How do you choose $K$? 

* Can the idea of sampling on orbits be related to elliptical slice sampling? Or Gibbs sampling? 

* It seems that NEO-MCMC produces many candidate samples (those on one orbit) that are never picked. This seems to be quite wasteful.


limitations_and_societal_impact: -
review_title: null

final_score: rating: 9: Top 15% of accepted NeurIPS papers, strong accept
review_content: 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.
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.

The 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.
limitations_and_societal_impact: Yes. The authors adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.

main_review: Strengths:
1. 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.
2. 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.
3. 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.

Weaknesses:
1.  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.
2. 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.
3. 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.

limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: Based on Non-Equilibrium IS (NEIS), the authors propose the new importance sampler NEO-IS.
The 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).
They empirically show that NEO-IS (and its MCMC variant) can be better that other recent methods for tasks of 
(1) finding the marginal likelihood, (2) Sampling from posterior distribution, (3) Inpaiting.

main_review: originality:
Though NEO-IS is based on NEIS, NEO-IS provides a new type of discretization which does not introduce any bias.
The MCMC-extension appears to be mostly building on iterated sampling importance resampling method (SIR), which appears not be the main contribution.

quality:
They theoretical and empirically support their claims. 
However, the comparison with the original NEIS seems to insufficient.
I do not understand why the comparison to NEIS is in the supplement material, and not in the main paper.

clarity:
The paper is extremely difficult to read.
One reason is that the author introduce many new (or relatively new) concepts in one paper.
I think putting the whole Section 3 (MCMC sampling) into the appendix, and instead explaining Section 2 in more detail might help.

significance:
The work appears to advance the state of the art for estimating normalization constants (marginal likelihood).
However, I am not sure about the significance of this work for posterior sampling, since a comparison to more recent works 
like for example [1], for which open source implementations are available [2], is missing.

[1] Deng, Wei, Guang Lin, and Faming Liang. "A Contour Stochastic Gradient Langevin Dynamics Algorithm for Simulations of Multi-modal Distributions." NeurIPS 2020.
[2] https://github.com/WayneDW/Contour-Stochastic-Gradient-Langevin-Dynamics

Questions:
In line 105, it says that they the use the Cauchy-Schwarz inequality. 
I think it's an application of Jensen's Inequality. Do I misunderstand here something?

---
Thank you for the clarification, and your efforts to compare to one more recent MCMC sampling method (like [1]). 
It would be good to get a more complete picture which includes a discussion about when your method might not work well.

limitations_and_societal_impact: The issue of total computational costs, and runtime is not addressed in the main paper.
(Is it addressed somewhere in the supplement material?)
review_title: null

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)