Estimating Gradients for Discrete Random Variables by Sampling without Replacement
Authors: Wouter Kool
Herke van Hoof
Max Welling
Venue:  (2020)
Keywords: gradient
estimator
discrete
categorical
sampling
without replacement
reinforce
baseline
variance
gumbel
vae
structured prediction

Abstract: We derive an unbiased estimator for expectations over discrete random variables based on sampling without replacement, which reduces variance as it avoids duplicate samples. We show that our estimator can be derived as the Rao-Blackwellization of three different estimators. Combining our estimator with REINFORCE, we obtain a policy gradient estimator and we reduce its variance using a built-in control variate which is obtained without additional model evaluations. The resulting estimator is closely related to other gradient estimators. Experiments with a toy problem, a categorical Variational Auto-Encoder and a structured prediction problem show that our estimator is the only estimator that is consistently among the best estimators in both high and low entropy settings.

Published as a conference paper at ICLR 2020
ESTIMATING GRADIENTS FOR DISCRETE RANDOM VARIABLES BY SAMPLING WITHOUT REPLACEMENT
Wouter Kool University of Amsterdam ORTEC
Herke van Hoof University of Amsterdam h. C. vanhoof@uva.nn
Max Welling
University of Amsterdam CIFAR m. we www.weennuuaa...mmmmmmmm nl
W. w. w.m. kool @uva. nl
ABSTRACT
We derive an unbiased estimator for expectations over discrete random variables based on sampling without replacement, which reduces variance as it avoids duplicate samples. We show that our estimator can be derived as the Rao- Blackwellization of three different estimators. Combining our estimator with RE- INFORCE, we obtain policy gradient estimator and we reduce its variance using a built-in control variate which is obtained without additional model evaluations. The resulting estimator is closely related to other gradient estimators. Experiments with a toy problem, a categorical Variational Auto- Entoder and a structured pre- diction problem show that our estimator is the only estimator that is consistently among the best estimators both high and low entropy settings.
INTRODUCTION
Put replacement in your basement! We derive the unordered set estimator an unbiased (gradi- ent) estimator for expectations over discrete random variables based (unordered sets of) samples without replacement. In particular, we consider the problem of estimating (the gradient of) the expectation of f() where has discrete distribution p over the domain D, i.e.
Ex- [f(x) = p(z) f(x).
(1)
This expectation comes up in reinforcement learning, discrete latent variable modelling (e.g. for compression), structured prediction (e.g. for translation), hard attention and many other tasks that use models with discrete operations in their computational graphs (see e.g. Jang et al. (2016)). In general, æ has structure (such as sequence). but we can treat it 'flat' distribution. omitting the bold notation, so x has a categorical distribution over D) given by p(x), x D. Typically, the distribution has parameters 0, which are learnt through gradient descent. This requires estimating the gradient Ee [f()), using set of samples S. A gradient estimate e(S) is unbiased if
Es(e(S)) V (e)
(2)
The samples S' can be sampled independently or using alternatives such as stratified sampling which reduce variance to increase the speed of learning. In this paper, we derive an unbiased gradient esti- mator that reduces variance by avoiding duplicate samples, i.c. by sampling S without replacement. This is challenging as samples without replacement are dependent and have marginal distributions that are different from p(x). We further reduce the variance by deriving built-in control variate, which maintains the unbiasedness and does not require additional samples.
Related work. Many algorithms for estimating gradients for discrete distributions have been pro- posed. A general and widely used estimator is REINFORCE (Williams) 1992). Biased gradients based on continuous relaxations of the discrete distribution (known as Gunbel-Softmaa or Con- crete) were jointly introduced by Jang et al. (2016) and Maddison al. (2016). These can be com- bined with the straight through estimator (Bengio et al. 2013) if the model requires discrete samples or be used to construct control variates for REINFORCE, in REBAR (Tucker al. 2017 or
"Code available httress///ttthaa..ccoooooeeeeeee ingraa wtw.rraattttttttttttttteee www.sstot---rppaaceeeee

---

Published as a conference paper at ICLR 2020
RELAX (Grathwohl al. 2018). Many other methods control variates and other techniques
to reduce the variance of REINFORCE Paisley et al., 2012: Ranganath et al. 2014 Gregor et al.,
2014
Mnih & Gregor 2014 Gu al. 2 Mnih & Rezende 2016).
Some works rely on explicit summation of the expectation, either for the marginal distribution (Tit-
Sias & Lázaro- Läzaro-Gredilla 2015) globally summing some categories while sampling from the
mainder (Liang et 20.11018: et al.) 2019). Other approaches use finite difference approxima-
tion the gradient (Lorberbom et al.) 2018 2019). Yin et al. (2019) introduced ARSM, which uses multiple model evaluations where the number adapts automatically to the uncertainty.
In the structured prediction setting, there many algorithms for optimizing a quantity under sequence of discrete decisions, using (weak) supervision, multiple samples (or deterministic model evaluations), or combination both (Ranzato et al. [0166] Shen et al., [2016] He al. [0166] Norouzi et al., 2016 Bahdanau et al., 2017 Edunov et al.) 2018 l Leblond et al. [018 Negrinho et al. 2018).
Most of these algorithms are biased and rely on pretraining using maximum likelihood or gradually transitioning from supervised reinforcement learning. Using Gumbel-Softma based approaches sequential setting is difficult as the bias accumulates because of mixing errors
(Gu et al. 2018
2 PRELIMINARIES
Throughout this paper, we will denote with B ordered sample without replacement of size and with S an unordered sample (of size k) from the categorical distribution p.
Restricted distribution. When sampling without replacement, we remove the set C C D already sampled from the domain and we denote with PMC the distribution restricted to the domain D D\O. C:
p(x)
(x)
--Ecc ((c) DEDIC.
Ordered sample without replacement B². Let B = (b)...., bw). by E D be an ordered sample without replacement, which is generated from the distribution as follows: first, sample b p, then sample b2 ~ PV(B),, by ~ = p)( etc. i.e. elements are sampled one by one without replacement, Using this procedure, B* can be seen (partial) ranking according to the Plackett- Luce model (Plackett 1975
Luce 1959 and the probability of obtaining the vector B is
p(b))
p(BB)
II
p D.B B (b.)
II
(4)
rb,))
We can also restrict 8* to the domain D \ C, which means that b & C for k:...:::
k
(l)(b.)
* II
p(b:)
(B = II - E ((0(b)
(5)
1- Σ p(c) - Σ p(b))) EEC
JCL
J&L
Unordered sample without replacement. Let D be an unordered sample without replace- ment from the distribution p. which can be generated simply by generating an ordered sample and discarding the order. We denote elements in the sample with S* (so without index) and write B(S*)) as the set of all k! permutations (orderings) B* that correspond to (could have generated) S It follows that the probability for sampling S given by:
p(b))
p(Sh) = Σ P(BB) Σ
II
II p(s) SESK
Σ
II
Eb))
Σ jat
p(b)))
B*EB(St)
BkEB 1=1
BBEB(Sk)
The last step follows since B* BBSk) is ordering of Shk such that 11 p(b:) 1L p(s)
Naive computation of p(5*) is O(k!), but in Appendix B we show how compute it efficiently.
2

---

Published as a conference paper at ICLR 2020
When sampling from the distribution restricted to D \ C, we sample S _ ED\ C with probability:
p (Sc
P(()) WESE
p(s)
Σ B B
Σ p(c) -
p(b))
cEC J2t
The Tombel-Toopk trick. As an alternative to sequential sampling, we can also sample B* and S by taking the top &o of Gumbel variables (Yello 1977 Vieira 2014 Kim et al. 2016). Following notation from Kool et al. (2019c), we define the perturbed log-probability Jo. = Φs + 9i. where 96, etc.,
Φ = log p(i) and gi Cumbel(O). Then let 6 arg maxieD 9s. b2 arg m
so Bk is the top k of the perturbed rog-robbbbilities in decreasing order. The probability of obtaining BR using this procedure given by equation 4 so this provides an alternative sampling method which is effectively a -on-diiferentiable) reparamcterization of sampling without replacement. For a differentiable reparameterization, see Grover et al. (2019).
follows that taking the top k perturbed log-probabilities without order, we obtain the unordered sample set S This way of sampling underlies the efficient computation of p(S*) ( in Appendix B
3 METHODOLOGY
In this section, we derive the unordered set policy gradient estimator: a low-variance, unbiased estimator of [= based on unordered sample without replacement Sht First, derive the generic (non- coon-gradeent estimator for [x)) the Rao-Blackwellized version of single sample Monte Carlo estimator (and two other estimators!). Then we combine this estimator with REINFORCE (Williams) 1992) and we show how to reduce its variance using built-in baseline.
3.1
AAO-BLACKWELLIZZATIOO OF THE SINGLE SAMPLE ESTIMATOR
A very crude but simple estimator for [z) based on the ordered sample B is to only use the first element b, which by definition is sample from the distribution p. We define this estimator as the single sample estimator, which is unbiased, since
E BB) [f(b]] En)- [f(b)) E Em-m())((()))
(8)
Discarding all but one sample. the single sample estimator is inefficient, but we can use Rao- Blackwelizzation (Casella & Robert 1996) to signficantly improve it. To this end, we consider the distribution B*1 which is, knowing the unordered sample Sh the conditional distribution over ordered samples Bh B(5*) that could have generated S Using B*|
we rewrite (b) as
E. B* ~p(( [fbb) E.stxp(St)
[E s*) [bbb))]] ~p(s") (p,, (S*) [sbb))]]
The Rao- woo-Blackwellized version of the single sample estimator computes the inner conditional ex- pectation exactly. Since B* is ordering of 5* we have bN 8 and we can compute this as
E Ep (st) [f(b))]
Σ aESt
P(b s(s))((s)
where, in a slight abuse of notation, P(b = =|S5*) is the probability that the first sampled element by takes the value 8, given that the complete set of samples S* Using Bayes' Theorem we find
P(h = = p(S s)) =)
PV {s))p(s)
(10)
P(Sk)
p(Sk)
The step p( = 8) = pS {+}) comes from analyzing sequential sampling without replacement: given that the first element sampled is the remaining elements have a distribution restricted to D ({{ss), {s), ,. so sampling s (including s) given the first element s is equivalent to sampling
the remainder 5 \ {s} from the restricted distribution, which has probability p P (s}) (see
equation 7
Note that |* is Plackett- Luce distribution restricted S*!
3

---

Published as a conference paper at ICLR 2020
The unordered set estimator.
For notational convenience, introduce the leave-one-out ratio.
Definition 1. The leave-one-out ratio of w.r.t. the set S is given by R(S 8) = P (S
p(8*)
Rewriting equation 10 as P(b1 = $|S*) = p(s) shows that the probability of sampling first, given S is simply the unconditional probability multiplied by the ona ratio. We now define the unordered set estimator as the Mao-Blackwellizer version of the single-sample estimator.
Theorem 1. The unordered set estimator, given by
(USh P(S)R((S 88)(s)
(11)
SESk
is the Rao-Blackweliized version of the (unbiased!) single sample estimator.
Proof. Using P(b, = +|5*) = P(s)))((5+ .) in equation 9 we have
B [nn))[((b]]]
Σ
P(b1 = s|s))
E p(s) ss)(ss) SES*
(12)
SESt
The implication of this theorem that the unordered set estimator, in explicit form given by equa- tion II is an unbiased estimator of [x)) since it is the Rao- Aho-Blackwellized version of the unbiased single sample estimator. Also, as expected by taking multiple samples, it has variance equal or lower than the single sample estimator by the Rao-Blackwar Theorem (Lehmann & Scheffe 1950).
3.2 RAO- BOO-BLLCCWELLIZATTEE OF OTHER ESTIMATORS
The unordered set estimator is also the result of Rao-Blackwellizingg two other unbiased estimators: the stochastic sum-and-sample estimator and the importance-weighted estimalor.
The sum-and-sample estimator.
We define as sum-and-samee sample estimator any estimator that relies
on the identity that for any C' D
Σ p(c)f(c) (1-E(( p(c) f(z)
E Expp(x) [f))(=)](()]] [Bae)))]Eeepppeoo (xo
(13)
NEC
For the derivation, see Appendix C.I or Liang et al. (2018): Liu al, (2019). In general, a sum-and- sample estimator with a budget of I evaluations sums expectation terms for set of categories C (s.t. CC| < k) explicitly (e.g. selected by their value f (Liang et al., 2018) or probability p (Liu et al, 2019 and uses k- Cl (diwn-weighted) samples from D C to estimate the remaining terms. As is noted by Liu et al. (201)), selecting C' such that 1-E.so p(c)
k-|C| is minimized guarantees to reduce variance compared to standard minibatch of samples (which is equivalent to setting C = 0). See also Fearnhead & Clifford (2003) for a discussion on selecting C optimally. The ability to optimize C' depends on whether p(c) can be computed efficiently a-priori (before sampling). This is difficult in high-dimensional settings, e.g. sequence models which compute the probability incrementally while ancestral sampling. An alternative is to select C stochastically (as equation [3] holds for any C),, and we choose C' Bk-1 to define the stochastic sum and sample estimator:
SSAS (B²) = Σ ((b))((b))) + (1 E-Ere 1=1
K-1
k-1 Enty,))) p(b)) [(ba). j=1
-
(14)
For simplicity, we consider the version that sums k - 1 terms here, but the following results also hold for version that sums k: m terms and uses m samples (without replacement) (see Appendix Sampling without replacement, holds that by g Di,B" so the unbiasedness follows from equation 13 by separating the expectation over B* into expectations over B and by| R
C.3
B BBB+)>=((B--)) [Boa [c [SSAS(Ba)) [B})]]
(p [=][ [[]]
E[f(x))
4

---

Published as a conference paper at ICLR 2020
In general, sum-and sum-and-sample estimator reduces variance if the probability mass is concentrated on the summed categories. As typically high probability categories are sampled first, the stochastic sum-and-sample estimator sums high probability categories, similar to the estimator by Liu et al. (2019) which we refer to as the deterministic sum-and-xampll estimator. As we show Appendix C.2 Bao-Blackwellizing the stochastic sun-and-sample estimator also results in the unordered set estimator. This even holds for version that uses m samples and k-m summed terms (see Appendix C.3 which means that the unordered estimator has equal or lower variance than the optimal (in terms of m) stochastic sum-an com-and-sample estimator, but conveniently does nor need to choose m.
The imporfance--eigghted estimator.
The importance- estimator (Vicira 2017) is
Σ p(s) eESt
w (S* ;k)=
g(8, 15) f(s).
(15)
This estimator is based on the idea of priority sampling Duffield et al. 2007). It does not use the order of the sample, but assumes sampling using the Gumbel-Topp- trick and requires access to K, the (k + 1)-th largest perturbed log prg--rrbbbiltt, which can be seen as the 'threshold' since go. > K Vs 5* g(8,a) = P(ge, > a) can be interpreted as the inclusion probability of E 5* (assuming a fixed threshold a instead of a fixed sample size k). For details and a proof of unbiasedness, |ieira (017) Kool et al. (2019c). As the estimator has high variance, Kool et al. (2019c) resort to normalizing the importance weights, resulting in biased estimates. Instead, use Bao-Blackwellizattre
eliminate stochasticity by R. Again, the result is the unordered set estimator (see Appendix D.I. which thus has equal or lower variance.
3.3 THE UNORDERED SET POLICY GRADIENT ESTIMATOR
Writing po indicate the dependency on the model parameters 0, we can combine the unordered set estimator with REINFORCE (Williams) 1992) to obtain the unordered set policy gradient estimator.
Corollary 1. The unordered set policy gradient estimator, given by
e (S*)
Σ Po()) Ve (og)
Σ SES*
(opo(>)R(S*,.))
(16)
aESt
is an unbiased estimate of the policy gradient.
Proof. Using REINFORCE (Williams 1992) combined with the unordered set estimator we find:
V Bo (()))))((()))=BB (e) Vo log (o))
= Es (S*)
Σ BES
P((s)
(o logro
Variance reduction using a built-in control variate. The variance of REINFORCE can be re- duced by subtracting baseline from f. When taking multiple samples (with replacement), simple and effective baseline is to take the mean of other (independent!) samples (Mnih Rezende 2016). Sampling without replacement, we can use the same idea to construct baseline based on the other samples, but we have to correct for the fact that the samples are not independent. Theorem 2.
The unordered set policy gradient estimator with baseline, given by
Vopo (s) ,) [(s) (1()) Σ (os))) (5)01))()
USPGRI (SK) (SP
Σ
(17)
S'ES"
where
Di(0,0') (st (s,
RPMO 8')
Pe
(18)
Pe (((s) (St {s})
the second order leave-one-out ratio, an unbiased estimate of the policy gradient.
5

---

Published as a conference paper at ICLR 2020
Proof. See Appendix E.1
This theorem shows how to include built-in baseline based on dependent samples (without re- placement), without introducing bias. By having built-in baseline, the value [(s) for sample is compared against an estimate of its expectation B[ [()] based on the other samples. The difference is an estimate of the advantage (Sutton & Barto, 2018), which is positive the sample s is 'bet- ter' than average, causing Po(s) be increased (reinforced) through the sign of the gradient, and vice versa. By sampling without replacement, the unordered set estimator forces the estimator to compare different alternatives, and reinforces the best among them.
Including the pathwise derivative. So far, we have only considered the scenario where f does not depend on A. If f does depend on 0, for example in VAE (Kingma & Welling, 2014 Rezende et al. 2014), then we use the notation fo and we can write the gradient (Schulman et al. 2015 as
Vo (f) (s) (a) Vo log (o)) + Vofo(=)).
(19)
The additional second ("pathwisc") ) term can be estimated (using the same samples) with the standard unordered set estimator. This results in the full unordered set policy gradient estimator:
FUSPG (s*)
= Σ (apo(s)
R(S* 8)So(() + Σ (os))R(S++)Voll
#ES*
SES*
Σ SES
R(Sk, Vo (Po()))o())))
(20)
Equation 20 is straightforward to implement using an automatic differentiation library. We can also include the baseline (as in equation [T] but must make sure call PROP_GRADIENT (DETACH in PyTorch) on the baseline (but not on (s)). Importantly, we should never track gradients through the leave-one-out ratio R(S*, 8) which means it can be efficiently computed in pure inference mode.
Scope & limitations. We can use the unordered set estimator for any discrete distribution from which can sample without replacement, by treating it as univariate categorical distribution over its domain. This includes sequence models, from which we can sample using Stochastic Beam Search (Kool et al., 2019c). as well as multivariate categorical distributions which can also be treated as sequence models (see Section 4.2). . In the presence of continuous variables or a stochastic function f. we may separate this stochasticity from the stochasticity over the discrete distribution, as in Lorberbom et al. (2019). The computation of the leave-one-our ratios adds some overhead, although they can be computed efficiently, even for large (see Appendix B). For a moderately sized model, the costs of model evaluation and backpropagation dominate the cost of computing the estimator.
3.4 RELATION TO OTHER SAMPLE ESTIMATORS
Relation to Murthy's estimator. We found out that the 'vanilla' unordered set estimator (equa- tion IT] is actually a special case of the estimator by Murthy (957). known in statistics literature for estimation of population total θ Σ.ED D Vi. Using y: = (i) we have θ = [E)] so Murthy's estimator can be used to estimate expectations (see equation IT). Murthy derives the esti-
mator by 'unordering' a convex combination of Raj (956) estimators, which, using y; (()),
are stochastic sum-and-sample estimators in our analogy.
Murthy 1957)) also provides unbiased estimator of the variance, which may be interesting for future applications. Since Murthy's estimator can be used with arbitrrry sampling distribution, is straightforward to derive importance-sampliin versions of our estimators. In particular, we can
sample without replacement using ((x) > 0, E D, and use equations [I 16 17 and 20 as long
compute the leave-one-out ratio R(S .) using q.
While part of our derivation coincides with Murthy (957).. we are not aware of previous work discuss practical computation of
using this estimator to estimate expectations. Additionally, p(S) (Appendix B). we show the relation to the importance- weighted estimator, and we provide the extension to estimating policy gradients, especially including built-in baseline without adding bias.

---

Published as a conference paper at ICLR 2020
Relation to the empirical risk estimator. The empirical risk loss (Edunov al. 2018 estimates the expectation in equation
[ by summing only a subset S of the domain, using normalized proba- Using this loss, the (biased) estimate of the gradient is given by
bilities (o()) (o(+)
Ee'es Po(s)"
pe(s)
e RISK (8
Σ Ve
Ex'Es (olsssooss)) Po( f(s).
(21)
The risk estimator is similar to the unordered set policy gradient estimator, with two important differences: 1) the individual terms are normalized by the total probability mass rather than the leave-one-out ratio and 2) the gradient w.r.t the normalization factor is taken into account. As result, samples 'compete' for probability mass and only the best can be reinforced. This has the same effect as using a built-in baseline, which we prove in the following theorem.
Theorem 3. By taking the gradient w.E.t. the normalization factor into account, the risk estimator has built-in -n baseline, which means it can be written as
RISK (Sh)= = Σ Vopo(s) SemEstPols")
[(s)
Σ po(o") (rol') Exrrst po(sn) ( 1(66)) F'ES"
pe(sm))(s')
(22)
BESH
Proof. See Appendix F.1
This theorem highlights the similarity between the biased risk estimator and our unbiased estimator (cquation 17). and suggests that their only difference is the weighting of terms. Unfortunately. the implementation by Edunov et al. (2018) has more sources of bias (e.g. length normalization), which are not compatible with our estimator. However, we believe that our analysis helps analyze the bias of the risk estimator and is step towards developing unbiased estimators for structured prediction.
Relation to VIMCO. VIMCO (Mnih & Rezende 2016) is an estimator that uses & samples (with replacement) to optimize objective of the form log > f((xz), which is multi-sample stochastic lower bound in the context of variational inference. VIMCO reduces the variance by using a local baseline for each of the k samples, based on the other & 1 samples. While we do not have log term, as our goal is to optimize general [x](()), we adopt the idea of forming a baseline based on the other samples, and we define REINFORCE with replacement (with built-in baseline) as the estimator that computes the gradient estimate using samples with replacement X
(#1,..., Ixk) as
((6)))+11 Σ
RFWR (x*)
1 T:
Vo log logpe(s;)
(((x))
1: -
1
((x)) -EEISO)
(23)
371
This estimator is unbiased, as Ezg,,, Vo (o: (2019b)) We think of the unordered set estimator the without-replacemmnt version of this timator, which weights terms by (a(s) Ps(*) s) instead of 1. This puts more weight on higher probability elements to compensate for sampling without replacement. If probabilities are small and (close to) uniform, there are (almost) no duplicate samples and the weights will be close to k. so the gradient estimate of the with- and nidhout-replacement versions are similar.
= O for i + j (see also Kool et al.
Relation to ARSM. ARSM (Yin et al. 2019) also uses multiple evaluations ( ("pseudo-samples) of Pe and f. This can be seen as similar to sampling without replacement, and the estimator also has built-in control variate. Compared to ARSM, our estimator allows direct control over the computational cost (through the sample size k) and has wider applicability, for example it also applies to multivariate categorical variables with different numbers of categories per dimension.
Relation to stratiffed/systematic sampling. Our estimator aims to reduce variance by changing the sampling distribution for multiple samples by sampling without replacement. There are alterna- tives, such as using stratified or systematic sampling (see, e.g. Douc & (app)((0005) Both partition the domain D into & strata and take a single sample from each stratum, where systematic sampling uses common random numbers for each stratum. In applications involving high-dimensional or structured domains, it is unclear how to partition the domain and how to sample from each partition. Additionally, as samples are not independent, it is non-trivial to include a built-in baseline, which find is key component that makes our estimator perform well.

---

Published as a conference paper at ICLR 2020
40
3x
AGM wo bukkes
18
(a) High entropy (1)
(b) Low entropy (1)
Figure 1: Bernoulli gradient variance (on log scale) as function of the number of model evaluations (including baseline evaluations, so the sum-and-sampa sample estimators with sampled baselines use twice many evaluations). Note that for some estimators, the variance is 0 (log variance -00 for k = 8.
4 EXPERIMENTS
4.1 BERNOULLI TOY EXPERIMENT
We use the code by Liu et al. 2019) to reproduce their Bernoulli toy experiment. Given a vector
(0.6, 0.51, 0.48) the goal is to minimize the loss L(1) Ez,, (enn= Ei (z, p.)² Here 21, 22, 23 are i.idd. from the Bernoulli(rrr)) distribution, parameterized by scalar E R. where a (11) (1 + exp(-n)))= is the sigmoid function. We compare different estimators, with and without baseline (either 'built-in' or using additional samples, referred to as REINFORCE+ in Liu et al. 2019)). We report the (log-)variance of the scalar gradient Dij as function of the number of model evaluations, which is twice as high when using a sampled baseline (for each term).
#C
As can be seen in Figure I the unordered set estimator is the only estimator that has consistently the lowest (or comparable) variance in both the high (17 = 0) and low entropy (17 = -4) regimes and for different number of samples/model evaluations. This suggests that it combines the advantages of the other estimators. We also ran the actual optimization experiment, where with as few as samples the trajectory was indistinguishable from using the exact gradient (see Liu et al. 2019
4.2 CATEGORICAL VARIATIONAL AUTO-ENCODER
We use the code from Yin et al. 2019) to train categorical Variational Auto-Encoder ( (VAE) with 20 dimensional latent space, with 10 categories per dimension (details in Appendix G.T]. To use our estimator, treat this as a single factorized distribution with 1020 categories from which we can sample without replacement using Stochastic Beam Search (Kool al. 2019c),, sequentially sampling each dimension as if it were sequence model. We also perform experiments with 102 latent space, which provides a lower entropy setting, to highlight the advantage of our estimator.
Measuring the variance. In Table we report the variance of different gradient estimators with k 4 samples, evaluated on trained model. The unordered set estimator has the lowest variance in both the small and large domain (low and high entropy) setting, being on-par with the best of the (stochastid oum-and-sample estimator and REINFORCE with replacemen(" This confirms the toy experiment, suggesting that the unordered set estimator provides the best of both estimators. In Appendix G.2 we repeat the same experiment at different stages of training, with similar results.
3 We cannot use the deterministic version by Liu et al. (2019) since we cannot select the top & categories. *We cannot compare against VIMCO Mnih & Rezende 2016) as it optimizes different objective.
Table 1: VAE gradient log-variance of different unbiased estimators with k 4 samples.
ARSM RELAX
REINFORCE
Sum & sample
REINE w.r. Unordered
Domain
(no bl) (sample bl)
(no bl) (sample bl)
(built-in bl) (built-in bl)
Small 10'
13.45
11.67
11.52
7.49
6.29
6.29
6.65
6.29
Large 2
15.55
15.86
13.81
8.48
13.77
8.44
7.06
7.05
8

---

Published as a conference paper at ICLR 2020
Trainin ELDO (13) lenrt cINtM1
Traning ELDG (13" levre
(13"t space)
22C
2015
1333
78.3 a- ieoreee Bon
133.4 ARSM
70.3 KOME bab400
0C-
222
10 206
463
6x 689
204
48
890
(a) Small domain (latent space size 10²)
(b) Large domain (latent space size 102h)
Figure 2: VAE smoothed training curves (-ELBO) of two independent runs when training with different estimators with & = 1, 4 or 8 (thicker lines) samples (ARSM has a variable number). Some lines coincide, so we sort the legend by the lowest -ELBO achieved and report this value.
ELBO optimization. We use different estimators to optimize the ELBO (details in Appendix Additionally to the haselines by Yin et al. (2019) we compare against REINFORCE with replacement and the stochastic sum-and-sample estimator. In Figure 2 tor performs on par with REINFORCE with replacement (and built-in baseline, equation 23) and outperforms other estimators in at least one of the settings. There are a lot of other factors, e.g. exploration that may explain why we do not get a strictly better result despite the lower variance. We note some overfitting (see validation curves in Appendix G.2). but since our goal is to show improved optimization, and to keep results directly comparable to Yin et al. (2019), we consider regularization a separate issue outside the scope of this paper. These results are using MNIST bina- rized by threshold of 0.5. In Appendix G.2 we report results using the standard binarized MNIST dataset from Salakhutdinov & Murray 2008).
we observe that our estima-
4.3 STRUCTURED PREDICTION FOR THE TRAVELLING SALESMAN PROBLEM
To show the wide applicability of our estimator, we consider the structured prediction task of pre- dicting routes (sequences) for the Travelling Salesman Problem (TSP) (Vinyals et al.) 2015) Bello al. 2016 Kool al. 2019a). We use the code by Kool et al. (2019a reproduce their TSP experiment with 20 nodes. For details, see Appendix
We implement REINFORCE with replacement (and built-in baseline) as well the stochastic sum- and-sample estimator and our estimator, using Stochastic Beam Search (Kool et al., 2019ch for sampling. Also, we include results using the biased normalized importance-weighted policy gradient estimator with built-in baseline (derived in Kool et al.) (2019b), see Appendix (.2).. Additionally, we compare against REINFORCE with greedy rollout baseline (Rennie al.) (017) used by Kool ctt al. (2019c) and batch-average baseline. For reference, also include the biased risk estimator, either 'sampling' using stochastic or deterministic beam search (as in Edunov et al. (2018))
In Figure 3a we compare training progress (measured on the validation set) as function of the number training steps, where we divide the batch size by & to keep the total number of samples equal. Our estimator outperforms REINFORCE with replacement, the stochastic sum-and-sample estimator and the strong greedy rollout baseline (which uses additional bascline model evaluations) and performs on-par with the biased risk estimator. In Figure 3b plot the same results against the number of instances, which shows that, compared to the single le sample estimators, we can train with less data and less computational cost (as we only need run the encoder once for each instance).

---

Published as a conference paper at ICLR 2020
Feforrance vaRvin stage
Nerfmance namber recances
Surt IIFOR prec
aeiihted buck
decigvaa De
Rak tranee
0.39C
049C
6.9%
0274
0/00
2000
200000
2000
00P
80
(a) Performance vs. training steps
(b) Performance vs. number instances
Figure 3: TSP validation set optimality gap measured during training. Raw results light, smoothed results are darker (2 random seeds). We compare our estimator against different un- biased and biased (dotted) multi-sample estimators and against single-sample REINFORCE, with batch-average greedy rollout baseline.
DISCUSSION
We introduced the unordered set estimator, a low-variance, unbiased gradient estimator based on sampling without replacement, which can be used as alternative to the popular biased Gumbel- Softmax estimator (Jang et al., 2016; Maddison et al., 2016). Our estimator is the result of Rao- Blackwellizing three existing estimators, which guarantees equal lower variance, and is closely related to a number of other estimators. has wide applicability, is parameter free (except for the sample size k) and has competitive performance to the best of alternatives in both high and low entropy regimes.
In experiments, found that REINFORCE with replacement, with multiple samples and built-in baseline as inspired by VIMCO (Mnih & Rezende] 2016), is simple yet strong estimator which has performance similar to our estimator in the high entropy setting. We are not aware of any recent work on gradient estimators for discrete distributions that has considered this estimator as baseline, while may be often preferred given its simplicity. In future work, we want investigate if we can apply our estimator to estimate gradients 'locally' (Titsias & Lázaro-Grees Gredilla, 2015). as locally we have a smaller domain and expect more duplicate samples.
ACKNOWLEDGMENTS
This research was funded by ORTEC. We would like to thank anonymous reviewers for their feed- back that helped improve the paper.
REFERENCES
Dzmitry Bahdanau, Philemon Brakel, Kelvin Xu, Anirudh Goyal, Ryan Lowe, Joelle Pineau, Aaron Courville, and Yoshua Bengio. An actor-critic algorithm for sequence prediction. In International Conference on Learning Representations, 2017.
Irwan Bello, Hieu Pham, Quoc Le, Mohammad Norouzi, and Samy Bengio. Neural combinatorial optimization with reinforcement learning. arXiv preprint arXiv: 161 1.09940, 2016.
Yoshua Bengio, Nicholas Léonard, and Aaron Courville. Estimating or propagating gradients through stochastic neurons for conditional computation. arXiv preprint 130.333308.333,,2222 2013.
George Casella and Christian P Robert. Bla.kwwlsllllittoonnnn of sampling schemes. Biometrika, 83 (1):81-94, 1996.
Randal Doue and Olivier Cappé. Comparison of resampling schemes for particle filtering. In ISPA 2005. Proceedings of the 4th International Symposium on Image and Signal Processing and Anal- ysis, 2005., pp. 64-69. IEEE, 2005.
Nick Duffield, Carsten Lund, and Mikkel Thorup. Priority sampling for estimation of arbitrary subset sums. Journal of the ACM (JACM), 54(6):32, 2007.
10

---

Published as a conference paper at ICLR 2020
Sergey Edunov, Myle Ott, Michael Auli, David Grangier, et. Classical structured prediction losses for sequence to sequence learning. In Proceedings of the 2018 Conference of the North Ameri- can Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume (Lon Papers), volume 1, pp. 355-364, 2018.
Paul Fearnhead and Peter Clifford. On-line inference for hidden markov models via particle filters. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 65(4):887-899, 2003.
Will Grathwohl, Dami Choi, Yuhuai Wu, Geoffrey Roeder, and David Duvenaud. Backpropagation through the void: Optimizing control variates for black-box gradient estimation. In International Conference on Learning Representations, 2018.
Karol Gregor, Ivo Danihelka, Andriy Mnih, Charles Blundell, and Daan Wierstra, Deep autoregres- sive networks. International Conference on Machine Learning, pp. 1242-1250, 2014.
Aditya Grover, Eric Wang, Aaron Zweig, and Stefano Ermon. Stochastic optimization of sorting networks via continuous relaxations. In International Conference on Learning Representations, 2019.
Jiatao Gu, Daniel Jiwoong Im, and Victor OK Li. Neural machine translation with Gumbel-greedy decoding. In Secrot AAAI Conference Artificial Intelligence (AAAT), 2018.
Shixiang Gu, Sergey Levine, Ilya Sutskever, and Andriy Mnih. Muprop: Unbiased backpropagation for stochastic neural networks. In International Conference Learning Representations, 2016.
Di He, Yingee Xia, Tao Qin, Liwei Wang, Nenghai Yu, Tie-Yan Liu, and Wei-Ying Ma. Dual learning for machine translation. In Advances in Neural Information Processing Systems, pp. 820-828, 2016.
Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparameterizzttion with gumbel-softmax. In International Conference on Learning Representations, 2016.
Carolyn Kim, Ashish Sabharwal, and Stefano Ermon. Exact sampling with integer linear programs and random perturbations. In Thirtieth AAAI Conference on Artificial Intelligence, 2016.
Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. In International Conference on Learning Representations, 2015.
Diederik P Kingma and Max Welling, Auto-encoding variational Bayes. In International Conference on Learning Representations, 2014.
Wouter Kool, Herke van Hoof, and Max Welling. Attention, learn to solve routing problems! In International Conference on Learning Representations, 2019a.
Wouter Kool, Herke van Hoof, and Max Welling. Buy reinforce samples, get a baseline for free! In Deep Reinforcement Learning Meets Structured Prediction Workshop at the International Conference on Learning Representations, 2019b.
Wouter Kool, Herke Van Hoof, and Max Welling. Stochastic beams and where to find them: The gumbel-top-k trick for sampling sequences without replacement. International Conference on Machine Learning, pp. 3499-3508, 2019c.
Hugo Larochelle and lain Murray. The neural autoregressive distribution estimator. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pp. 29-37, 2011.
Rémi Leblond, Jean-Baptiste Baptiste Alayrac, Anton Osokin, and Simon Lacoste-Julien. Searn: Training RNNs with global-local losses. In 6th International Conference on Learning Representations, 2018.
EL Lehmann and Henry Scheffé. Completeness, similar regions, and unbiased estimation: Part Sankhyā: The Indian Journal of Statistics, pp. 305-340, 1950.

---

Published as a conference paper at ICLR 2020
Chen Liang, Mohammad Norouzi, Jonathan Berant, Quoe V Le, and Ni Lao. Memory augmented policy optimization for program synthesis and semantic parsing. In Advances in Neural Informa- fion Processing Systems, pp. 9994-10006, 2018.
Runjing Liu, Jeffrey Regier, Nilesh Tripuraneni, Michael Jordan, and Jon Mcauliffe. Rao- Blackwellized stochastic gradients for discrete distributions. In International Conference on Ma- chine Learning, pp. 4023 4031,4 2019.
Guy Lorberbom, Andreea Gane, Tommi Jaakkola, and Tamir Hazan. Direct optimization through argmax for discrete variational auto-encoder. arXiv preprint 1rXiv:1806.022 02867, 2018
Guy Lorberbom, Chris Maddison, Nicolas Heess, Tamir Hazan, and Daniel Tarlow. Direct policy gradients: Direct optimization of policies in discrete action spaces. arXiv preprint arXiv: 1906.0006.0 2019.
Duncan Luce. Individual choice behavior: theoretical analysis. John Wiley, 1959.
Chris Maddison, Daniel Tarlow, and Tom Minka. A sampling, In Advances Neural Information Processing Systems, pp. 3086-3094, 2014.
Chris J Maddison, Andriy Mnih, and Yee Whye Teh. The concrete distribution: continuous laxation of discrete random variables. In International Conference on Learning Representations, 2016.
Andriy Mnih and Karol Gregor. Neural variational inference and learning belief networks. In International Conference Machine Learning, pp. 1791-1799, 2014.
Andriy Mnih and Danilo Rezende. Variational inference for Monte Carlo objectives. In International Conference on Machine Learning, pp. 2188-2196 2016.
MN Murthy. Ordered and unordered estimators in sampling without replacement. Sankhyā: The Indian Journal of Statistics ( (1933-1960), 18(3/4)3379-39) 1957.
Renato Negrinho, Matthew Gormley, and Geoffrey J Gordon. Learning beam search policies via imitation learning. In Advances in Neural Information Processing Systems, pp. 10673-10682, 2018.
Mohammad Norouzi, Samy Bengio, Navdeep Jaitly, Mike Schuster, Yonghui Wu, Dale Schuurmans, et al. Reward augmented maximum likelihood for neural structured prediction. In Advances In Neural Information Processing Systems, pp. 1723-1731, 2016.
John Paisley, David M Blei, and Michael I Jordan. Variational Bayesian inference with stochastic search. In International Conference on Machine Learning, pp. 1363-1370, 2012.
Robin L Plackett. The analysis of permutations. Journal of the Royal Statistical Society: Series
(Applied Statistics), 24(2):193 202, 1975.
Des Raj. Some estimators in sampling with varying probabilities without replacement. Journal of the American Statistical Association, 51(274):269-2) 284, 1956.
Rajesh Ranganath, Sean Gerrish, and David Blei. Black box variational inference. In Artificial Intelligence and Statistics, pp. 814-822, 2014.
Mare' Aurelio Ranzato, Sumit Chopra, Michael Auli, and Wojciech Zaremba. Sequence level train- ing with recurrent neural networks. In International Conference Learning Representations, 2016.
Steven Rennie, Etienne Marcheret, Youssef Mroueh, Jerret Ross, and Vaibhava Goel. Self-critical sequence training for image captioning. In Proceedings of the IEFE Conference on Computer Vision and Pattern Recognition, pp. 7008-7024, 2017.
Danilo Jimenez Rezende, Shakir Mohamed, and Daan Wierstra. Stochastic backpropagation and ap- proximate inference in deep generative models. In International Conference on Machine Learn ing, pp. 1278-1286 2014.
12

---

Published as a conference paper at ICLR 2020
Geoffrey Roeder, Yuhuai Wu, and David K Duvenaud. Sticking the landing: Simple, gradient estimators for variational inference. Advances in Neural Information Processing Sys- tems, pp. 6925-6934, 2017.
Ruslan Salakhutdinov and lain Murray. On the quantitative analysis of deep belief networks. In International Conference on Machine Learning, pp. 872-879, 2008.
John Schulman, Nicolas Heess, Theophane Weber, and Pieter Abbeel. Gradient estimation using stochastic computation graphs. In Advances Neural Information Processing Systems, pp. 3528- 3536, 2015.
Shiqi Shen, Yong Cheng, Zhongjun He, Wei He, Hua Wu, Maosong Sun, and Yang Liu. Minimum risk training for neural machine translation. In Proceedings of the 54th Anmual Meeting of the Association for Computational Linguistics (Volume I: Long Papers), volume 1, pp. 1683-1692, 2016.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Michalis K Titsias and Miguel Lázaro-Greiilla. Local expectation gradients for black box varia- tional inference. Advances Neural Information Processing Systems- Volume 2, pp. 2638- 2646, 2015.
George Tucker, Andriy Mnih, Chris Maddison, John Lawson, and Jascha Sohl-Dickstein. Rebar: Low-variance, unbiased gradient estimates for discrete latent variable models. In Advances in Neural Information Processing Systems, pp. 2627-2636, 2017.
Tim
Vieira.
Gumbel-max
trick and weighted reservoir sampling, 2014. http:://w.iiiia...a.t....////o/2
URL
gumbel -mammmax---- tr and wei -
Tim Vieira. Estimating means in finite htt.h//ww..................aaaaa
Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. In Advances in Neural
Information Processing Systems, pp. 2692-2700, 2015.
Ronald J Williams. Simple statistical gradient-ollowing algorithms for connectionist reinforcement learning. Machine learning, 8(3-4):229 256, 1992.
John I Yellott. The relationship between Luce's choice axiom, Thurstone's s theory of comparative judgment, and the double exponential distribution. Journal of Mathematical Psychology. 15(2): 109-144, 1977.
Mingzhang Yin, Yuguang Yue, and Mingyuan Zhou. Arsm: Augneen-réifooree-waaaenngggg esti- mator for gradient backpropagation through categorical variables. In International Conference Machine Learning, pp. 7095-7104, 2019.
13

---

Published as a conference paper at ICLR 2020
A NOTATION
Throughout this appendix we will use the following notation from Maddison et al. (2014):
es(g) cxp(-9 Φ)
(g) exp( - exp( + 6))
(g) ( Fo(g).
This means that Fg(g) is the CDF and [g) the PDF of the Gumbel(ø) distribution. Additionally we will use the identities by Maddison et al. 2014):
Fo(g) (l (g)
(24)
(o) = (F&(b) - Fo(a)) exp(1) exp(o)
(25)
Also, we will use the following notation, definitions and identities (see Kool et al. (0019c)):
Φ: = lloggo p(i)
(26)
Øs log Σp(1 p(i)
log
exp @;
(27)
iES
D = log Σ p(i) = log
1- -1-Ept p(i)
1
exp((1)
(28)
DES
iES
Go. Gumbel(o:)
(29)
Gøs = max Go, ~ Gumbel(os) IES
(30)
For proof of equation 30
see Maddison et al. (2014).
B COMPUTATION OF p(S*), p PS C) AND R(S
We can sample the set S from the Plackett-Luce distribution using the Gumbel-Top-h trick by drawing Gumbel variables Go, (umbel(d))) for each element and returning the indices of the k largest Gumbels. If we ignore the ordering, this means we will obtain the set 5 if min Go. > Dy Go. Omitting the superscript & for clarity, we can use the Gumbel-Max trick, i.c. that G Gopis maxigs Go. Gumbel(én,. (equation 30) and marginalize over Gøpie
p(S) = P(min Go, > GoDAs)
iES
P(Go, Gemisii S)
fodrs (Bop) P( x Ioprs: 5)0gebrs
Jep's
fedis (BeDre) II (1 (9.(o))))) 0gedis
(31)
Jepis
II SES
Fs, ( (w)) Ou
(32)
Here we have used change of variables Foms (fomrs). This expression can be efficiently numerically integrated (although another change of variables may be required for numerical stability depending on the values of Φ))
Exact computation in O(2*). The integral in equation identity
31 can be computed exactly using the
II 1E8
(a: b.) >
1-1)
b; II 0;
CCS
IEC
iES(C
14

---

Published as a conference paper at ICLR 2020
which gives
x
p(S)
PeDis(9bpo II (1 For (éeDs))) dgonss
iES
Σ
(-1)
Jams (ppms)
II sEC
Fs, (Jom))
II iESYC
10genss
CC8
9épis
Σ
(-1)
Boms coms(odnre FoDye (Domrs Foe (goors Agons
CE8
Σ
(-1)
Epps ) Pororsyu (Boor (000:)
CCS
expldnis)
Σ (-1) (-1) exp(o(n(s)uc)
CCS
Σ (-1))c) 1- Eies
(33)
1 1 E-Ees,op
CES
Computation of (S C). When using the Gumbel-Top-k trick over the restricted domain
D \ C, we do not need to renormalize the log-probabilities 6,, D \ C since the Gumbel-Top-k trick applies to unnormalized bog-pobbabilities. Also, assuming C S S it holds that (D)C) C) = DD
\ S. This means that we can compute p
similar to equation 31
p PS ())
P( min Go, Gormorson "ESIC
= P( min Go. > Goprs) iESiC
foors (Doors)
II iESIC
Fo, (o Ogoors.
(34)
Aépis =-00
Computation of R(Sk s).
Note that, using equation 10 it holds that
(S (sH)(())
Σ
Σ
P(b = )(
=1
p(5k)
RES
aESt
from which it follows that
1(S*) Σ
(S ( {s))pp(s)
SESL
such that
(St \ {s})
(S {s})
R(S 3)
(35)
p(Sk)
Evest PS (p())(()))
This means that, to compute the leave-one-out ratio for all E S* we only need to compute p (S( {s}) for s E S* When using the numerical integration or summation in O(2*), ), we can reuse computation, whereas using the naive method, the cost is O (k- - 1j!) O(k!), making the total computational cost comparable to computing just P(S*), and the same holds when computing the 'second-order' leave one out ratios for the built-in baseline (equation 17
15

---

Published as a conference paper at ICLR 2020
Details of numerical integration. For computation of the leave-one-our ratio (equation 35 for large we can use the numerical integration, where we need to compute equation 34 with C {8). For this purpose, rewrite the integral as
SODYS (oDrs)) iES/C
II
(1
Fo; (eoD())) Agoars
Bé
II iES/C
- For (F (FFDis(1) ( du
II iESIC
1 (1 (I-uxx((=-oDrs) Iu
exp((b)
(exp(b)-1 ( pexplox- dr
iESiC
II (1 11- (1-oonidott)) Sc.
expla dDiS)
===
1ESYC
Here we have used change variables u==p(=b) and a b - dDYs. This form allows to compute the integrands efficiently,
II (1 (1-xexpletta)== Ibes (1 - -exxpp((t+e) iES
llee (1 vexplorta)
where the numerator only needs computed once, and, since C {8} when computing equa- tion 35 the denominator only consists of single term.
The choice of may depend on the setting, but we found that 5 is good default option which leads to an integral that is generally smooth and can be accurately approximated using the trapezoid rule. We compute the integrands in logarithmic space and sum the terms using the stable LOGSUMEXP trick. In our code we provide an implementation which also computes all second-order leave-one-out ratios efficiently.
C THE SUM-AND-SAMPLE ESTIMATOR
C.1 UNBIASEDNESS OF THE SUM-AND-SAMPLA ESTIMATOR
We show that the sam-lee- estimator unbiased for any set C' C D (see also Liang et al. 2018 Liu et al. 2019)):
Σ [(c))((e)+ (1 1-E f(x))
LEE
REC
1 (1 p(c)
Σ M()s(())+++
8EC
LEC
Exe))(()
1 1-Eplo p(c)
Σ - Exec p(c) f(x)
p(x)
EEC
GEC
ZEDYC
Σ f(x)
aEC
mEDiC
Σ p(z)f(x)
ZED
E p [f(z]]
16

---

Published as a conference paper at ICLR 2020
C.2 AAO-BLACKWELLIZATION OF THE STOCHASTIC SUM-AND-SAMPE ESTIMATOR
In this section give the proof that Rao-Blackwellizing the stochastic sum-and-sample estimator results in the unordered set estimator.
Theorem 4. Rao- Blackwellliznng the stochastic aomn-andssampp estimator results in the unordered sel estimator, i.e.
Ep (8))
[((,))(()))+++++++ 111--
s(bb)
Σ p(s) ,s)((s). (s)
(36)
j=1
Proof. To give the proof, first prove three Lemmas.
Lemma 1.
p(5*) 1 {s})
p(s) S' (s) p(s')
P(b = s|8*)
(37)
p(Sk)
Proof. Similar the derivation of P(bi =15*) (equation in the main paper), write:
P(S* nb s)
P(ha = s|5*)
p(Sk)
p(S* \ (s)))
P(SA)
p(S* \ (6))
p(s)
p(Sh) 1- Ee p(s')
The step from the first to the second row comes from analyzing the event s using sequential sampling: to sample S* (including with being the k-th element means that we should first sample Sk {s} (in any order), and then sample from the distribution restricted D \ (S* \ {s}).
Lemma 2.
1 1 Evegp(d') +(S) (s)) T- EvEes p(8')
Pi())(S) {s))
(38)
Dividing equation 33 by Evesp(s' both sides, obtain
17

---

Published as a conference paper at ICLR 2020
Proof.
((S)
Exes p(s')
(-1) 0l
I=ENEsiOP(s)
CgS
= Σ
(-1)
1- EVESiOp(s) + (-1))cu(a))
1
1- p()))
(C
Σ
(-1)lc)
1
Σ
(-1)1ou(+)
ExESiOR(S))
CCS((#)
CESMst
= Σ
(-1)ic)
(-1)lc) 2
1-((s) E
2xE(S)OHNCC(() cES1(s)
(CS((s)
p(8) {s})
(-1)1C1
1 p(s)
p(a) 1-EVE(S((=))10
(o)
(ES)(
T-p(s)
pS (S))))
p(S) (8})
1 1- p(((s) E ExES((a) p(a')
1- EdESs P(s')
I-p(s)
DI (s))
p(S) {8t
1 (()) - EvES)(A) p(8") - EVVEs(()) p(5))
p (S) {0t) P(5) {s})
1 1- ExEspp((s) 1- ExES(()) p(s')
((s)
Multiplying by 1 Eves p(s)) and rearranging terms proves Lemma 2
Lemma 3.
p(s)+ +
(
1- E -1())) P(bx - $|s*)= - P(s))((S*
(39)
d'Est
Proof. First using Lemma annd then Lemma
we find
p(s) +
1 Σ p(s')
P(b =
s'ESt
p(S \ (s))
p(s)
=p(s) +
1 Σ p()')
P(Sk)
(SSA) p(5))
S'ESt
p(s)
Evese p(s')
p(S*) + 1- Ee Po)T (18)
P(SS)
p(s)
(5 (s}))
P(SR)
R(($) s).
18

---

Published as a conference paper at ICLR 2020
Now can complete the proof of Theorem 4 by adding f(b)) (bb))f(bb))
0 to the
estimator, moving the terms independent of B outside the expectation and using Lemma
R-1
E B& (Bt 15*)
p(b)){(b,)+
1
Σ p(b;)
f(ba)
5=1
k
= Btp
p(b)){(b))
1
Σ
p(b;)
s(bw)
j=1
Σ SES
p(s)f(s) + E BB
1
Σ
p(5')
f(bx)
sest
Σ
p())S(s)+
+ Σ
1 Σ
p(5')
P(bx - s(()))(())
#ES
BESt
8'ESt
Σ
p(s)+ +
1- Σ p(s')
p(b (7b=ss)st) f(s)
#ESt
s'Esk
= Σ (
SES*
C.3 THE STOCIASTIIC SUM-AND-SAMPLE ESTIMATOR WITH MULTIPLE SAMPLES
As was discussed in Liu al. (2019), one can trade off the number of summed terms and number of sampled terms to maximize the achieved variance reduction. As generalization of Theorem 4 (the stochastic sum-and-sample estimator with k summed terms), we introduce here the stochastic sum-and-sample estimator that sums k m terms and samples > terms without replacement. To estimate the sampled term, we use the unordered set estimator on the m samples without replace- ment, the domain restricted to D ==- In general, we denote the unordered set estimator restricted to the domain D \ C by
DS (aS((ss)))
Σ
D(s)R s)
(40)
SESEIC
where RS* ,) is the leave-one-out ratio restricted to the domain D \ C, similar to the second order leave-one-out ratio in equation 18
(DAOMS) ((S* \ ()
(S* 8)
Po
(41)
DVC (S* C)
Pg
While we can also constrain g c (D\CC) this definition is consistent with equation 18 and allows simplified notation.
Theorem 5. Rao- Cao-Blackwellizing the stochastic sum-and-sen sample estimator with m 1 samples results in the unordered set estimator, i.e.
k-m
k-m
Σ p(b)f((,)) + 1 1- j=1
p(b)) (I..iA
Σ p(s)R(S* s))(s)
E Bk Sk)
NES
(42)
Proof. Recall that for the unordered set estimator, holds that
US (5*) (n(ri1())))) [f(b:)] Ex-p(r) [(x)]| E s*1
(43)
19

---

Published as a conference paper at ICLR 2020
which for the restricted equivalent (with restricted distribution p pP()) translates into
eUS.DiC = (L0 [f(x) E SM] = Ez-p(() [f(x) St x CC.
(44)
Now consider the distribution bk-m+ meem++11 S5 B the distribution of the first element sampled (without replacement) after sampling Bk-m given (conditionally on the event) that the set of samples is St so have bk-m+1 E S and bk-m+1 & B*-". This means that its conditional expectation f(bk-m+H is the restricted unordered set estimator for B -h- since
e US DS (8*) En=p(x) [f(x) E S Bh-m]
Es, m 1-ppppp---------e-ee--- m BB)
(45)
Observing that the definition (equation 42 of the stochastic uum-and-sample estimator does not depend on the actual order of the m samples, and using equation [5] we can reduce the multi- sample estimator to the stochastic sum-and-sample estimator with E." k + such that the result follows from equation 36
E Bh pp B( (5))
p(, )f(b,)
(1-I p(b,) j=1
D.S.Di (st)
k-m
k-m
EBg (pp(BB-)((s)
Σ ((bb)
Σ p(b;) j=l
US DUS, (5t)
k-m
k-m
E BB in mm Bh mlst)
Σ p(b)){(b;) +
1 Σ p(b;)
18 mi (bb 18t B my [f (11mm++))]]
1 k-m
BB -p(Bt-m+11ss)
Σ p(bz){(bs)) +
Σ m(b))
s(he-mtt)
k-m
k-m
= -gs- S5t-m4i
Ept-m+ingh 1p (1
Σ p(b))f(b,) +
-1-
E p(b,) f f(bx-mtt)
-Egt-m+ijst Ss
Σ (ls))((ssssf(0)
#ESE
Σ ((s) (s).
(46)
D THE IMPORTANCE-EIIGTTEE ESTIMATOR
D.1 RAO-BLACKWELLIZATION OF THE IMPORTANCE-WEIGHT ESTIMATOR
In this section we give the proof that Rao-Blackwellizznng the importance-weighhee estimator results in the unordered set estimator.
Theorem 6. Rao- tho-Blaccwellizinng the importance-weighted estimator results in the unordered set estimator, i.e.:
p(s) Po, (n) 5())
Σ
Σ p(s)R(S* s))(s)) BE
(47)
BESL
Here we have slightly rewritten the definition of the inportance-weighee estimator, using that q(8, a) = P(gs. > a) = 1 Fo, (a), where Fe, is the CDF of the Gumbel distribution (see Appendix A).
Proof. We first prove the following Lemma:
20

---

Published as a conference paper at ICLR 2020
Lemma 4.
1 Fo, (1²
Encplix st))
RRS* ,))
(48)
Proof. Conditioning on Sk: know that the elements in S have the k largest perturbed log- probabilities. so K, the (k + 1)-th largest perturbed log-probability is the largest perturbed log- probability in D 5*, and satisfies m D\.s* Io. 90m. Gumbel(@prss)) Computing p(s{55*) using Bayes' Theorem, we have
Sh) (((()))(() p(5*)
I (1 Fo, (K))S (K)
(49)
p(5k)
which allows us to compute (using equation 34 with C = {8}} and Gomis = k)
E Expp(N)S*)
Fs. (15)
p(1e|5%)
Ox
1 Fø. (16)
ILees
Fs. (w)) pyst (K)
1 Ox
p(sk)
Fb, (1)
II (E)")s}}
(1- 1-Fo. Fo, (k)) (K))
p(Sk)
1 P(Sk)
(S {s})
= -R(S* .8).
Using Lemma 4 we find
p(s)
E Expp(n|S4)
Σ BESA
Fo, (k) f(s)
((s)
Σ B(s)BRenp(n)s)
1
f(x)
1 1 Fer (1))
#E
Σ P(s)R(S* {8)(s))
D.2 THE IMPORTANCE- IMPORTANCE-WEIGHTELL WEIGHTED POLICY GRADIENT ESTIMATOR WITH BUILT-IN BASELINE
For self-containment we include this section, which is adapted from our unpublished workshop paper (Kool et al. 2019b). The importance-weighhe policy gradient estimator combines REIN-
FORCE (Williams 1992) with the inportance-weighted estimator (Duffield et al. 2007:
Vieira
2017 in equation| 15 which results in unbiased estimator of the policy gradient Vol [o]]]]
Po(s) (0.x(8)
Ve log (o() = Σ Vopo(s) f(s)
!WPG x)
Σ
(50)
(0.x(s)
BESE
#ESK
Recall that is the (k + 1)-th largest perturbed log-probability (see Section 3.2 We compute lower variance but biased variant by normalizing the importance weights using the normalization
((*)) Eeesk (z)
Po(s)
21

---

Published as a conference paper at ICLR 2020
As show in Kool al. (2019b), include 'baseline' B(5*) E EEs g0.n(s) (s)
pe(s)
f(s) and
correct for the bias (since it depends on the complete sample S by weighting individual terms of (s)
the estimator by (s) (o.)(a))
Vopo(s) (0,x
(()) 1 po(s)+ po(s) B(st))
(en(()) )
e @WPGBL (S*
(S*, R))
Σ
(51)
For the normalized version, we use the normalization W(S*) = De(s) W((5*) = W(S
(0) for the baseline, and
po(e) (#) + po( to normalize the individual terms:
Vopo(s) (s)
B(S*) W(S*)
Vol. [[()] Σ
f(s)
(52)
BES Wi(Sk)
seems odd to normalize the terms in the outer sum by WI(SF) instead of W(St but equation 52 can be rewritten into form similar to equation 17 i.c. with a different baseline for each sample, but this form is more convenient for implementation (Kool et al. 2019b).
1
E
THE UNORDERED SET POLICY GRADIENT ESTIMATOR
E. PROOF UNBIASEDNESS OF THE UNORDERED SET POLICY GRADIENT ESTIMATOR WITH BASELINE
To prove the unbiasedness of result we need to prove that the control variate has expectation 0: Lemma 5.
Eg (St)
Σ
(opo(s)R(S*. s)
Σ Pols') (oles) s())(())))))) 0.
(53)
#ESH
s'ESS
Proof. Similar to equation
10
apply Bayes' Theorem conditionally dj to derive for
#
=s P(S 8 s) = 81b1 8')
P(b = s'|sk, bi =
P( =)
DV } (S* (8,8')) 81)p DVlet (8')
Pe
Dioo (St (x))
Po
po(s')
DI s¹).
(54)
(s))
For s' = 8 we have RD (Sk 88) (8k,,') by definition, so using equation 54 we can show that
Σ (o(s))DD\o>>( s')(s''))))))
s'ESt
(s(s) +
Σ
Po(s') PM ('s.ss(s))
po(s') RD (8)))))
(s) + po()))
Σ
- (e(s)
3'ESt
(s(s)f(s) (1 po(s))
Σ
P(b Sh , s)f(s')
{s}
pp(s))((s) + (1 (Bn Sh, (f(b2)
Besc:po((s/St,b. =2) (bbb (100))0))))++000000000000000)00)
22

---

Published as a conference paper at ICLR 2020
Now can show that the control variate is actually the result of Rao- tto-Blackwelliizttinn:
(o s)
Σ
po(s') RD ())((())
SESE
s'ESk
Σ
Pe ( log
v
po (R (8)(((')
SES
#'E
(S
Σ P(b = = Volgoo(s
Σ
po P (8)(('))
#ES
s'ESt
(Skk)
Bb ppo (8k)
V (ogg
Σ (o (P P (S+ (')((s')
e'ES"
(St
B (bi
logpe (pp b1) (bb( + (1 (ot)) - (
(S$)
E Bd (BM144
Ve lo (b1)
B (Bk)
Ve log (obb) (po(bi)f(6)) + (1 - (ob)))
This expression depends only on by and by and we recognize the stochastic sum-and-sample estima- tor for le 2 used as "baseline", As special case of equation 13 for C' = {61), we have
Epa-po (balbr) b1) ((Po (b, (bb)) + (1 - (o = Ei-ro()) [f(()]
(55)
Using this, and the fact that B, (ppppo(b))) (b.) Vo rog))((b)) = V Vo [1] Vol = 0 we find
Vopo(s)R(S*... 8)
Σ Pols' (
SESE
s'ESt
EBa
V (b))) (po (b,))) (1 po(b:))f(b2)) (1-p
Epr~po(bi)
Vo log (b (Apopp (po(b)))(()) +1 (obb)))
V log pe (ox [f()]]
(bb)
Vo lo (b (x) [x)
0 (x)po(()
[x)]
0
23

---

Published as a conference paper at ICLR 2020
F THE RISK ESTIMATOR
F.1 PROOF OF BUILT-IN BASELINE
We show that the RISK estimator, taking gradients through the normalization factor actually has built-in baseline. We first use the log-derivative trick to rewrite the gradient of the ratio as the ratio times the logarithm of the gradient, and then swap the summation variables in the double sum that arises:
po(s)
RISK (RIS
ΣVe V
E Ed'ES EVESPO(O)) Po(8') ((s)
(s(
po(s)
)
Vo log
E ExesPo(s')
((s)
S'ES Po(
SES
(o(s)
Vo Vologro(s) - Vo log
Σ
po(o') f(s)
ES Po(
SES
PES
(s(
Vepo(s) Eves Vopp(s')
f(s)
YES Po(s')
Po(s) EvesPols))
(opo(s)f(s)
Poles
Eves Po(
(EresPo(s'))
(opo(s)f(s)
Po
SE Eves Do(s')
Vepo(s)
((s)) Eves f((s')
EvesPo(s")
(s)
po(s')
f(s) Σ
E 5(6))
SES Ex Po("")
s'ES
G CATEGORICAL VARIATIONAL AUTO-ENCODER
G.1 EXPERIMENTAL DETAILS
We use the code by Yin et al. (219)) to reproduce their categorical VAE experiment, of which we include details here for self-containment. The dataset is MNIST, statically binarized by thresholding at 0.5 (although we include results using the standard binarized dataset by (Salakhutdinov & Murray 20088: Larochelle Murray (2011) in Section G.2). The latent representation is K 20 dimen- sional with C' = 10 categories per dimension with a uniform prior p(z = c) = 1/C, k = 1,..., K. The encoder is parameterized by Φ
(2|xx) II (2 (x) and has two fully connected hidden layers with 512 and 256 hidden nodes respectively. with LeakyReLU (a = 0.1) activations. The decoder, parameterized by 0, is given by (x)l)) = II. Po [=) where æ; {0, 1} are the pixel values, and has fully connected hidden layers with 256 and 512 nodes and LeakyRel.U activation.
ELBO optimization.
The evidence lower bound (ELBO) that we optimize is given by L( 0) Eznga(=la) [o (z) /)) + In p(z) In go [x)]
(56)
Ez>go(>)e) [ln =)] - KL [=|=)|[[(()
(57)
For the decoder parameters 0 since q ( (x) does not depend 0, it follows that
VoL(d, 0) Ez (V In po (x|
(58)
For the encoder parameters d, we can write Le 0) using equation 57 and equation 19 as (me VoKLiga (z))))
V CsL(6,)) = Ez =
V
(59)
ARM gradi wetrraddeent/SSS
24

---

Published as a conference paper at ICLR 2020
This assumes compute the KL divergence analytically. Alternatively, estimate for the KL divergence, and use equation 56 with equation to obtain
sample
( 0) ( In gp [x) po (=]=) + Inp()) go (z)=)) In go (2|ar)
(60)
(=la) In Co go (In
In (x(
(61)
Here we have left out the term [g [V In go = 0, similar to Roeder et al. (2017)
and,
assuming a uniform (i.e. constant) prior In p()), the term E2 (gz-g+<>le) [V go (2 In p(z)
0.
With built-in baseline, this second term cancels out automatically, even if it is implemented De- spite the similarity
the equation 56 and equation 57 their gradient estimates (equation 60 and equation (59 are structurally dissimilar and care should be taken to implement the REINFORCE estimator (or related estimators such as ARSM and the unordered set estimator) correctly using au- tomatic differentiation software. Using Gumbel-Softmax and RELAX, we take gradients 'directly' through the objective in equation 57
We optimize the ELBO using the analytic for 1000 epochs using the Adam (Kingma & Ba 2015) optimizer. We use a learning rate of 10-3 for all estimators except Gumbel-Softmax and RELAX, which use learning rate of 10-4 as we found they diverged with a higher learning rate. For ARSM, as exception we use the sample KL, and learning rate of 3 10
suggested by the authors. All reported ELBO values are computed using the analytic KL. Our code publicly available"
G.2 ADDITIONAL. RESULTS
Gradient variance during training. We also evaluate gradient variance of different estimators during different stages of training. We measure the variance of different estimators with k: = samples during training with REINFORCE with replacement, such that all estimators are computed for the same model parameters. The results during training, given in Figure 4 are similar to the results for the trained model in Table except for at the beginning of training, although the rankings of different estimator are mostly the same.
Negative ELBO on validation set. Figure shows the -ELBO evaluated during training on the validation set. For the large latent space, we see validation error quickly increase (after reaching a minimum) which likely because of overfitting (due to improved optimization), a phenomenon observed before (Tucker et al. 2017 Grathwohl et al. 2018). Note that before the overfitting starts, both REINFORCE without replacement and the unordered set estimator achieve a validation error similar to the other estimators, such that in practical setting, one
early stopping.
Results using standard binarized MNIST dataset. Instead of using the MNIST dataset binarized by thresholding values at 0.5 (as in the code and paper by Yin et al. (2019) we also experiment with the standard (fixed) binarized dataset by /Salahhuddinov & Murray 2008); Larochelle & Murray (001)), for which we plot train and validation curves for two runs on the small and large domain in Figure 6 This gives more realistic (higher) -ELBO scores, although we still observe the effect of overfitting. As this is a bit more unstable setting, one of the runs using REINFORCE with replacement diverged, but in general the relative performance of estimators is similar to using the dataset with 0.5 threshold.
httees/s/.tttaccooooooe/ee/eeees wtt. rep1 acement
25

---

Published as a conference paper at ICLR 2020
Thanisg log varance space), IDTO
Training ug varlance
scace), samo
12 A55
33.27 Sur Jungi
12
6.0 Learcen Daloora
5.45 Sar surai cariia
6,25 fam berek
382
20
(a) Small domain (latent space size 10²)
(b) Large domain (latent space size 1020)
Figure 4: Gradient log variance of different unbiased estimators with k 4 samples, estimated every 100 (out of 1000) epochs while training using REINFORCE with replacement. Each estimator is computed 1000 times with different latent samples for fixed minibatch (the first 100 records of training data). We report (the logarithm of) the sum of the variances per parameter (trace of the covariance matrix). Some lines coincide, so we sort the legend by the last measurement and report its value.
Valiiediinn E 110" latere Space)
Valcation 6:90 [104) stace)
360
STo Sefree
1203
Si coree Ooegle
224.2 Unarcnne DuLTEE
340
18.
330
420
6/2 123
320
420
(a) Small domain (latent space size 1
(b) Large domain (latent space size 10
Figure 5: Smoothed validation -ELBO curves during training of two independent runs when with different estimators with k = 1, 4 or 8 (thicker lines) samples (ARSM has a variable number). Some lines coincide, so we sort the legend by the lowest -ELBO achieved and report this value.
26

---

Published as a conference paper at ICLR 2020
canole Garpa
350
te ROSPONCE burdee
1304
130.4
Lnvremed
140
10.
330
abc
41
66
2/4
46c
aas
spack
Lacck
(a) Training -ELBO, small domain (10?)
(b) Training -ELBO, large domain (1020)
2108 nas
34C
1902 891
1i Kan coree Comple
C (arre
130
14L5
14:
375
330
(c) Validation ELBOO small domain (10?)
(d) Validation -ELBO, large domain (1020)
Figure 6: Smoothed training and validation ELBO curves during training on the standard binarized
MNIST dataset (Salakhutdinov & Murray 2008
Larochelle & Murray (011) of two independent
runs when with different estimators with k = 1,4 or 8 (thicker lines) samples (ARSM has a variable number). Some lines coincide, so we sort the legend by the lowest -ELBO achieved and report this value.
27

---

Published as a conference paper at ICLR 2020
H TRAVELLING SALESMAN PROBLEM
The Travelling Salesman Problem (TSP) is discrete optimization problem that consists of finding the order in which visit set of locations, given as x, y coordinates, minimize the total length of the tour, starting and ending at the same location. As a tour can be considered a sequence of locations, this problem can set up sequence modelling problem, that can be either addressed using supervised (Vinyals et al., 2015) or reinforcement learning (Bello et al. 2016 Kool et al. 2019a).
Kool et al. (019a) introduced the Attention Model, which is an encoder-decoder model which considers TSP instances as a fully connected graph. The encoder computes embeddings for all nodes (locations) and the decoder produces tour, which is sequence of nodes, selecting one note at the time using an attention mechanism, and uses this autoregressively as input to select the next node. Kool et al. (2019a), this model is trained using REINFORCE, with greedy rollout used as baseline to reduce variance.
We use the code by Kool al. (2019a) to train the exact same Attention Model (for details refer to Kool et al. (2019a)), and minimize the expected length of tour predicted by the model, using different gradient estimators. We did not do any hyperparameter optimization and used the exact same training details, using the Adam optimizer (Kingma & Ba 2015) with learning rate 10-4 (no decay) for 100 epochs for all estimators. For the baselines, we used the same batch size of 512, but for estimators that use k = 4 samples, we used a batch size of 512 128 to compensate for the additional samples (this makes multi-sample methods actually faster since the encoder still needs be evaluated only once).
4
28


Reviews:
[{"review_id": "rylJnHURKr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: This paper introduces an gradient estimator for loss functions that are expectations over discrete random variables. The basic idea is that an estimator over a discrete distribution can be Rao-Blackwellized by conditioning on the event that the discrete realization was produced by being the first sample drawn from an unordered set of samples drawn with replacement. Much of the paper is spent showing how this Rao-Blackwellized estimator can be computed in practice and how it compares to other known estimators.\n\nOriginality: This idea is original and quite nice.\n\nClarity: The paper is very easy to understand and well-written.\n\nQuality:\n- The derivations are all correct from what I can tell, and easy to read.\n- The experiments are all reasonably well done, but I could not find where the authors report which optimizer was used and how the hyperparameters were set. If I missed it, could the authors point that out in the rebuttal? If it is missing, then I strongly suggest that the authors include that in the paper. Even if the training protocol is taken from another code base, I think this paper should be reasonably self-contained. How the hyperparameters are tuned and which optimizer was used could affect the interpretation of the results. Additionally, if overfitting is an issue, I recommend the authors consider the use of regularizers, like weight decay. I see no reason that this would violate the spirit of the paper, and might make their results more compelling.\n\nSignificance: \n-This paper has some interesting ideas, and it is written well. So, it may inspire future work. Yet, from the experiments it is not obvious that this estimator adds much to the existing literature. In all experiments at least one known estimator matches the performance of the unordered set estimator. \n- All of these estimators, which require multiple evaluations of the gradient, are generally less common in practice. ", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "H1l1_PuhKB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: In this paper, an unbiased estimator for expectations over discrete random variables is developed based on a sampling-without-replacement strategy. The proposed estimator is shown to be a Rao-Blackwellization of three existing unbiased estimators with guaranteed reduction in estimation variance. The connections of the method to other gradient estimators are discussed. Experimental results on several toy and real-data DL/RL problems are reported to demonstrate the applicability of the proposed estimators in the practice of machine learning. \n\nStrong points:\n\n-S1. The addressed topic is interesting and timely in deep/reinforcement learning.\n\n-S2. The numerical results show some promise of the proposed estimator in reducing the gradient estimation variance in practice.  \n\nWeak points:\n\n-W1. A formal and detailed problem statement is missing. The paper quickly jumps from a high-level problem setup description in the introduction section into some technical details in the preliminary & methodology sections, without any formal definition of the so called unordered set policy gradient estimation problem provided. What is the input/output of the estimator? Why this problem is important and challenging? It will be better to provide one or two concrete examples such as those studied in the experiments to give a more complete picture of the problem in study. \n\n-W2. The motivation of study is not clearly elaborated. There are several existing options to reduce the gradient estimation variance via Rao-Blackwellization [see, e.g., Liu et al. 2019]. In which regimes the current method is more preferable than those prior ones and why? The justification of using the without-replacement-sampling strategy so far remains largely unconvincing. \n\n-W3. The overall novelty of theory is limited. It makes sense that gradient estimators based a mini-batch of sample under without-replacement-sampling should tend to have smaller variance than the single-sample stochastic gradient estimation. Although a guarantee of variance reduction from the perspective of Rao-Blackwellization looks promising, the proof technique is fairly standard and more importantly, the quantification of such a variance reduction remains largely unaddressed. Therefore, the overall degree of novelty in theory is still relatively low. \n\n-W4. The paper presentation quality can be improved. As another consequence of the above mentioned issues with problem statement and motivation, I found the paper a bit hard to follow smoothly. Particularly, too much space is spent on presenting the technical details while the principles/intuitions behind these fancy mathematical treatments are lacking in explanation. There are three theorems established in the paper, but none of them come up with sufficient discussions on the main messages conveyed by these results. \n\n=== update after author response ===\n\nThank you for your response. I find my concerns on motivation and presentation properly addressed in the feedback and the revised paper as well.  Concerning the strength of theory, however, I am still not convinced that the current analysis is strong enough to thoroughly justify the benefit of the proposed estimator. All in all, the paper is substantially improved in presentation and the proposed gradient estimator seems to be a novel and more attractive alternative to the existing ones in a number of popular DL/RL applications. I thus would like to increase the rating to weak accept.\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "B1l84u7oFS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Edited after rebuttal:\nI'm satisfied with the clarifications provided by the authors about where they see this work being applicable. I think they have correctly identified a setting that is of interest to a broad audience and where their approach is more attractive than the alternatives. I now recommend accepting this paper.\n\nThe authors develop a generic method for estimating expectations under discrete distributions based on sampling without replacement and apply it to the task of estimating gradients for training models with discrete latent variables. The proposed estimator is unbiased and the authors prove it has lower variance than the naive Monte Carlo estimator.\n\nI weakly recommend rejecting the paper. While the derivations and theorems presented in the paper are correct, the experiments are sensible and support the claims made, my impression is that the range of applications where the proposed method is a better alternative to the existing algorithms is extremely narrow. I would be willing to raise my rating to Weak Accept if the authors convince me that their method is useful more broadly than I think it is.\n\nThe method derivation is generally well-written and easy to follow. However, the account of the sum-and-sample estimator is somewhat misleading. As is, it suggests that it is natural to sum over k-1 elements and only draw one sample, while in fact choosing how many elements to sum over (I'll call this number S in my review) and how many samples to draw from the remaining set is the crucial step needed to make this algorithm work well. This is discussed by Fearnhead and Clifford [1] in the context of resampling in particle filters and I believe is also addressed by Liu et al. (2019). I understand that the authors are guiding the presentation towards a version of sum-and-sample they can compare with in theory and in experiments, but in the process they're doing a disservice to the reader. I think the authors should state the importance of choosing S well early on and then either compare with methods that attempt to set S optimally throughout experiments, or clearly explain that they restrict their discussion to a particular setting where S is difficult to optimize and explain why.\n\nThere are also additional baselines that should be considered. This includes methods such as stratified or systematic sampling, which are often discussed within the context of resampling [2]. Another strong but somewhat obscure baseline is given by Duffield et al. [3]. While it is possible that none of those methods are applicable in the experimental setting chosen in the paper, the authors should be very clear about how broadly they claim superiority of their method.\n\nOn the topic of experimental evaluation, the authors seem to have focused on the setting where sampling is done using stochastic beam search, presumably because in such a setting some of the strong baselines mentioned above, including sum-and-sample with the optimal choice of S, are not applicable. If that's true, I would like to see a detailed discussion about what it is about the problem setting that makes alternative baselines inapplicable. My current impression is that the proposed method is only worth considering when used with a stochastic beam search and I don't think such settings are particularly common. This is my main complaint about the paper.\n\nOn the subject of applicability, the experiments only test the proposed method in very low k settings, where the exponential algorithm for computing the leave-one-out ratio can be applied. While the appendix mentions that there is a faster alternative based on numerical integration, the claim that it can be efficiently integrated is not substantiated anywhere.\n\nThe plots could use some improvement. It took me a lot of squinting at Figures 2 and 3 to figure out what's going on, since the lines overlap too much - I couldn't even find the Unordered line in Figure 2 at first. Also I'm confused about why lines for sum-and-sample in Figure 1 extend beyond 8 evaluations, and VIMCO does not. Also figure captions could be a little more self-contained.\n\nFinally, I would recommend stating Theorem 1 in more concrete terms, such as \"estimator A has lower variance than estimator B\".\n\n[1] P. Fearnhead and P. Clifford. On-line inference for hidden Markov models via particle filters. Journal of the Royal Statistical Society, 65:887–899, 2003.\n[2] R. Douc, O. Cappé, and E. Moulines. Comparison of resampling schemes for particle filtering. In ISPA, 2005.\n[3] N. Duffield, C. Lund, and M. Thorup. Priority sampling for estimation of arbitrary subset sums. Journal of the ACM, 54, 2007.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors derive a novel, unbiased gradient estimator for discrete random variables based on sampling without replacement. They relate their estimator to existing multi-sample estimators and motivate why we would expect reduced variance. Finally, they evaluate their estimator across several tasks and show that is performs well in all of them.

The reviewers agree that the revised paper is well-written and well-executed. There was some concern about that effectiveness of the estimator, however, the authors clarified that "it is the only estimator that performs well across different settings (high and low entropy). Therefore it is more robust and a strict improvement to any of these estimators which only have good performance in either high or low entropy settings." Reviewer 2 was still not convinced about the strength of the analysis of the estimator, and this is indeed quantifying the variance reduction theoretically would be an improvement.

Overall, the paper is a nice addition to the set of tools for computing gradients of expectations of discrete random variables. I recommend acceptance.


Decision: Accept (Spotlight)