Low Bias Gradient Estimates for Very Deep Boolean Stochastic Networks
Authors: Adeel Pervez
Taco Cohen
Efstratios Gavves
Venue:  (2020)

Abstract: Stochastic neural networks with discrete random variables are an important class of models for their expressivity and interpretability. Since direct differentiation and backpropagation is not possible, Monte Carlo gradient estimation techniques have been widely employed for training such models. Efficient stochastic gradient estimators, such Straight-Through and Gumbel-Softmax, work well for shallow models with one or two stochastic layers. Their performance, however, suffers with increasing model complexity.
In this work we focus on stochastic networks with multiple layers of Boolean latent variables. To analyze such such networks, we employ the framework of harmonic analysis for Boolean functions.  We use it to derive an analytic formulation for the source of bias in the biased Straight-Through estimator. Based on the analysis we propose \emph{FouST}, a simple gradient estimation algorithm that relies on three simple bias reduction steps. Extensive experiments show that FouST performs favorably compared to state-of-the-art biased estimators, while being much faster than unbiased ones. To the best of our knowledge FouST is the first gradient estimator to train up very deep stochastic neural networks, with up to 80 deterministic and 11 stochastic layers. 

Under review as a conference paper at ICLR 2020
Low BIAS GRADIENT ESTIMATES FOR VERY DEEP BOOLEAN STOCHASTIC NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
Stochastic neural networks with discrete random variables are an important class of models for their expressiveness and interpretability. Since direct differentiation and backpropagation is not possible, Monte Carlo gradient estimation techniques have been widely employed for training such models. Efficient stochastic gradient estimators, such Straight-Through and Gumbel-Softmax work well for shallow models with one or stochastic layers. Their performance, however, suffers with increasing model complexity.
In this work we focus on stochastic networks with multiple layers of Boolean latent variables. To analyze such networks, we employ the framework of harmonic analysis for Boolean functions. We use it to derive analytic formulation for the source of bias in the biased Straight-Throve we propose FouST, simple gradient estimation algorithm that relies three simple bias reduction steps. Extensive experiments show that FouST performs favorably compared to state-of-the-art biased estimators, while being much faster than unbiased ones. To the best of our knowledge FouST is the first gradient estimator to train very deep stochastic neural networks, with up 80 deterministic and 11 stochastic layers in our experiments.
estimator. Based on the analysis
INTRODUCTION
Stochastic neural networks with discrete latent variables have been alluring class of models for their expressivity and interpretability, dating back to foundational work on Helmholtz machines (Dayan et al. 1995) and sigmoid belief nets (Neal 1992). Since they are not directly differentiable, discrete random variables do not mesh well with the workhorse of modern Deep Learning, that is the backpropagation algorithm. Monte Carlo gradient estimation is an effective solution where, instead of computing the true gradients, one can sample gradients from some distribution. The sample estimates can be either biased or unbiased. Unbiased gradient estimates like score function estimators (Williams 1992) come typically at the cost of high variance leading to slow learning. In contrast, biased gradient estimates such Straight-Through (Bengio et al., 2013). while efficient, run the risk of convergence to poor minima and unstable training. To this end several solutions have recently been proposed that either reduce variance in unbiased estimators MMnih Gregor 2014 Gu et 2015 Tucker et al.] [017]] Rezende et al.] 20144 Grathwohl et 2017) or control bias in biased estimators (Jang et al. [0166] Maddison et 2016).. These methods, however, have difficulty scaling up to complex neural networks with multiple stochastic layers: low-variance unbiased estimators are too expensive [. while the compounded bias from the continuous relaxations on multiple stochastic layers leads poor minima. In this work we focus biased estimators.
Our goal in this paper is a gradient estimator for Boolean random variables that works for any complex -deep or wide- neural network architecture. We resort to the term Boolean instead of binary to emphasize that we work directly on the Boolean space {-1, +1), without any continuous relaxations or quantizations. With this in mind we re-purpose the framework of harmonic analysis of Boolean functions, widely used in computational learning and computational complexity theory OODoonelll 2014, Linial et al. 1993, Mossel et al. 2003] Mansour 1994). We cast stochastic neural networks as Boolean functions f (2) over Boolean latent variables sampled from probability
'Training nonlinear sigmaid belief network model with two stochastic layers on MNIST with REBAR took day and a half on GPU.

---

Under review as a conference paper at ICLR 2020
Algorithm FouST Gradient Estimator
Require: Parameters E RK Bernoulli Representation {-a, a}. Interval Parameter b E [0, a].
Constant scaling parameter
1: Sample 24 Po, (z+), L...., K
> This and all steps below have constant complexity.
2: Sample y4 (ni a)
3: Set V/i := 24; y/
4: Compute ST gradient 0o == 8y. f(y)
5: Importance reweighing 0g, : 0.5/p(x;) 0g.
6: return partial gradient y0s, i 1,...
distributions p(2). We then use harmonic analysis to determine that the bias in the Trriigh-Thhough gradient estimates corresponds to the weighted sum of higher-order Taylor coefficients of f(z). The direct consequence is that one can control the bias in the Straigh--Throue estimator by manipulating the higher-order Taylor coefficients of [(z). Building upon the harmonic analysis of existing gradient estimators, we present an algorithm, FouST, that admits low bias gradient estimates for Boolean latent variable models. In experiments, networks, training deep stochastic residual networks with up to 80 deterministic and stochastic layers with little difficulty. We summarize FouST in Algorithm 1
were able to scale up the stochastic depth and width of neural
With this work we make the following three contributions.
1. We introduce the framework of harmonic analysis of Boolean functions to analyze discrete stochastic neural networks and their REINFORCE and Straight-Through gradients. We show that stochastic gradients compute Fourier coefficients.
2. Based on the above harmonic analysis we present FouST a low-bias gradient estimator for Boolean latent variables based on three bias reduction steps. As side contribution, we show that the gradient estimator employed with DARN (Gregor et al. (003)), originally proposed for autoregressive models, is a strong baseline for gradient estimation in large and complex models with many stochastic layers.
3. We show that FouST is amenable complex stochastic neural networks with Boolean random variables. To the best of our knowledge, FouST is the first gradient estimate algorithm that can train very deep stochastic neural networks with Boolean latent variables.
The practical outcome is simple gradient estimate algorithm that can be plugged in complex stochastic neural networks with multiple layers of Boolean random variables.
2 HARMONIC ANALYSIS OF BOOLEAN FUNCTIONS
We consider Boolean functions on the n-diimensionll Boolean cube, / (-1,+13" - R. The setting of Harmonie Analysis for Boolean functions is the space of Boolean functions f with product probability distribution on the Boolean input, that is p(z) I ==1 Pz(2). We denote pt as the probabilitt of the i-th dimension being one, i.e., p; == p1(a +1). We denote the mean and variance of 2; by μ4 and o, respectively.
example of Boolean function in this setting a generative neural network f f -> y with factorized latent distribution, as commonly done in representation learning (Kingma & Welling 2013) Higgins et al. 2017). In this example, is the stochastic input also known as the latent code in stochastic neural networks taking only two possible values and y is the output, like cross entropy loss. Often, the goal of generative neural network is to learn or approximate the latent distribution given input data æ, i..., p(2 (z),
will also explore in the experiments.
We first introduce a few basic operations the context of Harmonic Analysis of Boolean func- tions, which shall use further Further necessary details are in the Appendix A For more comprehensive introduction, however, we refer the reader to O' D'Donnell
Inner product. The inner product of two Boolean functions and g is: (f.g) (f (2)] Fourier expansion. Let S be any subset of dimensions of the n-diiensional Boolean cube, S S [n] ..,...... n). Per S we define a basis function, (s(2) = Ih (x(2)), where for the empty set
2

---

Under review as a conference paper at ICLR 2020
(2) = 1 and is the z-score normalized dimension, i.e., -: For example, under the uniform Bernoulli distribution for the i-th dimension, Pr(2; = +1) p, -1) 1/2, have (z(z) The 2n functions ds form an orthonormal basis for the space of Boolean functions f.
(x)=)) =1
(pt))) (2)) =
(1)))()
for j. where the expectations compute the inner product between two Boolean functions. The last identity derives from the independence of any dimensions i j.
We then expand the Boolean function on the set of 2n orthonormal basis functions,
f(z)
Σ
(S)Øs())
SCIm]
also known as the p-biased Fourier expansion of f. The (S) are the Fourier coefficients computed by the inverse Fourier expansion,
(3)
That is, the inverse expansion is computed by the inner product for Boolean functions defined above. The cardinality of S is the degree of the coefficient (S). For instance, we have only one degree-O coefficient, (2), which equals to the expected value of f under the distribution p(z). f(r) (2) [=)( since de 1. Further, have degree-1 coefficients f(() (i) (ʃ. db) and so on.
HARMONIC ANALYSIS ON BIASED STRAIGHT-THROUGE GRADIENTS
We examine
gradient estimates using the framework of Harmonic Analysis of Boolean functions. For training the model parameters with a loss function C = Ep(x) [f)) we want to compute the gradient 0,, C 0, (=)) for the i-th dimension. As the random sampling operation the expectation is not differentiable, Bengio et al. (2013) propose the Straight Straight-Through estimator that approximates the gradient with 0p, L == Bp(=) 00 J [z)]. Clearly, the Straight- Trigghh-Thuughh
computes biased approximation the true gradient.
Next, we quantify the bias in the Straight- Straight-Through the quantification of bias we first need the following lemma that connects the REINFORCE gradients with the degree-1 1 Fourier coefficients. The lemma is an extension of Margulis Russso (Margulis) 1974 Russo| 1982, O'Donnell 20114) formula.
Through estimator using the harmonic analysis of fzr) For
Lemma 1. Let f be Boolean function. Then, the REINFORCE gradient estimates the degree I Fourier coefficients (i) of f under p(z).
Ex(e) [REENFORCE] 0p. (pp)
2 -
Proof. For compactness and clarity, provide the proof in the Appendix B.1
We introduce notation. In the following lemma bias(r) (g' denotes the bias of the i-th gradient estimate under the distribution Also, given the distribution p(z), p² (z) is the distribution for which we set p(2, +1) = p(z, = -1) 1/2 for given dimension i. Lemma 2. Let f be a Boolean function, g" [f its true gradients and S' Ep(z) [0 [()] its Straight- Straight-Through gradient estimator. The bias in 9 due to mismatch between the higher-order odd terms in the Taylor expansion of g¹ and otz and is equal to
bias (p) (0,7) = bias (p'-1/2)
(0 - -E
KCR
14
(4)
A A=2
3

---

Under review as a conference paper at ICLR 2020
where ck are the Taylor coefficients for the i-th dimension f()), that is 24, around 0 and bias(r 12/2)
E 2)
Proof. For compactness and clarity, we provide only a proof sketch here showing the basic steps. These steps also needed later in the description of the proposed gradient estimate algorithm. For the detailed proof please refer to the Appendix 18.2] The proof sketch goes as follows. First, we derive relation between the Fourier coefficients under the unknown distribution p(z) and under the
uniform Bernoulli distribution p p))+ Then, using this relation we derive the Taylor expansions
for the true gradient as well as the Straight-Thoouhh Through gradient estimator. Last, to prove the lemma we compare the Taylor expansions.
Relation between Fourier coefficients under p(z) and p (z)) If we expand the function f in terms of its dg basis as in equation 2 and focus the i-th dimension, Lemma we show that the REINFORCE gradient is given by
(1) 2 3p ((c)) ( Oi
(5)
Taylor expansions of the true and the Straight-Through gradients. The Taylor expansion of f()) for x around O is given by f(z co + cı + 622 + caz, + c22f + c52 + where cykl = 0 fz))(== are the Taylor coefficients. All C are a function of zj.J + +i.
Let's first focus on the true gradient. Since we work with Boolean #1 values, we have that of = 1 for even l and 2 = 2; for odd k. This will influence the even and the odd terms the Taylor expansions. Specifically, for the Taylor expansion of the true gradient
show that
Op. (p1n = 2f (1) 2 (2) + c + c22 + +...
(6)
2I (cr + c +
The expression in equation 7 jimplies that the true gradient with respect the p3 the expected sum of the odd Taylor coefficients. Here we note that although the final expression in equation ( can also be derived by a finite difference method, does not make explicit, as in equation 31, the dependence on and μ4 of the term inside the expectation.
Now, let's focus on the Straight- Straight-Through gradient. Taking the derivative of the Taylor expansion w.r.t. to we have
fz.f(=) + 202zi + 3032 4c42, + 50g
(8)
The Straight- Throughh gradient is the expectation of equation X in the i-th dimension, that is
[=;)))=;[[())) [c + 2022; + 30 4c42 2i + 5csz +...] Ep(t,,) /ea + 30s 5cs + ... Ep( [2c2 + 4ca +..
(9)
(10)
where 2/1 = 1, 2j+1 z;, and (Epce = 14--
Comparing the Taylor expansions. By comparing the expansion of the Straight-Through Through gradient in equation 10 and the expansion of the true gradient in equation 7 and given that bias (P) (o
10, [p))
(p) (o =Ep()))))
Σ
(I: - 2)cx + Exp()r))
Σ k=21->0
kook
14i-
(11)
k=
Taking the expectation in equation leaving (ia (g) = Ep(a,)
under - causes the final term in equation 11 to vanish
Σ Ex=2j+15sof 2)c²} Combining this expression with equation 9 gives the final expression (equation 4 from the lemma.
4

---

Under review as a conference paper at ICLR 2020
4 LOW-BIAS GRADIENT ESTIMATES
4.1 FOUST GRADIENT ESTIMATION ALGORITHM
Inspired by the Harmonic Analysis of the Straight-Through gradient estimates, we present gradient estimate algorithm for deep Boolean latent models, FouST, for Fourier BtraightTThrouge estimator. The algorithm relies on three bias reduction steps on the Straight- TrrighhtThrough, lines 2, 5 in Algorithm
4.2 LOWERING BIAS BY IMPORTANCE SAMPLING CORRECTION
As detailed earlier, the bias in the Straight-Thhee Through estimator is the sum of the bias under the uniform Bernoulli distribution plus extra bias due to non-zero expectation terms higher-order harmonics when sampling from p(z). Sampling from p² p² instead of p(2) would decrease the total bias from the form in equation I by setting the final term to O.
As a first bias reduction step, therefore, we do importance sampling. Specifically, after getting samples from p(=) and computing the gradients fz; with the Sraight-Through, we estimate the expectation under 1112
(2)) Oz [()] = Ep(=)) 2p(2;)
On [())
(p) ())) = 1/2)
(12)
Interestingly, Gregor et al. (2013) arrive at equation 12 in the context of unbiased control variates for quadratic functions.
4.3 LOWERING BIAS BY MATCHING UNIFORM DISTRIBUTION MOMENTS
Lemma shows that part of the bias in the Straight-Throuus estimator due to the presence of extra factors the Taylor coefficients. We can reduce the effect of these factors by taking advantage of the moments of the uniform distribution. Recalling that fo 1 u the coefficients in equation 9 which for =* have the form (k: + 1)ck. with the same extra factor of k + 1 that appears in the denominator of the kth moment. This suggests that can sample from an auxiliary variable u and then use the auxiliary variable u with f instead of and exploit the higher moments the uniform distribution reduce bias.
g*
E+I we can attempt correct
For brevity, we illustrate the method with case study of a two-dimensional 2, and a bivariate 22),
As in Lemma 2 the partial true gradient of f(21, 22) w.r.t. the first distribution parameter equals to Σ cas Epailss
0p, Ez)) Σ E
Σ Cs. Bp(2)
(13)
"Bernoulli splitting uniform" trick.
Assume an auxiliary variable (u,, U2), which we choose
as follows. First, sample = = (21, 22) from the uniform Bernoulli distribution p 11-1/2 with (i set to 1). Then we take a uniform sample (u1, U2) with u, sampled from either [0, for 2; = +1 or from [-1,0] if -1
The expectation of the gradient under such random sampling is
Ex 10,, (ui u2)]
Σ CLi E. + Σ
E
C3. E
(14)
Further detail is in Appendix C. We compare equation 14 with equation 13 In equation 14 we observe that the pure terms 21, namely terms with O. always match those of the true gradient in equation 13 For > ( we obtain mixed terms with coefficients that do not match those of the true gradient in equation
1 factor, for small j the mixed-degree terms are closer to Due to the J+I
1 For functions with small mixed degree terms, this can lead to bias reduction, at the cost of an increased variance because of sampling an auxiliary variable. In practice, to manage this birs-variance trade-off and to deal with functions that have greater dependence on mixed degree terms, use smaller intervals for the random samples in Algorithm
the original ones in equation
5

---

Under review as a conference paper at ICLR 2020
To summarize, for appropriate functions, the "Bernoulli splitting uniform" relies on the continuous variable u conditioned on the binary sample to reduce the bias. However, it is important to emphasize that is only auxiliary variable; the actual latent variable is always binary. Thus, the "Bernoulli splitring uniform" trick does not lead to a relaxation of the sort used by Gumbel-Softmax (Jang et al., 2016), where there are hard samples. Lastly note that for univariate the "Bernoulli splitting uniform" trick leads to an unbiased estimator with an increased variance.
4.4 LOWERING BIAS BY REPRESENTATION SCALING
The Fourier basis does not depend on the particular input representation and any two-valued set, say {-t, } can be used as the Boolean representation. The choice of representation, however, does affect the bias as we show next. As a concrete example, we let our input representation be 2, 1-21 1/2]", where p; p(z; +1/2). While we change the input representation like that, in general the Fourier coefficients equation will be different than for the f-1,+1 representation. We give the final forms of the gradients here. Details are given in Appendix C.2
Under the p1/1 distribution the degree-1 Fourier coefficients are:
fl (2))
C1
C3 23
(15)
2
25
we still get the odd terms c₁, C3 albeit decayed by inverse powers of 2. Following the same process for the Straight-Through gradient as in equation 10 we have that
Note that compared to equation 7 in equation 15
1 2
1/2 (0.. (0
R
C1
303
5cs
+--
(16)
23
25
While this is still biased, compared to equation the bias is reduced by damping higher order terms by inverse powers of 2.
4.5 ALGORITTMIC COMPLEXITY
The algorithm, described in algorithm || is a Straight- Throouhh gradient estimator with the bias reduction steps described above, where a single sample is used to estimate the gradient. We emphasize that the algorithm uses a single sample and a single evaluation of the decoder per example and latent vector sample. Thus, the algorithm has the same complexity as that of the original estimator.
RELATED WORK
Monte Carlo gradient estimators for training models with stochastic variables can biased or unbiased. Perhaps the best known example of an unbiased gradient estimator is the REINFORCE algorithm (Williams) 1992). Unfortunately, REINFORCE gives gradients of high variance. For continuous stochastic variables Kingma & Welling (2033) propose the reparameterization trick, which transforms the random variable into a function of deterministic ones perturbed by a fixed noise source, yielding much lower variance gradient estimates. For discrete stochastic variables, REINFORCE is augmented with control variates for variance reduction. A number of control variate schemes have been proposed: NVIL (Mnih & Gregor 2014) subtracts two baselines (one constant and one input-dependent) from the objective to reduce variance. MuProp (Gu et al., 2015) uses the first-order Taylor approximation of the function as baseline. REBAR (Tucker al. 2017) uses the Gumbel-Softmax trick to form a control variate for unbiased gradient estimates. RELAX (Grathwohl et al. 2017) generalizes REBAR to include an auxiliary network in the gradient expression and uses continuous relaxations and the reparameterizzttion trick to give unbiased gradients.
estimator (Bengio et al., 2013) which uses the gradient relative to the sample that relative to the probability parameter. Another recent approach is to use continuous relaxations of discrete random variables so that the reparameterization trick becomes applicable. The most common example of this being the Gumbel- Softmax estimator (Maddison et al. (2166) Jang et al., 2016). Although this is a continuous relaxation, it has been used to define the Gumbel Straigh-TThrouge estimator with hard samples. This uses
Regarding biased estimators, a simple choice is the

---

Under review as a conference paper at ICLR 2020
arg max in the forward pass and the Gumbel-Softme gradient is used as approximation during in the backward pass. DARN (Gregor et al. 2013). like MuProp, also uses the first-order Taylor expansion baseline but does not add the analytical expectation, making the estimator biased for non-quadratic functions.
In this work focus biased Straight-Through gradient estimators. Specifically, analyse how to reduce bias via Fourier expansions of Boolean functions. The Fourier expansion itself is widely used in computational learning theory with applications learning low-degree functions (Kushilevitz & Mansour 1993). decision trees (Mansour) 1994). constant-depth circuits (Linial et al. 1993) and juntas (Mossel et al., 2003). To the best of our knowledge we are the first to explore Fourier expansions for bias reduction of biased stochastic gradient estimators.
EXPERIMENTS
Experimental Setup. We first validate FouST toy setup, where we already know the analytic expression of f(z). Next we validate FouST by training generative models using the variational autoencoder framework Kingma & Welling (2013). We optimize the single sample variational lower bound (ELBO) of the log-likelihood. We train variational autoencoders exclusively with Boolean latent variables on OMNIGLOT, CIFARIO, mini-ImageNet (Vinyals et al.) 2016) and MNIST (Appendix D.I). We train all models using regular GPU with stochastic gradient descent with a momentum of 0.9 and a batch size of 128. We compare against Straight-Through Gumbel- Softmax, and DARN, although more complex models some estimators diverge. The results were consistent over multiple runs. Details regarding the architectures and hyperparameters used are in Appendix E Upon acceptance will open source all code, models, data and experiments.
6.1 BIASED ESTIMATORS ON A TOY PROBLEM
Gumbal Softmax
To validate the excessive bias in the Etraight-Throuse estimator, as well as to explore the benefits of FouST,
FouST(O.5]
DARN
ST
we first explore a toy problem. Similar to Tucker (017)), we minimize ((tt))(== () where E (0, I) continuous target value and 2 sample from the Bernuulii distribution p(z). The optimum is ob-
Probability
tained for p(= = +1) E 1). Figure ! shows case with t = 0.45, where the minimizing solu- tion is p(z = +1) = O. We observe that unlike the Straight-Through estimator, FouST converges the minimizing deterministic solution (lower is better).
-003
2000
2000
4000
5000
Steps
Figure/ I: Biased estimators on toy problem
6.2 FOUST vs.
GRADIENT ESTIMATORS
Training Stochastic MLPs. We train MLPs with one and two stochastic layers on OMNIGLOT, following the non-linear architecture of Tucker et al. (2017). Each stochastic Boolean layer is preceded by two deterministic layers of 200 tanh units.
All hyperparameters remain fixed throughout the training. All estimators use one sample per example and a single decoder evaluation. We present results in Fig. [ FouST outperforms other biased gradient estimators in both datasets and architectures. FouST is clearly better than the Straight- Through estimator. Despite the complicated nature of the optimized neural network function f()) the bias reduction appears fruitful. With one two stochastic layers we can also use the unbiased REBAR. REBAR is not directly comparable to the estimators we study, since it uses multiple decoder evaluations and for models with multiple stochastic layers, multiple passes through later layers. Nevertheless, as shown in appendix D. MNIST, with two stochastic layers REBAR reaches worse test BLOO of -94.43 v. -91 91.94 for FOuST. A possibility of worse test than training ELBOs for REBAR was also suggested in the original work (Tucker et al. 2017).
Training Stochastic ResNets. We further validate FouST in setting where the encoder and decoder are stochastic ResNets, S-ResNets, which are standard ResNets with stochastic layers inserted between ResNet blocks. Similar to MLPs, FouST outperforms other biased estimators in this
7

---

Under review as a conference paper at ICLR 2020
setting CIFAR-10 10 (left in Figure 3) Note that despite the hyperparameter sweep, to train S-Res with Gumbel-Softtax. So we compare against DARN and StraightTTrough only. With S-ResNet with 12 ResNet blocks and 4 stochatic layers FouST yields score of 5.08 bits per dimension (bpd). This is comparable to the 5.14 bpd with the categorical VIMCO-trained model (Mnih & Rezende 2016) obtained with 50 samples per example, reported by van den Oord et al. (017)).
unable
In the plots, we observe sharp spikes slower curv- ing. We hypothesize these are due, respectively, to stochasticity and bias, and are corrected some degree along the way.
Table 1: Wall clock times for various gradient
estimators on MNIST.
Method #Eval.
Walltime in sec./Epoch
Efficiency. We compare the efficiency of differ- ent estimators in Tab, [ Like other biased estima- tors, FouST requires single sample for estimat- ing the gradients and has similar wallclock times. On MNIST, the unbiased REBAR is 15x and 40x slower than the biased estimators for two and five stochastic layer MLP's respectively.
layers
5 layers
REBAR
45.3
205.15
ST
2.86
4.96
Gumbel
3.27
6.14
DARN
1
2.96
5.36
FouST
3.1
5.67
From the above experiments we conclude that FouST allows for efficient and effective training of fully connected and convolutional neural networks with Boolean stochastic variables.
6.3 ADDING STOCHASTIC DEPTH AND WIDTH
Last, evaluate FouST more complex neural networks with deeper and wider stochastic layers. perform experiments with convolutional architectures on the larger scale and more realistic mini-ImageNet [Vinyals et al. 2016). As the scope of this work is not architecture search, we present two architectures inspired from residual networks (He ct al. 2016) of varying stochastic depth and width. The first one a wide S S-ResNet. S 4ResNet-40-2-- 40-2-800, and has 40 deterministic (with encoder and decoder combined), 2 stochastic layers, and 800 channels for the last stochastic layer. The second, --ReNett-80-11 10-11- is very deep with 80 deterministic and 11 stochastic layers, and last stochastic layer with 256 channels. Architecture details are given in Appendix E.2 In this setup, training with existing unbiased estimators is intractable.
We present results in Fig. 3 We compare against DARN, since we were unable to train the models with Gumbel-Softmax. Incomplete lines indicate failure.
We observe that FouST is able to achieve better training ELBO's in both cases. We conclude that FouST allows for scaling up the complexity of stochastic neural networks in terms of stochastic depth and width.
FouST DARN
FouST DWRN
-112
Gumbel-TT
Gumbel-S7
Training ELBO
Training ELBO
ST
-115
-110
-115
195
155
-122
55300
Z08000
700603
1535000
1953890 150c0ss
1200000 N000000
-130
200633
59006
750000
1000c66
1900066
553000
175300 P006030
Steps
Steps
Figure 2: Training ELBO for the one (left) and two (right) stochastic layer nonlinear models on OMNIGLOT
8

---

Under review as a conference paper at ICLR 2020
FouST[A] DAANAA STTA] FouSTIR) DARNBB
0.93
Training ELBO
Traiming ELBO
20000
2750
ST[R]
10000
6590
8.90
14000
FauSTT
DARN
4750
12000
FouSTWWick
DARN]Wtd))
50000
1039X)
150000
230393
13000
50008
20000
43000
50003
60000
70000
80000
Steps
Steps
Figure 3: Training ELBO on CIFAR-10 (left) and mini-ImageNee (right)
7
CONCLUSION
In this work we introduce the framework of harmonic analysis for Boolean functions. We then use the harmonic analysis derive the source of bias the Straight-Through estimator for Boolean random variables. Based on the analysis we propose FouST, which is novel gradient estimate algorithm. We use FouST train neural networks with Boolean random variables stochastic layers. FouST outperforms state-of-the-ar biased gradient estimators, while maintaining efficiency that is orders of magnitude higher than unbiased estimators. Importantly, to the best of our knowledge FouST is the first gradient estimate algorithm, biased or unbiased, to be able to train very deep and wide neural networks with Boolean random variables. In our experiments FouST successfully trained networks with up to 80 deterministic and 11 stochastic layers. We conclude that the Harmonic Analysis framework for Boolean function is a useful methodological tool for analyzing Boolean neural networks. Also, we conclude that FouST is practical gradient estimate algorithm that can train complex stochastic neural networks with multiple layers of Boolean random variables.
REFERENCES
Yoshua Bengio, Nicholas Léonard, and Aaron Courville. Estimating propagating gradients through stochastic neurons for conditional computation. arXiv preprint 1xXiv:138.3432.. 2013.
Peter Dayan, Geoffrey E Hinton, Radford M Neal, and Richard S Zemel. The helmholtz machine. Neural computation, 7(5):889-904, 1995.
Will Grathwohl, Dami Choi, Yuhuai Wu, Geoff Roeder, and David Duvenaud. Backpropagation through the void: Optimizing control variates for black-box gradient estimation. arXiv preprint arXiv:1711.00013.. 2017.
Karol Gregor, Ivo Danihelka, Andriy Mnih, Charles Blundell, and Daan Wierstra. Deep autoregressive networks. arXiv preprint arXiv:1310.8499 2013.
Shixiang Gu, Sergey Levine, Ilya Sutskever, and Andriy Mnih. Muprop: Unbiased backpropagation for stochastic neural networks. arXiv preprint 1rXiv:1511.05176 2015.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference computer vision and pattern recognition, pp- 770-778, 2016.
Irina Higgins, Loic Matthey, Arka Pal, Christopher Burgess, Xavier Glorot, Matthew Botvinick, Shakir Mohamed, and Alexander Lerchner. beta-vae: Learning basic visual concepts with constrained variational framework. ICLR, 265) 2017.
Eric Jang. Shixiang Gu, and Ben Poole. Categorical reparameterization with gumbel-softmax. arXiv preprint 1xXiv:1611.01144 2016.
Diederik P Kingma and Max Welling. Auto-encoding variational bayes. arXiv preprint arXiv: 1312.613 2013.
Eyal Kushilevitz and Yishay Mansour. Learning decision trees using the fourier spectrum. SIAM Journal on Computing, 133-:133,, 1993.
Nathan Linial, Yishay Mansour, and Noam Nisan. Constant depth circuits, fourier transform, and learnability. Journal of the ACM (JACM), -063)607--60, 1993.

---

Under review as a conference paper at ICLR 2020
Chris Maddison, Andriy Mnih, and Yee Whye Teh. The concrete distribution: A continuous relaxation of discrete random variables. arXiv preprint (iXiv 2016.
Yishay Mansour. Learning boolean functions via fourier transform. In Theoretical advances neural computation and learning, pp. 391-424. Springer. 1994.
Grigorii Aleksandrovich Margulis. Probabilistic characteristics of graphs with large connectivity. Problemy peredachi informatsii, 101-080 1974.
Andriy Mnih and Karol Gregor. Neural variational inference and learning belief networks. arXiv preprint arXiv:1402.00 0030, 2014.
Andriy Mnih and Danilo J Rezende. Variational inference for monte carlo objectives. arXiv preprint arXiv:1602.06725 2016.
Elchanan Mossel, Ryan O' O'Donnell, and Rocco P Servedio. Learning juntas. In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, pp. 206-212. ACM, 2003.
Radford M Neal. Connectionist learning of belief networks. Artificial intelliggnnce 56(1):71-113, 1992.
Ryan O'Donnell. Analysis of boolean functions. Cambridge University Press, 2014.
Danilo Jimenez Rezende, Shakir Mohamed, Daan Wierstra. Stochastic backpropagation and approximate inference deep generative models. arXiv preprint arXiv:1401 4082, 2014.
Lucio Russo. An approximate zero-one law. Probability Theory and Related Fields, 61(1):129 1391),9999199,,, 1982.
George Tucker, Andriy Mnih, Chris J 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.
Aaron van den Oord, Oriol Vinyals, al. Neural discrete representation learning. Advances in Neural Information Processing Systems, pp. 6306-6315, 2017.
Oriol Vinyals, Charles Blundell, Timothy Lillicrap. Daan Wierstra, et al. Matching networks for one shot learning. In Advances in neural information processing systems, pp. 3630-3638, 2016.
Ronald I Williams. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine learning, 8(3-4):229 256. 1992.
APPENDICES
A FURTHER DETAILS FROM THE HARMONIC ANALYSIS FRAMEWORK FOR BOOLEAN FUNCTIONS
A.1 DISCRETE DERIVATIVE
For a Boolean function f the discrete derivative on the i-th latent dimension with basis function Φi is defined
as
(z) o. f(a,, +1,... 2n) f(21,
1,... 2n)
(17)
The Fourier expansion of the discrete derivative equals Da, f2)
E s2c (S) The Fourier contain the i-th dimension
expansion of the discrete derivative derived by equation 2 all bases that Bég de. Φsri from the definition of
are constant to é; and thus set to zero, while (ii) for the rest of the terms
basis functions (z). In the following we differentiate partial derivatives on continuous functions noted with d. from discrete derivatives Boolean functions noted with D.. The i-th discrete derivative is independent of both in the above definitions.
10

---

Under review as a conference paper at ICLR 2020
B HARMONIC ANALYSIS OF EXISTING GRADIENT ESTIMATES
PROOF OF LEMMA 1
Proof. We follow O Donnell 2014 $8.4). In this proof we work with two representations of the Boolean function f. The first is the Fourier expansion of f under the uniform Bernoulli distribution. This is also the representation obtained by expressing / polynomial in Since the domain of the function is the Boolean cube, the polynomial representation is multilinear. That is f()) Escinl [[;)s 2j. To avoid confusion and differentiate the representation from the Boolean function, use (=)) denote this representation in following. Note since this representation a polynomial is defined over any input in IR.. particular,
[+] = E
Σ f(S) I
II 2 JES
Σ f(S)
Il B|2,] = (un (ui...., Mn)
JES
The second representation use is the Fourier expansion of the Boolean function f under p(z). We denote this by f(r).
The following relation follows from the fact that when working with the Fourier representation, f(z) is multilinear, [x(s)[=;] = #4 and the linearity of expectation.
zn)] (a
Exte) (a
(Ma.... Ho.)
(18)
As the partial derivative of f(") w.r.t l4 is equivalent discrete derivative of f(v) w.r.t 2s f (f4)
Dz; f(n) (H), and keeping in mind that oi (2: mi)fa,, we have that
Da, (n))
(n) Ep(=) (D. (21 (s....., 2n)]
(from equation 18
(19)
Ep(=) (Do, p(0) (21,...,
(set Φ; (z pi)/ then chain rule)
(20)
(1) (1)
(21)
We then note that the discrete derivative of f w.r.. 24. Dz.f ((,f()))), from the left hand side of equation 19 is equivalent to the partial derivative of w.r.t. pi, on (()) (p))
fir) (i) Dz, (( D (x) 0n, (t)) (x)
(22)
pp. f(1)(1) (1)
(set = 2p, 1, then chain rule)
(23)
Up (p
(from equation 18
(24)
We complete the proof by noting that the right hand side in equation 24 is times the REINFORCE gradient.
B.2 ANALYSIS STRAIGHT-TEE THROUGHH-THROUGH
The detailed proof of Lemma 2 is as follows.
Proof. We first derive the Taylor expansions for the true gradient as well as the Straight-Through gradient estimator. Then, we prove the lemma by comparing the Taylor expansions.
By expanding function f in terms Φe basis as in equation 2 have that
and focusing on the dimension, we
(() f(r)
p(r)
(()
(25)
a;
The first term, (t) 24 is the term corresponding (i} in the Fourier expansion of under p 11) That is
flo-21/2 (())
(26)
This follows from the fact that when moving from p(z) to 1opp'=170 1/2 (i) we have that Φi = and (ii) no other term under the p(2) expansion contributes the term under the p² 11/1 expansion.
11

---

Under review as a conference paper at ICLR 2020
As consequence of Lemma Thee REINFORCE gradient for the i-th dimension is given by
Op Op.Bp(s) - f(() (i) 2 (()))
(27)
Next, we will derive the Taylor expansions of the true and the Straight- Through gradients. The Taylor expansion of f(2) for 2, around 0 is
f() = cu + c + c227 + cati + caRl + co + ..:
(28)
where cak! 0th (z)] the Taylor coefficients. All eą are function of zj: + i.
Let's first focus the true gradient. Since work with binary #1 values, we have that 2 for even & and 2! for odd k. This will influence the even and the odd terms of the Taylor expansions. Specifically, for the Taylor expansion of the true gradient we have from equation 27 and equation that
8z [f f (2)))/1)))))))))))))) (i) 2B 21/ c121 c227 +...)++
(29)
--,--/ c00 + c + +....
(30)
2E / louz t1 c2 + cs + ...] (2.)) = 1,, 2/ 24, B,, 0)
(31)
2E p( +
(32)
The expression equation 2 implies that true gradient with respect to the p. is the expected sum of the odd
Taylor coefficients. Here we note that the although final expression in equation also be derived by a finite difference method. it does not make explicit, as in equation 3] the dependence on and μu of the term inside the expectation.
Now, let's focus on the Straigh-TTroouh gradient. Taking the derivative of the Taylor expansion in equation 28
w.r.t. to 2, have
0z = cı + 2022; + 3cz2 + 4ct2, + 5cs= +...
(33)
The Straight-Through gradient the expectation of equation 33 in the i-th dimension, that
Epca) 0z, [[)] = Epçayles [en + 202z + 3cae? 4c4z + 5coo, +...]
(34)
= Bpta, |e: + 3cs + 5cs + ... + Eptc [2cz + 4ca + +..--u 114 (2 = 1, 2, Bpix [+]] = pb)
(35)
By comparing the expansion of the Throuuhh gradient in equation and and the expansion of the true gradient in equation 32
bias (p) (GST)
-p.
(36)
By(a)))
(ks 2)cx
+ Bpla)))
ICC
P4-
(37)
k= 2=2
22
Taking the expectation in equation 34ddrr p² 11/2 causes the final term in equation
37 to vanish leaving
bias (p (1)
Σ
(k-
2)ca
(38)
k=2-+1.f30
C LOW-BIAS GRADIENT ESTIMATES
C.I LOWERING BIAS BY MATCHING UNIFORM DISTRIBUTION MOMENTS
We describe the case of a bivariate function in detail.
For brevity, we focus case study of a two-dimensional and a bivariate f(21, 22) with the bivariate Taylor expansion f(21, 22) = Σ.,, zf..
As Lemma the partial true gradient of f(21, 22) w.r.t. the first distribution parameter pl equals
0, (2) Σ En
E + Σ c5. Ep
(39)
Further, the Taylor expansion of 0p, f21, 22) is 0z, ( 22) E, o +2E, 02. +3E, ca.5 +f
12

---

Under review as a conference paper at ICLR 2020
"Bernoulli splitting uniform" trick. Assume auxiliary variable (u1, uz). which choose
follows. First, we sample (#1, #2) from the uniform Bernoulli distribution p² p/11/2 Then take uniform sample (ua, Ma) with a, sampled from either [0, for 2, +1 or from [-1, if -1. At this point it is
important note that the moments of the uniform distribution in (a, bj are Jn v-a"" simplifies 2/2, 6² /3, b² /4, for a O, and where we think b binary sample i.c., E (-1,1) The expectation of the gradient under such random sampling is
gh+1 which
E [0., / (u,, u2)]
E e
2
Ca Eu + 3 ca [ug]),
Σ
B. +
C3.
B.
(40)
We then compare equation 40 with equation 39 In equation 40 we observe that the pure terms in 21, namely terms with j = O, always match those of the truc gradient in cquation 39 For j >> 0 we obtain mixed terms with coefficients that do not match those of the true gradient in equation 39 However, the partial gradient obtained with the auxiliary variables in equation 40 has coefficients following a decaying trend due to j41
1_ For small that is, the mixed-degree terms are closer to the original ones in equation 39] For functions with smaller mixed degree terms this leads bias reduction, the cost of increased variance due additional sampling. practice many functions would have greater dependence mixed degree terms. For such functions and manage the bias variance trade-off we choose smaller intervals for the uniform samples, that is a + b.
C.2 LOWERING BIAS BY REPRESENTATION SCALING
The Fourier basis does depend the particular input representation and any two-valued set, say {-t, f) be used as the Boolean representation. The choice of representation, however, does affect the bias as we show next. As concrete example, we lct our input representation be 2, E {-1/2, 1/2]", where pi p(z = +1/2), While we can change the input representation like that, in general the Fourier coefficients in equation 3 will be different than for the { +-1 representation. Letting lu(z)) 2z; (-1, 1], the functions d; now given di -(s))
Next, we write the Taylor series of f in terms of h(2;),
f(=) co + c1 c2 + c32 + ca2t + cs2 +...
(41)
cp + h(()) 2 M2x)² 23
1(x,)
c4 1(x)*
C5
n(z)
(42)
24
2
Under the p 1112 distribution, we still have that 1 [h(x)) 0 and the degree-1 Fourier coefficients are:
(10-1/1))) = E [(=))(())) = E, (-) 2
C1 + +
(43)
Note that compared to equation 7 in equation 43 43wwe we still get the odd terms c1 Ca albeit decayed by inverse
powers of 2. Following the same process like for equation
10
we have that
3cs
5cs
2 [1 [()]]
E 1-12
(44)
2
23
25
D EXTRA EXPERIMENTS
D.1 EXPERIMENTS ON MNIST
Pr.ST
Gunita-SSllmme
Cumbee-Soflmme DARN
Training ELBO
1000
Training ELBO
-15
ST
102.5
1050
-100
1100
-125
1100
-115
Figure 4: Training ELBO for the one (left) and two (right) stochastic layer nonlinear models on
MNIST
13

---

Under review as a conference paper at ICLR 2020
Table 2: Test set performance with increasing stochastic depth MNIST.
Method
Stochastic Layers
Hidden Units per Layer
Test ELBO
Rebar
2
200
-94.43
FouST
2
200
-91.95
FouST
3
200
-89.11
FouST
8
500
-87.31
FouST
20
500
-87.86
D.2 ABLATION EXPERIMENTS
To further judge the effect of proposed modifications Straight-Through performed ablation experiments where separately applied scaling and noise the importance-correeta Strighh-TThrouge These experiments were performed on the single stochastic layer MNIST OMNIGLOT models.
The results of the ablation experiments are shown in figure 5 From the figure it can be seen that scaling alone improves optimization in both cases and noise alone helps in the case of MNIST. Noise alone results in worse ELBO in the of OMNIGLOT, but gives improvement when combined with scaling. From these results we conclude that the proposed modifications effective.
Training ELBO
Training ELBO
114
-11
DARN-scall
DARN-sca
FouST
FousT
TE0000
1035000
1553000
2000000
250003
100000 Steps
1530000
1753000
Steps
Figure 5: Ablations for the one stochastic layer nonlinear model on OMNIGLOT (left) and MNIST (right)
E
ARCHITECTURES USED IN THE EXPERIMENTS
E. ARCHITECTURES FOR MNIST AND OMNIGLOT
encoder and decoder networks in this case are MLP's with one or more stochastic layers. Each stochastic layer is preceded by 2 deterministic layers with a tanh activation function.
We chose learning rates from (1 x 1 x 10 4, 4 x 10-4 0--4,0 6 10"*), Gumbel-Softmax temperatures from (..1, and noise interval length for FouST from (0.1,0.2),
E.2 ARCHITECTURES FOR CIFAR-10 AND MINI- MINI-IMAGENET
these dataset we use stochastic variant or ResNets layers. Each layer has (i) one regular residual block as in He et al. (2016). (ūi) followed by at most one stochastic
et al. 2016). Each network composed stacks
layer, except for the CIFAR architecture B in figure 3 where we used two stochastic layers in the last layer. The stacks are followed by final stochastic layer in the encoder. We do downsampling most once per stack. We
used layers per stack.
CIFAR we downsample twice so that the last stochastic layer has feature maps of size 8x8. chose learning
rate from {9 x 10 10-7, x 10 10-5,3 2 x 10 10-6 9,4 10 10-9), the FouST scaling parameter from (0.5, 0.8, 0.9), and the uniform interval was scaled by factor from {0.01, 0.05, 0.1}
For mini-ImageNet downsample thrice. We chose the learning rate from (2 x 10-7,3 7,0 10-7 7, 10-7.5. 10 -...
14

---

Under review as a conference paper at ICLR 2020
For the decoder the structure of the encoder is reversed and convolutions replaced by transposed convolutions. The output model Gaussian with learned mean and variance.
15


Reviews:
[{"review_id": "rJglOLeCFB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "------------- updated after rebuttal -------------------\n\nI thank the authors for clarifying and correcting the notations in Lemma 3. Though I still think the current state of the derivation is presented in a suboptimal way, and as a result, can be misleading to people.\n\nThe Fourier analysis used to give the results that the exact gradient equals $2\\hat{f}^{(p\\to 1/2)}(i)$ (eq. 5) is totally unnecessary: Despite it might seem fancy as a Fourier coefficient, it is just another way of writing the local expectation estimator (Tokui, S., & Sato, I., 2017), if we expand it using the definition $\\hat{f}^{(p)}(S) = E_{p(z)}[f(z)\\phi_S(z)]$.\n\nThe authors argue that the Fourier analysis is essential to show the bias of the estimator. However, the only conclusion they draw from Fourier analysis is eq.5. And all the bias analysis follows by using Taylor expansions of it. The paper can be greatly simplified if they remove all boolean analysis parts and start from eq. 5 (which has a straightforward proof), using the conventional notation instead of Fourier coefficients. \n\nDuring writing this, I read the bias correction section again and had another concern, the bias correction effect is only justified for functions with small mixed degree terms:\n\n\"For functions with small mixed degree terms, this can lead to bias\nreduction, at the cost of an increased variance because of sampling an auxiliary variable\"\n\nFor general multivariate functions, it is even not clear whether the proposed estimator has a smaller bias than the straight-through one. This weakness has a deep reason behind it because they are trying to generalize a bias reduction technique from a univariate function to multivariate functions, which, if done natively, would require K evaluations of the function (K is the number of input dimensions) (as I pointed out in the original review).\n\nOverall, I argue rejecting the paper in its current form.\n\n----------------------------------------------------------------\n\nThis is not my first time reviewing this paper. Previous concerns on clarity has been addressed and the paper is now more readable. Though I still believe that the boolean analysis part is unnecessary for deriving the final estimator (which can be easily derived from the exact local-expectation estimator E_p[f(z_i=1) - f(z_i=0)] and applying f(1) - f(0) = \\int_0^1 f'(x) dx \\approx f(e), e~Unif[0,1].) plus some importance sampling trick.\n\nI think the proof of Lemma 3 is incorrect (though the conclusion is correct). f is never multi-linear in the continuous space. It is only for the boolean space, that f has an multi-linear form with Fourier expansion. So the claim that f is multi-linear then\n\nE_{p(z}}[f(z_1, ..., z_n)] = f(\\mu_1, ..., \\mu_n)\n\nis incorrect. This can only be true when f is also linear in the continuous space (which is not true for typical vaes).\n\n", "extra_scores": {"experience_assessment": "I have published one or two papers in 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 thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "H1eAZuvkqr", "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:\nThe authors analyze the bias in the straight-through gradient estimator using the framework of harmonic analysis of boolean functions. Based on this analysis, they propose three methods to reduce the bias of the straight-through estimator, resulting in a less-biased estimator that is the same computational complexity as the original. They evaluate this estimator on a series of generative modeling tasks where they demonstrate improvements over existing methods, including the ability to train a very deep stochastic network.\n\nI enjoyed this paper -- the exposition is clear, the ideas are (to my knowledge) novel and make sense, and the experimental evaluation is thorough and convincing. I recommend an accept. \n\nI skimmed through the proofs in the appendix so cannot with absolute confidence vouch for their correctness.\n\nOne small piece of feedback: I found the most confusing part of the paper was the section on the 'bernoulli splitting trick'. It might be helpful to pull some of the appendix material into this section to make it a little less sparse.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BkgiaQoTFH", "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": "***Score updated to weak accept after the rebuttal.***\n\nStraight-Through is a popular, yet not theoretically well-understood, biased gradient estimator for Bernoulli random variables. The low variance of this estimator makes it a highly useful tool for training large-scale models with binary latents. However, the bias of this estimator may cause divergence in training, which is a significant practical issue. The paper develops a Fourier analysis of the Straight-Through estimator and provides an expression for the bias of the estimator in terms of the Fourier coefficients of the considered function. Motivated by this expression, the paper proposes two modifications of Straight-Through which may reduce the bias of the estimator, at the cost of the variance. The experimental results show advantage of this improved estimator over Gumbel-Softmax and DARN estimator.\n\nWhile I really like the premise of the paper, I feel that it needs a significant amount of additional work. The text is currently fairly hard to read. The theoretical part of the paper does not quantify the variance of the estimator. The experiments are a bit unfinished and do not include ablations of the proposed modifications of Straight-Through. Most importantly, I think that in the current form the theoretical and the empirical parts of the papers are not well-connected. Because of this, I believe that the paper should currently be rejected, but I encourage the authors to continue this line of work.\n\nPros:\n1. Theoretical analysis and empirical improvement of the Straight-Through estimator is an important avenue of work.\n2. The paper makes a solid contribution of deriving the Fourier expansion of the Straight-Through estimator bias.\n3. Based on this expansion, the paper proposes an algorithm with reduced bias. The algorithm is simple to implement, practical and appears to work slightly better than DARN.\n\nCons:\n1. The key weakness of the theoretical part of the paper is that it focuses on the bias of the estimator, but does not quantify the variance, especially after the modifications. If reducing the bias was the only goal, one could use unbiased (but high-variance) estimators such as REINFORCE or VIMCO.\n2. The final algorithm appears to be the DARN estimator combined with relaxation by uniform noise (“Bernoulli splitting uniform”) and scaling. The paper does not have an ablation showing how the uniform noise and scaling perform on their own.\n3. There are a few incorrect statements that I’ve noticed.\n* “As a side contribution, we show that the gradient estimator employed with DARN (Gregor et al., 2013), originally proposed for autoregressive models, is a strong baseline for gradient estimation.” - MuProp paper compared to this estimator under the name 1/2-estimator\n* In Lemma 1 the “REINFORCE gradient” is just the exact gradient of the expectation, not a stochastic REINFORCE gradient.\n* “ To the best of our knowledge, FouST is the first gradient estimate algorithm that can train very deep stochastic neural networks with Boolean latent variables.” This paper uses up to 11 latent variable layers, while [1] has trained models with >20 latent variable layers (although their “layers” have just one unit).\n4. The derivation of “Bernoulli splitting uniform” trick is confusing and contains a lot of typos. For instance, the text before eqn. (14) implies that the distribution of u_i is U[-1, 1], which cannot be right and does not correspond to Algorithm 1. The statement that this trick does not lead to a relaxation is odd, since the function is being evaluated at non-discrete points.\n5. There are generally many typos and some poor formatting in the math. For example, in eqn. (6) the coefficients are off by one: it should be c0 + c1 z1 + c2 z2^2 + … . The equations (10) and (11) are poorly formatted. The notation \\partial_z1 f(u_1, u_2) in eqn. (14) is strange. In many places p^{i->½} is denoted as p^{1->½}.\n5. I don’t think I understood the idea of representation scaling (Section 4.4). The eqn. (16) would suggest that the scaling should optimally be set to zero, which is just saying that the gradient is unbiased when the model does not use the latents. There is no other practical guidance on choosing this coefficient. Furthermore, one can always absorb the global scaling factor into the succeeding weights layer of the model, so this trick can probably be replaced by a modification of the weights initialization.\n6. The experiments are missing a comparison to the Straight-Through Gumbel-Softmax estimator, introduced in the original Gumbel-Softmax paper. This is a popular biased estimator for Bernoulli latents, e.g. used in [1] [2]. Another interesting comparison would be [3] which proposes a lower-bias version of Gumbel-Softmax.\n7. Figure 2 is missing the line for REBAR, even though this line is referred to on Page 8. Figure 2 and Figure 4 are both labeled as training ELBOs, despite the plots being different.\n\n[1] Andreas Veit, Serge Belongie “Convolutional Networks with Adaptive Inference Graphs” ECCV 2018\n[2] Patrick Chen, Si Si, Sanjiv Kumar, Yang Li, Cho-Jui Hsieh “Learning to Screen for Fast Softmax Inference on Large Vocabulary Neural Networks” ICLR 2019 https://openreview.net/forum?id=ByeMB3Act7\n[3] Evgeny Andriyash, Arash Vahdat, Bill Macready “Improved Gradient-Based Optimization Over Discrete Distributions” https://arxiv.org/abs/1810.00116", "extra_scores": {"experience_assessment": "I have read many papers in 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": {}}]

Author rebuttal:

Meta-review: Straight-Through is a popular, yet not theoretically well-understood, biased gradient estimator for Bernoulli random variables. The low variance of this estimator makes it a highly useful tool for training large-scale models with binary latents. However, the bias of this estimator may cause divergence in training, which is a significant practical issue. The paper develops a Fourier analysis of the Straight-Through estimator and provides an expression for the bias of the estimator in terms of the Fourier coefficients of the considered function. 

The paper in its current form is not good enough for publication, and the reviewers believe that the paper contains significant mistakes when deriving the estimator. Furthermore, the Fourier analysis seems unnecessary. 
Decision: Reject