Sampling from Discrete Energy-Based Models with Quality/Efficiency Trade-offs
Authors: Bryan Eikema
Germán Kruszewski
Hady Elsahar
Marc Dymetman
Venue: ICLR 2022 Submitted (2022)
Keywords: Monte Carlo
sampling
rejection sampling
Energy-Based Models
EBMs
controlled text generation
language models

Abstract: Energy-Based Models (EBMs) allow for extremely flexible specifications of probability distributions. However, they do not provide a mechanism for obtaining exact samples from these distributions. Monte Carlo techniques can aid us in obtaining samples if some proposal distribution that we can easily sample from is available. For instance, rejection sampling can provide exact samples but is often difficult or impossible to apply due to the need to find a proposal distribution that upper-bounds the target distribution everywhere. Approximate Markov chain Monte Carlo sampling techniques like Metropolis-Hastings are usually easier to design, exploiting a local proposal distribution that performs local edits on an evolving sample.  However, these techniques can be inefficient due to the local nature of the proposal distribution and do not provide an estimate of the quality of their samples. In this work, we propose a new approximate sampling technique, Quasi Rejection Sampling (QRS), that allows for a trade-off between sampling efficiency and sampling quality, while providing explicit convergence bounds and diagnostics. QRS capitalizes on the availability of high-quality global proposal distributions obtained from deep learning models.  We demonstrate the effectiveness of QRS sampling for discrete EBMs over text for the tasks of controlled text generation with distributional constraints and paraphrase generation.  We show that we can sample from such EBMs with arbitrary precision at the cost of sampling efficiency.

Under review as a conference paper at ICLR 2022
SAMPLING FROM DISCRETE ENERGY-BASED MODELS WITH QUALITY/EFIIIENCY TRADE-OFFS
Anonymous authors Paper under double-blind review
ABSTRACT
Energy-Based Models (EBMs) allow for extremely flexible specifications of proba- bility distributions. However, they do not provide a mechanism for obtaining exact samples from these distributions. Monte Carlo techniques can aid us in obtaining samples if some proposal distribution that we can easily sample from is available. For instance, rejection sampling can provide exact samples but is often difficult or impossible to apply due to the need to find a proposal distribution that upper- bounds the target distribution everywhere. Approximate Markov chain Monte Carlo sampling techniques like Metropolis-Hastinng are usually easier to design, exploiting a local proposal distribution that performs local edits on an evolving sample. However, these techniques can be inefficient due to the local nature of the proposal distribution and do not provide an estimate of the quality of their samples. In this work, we propose a new approximate sampling technique, Quasi Rejection Sampling (QRS), that allows for trade-off between sampling efficiency and sampling quality, while providing explicit convergence bounds and diagnostics. QRS capitalizes on the availability of high-quality global proposal distributions obtained from deep learning models. We demonstrate the effectiveness of QRS sampling for discrete EBMs over text for the tasks of controlled text generation with distributional constraints and paraphrase generation. We show that sample from such EBMs with arbitrary precision at the cost of sampling efficiency.
INTRODUCTION
Obtaining samples from probability distribution is use- ful in many natural language processing applications, e.g. generating diverse outputs from language model (Holtz. man et al., 2020), producing debiased sentences from pretrained model (Khalifa et al. 202T), or proposing a set of choices to some decision rule (Eikema & Aziz, 2021). In many cases, when the probability distribution is con- veniently factorized and normalized (e.g., autoregressive sequence models), this can be done easily. However, this simplicity in sampling often comes the cost of expres- sivity. Energy-based models (EBMs) (LeCun et al. (2006) enjoy greater representational freedom by mapping elements into arbitrary unnormalized non- negative scores. In particular, discrete EBMs have been leveraged by prior studies to tackle number of different tasks, including data-efficient learning (Parshakova et al., (019a),, language modelling (Deng et al., 2020), machine translation (Naskar et | (020). natural language under- standing (He et al. (202)), and controlled text generation (Khalifa al. 2021). However, not. immediately clear how to obtain samples from such EBMs.
B9
rejece
Scceys
Figure 1: QRS, 3 is a scalar parameter that controls the qualitylefficiency trade-off. The blue shaded area depicts the truncated distri- bution that QRS samples from.
In this work we investigate the usage of Monte Carlo (MC) sampling techniques (Robert Casella 2004) to approximate the target distribution. MC techniques allow to estimate expectations and to sample from unnormalized distributions, of which discrete EBMs are a subclass, as long as a proposal distribution from which it is possible to obtain samples is available. One can distinguish between two kinds of proposal distributions: local ones, that is, conditional distributions approximating the normalized target distribution around given point (for instance, by focusing on set of local

---

Under review as a conference paper at ICLR 2022
edits), and global unconditional ones that approximate the target distribution over the full sampling space. Because local proposals are generally easier to design, Markov chain Monte Carlo (MCMC)
techniques that exploit these, such as Settropolis-aattiie are quite popular. The convergence theorem for Metropolii-HHatiings Markov chains (see Fig. 7 in the Appendix) guarantees that i) the expectation estimate converges to the true value over a single chain of increasing length, and ii) the distribution obtained by repeatedly running a chain of length n and outputting the n-th element converges to the target distribution for increasing values of n. These important theoretical results, unfortunately, do not come with concrete convergence diagnostics, which presents serious risks in practice, such as believing that the chain has explored the most relevant parts of the space when it has not (Cowles & Carlin, 1996; Roy 2020).
(Metropolis et al. [9533] Hastings 1970).
Fortunately, there are cases where a reasonable global proposal is available. While such cases were the exception in the traditional MC literature, the situation is changing with the advent of powerful neural network training techniques allowing for flexible approximations to a wide class of distributions. We will later show three different instances of global proposal distributions obtained in this way. When eetropolis--Hasting (IMH)
global proposal is available, Sattroooli--Hastinn reduces to independent (Robert& & Casella 2004 $7.4), where proposed moves do not depend the current point. While this brings some simplifications in the analysis of the chain, by and large, practical convergence diagnostics remain difficult. If the goal is compute expectations, the much simpler importance sampling algorithm, which often leads to concrete convergence diagnostics (Owen 2013). is more appropriate and we will heavily use in the sequel at points where we need to estimate expectations. If the goal is to produce samples, IMH does not produce i.i.d samples and can suffer from high auto-correlation between samples. Appendix E discusses IMH in detail and provides a theoretical and experimental comparison with our proposed algorithm, QRS, which we introduce next.
With global proposal, if we can find some constant with which we can bound the importance ratio between the target and proposal distributions, we can use rejection sampling to obtain exact samples (Von Neumann 1951 Martino et al., 2018). However, it is often hard or impossible to find such a bound. Moreover, if the bound is too large, then the method can be extremely inefficient (Andricu et al. (200)). In this paper we introduce quasi rejection sampling (QRS), extending rejection sampling by providing the possibility to approximately sample from the target distribution without requiring to know a bound on the importance ratio or even that such a bound exists at all. QRS produces i.i.d samples and allows controlling the trade-off between the approximation quality of the sampler and its efficiency. Furthermore, QRS does provide explicit convergence diagnostics, while also supplying precise estimates of the sampling quality (i.e., the distance of the sampling distribution to the target distribution) and efficiency (i.e., the sampler's acceptance rate).
We demonstrate the effectiveness of QRS on controlled text generation following the setting of Khalifa et al.] (2021) and paraphrase generation inspired by the work of Miao et al. (2019). We sample from EBMs that i) restrict a GPT-2 small (Radford et al. 2019) model to generate sequences containing the term "Wikileaks". iij debias GPT-2 fine-tuned on biographies to produce 50% female biographies while exclusively generating biographies about scientists, and iii) generate paraphrases that maintain the fluency of GPT-2 while being similar to the input sequence under sentence embedding model. In order to apply QRS we explore a variety of ways to construct proposal distributions by either i) prompting a pre-trained language model, ii) training an auto-regressive sequence model to approximate the EBM (Khalifa et al., 202I), or iii) making use of off-the-shelf machine translation models to specify conditional proposal distributions. The results show that we are able to approximate the target distributions to arbitrary precision at the cost of sampling efficiency. The off between these two confficting objectives can be computed explicitly within QRS, allowing user-defined choices depending on the intended application. In short, our contributions are:
We introduce QRS, a variant of rejection sampling that does not require global upper-hounds importance ratios, and uses a scalable parameter / to trade-off sampling quality with efficiency.
To support this trade-off, we provide explicit estimates and bounds on discrepancy measures (total variation distance and Kl.-divergence) between the distribution of QRS samples and the EBM.
We show how QRS can exploit high quality global proposals readily available today thanks to deep learning. We present experimental results based on three sorts of such proposals. originating from i) the use of prompts in pre-trained language models, ii) a fine-tuning technique for approximating EBMs, and ùii) the use of round-trip translation in the context of a paraphrasing EBM.
2

---

Under review as a conference paper at ICLR 2022
2 FORMAL APPROACH
Our general problem is the following. We consider discrete (i.e. countable) sample space X We are given a nonnegative real function - aka EBM - P(z) over X, such that the partition function Z ΣzEx P(x) is strictly positive and finite. We can then associate with P normalized probability distribution p(x:) = z Z-1P(at) P(x). Our goal to define "sampler" w, that is generator of elements from X, such that w produces sample with a probability wxxz) as close possible to our target p(x), in terms of discrepancy measures such as KL-divergence DKL (p, w) and total variation distance TVD(p, w). to be detailed later. To help us solve that problem, we assume that we have at our disposal a global proposal distribution g(z) such that i) we can effectively compute ((x) (i.e. score 2) for any X, ii) can effectively generate samples from q. and iii) the support of q includes the support of p. i.e. p(x) > 0 + ((x) > 0 (but see footnote for a generalization).
Additionally, and crucially for the tractability of the techniques, the proposal q should be chosen in such a way that it provides a "reasonable" starting point towards our target in terms of TVD or DKL. One important methodological contribution of our approach will be to stress the role of deep learning in producing good proposals in way that is not typical of classical MCMC approaches.
2.1 QUASI REJECTION SAMPLING (QRS)
Our proposed approach, QRS, is based on Algorithm
Algorithm QRS [rejection sampling (RS))
Require: p.q.8 B
DO < 3 < 00
I: while True do
2: x~
3: Tx f 2.miii(1, ((s))((((
[vs. 1x P(s)/3(((())
> Acceptance prob. > Uo.11 unif. dist. over [0, 1]
4: u~ [0.1]
5:
if S Tx then
6: output
In addition to P and q. QRS requires the input of finite positive number 3. QRS differs from standard rejection sampling in two aspects: i) contrary to rejection sampling it does not require 3 to be "global" upper-bound, that is, to have P(x)/ qq(x) ) S B for all x's in X, and (2), shown on line 3, the "acceptance probability" Tx is generalization of the one used with rejection sampling, for cases where P(z)/3q(a) 1. In ease / happens be a global upper-bound, QRS simplifies to standard rejection sampling. See Fig. for an illustration of QRS.
Both rejection sampling and QRS produce an i.i.d sequence of x's (line 6). where each is generated with probability that we will denote as (z))). As is well-known (Robert & Casella 2004). in the case of rejection sampling, we actually have p/ = p. other words, rejection sampling is a perfect sampler for This is of course major advantage, however it comes with serious theoretical and practical limits: i) rejection sampling requires the existence of finite upper-bound 8, ii) this 3 needs to be known beforchand. These conditions often do not hold for the proposals q that we will consider, typically autoregressive models whose statistics are not known in closed form. Even if such a bound could be found, the resulting sampler could be extremely inefficient:
will see (Equation (2). the "acceptance rate" of rejection sampling is proportional to 1/3, which can be extremely small.
By relaxing the requirement that 3 be global upper-bound, QRS loses the identity between Ps and p. However, QRS becomes much more generally applicable, and crucially, allows an explicit trade-off between the sampling efficiency of pa and its sampling quality, as measured by distributional discrepancy between pa and p Let's now look this in more detail.
In our experiments X will mostly be of finite sequences over linguistic tokens, hut here we consider an arbitrary discrete space. We note that for off-the-shelf usage, provide in Appendix D specific variant of the algorithm that automatically estimates the best possible given some efficiency constraints.
3

---

Under review as a conference paper at ICLR 2022
2.2 FORMAL PROPERTIES OF QRS
We will keep the notation from above, and will also be using two standard discrepancy measures between distributions pl, P2 over X: the KL-divergence (p), = Ex-p, log(p1 (x) /pa (2(x)
and the total variation distance TVD pP)) = 1/2 Σg (pr P2(1) (see e.g. Chafai 2010
Both measures are null iff p1 = P2- with TVD (resp. KL) ranging between 0 and 1 (resp. and (C).
The following facts are proven in Appendix A
Define (2) = min P(z), [g(x)), and let Ze = Ens L Pa(x) be the partition function of Pz(z). Then Pa is the normalized distribution associated with Pg. with:
(=(2)= 1/2 Pz(x).
By definition, the acceptance rate , of the QRS sampler ps is the proportion of samples from q- in line 2 of the algorithm, that produce an output on line 6. AR, a decreasing function of B3 and:
A Exng min(1, P(z))B(()) Zg/3.
Let = = for E P(a)/a(x) < 3). Then:
TVD(p.Ps)
p(AR);
(3)
lim (1 p(As) = 0.
(4)
8+000
other words, 1-p(A)) (which can understood as the probability of violating P(=)/g(a) s ()
bounds the TVD between p3 and p. and P3 converges to p for B 00
2.3 PRACTICAL IMPLICATIONS: ESTIMATES
The previous facts have important practical implications, in particular concerning the production of explicit estimates for different quantities of interest. The general recipe for producing such estimates will be to use importance sampling (Owen) 2013), using once again 9 as the proposal distribution. base estimates on sample (.i,..., EN of i.i.d draws from qi if a real-valued function
on X, we then rewrite ΣxEx f(x)= = E Exn ((m)
[(z)
N
Σ LiEnLNi a(a.)
[xx) In particular, we have:
2 N-1 Σ
P(æ:)
(5)
=(As)=N=
Σ
Zq(x:) [ E As),
P(æ:)
(7)
((x;))
(E[L.N]
[E[I.N]
Px(
Σ Pa(x.)
Zg ~ N
(6)
Ex-ny ~ N
f(zi),
(8)
((x:)
Zzg(x:))
(E(L.N]
iE[1,N]
where we note that explicit values for Pa(x) and 1/x E As] are available, namely: Pa(x) min(P(()), min(P((),BB(xx) and [[z E As] = iff P(x) S Bq(x).
We can use these estimates to obtain estimates of the discrepancies between p and Ps, again by importance sampling with g. We have (see Appendix B):
P(x.) Po(z.)
TVD(P. 1/2
Σ
Zg(z.)
Zaq(x:)
RE[I.N]
DRI(D.PE) = log
ZB
+ N-1 Σ
P(I:)
log P(x:)
(10)
7.
Zq(x;)
Pz(1:)
x
3 EXPERIMENTS
3.1 TWo POISSONS
To demonstrate how we can use the QRS algorithm to obtain samples from a distribution p(#) using proposal distribution g(x) we start with toy setting using two Poissons. The goal is to sample
"In all this discussion, we have kept the standard assumption about supports of and g, namely that Supp(p) C Suppíg). Interestingly, when this assumption is not true, all the previous properties of QRS still hold, apart from (4). which generalizes limg-ro0 p(A))) p(Supp(1)) (see Eq. 18 in App. Ab.
4

---

Under review as a conference paper at ICLR 2022
apoorance E30
10
K.lpp
10"
1071
1-:0Au TVDis
CJUE
1071
23
Kup. 01
KLGP
accepCance
acceptance rate
Figure 2: Estimation of sampling quality (TVD(p, ps) and Dxr. Ps)), efficiency (acceptance rate), and the trade-off between them for a QRS sampler when using proposal Poisson 10) to approximate p = Poisson(A ( = 11) over five independent experiments with 10M samples.
from a target Poisson distribution p with rate A 11 using samples from a proposal Poisson distribution with rate Xg = 10. Rejection sampling is not possible in this setting as the ratio p(x)/g(x) = 1e_" 1111///d / 100100000 10"/2!) /z!) = e- 1.1" can take arbitrarily large values when increases, i.c. is unbounded. However, it still possible and practical to use the QRS sampler.
We perform five independent experiments in which we sample 10M elements from that we use to compute the quality of the approximation by estimating: TVD(p, P3) (Eq. 9). its upper bound 1 p(As) 3. and DKL (p. pa) (Eq. 10) measured in nats/sequence. In all cases, we use range of [3 values in the interval [0.5, 4). Furthermore, we compute the sampler's s efficiency by estimating the acceptance rate (AR) for each value of 3 following Equations 2 and To visualize the trade-off between quality and efficiency, we also plot one as a function of the other by computing the inverse of the AR curve and composing it with the TVD and KL ones.
We first display quality and efficiency results as a function of B (first three panels in Fig. 2 As shown, using higher values of 3 improves the TVD and KL, even though this comes at the cost of lower acceptance rate. The last two panels in Fig. 2 show the quality/efficiency trade-off in a more concise form, which is why will prefer this presentation in experiments below. As shown, the TVD reaches very low values (< 10-2) with moderate acceptance rate of 0.25.
3.2 GENERATION WITH DISTRIBUTIONAL CONTROL
Our following experiments focus on the generation with distributional control setting introduced by Khalifa et al. (2021). Given language model a(x), the goal of this task is to obtain model p(æ) that, on the one hand, constrains the moments of a set of n pre-defined features ((x) to match some desired values j (i.e., (z==)((x) = ji), while on the other hand minimizing DKL. (p, a). For example, one might want to debias language model trained on a corpus of biographies to produce biographies
only of scientists, 50% of which should be female. Then Φ1 (x) and (2(x) would be binary classifiers assessing whether a sentence speaks about scientist or female person respectively, and the desired moments would be set to j [1, 0.5].
The authors show that can be expressed as an unnormalized EBM P(x) = ((x)b((z) and describe two variations. On the one hand, they consider pointwise constraints, where p E {0, 1)". For instance, if there is single binary feature for which we would like that Vz: : Φ(x) = 1, then b takes the form b(x) = (xx). Otherwise, the case of distributional constraints in which já E IR., they show that there is vector À E IR" such that b(z) exp(X o(x) (z){ such that p(x) a(z)b(x) fulfills the requirements of moment matching and minimal KL distance from the original model. Finding this vector of À parameters is done through combination of self geff-normalized importance
sampling (Owen) 2013 Parshakova et al.) 2019a) and stochastic optimization.
3.2.1 PROPOSAL. DISTRIBUTIONS FOR A POINTWISE CONSTRAINT
We first experiment with constraining GPT-2 small (Radford et al. 2019 using one of the pointwise constraints (ji 1.0) proposed in Khalifa et al. 2021). ), namely, .
Jxr contains "Wikileaks").
In order to apply QRS we need to find a suitable proposal distribution. A possible candidate is
FFor a precise formulation covering all cases, Khalifa al. 2021
5

---

Under review as a conference paper at ICLR 2022
14-
DPG CPT3 small
prompt-
prompt
nume
08-
smole
simple
Wikileaks.
knowledge Iespaddy news
multiple
Wikileaks, Wikileaks, Wikileaks.
0.4
knowledge
Here what know about Wikileakss:
joopardy
This medium was founded by Julion Assange in 2006.
02-
news
Here are the latest developments on Wikileaks:
107
10
10
10
10
30
10"
30'
acceptance nate
Figure 3: GPT-2 generations containing the term "Wikileaks". We use GPT-2 small, GPT-2 small conditioned on various prompts and the fine-tuned model obtained through DPG (Khalifa et al. 2021) as proposal distributions q for the QRS algorithm. Points in the left-upper corner correspond to TVD(p. g) before QRS, while the curves show TVD(p, ps) as a function of the acceptance rate.
GPT-2 small itself. An advantage of this proposal is that we can use pure rejection sampling with an upper-bound B
obtain exact samples from the EBM. This is because we can upper bound the ratio P(=)/q(x) = a (z) (2)))(((/((())
= b(x) < 1. Furthermore, for b(xz) E {0, 1] this process reduces to "naively" filtering out all samples for which b(x) O. However, a serious disadvantage that the acceptance rate will be given by the natural frequency of the constraint (in this case, in the order of 10-4). Using QRS, we can employ proposal distributions leading to better efficiency at a small cost in quality of approximation to p. We explore two such options. First, we make use of the model proposed by Khalifa et al. (021), which consists of a fine-tuned auto-regressive model obtained from applying the distributional policy gradient (DPG) algorithm (Parshakova et al. 2019a) to approximate the target EBM. While this model is considerably better at satistying the desired constraints, it does not match the desired distribution perfectly. Second, we propose to condition o(x) on prompt with the aim to increase the constraint satisfaction rate in the resulting conditional distributions. In contrast to the previous approach, this solution does not require training a model, even though it does require to find the prompts themselves. We experiment with five such prompts, which we present in Fig. 3
The right panel of Fig. 3 shows the TVD as function of the acceptance rate for different samplers. For this and fo followng experiments, we chose range of 33 values that yield acceptance rates in range 10--10-5 5 (cf. [ Appendix). We first show the TVD(p, q) for each proposal q. at an acceptance rate of 1, before applying QRS. Then, we plot TVD(p, (p) as a function of acceptance rate, running the QRS sampler for each of the various proposal distributions. We compute importance sampling estimates of the TVD on 1M samples from each proposal distribution. As expected, using GPT-2 small comes with perfect TVD at the cost of low efficiency with an acceptance rate around 10-4, Using prompting, we can improve the constraint satisfaction of the resulting proposal distributions and trade-off quality for efficiency using QRS. Some prompts work notably better than others and we do not exclude the possibility of there existing prompts that perform even better than the ones we tested. We leave a more extensive exploration of prompting to create proposal distributions to future work. The uuto-regressive policy obtained from the DPG algorithm is the best proposal distribution we tested. Notably, it allows for obtaining very low TVD values at higher acceptance rate than would be obtained by naively filtering samples from the base language model.
3.2.2 DEBIASED SCIENTIST BIOGRAPHIES
We now turn to the task, also introduced by Khalifa et al. 1222 of generating biographies of scientists while debiasing the gender distribution to contain female scientists 50% of the time. For this we make of GPT-2 Biographies (a(x)). language model fine-tuned on Wikipedia biographies and follow the same the setup as the authors to define the binary classifiers identifying sequences talking about scientists or female figure and infer an EBM that matches the distributional constraints with minimal deviation from the original model. The frequency of a(x) generating scientist biographies is 1.8%, female biographies 7.5%. and female scientist biographies only 0.14%. As proposal distribution we use the DPG model that Khalifa et al. (202I) trained to approximate the EBM, which reaches a constraint satisfaction of 69.0% scientist, 27.3% female and 19.6% female scientist biographies.
htttts:///ugggt http://ugginggafaaeccm ing co/ co/mkha1 fa /gppt/t22bb ographies
Gender is estimated by the ratio of female to male pronoun counts, scientists are identified by the mention of at least of multiple words associated with the profession.

---

Under review as a conference paper at ICLR 2022
QRS samples from AR 10
(bor l'ebruary 11, 1965) social scientist, activist, poes, and author living Portugal.
Enrella Carrèrr Canadion writer, tronslator, and philosopher specializing the history of show business, She covered topics such the direction and psychology of television and the evolution of human...
Albert Fahn (born 1970) is an American scientist who focuses on algorichuns for generating biomechanical data, Methods to generate and construct biomechanical from...
Wyndham Radnor (bamn 1946) British historian and criminologist specialising in the subject of labour law. Ile has written extensively on....
2.0
1 pldy) TVD
20
Kuggi Ral KUelia!
Kitpylaa Kitajle)
5.00
0.6
TVDKo
1.5
4.80
0.4
3.0
4.50
0.5
3.0
0.0
accaplance rale
atcuplannce
acceplante 1ata
50
100
90-
target moments
80
70
10
acceptance 10
acceptance
Figure 4: Estimation of the divergence from the EBM (TVD and KL p), moments of features female and science, and divergence from the original base model (KL from a) to debias GPT-2 biographies talking about scientists. We also show samples from running the QRS sampler at 10-3 acceptance rate. Samples are cut off at 40 (subword) tokens and are manually chosen to show two male and two female biographies, for constraint satisfaction (moment matching) results refer the graph. We color words that fire our female or science features.
As before, we obtain 1M samples from the proposal distribution to compute importance sampling estimates of quality and efficiency metrics (i.e., TVD(p, (p. p3). DKL Dkl(pllpd (pllps) and AR), plus the backward
KL-divergence from the base language model DKL (-l[())))) (Eq, 27 in Appendix B and the moments
of the features that wish control (Eq. [ We show all metric curves function of acceptance rate of the QRS algorithm as well as some example generations in Fig.
We find that TVD(p, Pa) and DKL(plpe)) (as well the upper-bound on TVD(p, pp)) steadily converge to 0 as the acceptance rate decreases, meaning that we can perfectly match the target EBM the cost of sampling efficiency. As a result, moderate acceptance rate AR 10-3 we nearly perfectly debias our original language model while exclusively having it generate biographies about scientists (49.5% female and 99.8% scientist biographies). We show some example generations at AR 10-3 chosen manually to show two male and two female biographies. Notably, we also achieve very decent constraint satisfaction (44.8% female and 99.7% scientist biographies) and TVD (at 0.27) already AR 10-1 allowing to considerably improve the quality at small cost in efficiency. Divergence to the original language model DKL. (polla) steeply increases as the feature moments matched more closely, after which it gradually decreases before stabilizing. This reflects the construction of the EBM, which projects az)) onto the constraint manifold in such way that the KL-divergence from the original language model is minimized. Two more pointwise and two more distributional constraints are shown in Appendix G with similar results.
3.3 PARAPHRASING
Finally, inspired by Miao et al. 2019). we do proof-of-concept experiments on paraphrase generation by framing it as conditional EBM. Specifically, given sentence paraphrase, define EBM through a pointwise constraint on a(x) = GPT-2(x), with b(x) a binary classifier that classifies pair (3r, y) paraphrase if the cosine similarity between their sentence embeddings is above 0.95.
7

---

Under review as a conference paper at ICLR 2022
How the two wheeler insurance from Axa insurance?
Are there Doctor Who references the Muse song 'Knights of Cydonia"?
French, how you say "coal"?
1.00
1,00
1.0
2 0.50
3.50
0.50
0.25
0.00
3.00
0.00
000000000000
10
10
accepcance rate
acoapcance rabe
acooptance
Input Sequence
Propesal Distribution
QRS samples from AR 10
How the two wheeler
What about bicycle insurance from Bharti Axa insurance?
How is the Axa Bharti two wheeler insurance policy?
insurance from Blurti
What about the Bhurti Asa insurance? is
How is Bharti Asa insurance for two-wheeler?
Asa insurance?
Axa insurance plan?
The Bharti Two wheeler insurance. How
Are there Doctor Who references the Muse song "Knights Cydonia"?
Do you hear a hint of doctors in the Muse songs "Knights Are there Doctor Who references in Muse's Knights of Cydonia"?
of Cydonia?
Can you find a hint at Doctor Who in the "Knights of Cy- Does this Muse song 'Knights of Cydonia' have any references to Doctor Who?
donia" line from the book's Muse song?
Are there any references to Doctor Who in a muse song, Are there Doctor Who references in Muse's Knights Cydonia?
Knights Cydonia?
How do you call 'cool' in French?
How to Say "cool" in French
In French, how do you say "?
How do you
language Cool in French?
How to Say 'Cool' in French
How do you say "coo'' in French?
How do you say "coo!" in French
Figure 5: TVD(p, Pa) running the QRS sampler at various acceptance rates to generate paraphrases of three sequences (top). We show some example paraphrases from both the proposal distribution ((x)) (round-trip NMT) as well as the QRS sampler ps at an acceptance rate of 10 (bottom).
We obtain high-quality sentence embeddings from sentence BERT (Reimers & Gurevych 2019). As proposal distribution we will not be using GPT-2, but rather illustrate how we can utilize off-the-shelf deep learning models proposal distributions for QRS. In particular, we use round-trip MT model, which is a well-known tool in generating paraphrases (Bannard & Callison-Bure
2005 Mallinson the English-to-Gemme and German Crimman-tt-Ennliitee models from Ng et al. (019). We first obtain a beam searched (Graves] 2012) translation into German and then define the proposal distribution as the German-to-Fnnglle model conditioned on the beam searched translation. We locally renormalize the model to do top-30 sampling (Fan et al.) 2018).
eet al. 2017). Specifically,
We show importance sampling estimates of TVD(p, (p. pa) using 1M samples for three sequences in Fig. Jalong with example samples from both the proposal distribution and QRS AR 10-5, The proposal distribution quality varies per input sequence as can be seen by the slope of the curve and the low-efficiency starting points of some curves (non woom-paraphrases are always rejected and so have big influence on the acceptance rate). Still, QRS allows us to approximate the target EBM reasonably well the cost of sampling efficiency (TVD p&)) is 0.20, 0.42 and near 0). Looking at the examples, find the proposal distribution to produce decent paraphrases, but not always semantically equivalent or grammatically correct. The QRS samples are mostly semantically equivalent, though they still produce some mistakes ("Axa Bharthi" vs "Bharti Axa") and seem to be insensitive to the question mark and to the casing of words ("Cool"". "Two-wheed wheeler insurance"). Interestingly. this experiment illustrates how the presented approach could be employed to disentangle the questions of how to model a problem (by defining the corresponding EBM) and how to efficiently sample from (by improving the proposal distributions), allowing to work on each of these questions separately.
RELATED WORK"
Sampling from discrete EBMs does not require an MC approach. DPG (Parshakova et al. 2019b) instead trains autoregressive model that approximates a given EBM, which can then be used to obtain samples efficiently. However, it can be hard or impossible, in practice, to approximate the target EBM accurately because of its complexity, more fundamentally, because of inherent
We use http://///..ooeefeee///////eeeta
$ Wee use heam size of 5.
For more related work, in particular about continuous EBMs, and also the use of sampling techniques in natural language processing, please see App.
8

---

Under review as a conference paper at ICLR 2022
limitations of autoregressive architectures (Lin et al. 2021 For instance, while empirical results by Khalifa et al. (021) show that their DPG- based approximation is reasonable, there is still a sizeable gap to the target distribution. Here, close the gap almost completely at moderate cost in sampling efficiency by using the approximation as a proposal distribution for QRS. For this paper we were inspired by the ability of some Monte Carlo approaches guarantee accurate sampling in the limit. Without trying to cover the full landscape here, we provide some pointers to relevant MC techniques that can exploit global proposal distributions. Possibly the most obvious MCMC candidate, as already mentioned, is IMH (Robert & Casella 2004 $7.4); we devote Appendix E to a detailed comparison of IMH with QRS. Due to the non i..dd nature of the associated sampler. to its inability to score its samples, and the resulting unavailability of explicit convergence diagnostics, we then argue for the superiority of QRS for our purposes. Several other approaches than ours have taken rejection sampling as their starting point. Similar to us, Rejection Sampling Chains (Tierney 1992). Chib & Greenberg 1995] $6.1) do not require a global upper-bound. It is a hybrid that uses rejection sampling a region satisfying partial upper-bound but combines it with IMH outside of that region to produce a Markov chain that converges to the correct stationary distribution in the limit. Caffo et al. (002) propose Empirical Supremum Rejection Sampling, an algorithm that adaptively increases the 3 upper-bound based on the maximum observed so far, with focus on convergence in the limit rather than approximation quality. Some researchers have observed before that partial bound 3 leads to the probability distribution presented in Eq. [ Rejection Control (Liu et al. 1998). (Liu 2004 pp. 44-45) makes use of this observation for accelerating the computation of an unbiased importance sampling estimate of the expectation (x)) in situations where computing (x) expensive and where is desired to reduce such computation in regions of p for which the importance ratios are small and have less impact on the importance sampling estimate. None of the above approaches provide explicit convergence diagnostics nor consider a trade-off between efficiency and approximation accuracy. We argue that such a trade-off is important for practical use-cases of sampling, where fast response time may be prioritized over obtaining exact samples.
5 CONCLUSIONS
In this paper, we address the problem of obtaining samples from a target EBM given access to a good global proposal distribution. In general, a technique that addresses this question has the potential to decouple, for any generative task, modelling (by tuning the EBM definition) from efficient sampling (by tuning the proposal distribution). In the past, high-quality global proposals were typically not easy to come by, thus strongly motivating the development of MCMC techniques which could exploit simple local proposals that computed transition probabilities between candidate samples. Today, however, developments in neural network training techniques make high-quality global proposal distributions easier to obtain than before. Motivated by such developments we propose QRS, a generalization of rejection sampling that exploits such proposals to approximately sample from an EBM. QRS can be applied even cases in which no upper bound of the importance ratio between the FBM and the proposal distribution scores is known, or even exists at all. Notably, QRS also provides strong theoretical guarantees, which include not only convergence to the target distribution (Eq. 4 but also diagnostics that are not available for other MCMC sampling techniques like independent Metropolis- Hastiing,,, such as an upper bound on the TVD (Eq, 3 or unbiased estimators of the TVD and KL divergence to the target distribution (Eqs. TO Our experimental results discrete EBMs show that QRS achieves strong results on the studied controlled text generation setting where, for instance, the sampler achieves excellent debiasing of the language model using acceptance rates in the range of 10-1 to 10-3, Furthermore, we show the versatility of the approach by showing how it can be applied sample paraphrases from an EBM formulation derived from combining a pretrained language model and a sentence similarity score. Yet, there is a tradc-off between quality and efficiency, and finding the right balance will depend on the particular application. QRS allows to use any arbitrary value of 3. producing levels of quality and efficiency that can be estimated. For convenience, in Appendix [ we also describe variant of QRS that automatically adjusts 3 under the constraint of not falling below a target acceptance rate. Last, we note that while here we have focused on EBMs for discrete sequential spaces, nothing prevents QRS from being applied to continuous spaces, making it potentially useful for such applications speech or vision.

---

Under review as a conference paper at ICLR 2022
REPRODUCIBILITY STATEMENT
To ensure the full reproducibility of this work, we have included in Appendix A and B complete proofs and derivations of all propositions and quantities in this paper. Furthermore, source code of all experiments is provided as an anonymized link to the reviewers and will be open-sourced upon publication of this manuscript. Lastly, table with the range of values used to generate the plots is given in Table in the Appendix.
ETHICS STATEMENT
Part of the experimental section of this paper studies the generation with distributional control task, defined by Khalifa al. (202T). The goal of this task is adapt the generations of language model to a given set of norms that should be quantifiable as preferences over the moments of certain features. This formalization has the potential of addressing numerous problems related to social bias in large pretrained language models (Sheng et al. 2019 Liang et al. 2021), including gender bias. Nonetheless, we note that the approach is not prescriptive with respect which norms should be applied, nor about how to quantify the relevant features, all of which can be decided with the relevant stakeholders. Finally, we note that all experiments have been done on the English language due the availability of large pre-trained language models in this language. We believe that the presented set of techniques should be equally applicable to other languages and multilingual models as well.
REFERENCES
Christophe Andrieu, Nando De Freitas, Arnaud Doucet, and Michael Jordan, An introduction to meme for machine learning. Machine learning, 50(1):5-43, 2003.
Colin Bannard and Chris Callison-Burchy Paraphrasing with bilingual parallel corpora. In Proceedings of the 43rd Annual Meeting of the Association for Computational Linguisties (ACL '05), pp- 597-604, Ann Arbor, Michigan, June 2005, Association for Computational Linguistics. doi: 10.3115/1219840. 1219914. URL httts:::: ptttts:://acannthol..o www.aaathooooyyooo///-----00 org//o5-10/P
Brian S Caffo, James G Booth, and AC Davison, Empirical supremum rejection sampling. Biometrika, 8944)744--75, 2002.
Djalil Chafai. Back to basics - Total variation distance, 2010. URL htt.::t::: faa
net/ http//llgg/2/110// 11//2/11110// 1ttp1////1////1-11/1e0 wtwpac/ttt-bbasiieeeeeooo--ooo-e -oto--aaiiccttttlllaaaaaaaea--ee oataaaas-etttttaaaaaaaaaaaaaaaee
Siddhartha Chib and Edward Greenberg. Understanding the metropolis- algorithm. The Utt
American Statistician, 49(4):327-335, 1995. doi: 10. 108000003
/ //amstatt.tadffooo nee. wwm/ wwt.coo/ooooooooooooo
080 00080/0003130000
Mary Kathryn Cowles and Bradley Carlin. Markov chain monte carlo convergence diagnostics: A comparative review. Journal of the American Statistical Association, 91(434):883-904, 1996.
URL http:://www/ww.. jstor wwt//t/gaaaaooooo wtt.ssaaabeeeeit
Yuntian Deng, Anton Bakhtin, Myle Ott, Arthur Szlam, and Mare' Aurelio Ranzato. Residual energy- based models for text generation. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. URL https
//openreview n httee//ooummdddl1eeeee0
Yilun Du, Shuang Li, B. Joshua Tenenbaum, and Igor Mordatch. Improved contrastive divergence training of energy based models. In Proceedings of the 38th International Conference on Machine Learning (ICML-21). 2021.
Bryan Eikema and Wilker Aziz. Sampling- based minimum bayes risk decoding for neural machine translation. CoRR, abs/2 108.04718. 2021. http://p/////.l...////////////// 04718
Angela Fan, Mike Lewis, and Yann Dauphin. Hierarchical neural story generation. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). pp. 889-898, Melbourne, Australia, July 2018. Association for Computational Linguistics. doi: 10.18853/v1/P 1082. URI. a anthol ogy. ogt.oog/oooogo-ee.
10

---

Under review as a conference paper at ICLR 2022
Kartik Goyal, Chris Dyer, and Taylor Berg- Kirkpatrick. Exposing the implicit energy networks CoRR, abs/2106.02736, 2021. URL
behind masked language models via metropolis-hastinn
/bbs htttss://arxiii org/ a / 2106. 02736
Will Grathwohl, Kevin Swersky, Milad Hashemi, David Duvenaud, and Chris Maddison. Oops i
took a gradient: Scalable sampling for discrete distributions. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning. volume 139 of Proceedings of Machine Learning Research, pp. 3831-38/44 1-841. PMLR, 18-24 Jul 2021. URL m0m.mrrr.... htttps::/proceedii pree:///pppceeeec.......eessssse
html]
Alex Graves. Sequence transduction with recurrent neural networks. In ICML. Workshop on Repre- sentation Learning, volume abs/1211.3711, 2012.
Michael Gutmann and Aapo Hyvärinen. poise-contrastive estimation: A new estimation principle for unnormalized statistical models. In Yee Whye Teh and Mike Titterington (eds.), Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, volume 9 of Proceedings of Machine Learning Research, pp. 297-304, Chia Laguna Resort, Sardinia, Italy, 13-15 May 2010. PMLR. URL Stthttt:: /tt/ttts://prcccddng..s mlr www.rr.esssvve. httSs/////ggttann//n// html
W Keith Hastings. Monte carlo sampling methods using markov chains and their applications. Biometrika, 57(1):97-109, 1970.
Tianxing He, Bryan McCann, Caiming Xiong, and Ehsan Hosseini-Asl. Joint energy-based model training for better calibrated natural language understanding models. In Proceedings of the 16th Conference of the European Chapter of the Association for Computational Linguistics: Main Volume, pp. 1754 1761, Online, April 2021, Association for Computational Linguistics. URL https: / www. ac aclweb orq/ http://ahhoooogy. wwwp:///oggg.....eaaeeaaaaaa.aaa
151
Geoffrey E. Hinton. Training products of experts by minimizing contrastive divergence. Neural Comput., 1470)1177--1800,, 2002. doi: 10. 10.1662089976602262228888 URL https://doo
org/10.1162/ 12r111622/02
Ari Holtzman, Jan Buys, Li Du, Maxwell Forbes, and Yejin Choi. The curious case of neural text degeneration. In International Conference Learning Representations, 2020. URL https
(ongenrerieee.netfforim.mmm.a net for d
Aapo Hyvärinen. Estimation of non-normalized statistical models by score matching. J. Mach. Learn. Res., 6:695-709, 2005. URL http://dblp... uni trier. detp:e//aaa//////uaaaaaaaaaaaa
feal:/mmlrr..r ht
Muhammad Khalifa, Hady Elsahar, and Mare Dymetman. distributional approach to controlled
text generation. In International Conference on Learning Representations, 2021. URL https
//openreview. net pnset/forumidd jokw45-ww4455--- -
Yann LeCun, Sumit Chopra, Raia Hadsell, Marc' Aurelio Ranzato, and Fu Jie Huang. A Tutorial on Energy-Basse Based Learning. Predicting Structured Data. MIT Press, 2006.
Paul Pu Liang, Chiyu Wu, Louis-Philippe Morency, and Ruslan Salakhutdinov. Towards understand- ing and mitigating social biases in language models, 2021.
Chu-Cheng Lin, Aaron Jacch, Xin Li, Matthew R. Gormley, and Jason Eisner. Limitations of autoregressive models and their alternatives. In Kristina Toutanova, Anna Rumshisky, Luke Zettlemoyer, Dilek Hakkani- Türr Iz Beltagy, Steven Bethard, Ryan Cotterell, Tanmoy Chakraborty, and Yichao Zhou (eds.), Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACL-HIL 2021, Online, June 6-11, 2021, pp. 5147-5173. Association for Computational I Linguistics, 2021. doi: 10.18653/v 1ttl//112000 1/22 mhaacl-miin444 405. URL https: //te::///oo... 1ttp://111.1133////////00
naacl-mas ma 405
Jun S. Liu. Monte Carlo Strategies in Scientific Computing. Springer Series in Statistics. Springer New York, 2004.
11

---

Under review as a conference paper at ICLR 2022
Jun S Liu, Rong Chen, and Wing Hung Wong. Rejection control and sequential importance sampling. Journal of the American Statistical Association, 93(449):1022-1001,, 1998.
Jonathan Mallinson, Rico Sennrich, and Mirella Lapata. Paraphrasing revisited with neural machine translation. In Proceedings of the 15th Conference of the European Chapter of the Association for Computational Linguistics: Volume I, Long Papers, pp. 881-893, Valencia, Spain, April
2017. Association for Computational Linguistics. URL https: / /acc/aaaatttti awwlanhoooooyyyooooooooooooooooe org/ E17-1083
Luca Martino, David Luengo, and Joaquín Míguez. Accept-rejeed methods. In Independent Random Sampling Methods, pp. 65 113. Springer, 2018.
Nicholas Metropolis, Arianna Rosenbluth, Marshall N Rosenbluth, Augusta Teller, and Edward Teller. Equation of state calculations by fast computing machines. The journal of chemical physics, 21(6):1087-102. 1953.
Ning Miao, Hao Zhou, Lili Mou, Rui Yan, and Lei Li. CGMH: constrained sentence generation by metropolis-hastinge sampling. In The Thirty-Third AAAI Conference on Artificial Intelligence, AAAI 2019, The Thirty-First Innovative Applications of Artificial Inteligence Conference, IAAI 2019, The Ninth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019, Honolulu, Hawaii, USA, January 27- February 1, 2019, pp. 6834-6842, AAAI Press, 2019. doi: 10. h33p///....v300..33303 33C16834
v33101
Ning Miao, Yuxuan Song, Hao Zhou, and Lei Li. Do you have the right scissors? tailoring pre- trained language models via monte-carlo methods. In Dan Jurafsky, Joyce Chai, Natalie Schluter, and Joel R. Tetreault (eds.), Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, ACL 2020, Online, July 5-10, 2020, pp. 3436-3441, Association for Computational Linguisties, 2020. doi: 10. 10.18653/w1/2020 aw0.200..-mmmi.3333333 URL https://doi org/ 1xx//10.18553/1122 acl aclaammm....mmam...maaaaaamaaaam 314
Subhajit Naskar, Pedram Rooshenas, Simeng Sun, Mohit lyyer, and A. McCallum. Energy- based reranking: Improving neural machine translation using energy-based models. ArXiv, abs/2009. 13267,, 2020.
Nathan Ng. Kyra Yee, Alexei Baevski, Myle Out, Michael Auli, and Sergey Edunov. Facebook FAIR's WMT19 news translation task submission. In Proceedings of the Fourth Conference on Machine Translation ( (Volume 2: Shared Task Papers, Day 1), pp. 314-311 Florence, Italy, August 2019. Association for Computational Linguisties. doi: 10.18653/v 1/11955333. URL https:/ //cc///ccaaa antho I wog.oogg...oooooo...............
oot.aaaooooooooooooooo.... W1 901gg///99553001 5333
Art B. Owen. Importance Sampling. In Monte Carlo theory, methods and examples, chapter 9, 2013. URL htt.:httss//stttweeet an ord. edw/ Chaee/hhaaarrraaeeeee iiniisspffff.
G. Parisi. Correlation Functions and Computer Simulations. Nucl. Phys. B, 180:378, 1981. doi:
121016/05500-32138119005555
Tetiana Parshakova, Jean-Mare Andreoli, and Marc Dymetman. Global Autoregressive Mod- els for Data-Efficiiet Sequence Learning. In Proceedings of the 23rd Conference on Com- putational Natural Language Learning (CoNLL), pp. 900-909, Hong Kong, China, Novem- ber 2019a. Association for Computational Linguistics, doi: 10.18653/v1/119--088. URL
https: www wwwp://.www..rr//tttoo..ooo 919-0004
Tetiana Parshakova, Jean-Mare Andreoli, and Mare Dymetman. Distributional Reinforcement Learning For Energy-Basee Sequential Models. ArXiv, abs1191.0087,,, 2019b.
Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. Language models are unsupervised multitask learners. OpenAl Blog. 1(8):9, 2019.
Nils Reimers and Iryna Gurevych. Sentence-bert: Sentence embeddings using siamese nett-netw In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing. Association for Computational Linguistics, 11 2019. URL Rtthttps: :/ap/xiv/////////////a///a orq/ abs wabb//990 1908
1 10084
12

---

Under review as a conference paper at ICLR 2022
Christian P. Robert and George Casella. Monte Carlo Statistical Methods (Springer Texts in Statistics). Springer- Verlag, Berlin, Heidelberg, 2004.
Vivekananda Roy. Convergence diagnostics for markov chain monte carlo. Anmual Review of Statistics and Its Application, 7(1):387-412, 2020. doi: 10.1 40 https: .rg. www.:/1/////eeaeeeeeee annurev
URL 031219-
Emily Sheng, Kai-Wet Chang, Premkumar Natarajan, and Nanyun Peng. The woman worked as babysitter: On biases language generation. In Kentaro Inui, Jing Jiang. Vincent Ng. and Xiaojun Wan (eds.), Proceedings of the 2019 Conference Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing, EMNLP-IJCNLP 2019, Hong Kong, China, November 3-7, 2019, pp. 3405-344110 Association for Computational Linguistics, 2019. doi: 1..18663//1/D119-1 URL httpstttst//i.ooo////// 18653/v1/D19-110
Yang Song and Stefano Ermon. Improved techniques for training score-based generative models. CoRR, 1bs/2006.09011, 2020.
29011
Yang Song and Diederik P. Kingma. How to train your maneery-bbssdd models. CoRR, abs/2101.03288, 03288
2021.
Luke Tierney. Exploring posterior distributions using markov chains. Technical report, MINNESOTA UNIV MINNEAPOLIS DEPT OF STATISTICS, 1992.
John Von Neumann. Various techniques used in connection with random digits. National Bureau of Standards Applied Math Series, 12:36-38, 1951. Notes by G E Forsythe. Reprinted in von Neumann's Collected Works, 5 (1963), Pergamon Press pp 768-770.
Giacomo Zanella. Informed proposals for local MCMC discrete spaces. arXiv: [math, star], November 2017.
Maosen Zhang. Nan Jiang, Lei Li, and Yexiang Xue. Language generation via combinatorial
constraint satisfaction: tree search enhanced Monte-Carlo approach. In Findings of the Asso- ciation for Computational Linguistics: EMNLP 2020, pp. 1286-1292 Online, November 2020. 1m1... URL
Association for Computational I Linguistics. doi: 10.
hetpss:/aclanttoloogy
2020..020... findings emnlp 115
Yaoming Zhu, Sidi Lu, Lei Zheng. Jiaxian Guo, Weinan Zhang, Jun Wang, and Yong Yu. Texygen: A benchmarking platform for text generation models. In Kevyn
Qiaozhu
Mei, Brian D. Davison, Yiqun Liu, and Emine Yilmaz (eds.), The 41st International ACM SIGIR Conference on Research & Development in Information Retrieval, SIGIR 2018, Ann Arbor, MI, USA, July 18 2018, pp. 1097-1100, ACM, 2018, doi: 10.1145/3209788.221000 3210080
URL
https: /oi org 11..0..1141..00
13

---

Under review as a conference paper at ICLR 2022
A PROPERTIES OF QRS: PROOFS
Equation I: By definition Pa (a( is the probability that the firs output from Algorithm
equal to On the first step of the algorithm, the probability that given z is accepted is (x)), while the probability that no I at is accepted is p E g(z) Tx)
Exex ((z)rz. More generally, the probability for æ to be accepted on step of algorithm, while no z was accepted on previous steps is then p² g(z)r= Overall, the probability (2(x) of x to be the first to be accepted is:
Σ (x))r> = g(x)rr
(11)
1
g(z)r==
Ps(x).
(12)
ΣxEx (())r
ZB
Equation (2: We have:
AR3- Ezin ((=))(())))) = Σ
min min(P(x))
(13)
#EX
- Σ -a(x)=2(p)
(14)
Equation (3):
For the proof, we will need a well-known property of TVD (Chafai 2010), namely that, for any distributions pt, p2 over X, have:
TVD(PI,P2)
Σ
(1(x) - p2(1).
(15)
x xEX:pI (z)
The reason is simple; we have:
Σ
P1(x) - p2(xx)
E P2(x) (x())
(EXp)(+)2mm(11)
Σ (1 - Σ p2(x) 0,
zex
xEX
which proves that the first and second expressions under brackets are equal. Then we have:
TVD(P1,P2) = 1/2
(x) P2(1)
xEX
=1/2
Σ
(x()) P2(x))
+1/2
Σ
P2(x) Pi
(o)
(a)
Σ
(
=EX:pi(=)2pat
Our main proof, illustrated in Figure 6 proceeds follows. Let Ag = {I X P(z) Bq(x)) and Ag = X Ag. We have Pa(x) = min( min)
and therefore Pa(x:) P(x) for Ag, and
Pz(x) < P(x) for Ag. Overall P3 is smaller or equal to P and thus ZB < Z.
For any
have p=(x)= 1 and p(z) -- = and hence for Ag.
=
p(x) S (2)).
If we define C3 = fxE X: p(x) & pb(t)), and C3 x Cs. we have Ag S Css and
Cg S Ag.
Using Equation
15
we now see that TVD p3) = Exe Exexxp(=)2pp0 p(z) - po(x) = p(z) pa(x) = Eneo, p(x) p2(x)) < Exer, p(x).
Exex Exexp(r)xpp())
Finally we get:
TVD(p, ps) p(Op) < p(A)) = p(Ag).
(16)
Or, for that matter, due the obvious i.i.d nature of the algorithm, for any fixed ki the k-th output.
14

---

Under review as a conference paper at ICLR 2022
PB
Pp
Ap
Ag
Ap
Ap
Cp
Cp
Figure 6: Visualization of Main Proof. The left panel shows the unnormalized distributions P and Pg. the right panel their normalized versions p and p3- On the right panel, the under the p (resp. the pa) curve represents the total p-mass (resp Pa-mass) of X, namely 1. To simplify visual comparison, the figure assumes that
and pæ is Pa moved up by the constant factor Z The TVD between p and p3 is equal to the area between the two curves above /
1, in other words that P p: then Zg
Cg. but also to the area between the two curves above Cj. This last area is included inside the area below the curve above As, which is the visual counterpart of equation (6
Equation 4 Clearly, for any (normalized) distribution p over a discrete space X, for any > 0, there exists finite subset X' S X s.t. p(X') 1 - If we take 8 = max ((ar) 3 is finite, X' C Ag, and therefore p(As) 2 1 - e, which proves the result.
P(x) then
A generalization to arbitrary q-supports This last result exploits the assumption that we made during the whole section[]- that the support of p. Supp(p), is contained in the support of q. Supp(g), in other terms, p(x) 0 <(x) 0. If that
not the case P(z) could be infinite and As would not be defined. However, is
then 3 = ma q(x)
interesting that we can actually generalize the result to the case where Supp(p) may not be contained in Supp(g). Then, for any E > 0, there exists a finite subset Y' S Supp(q) s.t.
p(Y") > p(Supp(g) - If we now take 3 = max q(a)" and therefore p(As) 2 p(Supp(q)) c. For any B, because all the x's in Ag are obviously in Supp(q), we have p(As) S ((Supp(4)), and therefore
P(z) then / is finite, Y' C Ag,
p(Supp(a)) 2 p(Ag) 2 p(Supp(a)) -.
(17)
When the support of p is included in Supp(4). we have p(Supp(g)) = 1, and therefore we get the previous result back, but now we see that, in the general case:
lim (1 p(Ag)) 8
p(Supp(a))
(18)
B TVD AND KL ESTIMATES
Here provide derivations for the estimates of equations p and
10)::
P(x)
Po(x)
TVD(p.Ps) 1/2
Σ
1p(x)
pp(x)) = 1/2 Eara
(19)
Zg(x)
Z,g(x))
xEX
P(x))
Pz(
1/2 Σ
(20)
Zg(Ø,)
Zzq(xz))
KE(L
p(x)
ZB
P(x)
log P(z)
DRL(p.Ps) Σ p(x)) log
log Z
+ Exryy Zg(z)
(21)
(z(x)
Ps(x))
xEX
ZB
P(x.)
P(xs)
log
N
Σ
log
(22)
Zg(x;)
Ps
[E[L.N]
15

---

Under review as a conference paper at ICLR 2022
Furthermore, we present the derivation and estimate for DEL (ps.a)) a):
pz(x) a(x)
Expp log Pz(x)
DEL(P3, a) = -Ea-py log
(23)
ZB a(x)
Pz(x))
=- log ZB + E Eapps log
(24)
a(x)
=- -oog log 2z + R Reng P3(x) xz)
log Pœ(a)
(25)
7B ((x))
x3)
a(x)
- =log EB + 4o Egnn Po(x)
log PĄ(œ)
(26)
g(z)
a(x)
Po(ai)
log Pa(x,)
log Zz + Z3 N-1 Σ
(27)
((xz)) VE(I,N]
a(x,)
C PROJECTION OF THE PROPOSAL FOR POINTWISE CONSTRAINTS
Lets say we have a proposal distribution q that we want to use for approximating an EBM with pointwise constraint Pxx) alz)b(z) where b(x) {0. One simple approach would be projecting q directly into the manifold of the sequences matching the constraint, by simply rejecting all sequences x where b(z) O. In other words, are sampling from new probability distribution aproj (2) xx ((x)b(x). It turns out that we can compute the probability assigned to each sequence x by Uproj, as follows:
Upros (x) = 1/7 aroos ((z)
for b(x:) 1
= 0
for b(x) 0
Note that Z Sproy
Σx (x))((r) can be easily estimated by using sample from
Therefore, the TVD(p, 9proy) and DKL (p, aproz) can be estimated following the same procedure as Eqs. 19 and 21 respectively.
D INCREMENTAL PRUNING WITH MINIMAL EFFICIENCY TARGETS
The following algorithm describes a version of QRS that incrementally builds a batch of samples S with desired minimum acceptance rate ar min- The algorithm works by obtaining samples x from g and provisionally storing them into S' as long as the rejection coefficient a, not exceed the current value of 8, where u2 Ld( 1). Given that higher values of / imply lower upper bound on the TVD between the samples and the target distribution, ,3 is continually adapted to be as high as possible. Yet, the higher is, the lower the acceptance rate becomes. Therefore, to be practical, ,9 is capped at the highest possible value such that the acceptance rate of the samples seen so far would not fall below a minimum threshold armin. The corresponding maximum 3 value for acceptance rate threshold min is computed as the value for which the percentage of all previously obtained samples satisfying Oz > a is ar'mn (i.e., the percentile armin of all previously computed A {a.) values). Should 3 be increased at any point, previously stored samples in S are pruned to remove those that failed to meet the acceptance criterion 0₂ > B. The algorithm stops when at least n samples have been collected.
( does
16

---

Under review as a conference paper at ICLR 2022
Algorithm 2 QRS with incremental pruning
Require: EBM P, proposal desired number of samples na, minimum acceptance rate ar armin-
Ensure: A set of samples S and an estimation of / s.t. the acceptance rate is at least drmin.
1: procedure QRS-QNCRSRRRR QRS-INCREMENTAL
S S []: 3: while [S] < do
0, [], Smaze
4: I. ~ 9(-)
5:
Br + 9tx)
P(n)
6:
Bma <- PERCENTILE( A, ar
7:
if (maz)(32.mmaa) > then
8:
3 min(B2, 3maz)
PRUNE(S, ())
10:
Mr Unif(0,
11:
a, + az
if as > B then
ie. ue 3q(a)
< + [(r, a.)]
14:
A [(a=)] return S
15:
16:
procedure PRUNE(S, (3)
17:
keep (I, a²) in iff 0i2 > 3
b i.c. up <
P(a) Pq(mn)
procedure PERCENTILE(A.77
19:
return max Os s.t. jay E A ay S asl < <r/A].
E
INDEPENDENT METROPOLIS HASTINGS (IMH): ALTERNATIVE TO QRS! ?
274
The Netropolls-Hastinne Algorithm
We therefore have the following convergence result for SeetrpolissHassings Markov chains.
Theorem 7.4. Suppose that the Metropolis-Hastings Markov chain (X(t)) is f-irreducible.
(i) h E Lf)), then
Σ M(x(1)) = ((=))(()dde - 1=1
lim T-200
a.c f.
(it) If. addition, (X(9) aperiodic, then
lim // (2, (m(x)) - =0
for every initial distribution μe, where K (z, denotes the kernel for transitions, as (6.5).
Figure 7: Necropolis-Hastting Theorem 7.4. copied from (Robert & Casella 2004). Here f is the target distribution. Note the difference between (i) and (ii). Property (i) is concerned with the f-expectation of R. h, and considers the average over the T first elements of a single chain, which converges to the expectation for increasing T. Property (ii) concerned with the TVD distance between the target distribution f and the distribution obtained by repeatedly running an n-step chain and outputting the n-th element. This distance converges to for increasing n.
E. THE INDEPENDENT METROPOLIS HASTINGS (IMH) ALGORITHM
Markov chain Monte- Monte-Carlo (MCMC) (Robert Casella 2004 is the most developed general class of techniques for sampling from EBMs, exploiting random walk and Markov Chain theory (rejection
17

---

Under review as a conference paper at ICLR 2022
sampling (RS) and QRS do not random walks, and do not qualify MCMC). In the situation that we are focussing on here, namely, the availability of global proposal & that already approximates to some extent, a suitable MCMC technique is Independent Metropolis- -aapting (IMH) (Robert & Casella
2004 $7.4), see Algorithm
Algorithm 3 IMH
Require: P.
1: x ~ q
2: while True do
3: x' ~
Ta.s' min(1, P((')/((a')
4:
P(x)/a(m)
Prob. of moving x!
5:
u~ [0,0)))
6:
uf S T2,2' then
7:
output
8:
+- x¹
9:
else
10:
output
IMH is a special case of the Satoopolis-Hsstingg (MH) algorithm, where the proposal g(x') does not depend on the current x []]
IMH and QRS vs. RS: no need for global 8 IMH and QRS share common advantage over RS: they do not need a global 3 with P(x)//(x)) < 3, Vo E X. It is often the case that such bound does not exist, is not known, or is intractably large. In such cases, RS cannot be used, but both IMH and QRS can.
IMH vs. QRS: convergence to p in the limit IMH inherits from MH fundamental "convergence to in the limit" property:
lim TVD(p, (m) = 2+000
(28)
where x (n) denotes the sampler associated with what we will call the "n-steps variant of Algorithm 3 namely the algorithm that performs the loop on Line exactly n times, does not output anything, but returns the last x. This property corresponds, in our own notation, to Theorem 7.4.(i) of (Robert)
Casella 2004). copied Fig. 7
QRS has its own form of convergence in the limit, Equation
IMH vs. QRS: convergence diagnostics Equation 28 tells us that performing steps of MH (and in particular IMH) produces distribution x7(*) that gets closer and closer to p with increasing n, but it does not provide any explicit estimate of TVD(p, x (n)),, nor any other divergence metric from the target distribution.
In general, with MCMC techniques, such explicit convergence diagnostics very difficult obtain (Cowles & Carlin 1996 Roy 2020). By contrast, as we saw (Equations 3 7 1Op, the QRS algorithm does provide such explicit estimates. This important because it allows calibrate the level of effort (acceptance rate) we have to invest in order to obtain a certain quality (TVD or KL to
IMH vs. QRS: ability to score Equation provides an explicit value for (z(x). This is an important property, which, in particular, exploited in the computation of estimates of TVD(p, ps) and DKL (p. p3) in Equations and (10p. This ability to score is conspicuously absent in IMH: there is no obvious way to compute o (a:), not even up constant factor.
In the general MH algorithm, line replaced by: f.. min(1, Piz')/u(a'le))
12 However, IMH does have an advantage over MH here. In the special case that a global ( s.t. p(a) g(z) < 3, Va
X exists, can he shown that TVD(p, (=)) < (1 - (Robert & Casella 2004 p. 277). However, this hound be very conservative and unusable in practice, even those cases where is explicitly known.
18

---

Under review as a conference paper at ICLR 2022
Rager
1e:01
02
Ie
01
1-02
03.03
16-11
16:23
Ie-53
(a) IMH QRS
100
045
60
12-
10
60
40
13
10-
10:01
36-02
1640
10-11
In-02
1e:03
16:00
accestance rate
acceptance 1996
scouptarce rats
(b) IMH-reset vs QRS
Figure 8: We compare the QRS and IMH samplers in practice by taking 1,000 samples at 3 orders of acceptance rate for the constraint 50% female and 100% science. We experiment with a version of IMH in which rate, as well as a version in which we reset the chain after 10, 100, or 1,000 samples. For the latter version we can also estimate perplexity as the samples i..dd We do show the percentage of unique samples for the latter version, but note this is 100% for both QRS and IMH-reset.
fixed burn-in of 1000 and thinning as obtain the desired acceptance
IMH vs. QRS: i..d properties The outputs produced by the QRS Algorithm are immediately Li.d: the acceptance of an x on Line 6 does not depend on the acceptance of previous æ. By contrast, with any MH algorithm, and in particular IMH, if the goal is to produce actual samples, we face a choice. First, we could follow the spirit of (Theorem 7.4.ii) above, restarting the chain each time need to produce sample. Then we would produce i.i.d samples, but at the high cost of wasting n - 1 draws from the proposal before producing just one sample. Or we can - similar to the spirit of (Theorem 7.4.i) for expectations - just produce one long chain from which actual samples, which is the approach we are taking in Algorithm The outputs of this algorithm i.i.d: is possible for the new proposal x be rejected (Line 6) and then the current is repeated the sequence of outputs, possibly many times the current x is "good" (i.e. has a high importance ratio P(w) To mitigate that problem, it is often advocated use "thinning" heuristics on the outputs of the algorithm: only retain output of m, in order reduce the autocorrelation, in the hope of obtaining good balance between the quality of the samples and the efficiency of the sampler, but again, without explicit quality estimates.
extract the
q(x)
E.2 IMH vs. QRS EXPERIMENT
In Figure Sh we compare the QRS and the IMH sampler on the 50% female and 100% science EBM by taking 1,000 samples from each sampler different levels of acceptance rates. We use the procedure described in Appendix D to obtain QRS samples at the specified acceptance rate. For the IMH sampler obtain the desired "acceptance rate" by having fixed burn-in period of 1,000 samples and afterwards only keep every 10p, 100,, or 1000,, sample. The definition of "acceptance rate" for both samplers is the ratio of samples obtained from the sampler (1,000)
19

---

Under review as a conference paper at ICLR 2022
and the number of samples used from the proposal distribution. We use the DPG model as proposal distribution.
We find that while IMH is able to achieve constraint satisfaction similar to the QRS sampler at similar acceptance rates, it does so by repeating some samples multiple times. This can be seen in the fraction of unique samples, which can get as low as 50% out of the 1,000 samples obtained at lower amounts of thinning. While this does not hinder the IMH sampler from achieving asymptotic consistency in estimating expectation values, we believe this be an undesirable property of sampler whose outputs are to be used in actual applications. QRS does not suffer from the same problem, as the QRS algoritm does not make use of a Markov chain.
In Figure Sp we also experiment with a version of LMH that does obtain i.i.d samples by resetting the Markov chain after every sample obtained. We coin this version IMH-reset. We achieve desired acceptance rates by resetting the chain after every 10g, 100,, or 1h00 sample. We obtain 100% unique sequences for this version for a sample of 1,000 samples, like the QRS sampler. For this version we can additionally estimate perplexity under GPT-2, as we have i..d. samples from both samplers. We find that at the target feature moments (for both samplers at the acceptance rate of 10 10-3, QRS samples achieve slightly lower perplexity than IMH-reset.
F ADDITIONAL RELATED WORK: CONTINUOUS EBMS AND EBMS FOR NLP
While this paper is concerned about generating samples from discrete EBMS, more research so far has been more concerned with the training of continuous EBMs, in particular for applications in vision. Continuous EBMs have the advantage over discrete ones in that it is possible to differentiate the EBM P (z) relative to x. and not only the approximating model Ty relative to O. Training such EBMs (see the survey in (Song & Kingmal ))2TT) can then often be addressed through techniques such as contrastive divergence (Hinton, (202] Du et al., (022), score matching (Hyvärinen] 2005 [Song & Ermon )020), or noise contrastive estimation (Gutmann & Hyvärinen 2010). These approaches
sometimes require an internal sampling procedure, and then one technique of choice is Langevin MCMC (Parisi 1981). J. in which the local Markov chain moves are done based on v,P((x)., a technique which is also employed in case actual samples need to be generated. While such techniques are not available for discrete EBMs, some recent efforts are trying to bridge the gap (Grathwohl et al. 2021).
Sampling techniques are popular in various natural language processing (NLP) applications. For example, MMao et al. (2020) construct rejection-sampling inspired sampler that aims to counteract over- and underestimation of probability regions due to overfitting when fine-tuning large pre-trained language models on small datasets. [Dnng et al. (2020) train globally normalized language models to combat negative effects of local normalization, and use form of SIR to sample from the resulting EBM using an autoregressive proposal language model. Goyal et al. (202T) develop a Metropolis- Hastings algorithm to sample from masked language models. For controlled text generation Miao et al. 2019) propose a random-walk Metropolis- Hastings (MH) algorithm for sampling from an EBM that encodes sequence-level preferences on natural text. Their proposal distribution consists of local string editing operations on randomly selected words or positions. Zhhag et al. (2020) improve on this approach by making use of tree-search algorithm to more efficiently explore the space of proposals, by allowing several edits in a single step of the MH algorithm. In contrast with these approaches we make use of strong global proposal distribution and the QRS sampler. This eliminates any autocorrelations in the samples and ensures good sample diversity inherited from the underlying EBM. Furthermore, the QRS sampler allows us to assess the quality of our samples through divergence metrics from the target EBM, something that is famously difficult to do with MCMC samplers.
G ADDITIONAL CONTROLLED TEXT GENERATION RESULTS
We perform constrained text generation on a distributional, two pointwise and two mixed distributional pointwise constraints. In particular, we constrain the GPT-2 biographies model to contain 1) 50% female biographies about scientists, 2) 50% female biographies about sports or 3) 50% female biographies without additional constraint. Also, constrain GPT-2 small to generate exclusively sequences containing the term "amazing" or to generate exclusively sequences containing the term "Wikileaks". For each of these tasks, we obtained fine-tuned model using DPG, which serves both
20

---

Under review as a conference paper at ICLR 2022
ToM T0
MAM
(a) 50% female scientist biographies
(b) 50% female sports biographies
127
17
12
(c) 50% female biographics
115
6/5
Luge
12
100% sequences containing "amazing"
Ridss
1.5
(e) 100% sequences containing "Wikileaks"
Figure 9: We show importance sampling estimates of TVD(p.-), an upper-bound on TVD(p, Ps). (pll)) DKL(- (a) and feature moments as a function of acceptance rate. We show three distribu- tional constraints on GPT-2 Biographies and two pointiwse constraints on GPT-2 small. As proposal distribution we make use of a DPG model trained for each constraint separately. We show separate lines for the target moments and the moments realized by the EBMs, revealing slight inaccuracies the EBM moments for some constraints. We also show observed moments for 50k QRS samples obtained at acceptance rates 10 10-2, and 10-3
21

---

Under review as a conference paper at ICLR 2022
Experiment
Amin
9max
50% female and 100% scientists
1.0 10 12
9.3 10
50% female and 100% sports
1.0 10-12
2.9 107
50% female
1.0710-7
4.0 103
100% "amazing"
1.0-10
5.3 13'
100% "Wikileaks"
1.0 10-12
100
Table 1: We report the range of B values used to obtain the range of acceptance rates in Figure 9 We note that the procedure described in Appendix D can be used to find 5 values that target some minimum acceptance rate.
as a baseline and as proposal y that we can sample from. the case of pointwise constraints, we also consider naive filter sampler gproj in which the proposal distribution is directly projected onto the constraint manifold by filtering out all samples that do not match the constraint. This sampler also assigns well-defined probabilities the sequences that samples (see Appendix C and can compute estimates of the TVD and DKL for it.
For each task, again obtain 1M samples from the corresponding proposal, which evaluate the proposal q, the projected proposal Oproj (only for the pointwise constraint), and QRS sampling (p)) for range of / values reported in Table T For all of these, compute estimates of the same metrics as in Section 3.2.2 (i.e., TVD(p, ps). (p, ps). AR, backward KI KI--divegeenc from the base language model ( (-laa) la). and the moments the features that we wish to control). Furthermore, we do downstream evaluation of 50k samples obtained through QRS choosing 8 so that the acceptance rate falls exactly at 10-1, 10-2 and 10 (The process is described in Appendix D In particular, we look at the feature moments of the obtained samples.
to
Our results are shown in Fig. 9 As expected, we find that the upper bound of the TVD of pa with p and the KL-divergence from p& to p steadily converge towards 0 as the acceptance rate decreases. For the distributional constraints and corresponding proposal distributions shown here, seems that an acceptance rate of 10 is sufficient to match the target EBM nearly perfectly. Feature moments therefore shows the same pattern, converging towards the target moments with lower acceptance rates, although we find that in some cases the QRS sampler matches the target EBM closely that small inaccuracies in the lambdas obtained from the EBM estimation procedure as described in Khalifa et al. (2021) become apparent. As for the divergence to the original language model DKL. (P la), there is no obvious trajectory that it should follow other than it should converge to the lowest possible value when all constraints are satisfied. Indeed, our results show that this metric follows non-monotonic path at different ARs. Validating our estimates, we note that the moments computed downstream on QRS match tightly the IS predictions, giving us confidence in the accuracy of those estimates. Finally, in the case of our pointwise "amazing" and "Wikileaks" constraints, we find that the naive filter strategy (9proj) corresponds to running the QRS sampler at high acceptance rate.
H EXTRA EXPERIMENTS AND COMPARISONS WITH LOCALIZED MCMC
We focus on discrete Random Walk Metropolis-Hasttingss (RWMH) for text generation, conceptually close to Miao et al. (2019) with some ingredients from Goyal et al. (2021). We did consider GwG Grathwohl al. (20TT) and other related gradient-based proposals, but felt that attempting to apply such techniques for text generation tasks such as those considered in our main experiments would be very ambitious and worth a paper on its own, see Appendix !!
Troobs-with-Grddeee
In our proposed experiments, we construct a local proposal distribution composed of single-token insert, delete and replace operations (chosen randomly from uniform distribution like in Miao et al. (2019). We inform the insert (resp. replace) operation by inserting (resp. replacing word with) a [MASK] token and sampling a new token from BERT. This differs Miao et al. (2019). who instead do a form of Gibbs sampling for insert and replace operations, which requires V (vocabulary size) assessments of the EBM per such operation (an EBM with GPT-2 as a component). This would make this version prohibitively more expensive than our QRS and IMH operations. for which reason we replace this with a single pass of BERT instead. We accept or reject such edits using the Metropolis- acceptance ratio and seed the chain using high-quality global proposal
22

---

Under review as a conference paper at ICLR 2022
Method
AR
% Female tesp. 50%)
S.Science (exp. 100%)
PPLL
Sell-BLEU-SL
% Unigt
TVD.
KL.
CDC
28.1 + 1.8
69.2
+ 1.2
31.9 + 1.1
60.9 2 0.2
100 + 0.0
(hd
RWM11-10
10
37.5
32.2
99.97
Unk.
Unk.
rest--re
10
26.3
G8.4
36.1
59.6
10U
Unk.
Unk.
IMH-10
55.0
100
94.7
58.0
Lnk.
Unk.
TMH--rostt10 10
10-1
41.4
99.4
29.6
91.4
100
Unk.
Unk.
QRS
10
44.1 4 1.1
99.8 1: 0.2
30.2 1 0.8
91.0 1 0.2
100
1: 0.0
0.29
0.56
XWMHS-LOW
100
100
0.1
Unk.
Unk.
RWMHH-eset-1000
10
26.G
G8.2
33.1
90.0
100
Lnk.
Unk.
1MH-1000
10-3
51.5
99.9
91.2
Unk.
Iest- 1000
10-3
48.8
99.8
35.6
90.8
100
Unk.
Unk.
QRS
10 3
49.3
99.8
1.1
90.8
100
0.02
0.02
Table 2: Additional results comparing MC sampling methods on obtaining samples from the "female- science" EBM described in Section 3.2.2 We do not compute perplexity for IMH and RWMH without reset as it does not yield i.i.d. samples. As noted, TVD and KL for MCMC methods are unknown (i.e. we have no way of estimating them). Where available we show mean + one standard deviation over 10 runs.
Method
5:Amazinn (exp. 100%)
PPL.
SLIL-BEEUSS
% Uniq
TVD.
KL.
GDC
1.5
62.4 1.2
85.7 1: 0.3
100 1 0.0
Osd
RWMII-10
10
100
99.96
47.9
Unk.
Unk.
KW KWMH--rset-10
10
61.7
60.1
85.3
100
Unk.
Unk.
IMH-10
10"
100
91.6
62.9
Usk.
Unk.
IMF--reat-10
10-1
100
60.4
87.2
100
Unk
Unk
QRS
10
100 = 0.0
62.8 + 1.1
86.9 1: 0.3
100
1: 0.0
0.17
0.27
RW XWMHH-100
10
71.2
97.3
59.2
Unk.
Unk:
KWMH-1000 0.01 di "rmaazingg
10
100
100.0
Unkk
Unk.
RWMH--100- - 0.1 AC Camazing")
10-3
rhd
dhd
Hhl
Unkk
Unk
1000
10-3
63.7
85.5
Unk.
RWMJI reset 1000 + 0.01 5( (''mmzzing")
10
64.1
61.6
85.8
100
Unk.
Unk.
KWMHHerset-110 1000 a 0.1 (("amazigg")
10 3
63.7
50.9
86.0
100
Unk.
Unk:
IMH- 1090
10-3
100
87.3
99.6
Unik
Unk.
IMff-rewet- 1000
10-3
100
64.0
87.1
100
Unk.
Unk.
QRS
10-3
100
0.0
64.1
8:
1.3
86.6
1: 0.2
100
1:
0.0
0.01
0.01
Table 3: Additional results comparing MC sampling methods on the task of obtaining samples from an EBM with a point-wise constraint to include the word "amazing" in the sequence. We do not compute perplexity for IMH and RWMH without reset it does not yield i.i.d. samples. As noted, TVD and KL for MCMC methods are unknown (i.e. we have no way of estimating them). Where available show mean + one standard deviation over 10 runs
distribution (DPG, as used in QRS experiments). Per step of the MCMC chain this algorithm is roughly similar in cost to our IMH algorithm. A single step of RWMH requires a pass through BERT (for insert or replace) and a pass through GPT-2 (for scoring under the EBM), while a single step of IMH requires sampling a sequence from DPG (a highly parallelizable operation, in practice we take many samples once and pre-store them on disk) and pass through GPT-2 as well (for scoring under the EBM). Therefore, we use the same definition of acceptance rate as in the IMH experiments in Appendix
E. Like for IMH, we also provide two versions of RWMH: one in which we do thinning to reduce autocorrelations (RWMH) and one in which we reset the chain (RWMH-reset) after a number of steps (and set the seed again from the DPG proposal). The value of the thinning parameter and the number of steps after which the chain is reset determines the AR of the algorithm. In order to inform the local proposal distribution of the EBM, we also investigate mixing BERT with Dirac 5 on a particular word (e.g. "amazing" or "Wikileakss") for a pointwise constraint. We compare each sampler (QRS, IMH, IMH-reset, RWMH. RWMH-reset) in terms of moment matching results, perplexity, Self-BLEU (Zhu et al.) 2018), and finally TVD and KI. where possible (that is to say, for QRS only, as we stress below).
We run on both pointwise constraint (generating from GPT-2 using the word "amazing") and mixed distributional constraint (debiasing scientist biographies, see Section 3.2.2) to compare the samplers. We run all samplers (QRS, IMH, IMH-reset, RWMH, RWMH-reset) both at 10-1 and 10 acceptance rate. We use Algorithm 2 for QRS to find a 3 value that approximately satisfies the target acceptance rate. For IMH and RWMH we have fixed burn-in period of 1,000 steps and define the acceptance rate as the amount of thinning that is done: e.g. keep only every 10p sample for an acceptance of 10-1, For IMH-reset and RWMH-resse we define the acceptance rate by the rate at
23

---

Under review as a conference paper at ICLR 2022
which we reset the chain (and re-seed from the global proposal), e.g. rum chain of length 1, 1,000 and only keep the last sample for an acceptance rate of 10-3. We also report performance on the global proposal (DPG). We show results on collecting 1,000 samples of each in Tables 2 and gl
We find that IMH, IMH-reset and QRS perform considerably better than RWMH and RWMH-rese at all acceptance rate levels. RWMH and RWMH-reset seem to have trouble achieving good constraint satisfaction consistently. We currently report numbers on a single run of the sampler, which might suffer from poor seed sampled from DPG. In the final version we shall include mean and variance results over multiple runs.
QRS, IMH and IMH-reset meet the imposed constraint of only generating sequences containing the term "amazing" and, at lower acceptance rate, also the constraints of generating debiased scientist biographies roughly. At 10 acceptance rate IMH suffers from high autocorrelation among the samples due to repetitions (as seen from the percentage of unique sequences). Also at a 10-3 acceptance rate IMH and IMH-reset both seem to have slightly less diversity than QRS, but all in all do achieve similar self-BLEU QRS and produce roughly 1,000 unique sequences. Perplexity is also similar for QRS and IMH-reset (we do not compute perplexity for IMH as the computation requires i.i.d. samples), slightly in favor of QRS in the mixed distributional constraint. We found similar results before in Appendix E.2 In conclusion, QRS and IMH-reset have an advantage over IMH in that they provide i..d. samples and have higher diversity at high acceptance rates. Both versions of IMH and QRS perform on par in terms of perplexity and self-BLEU. QRS, however, has large advantage in that it allows compute actual divergence from the target distribution (TVD and KL), something simply not available to MCMC methods 14
H.1 INFORMING THE LOCAL PROPOSAL DISTRIBUTION
We attempt to inform the local proposal distribution without introducing excessive additional com- putation by proposing a simple mixture model for the insert and replace operations. With small probability, that we tune as a hyperparameter, the proposal distribution proposes to insert or replace a token with the token "amazing" (additionally to the probability of that occurring under BERT alone). We show some preliminary results of this on RWMH and RWMH-reset in Table 3
Our preliminary results do generally increase the constraint satisfaction of the resulting sampler. However. in the case of RWMH it leads to a catastrophic failure mode: where in the burn-in period an "amazing" was inserted somewhere in the sequence, and the chain got stuck that local optimum for all 1,000 samples we collected (including thinning steps). The results on RWMH-reset look more promising, increasing constraint satisfaction only slightly, but steadily improving perplexity. We will perform more experiments on this for the camera-ready version and include some variance estimates over different runs of the algorithm.
I OBSERVATIONS ON GWG AND OTHER GRADIENT-BASED TECHNIQUES FOR DISCRETE SPACES
Gibbs with Gradients (GwG) (Grathwohl al. 2021 is a recent promising technique for importing the effective gradient techniques of continuous EBMs (as in vision) to discrete EBMs. Grathwohl et al. (202T) start by observing that basic techniques for discrete distributions such as RWMH (Random Walk Metropolis Hastings) (i) require meticulous customization of the local proposal to lead to reasonable results and (ii) are unable to exploit differentiability over sample-space densities, which are so crucial for efficient MCMC sampling from EBMs in continuous domains. The method they propose instead addresses those situations (which they argue are many) where the discrete EBM can be seen projection of a differentiable function over underlying continuous space, which
We note that our perplexity numbers slightly differ in magnitude compared to Appendix E.2 due to a slight change in tokenization. We will update this in the final version to be consistent throughout the appendices. "Note that constraint satisfaction plus perplexity estimates do provide good estimate of distributional divergence (TVD or KL) from p. This true for both pointwise and distributional constraints. For instance, with the female-science experiment, if a sampler w generates only two fluent sentences each with probability 0.5, both about science, and one of the two with female mention, then constraint satisfaction is perfect and perplexity (i.e. fluency) is very good, hut divergence from can be terrible. Self-BLEUU is proxy diversity that improves the evaluation hat, but still does allow to estimate divergence.
24

---

Under review as a conference paper at ICLR 2022
8
le-12
3.1c3
4.4e4
6.4e5
9.3e6
AR
1.00 4: 0.00
1.de-1 3.4e-4 4e-4
1.6e-2 = Be-5
1.3e-3 1.2c-5
9.2c-5
1
TVD(2. P8)
0.70 4: 0.00
0.38 = 0.01
0.14 = 0.01
0.02 + 0.01
1.6c-6
5. -
(p.(P.Pp) pg)
2.0c-6
Table Means and standard deviation of importance sampling estimates of acceptance rate, TVD with the target distribution and KL-divergence to the target distribution for various 3 on debiasing scientist biographies (see Section 3.2.2). We perform 10 runs using 1, 1,000,000 samples each to compute the means and standard deviations. Values of B are chosen within the range used for our experiments as reported in Table [
leads them perform sampling in the discrete space, but with novel "locally informed proposal" (Zanella 2017) that exploits gradients in the underlying continuous space in order to avoid explicitly computing the energy of each point in the "local neighborhood" of x, a very costly operation.
Grathwohl et al. 2021) |) do not experiment with textual data, and we believe that while applying their technique to some text generation EBMs similar those of our current experiments would be possible (see just below), this would be an ambitious research project on its own, beyond the scope of the current paper.
A possible GwG approach for P(x), where = 21, In is text to be generated, and where P(x) could be computed as a differentiable function of E ...... ens where e, the embedding of x,, could work as follows, adapting to text generation the last line ("Deep EBM"" of Table in Grath wohl et al. (021). We would first pick some position m, then compute Ve., P(e1, Cy Cx) would approximate P(el...., 6y en) using the previous gradient 15 a much less costly operation than computing
Then for each x' 21..... T .... In differing from only at position
P(e1...., cm ..... e..) from scratch (this is the gist of GwG). In principle such procedure could be done for any P(z) = a(x)b(x)). where a is a neural model (hence in principle differentiable over the word embeddings, e.g. for autoregressive model), and b is differentiable over these embeddings. As mentioned above, this would be a whole project on its own, but note that the requirement that b be differentiable could make the approach tricky apply arbitrary binary predicate, is provided as a black box, etc.
cases such when b computes
Grathwohl al. (2021 contrast their approach other recent gradient-based techniques, such as "continuous relaxation". that first map discrete x's to continuous representations, perform gradient- based MCMC there (e.g. with HMC, SGLD, etc.) and then map back to the discrete space (while GwG performs MCMC in the discrete space). They argue that MCMC sampling in the continuous relaxation does not directly exploit the underlying discrete structure the space and therefore that sampling performance in the relaxed space may not be indicative of sampling performance in the discrete space. We are not aware of such techniques that we could directly apply to our text generation tasks, and did not attempt experiments in this space.
J IMPORTANCE SAMPLING AND VARIANCE
We perform many importance sampling estimates in this work to estimate quantities such ac- ceptance rate, and TVD and KL to the target distribution. We report variance estimates for the experiments debiasing scientist biographies (Section 3.2.2) in Table 4 We collect 10 times the number samples used to generate our plots (1 million) and report mean = one standard deviation for 3 values within the range used within experiments (also see Table T). We find estimates to be accurate within reasonable variance.
15 "se(e,, ... en.
e en) z Ple Cm: ... (n) (Vem Ple Cm: C.. (n) em)).
25


Reviews:
[{"review_id": "ymiDt5M8KMO", "reviewer": "Reviewer_RQGP", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "## Weaknesses\n\n1 - 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.\n\n2- 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.\n\n3 - Uninteresting Section 2.2:\n    - Equation 1 needs a parenthesis to avoid confusion\n    - 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)\n    - Equation 4 is obvious since using the apropriate upper bound gives you rejection sampling which is a perfect sampling algorithm.\n\n4 - 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.\n\n5 - 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:\n    - They're not unbiased estimators since $Z$ is not known and needs to be estimated, this point is not explicitly stated.\n    - It is assumed that the normalizing constant of $q$ is known, which is not always the case.\n    - They rely on importance sampling, which begs question 1.\n", "summary_of_the_paper": "The authors propose a method called Quasi Rejection Sampling (`QRS`) which is a relaxation of Rejetion Sampling (`RS`).\nThe 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.", "summary_of_the_review": "The reviewer strongly recommends rejection since the paper lacks both significance and novelty.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "ohGu5shAh3F", "reviewer": "Reviewer_rWrS", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The proposed method is very simple and easy to use in practice. However I have the below concerns.\n\n1.\tThe 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. \n\n2.\tGiven 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. \n\n3.\tAlgorithm 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. \n\n", "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.\n", "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.  ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "OneLxjUeZy8", "reviewer": "Reviewer_d6gm", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "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.\n\nAs 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?).\n\nAnother 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. \n\nWeaknesses:\n\nThe 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. \n\nI 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).\n\nThe 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. \n\nI 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. \n\nBesides 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? \n\n---------Post discussion period------------\nI 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. \n", "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). \n\nThis 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. \n\nExact 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. \n\nThe 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. \n\nThe 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).\n", "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. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

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