An approximate sampler for energy-based models with divergence diagnostics
Authors: Bryan Eikema
Germán Kruszewski
Christopher R Dance
Hady Elsahar
Marc Dymetman
Venue: Accepted by TMLR ()

Abstract: Energy-based models (EBMs) allow flexible specifications of probability distributions. However, sampling from EBMs is non-trivial, usually requiring approximate techniques such as Markov chain Monte Carlo (MCMC). A major downside of MCMC sampling is that it is often impossible to compute the divergence of the sampling distribution from the target distribution: therefore, the quality of the samples cannot be guaranteed. Here, we introduce quasi-rejection sampling (QRS), a simple extension of rejection sampling that performs approximate sampling, but, crucially, does provide divergence diagnostics (in terms of f-divergences, such as KL divergence and total variation distance). We apply QRS to sampling from discrete EBMs over text for controlled generation. We show that we can sample from such EBMs with arbitrary precision in exchange for sampling efficiency and quantify the trade-off between the two by means of the aforementioned diagnostics. 


Published in Transactions on Machine Learning Research (11/2022)
An approximate sampler for energy-based models with di- vergence diagnostics
Bryan Eikema" University of Amsterdam
Leikema@@vo.nl
Germán Kruzsewski NAVER Labs Europe
Christopher Dance
christopher. htw.:peeee..deeeeeeeeerraaaaaaoo
NAVER Labs Europe
Hady Elsahar Meta AI
hadgelsaherr@metta.cmm
Marc Dymetman'
Independent researcher
Reviewed on OpenReview: https: opwpr/vveeereeeeee.. net/ forum? VW4IrCOnOM
Abstract
Energy-based models (EBMs) allow flexible specifications of probability distributions. How- ever, sampling from EBMs is non-trivial, usually requiring approximate techniques such as Markov chain Monte Carlo (MCMC). major downside of MCMC sampling that it often impossible to compute the divergence of the sampling distribution from the target distribution:
therefore, the quality of the samples cannot be guaranteed. Here, intro- duce quasi-rejection sampling (QRS), simple extension of rejection sampling that performs approximate sampling, but, crucially, does provide divergence diagnostics (in terms of f- divergences, such as KL, divergence and lotal variation distance). We apply QRS to sampling from discrete EBMs over text for controlled generation. We show that we can sample from such EBMs with arbitrary precision exchange for sampling efficiency and quantify the trade-off between the two by means of the aforementioned diagnosties
1 Introduction
Generating samples from probabilistic model is fundamental part of many machine learning tasks. Sometimes, the relation between the probabilistic model and the associated generative process is direct: for instance, in language modelling, autoregressive model can both generate sequence by ancestral sampling and compute its probability. However, the simplicity of sampling in such models often comes at the cost of expressivity. A family of models with much greater represcntational freedom is the family of eneryy- based models (EBMs) (LeCun et al.) 2006). Such models map elements x of the sample space to real-valued "energies" " E(x), or, equivalently, to non-negative scores P(z) = -E(x) which can be seen as unnormalized probability distributions. However, EBMs can be difficult sample from.
Work done during internship at NAVER Labs Europe.
Work done at NAVER Labs Europe. 'To the code for this work (scheduled for release in Jan. 2023) and for short introductory video, please go https://disco.eet www.:iisccoeurr...eeeeeeee www.eee..eeerlllee.e.e wtt.aaa......oseeeeeeeeeeeeeeeee com/QRS)

---

Published in Transactions on Machine Learning Research (11/2022)
In this paper, we address the problem of sampling from EBMs (as in "obtaining samples" and not just computing expectations, which is an-
spadll
other popular but different problem), with a particular focus on discrete spaces of sequences over a finite vocabulary, and study applications to text generation. A popular approach to sampling from complex, unnor- malized, probability distributions, such as EBMs, consists applying Markov chain Monte Carlo (MCMC) techniques, which are guaranteed to converge to the target distribution in the limit, under mild regularity conditions (Robert and Casella 2004). In practice, however, the length of the Markov chain is finite, in which case often only approzimate samples are obtained. In order to know whether the samples are representative of the target distribution, ideally, one should quantify the divergence of the MCMC sampling distribution from the target distribution in terms of well-established metrics (e.g. total variation distance or KL divergence). Unfortunately, evaluating convergence is often challenging (Cowles and
reject
pccept
Pg
Figure 1: Quasi-rejection sam- pling (QRS) approximates a lar- get distribution P with a Iruncated distribution P3 (the blue shaded area). This QRS distribution is de- fined in terms of a global proposal distribution q and a scalar param- eter & that controls the quality of the approximation.
Carlin 1996 Roy 2020), especially if one makes no assumptions about the sample space. For instance, popp ular convergence assessments such as effective sample size (ESS) |Gamerman and Lopes 2006 or R (Gelman and Rubin 1992 Vehtari et al.) 2021) require Fuclidean structure for computing variances and correlations of real-vatued variables (or vectors in multivariate generalizations; Vats et al. 2019 Brooks and Gelman 1998), which are not intrinsically defined on discrete spaces only endowed with a probabilistic structure. For this reason, prior work on sampling from discrete sequence spaces often relies on proxy metrics (such as perplexity, diversity metrics and constraint satisfaction). Such proxies are typically insufficient to assess how representative the samples are of the target distribution, and can be misleading.
In this paper, we introduce a simple approximate sampling technique, quasi-rejection sampling (QRS), which provides explicit estimates of the divergence from the target distribution for the general class of f- divergences, which includes the total variation distance (TVD), forward and reverse KL, Jensen-Shannon, and =diiieegeneee (Polyanskiy) 2019). This is possible because QRS associates explicit probability scores with samples: a property generally lacking in MCMC samplers. One may use such divergence estimates to tune the sampler, controlling the tradc-off between efficiency (acceptance rate) and quality (divergence).
QRS is relaxation of rejection sampling that obtains approximate samples from a target distribution (see Fig. D This requires access to a global proposal distribution that, ideally, produces samples close to the target distribution. Traditionally, MCMC mothods work with local proposals (conditional distributions defined around a given point, for instance a distribution defined by performing a set of local edits), since high-quality global proposals have been hard to construct. Fortunately, with the advent of powerful neural network training techniques, this situation is rapidly changing and obtaining powerful global proposals is now possible as show in our experiments.
We demonstrate the effectiveness of QRS on controlled text generation. Large pre-trained language models are becoming increasingly useful general purpose tools and generation is typically accomplished by sampling [Nadeem et al. 2020). Controlling the distribution of these language models to accommodate human prefer- ences can be difficult, but EBMs are a promising way to achieve this (Khalifa et al. 2021). However, sampling from EBMs defined over a discrete sequence space is non-trivial, making a challenging task to benchmark QRS. In this paper, we experiment with EBMs resulting from restricting a GPT-2 language model (Radford et al. 2019 in some way: either the model is restricted to only generate sequences containing a specific term; or the model is restricted to have certain moments, for example debiasing a distribution over biographies to consist of 50% female biographies. We explore a variety of ways to construct proposal distributions for QRS. In particular, we explore prompting a pre-trained language model, as well as training an autoregressive model to approximate the EBM (Khalifa et al. 2021). In App. B we also experiment with a paraphrase generation task in which we use off-the-shelf machine translation models as conditional proposal distributions. Results show that we are able to approximate the target distributions to any desired level in exchange for sampling efficiency. Finally, we include experimental comparisons with both local (random-walk) and global MCMC methods, showing that QRS performs comparably or better, while providing stronger guarantees
We will release the code for our experiments upon publication.
2

---

Published in Transactions on Machine Learning Research (11/2022)
We summarize main contributions follows:
We introduce QRS, a relaxation of rejection sampling that produces approximate samples and, contrast most existing approximate sampling techniques, provides estimates of sampling quality in the form of f f-divergences.
We prove two theorems about QRS: one provides upper bound on the TVD between the target and QRS distributions; the second shows the f-divergence is monotonic function of QRS's tuning parameter B. We also exploit the sata-processing inequality to at least provide a lower bound on the divergence of MCMC samplers and compare to the precise divergence estimate for QRS.
We show experiments on text generation how QRS able to approximate the target EBMs to any desired level of accuracy in exchange for sampling efficiency.
We show how construct efficient global proposal distributions for text gencration making use of recent advances in large language models: prompting, training objectives for approximating EBMs, and the widespread availability of pre-trained sequence models.
We compare QRS with both local and global variants of Metropolis Haggliss-astinss,, and show that QRS outperforms local variants, while performing par with global variants, according to proxy metrics. We show, however, how proxy metrics can fail to reliably estimate the divergence from the target EBM, a quantity typically not available to MCMC.
2 Formal Approach
Our general problem is the following. We consider discrete (i.e. countable) sample space X. We are given nonnegative real function such as EBM - P(x) over X, such that the partition function Z = Emex P(z) is strictly positive and finite. We can then associate with P normalized probability distribution p(z) = P(x)/Z. Our goal is to define a "sampler" w, that is a generator of elements from X, such that w produces a sample x with a probability w(x) as close as possible to our larget p(x), in terms of distance measures such as KT. divergence (KL w) and total variation distance TVD(p, and more generally the large family of f-divergences (Liese and Vajdal 2006), which we discuss later. To help us achieve this goal, we assume that have at our disposal global proposal distribution ((x) such that i) we effectively compute ((r)) (i.e. score æ) for any x E X, ii) we can efficiently generate samples from q, and iillp is absolutely continuous relative to (denoted by p < q), in other words the support of includes the support of i.e. p(z) > 0 ((x) > 0.
2.1
Quasi-rejection sampling (QRS)
Our proposed sampling method, QRS, is given as Algorithm !
Algorithm 1 QRS
Require: Target P, proposal 4, parameter B, number of required samples N 0
(0< 8 oo)
3: while n < N do
4: x~
5: Fx + min (1, ((x))()g(x))
{Acceptance prob. (U.. : unif. dist. over [0, 1]}
u~ u~Upa
if u Ta then
output
++++1
10: end if
11: end while
In addition P and q, QRS requires the input of a finite positive number B. For a given B, the QRS sampler, which will denote by ps, produces an independent and identically distributed (i.i.d.) sequence of
3

---

Published in Transactions on Machine Learning Research (11/2022)
values (line 8), with a probability mass function that we denote by ps(x) p If /3 is global upper bound on P(x)/g(z), then the behaviour of the QRS algorithm is identical of that of the classical rejection sampling (RS) algorithm (voo Neumann 1963). However, QRS does not require 3 to be an upper bound, and the acceptance probability Tz in line is an extension of that used in RS to situations where P(x) > Bq(x). In such situations the sample x is always accepled at line 7.
QRS has crucial practical advantages over RS. It is well known that for rejection sampling, with 3 a finite global upper bound, have py = p: in other words, rejection sampling is perfect sampler for p (Robert and Casella, 2004). This is of course major advantage, however it comes with serious theoretical and practical limitations: there may not exist such finite upper bound, and even if one exists, its value may not be known. Furthermore, even if such a bound could be found, the resulting sampler could be extremely inefficient: the "acceptance rate" of rejection sampling is proportional to 1/3, which can be very small. By relaxing the requirement that & is a global upper bound, QRS sacrifices the identity between Ps and p. However, QRS becomes much more broadly applicable, and crucially, allows an explicit trado-off between the sampling efficiency of ps and its qualily.
2.2 Explicit f-divergence diagnostics for QRS
Let / (o) - IR be convex function such that f(1) = 0, let ʃ(0) = limego [(1), and let pi and p2 be probability distributions over discrete sample space X. The f-divergence of pı from p2 is defined as
pi (1)) p2(x))
Dy(p1,p2) = EaIpal S
+ (0o) p1 = -),
(1)
where Pi = =) denotes the pr Pa-mass of the set fo E X p2(2) = 0}, and where f((o)) = lim f(1/t). Here the convention is that if pı (p2 = 0) = O, the product f'(oo) pi (p = 0) is taken to be equal to O, whatever the (possibly infinite) value of ('()) (Polyanskiy 2019
Unless mentioned otherwise, will always assume in the rest of the paper that p1 < p2, in other words that pı (p2 0) 0, so that the previous definition simplifies to
(1())) p2(x))
Dy(pi,p2) = Ex I
(2)
The family of f-divergences enjoys a number remarkable properties 5 and contains many standard hods
for measuring differences between probability distributions (Polyanskiy) 2019 Liese and Vajda 2006). In
our experiments, we mainly work with the total variation distance Pp Σxex (PT(x) p2(2))/2.
obtained with f(x) = |1 - xl/2, and KL divergence (KI.PI,P2) = =xrex (z(x) log (1(a) llgg.. x.
pz(a) which has f(x) =
Explicit form for Pa and f-divergence estimation Let Ps(x) = min(P(x), 3g(x)), (g(()),),,g())), and let Zg = EnEx Pa(x) be the associated partition function. Also, define the acceptance rate AR, of the QRS sampler Pg as the proportion of samples from q, in line 4 of the algorithm, that are accepted on line 7, a proportion that provides a measure of the efficiency of the algorithm. We then have the following properties, proved in App. D
(a(x) = min 6())) AR,- Razg min(1, P()))(8((=)) 73/33.
(3)
Eq. 3 provides an explicit form for Pa as the normalized distribution associated with P3, while Eq. 4 that the acceptance rate is a nonincreasing function of parameter 3.
shows
Thhis involves some abuse of notation, as Pa refers to both sampler and distribution that "scores" elements of X. 'Both f(0) = lim, f(t) and f'(x)) =b2 limeyo f(1/t) be shown to exist for convex function with domain (0, oo), if allow these limits to take the value +oo (Hiriant- [Hirtart-Urruty and Lemaréchal 1996).
IIn particular Dy(p1. (y(11.p2 p2) 2 0, and, for ʃ strictly convex 7 1, (y(P1.P)) iff p1 = 72- Also, we have Dp(p1 (2). = (y P1), where [(0) = t f(1/t) is another convex function with f(1) = 0 known as the perspective of I (Remark 7.2
Polyanskly 2019).
4

---

Published in Transactions on Machine Learning Research (11/2022)
This explicit form given in Eq. enables to directly compute empirical estimates of the f-divergence of the target from ps- It is easy to see that, under our assumption at the beginning of the section that < q. we have both & Pa and pø < p and in particular we can write
p(z) (s(x)
= Exwpal
(5)
Crucially, to estimate this quantity given collection of samples from pe we need to compute (or at least approximate) the two values p(x) and (a( for any given And this is something that we do with QRS thanks to the explicit form of ps of Eq. B and given that we can estimate the partition functions Z and Z/
see Eqs. G and below.
The contrast here with a typical Markov chain based sampler w is striking: it usually unfeasible to estimate the probability w(x) for a given (even one sampled from w): do so, one might estimate the chain's transition matrix or kernel, and repeatedly multiply by it, but this matrix is usually huge, or even infinite. In other words, ullike QRS, these samplers are not "scorers", making it impractical to estimate f-divergences (p) as in Eq.
Divergence estimates via importance sampling Computing divergences as described above requires obtaining a different set of samples for every value of B. More conveniently, one can use a single collection (ai,...,, m of i.i.d. draws from q and use importance sampling (IS) (Owen) 2013) to compute such quan- tities. Let be a real-valued function on X, such that Ezex h(z) is well defined (it may be infinite) and
let ((x) = + h(z) 0. Then can then rewrite Σxex h(x) ExeX:g(x)>0 q(x) h(z) A(m:) N-1 E q(z,))
h(a)
- q(z)
q(a)
to compute:
N P(æ+)
N Po(x:)
Z -~ N~ Σ
Zg N
(6)
(33;)
g(zg)
1=1
Po(a.)
Zg P(x,)
Dy(p.po) N
(7)
Zzg(z;)
Z P3(xx))
In Eq. 7 we exploit the fact that Ps(x) = min()))))
is known explicitly.
More details are provided in App. D about how Eqq 7 specialies in the case of TVD and KL divergences, the measures we use in our experiments. There, we also describe the IS formulas we use for estimating the acceptance rate AR3, the expected value h(r)) of a function h expressing a constraint, as well as the probability p(As) (see next paragraph).
Remark about partition function estimates As the sample mean is an unbiased estimator of the mcan, the estimates Eq. G are unbiasod. These estimates converge (almost surcly) to and Z3 for N 00, consequence of the strong law of large numbers Tao 2008), whether or not the random variables P(x) (RVs) q(e) and Pa(ar) have finite variances. However, in order to provide guarantees about the accuracy of these estimates- e.g. in terms of confidence bounds- - one would need to estimate these variances, or their (I + a) momennt for some a > 0 as discussed by Lugosi and Mendelson (2019) p. 8). A practical approach consists in providing empirical variance estimates based on the same N samples, and this is what we will do in several experiments (see Sec. 3). comforting us about the practical accuracy of our estimates of Z and Zz. However, theory, the empirical variance estimates could themselves be wrong, resulting in an estimation circularity. The only way to avoid this circularity, that we are aware of, consists in cases where the RVs P(a)
{())
q(z) can be bounded a priori, in which cases the variances of these RVs can also be formally bounded using Popoviciu's inequality (Popoviciu 1935) or, more aggressively, confidence intervals produced through Hoeffding's inequality (Hoeffding 1994), so that confidence bounds for Z and Zg can be obtained. Interestingly, the random variable Pate) min(((=)//(())) B) < 3 appearing in Z is bounded by construction, so that one can always provide formal guarantees about the Z estimate. By contrast, in the
q(z) and Pa(x)
((x)
P(z) is known, such proposals can be case of Z, while one can often find proposals q for which bound q(x)
5

---

Published in Transactions on Machine Learning Research (11/2022)
unacceptably inefficient, while other proposals, closer to the target, are much more efficient in practice, but eschew strict formal guarantees. We provide details and compute such provable bounds on Z for some of the EBMs that we consider in our experiments in App.
2.3 Two theorems about QRS: bounding and monotonicity
TVD bounds QRS We first provide simple upper bound on the TVD between the sampling and largel distributions.
Let A3 = {x E X P(r)/q(x)> > }} be the set of "violators" of the 3 bound. It is intuitive that the "fewer" violators there are, the closcr pg is to the target p. The following theorem, proven in App. D makes this statement precise, terms of the actual p-mass of the violators:
Theorem 2.1. TVD(p, ps) S p(A)).
As a corollary of this, observing that limg-x p(As) + O, one sees that pa converges to for 3 + 00
/-divergence monotonicity of QRS While the previous upper bound is specific to TVD, QRS enjoys an attractive monotonicity property for all f-divergences. We provide two proofs of this result. The first proof, given in App. D.3, relies on fundamental "majorization" properties of convex functions, does not involve the differentiation of the divergence, and provides some graphical intuition in terms of gaps associated with Jensen's inequality. The second proof given in App. D.4] replaces large part of the first proof by much shorter valculus-based derivation that exploits extension of the fundamental theorem of calculus not requiring differentiability but only absolute continuity.
Theorem 2.2. Let 0 < 8 00. Then Dy(p,p>) S Dy(p.ps).
Theorem 2.2 guarantees that increasing the value of parameter B never increases the f-divergence of the target distribution from the QRS distribution. Moreover, in the light of footnote 5 increasing 3 never increases the divergence of the QRS distribution from the larget distribution.
3 Experiments
3.1 Approximating Poisson distribution and the quality-efficiency trade-off
To demonstrate the usage of QRS start with toy setting using two Poissons. The goal is to sample from larget Poisson distribution p with rate Ap 11 using samples from a proposal Pois- son distribution q with rate by = 10. Rejection sampling is not possible in this setting as the ratio p(=)/g(x)= = (e (0-1111/xx!))) 100 = e 1.1 can take arbitrarily large values when x increases, i.c. the ratio is unbounded. However, it is possible to use QRS here.
We perform ten independent experiments in which we sample 10 elements from q that we use to compute the quality of the approximation by estimating: TVD(p, p3) and its upper bound p(As). ) (See App. C.1 for additional results on (KL(p.Ps) In all cases, we use 8 values in the interval [0.5. Furthermore,
compute the sampler's efficiency by estimating the acceptance rale (AR) for each value of B (Eq. As
described previously and detailed in App.
D we compute estimates for all these metrics using importance
sampling. Results are displayed in Fig. 2 As shown, using higher values of B improves the TVD, oven though
6 In principle, it is possible construct examples where Z = Ex=q q(2) is finite while the variance Varz P(x)
P(x)
is infinite,
see App. g In practice, for text generation, we have not observed such situations. Note that all the EBMs of Sec. 3 are of the form P(æ) = a(x) b(2), with
autoregressive model and b(æ) upper-bounded; therefore if one takes q then P(x)/q(a) is bounded so the variance is bounded, although the proposal a can be incfficient.
could provide guarantees about the asymptotic speed of convergence to p. When the support of P is a finite set, the answer is easy and positive: there exists value å such that 3 >> Bg implies that ps is identical Supp(P))- However, when the support of P is an infinite set, prove in A the following negative result (Theorem) K. for arbitrarily slowly docreasing function g(8) that converges to 0, there exists some proposal such that TVD(p, ps) converges even more slowly than g(5). In other words, if one plays "adversarially", it always possible design arbitrarily bad proposal terms asymptatic convergence rate. We thank one the reviewers for suggesting this proof
"One reviewer asked whether
to p, by simply laking & max( max(((x))/(gg (P(z)//(x)
6

---

Published in Transactions on Machine Learning Research (11/2022)
10-
1 ((AAA)
1.
16.
1- PalA)
TVD Dy)
011
TVD Ps)
TVD 4)
TVD
accoptancc nd52
03
1VD
07
2.-
Est. TVD True TWD
0.004
0.002
0.4
0.4-
0.000
-0.002
-0.004
0.-
5.0-
accoptarice raCe
number of samples
(a)
(b)
Figure 2: (a) Estimation of sampling quality as (VD ps), efficiency (acceptance rate), and the tradc-off between them for a QRS sampler when using a proposal g = Poisson(A 10) to approximate p = Poisson(A = 11) computed in 10 independent experiments over 10 samples. (b) Differences between estimated TVD ps) and their true values for B = computed 1000 times for each different number of samples. The blue line is the mean and shaded areas represent standard deviation.
this comes at the cost of lower acceptance rate. In particular, with B 3.5, the TVD is tiny (N 10 10=²). yet the acceptance rate is moderate (0.3, i.c. 30% of proposal samples are accepted). Notably, we can case the visualization of the trade-off between quality and efficiency by reparametrizing the divergence metrics in terms of the acceptance rate (last panel of Fig. 2a). A procedure to map acceptance rates to corresponding B is outlined in App. F We use this concise reparameterized representation to plot subsequent results.
Empirical estimates of the divergence diagnosties In the previous and following experiments, we use a sufficiently large sample size to obtain accurate estimates of the divergence diagnostics. However, it is reasonable to wonder about the bias and variance of these estimators for smaller sample sizes. While it is not possible to provide definite answer for all EBMs (cf. Sec. 2.2). we can investigate this question by exploiting the fact that can compute with great precision Dy when both p and q are Poisson distributions (see App. H for a derivation). We compare this approximation to the true value with the estimators proposed in Sec. using sample sizes n E {10?..... } and repeating the process 1000 times. Results for TVD are shown on Fig. 2b (see App. C.1 for results on KL). As it can be seen, there is some slight variance when only 100 samples are used for the estimation, and quickly improves as more samples are used. In contrast, the estimation bias is tiny.
3.2 Generation with distributional control
The following experiments focus the task of generation with distributional control, introduced by Khalifa et al. (2021), task that requires sampling from an EBM over sequences of discrete tokens, making it an ideal test bed for QRS. Given a language model a(z), the goal of this task is to sample from model p(z) that, on the one hand, constrains the moments of a vector of n pre-defined features Φ(x) to match some desired value ı (i.e. Ex=) = p), while on the other hand minimizing DKL(p, a), a generalized version (Ssiszar 1975 Kullback and Khairat, 1966) of the maximum entropy approach (Jaynes) 1957 Rosenfeld 1996). For example, one might want to debias a language model trainod on a corpus of biographics produce biographies only of scientists, 50% of which should be female. Then (1(x)) and Φ2(x)) would be binary classifiers assessing whether sentence speaks about scientist or female respectively, and the desired moments would be set to f [1. 0.5).
The authors show that p can be expressed as an unnormalized EBM P(x) = a(x)b(x), and describe two choices of b(x). On the one hand, they consider pointwise constraints, where μ E (0,1) 1)". For instance, if there is a single binary feature for which we would like that Vx : Φ(z) = 1, then takes the form b(x:) = ((x). Otherwise, in the case of distributional constraints in which j E R", they show that there is a vector À E RM such that b(x) exp(A <0x)) and p(x) a(x))(xx) fulfills the requirements of moment. matching and minimal
7

---

Published in Transactions on Machine Learning Research (11/2022)
1.0
prompt name
prompt
DPG
GPT-2 small
jeoparey
simple
Wikileaks.
knowledge
multiple
Wikileaks, Wikileaks, Wikileaks,
multiple
knowledge
Here is what know about Wikileaks:
news
jeopardy
This medium was founded by Julian Assange 2006.
simple
news
Here are the latest developments on Wikilenks:
0.0
10'
10"
10
10-1
10-1
10-
10
10-1
acceptance rate
Figure 3: Comparing GPT-2, GPT-2 conditioned on various prompts, and a fine-tuned model (DPG) as proposals for generating sequences containing "Wikileaks". Disconnected points in the upper-left corner indicate TVD(p, q) for each proposal, while the curves show TVD(p, Pş) as a function of the acceptance rate. Standard deviation bootstrap estimates are shown as shaded regions for every proposal.
KL divergence from the original model. The vector À is found using self-normalized importance sampling
Owen 2013
Parshakova et al. 2019a) and stochastic optimization.
3.2.1
Proposals for a pointwise constraint
We first experiment with constraining GPT-2 small (Radford et al. 2019 using one of the pointwise con- straints (ī = 1.0) proposed Khalifa et al. (2021), namely, b(x) = 1 2 contains "Wikileakss). In order to ap- ply QRS need to find suitable proposal distribution. A possible candidate GPT-2 small itself, An ad- vantage of this proposal that we can use pure rejection sampling with an upper-bound
to obtain exact upper bound the ratio P(z)/q(z) a(=)6(=)/a(z)) b(z) s 1. In fact, for b(x) E {0, 1) this process reduces to "naively" filtering out all samples for which b(x) = 0. However, a serious disadvantage is that the acceptance rate will be given by the natural frequency of the constraint. 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:
samples from the EBM. This is because
1. First, we make use of the model proposed by Khalifa et al. autoregressive model obtained by applying the distributional policy gradient (DPG) algorithm (Par- shakova et al.] 2019b) to approximate the target EBM in a generic way. While this model is considerably better at satisfying the desired constraints, it does not match the desired distribution perfectly.
22021) which consists of a fine-tuned
2. Second, in the spirit of "in-context lcarning" (Brown et al. 2020 we propose to condition a(x) on a prompt with the aim of increasing the constraint satisfaction rate in the resulting conditional distributions. In contrast to the previous approach, this does not require the training of a new model, even though it does require the manual selection of promising prompts. We experiment with five such prompts, which we present in Fig.
Fig. 3 shows the TVD(p,)) -) as a function of acceptance rate for different samplers. In this and the following experiments, we chose a range of 3 values that yields acceptance rates in the range 100-10-5 5 (cf. Table 2 in App. A), using Algorithm 2 in App. F for this purpose. We first show the TVD(p, q) for each proposal g, at an acceptance rate of 1, before applying QRS (in the upper left corner). Then, we plot TVD(p, Ps) function of acceptance rate for each proposal distribution. We compute IS estimates of the TVD 1M samples from each proposal distribution. Variance is estimated using the bootstrap estimator (Wasserman) 2010). Note that all samples obtained from QRS satisfy the constraints perfectly, as sequences that do not satisly the constraint are always rejected, and for this reason the curves start with different acceptance rates. As expected, using GPT-2 small results in zero TVD, but comes at the cost of low efficiency, with an acceptance rate around 10-4, Using prompting, we improve the constraint satisfaction of the resulting proposal distributions and trade-off approximation quality for greater efficiency using QRS: For instance, if TVD of 0.3 can be tolerated, then some of the prompt proposals provide 10-fold higher acceptance
8

---

Published in Transactions on Machine Learning Research (11/2022)
Chandra Pradha Towni (born Fehruary 11, 1965) is a social scientist, activist, port, and author living in Portugal. She is... Enrella Carrière is & Canadian writer, translator, and philosopher specializing in the history of show business. She has covered topics such direction and psychology of television and the evolution of human...
Albert Fahn (born 1970) American scientist who focuses on algorithms for generating biomechanical data. Methods generate and construct bionechanical data...
Wyndham Radnor (born 1946) is British historian and criminologist sporialising in the subject of labour law. He has written extensively on...
1.0
(())))
50
100
0.8
TVDip, Bsl
TVDip. q)
science 96
90
0.6
40
35
target moments
0.2
Pe
0.0
10a
10-1
10
10
10
10"
10
10
10
10
10"
10
10
10
10
acceptance rate
ecceptance rate
acceptance
Figure 4: Estimation of the divergence from the EBM (TVD), and moments of features female and science in sampling debiased GPT-2 biographies talking about scientists. Variance is negligible as shown in Table 10 in App. [ We also show samples from running the QRS sampler at acceplance rate of 10-3, 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 to the graph. We color words that fire our female or science features.
rate with respect to the base GPT-2 model with no further training. 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 more extensive exploration of prompting to create proposal distributions for future work. The autoregressive policy obtained from the DPG algorithm is the best proposal distribution tested. Notably, it allows one to obtain low TVDs at higher acceptance rates than is possible by naively filtering samples from the base language model. For example, we can oblaín TVD of 0.1 at 100x the acceptance rate (see Table 10 in App. [ for more numerical results).
3.2.2 Distributional constraints
We now turn to the task, also introduced by Khalifa et al. (2021), of generating biographies of scientists while debiasing the gender distribution to contain female scientists 50% the time. For this we make use of GPT-2 Biographies (a(x)), a language model fine-tuned on Wikipedia biographies and follow the same setup as the authors to define the binary classifiers identifying sequences talking about scientists or females and infer EBM that matches the distributional constraints with minimal deviation from the original model. The frequency with which the model a(.) generates scientist biographies is 1.8%, female biographies 7.5%, and the frequency with which it generates female scientist biographies is only 0.14%. As proposal distribution, we use the DPG model that Khalifa et al. (2021) trained to approximate the EBM, which reaches a constraint satisfaction of 69.0% scientist, 27.3% female and 19.6% female scientist biographics. (Sce Table in thoir paper for examples generated by this proposal.)
As before, we obtain 1M samples from the proposal distribution to compute importance sampling estimates (detailed in App. E} of TVD(p, ps),, acceptance rate (AR₃), and the moments of the features that we wish to control. We show all metric curves function of acceptance rate of the QRS algorithm well some generation examples in Fig.
We find that both TVD(p, ps) and the upper-bound on TVD(p, Ps) steadily converge to zero as the acceptance rate decreases, meaning that we can perfectly match the target EBM in exchange for sampling efficiency. As result, at an acceptance rate of AR2 10-3 we nearly perfectly debias the original language model
/https://huggiggeee wwtp://aawl...aggeeeeeeeeeeeeeee biographies
10needer estimated by ratio lemale male pronoun counts, scientists identified by the mention of least one of multiple words associated with the profession.
9

---

Published in Transactions on Machine Learning Research (11/2022)
while exclusively generating biographies about scientists (49.5% female and 99.8% scientist biographies). We show some example generations at AR3 = 10-3 chosen manually to illustrate two male and two female biographies. Notably, we also achieve a good level of constraint satisfaction (48.4% female and 99.9% scientist biographics) and a TVD of 0.1 at AR,3 = 10-2 This is a considerable improvement in quality with respect to the proposal distribution (with a TVD of 0.7), and acceptance rate relative to directly rejecting from GPT-2 Biographies (which would result in AR I x 0.14% = 2.8 x 10-3). Two more pointwise and two more distributional constraints including additional metrics such DKL (p, and (pI a) are shown in App. A with similar results.
3.2.3 Comparison with MCMC techniques
We now compare QRS with MCMC samplers, for which we focus on the EBM for pointwise constraint restricting GPT-2 to only generating sequences containing "amazing".
Baselines We use the popular Metropolis- Hastings (MH) algorithm (etropolis et al. 1953 Hastings 1970). This algorithm works by constructing Markov chain of dependent samples, in which the next state of the chain is equal to a newly proposed sample with a certain acceptance probability, and otherwise the next state is the same as the current state. When the length n of the chain tends to infinity it can be proven (Robert and Casella 2004, Theorem 7.4), see App. J that the average of statistic on the elements of the chain converges to its expected value under the target distribution and, more importantly when focussing on sampling as we do, that the distribution of the th element of the chain converges (in total variation) to the target distribution. In practice, the chain is of finite length and only approximate samples are obtained.
Common practices are to discard the first few samples of the chain to reduce the effects of poor starting conditions (which is known as burn-in), and to only keep every 1th sample to reduce autocorrelations (which is known as thinning). We use both these heuristics in our experiments. We set a burn-in period of 1,000 steps and only keep every 1, 000 sample to attain an acceptance rate of 10-3, Note that we chose not to include the burn-in period to compute the acceptance rate of MCMC samplers, as this period is constant and does not grow with sample size. We also experiment with reset variant (-R) of the MH samplers that does away with autocorrelations among samples altogether (i.e. produces i.idd samples like QRS) by, instead of using thinning, resetting the chain after 1,000 steps and only retaining the last sample of the chain (see Robert and Casella 2004 Theorem 7.4 (ii)). This variant does not make use of a burn-in period.
We experiment with two proposal distributions for use in the MH samplers: i) the global proposal distribution used in QRS, i.e. DPG, for independent MH (IMH) (Robert and Casella, 2004, Sec. 7.4) and ii) a local proposal distribution that makes local edits to an evolving sample in the chain for random-wall MH (RWMH), As far as are aware, IMH is not commonly employed in the literature due to global proposals classically being difficult to come by. We stress that. with the advances in neural network training techniques such DPG, global proposals are more accessible than ever and we therefore include LMH as a strong baseline in our experiments. Our design of the local proposal is inspired by uses of MCMC in controlled text generation, in particular by Miao et al. (2019) and Goyal et al. (2021). The local proposal randomly performs either an insert, delete or replace operation on the token level, where insert and replace operations are performed by sampling from BERT (Devlin et al., 2019). Locations of insertions and deletions are chosen uniformly random. To inform the local proposal distribution about the target distribution, and replace operations by randomly mask-filling using BERT (99% of the time) and filling with "amazing" (1% of the time). We initialize the chain using sample from the global proposal distribution TT
implement the insert
Metrics As no f-divergence estimates are available for the MCMC samplers, we instead resort to some proxy metrics specific to controlled text generation to measure the sample quality, extracted from 10 samples over ten independent experiments. In particular we measure constraint satisfaction (% amazing), perplexity (PPI.) of our samples under GPT-2, diversity across samples with Self-BLEU-5 (Zhu et al. 2018) and percentage of unique samples (% Uniq), and finally, diversity within samples as given by the percentage of
Note that localized MCMC methods can still take advantage of good starting points, especially the reset variants. We therefore also provide our variants of RWMH with a global proposal distribution for obtaining good starting points, the same global proposal as used for QRS.
10

---

Published in Transactions on Machine Learning Research (11/2022)
Method %6maaiig PPL1
Self-BLEU-5j %Uniqt
Dist-21 TVD1"
proposal
62.9 0.4
61.7 1 0.3 85.8 1 0.1
100 T 0.0
96.1 1 0.0 0.67
RWMH
100 0.0
99.8 1 0.2
32.0 1.0:100 33.7
83.8 1 17 Unk.
RWMHH-B
100 0.1
58.7 + 3.3 87.6 + 0.4
100 + 0.0
92.0 0.3 Unk. (2 0.28 - 0.02)
IMH
100 0.0
86.9 + 0.3
0.5
96.3 0.1 Unk.
IMH-R
100 0.0
63.4
= 1.5 86.7
# 0.1
100 # 0.0
96.3 0.1 Unk. (2 0.01 + 0.01)
QRS
100 1.0
62.8 1 1.6 86.6 1 0.2
100 1 0.0
96.3 1 0.1 0.01
Table 1: Comparing with MCMC samplers for the constraint of including "amazing" in the sequence. We show mean + one standard deviation over 10 runs. All samplers are run at an acceptance rate of 10-3, "TVD is estimated on 10t independent samples, standard deviations are below 0.01. App. G contains additional results from these experiments.
distinct bigrams (Dist-2; Li et al. 2016). However, we note that these metrics can casily be cheated. An example of this is if we would mamually construct a sampler that would repeat a small set of reasonably diverse, high probability (under GPT-2) sequences that meet the target constraint. The resulting sampling distribution would not be close to the target EBM, but would score well on such proxy metrics. For QRS we do report the TVD to the target distribution, which cannot be gamed in this way! Notably, for MCMC we can also provide lower bounds on the TVD thanks to the data-processing inequality (DPT). The DPT tells us, informally, that the f-divergence of one distribution to another can only decrease by applying the same "projection" " to the two distributions. A precise formulation of this theorem is provided as Theorem 6.2 of Polyanskiy and Wu (2017), but, for our purposes, the following special case ("lumping property") proven as Lemma 4.1 of Csiszár and Shields (2004) will be sufficient:
Theorem 3.1. Let p and q be distributions over a sample space X. Let (AI...., As3 be a finite partition X. X. Then the distributions (i) = p(A,) and (i) = q(A,) over {1....,k k} satisfy Dy (p'. (p'.'')) S Dy(p.))
While it is in general unfeasible to estimate the actual divergence of two distributions p, g over a large space X based only on a moderate number of samples (as opposed to scores) from p and q (Canonne) 2020), by projecting these samples onto much smaller number k of "bins", it is possible to obtain precisc estimates of the divergence of the "histogram" p' from g', and therefore to lower bound the divergence of p from q-
We use this result to obtain lower bounds on the TVD to the target distribution of RWMH-R and IMH-R, for which we have i.i.d. samples, whereas this is not the case for RWMH and IMH. After manually inspecting a single set of 10a samples out of ten independently sampled sets to look for salient defects, we chose a binning function that classifies sample two bins according to whether it contains a newline character or not. Then, we used it to bin the samples of the remaining nine sets and compute their mean TVD to the binned target distribution to obtain lower bounds the TVD.
Results Our results are shown in Table | (with some samples shown in App. Gl. All samplers satisfy the constraint of only generating sequences containing the term "amazing". The EBM p. however, is defined to be, among all those distributions that satisfy the constraint, the one closest to the original language model a (GPT-2) under (KL a). Constraint satisfaction alone thus does not tell us how well the samplers approximale the larget EBM. For MCMC samplers we have to rely on proxy metrics. RWMH-R seems to excel in terms of perplexity while also obtaining competitive diversity metrics (Self-BLEU--, % Uniq, and Dist-2). However, we can identify large TVD between its sampling distribution and the target one, showcasing the failure of proxy metrics to reliably measure the approximation accuracy of our samplers, and
1his may raise a question: Could one design any proxy metrics that would rellably assess closeness of an MCMC sampler to the target p. given a limited number of MCMC samples? When the space X is very large, as is the case here, probably not. For an intuitive example, say p is the uniform distribution over X and w is the uniform distribution over an unknown subset Y of X, of size half that of X. The number of samples to distinguish these distributions clearly grows with the size of X if only somples from are available, but if the value of the probebility w(x) is also available then single sample x is sufficient. More formally, one might consider algorithms that compare two distributions p and ws set X of size which should 'accept' with probability 2/3 if TVD(p, w) S e1 and 'reject' with probability 2/3 if TVD(p. w) 2 62- Canonne (2020) Theorem 12.9. p. 58) shows that such algorithms require 0(1/(E1 =2)²) samples from w if the probabilities w(x) are known; whereas Canonne et /n
2202 Theorem 1.1) show that Ω
log R2 max
E1
samples are needed if these probabilities are unvailable.
11

---

Published in Transactions on Machine Learning Research (11/2022)
demonstrating the benefits of having explicit estimates of divergence measures. After qualitatively inspecting samples of both local MCMC methods (see Tables G and 7 in App. G we found many samples to contain repetitions, e.g. of punctuation marks. Also, RWMH seems to suffer from low diversity across samples (as evidenced by the high Sclf-BLEU-5 and low % Uniq scores), containing many repeated samples. On the other hand, IMH, IMH-R and QRS do not suffer from this lack of diversity. The variants of TMH and QRS seem to perform on par in terms of sample diversity, and QRS attains slightly lower perplexity than IMH-R.
An estimate of the TVD around 0.01 shows that QRS closely approximates the target EBM and shows considerably more diversity within and across samples. It might be that the IMH and IMH-R samplers would achieve similar results, but we cannot know as no divergence estimates are available. We only know that the bimming strategy failed to detect any large divergences for IMH-R. One case in which we can estimate f-divergences for IMH-R and RWMH-R variants is the Poisson example that we discussed in Section 3.1 We present a comparison between QRS and those reset variants of MH for this Poisson example Appendix C.2 finding that QRS consistently results in lower divergences for all acceptance rates (for AR,3 < 1).
4 Related Work
The vast majority of approaches to approximate sampling from complex probability distributions have been based on MCMC. However, few approaches have taken rejection sampling as their starting point. Like QRS, the method of rejection sampling chains (Tierney 1992 Chib and Greenberg, 1995, Sec. 6.1) does not require a global upper bound. This is a hybrid method that uses rejection sampling in a region satisfying a partial upper bound but combines with IMH outside of that region to produce a Markov chain that converges to the correct stationary distribution. Caffo et al. (2002) propose empirical supremum rejection sampling, an algorithm that adaptively increases the B upper bound based on the maximum observed so far, with a focus on convergence in the limit rather than approximation quality.
Closer to our work, some researchers have observed before us that a partial bound [3 leads to the probability distribution presented in Eq. 3 Rejection control (Liu et al., 1998 Liu 2004, pp. 44-45), in the context of particle filters, exploits this observation to accelerate the computation of an unbiased IS estimate of the expectation (x) in situations where computing fx) is expensive and must be done repeatodly. While the focus of that work was not to produce divergence diagnostics, interestingly, on close examination, we find that one of their proofs (Liu 2004] App. A.1, Eq. (A.4)) formulated a x--divergence between target distribution and proxy distribution similar to ps. Variational rejection sampling (Grover et al. 2018) uses a relaxation of Eq. to better approximate the variational posterior in a variational inference setting. They aim to construct a differentiable sampler that can tighten the evidence lower bound, if additional computing power is available. The focus of our work is more general: we propose a generic sampler for which we can quantify a trade-off between sampling efficiency and approximation quality and we study the properties of this sampler.
While this paper is concerned with generating samples from discrete EBMs, much research so far has been more concerned with continuous FBMs, in particular for applications in vision. Continuous EBMs have the advantage over discrete ones that it is possible to differentiate the EBM P(z) with respect to x, and not only the approximating model Ty relative to 0. This opens a range of optimized training techniques (see the survey by (onn and Kingma 2021), including Langevin and Hamiltonian dynamics (Parisi 1981 Duane et al. 1987) where the local Markov chain moves are informed by V, log P(x). While such techniques are not available for discrete EBMs, some recent efforts are trying to bridge the gap. For instance, continuous relazation techniques (Han et al. 2020 Nishimura et al. 2020; relax the original discrete space into a contimuous space, perform the sampling in this space, then map the samples back to the discrete space; while Grathwohl et al. (2021): is Zhang et al. (2022) Rhodes and Gutmann (202)) sample directly in the discrete space, but inform the local moves of the chain through gradients computed in a larger continuous space. To the best of our knowledge, while Zhang et al. (2022) do experiment with "text infilling", the ability to replace some blanks in given sentence by actual words, none of the above work has so far dircctly addressed text generation applications of the kind we have been considering here, in which the sample space is not only discrete, but composed of structured objects, namely word sequences of varying length, raising specific challenges.
12

---

Published in Transactions on Machine Learning Research (11/2022)
Monte Carlo sampling techniques popular for various NLP applications, in particular language modeling. For example, Miao et al. (2020) propose a sampler that mitigates poor estimation of probabilities due to overfitting. Deng et al. (2020) train globally normalized language models to combat negative effects of local normalization, and use a form of sampling importance resampling (Rubin 1987 to sample from the resulting EBM using an autoregressive proposal language model. Goyal et al. (2021 develop a Metropolis- Hastings algorithm to sample from masked language models. For controlled text generation Miao et al. (2019) propose & handom-walk
Miaa SetrrpooissHassting algorithm for sampling from an EBM that encodes sequence- level preferences natural text. Their proposal distribution consists of local string editing operations randomly selected words or positions. Zhang et al. (2020) improve on this approach by making use of a 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 to QRS, none of these approaches attempl to directly est istimate the divergence between the sampler and the target EBM, but rely on unreliable proxy metrics.
5 Discussion
QRS is a simpleeyyt-powerful technique: why has it not previously been promoted as a practical sampling method? One possible reason is the limited repertoire of global surrogates to complex distributions, apart from certain special cases in Euclidean domains (e.g. log-concave targets). This lack has strongly moti- vated the development of MCMC techniques which can exploit simple local proposals to compute transition probabilities between samples. This is now rapidly changing with advances in neural training, such as the impressive ability of pretrained language models to exploit simple prompts to orient their productions to- wards certain desired outcomes (but without formal guarantees); or with certain recent generic techniques, such as DPG, for fine-tuning autoregressive models towards arbitrary EBMs (but without the ability to totally reproduce them).
We believe that, given such global proposals, QRS can be a strong competitor to MCMC approaches. In particular, QRS has strong theoretical guarantees, not shared by these approaches: i) the ability to estimate, for any value of the B parameter, the divergence of the target EBM from the QRS sampler ps, for any member of the large class of f-divergences, including TVD and KL, ii) the ability to tune the sampler to attain a desired quality--fficiencc trade-off, and the intuitive nature of this luning process thanks to the monotonic relationship between parameter and the f-divergence (Theorem 2.2 iii) the existence of a simple, intuitive bound on the TVD between the QRS sampler and the target, provided by Theorem 2.1 and iv) the fact that QRS directly produces i.i.d. samples, rather than the correlated samples of typical MCMC method.
Our experimental results show that QRS achieves strong results on the task of controlled text generation, where for instance, the sampler achieves excellent debiasing of the language model for acceptance rates in the range 10-1 to 10-3, We show the versatility of the approach by applying it to different sources of global proposals: proposals over EBMs obtained by generic DPG-style fine-tuning; proposals based on handerafted prompts; and for paraphrase generation (App. B), proposals based on round-trip translation.
Finally, when comparing QRS to variants of Hetropolis-Hastingss, we find QRS outperforms the local variants (RWMH and RWMH-R) and performs on par with the global variants (TMH and IMH-R), according to the proxy metrics available for all samplers. Our results on RWMH and RWMH-R, however, show how proxy metrics can be deceiving and do not give us a full picture of the approximation accuracy of our samplers. Therefore, we stress the importance of well-founded divergence measures and, in this work, have proposed a sampler for which we can estimate these.
Acknowledgments
We would like to thank the reviewers for their thorough feedback and suggestions for improvements. Also thanks to Jos Rozen for his help with experiments, and to Stéphane Clinchant who, in discussion with one of the authors, suggested using prompting for the purpose of producing global proposals oriented towards a certain generation objective.
13

---

Published in Transactions on Machine Learning Research (11/2022)
References
Colin Bannard and Chris Callison-Burch. Paraphrasing with bilingual parallel corpora. In Proceedings of the 43rd Annual Meeting of the Association for Computational Linguisties (ACL 00), pages 597 604, Ann Arbor, Michigan, June 2005. Association for Computational Linguistics. doi: 10.3115/ 10.3115/1219840.11 1219840012199114
URL
Stephen P. Brooks and Andrew Gelman. General methods for monitoring convergence of iterative simulations. Journal of Computational and Graphical Statistics, 7(4):434 455, 1998.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, J. Kaplan, P. Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Kosse, G. Krüger, Tom Henighan, R. Child, Aditya Ramesh, D. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, E. Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, J. Clark, Christopher Berner, Sam Mc- Candlish, A. Radford, Nya. Sutskever, and Dario Amodei. Language models are few-shot learners. ari, abs/2005.141ee 14165, 2020. GPT-3.
Brian S. Caffo, James G. Booth, and A. C. Davison. Empirical supremum rejection sampling. Biometrika, 89(4):745-754, 2002.
Clément L. Canonne. A Survey on Distribution Testing: Your Data is Big. But is it Blue? Number 9 in Graduate Surveys. Theory of Computing Library, 2020. doi: wttp////o...../0...... URL http:
//www. theoryof org/ (atpac/lee//ss0///00g......
Clément L. Canomne, Ayush Jain, Gautam Kamath, and Jerry Li. The price of tolerance in distribution testing. In Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pages 573 024, 2022. URL hww.:httpp///i https://proceeddngss mlr. pwtps//v17/canooneee//o html
Djalil Chafai. Back to basics Total variation distance, 2010. URL https://djalil www.aaaenntalllga...l.oaoo
Sourav Chatterjee and Persi Diaconis. The sample size required in importance sampling. The Annals of Applied Probability, 28(2):1099-1133) 2018.
Siddhartha Chib and Edward Greenberg. Understanding the Metropolis-Hastingg algorithm. The Amer-
ican Statistician, 49 4974)3327-335, 1995. doi:
1995.10476177. URL bett://amstar
Bandfonline.co wtt.:iiee.ooooooiaaaiaaaaa aab//10b//1000 1080/00031305. 1995. 10476177
Mary Kathryn Cowles and Bradley P. Carlin. Markov chain Monte Carlo convergence diagnostics: A comparative review. Journal of the American Statistical Association, 91(44)):883 904, 1996. URL http:
//www.jstor. org/stable/2291683
I. Csiszar. I-Divergence Geometry of Probability Distributions and Minimization Problems. The Annals of Probabilily, 3(1):146 158, 1975. doi: 10. 10.121//a0p/117799661 URL https://doi https:://oo..org/10.12144. 1176996454
Imre Csiszár and Paul C. Shields. Information theory and statistics: A tutorial. Commun. Inf. Theory, 1(4): 417-528, December 2004. doi: 10.1561/01000000 URL https://www https::/www.sta.... berkeberr.ey.y.. www.eelleeeduu-biyyy.
212A/papers/cs.pp pd
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 httppp:://opeeeeeiee....o
Jacob Devlin, Ming-War Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of deep bidirec- tional transformers for language understanding, In Proceedings of the 2019 Conference of the North Amer- iean Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume (Long and Short Papers), pages 4171-4186, Minneapolis, Minnesota, June 2019. Association for Compu- tational Linguistics. doi: 10. 00.18633/v1/N99 1423. UR..tttss:/ httpts:///w/ww http://:////wwwwwbbb....mm// aclweb. hrw.lebb.rg//anhhooog////1------
14

---

Published in Transactions on Machine Learning Research (11/2022)
Simon Duane, A. D. Kennedy, Brian J. Pendleton, and Duncan Roweth. Hybrid Monte Carlo. Physics Letters B, 195 222, 1987. ISSN 0370-2693. doi: DOI: sciencedirect. www.com///cc//e http://www....eeeeeeoee/oooeeoaa htt.:///www.....///////////////.
URL http: /ww.
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), pages 889-898, Melbourne, Australia, July 2018. Association for Computational Linguistics. doi: 10.18653 1118653/11/P1810888
URL
-tw.:/logyy.og/1--1/100 1082.
Ladislas Fuchs. A new proof of inequality of Hardd--iitllwood-Polyy Mal. Tidsskr. B, 1947:53 54, 1947.
Dani Gamerman and Hedibert F. Lopes. Markoe Chain Monle Carlo: Stochaslic Simalalion for Bayesian Inference. Chapman and all/CRC, 2006.
Andrew Gelman and Donald B. Rubin. Inference from iterative simulation using multiple sequences. Stalis- tical science, pages 457-472, 1992.
Gustavo L. Gilardoni. On a Gel'fand- Bonnd-Ygllm--Peen Peres theorem for f-divergences. arXiu, abs/0911.1934, 2009.
Kartik Goyal, Chris Dyer, and Taylor Kirkpaiik.....c. Exposing the implicit energy networks behind masked language models via Satropolis-Hastings. CoRR, abs/2106.027766, 2021. URL https://arxiv
org/abs/2100 01736
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, editors, Proceed- ings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 3831 3841. PMLR, 18 24 Jul 2021. URL ltttps://proceedingg mlr. /ttpppiiinnnnnr.peessee//e press/ 1118/grathwoh121a.htm
Alex Graves. Sequence transduction with recurrent neural networks. arXin:1211.3711, 2012. URL https:
//arxiv.org/abatt wrgg/bas/2....//111111
Aditya Grover, Ramki Gummadi, Miguel Lazaro- Gredilla, Dale Schuurmans, and Stefano Ermon. Variational
rejection sampling. 100..01804 2018. URL httppe////ardiv..rrgaaa/a////// 01712
Jun Han, Fan Ding, Xianglong Liu, Lorenzo Torresani, Jian Peng, and Qiang Liu. Stein Variational Inference for Discrete Distributions. arXiv:2003. 00605, 108, 2020. URL http:///araav.orr//aa///0000
W. Keith Hastings. Monte Carlo sampling methods using Markov chains and their applications. Biometrika, 1711)997--09, 1970.
Jean-Baptiste Hiriart-Urrut,, and Claude Lemaréchal. Conver Analysis and Minimization Algorithms 1: Fundamentals. Springer, 1996. ISBN 9783540568506.
Wassily Hoeffding. Probability incqualitics for sums of bounded random variables. In The Collected Works of Wassily Hoeffding, pages 409 426. Springer, 1994.
E. T. Jaynos. Information thoory and statistical mechanics. Phys. Ree., 106(4))620-630, May 1957. doi: 10.1103/PPO hwtp///yyyeeee....2505 URL http://prola. http:///l..app...aaataatttaaaaaa
Muhammad Khalifa, Hady Elsahar, and Marc Dymetman. A distributional approach to controlled text generation. In International Conference on Learning Representations, 2021. URL https://openrevierr
het//forum?dd==jWeu555--- 9AbL
S. Kullback and M. A. Khairat. A Note Minimum Discrimination Information. The Annals of Mathemat- 280, 1966. doi: 10.221//somm//1776966.. URL https://doi.orrg/// 1214//
ical Statistics, 37()))279
aoms/ 4oms/1177699619
Yann LeCun, Sumit Chopra, Raia Hadsell, Mare' Aurelio Ranzato, and Fu Jie Huang. A Tutorial on Energy- Based Learning. In Predicting Structured Data. MIT Press, 2006.
15

---

Published in Transactions on Machine Learning Research (11/2022)
Jiwei Li, Michel Galley, Chris Brockett, Jianfeng Gao, and Bill Dolan. A diversity-promoting objective function for neural conversation models. In Proceedings of the 2016 Conference of the North American Chapter of the Association for Computational Lònguistics: Human Language Technologies, pages 110-119, San Diego, California, June 2016. Association for Computational Linguistics. doi: 10.18653/v1/N16. 1014. URL wtttps://www..allbbb... wwwp://ww..rr/atttoooooooo/----a
Friedrich Liese and Igor Vajda. On divergences and informations in stafistics and information theory. IEEE Transactions on Information Theory, 52(10):4394 4412, 2006. ISSN 00189448. doi: 10.1109/TIT:2000
881731.
Jun S. Liu. Monte Carlo Strategies in Scientific Computing. Springer Series in Statistics. Springer New York, 2004.
Jun S. Liu, Rong Chen, and Wing Hung Wong. Rejection control and sequential importance sampling, Journal of the Americon Statistical Association, 98(4433:1022-1033 1998.
Gábor Lugosi and Shahar Mendelson. Mean estimation and regression under heavy- distributions: A survey. Foundations of Computational Mathematics, 1965):1145-1190, 2019.
Jonathan Mallinson, Rico Semnrich, and Mirella Lapata. Paraphrasing revisited with neural machine transla- tion. In Proceedings of the 15th Conference of the European Chapter of the Association for Computational Linguistics: Volume 1, Long Papers, pages 881-893, Valencia, Spain, April 2017. Association for Compu- tational Linguistics. URL
Nicholas Metropolis, Arianna W. Rosenbluth, Marshall N. Rosenbluth, Augusta H. Teller, and Edward Teller. Equation of state calculations by fast computing machines. Journal of Chemical Physics, 21 26): 1092- 1953.
Ning Miao, Hao Zhou, Lili Mou, Rui Yan, and Lei Li. CGMH: constrained sentence generation by Metropolis- Hastings sampling. In The Thirty- Third AAAI Conference on Artificial Intelligence, AAAI 2019, The Thirty-First Innovative Applications of Artificial Intelligence Conference, LAAI 2019, The Ninth AAAI Symposium on Educalional Advances in Artificial Intelligence, AAAI 2019, Honolulu, Hawaii, USA, Jan- uary 27 February 1, 2019, pages 6834 6842. AAAI Press, 2019. doi: 10.1609 /at/a/aai..... v33101.33300 33011663..4 URL https://doi.org: 10. /0009//aaa....
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, editors, Proceedings of the 58th Annual Meeting of the Association for Computational Linguis- tics, ACL 2020, Online, July 5-10, 2020, pages 2020. doi:
Association for Computational Linguistics, /220:/11112000mmmmmmii 314. URL http:://aaa..oggg1...85//////// http:///22222...m1........
Moin Nadeem, Anna Bethke, and Siva Reddy. StereoSet: Measu bias in pretrained language models. CoRR, abs/ /os/2004.094566 2020. URL
/9940 09456
Nathan Ng, Kyra Yee, Alexei Baevski, Myle Ou,, Michael Auli, and Sergey Edunov. Facebook FAIR's WMT19 news translation task submission. In Proceedings of the Fourth Conference Machine Transla- tion (Volume 2: Shared Task Papers, Day 1), pages 314-319, Florence, Italy, August 2019. Association for Computational Linguistics. doi: 10. 10.18653/vil /01////v1/i//// 511-/333. URL https:
Akihiko Nishinura, David B. Dunson, and Jianfeng Lu. Discontinuous Hamiltonian Monte Carlo for discrete parameters and discontinuous likelihoods. Biometrika, (06 380, Mar 2020. ISSN 1464-3510, doi: (00009///iom///s////// URL htttp://dx... /ttp//xxxdoiiooo///oo/////oooo www.ddo...o..../oooo 10. 100/11100000/00//////////000
Art B. Owen. Importance Sampling. In Monte Carlo Theory, Methods and Eramples, chapter 9, Unpublished Lecture Notes, 2013. URL htttss:// stanford wwwpd/owweeeeeeeee mc/ / htth:mm//hhhaaaaaaeee -hh-var-ss.pd
G. Parisi. Correlation Functions and Computer Simulations. Nuclear Physics B, 180:378, 1981. doi: 10.
(016/0050-3311((1)))) 900066000
16

---

Published in Transactions on Machine Learning Research (11/2022)
Tetiana Parshakova, Jean-Marc Andreoli, and Mare Dymetman. Global Autoregressive Models for Data- Effiicient Sequence Learning. Tn Proceedings of the 23vd Conference on Compulational Natural Language Learning (CoNLL), pages 900-909, Hong Kong, China, November 2019a. Association for Computational Linguistics. doi: 10.18653/v /000553/v1///// /t////11/1111///// URL https:://///t htops://wwwww.. wwwp:w/wwwwbb..o... www.:aaawww...aaaaaeee htt.://rorr.aaaaoooo/11/-----000
Tetiana Parshakova, Jean-Mare Andreoli, and Marc Dymetman. Distributional Reinforcement Learning For Energy-Based Sequential Models. arXiv, abs/1912.08511, 2019b.
Yury Polyanskiy. MIT Information Thcoretic Methods in Statistics and Computer Science, Lecture 1: f- Divergences, 2019. URL https:// lids mit http://pp//hmmpag///aaaaatbeeeea http:///dddaaaaaaaa.pppap fdiv..dff
Yury Polyanskiy and Yihong Wu. MIT, Yale and UTUC, Lecture Notes on Information Theory, 2017. URL http://people. lids. mit. wwt.t./ea///pphooogggg/aattt/t// http://pppppppttaaaaallttteeeeee pdff
Tiberiu Popoviciu. Sur les équations algébriques ayant toutes leurs racines réelles. Mathematica, 9(129-145): 20, 1935.
Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. Language models are unsupervised multitask learners. OpenAl Blog, 188):9, 2019.
Nils Reimers and Iryna Gurevych. Sentence-BERT Sentence embeddings using siamese BERT-networks.. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing. Association for Computational Linguistics, 11 2019. URL htttps//arxiv... hwtpa/vv.rgg//a/////eeeeee att////////////////// 10084
Benjamin Rhodes and Michael Gutmann. Enhanced gradient- based meme in discrete spaces. arXic preprint arXiv:2208.0000 2022.
Christian P. Robert and George Casella. Monte Carlo Statistical Methods (Springer Texts in Statistics). Soringer-Verlag, Berlin, Heidelberg, 2004.
Ronald Rosenfeld. A maximum entropy approach to adaptive statistical language modelling. Comput. Speech Lang,, 10(3):187 228, 1996. doi:
URL htttps://doi.o org/10. 11.10066/s11. 1996.
0011
Vivekananda Roy. Convergence diagnostics for Markov chain Monte Carlo. Annual Review of Statistics and Its Application, 7(1):387-412, 2020, doi: 10.1146/anman /annaaressttttiiiiisssssssss 031p:sstttttttts00111-1101111110 URL https: 041300
7/do1. org/10.
Halsey Royden and Patrick Fitzpatrick. Real Analysis. Pearson, fourth edition, 2010.
Donald B. Rubin. Comment on "The calculation of posterior distributions by data augmentation". Journal of the American Statistioal Association, 82(398):543 546, 1987.
Yang Song and Diederik P. Kingma. How to train your energy-based models. CoRR, abs/ 210110388, 2021. URL
Terence Tao. The strong law of large numbers, 2008. URL https://eerytaa.wordrrree c0m.//000// 18/ 23/the-stee -aazoog--ar-----arg------- numberss
Tuke Tierney. Exploring posterior distributions using Markov chains. Technical report, Minnesota University, Minncapolis Department of Statistics, 1992.
Dootika Vats, James M. Flegal, and Galin L. Jones. Multivariate output analysis for Markov chain Monte
Carlo. Biometrika, 2019.
Aki Vehtari, Andrew Gelman, Daniel Simpson, Bob Carpenter, and Paul-Christian Bürkner. Rank- normalization, folding, and localization: an improved R for assessing convergence of MCMC (with discus- sion). Bayesian Analysis, 16(2):667-77) -7166 2021.
John von Neumann. Various techniques used in connection with random digits. John von Neumann, Collected Works, 5:768-770 1963.
17

---

Published in Transactions on Machine Learning Research (11/2022)
Larry Wasserman. All of Statistics: A Concise Course in Statistical Inference. Springer, New York, 2010. ISBN 9781441923226 1441923225.
Maosen Zhang, Nan Jiang. Lei Li, and Yexiang Xue. Language generation via combinatorial constraint satisfaction: A tree search enhanced Monte-Carlo approach. In Findingg of the Association for Compu- tational Länguistics: EMNLP 2020, pages 1286-1298, Online, November 2020. Association for Computa- tional Linguisties. doi: (118653/w1/2000ffniiinge/
URL
Ruqi Zhang, Xingchao Liu, and Qiang Liu. A langevin-like sampler for discrete distributions. In International Conference Machine Learning, pages
PMLR, 2022.
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 Collins-Thompsot Qiaozhu Mci, Brian D. Davison, Yiqun Liu, and Emine Yilmaz, editors, The 41st International ACM SIGIR Conference Research & Development in Information Retrieval, SIGIR 2018, Ann Arbor, MI, USA, July 08-12, 2018, pages 1097 1100. ACM, 2018. doi: 10. 021144//3299978331000885 URL https://doi....oe org/1//..r110110 115p///999114///99997999 3210080
18

---

Published in Transactions on Machine Learning Research (11/2022)
A Additional Controlled Text Generation Results
We perform constrained text generation for a variety of distributional and pointwise constraints. In partic- ular, we constrain the GPT-2 biographies model to contain (a) 50% female biographies about scientists, (b) 50% female biographies about sports, or (c) 50% female biographies without additional constraint. Also, we constrain GPT-2 small to exclusivcly generate sequences containing (d) the term "amazing", or (c) the term "Wikileaks". For each of these lasks, we obtained fine-tuned model using DPG, which serves both as a baseline and a proposal that we can sample from. In the case of pointwise constraints, also consider naive filter sampler (proj in which the proposal distribution is directly projected onto the constraint man- ifold by filtering out all samples that do not match the constraint. This sampler also assigns well-defined probabilities to the sequences that it samples, so we can compute estimates of the TVD and DKL. for it.
For each task, we again obtain 1M samples from the corresponding proposal, which we use to evaluate the proposal q, the projected proposal Oproj (only for the pointwise constraint), and QRS sampling (pş) for a range of B values reported in Table For all of these, we compute estimates of number of metrics including those of Sec. 3.2.2 (i.e. TVD(p, pp), (pL pa), AR, reverse KL divergence from the base language model DRL(-, a), and the moments of the features that we wish to control).
Our results are shown in Fig. 5 As expected, the upper bound on the TVD between and p, and the KL divergence of p from pa both converge monotonically to zero as the acceptance rate decreases. For the constraints and corresponding proposal distributions shown here, it seems that an acceptance rate of 10-3 is sufficient to match the target EBM nearly perfectly. The feature moments also converge as the acceptance rate decreases, although in some cases the QRS sampler matches the target EBM closcly that small inaccuracies in the À values obtained from the EBM estimation procedure (which is from Khalila et al. 2021 become apparent. As for the divergence of the QRS distribution from the original language model DKL a), there is no obvious trajectory that it should follow other than a tendency to converge to the lowest possible value (p, a) when all constraints are satisfied (by definition, the EBM p is the distribution e which minimizes (CI.Ce, a) among all distributions satisfying the constraints). Indeed, our results show that this metric a mon-monoto function of AR. We observe that the moments computed downstream on QRS closely match the IS predictions, giving us confidence in the accuracy of those estimates. Finally, in the case of our pointwise "amazing" and "Wikileaks" constraints, find that the naive filter strategy (Gproj) corresponds to running the QRS sampler at a high acceptance rate.
Experiment
Buin
fmax
50% female and 100% scientists
1.0 10 12
9.3 106
50% female and 100% sports
2.9 10?
50% female
40--
4.0 10
100% "amazing"
1.0-
5.3- 10a
100% "Wikileaks"
100-10-12
6.0
simple
1.0-
3.8
multiple
1.0 10-11
2.3
knowledge
1.0 10-10-12
24.0
jeopardy
10 10 10 12
29.0
news
10 10 12
3.0
Table 2: We report the range of B values used to obtain the range of acceptance rates in Fig.
3
and 5
B Applications to Paraphrase Generation
Inspired by Miao et al. 20199 we perform proof-of-concept experiments on paraphrase generation by framing the task in terms of conditional EBMs. Specifically, given a sentence y to paraphraso, we define our EBM in terms of a language model a(x) GPT-2(x), and pointwise constraint b(x) given by a binary classifier that classifies pair (x. y) as paraphrase if the cosine similarity between their sentence embeddings is
19

---

Published in Transactions on Machine Learning Research (11/2022)
1-24 Ti netuaa
Dul-pol Duib.d
Rr 4 Os 30.40
2.5
5.00
constraint t-feraae 55
6
2.3
8
0.11
4:60-
targrt PorWWn
bagget POSTTITS
UP1
18-1
10"1
32-1
15
acoeptance
socostanc
accaptance Tite
acciplance
eccoptance
(a) 50% female scientist biographies
I-sky] Tidla.a
Auls mn Duth ct
1o of
2/4-
Conotrant-ffrmlle
conszroant spports
TVD
3.4-
3.20
55
5
0.2-
12
3.00
sareet FOOTOAES
target FOaTTITT
2.50
167
10-1
12-0
1071
1911 10-1
1277
DPPT
12-1
1011
10-1
acceptance
accupla
(b) 50% female sports biographies
1.0
Oulo al
Dulc
Tutgpu oi
0.4
0.00
constraint Tomale %
TV0
0.5-
0:00
0.2
0.2
0.1
targdt mome
0.00
187
22th
12-1
20-1
eccestorce co 1iee
accptancerste
OcceStance 1900
(c) 50% female biographies
1.-
SHN00000009
2.-
Ou
7.50
Dallyy
55-
6,50
5
6,00
00-
0:3
5:00
2.0
0.3
2
20-1
scraptaree wis
accoptanca rate
acceptance Fi04
accaptarce 1at
(d) 100% sequences containing "amazing"
18.8
2.8
20.2
commorainc WillrraiccWWillllss.ss. So
1.5
10-2
Datoo
0.2
52
9.20
00-
00000000000
0.7
000000000000
4.0-
0000000000000
socaparca
(e) 100% sequences containing "Wikileaks"
Figure 5: We show IS estimates of TVD(p, +), an upper-bound on TVD(p. (KL(p.)), (x and feature moments as a function of acceptance rate. We show three distributional constraints on GPT-2 biographies and two pointwise constraints on GPT-2 small. As proposal distribution, we use a DPG model trained for cach constraint scparately. We show soparate lines for the target moments and the moments realized by the EBMs, revealing slight inaccuracies in the EBM moments for some constraints.
20

---

Published in Transactions on Machine Learning Research (11/2022)
How is the two wheeler insurance from Bharti Axa insurance?
Are there Doctor Who references in the Muse song "Knights Cydonia"?
In French, how you say "caal"?
0.75
0.75
0.75
0.50
0.50
0.50
0.00
0.00
0.00
10
10
10
10-3
10-
10
10-3
10
10-9
10
10
10"
10-9
acceptance rate
acceptance rate
acceptance rate
Input Sequence
Proposal Distribution
QRS samples from p at AR = 10
How is the two wheeler Insurance
What about bicycle insurance from Rharti Axa insur- How is the Axa Bharti two-wheeler insurance pol- ance?
ley?
from Bharti Axa insurance?
What about the Bharti Axa insurance?
How is Bharti Axs insurance for two-wheeler?
What is the Bharti Axa insurance plan?
The Bharti Axa Two-wheeler insurance. How is it?
Are there Doctor
Do you hear a hint of doctors in the Muse sougs Are there Doctor Who references in Muse's ' Knights of Cydonia?
Who references in
'Knights Cydonia"?
the Muse song "Kuights Cydonia
Can you find a hiat at Doctor Who in the 'Knights of Does this Muse song 'Knights of Cydonia' have any references to Doctor Who?
Cydonia' lime from the book's 's Muse soug?
Are there any references Doctor Who
song, Are there Doctor Who references in Muse's Knights of Cydonia?
Knights of Cydonia?
How do you call 'cool' in French?
How to Say "cool" in French
In French, how do you say "cool"?
How you keep language Cool in French?
How Say 'Cool' in French
How do you 'cool' in French?
How do you "cool" in French
Figure 6: 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 g(x) (round-trip NMT) as well as the QRS sampler pa at acceptance rate of 10-5 (bottom).
above 0.95. We obtain high-quality sentence embeddings from Sentence-BER11 [Reimers and Gurevych 2019). As proposal distribution we do not use GPT-2, but rather illustrate how can utilize off-the- shelf deep learning models as proposal distributions for QRS. In particular, we use a round-trip machine- translation model, which a well-known tool in generating paraphrascs (Bannard and Callison- Burch 2005; Mallinson et al. 2017). Specifically, we use the Baylish-to-Germaal and German-Io-Fangissl models from Ng et al. (2019). We first obtain a beam-scarched (Graves) 2012) translation into German and then define the proposal distribution as the German-to-Enun English model conditioned on the beam searched translation. We locally renormalize the model to do top-30 sampling (Fan et al., 2018).
We show IS estimates of TVD(p,Ps) ps) using 1M samples for three sequences in Fig. 1 along with samples from both the proposal distribution and QRS at AR = 10-5, The quality of the proposal distribution varies with the input sequence, as can be seen from the slope of the curve and the low-efficiency starting points of some curves (non-paraphrases are always rejected and so they have a big influence on the acceptance rate). Still, QRS gives excellent approximations the target EBM two out of the three examples (in the "insurance" and "cool" examples, the TVD is nearly zero), although the TVD in the "Doctor Who" example remains above 0.4 even for AR 10-5). Looking at the examples, we find that the proposal distribution produces decent paraphrascs, but they are not always semantically equivalent or grammatically correct. The QRS samples are mostly semantically equivalent, though they still contain some mistakes ("Axa Bharthi" vs "Bharti Axa") and seem to be insensitive to the question mark and to the casing of words ("Cool", "Two-wheeler insurance"). Interestingly, this experiment illustrates how the presented approach could be employed to disentangle the questions of how model a problem (by defining the corresponding EBM) and how to efficiently sample from it (by improving the proposal distributions), making it possible to work each of these questions separately.
We http:://wwgiiiggaaaae.cc///ettte
14 We use beam size
21

---

Published in Transactions on Machine Learning Research (11/2022)
0.5
10
Dalp.ps)
0/9
Dule, 9)
acceptance rete
0.23
67
0.0010
--- Au0. Bu
0.0005
0.22
6.02
8
0.0000
64
-0.0010
0.8
0.3
10a
10a
10
10P
10
3.0 6.8
accettance rate
64
number of samples
(a)
(b)
Figure 7: (a) Estimation of sampling quality as DKL Ps), efficiency (acceptance rate), and the trade- off between them for a QRS sampler when using a proposal g = Poisson() = 10) to approximate p Poisson (A 11), computed
10 independent experiments over 101 samples. (b) Differences between estimated (p)(P. and their true values for 3 2, computed 1000 times for each different number of samples. Shaded areas represent one standard deviation.
Additional Results for Poisson Distributions
C.1 KL-divergence results for QRS
Fig. shows the convergence estimates of the KL divergence when using QRS with Poisson distributions. As in the analogous plots for TVD (Fig. 2), we see that the divergence quickly converges zero as B increases, and that the standard deviation of the estimates is much larger than the bias.
C.2 Comparison of QRS, IMH-R and RWMH-R
We now compare the performance of QRS with other approximate sampling methods, namely the reset ver- sions of the independent Metropolis Hastings (IMH-R) and the random-wall walk Metropolis Hastings (RWMH-R) samplers. As above, use the proposal g Poisson() 10) and target p Poisson(A 11). To ensure accurate values for the KL divergence and TVD, we implement each method in closed form, as now explained.
Calculating the probability mass functions of the samplers For QRS, we compute the probability mass function ps and acceptance rate using Eq. 3 and For IMH-R, we take k samples from the proposal q according the generative process:
( 9:
for 1 k....
k-1
((1)
(e)
/ with probability min (1, p(x(-11) (((((111)))
x
((-1)) otherwise.
For nonnegative integer states ((r-1) za and x 3ı, this corresponds to the transition matrix (or Markov kernel, noting that the state space is infinite)
T mn ((zz))(mi) min (1, p(an)//((1))
Yz * z
p(an)//(zn)
T Trg. =
Σ Te
We compute the divergence of the target from the distribution of (k-1), which is T q; and for comparison with QRS, we compute the "acceptance rate" 1/k, i.e. the reciprocal of the number of times sample
22

---

Published in Transactions on Machine Learning Research (11/2022)
0.00
0.12
0.10
TVDip-]
0.02
0.01
QRs
0.02
QRS
0.00
BWMI R
0.00
RWW R
0.8
0.6
1.0
0.8
0.2
scceptonce
accegcance
Figure 8: Quality-efficiency trade-off for QRS, IMH-R and RWMH-R samplers, when approximating the target distribution = Poisson(X= 11). We use distribution Poisson(X 10) proposal for QRS and IMH-R, and as initial distribution for RWMH-R. Quality is measured as Paaptr) in the left plot, Psampler)
and as (p. Psampler) in the right plot. Efficiency is measured as the acceptance rate for QRS; and as the reciprocal of the number of sampling itcrations for IMH-R and RWMH-R, which we call the "acceptance rate" in this context.
from For RWMH-R, we consider the chain:
(0) 9:
for t = 1....,k -
((=-1) -1 with probability Y
y(
x((-1)) +1
otherwise
(t)
with probability min (1,
p1r(0) (1,p((011)
x(()
((-11) otherwise,
corresponding to the transition matrix
min (1,
p(21) p(zo)
if ( - Fo = 1
T .z
0
if |x| zo >
E - 20/== Tr
if æ = Tn-
We compute the divergence of the target from the distribution of ( which is T q; and for comparison with QRS, we compute the "acceptance rate" as L/k, i.e. the reciprocal of the number of times we must evaluate the target distribution p (or for à = the number of times sample from the proposal q)- Clearly, the performance of RWMH-R might be improved by using different random walk: the +1 random walk is used here as it seems the simplest and most natural choice.
Truncation errors For all methods, lo ensure practical computation, we truncate the distributions, work- ing only with states æ < 50. To assess the truncation error, we repeat the experiment, this time truncating with < 100, and find that the largest relative error KL, TVD or AR for any method is in the KI. divergence of QRS for B = 5, which is
DEL(p, (p)eceo DKL((pP9)es00) 1.48 ... x 10 10
DKL (p, 10)
Results Figure 8 presents the TVD and KL divergence as a function of AR, computed for parameter / in the range (0.1. 5] for QRS, and for 1,2,... ... iterations of IMH-R and RWMH-R. For acceptance rate AR 1, all samplers give the same divergence, as they all return samples directly from the proposal g.
23

---

Published in Transactions on Machine Learning Research (11/2022)
For each lower acceptance rate the TVD of QRS is systematically lower than that of IMH-R, and the TVD of IMH-R is systematically lower than that of RWMH-R; and the same holds for KT, divergence. On investigating the ratios of the divergences, we find that these advantages increase as the acceptance rate decreases, and for AR = 1/5 we have
PIMM-R 2.24 10a and TVD PQRS.8=6)
DRL(P, PIMM-R,A-S) 3.60 102
DKL (p, PQRS,
D Properties of QRS: Proofs
D.1 Proofs of Eq. and Eq.
16 output from Algorithm is equal Proof of Eq. 3 By definition, (a))) is the probability that the first
to Σ. On the first step of the algorithm, the probability that a given I is accepted is g(z)ra, whereas the probability that the algorithm rejects its first sample is p= Ezxx (()) Tx) = 1 ΣvEx ((x)r=. More generally, the probability for x to be accepted on step of the algorithm, while no x was accepted on previous steps is then p'= (xx)) Overall, the probability pą(x) that the first sample accepted is æ is
(0))r= (()r,
g(x)r=
1 1-
((x)r=
Zg Ps(x))
ExEx ((x)rz
Proof of Eq. 4
We have
AR3- Exnn min P(s)(((((())
8-1 min(P(r),B((zz)
DEX
B Σ
Pa(x) Z3/B.
xEX
D.2 Proof of Theorem 2.1
We will need well-known property TVD (e.g. see Chafai 2010). namely that, for any distributions Pt, P2 over X, we have
TVD(PI.2)) =
Σ
(pi(x) - pp)(x))
(8)
(eX2x(+)2p.(())
The proof, illustrated in Fig. 9 then proceeds as follows:
Let Ag = {ar E X P(x) < (q(x)} and Ag = X Ag. We have Pa(x:) = ((P)(()),g()))) and therefore Pa(x) = -P(x) for x E As, and Pa(x) < P(x) for æ E Ag. Overall, Ps is less than or equal to P, and
thus Zg < Z. For any x, we have p=(x)= = Pa(x)/Zg and p(x) = P(x)/Z, and hence for x E Ag we have
p(a) S (1)).
If we define Cj - fxr X: p(x) S p)(x)), and Eg = X Cs, we have Ag Cg and Ö3 C Ag. Using Eq. now that
TVD(P.Ps)=
Σ
(p(x) -p(()))) = Σ
(p(x) - -M(x)-pp())) < Σ p(x).
zeCa
#EC₁
Finally we get
TVD(p.P3) S p(C)) p(p)) = 11 p(A))
(9)
The acceptance rates of QRS for 3 2, 2,3... nearly cqual to 1/3,, because AR Z,/8 by Eq. and for this choice of B. p and g we have Zg 16.r, for that matter, due to the obvious i.i.d. nature algorithm, for any fixed the k-th output.
24

---

Published in Transactions on Machine Learning Research (11/2022)
P
P6
PR
Ap
Ag
Ap
Ap
Cp
Cp
Figure 9: Visualization of Theorem 2.1 The left panel shows the unnormalized distributions P and Ps. the right panel their normalized versions and pa. In the right panel, the area under the curves and pa represent the total p-mass and Py-mass X respectively, which are both 1. To simplify visual comparison, the figure assumes that = 1, in other words that = p. then Z3 S and Pş P3 scaled by the factor 1/Zg. The TVD between p and pa is equal area between the two curves above C3. This last area is included inside the area below the p curve above Ag, which is the visual counterpart of Eq. 9
the area between the two curves above C3, but also to the
Proof of the corollary to the theorem For any (normalized) distribution over discrete space X, we have Ei= p(x;) = 1, hence for any e > 0, there exists finite subset X' S X such that p(X') > 1 1 e, with X' [ Supp(p) S Supp(g). If we take = maxxxxx <(x) p(Ag) 2 1 e, which proves the result.
P(w) then 33 finite, X' S Ag; and therefore
A generalization to arbitrary g-supports The corollary exploits the assumption that we made throughout Sec. 2 that the support of p. Supp(p), is contained in the support of q. Supp(g), in other terms, p(z) > 0 - g(x) > 0. If that were not the case then 3 = maxxex P(a) could be infinite and Ag would not be defined. However, it interesting that we can actually generalize the result. the case where Supp(p) may not be contained in Supp(q). In that case, for any > O, there exists a finite subset Y' S Supp(q) such P(z)
(())
that p(Y") > p(Supp(a) - e. we now take B = maxzey q()) then 3 finite, Y' C Aş; and therefore p(As) 2 p(Supp(4)) -c. For any B, cach element a of Ag is either in Supp(g), or it satisfics 0 = (x(xx) 2 P(z) so that p(#) = 0. It follows that p(Ag) I p(Supp(a)). Therefore
p(Supp(a)) 2 p(4s) 2 p(Supp(a)) -
When the support of is included in Supp(4), we have p(Supp(a)) = 1, and therefore we get the previous result back, but now we see that, in the general case
lim (1 - (0-(((A)) = = p(Supp(a)). $
(10)
D.3 Proof of Theorem 2.2 (Monotonicity)
Notation It will be convenient to use the notation a A b to denote min(a, b).
D.3.1 Preliminaries:
majorization of convex functions and a squeezing lemma
We will exploit the following "majorization" result about convex functions. Theorem D.1 (uuhh 1947). ). Let ,i....,Pr Pn. be real numbers, and let
b> 91 2 2 > a. b> ví 2 2 v/2 > a
be nonincreasing sequences of real numbers, such that
Σ pau Σ
Palis
Σ
park < Σ
Pillis
(11)
1=1
i=l
25

---

Published in Transactions on Machine Learning Research (11/2022)
Squeezing
Σ pi f(o)
Σ Pi P050
f(0)
f00
Jr
P,y.
Σ p. = E,
Figure 10: Squeezing lemma. We let E, PiYli and represent the points and yf through dots with sizes proportional to pi.
for k 1, 1....,7 n 1. Then for any conver function (a, R, have
EnflW S p(f(()))
(12)
1=1
Our application of this theorem will be based on the following "squeezing" lemmna (see Fig 10 Lemma D.2. Let ,I, be nonnegative real numbers, with Σi 1, let f be convex function f (a, b) -, R, and let
か>ツ yn a, be nonincreasing sequences of real reumbers, such that
b> ví 2 2 1/2 > a
Pivl Σ
Piy::-
i=1
Suppose that there crists an integer k such that v/c s if i s k and 2 2 y otherwise. Then
Ensl) S Σ pvf(
(13)
Proof. If S k then Em Pi( 8/) as 3\ < y for i S k. If > le then
Pi(Us - 1/1 = Σ P.(v - y.) 2 0, Σ
1=1
i=
Σ 1 Pi(y: v/{) 0 and , 2 yi for i > k. This means that the conditions 11 are satisfied, and we
then conclude through 12
D.3.2 For the main proof, we can focus on the case where P is normalized, the general case follows
Suppose that p the normalized version of P, with p(x) P(z)/Z. We have by definition pa(x) (P(x) (8q(z))/Zp, in other words pa(x) P(x) (Bq(z))- Let denote by Pg the similar distribution.
26

---

Published in Transactions on Machine Learning Research (11/2022)
but this time defined relative to P = p, in other words Pa(x) & P(æ) A (Bq(x)) p(x) A (Bq(z)), oquivalently, (z( & p(z)) A (ZB ((x)) = P(z) A (Zg q(x), thus if B = Z then it follows that Ps = P3- Therefore, order to prove that < 3 < 3 < implies Df(p,ps' S Dy(p.ps) it enough to prove that
<< 3 < oo implies (p pb) - Dy (p.
D.3.3 Some basic properties of p3
Let 0 < B < 00. We have
00.
Pa(æ) = p(z) A (3q(z)),
(14)
that
23 = Σ P3(x) E (3q(x)) (
> p(x)) (LN()(())ML)))
(15)
Ps(x)
p(z)
g(x))
p(x) 1A 1A (3q(c)/p(())
(5(
(16)
Zg
ZB
Z3
The following observations will be key in the proof. For S B' < oc, we have
1
8 3
(17)
Z
ZB ZzI
which are simple consequences of the following facts:
Zg = Σ p(x) A (3g(x)) = Σ p(x) (3'g(z)) = Z
Za
p(x)
p(x)
7
A ((x) 2
A ((x))=
8
3
3
3r
10
D.3.4 Using the form Dy(ps.p) p) instead of the form (p(p
As already remarked in footnote f-divergences have the property that Dy(P1,P2) D Dy P1), where f(t) = tf(1/t) is the "perspective" transform of f, which is convex when f is convex PPllynskiy 2019 Remark 7.2). 17
For the monotonicity proof, it will be more convenient to use the form Dy(ps, p) than the form (p We will then prove that for any convex function (with the usual conditions on f-divergences), if0 < < f < then (p p) S D (p(p.))), P), which will imply that for any convex function (with the usual conditions on f-divergences), if < 8 < B < xo then Dy(p. pa)) S (p))),)) the original formulation of Theorem 2.2
With p fixed, will use the abbreviation Dg + Dy(ps,p), that
(p(xz)
Ex(x) s (IA(3(())/D(o))
D3 = DDDDa(p =Ep(x) /
(18)
p(r))
Z
D.3.5
Focusing the finite case X (01, f Fm first
Our proof will now proceed by assuming that X = fai...., Fm is finite, but we will show at the end (Sec. D.3.8 that the proof generalizes to any countable space X.
For discrete distributions P1.P2 in particular, this is always true, irrespective of whether P1 & &. or & with & denoting absolute continuity, that is & p2 meaning that Supp(p1) C Supp(rz) and similarly for the reverse case but this requires small technical extension of the notion of f-divergence, see Polyanskiy (2019), Remark 7.1. In the case where pi Ps.P2 p, we do not need this extension because we have both ps & and < Ps, an easy consequence of the fact that q by hypotheses and of pa(x) P=(x) p(r)A(aq(x))
Zn
27

---

Published in Transactions on Machine Learning Research (11/2022)
DB
B
PB = q
continuity
PB =
To
71
In
A
B
C
To
71
Tk
Tk+1
Tn
B
Figure 11: Left: three regions for B. Right: continuity of Dg.
D.3.6 reparametrization in terms of importance ratios
Let
r(z) = p(x)/g(a), R= (0) U r(X) (I..,,,...,
where ro = 0, and for >>>000 0, rı is the image by r of some r X (where = (.I,..., Im now finite, by assumption; note that may or not appear in r(X) and that m can be larger than n + 1). We order the r such that 72 Ti+1;
1o
Tn
We can re-express Eq.
14
16 and 18 in terms of rs:
p(r:) = Σ p(x),
(19)
*EX:r(a)=n;
33 Σ p(r)) (3/r)/)))),
(20)
po(ri) = p(r)) (3/rr)
(21)
Zg
D3 = Σ p(rs) o (patr)) = Ex(re) f (1A(8/11)
(22)
Z3
Note 1 We abuse notation: x E X and r E Ryo are in diffcrent spaces, so we could really write p(r:) instead of p(r.) to distinguish the two spaces.
Note 2 We let p(ro) in all cases.
D.3.7 Focusing on sub-intervals is enough
As the right-hand side of Eq. 20 is continuous and positive function of (0, o0), the right-hand side of Eq. 22 is also continuous, and therefore Da is continnous function of B (0, oo). The index i runs over finite set, hence to prove that Dg is non-increasing in 3 it is enough to prove that it is non-increasing cach interval (rk,rk-1).
It will be useful to distinguish three regions for 3 (see left, panel of Fig. 11 namely region A, with 3 smaller than the smallest non-null importance ratio ri; region B with 3 between 71 and Tai and region C' with B larger than the largest importance ratio rn.
We start by noting that pa is constant. A and on C:
28

---

Published in Transactions on Machine Learning Research (11/2022)
Yn
yet1
b/ra
b/Tk+1
1
Zb
Zb
Zp
Zp
b' D1/Th
b' D
1
Zp,
Zp
Zpr
Zo
y'n
YK1
y'x
y'1
Figure 12: Application of squeezing lemma to rh < b < Dy < rk+1
For E A have
- fo p(x) 0
p(x) A (9q(x))
(q(x))
p(x) > 0
and it follows that
pạ(x) = {0 1 q(ar)
p(x) = 0 p(x) > 0,
((Supp(e)
which is the "normalized" version of relative to Supp(p).
For 8 E O we have pa(x) p(x) A (Bg(x)) = p(x). Hence ps (standard RS).
It follows that Dg is constant for B E A, and again constant (actually mull) for B E C. Thus, in order to prove our monotonicity result, it is sufficient to prove that Dg decreases for 3 increasing inside each interval (rk, (k+1) for k = 1,2,..., n - (see right panel of Fig.
Let S l < n and consider Th < D' Tk+1s we want show that Dy Dy(pv:P) S Do (D. For 1, 2, .......2. n, let
1 b
1A V Zu
(23)
Zn
From 20 and 22
we have
Eplri 11
Eplrish =1= Do Ep(rit(())
(24)
Do Eptrid(ou).
(25)
We further note that
W1
b/r:
%
< k
and
3/1
1//n Ze
Zy
1
isk k i>
(26)
i > k
2o
and we saw earlier in
17 that
b'
< Zb
and
(27)
Zy
Zv
Zo
It follows that
3 S 94
for
< k
and
yi 5 v\ for i > k.
(28)
29

---

Published in Transactions on Machine Learning Research (11/2022)
We can apply our squeezing lemma, Fig. 12 previous paragraph, and let Pt = p(ri). By Eq. 24
apply Lemma D.2 to the ys. v. and k of the the hypothheses of the lemma are satisfied,
25 and 28).
and we conclude that Ex (vf( S Ei ===l P.f (yi)
so that
Dy(ps, p) - (ps.p))
(29)
D.3.8 Concluding the proof: from the finite case the (countably) infinite case
Having proved the monotonicity result 29 for fimite sample spaces X, we now wish to generalize this result to an arbitrary countable space X. We will use the following theorem, adapted from Gilardoni (2009) Proposition 1) to the case of probabilities over discrete spaces. For a partition & (Fi,.... ...F of X into subsets, and distribution p over X, let pe denote the projection of p onto the finite set { 1} given by (i) = p(E)..
(A)
Theorem D.3 (Gilardoni 2009 Let r and be probability distributions over X. Let Dj denote the f- divergence for some conver function f with f(1) 0. Then
Dylr,s) 8) sup (y(re,
E
where the sup is laken over all fivile partitions & of X.
(B) Let p,q and Pa be distributions over a countable space X, and let a and b be values of the QRS parameter B such that 0 < a < b xc. We prove that Dy(p.po) pb) S Dy Pa) by contradiction. Suppose that Dy( > Dy(p.Pa). Then, by Theorem D.3 there exists a finite partition {Fi...., F.} of X such that
Dy(pe, (pb)8) Dy(p,Pa)-
(30)
(C) For each i E {l...., I}, let us split E; into three subsets
D = (s E. p(x) s a g(x)) $ bb()));
EX²) = frr E, az(()) < p(2) 5 bg(())
E = f- E E a < bg(z) < p(x)),
and consider the refinement of partition & given by
F
(E( 1sis I E #0}.
so that J S 37. Lot 8 E {a, It easy to see that F has the following homogeneity property: one can split the indices Ind [I....,J} into two disjoint subsets Indg and Indg, with
Indg = (j E Ind p(x) < Bq(x) Vo E F2J and Indg = Li E Ind p(x) Br(x) Vo E Fy).
(Sets Indg and Indg do not necessarily form partition of Ind as one of these sets may be empty.) We can consider the projections pr and qr of p and q onto Ind, and the associated QRS distribution (pr)s,
which is given by
p(Fx) Z,
j E Indg
(pF))()) PF(1) A (Bqr()) p(F,) A (Bq(F)))
Z
Zg
Bg(F.)
j E Indg,
2,4
where
Z = Σ {B)))(( = Σ p(P)+ Σ Ba(F)).
jElnd
jEInd,
JEIndg
30

---

Published in Transactions on Machine Learning Research (11/2022)
But we also have
ExEF, p(z) A (3q(x))
p(F,)
j E Indæ
Za
= -P((F)) (ps)=(})=ps{F)
Z3
Bg(F,)
j E Indg.
ZB
where
23 = AB(x)
E p(f))+ +
E Bg(F)).
ZEX
jEInd
jEInds
Comparing these two sets of equations, we see that ZB Zz and that
(ps)== = (p=)g.
(D) Let now go back to Eq. 30 The distributions pe and (P6)g can be seen projections of the distributions pf and (pt)z from the set (1,...,J) to the set (1...., /}, and therefore the DPI (Theorem 3.1 applies, implying that (pE (ps)e) s Dy(pr, (pt)=), and therefore:
Dy(pF, (pb)z) > Dy(p.Pa).
A second application of the DPI theorem, this time projecting p and Pa from X to the set {1,...,J}, J}, implies that Dy(pr, (pa) S (p.p),)), and therefore
Dy(PF, (po) > Dy(pF, (pa)z).
(E) We saw earlier that (pb)= (p=)s and (pa)z (pF)a, hence
Dy(pr, (pF)o) > Dy(ps, (px)a),
which contradicts our monotonicity result for the finite set {1,..., concluding the proof.
D.4 Alternative proof of monotonicity for finite X, based on calculus
Sections D.3.1 D.3.7 proved the monotonicity of the f-divergence (y p) for distributions on a finite space X, based result about majorization (Theorem D.1. We now give alternative proof, which avoids this potentially unfamiliar majorization result, and which is based the easy-to-prove observation that the derivative of (Ps.P) with respect to 3 is nonpositive. However, this derivative does not exist for all 3, as neither the partition function Z3 nor the function f is necessarily differentiable. Thus to prove monotonicity, we must do some work to show that Dy p) is a Lipschitz continuous function for 33 in an appropriate interval. We prove the following, which readily generalizes infinite spaces X using the arguments of Section D.3.8] Lemma D.4. Let Rs0 + R be conver function satisfying f(1) 0. Let the set X be finite, and let 0 0< < B < co. Then Dy(ps, Dy(ps.P).
Proof. The partition function Z, of the QRS distribution is
Z, Σ (((r)((
as previously remarked Eq. 20 where
R = (ro.
rn = {0) u (p(x)/(((() x X}.
If of R then this may be written in the form
Z, = Σ p(re) +b Σ (p(rn)/r))
Errcc
31

---

Published in Transactions on Machine Learning Research (11/2022)
the quotient rule gives
d b
Zo -
hen, >b -bEnn
(p(rn)/r))
Etrres <b p(re)
db Zb
Z
Z
Similarly, as remarked Eq.
22 the divergence is
Eplriss (IA(b/T))
Dy(Po.
Zb
and if b & R then this may be written in the form
P) = p(ref
Zb )
+ E p(rn)f
trrc
hrrw
Let N be the set of values of b E [8, such that f is nondifferentiable at one of the arguments 1/Zb 2/) in the above expression. For b & RU N, the chain rule gives
dD dDy(Pb:P) p)
Σ errech
p(ref
( (-
Σ p(rn) (112)))
( (Eerres rh Zi
db
23
hir 2b
Σ
p(re)p(ra)
(p'
b
-
1
S 0,
(31)
Zb
Zb
Prrech harg
where the final inequality follows from the convexity of f.
Now argue that Dy(pb: p) is Lipschitz continuous function of b E [3,88).
As the support of contains the support of p, we have max R < co. Thus, the partition function Z, = E, p(r)((1 (b/rz)) is bounded by
vb E [8,8],
0 < = 1A (B/ max R) S Zo S 1.
It follows that the arguments of function f appearing in D(pb, p) are bounded by
(b/r)))
1
vb [8,8%,
0 < 2io I
Zo
Zoo
That is, all these arguments lie in an interval [zo, with 0 < xp < F1 < 00.
As is convex on (0, oo), the restriction of f to the domain [zo, with 0 < < 21 Lipschitz.
oo is
The following are Lipschitz: finite sums of Lipschitz functions; the minimum of two Lipschitz func- tions; the function æ + 1/x for æ > a where a > 0; the product of bounded Lipschitz functions; and the composition of two Lipschitz functions. follows that D(po.p) is Lipschitz for e [8.
If a function is Lipschitz inntin closed bounded interval, then is dilferentiable almost everywhere on that interval, and the change in the function over that interval is equal to the integral of its derivative (see for instance Royden and Fitzpatrick 2010 Chapter 6, Proposition 7 and Theorem 10). Therefore,
1
8 dDy P) db < 0,
Dy(ps. - DD(sp())
db
where the inequality follows from Eq. 31 This completes the proof.
32

---

Published in Transactions on Machine Learning Research (11/2022)
E Importance Sampling (IS) Estimates
estimates and their derivations. As mentioned in Sec. 2 base all estimates on a sample {zI,..., INJ of i..d. draws from q and if the sum Exer x h(x) is well-defined for a function h : X - R, then we have
Here we provide all relevant IS Owen
2013
we
((x) h(z) q(z)
h(x) g(x)
1 h(x;)
Σ #EX
h(z)
Σ =EX
=Bzng
~
N ((z))
In this way, we find
P(x.)
== P(a)
P(x)
((rs)
ZEX
Pa(x,))
ZB
Σ Pa(x)
N
(2r4))
DEX
P(x)
min (1, Bg(zz)) (1)
P(x))
A = Exzg min
(32)
N
1=1
P(x;)
p(As)= = [(to)((r AAl
1 1 E As),
Zq(x;)
Pp(2i)
Be-psh(x)
Σ ps(x))(z) xEX
h(zz).
N
Zzq(ar+)
Similarly, we may estimate f-divergences with
Dy(p.Ps) E Erng Ps( Zg P(x) P3(x))
Pa(2i)
ZB P(xi)
f f Pa(a;;
Zg ((x))
Za q(x:)
which for TVD (f(() = - 21) and KL divergence (f(t) = t log t) rearranges to
N
Pa(xi)
P(r.)
TVD(P,P3) =
Σ
(33)
2N
Z ((x;))
Zq(x;)
1=1
Zg
1 N
P(r;)
log P(x:))
DRI(p,PP) ~ log
(34)
7
N
Zq(x;)
Ps(1:)
F Estimating the Mapping Between B and AR
Eq. 32 provides a way to estimate the AR given a value of B and a set of samples from a proposal q. How can we go in the opposite direction and estimate for a target AR value? One way to do so, is estimate the full mapping from AR to 8, and interpolate it the target AR. Algorithm 2 estimates this mapping sum of two terms:
efficiently, based the observation that Eq. 32 can be rewritten
ARg ~ (a+ + bi) /N
at B 8= = 3
(35)
where
N b,
8, = P(a))((a)),
a, = Σ 18, $18,1/8
Σ 1 1B 8.). 1=1
(36)
noting that both and b can be computed efficiently given sorted list of B, values. (In the case that B, 3, for some # i, the output will contain repeated values, which are easily filtered out, if necessary.)
33

---

Published in Transactions on Machine Learning Research (11/2022)
sampler
Alt
Xfeeale
%pccence
PPL
Selt-BLRU-S] KUnig!
Dist-1f
Diss-21
Dixt-31
TV) 4" PKu Pa)
DPG
1
27.3
0.4
00.1
0.2
50.8 0.1
100.0 = 0
0.1
86.8
0.0
83.1 0.0 0.7 # 0.00099
2:28 #: 0.03
IMH
10
40.3
+
4.8 99.8 0.1
0.6
56.7 + 6.8
0.73
96.0
0.00+022
0.2 98.4
0.2 Unk.
Unk.
Usk.
QRB
44:2
2.6
89.7
6.1
20.9 2
91.1
100.0
89.4
96.0
6.1 93.3
0.0 0:37 0.0049
0.77 0.036 Unk.
10
28.9
15.6
15.6
10.0
45.8
100.0 0.0
1.6 59.3 4.7
#6.1
83.0
2 1.0 Unk.
RWMH--R-buse
28.0
6..
34.0
0.2
100.0=0
0.
98.1
0.1 Uak.
Ual.
10
49.5
01.2+-0.2
07.4
89.1
96.9
98.4
0.0
Uak.
Unk.
IMH-R
10-3
49.5
1.6
90.8
34.1
0.8
90.9
0.2
100.0 = 0 89.1
0.2
96.9
0.1
98.4
0.0 Dalk.
Unk.
QRS
10 4.44
9..4
34.1 2 0.2 0.2
100.0 89.1
06.9
0.1 93.4 0.0 0.012 + 0.0055
0.0064 I 0.0048
Table 3: Further comparisons of samplers the "female-science" EBM described in Sec. 3.2.2 We do not compute perplexity for LMH and RWMH without reset as it does not yield 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. *TVD and KL are estimated on independent sets of 10 samples.
Algorithm 2 Estimate AR - 3 mapping
1: Require: P, g, S
for 1,2, ..... N do
I, 4
5:
B, + P(a:)//(x;))
6:
+ Sli] [
7: end for
8: S, + SSrtAscceningg(S)
{Array sorted 3.}
Qunr( [0] +
10: for 1,2, ..., N do
11: B, + S
12: Gauel? [i] x- Gouz Ji - 1] + 3,
{ali] = E j:9,5a 83) {b[i] Σ, [8g Bil
13: bli] -
14: end for
15: for i= 1,2, N do
16: B, + S
17: afi] + Ouur [3]/B
{ali] = E,
18: ARli] + (alt) + b(t))NN
19: end for
20: return AR and S
[S is the 3 at which ARg AR(i]
G Further Comparisons with MCMC
Table 4 shows results complementing those of Table 1 RWMH-base and RWMH-R-bass denote variants of RWMH and RWMH-R that do not use a mixture distribution to inform the local proposal distribution. Moreover, Table 3 shows results for similar experiments performed on sampling from the "debiased scientist biographies" EBM described Sec. 3.2.2 Here, there no obvious way to inform the proposal and therefore, we only use the -bse variants for the RWMH sampler. Furthermore, Tables 5 7 and show a collection of the first. 10 samples produced by the QRS, RWMH, RWMH-R, IMH and IMH-R samplers, respectively.
H Computing Divergences for Two Poissons
Given Poisson distributions and with rates Ao > Xag 0, we wish to find the divergence
20
Pz(x),
p(x))
Dy(p.ps)
Σ
(37)
Za
Px(x)
==U
34

---

Published in Transactions on Machine Learning Research (11/2022)
sumpler
AR
Ramasiin
PPL4
BeIE-BLEU-SL MCnia"
Diat-1t
Ditt22
Dist-31
TVD(x.pg) 4" (RL(P 4
DPG
1
62.8
1 0.4
61.7 1 0.3 85.8 0.1
100.0 1 0
89.3 1 0.1
96.1
94.1 1.1100 0.0
0.87 0.00095
1.91 1 0.04
IMH
10
100.0 t 8
92.0 = 0.7
06.3 + 3.9
59.9 2 0.3
96.3
94.3
Unk.
Unk.
IMH-RR
10-1
100
i 0
00.8
87.1
0.2
100.0
0.2
96.4
0.1
94.4 0..1
Unk.
Unk.
QRS
100.0
01.8 0.8
100.0
0..
0..4
04.3
0.27 0.0064
0.45 0.045 Unk.
10
80.0 + 40.0
00.00.0
21. + 28.5
65.8
91.1
67.2 14.6
Unk.
10
63.2 1 1.3
61.9 1.2 00
100.0:0
0.1
91.3110.11 9. Unk.
Unk.
Unk.
IMH
3
100.0
0.1
Unk.
IMH-R
10-3
100 0 4 0
63.4 1: 1.5
86.7 0:1
100.0
0..
6.
0..3..0.11 Unk.
Unk
QRB
10-3
100.0 + 0
02.8 1.6
86.0 0 0.2
100.0
0..
06.3
0..3
0.01 0.0067
0.011
0.0093
RWMH
10-3
55.7
63.1
Unk.
Unk.
RWMB-R
10 8
100.0 0
S7.7 9.9 87.8
100.0
82.9 0.4
98.2+004
92.4 0.3
Unk.
Unk.
Table 4: Further comparisons of samplers on an EBM with a pointwise constraint to include the word "amazing" in the sequence. We do not compute perplexity for IMH and RWMH without reset as does not yield i..d. samples. As noted, TVD and KT. 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. "TVD and KL are estimated on independent sets of 10 samples.
QRB camples at 10-3 acceptance rata
Doagtrt
atte Perhhyytt1lleem #tragpedrreer by
your asentsing snszteg
[2] Sersen Snlpe
#clordp
got soprecadented
years ago
interesting
Chrlli Helds rendered its seantig vordded, and forr dand within thrne of
loss 1oee, acholarebip blind bretal frong. Oragory Vade accidenally three bystandere, Teaet
4279 tatte ba
the 3 (e alea chece eav socres alscetng 'Sase fata to FuS indience Jaeeptd Jattars alss have rastnng contaner
Seuige beard stay stylish when straggi look like sard. This Dollection nakee your langthening saazing, ther
anler falt, Sota fals
Hell
If you' to corsacted our sponsor, they kow shi you are and hos bard you work. Delose notthe pass vithous postcard. Best Sorved to mees overyshing you demand. Yoo are
aeaning and are
I'n sire lot of people ars west axnteed to nan an F-26 M Mightning IT 92 today hecveee of the asazing tier that's (interatandaaly) in the ingine vous ane that Renzop Cxcherina ie carelcashle, hapey, and eccoesttt.. The lorne teaching. taving childree and sxving time. The ragilariy ucriee with can and ie an smottng :tetseer @ @
comrintr in tull of
The vollien of the russ vas amozing. A soo of complemaat vere good, inclading wow onigthering drossing roo apperancce.. Bo long wezked up info, ny 2014 Hosteng bad loss of special agensng-aeittti
Table 5: The first 10 examples produced in the first run of QRS on the EBM filtering GPT-2 sequences containing "amazing".
RWMH campler 10-3 acceptance
The Bastius Ls cse of the acst unszing anartphozsa we'ne we over tried. It's as exteusely poveziul snartphecs you's 'e naver heard of bufore, and cascies in saszing bastury
1sfe, or hattary 15te it
The Inapine
aze the mort snaxing martghhae un'sn nour trtted It's xn axtrunaly poowrful exartphore you' oo never beard of before, and exrries in aaaxing hattery
155e, or battary 1ife z'm
DaoPlon
wost enezing wourt tphoree we' ever tried. exteenll poverfu) snactphite you've never board of before, and cervics onsning battery
1sfe. battery Life
tzied. extranll postrill spaciphose you' v boaed befcce,
extresely porertul spartphone you's
saszing bactery
The BasBlus
unszing iplosee
unszing baliney
1sfe, hattory 15fa Ite
The Ihatius
aest snazing martptanae we'ne sver tried. It's extrenlly porerful eaartphone you' 'oe never beard of befere, and carries saazing bactery
lsfe. battery life I's
The Diael is of the wast snening swrtgtttes us' too over tried. It's at extrenlly pocerto) eaartphine you' vo never heard of before, and carries in saxsing battery
15te, or hartwry 15ta the
The Bastius ia ase of the acst enezing sour tphonse we'ne fo your tried. It's us estruslly poveziul amartphone you's ve naver heard of before, and caspies in usszing bastery
Life, oz battues life I'm
aze the mort snaxing martpphmas un'ea nour txted. It's xs extranaly ponerful eaartphone you' oo never beard of bafore, and exrrtes to saaxing battery isde, battary life z'm
The Imabinn
The Bnatius
the aost snaxing aaattpbezes wa're over tried. It's as exteensly povertul saartphone you's ve never beard badors, and careies saszing battery
15te, hattery
Table 6: The first 10 examples produced in the first run of RWMH on the EBM filtering GPT-2 sequences containing "amazing".
35

---

Published in Transactions on Machine Learning Research (11/2022)
RWMH-R sampler at 10 acceptance rate
pogtst this gone le amseing! 11S1 osol plysical ooi Ei oction gou vauze you plas a bardened jaskie with es old giclCrisod vio'o inuh in the immediase attemntt of the thrrct shurdosn, strange and aften anazing eveats raised the queation of shesher the geverneent and ever given up its restrictive costrol of religious provesations for political purpones and usmumed aev politicai. lentership
bad un snszing out of 10, out of 10, 9 30, e anazing S... 1ized it... the stoes... must/comphaee soteaaadd-aaaactte
partiontar, eysnlr bettdiing wot racondary
"Bhe tay
played "Feisuda," "t
usugo thet loved Iowe that's amszing," Kleste said. "Thy ochmellogging cesponsibll thenes.
passionate this
thase need these are distracted
work the Beadez Space Foundation, vhick Kcuturs artists sho make biearre 776175 3, saaxing / / a 5 ( 776265
ostaide world.
i 77574
Ve insptred the
global uxdience thrvugh kaovledge,
and advceacy.
It's mads
the caranoos is saaning the any to this being classte, a true black lace hra sade free di 's, Tach and all the rabetie that are sostlacla tn pine and black. on, bane scee trust, regae, sicautne, Setngg shiager, vor, good for you
and it to only using standard ruies of thinb, but it in smazing that all the use of can be tacen faco account.
essabl inked.
with to may seantig actors agpearing or avery lavel to a ssone onos ih's rileed, Bear Vare Rabale follows the Rabal 1ion shronghont 2017 with in mosea) anchive of credits from the originel and Rebala twe Cants.
Table 7: The first 10 examples produced in the first run of RWMH-R on the EBM filtering GPT-2 sequences containing "amazing".
IMH samples 10 acceptance
17 ALL, The Verifiers she voted for teages Quast Bavanted, tro seazing chotces are going to still be in the fire. To sake up for the lest dapth, Vaicase will mate a basy M0 anter tasted, protecting the lab tree detection by pribiatic prodectes is asaning (e))) yaans ago, actantiata fornd the comsbbnniddbhhneirr dreg it veepontbbe
You have sarches The Nircher 3 as a 2id. You leve cates pleaty of seat at your menio. You's 've aves video gune show beforv that has bean smscing. Tuy fer people heve
geven up without
11 ae Spe 230-701-4p00 701-570777 to lift ResTT, larated is Vastington, D.C. do you have nore quastionz sboot lifting sonathing seazing to the Farn 600 se(
Bringing this gift is unique ipprtusity to shere with your loved oses abous the hove vo love. Our Comily stuese cloud of feollock aad the seuly taazing bandadde iseno we
came upos inolused, peaciding a greas
Drez group of baseteer antiarissts gutbered for beez aampling on Hedasaday acrzing, they shared sime arazing bonsbeew pecipes with beer uutbusisats on the ceaft beez of the weskand. will aoes atur beavers hess
RIDEX VIDEITA2g 1803 SEVERLY 10 APAIK pasod to pessusi you the usecing R4D20 crailuble Live BCN Hollysood: hitp://vew personsluuii
with commusia, scroobol Polilare Center
bilborrtting sutboro planers Connettin friends fimily, live with family of vue vosderial cnssing people (Pe Albury
lened
veloriing shee. They love amazing aves perdyully e 20e0 it'a troe that simest every persez touching your skis is uader their oas skin, bas wbsu you here costribuse, you see competing agoima azt Lizat.
Play
Bax Career Missonta full different, seaning leabiar gay couplen
It's awasing
Table 8: The first 10 examples produced in the first run of IMH on the EBM filtering GPT-2 sequences containing "amazing".
IMH-R camples 10 acceptance rate
Jourasy to Haza! Especusasive Black Hols Becovered Fres Sig Bane Boostts Bky e + Lt took in seazingly pevere situaticn to produce in saszing IDI image through single zvccubination vith nassire sudio uplisk
Backy in the croditu guns Sid Meier looked over Bandi with has saagly vacited fuce. e MMaci if," be uvurted, "Il you thisk Randl's i doing cnszing things to
Mhile Gilinta tells everyboly whas she has is cind in the pest, ossive thst desgate ile Maez conpesataeeeese and anscing atbloticion, they de ostlive the fooioo and don't
recogrize are motber (e] [2) (e)
neoral batraancerr from Progue DIe), this wan't blast. It use aostoes. My test tass sar asoxing [Cle] you was againet ar soses that
Lest day was so snazing. I vas going to lay dova for sous bucch on the park dock and watch contestants go satu. Happy nocning e a Paychos Solid: Visning the Supez Book
ten
Ous Ceotonurs Genscacion Supurtt Field Treeher T Well, it Looko like it's gams be well saben care of .. Josnting cea alse uppreeslly utilive compiled oound block and got orne asozing gien
86 Erplicis Bor 15, 2016 FIVE us 2005 concuuscons Saturday sight you'll find as amaziag bunch colleges and mivernitien alike as they bost the "HE LAST Tiae'' pansi
foz
Pick saything you wish for appeass in ner like Black Bag havenge, Berage Coust, Bride Valboa. Dianibor and much meee Doneriin of The Mooth Biar Trude Baply wus olde to Cleg dova oue during the lest few kilonwtew and bers the pover happy about 6o for while, since cas Like thes becouse the fost thet the boastifal side bas proves amecing sakeo uuee leazsod to love then zore and Locking
At e miles zu, the Gudaver bunge on smssingly bocuted cange willis Kaskhan counly,
Table 9: The first 10 examples produced in the first run of IMH-R on the EBM filtering GPT-2 sequences containing "amazing".
36

---

Published in Transactions on Machine Learning Research (11/2022)
As (x) is increasing in 2, for any fixed B >> 0 and nonnegative integer we have p(1) S (q(x))
< (Lp/Ag) Bexp(Ap Ag)
x S k
where
Ap Xy + log log Xp Xxg)
Thus the partition function appearing in Eq. 37
00
Zp
Σ min (p(1),
Σ p(1 + Σ g(i) = Fx, (k) + 3(1 - (x)
i=++1
where Px is the cumulative distribution function of a Poisson of rate X.
Given this value Zp, the f-divergence in Eq. 37 may now be approximated by truncating to n terms for suitably large n, provided the convex function does not grow too rapidly:
Pa(x)) f
p(z)Zx
Dy(p.Ps) =
Z3
(5(x)
Importance Sampling and Variance
In this work, we perform many IS estimates of quantities such acceptance rate, TVD and KT. divergence. We report variance estimates computed using the bootstrap estimator for the experiments on debiasing scientist biographies (Sec. 3.2.2) and other EBMs reported in Appendix A in Table 10 We report mean + one standard deviation for B values within the range used in our experiments (also see Table 2). We find our estimates to be accurate within reasonable variance.
Secondly, noted in Sec. 2.2 it not generally possible to compute Z its variance for any given EBM with certainty. This observation however, that when we can bound P(x)/q(x) we can have formal bounds on these quantities, allowing to double-check the accuracy of these estimates. In particular, this is possible when P(x) a(z)b(z), g(z) = a(x) and (xx) E [0, M), as in that case we have P(x)//(x) < M. Using Popoviciu's inequality PPopoviciu 1935 J we know that
put into question the validity of the above-described estimates. We note,
P(x) ((x)
M
Var
<
(38)
4
and thus, the IS estimator of Z has variance
N
P(a:)
M
Var
<
(39)
N (xx;)
4N
We generated 1M samples with GPT-2, and used them to compute the partition functions of the EBMs for pointwise constraints, with provable bounds on their variance following Eq. 39 For the 100% "amazing" EBM, obtained Z 2.5 x 10-3 3 + 2.5 x 10-7; whereas for 100% "wikileaks" we obtained Z 1.5 + 2.5 x 10-7 These are in agreement with the estimates in Table 10 However for experiments with distributional constraints, we determinined the rather large bound M 304868, and we would need to gather al least 1002 samples to obtain a reasonable bound on the variance. This highlights the need for better proposal distributions to compute these quantities, especially considering that the number of samples that IS ncods to compute partition function of P(x) inversely proportional to cxp (p. q)) (Chatterjoc and Diaconis 2018). This the reason why, in practice, good proposal distribution can allow us compute accurate estimates, even if that comes at the loss of the above-described formal bounds.
37

---

Published in Transactions on Machine Learning Research (11/2022)
TVD(p.Pu)
(p
7.8 7-8 1322
0.0
0.05 0.00
1,2
10
0.01 10-3
0.01 0.13 10
7-4 x 10
0.122.1
0.3
0.6 0.03
100% wikileake
0.01
8.5 10
10-a
+.002
26.8 8.2
23..
1.9
10
10-4
10-4
x
0.01 1.5xx 10-6
6 x
2 10?
x11x100 +1.5 10-8
2.7 10 4
-1.7x10"
T.X 103
0.08 1.7x 10-4
0.3 10-3
0.000003
50% femmle 100% science
165
10x10-110 23.5 10-5
0.07 207=7.11 10-3
0.00
4.9
10-3
10a
sporte
7:5
0.a1 233 10
0.04 1 3.8 10-3
0.04 204 10
1.2 107
6.5 4 10
1.2 43.2x10
4.2
5.3.6
0.02
100% smastng
0.3
2.5 10 22.3
7.8 10- 1322
1.2810 1
7.4 10-4
0.1+2.1
100% wikileaka
1. 14xx10-4214x00
0.2
8.2x 116.610
x 102
2 10
0.01 1.8 1
103
X. 103
0.08 1 1.7.1. 10-4
50% Temale
100% scieuce
106
x
3 x
1.3 10- 11000
16.
1 1.3
apocta
7.5. 16f
x 6
0.01 4 3.5
107
8.5 1
Table 10: Means and standard deviation of IS estimates of acceptance rate, TVD with the target distribution and KL divergence to the largel distribution for various on various EBMs using DPG fine-tuned proposal. We perform 5,000 bootstrap simulations using 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 Table
38

---

Published in Transactions on Machine Learning Research (11/2022)
Estimating Z: example with finite mean and infinite variance As mentioned in footnote 6 the variance Varz~a P(x) may be infinite. For instance, if and q are distributions satisfying P(x)² ( on
q(z)
support I = 0, 1..,. then
P(x)2 E B ((0)3
(())
000
z=0
As the variance is the mcan-square minus the squared- mean, it too is infinite. The condition p2 q holds for appropriately normalized geometric distributions p(x) a and q(ar) a² for any < <.
J About the Metropolis- Algorithm
Robert and Casella 20044 Theorem 7.4, p. 274) prove the following theorem, with f the target distribution.
Our motivation for reproducing this result is to emphasize point (ii), which especially relevant in the context. of this paper.
Theorem J.1. Suppose that the Metropolis-Hasse Hastings Markov choin (x(9) is f-irreducible.
(i) h h is an f-integrable function, then
lim T-00 T -(x() / h(x) dz
almost surely.
(ti) If. in addition, (X(9) is aperiodie, then
lim TVD (5, / K" Km (x, u(dr)) 0
for every initial distribution μe, where K (x, denotes the kernel for transitions.
Property (i) says that the average over the first elements of single chain converges to the expectation of h()) for x ~ f, as T increases. Property (ii) concerned with the TVD between the target distribution f and the distribution obtained by repeatedly rumning an n-step chain and outputting the th element the resel (-R) variant of the MH algorithu that have denoted by RWMH-R or IMH-R. This distance converges to zero increases.
K Arbitrarily Slow Proposal q
We assume that X = N 10,1,2..... that p has full support and is strictly decreasing over
Theorem K.1. Let g (c) + (0, 1] be a strictly decreasing continuous function with limg g(3) = Then there exist a real number 3o and proposal probability distribution q over N such that the QRS distribution Pa for larget p satisfies
TVD pa) 2 ((3)
for all 3>6 So.
(40)
tribution associated to p and q at B.
Proof. See below.
In other words, whatever the "slowness" with which g(B) decreases 0, we can always find a proposal q that guarantees that, asymptotically, TVD(p,ps)) decreases even more slowly
39

---

Published in Transactions on Machine Learning Research (11/2022)
m())
m(1)
m2
(3)
((0) F(1)
(
((3)
Figure 13: Illustration of Lemma K.2
Proof sketch
The proof, which we only sketch, is based on two lemmas.
Lemma K.2. If q is distribution over N with full support, let V/ = {i E N p(x)/q(x) 2 B}. Let h(8) be any strictly decreasing continuous function from (0, 00) to [o, 1), such that lim h(8) = 0. Then there exist some q and 31 > 0 such that
8231
p(VB) 2 1(3).
Proof. For x E N, let m(x) = p(f2, x + 1....)) and B(x) = inf h(3) S m(x)]. This casily seen imply that h(3(z)) = m(x) and that B(x) is strictly increasing (see Fig. 13 Then construct distribution over 10, such that for some To 2 1, and for any x 2 Io, one has g(x) B(++1) and we set 31 = (rro) We note that the intervals [3(x0), ((z0 + 1)), [8(x0 + 1,, +)),.... cover the whole interval [To, 00). Then consider some integer k z0 and take in the interval [B(k), B(k 1)). For æ 2 k, we have p(z) = B(x + 1) 2 8(k + +) 2 3, hence x E Vg. But p(kk + 1,...)) M(((k) Z M(3), hence
p(a)
((2)
p(V3) 2 (33).
Lemma K.3. Let be distribution over N with full support, and let W3 = for e N p(x)/g(x) 2 33}. Then there erists a real namber B2 > 0 such that
B B26 82
TVD(p. pB) 2 2W
Proof. We have
pa(x) p(x) (Bq(z)) p(x) (1 IA (30(e)))
Zg Σp(a) (Bq(z))
Zg
Zg
p(x)
Hence, for I E Ws,
[ g(x)
(2(x)
1
p(x)
1
p(x)
ZB
3 3
Let Bg > 0 be such that B 2 B2 + Zg > 0.9. (It is easy to see that such a .3 exists, as Zg is increasing in B
and converges to 1.) Then for $ 2 A2 and for Ws, we have ps(a)
p(x) 3x0.9 I 2, so that
plx) pp( =(x)) (1 Pn(x))
p(x)
p(z)
2
and therefore TVD(p.P2) = Expto - p2(x)) 2 (/2)
18rThese conditions WLOG, as can easily be checked.
19 Based on the properties proved in the paper, we know that eventually TVD(p.Pg) decreases
40

---

Published in Transactions on Machine Learning Research (11/2022)
Proof of Theorem K.1 From these two lemmas, the proof of the theorem follows casily. Indeed, let h(3") =
g (3)). For 3' = 3 3, we have Wa VVr, and therefore, by Lemma K.3 TVD(p.Pa) 2 (V
for 3 2 $2. By Lemma K.2 we have p(V²) 2 h(3") = 2g(3) for 8¹ 2 81. so that TVD(p, Pp) 2 ( for B
large enough that ( I 1/2, and we conchude.
41


Reviews:
[{"review_id": "ZpQ6YCWkNA", "reviewer": "Reviewer_paAR", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: \n\nThe authors emphasize a lot on the f-divergence which is new for discrete energy based models. The idea is clearly presented and the convergence analysis is established in the appendix. \n\nWeakness:\n\nIt seems that Metropolis-Hastings is an relative old algorithm, which is used as the bench mark in the experiments. The authors did mention about the continuous model and algorithms, which seems to not imply application in NLP. My only question here is the following: does the exiting continuous model work for the NLP with some adjustment in the experiment?  (The author said: \"none of such prior work has so far  directly addressed NLP applications\"). If the continuous model does work, could the author compare with those to show the powerfulness of the QRS? From my understanding, the divergence and convergence of continuous model, e.g. Langevin based algorithms, is quite powerful and well-known. Can the authors compare more why the f-divergence is new and the main difficulty compared to the continuous model here? ", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors propose to study the quasi-rejection sampling to generate samples from discrete data. The main advantage is that the authors can compare the general f-divergence between the sample distribution and target distribution, which provides estimates about how good the samples are compared to the target distribution. Several examples are provided. The proposed algorithm seems to work well in NLP and does over perform existing algorithms, like the well-known  Metropolis-Hastings algorithm. The analysis of the convergence and the estimate of the desired  quantile seems to be the new theoretical contribution.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "The main questions is about the experiment for QRS. Can the authors compare QRS with more recent algorithms, and show that it is the state-of-art in the discrete EBM. Is it possible to compare QRS with continuous model algorithms that haven been mentioned in the discussion. ", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "a4G1RBtHMA", "reviewer": "Reviewer_ZGKb", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n* The proposed method is straightforward and sensible. A major benefit of the proposed method over existing sampling methods is tractability of divergence diagnostics and improved sampling efficiency compared to standard rejection sampling. This comes at the cost of approximate sampling, which can be quantified with divergence diagnostics and which appears to be close to the true distribution in experiments.\n* The paper provides nice development of theoretical properties, in particular the result in Theorem 2.2 that increasing $\\beta$ strictly improves the approximation of the target distribution.\n* Experimental results show solid performance for fine-tuning language models to produce specific outputs. Plots in Figures 3 and 4 show that the divergence diagnostics are useful for measuring the approximate convergence of the sampler across different settings of $\\beta$.\n* Reasonable comparisons are made between QRS and existing MCMC methods, specifically Random Walk MH and IMH.\n\nWeaknesses:\n* The method relies on the existence of a good global proposal distribution, which limits its utility as a general-purpose sampler. However, the language modeling setting provides a strong example of a situation where using an EBM to fine-tune a global proposal provides significant benefits.\n* The title is somewhat confusing. It seems to imply that divergence diagnostics are used for sampling, instead of being available after sampling to assess the sampling results. It might be good to mention \"approximate rejection sampling\" or something similar in the title.\n* The baseline IMH approach gives very similar performance to QRS across the metrics investigated. The main benefit of QRS over IMH is the ability to calculate divergence diagnostics. The paper investigates a lower-bound for the TVD that results from sampling with IMH, but this lower bound is nearly identical to the TVD from the QRS diagnostic. Thus, there is no direct evidence in favor of applying QRS instead of IMH. Nonetheless, IMH is still incompatible with easily-obtained divergence diagnostics. A clear case where QRS outperforms IMH in divergence diagnostics would strengthen the paper, although I can still see the appeal of QRS over IMH from the perspective of straightforward diagnostics.", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work proposes a relaxation of rejection sampling, called QRS, that replaces the strict upper bound for the proposal distribution with an approximate upper bound. The use of an approximate upper bound allows the method to be applied in cases when a true upper bound is unknown, and can greatly increases the efficiency of the sampler at the cost of accuracy compared to classic rejection sampling. Moreover, the QRS method can provide approximate divergence diagnostics that allow the user to estimate the sampling error incurred from using an approximate upper bound. The divergence diagnostics provide a way to trade off between accurate approximation of the target distribution and sampling efficiency. The QRS method is applied to sample from language models using a large pre-trained model as an initial proposal distribution. Experiments show that QRS is able to effectively fine-tune language models to produce outputs that are compatible with user-defined criteria such as gender parity and inclusion of specific topics. The divergence diagnostics show that the method is able to strike an effective balance between sampling accuracy and sampling efficiency, with the notable ability to gain speedup of an order of magnitude or more with only slight loss of sampling accuracy.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "Significant Changes:\n\n* It would be helpful to show the results of a MCMC and IMH for the toy Poisson experiment for baseline comparison vs. QRS.\n\nMinor changes:\n\n* First paragraph of Page 1: \"Such models map elements of the sample space to non-negative scores.\" The \"non-negative\" part is not true in general, as energy functions can often take on negative values (especially in the context of the 2006 LeCun paper where the energy function is not necessarily probabilistic). The unnormalized density $e^{- E(x)}$ is non-negative, but the energy function $E(x)$ might be negative.\n* Algorithm 1: might be helpful to indicate that the algorithm will return the samples $x$ as the final output (maybe change \"While True do:\" to \"While num_samples_generated < num_samples_target\")\n* Page 4 top: change \"contains many discrepancies\" to \"contains many common divergence objectives\"\n* Section 3.2.3 Baselines paragraph: typo \"focussing\" instead of \"focusing\" ", "broader_impact_concerns": "The authors sufficiently address ethical concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "pOdFWJD4aU", "reviewer": "Reviewer_6dL8", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I found the theoretical component of the paper to be thin, as there is essentially no quantitative justification for the procedure. I do find the theorem on monotonicity of the f-divergence as a function of β to be interesting. The current proof, based on the spread lemma for convex functions, is mysterious to me. I propose an alternative proof based on calculus (the proof assumes that f is differentiable, but I believe that this restriction can be lifted via approximation arguments), see https://drive.google.com/file/d/17ZFUnGBdzhDnC6r6WEPIznRX68N2YzAI/view?usp=sharing.\n\nAlthough the use of QRS is motivated by the importance sampling estimators for the f-divergence, in general I believe that the variance of these estimators typically scales exponentially with the size of the state space. This to me seems like a serious disadvantage of the proposed algorithm. Also, since QRS is simply an approximate form of RS, it shares its shortcomings. Namely, the acceptance probability of RS is often too low to be practical; although QRS can increase the acceptance probability by setting β to be small, it does so at the cost of sacrificing sample quality (and this is not quantified well in this work). To counter this point, the authors claim that neural networks can provide good global proposals for RS and QRS, but this is rather handwavy and unsubstantiated.\n\nI find the experiments to be a strength of this paper, since they demonstrate well that in certain applications QRS can be effective. Also, I’d like to add that the paper is extremely well-written. My main doubts lie in whether QRS is useful more generally.\n\nOverall, although QRS is fairly natural, I feel that this paper could benefit from further investigation. For example, perhaps the authors could further investigate QRS in some simple test settings in order to investigate more quantitatively the trade-off for the value of β, the variance of the importance sampling estimators, and comparison with mixing times of natural Markov chain algorithms. Besides this point, I feel that some of the limitations (e.g., that non-adaptive RS is typically not used beyond simple settings) are not discussed well.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors study quasi-rejection sampling (QRS) for discrete distributions. QRS is akin to rejection sampling (RS), except that the scaled proposal may be improper, i.e., may not be a global upper bound on the unnormalized target distribution. This means that unlike RS, QRS is not an exact sampler. Nevertheless, the authors motivate the use of QRS because it leads to higher acceptance ratios. By tuning the value of a parameter β which controls the degree to which the scaled proposal is improper (letting β tend to infinity, one recovers RS), one can achieve a trade-off between the computational complexity of the algorithm (related to the acceptance ratio) and the quality of the sample (how close it is to the target).\n\nThe other motivation for QRS is that unlike Markov chain Monte Carlo (MCMC), by using importance sampling estimates together with the explicit proposal, one can obtain estimates on the f-divergence of the output from the true target distribution. This addresses the important practical problem of obtaining convergence diagnostics for sampling.\n\nAlthough there is no theoretical guarantee for the accuracy of the sample as a function of β, the authors do prove the non-trivial fact that the f-divergence of the output of the sample to the target decreases monotonically as a function of β. The approach is also validated with experiments on real-world data.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "Please discuss the limitations of RS and importance sampling further. Are there simple assumptions which entail that the TVD between p_β and p goes down as an explicit function of β, e.g., at rate 1/β?\n\nFor the definition of the f-divergence in eq. (1), this is only valid if p_1 is absolutely continuous with respect to p_2, or if f grows superlinearly. In the case when f grows linearly at infinity, which is the case for the TV distance, one needs to add an extra term consisting of f’(∞) times the measure under p_1 of the set {p_2 = 0}. (In the current definition, one can see that if p_1 and p_2 have disjoint supports and the f-divergence is the TV distance, the formula (1) yields 0 but the true TV distance is 1.)\n", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: All three reviewers were satisfied with the revision and are in favour of accepting the paper. Congratulations.

For the camera-ready version, I would like the authors to consider the following two minor requests:

1. Algorithm 1 may need updating as the counter "num_samples_generated" is not incremented in the loop and the hyperparameter num_"samples_target" is likely missing in the list on the first line.

2. In Sec 3.2, I would suggest that you include a brief sentence on the connection to maximum entropy models. You currently refer to the work of Khalifa et al, 2021, which is certainly the main reference, but given the similarity to maximum entropy models, a brief sentence on this connection is likely useful to the reader.

Decision: Accept (poster)