Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper introduces Quasi Rejection Sampling to balance sampling accuracy and efficiency for energy-based models. Specifically, the authors introduce a hyperparameter beta to the standard rejection sampling to truncate the target distribution. By doing so, a bound on the importance ratio is not needed but the target distribution is no longer preserved.

main_review: The proposed method is very simple and easy to use in practice. However I have the below concerns.

1.	The main concern I have is how efficient the proposed method is given a usable sampling quality. From the results in the experiment section, to reach a reasonable TVD (e.g. < 0.001), the acceptance rate has to be very low which means QRS needs many steps to produce one sample. Besides, the hyperparameter beta and the proposal distribution need to be carefully chosen. 

2.	Given the above concern, I wonder how the proposed method compared to MCMC methods. Given a similar number of steps, the MCMC method might also be able to mix and produce usable samples. This comparison is important and it is currently missing. For example, the authors could consider comparing with [Oops I Took A Gradient: Scalable Sampling for Discrete Distributions, ICML 2021] where they also tested on EBM, and the independent Metropolis-Hastings as mentioned in the paper. 

3.	Algorithm 2 with automatically tuned beta is interesting since beta is an important hyperparameter and may require a lot of tuning to make QRS work. It will be better to show some experimental results of Algorithm 2. Right now it is not clear to me what the distribution it samples from.  Since beta changes along with the training, the target distribution also changes. 


summary_of_the_review: In summary I think the methodology is simple and practical. It could have potential usage on many applications. But the empirical demonstration is not convincing, especially missing the comparison with MCMC methods.
review_title: null

final_score: rating: 1: strong reject
review_content: summary_of_the_paper: The authors propose a method called Quasi Rejection Sampling (`QRS`) which is a relaxation of Rejetion Sampling (`RS`).
The only difference between `RS` and `QRS` is that the authors use a paramater $\beta$ instead of the upper bound $B = \sup \frac{p}{q}$ used in traditional Rejection sampling, where $q$ is the proposal and $p$ is the target distribution.
main_review: ## Weaknesses

1 - The authors propose a relaxation of rejection sampling which is using an arbitrary parameter $\beta$ instead of the true upper bound of the ratio $\frac{p}{q}$ when the latter cannot be computed. The reviewer fails to understand why the authors did not directly use Importance sampling in the first place.

2- In algorithm 1, the reviewer fails to see a difference between QRS and RS, and will change their opinion if the authors can point out a value of `u` for which QRS and RS will behave differently.

3 - Uninteresting Section 2.2:
    - Equation 1 needs a parenthesis to avoid confusion
    - Equation 3 is pretty much obvious from the definition of TVD (Lemma 2.19 Aldous and Fill https://www.stat.berkeley.edu/users/aldous/RWG/book.html)
    - Equation 4 is obvious since using the apropriate upper bound gives you rejection sampling which is a perfect sampling algorithm.

4 - In the abstract the authors require the proposal distribution to upper bound the target everywhere which is not true as the authors themselves clarify in the text.

5 - While Equation 9 and 10 are great in that they can be used to compute TVD and KL between the true and QRS distributions, there are multiple issues which are neither stated as assumptions nor addressed appropriately, namely:
    - They're not unbiased estimators since $Z$ is not known and needs to be estimated, this point is not explicitly stated.
    - It is assumed that the normalizing constant of $q$ is known, which is not always the case.
    - They rely on importance sampling, which begs question 1.

summary_of_the_review: The reviewer strongly recommends rejection since the paper lacks both significance and novelty.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper focuses on the challenge of sampling from unnormalized probability distributions (or Energy-Based Models) -- typically those found in the context of NLP when dealing with the task of controlled generation (post-hoc conditioning of a pre-trained unconditional model). Previous approaches for this have been based on MCMC or have sought to finetune the unconditional model to more closely match the desired conditional model (usually through policy-gradient methods). 

This work proposes a different method of sampling from such distributions, motivated by the accessibility of powerful generative models. Previous approaches have shown how to train a tractable generative model (which can be sampled from exactly) to approximate some known, unnormalized distribution. This work proposes to use these models as a proposal distribution for a rejection-sampling-like algorithm which will arrive at samples that are distributed more closely to the desired distribution. 

Exact rejection sampling requires the user to know some upper bound M on the likelihood ratio between the desired distribution p(x) and the chosen proposal distribution q(x) [M > p(x)/q(x) \forall x]. In practice, this M may not be known, or may not exist. The proposed method, Quasi-Rejection Sampling (QRS), alleviates the need for this bound and replaces it with a tunable parameter \beta. This broadens the settings where we can apply this method compared to standard rejection sampling. 

The authors demonstrate that as \beta \leftarrow \infty then TVD/KL between the output samples and target distribution goes to zero. This comes at the cost of increased rejection-rate which decreases the efficiency of the sampler. To make this approach more usable, the authors also provide importance sampling estimators for the TVD/KL which, along with the acceptance rate, can be used to tune \beta and provide estimates of sample quality. 

The authors demonstrate the effectiveness of their approach in a number of controlled text generation settings and demonstrate that it can lead to improved samples over prior works (at the cost of additional computation).

main_review: Sampling from unnormalized distributions is notoriously difficult. Traditional rejection sampling cannot be applied in many settings (including the settings addressed in this work) and because of this, MCMC techniques are often favored. Unfortunately, diagnostics for tuning MCMC methods often do not exist and therefore they are often tuned in qualitative ways. QRS gives more to the user in this way. If the user has a fixed computation target, the user can get some idea of the quality of their samples within some budget. The same cannot be said for MCMC methods. This is a desirable property in a method intended to be used by people who may not be MCMC whizzes.

As well, the method is very simple and near trivial to implement which will greatly add to the impact of this method. Given a computation budget or a divergence target, the single parameter appears simple to tune and could even be done automatically (have you thought of this?).

Another nice property of the approach is that it can be easily applied on top of any new advances in learning the proposal distributions. If development is made in this area, QRS could easily be dropped-in on top to further improve results. 

Weaknesses:

The main weakness in this work is in the empirical evaluation. The method is mainly compared with sampling only from the original proposal distribution. In this comparison, the method (clearly) appears favorable. As well, there is a comparison with Independent Metropolis-Hastings (IMH) in the appendix where there appears to be some benefit but it is not as drastic. 

I believe a comparison with localized MCMC methods should also be provided. There has been recent development in this space and it would be useful to understand how well this approach works in the context of these recent developments. The same evaluations could be used as in Figure (b) in the appendix. You could seed the chains with your proposal distribution and then apply some MCMC algorithm for a certain number of steps. You could compare with any number of MCMC samplers such as random-walk metropolis, Gibbs sampling, locally-balanced proposals, gibbs-with-gradients, discontinuous HMC, discontinuous SGLD, etc (I am not asking you to compare with all of these approaches, just one or two maybe).

The x% acceptance rate QRS requires 1/x samples per accept. Since each sample requires L model evaluations (where L is sequence length) this requires L/x model evaluations in total. Metropolis requires 2 evals, gibbs-with-gradients requires 4 (2 evals + 2 gradients), so a runtime-fair comparison could easily be obtained with many of these local MCMC approaches. 

I want to reiterate that I enjoyed this work and would like to see it accepted, but I feel it is lacking context in its current presentation. The authors claim a major upside of QRS is due to a number of deficiencies in these methods, so I think a comparison with the most recent methods in this area is warranted. I am happy to facilitate a discussion about this and if you feel this request is unreasonable, I am happy to discuss. 

Besides this, I am also somewhat concerned with the importance sampling estimators of TVD/KL/accept-rate. Importance sampling maybe unbiased but it can have high variance. Could you also provide some information on the variance of the estimates used in your experiments? 

---------Post discussion period------------
I thank the authors for responding to my comments. I appreciate the new experiments on localized MCMC. It appears that the proposed approach gives improved performance for a similar compute budget. While I would love to have seen a GWG comparison, I understand the overhead that it would require and am fine that it was not included. Unlike the other reviewers, I do not see the "lack of novelty" as an issue of this work. It should be favored when simpler ideas, applied in novel ways or to new problems, lead to good results on important problems. Based on the authors response, I will raise my score slightly in favor of acceptance. 

summary_of_the_review: The proposed approach, QRS, is a novel extension of rejection-sampling which can be applied in settings where standard rejection-sampling cannot. The approach has a number of benefits over alternative sampling approaches such as the ability to estimate useful metrics for tuning. The approach can bootstrap on top of further development for learning proposal distributions to target unnormalized distributions. While the paper is well written and the method appears powerful and novel, the paper has issues with its evaluation. QRS is not compared with sequential sampling approaches. This leaves out much context and ignores much recent work on discrete sampling. The paper would be greatly improved with a comparison to some of these approaches.
review_title: null

Meta-review: This paper proposes a new approximate sampling approach called Quasi Rejection Sampling (QRS) to exploit global proposal distributions without requiring to know a bound on the associated importance ratio, and providing a trade-off between the approximation quality of the
sampler and its efficiency. QRS is demonstrated on EBM-based text generation tasks. The reviews acknowledge the simplicity of the approach which when combined with advances in learning proposal distributions opens up many potential applications. At the same time, the reviews indicate that more work could be done to make the empirical demonstrations more compelling, with a more thorough coverage of comparisons with MCMC and other alternatives. The authors are encouraged to revise their submission and clarify significance and novelty.
Decision: Reject