Reintroducing Straight-Through Estimators as Principled Methods for Stochastic Binary Networks
Authors: Alexander Shekhovtsov
Viktor Yanush
Venue:  (2021)
Keywords: straight-through
binary
stochastic binary
mirror descent

Abstract: Training neural networks with binary weights and activations is a challenging problem due to the lack of gradients and difficulty of optimization over discrete weights.
Many successful experimental results have been achieved with empirical straight-through (ST) approaches, proposing a variety of ad-hoc rules for propagating gradients through non-differentiable activations and updating discrete weights. At the same time, ST methods can be truly derived as estimators in the stochastic binary network (SBN) model with Bernoulli weights. We advance these derivations to a more complete and systematic study. We analyze properties, estimation accuracy, obtain different forms of correct ST estimators for activations and weights, explain existing empirical approaches and their shortcomings, explain how latent weights arise from the mirror descent method when optimizing over probabilities. This allows to reintroduce, once empirical, ST methods as sound approximations, apply them with clarity and develop further improvements.

Reintroducing Straight-Through Estimators as Principled Methods for Stochastic Binary Networks*
Alexander Shekhovtsov and Viktor Yanush?
Czech Technical University in Prague
shekhole@fel. cvut.cz
Bamsung-HSS Laboratory National Research University Higher School of Economies, Moscow yanushvixtor@@gaall..omm
Abstract. Training neural networks with binary weights and activa- tions is a challenging problem due to the lack of gradients and difficulty optimization over discrete weights. Many successful experimental results have been achieved with empirical straight-through (ST) approaches, proposing variety of ad-hoc rules for propagating gradients through non-differentiable activations and updating discrete weights. At the same time, ST methods can be truly derived as estimators in the stochastic binary network (SBN) model with Bermoulli weights. We advance these derivations more complete and systematic study, We analyze proper- ties, estimation accuracy, obtain different forms of correct ST estimators for activations and weights, explain existing empirical approaches and their shortcomings, explain how latent weights arise from the mirror descent method when optimizing over probabilities. This allows to rein- troduce ST methods, long known empirically, sound approximations, apply them with clarily and develop further improvementts.
1 Introduction
Neural networks with binary weights and activations have much lower compu- lation costs and memory consumption than their real-valued counterparts [18, 26, 45). They are therefore very attractive for applications in mobile devices, robotics and other resource-limited settings, in particular for solving vision and speech recognition problems [8, 56].
The seminal works that showed feasibility of training networks with binary weights [15] and binary weights and activations [27] used the empirical straight- through gradient cstimation approach. In this approach the derivative of a step function like sign, which is zero, is substituted with the derivative of some other function, hereafter called a prozy function, on the backward pass. One possible choice is identily proxy, i.e., to completely bypass sign on the backward pass, hence the name
[3]. This ad-hoc solution appears to work
We gratefully acknowledge support by Czech OP VVV project "Research Center for Informatics (CZ.02.1.01/0.0/0... 010.:///000000000000000000000000 16019/0000765)"

---

2
A. Shekhovtsoy & V. Yanush
(b)
2
2
2
2
2
0
2
0
1
2
2
2
-2
2
-2
2
-2
-2
2
-2
Bign Tunction
Idensity
Htanh
Tanc
ApprosSign
/uniform noise
logiaatcc moise
trianguins noian
Fig. 1: The sign function and different proxy functions for derivatives used in empirical ST estimators. Variants (c-e) be obtained by choosing the noise distribution in our framework. Specifically for real-valued noise with odf F, in the upper plots
show [zisinnaa - =)] 2F - and, respectively, twice the density, 2F in the lower plots. Choosing wniform distribution for 2 gives the density p(z) = [[1 and recovers the common Htanh proxy in (c). The logistic noise has odf F(z) = (2z), which recovers lanh proxy (d). The triongular noise has density p(z) max(0, [(2 =)/4),, which recovers scaled version of ApproxSigu [34] in (e). The scaling (standard deviation) of the noise in each case chosen so that 2F* (0) 1. The identity ST form in (b) we recover as latent weight updates with mirror descent.
surprisingly well and the later mainstream research on binary neural networks heavily relies on it [2, 6, 9, 11, 18, 34, 36, 45, 52, 60).
The de-facto standard straight-through approach in the above mentioned works is to use deterministic binarization and the clipped identity proxy as pro- posed by Hubara et al. [27]. However, other proxy functions were experimentally tried, including tanh and wise quadratic ApproxSign [18, 34], illustrated in Fig. 1. This gives rise to diversity of empirical ST methods, where various choices are studied purely experimentally [2, 6, 52). Since binary weights can be also represented as sign mapping of some real-valued latent weights, the same type of methods is applied to weights. However, often different proxy is used for the weights, producing additional unclear choices. The dynamics and inter- pretation of latent weights are also studied purcly empirically [51]. With such obscurity latent weights, Helwegen al. [24] argues that "latent weights do not exist" meaning that discrete optimization over binary weights needs to be considered. The existing partial justifications of deterministic
approaches are limited to one-layer networks with Gaussian data [58] or bina- rization of weights only [1] and do not lead to practical recommendations.
In contrast to the deterministic variant used by the mainstream SOTA, straight- through methods were originally proposed (also empirically) for stochas- tic autoencoders [25] and studied in models with stochastic binary neurons [5, 44). In the stochastic binary network (SBN) model which we consider, all hidden units and/or weights are Bernoulli random variables. The expected loss truly differentiable function of parameters (i.e., weight probabilities) and its gradient be estimated. This framework allows to pose questions such as: "What is the truc expected gradient?" and "How far from it is the estimate computed by

---

Reintroducing Straight-Through Methods
3
ST?" Towards computing the true gradient, unbiased gradient estimators were developed [20, 55, 57]. which however have not been applied to networks with deep binary dependencies due to increased variance in deep layers and complex- ity that grows quadratically with the number of layers [48]. Towards explaining ST methods in SBNs, Tokui Sato [54] and Shekhovtsov al. [48] showed how derive ST under linearizing approximations in SBNs. These results however were secondary in these works, obtained from more complex methods. They re- mained unnoticed in the works applying ST in practice and recent works its analysis [13, 58]. They are not properly related to existing empirical ST variants for activations and weights and did not propose analysis.
The goal of this work is to reintroduce straight-through estimators in a prin- cipled way SBNs, to formalize and systematize empirical ST approaches for activation and weights in shallow and deep models. Towards this goal we re- view the derivation and formalize many empirical variants and algorithms using the derived method and sound optimization frameworks: show how different kinds of ST estimators can occur as valid modeling choices or valid ipiinization choices. We further study properties of ST estimator and its utility for opti- mization: we thcoretically predict and experimentally verify the improvement accuracy with network width and show that popular modifications such as deterministic ST decrease this accuracy. For deep SBNs with binary weights we demoustrate that several estimators lead to equivalent results, as long as they are applied consistently with the model and the optimization algorithm.
More details on the related work, including alternative approaches for SBNs we discuss in Appendix A.
2 Derivation and Analysis
Notation We model random states x E (-1, using the noisy sign mapping:
sign(a; - 2;),
(1)
where z are real-valued independent noises with fixed edf F and a; are (input- dependent) parameters. Equivalently to (1), valued Bernoulli distribution with probability p(z;=1) = P(a:-2; 2 0) = P(; <
say that x; follows 1-1,1}
a;) = F(a.). The noise odf F will play an important role in understanding different schemes. For logistic noise, its odf F is the logistic sigmoid function a.
Derivation Straight-through method was first proposed empirically [25, 32] in the context stochastic auloencoders, highly relevant to date [e.g. 16). In con- trast to more recent works applying variants deterministic ST methods, these earlier works considered stochastic networks. It turns out that in this context it is possible to derive ST estimators exactly in the same form as originally pro- posed by Hinton. This is why we will first derive, using observations of [48, 54], analyze and verify it for stochastic autocncoders.
Let y denote observed variables. The encoder nelwork, parametrized by Φ computes logits aly: Φ) and samples a binary latent state x via (1). As noises z

---

4
A. Shekhovtsoy & V. Yanush
Algorithm 1:
Algorithm 2:
Straight-Throughe -eiiigg-iioghtttttttt Weights
/* a: preactivation
*/
/* m: latent weights
/+ F: injected noise cdf :/
/+ F; weight noise cdf
/
/+ æ E {-1,1)"
/* {-1,1]
/
Forward a
Forward 17
2
p F(a);
p F(n);
return 2Bernoull(p)
return w ~ 2Bernouli((p) - 1;
4 Backward( dc
dz
Backward
5
return da = 2 diag F" (a)) dz:
return 2 2w
are independent, the conditional distribution of hidden states given observations p(aly;; Φ) factors as I1, p(2; y: Φ). The decoder reconstructs observations with
p pa ( x another neural network parametrized by The autoencoder roconstruction loss defined as
Eyr-data Peapleete log pde (y ac; 0)]]
The main challenge is estimating the gradient w.r.t. the encoder parameters & (differentiation can be simply taken under the expectation). The problem for a fixed observation y takes the form
E E [C(x)] B [L[siiinn =))]]] Bib
33)
where p(æ; Φ) is a shorthand for p(aly: Φ) and L(x) - p (y) 2; 0). The reparametrization trick, i.e., to draw one sample of in (3) and differentiate L(sign(a 2)) fails: since the loss as function of a and z is not continuously differentiable we cannot interchange the gradient and the expectation in z If we nevertheless attempt the interchange, we obtain that the gradient of sign(a- =)) is zero as well as its expectation. Instead, the following steps lead to an unbiased low-variance estimator. From the LHS of (3) we express the derivative as
2Φ En (I.p((r; E. E, P(wy; x)) 2 pap ((x). (4)
Then we apply derandomization [40, ch. 8.7], which performs summation over holding the rest of the state fixed. Because x, takes only two values, we have
Σn 8p(zad) d6
L(xr)
0p(za0) de
[(x)) 011 p(1-p(z;:00) L(arp))
8Φb
ae pl:; x) L(m)s)),
where æi denotes the full state vector æ with the sign of x; flipped. Since this expression is now invariant of Fú, we can multiply it with 1 = E., p(z,; Φ) and
The conditions allow to apply Leibniz integral rule to exchange derivative and inte- gral. Other conditions may suffice, e.g., when using weak derivatives [17].

---

Reintroducing Straight-Through Methods
5
express the gradient (4) in the form:
E.E.., (II, p(zv: Φ)) Ex, p(a,;; Φ)
@pla.s0)
Be
En IIx p(av; Φ)) E; Opla..0)
(C(z)-
dep
= =Em<p(nge Σ.
Op(z..d)
(L(z)-((<)))
(6)
where a denotes all states excluding To obtain an unbiased estimate, it suffices to take one sample x p(æ; Φ) and compute the sum in i in (6). This estimator is known as local expectations [53] and coincides this case with GO-gradient [14], RAM [54] and PSA [48].
However, evaluating ((x1)) for all may be impractical. A huge simplification is obtained if assume that. the change of the loss & when only a single latent bit I2 is changed be approximated via linearization. Assuming that L is defined as differentiable mapping R= -R (i.e., that the loss is built up of arithmetic operations and differentiable functions), we can approximate
[(x) ((x 2r, aC(2)
Ba;
where we used the identity is - (-x;) 2z, Expanding the derivative of con- ditional density oe pop; Ø) 2, F² (a,
(((,((())))) ()) 26 (.(())) (Φ), we obtain
0p(z,, ((r))_(((j())) ~ 2F (as (b) 8ib
(a.(d) ac(w)
(8)
06
dm.
we now define that dz approximation (8) can be written the form of a chain rule:
= (a,), the summation over in (6) with the
du:
(0,( aC(x) Be Bag
aC(x)) ön, 8a,(d) Σ.
(9)
Oa; Bib
To clarify, the estimator already defined by the LHS of (9). We simply want compute this expression by (ab)using the standard tools, and this is the sole purpose of introducing an;" Indeed the RHS of (9) is a product of matrices that would oceur in standard backpropagation. We thus obtained ST algorithm Alg. 1. We can observe that it matches exactly to the one described by Hinton [25]: to sample on the forward pass and use the derivative of the noise caf on the backward pass, up to the multiplier 2 which occurred due to the use of +:1 encoding for æc
da,
2.1 Analysis
Next we study propertics of the derived ST algorithm and its relation to empir- ical variants. We will denote a modification of Alg. that does not use sampling Line 3, but instead computes z = sign(a), a deterministic ST; and a modifi- cation that uses derivative of some other function G instead of in Line 5 as using prozy G.

---

6
A. Shekhovtsov & V. Yanush
Invariances Observe that binary activations (and hence the forward pass) stay invariant under transformations: sign(a; - 2) sign(T((::) - T(=)) for any strictly monotone mapping T. Consistently, the ST gradient by Alg. is also invariant to T. In contrast, empirical straight-through approaches, in which the derivative proxy is hand-designed, fail to maintain this property. particular, rescaling the proxy leads different estimators.
Furthermore, when applying transform T F (the noise edf), the back- propagation rule in line 5 of Alg. 1 becomes equivalent to using the identity proxy. Hence we see that a common description of ST in the literature back-propagate through the hard threshold function as if it had been the iden- tity function" is also correct, but only for the case of uniform noise in [-1, Otherwise, and especially so for deterministic ST, this description is ambiguous because the resulting gradient estimator crucially depends on what transforma- tions were applied under the hard threshold.
"to
ST Variants Using the invariance property, many works applying randomized ST estimators are easily seen to be equivalent to Alg. 1: [16, 44, 49). Furthermore, using different noise distributions for 2, we can obtain correct ST analogues for common choices of sign proxies used empirical ST works as shown in Fig. 1 (c-e). In our framework they correspond to the choice of parametrization of the conditional Bernoulli distribution, which should be understood similarly to how neural network can be parametrized in different ways.
If the "straight-through" idea is applied informally, however, this may lead to confusion and poor performance. The most cited reference for the ST esti- mator is Bengio et al. [5]. However, [5, Eq. 13] defines in fact the identity ST variant, incorrectly attributing it to Hinton (see Appendix A). We will show this variant be less accurate for hidden units, both theorctically and experimen- tally. Pervez et al. [42] use +1 binary encoding but apply ST estimator without coefficient 2. When such estimator is used in VAE, where the gradient of the prior KL divergence is computed analytically, it leads to significant bias of the total gradient towards the prior. In Fig. 2 we illustrate that the difference in performance may be substantial. We analyze other techniques introduced in FouST in more detail in [47]. An inappropriate scaling by factor of can be well detrimental in deep models, where the factor would be applied multiple times (in each layer).
Bias Analysis Given rather crude linearization involved, it is indeed hard to obtain fine theoretical guarantees about the ST method. We propose an analysis targeting understanding the effect of common empirical variants and understand- ing conditions under which the estimator becomes more accurate. The respective formal theorems are given in Appendix B.
I) When ST unbiased? As we used linearization as the only biased ap- proximation, it follows that Alg. 1 is unbiased if the objective function L is mullilinear in æ. A simple counter-exanple, where ST is biased, is L(xr) 22

---

Reintroducing Through Methods
7
Ir#0.003
1r=0.000)
0.0003
00000001
ST
ST
ST
110
FouST:57
1:40
FouST:5T
150
FouST:ST
3.40
144
140
236
210
3500
3000 160
4500
Fig. 2: Training VAE on MNIST, closely following experimental setup [42]. The plots show training loss (negative ELBO) during epochs for different learning rates. The variant of ST algorithm used [42] misspecified because of the scaling factor and performs substantially worse at for all learning rates. Full experiment specification given in Appendix D.1.
In this case the expected value of the loss is 1, independently of a that deter- mines z; and the true gradient zero. However the expected ST gradient is (a)xx]
(2FF() - 1), which may be positive or negative depend- ing on a. On the other hand, any function of binary variables has an equivalent multilinear expression. In particular, if we consider L(x) || yl,,,, analyzed coincides by Yin et al. [58], then L(x) || -2 x² W., + W,,
with C on all binary confgurations and is multilinear. It follows that ST applied to gives an unbiased gradient estimate of E [], an immediate improvement compared to [58]. In the special case when L linear in æ, the ST estimator is not only unbiased but has zero variance, i.e., is exact.
II) How does using a mismatched proxy in Line of Alg. 1 affect the gradient in Φ² Since tiag(F") occurs in the backward chain, call estimators that use some matrix A instead of diag(F') internally rescaled. We show that for any A > 0, the expected rescaled estimator has non-negative scolar product with the expected original estimator. Note that this not completely obvious as the claim is about the final gradient in the model parameters & (e.g.. weights of the encoder network in the case of autoencoders). However, the ST gradient. by Alg. is biased (when C is not multi-linear) but is nevertheless an ascent direction in expectation, the expected rescaled estimator may fail to be an ascent direction, i.e., to have positive scalar product with the true gradient.
III) When does ST gradient provide valid ascent direction? Assuming that all partial derivatives (x()) #C(z)
Diss are L-Lipschitz continuous for some L,, we show that the erpected ST gradient is an ascent direction for any network if and only if [=]]][ > L for i.
IV) Can we decrease the bias? Assume that the loss function is applied to a linear transform of Bernoulli variables, i.e., takes the form L(x) = (Wx). typical initialization uses random W normalized by the size of the fan-in, i.e., such that || l2 = 1 Vk. In this case the Lipschitz conslant of gradients of L scales as OLL/vn), where is the number of binary variables. Therefore, using more binary variables decreases the bias, at least at initialization.

---

8 A. Shekhovtsoy & V. Yanush
V) Does deterministic ST give an ascent direction? Let g" be the determin- istic ST gradient for the state x² sign(a) and p" p(z*la) be its proba- bility. We show that determinislic ST gradienl forms a positive scaler product with the expected ST gradient if 1oo 2 21(1 -p") and with the true gradient if 1oo 2 (L(1-p")+11 From this we conclude that deterministic ST positively cor- relates with the true gradient when C is multilinear, improves with the number of hidden units in the case described by TV and approaches expected stochastic ST units learn to be deterministic that the factor (1 (1-p1 p*) decreases.
Deep ST So far we derived and analyzed ST for a single layer model. It turns out that simply applying Alg. 1 in each layer of a deep model with conditional Bernoulli units gives the correct extension for this case. We will not focus on deriving deep ST here, but remark that can be derived rigorously by chaining derandomization and lincarization steps, discussed above, for cach layer [48]. In particular, [48] show that ST can be obtained by making additional lineariza- tions in their (more accurate) PSA method. The insights from the derivation are twofold. First, since derandomization is performed recurrently, the variance for deep layers is significantly reduced. Second, we know which approximations con- tribute to the bias, they are indeed the linearizations of all conditional Bernoulli probabilities in all layers and of the loss function as function of the last Bernoulli layer. We may expect that using more units, similarly to property IV, would improve linearizing approximations of intermediate layers increasing the accuracy of deep ST gradient.
3 Latent Weights do Exist!
Responding to the work Laatent weights do not exist: Rethinking binarized neural network optimization" [24] and the lack of formal basis to introduce
latent weights in the literature (e.g., [27]), we show that such weights can be formally defined in SBNs and that several empirical update rules do in fact correspond to sound optimization schemes: projected gradient descent, mirror descent, variational Bayesian learning.
Let w be =1-Bernoulli weights with p(w,=1)= 6,, let L(w) be the loss func- tion for fixed training input. Consistently with the model for activations (1), we can define w; sign(1, - x) in order to model weights w; using parameters E R which we will call lalent weights. It follows that 0, = F2(m)) We need to tackle two problems in order to optimize Ew--tw))) ( [[(w] in probabilities 0: i) how estimate the gradient and ii) how handle constraints [0. 1|m
Projected Gradient A basic approach to handle constraints is the projected gradient descent:
g := clip((' -eg',
(10)

---

Reintroducing Straight-Throuuh Methods
9
where g¹ Vell pfl [C(w)] and clip(æ, a, b) max(min(2; 6), a) is the projection. Observe that for the uniform noise distribution on [-1,1] with F(2) clip( 2
2+1 0, 1), we have 0g = p(w;=1) = F(n.) clip( 2 O, 1). Because this F
is linear on [_,, the update (10) can be equivalently reparametrized in o as
+=
= clip(nn
(11)
where h' V, ((n)) [[(w)] and =' 4e. The gradient in the latent weights, h', can be estimated by Alg. and simplifies by expanding 2F" 1. We obtained that the emperically proposed method of Hubara et al. [27, Alg.1] with stochastic rounding and with real-valued weights identified with n is equivalent to PGD on n, with constraints 17 E [-1,1]" and ST gradient by Alg. 1.
Mirror Descent As an alternative approach to handle constraints 0 E [0, 1]mh, we study the application of mirror descent (MD) and connect it with the identity ST update variants. A step of MD is found by solving the following proximal problem:
o = =ming [(g' - 0²) [
(12)
The divergence term D weights how much we trust the linear approx- imation (g', 0-00) when considering a step from 0f to 0. When the gradi- ent is stochastic we speak of stochastic märror descent (SMD) [3, 59]. A com- mon choice of divergence to handle probability constraints is the KL-divergence 01),,0)) (T,(BerOO,,, Ber(O!)) = 0, log( 8 + (1 - 0.) log( h ). Solving for a stationary point of (12) gives
0 = of + _ [log( (1-))))))) - -log( T-
(13)
Observe that when F = a we have log( (og( = nh. Then the MD step can be written in the well-known convenient form using the latent weights n (natural parameters of Bernoulli distribution):
0c = (nn";
1y n
(14)
We thus have obtained the rule where on the forward pass 0 (n) defines the sampling probability of w and on the backward pass the derivative of a, that otherwise occurs in Line 5 of Alg. 1, is bypassed exactly as if the identily prozy was used. We define such ST rule for optimization in weights as Alg, 2. Its correctness is not limited to logistic noise. We show that for any strictly monotone noise distribution F there a corrosponding divergence function D: Proposition 1. Common SGD in latent weights n using the identity straight- through-weights Alg. 2 implements SMD in the weight probabilities 0 with the divergence corresponding to F.
Proof in Appendix C. Proposition reveals that although Bernoulli weights can be modeled the same way as activations using the injected noise model

---

10 A. Shekhovtsov & V. Yanush
sign(1) =), the noise distribution F for weights correspond to the choice of the optimization proximity scheme.
Despite generality of Proposition 1, we view the KL divergence as a more reliable choice in practice. Azizan et al. [3] have shown that the optimization with SMD has an inductive bias to find the closest solution to the initialization point as measured by the divergence used in MD, which has a strong impact generalization. This suggests that MD with KT. divergence will prefer higher entropy solutions, making more diverse predictions. It follows that SGD on latent weights with logistic noise and identity straight-through Alg. 2 enjoys the same properties.
Variational Bayesian Learning Exlending the results above, we study the variational Bayesian learning formulation and show the following:
Proposition 2. Common SGD in latent weights with weight decay and identity straighhtthrooggh-wiihhts Alg. is equivalent to optimizing a factorized variational approzimation to the weight posterior p(w) data) using a composite SMD method.
Proof in Appendix C.2. As we can see, powerful and sound learning tech- niques can be obtained in a form of simple update rules using identity straight- through estimators. Therefore, identity-ST is fully rehabilitated in this context.
4 Experiments
Stochastic Autoencoders Previous work has demonstrated that Gumbel- Softmax (biasod) and ARM (unbiased) estimators give better results than ST on training variational autoencoders with Bernoulli latents [16, 29, 57]. However, only the test performance was revealed to readers. We investigate in more detail what happens during training. Except of studying the training loss under the same training setup, we measure the gradient approximation accuracy using ARM with 1000 samples the reference.
We train simple yet realistic variant of stochastic autoencoder for the task of text retricval with binary representation on 20newsgroups datasct. The autoen- coder is trained by minimizing the reconstruction loss (2). Please refer to Ap- pendix D.2 for full specification of the model and experimental setup.
For each estimator we perform the following protocol. First, we train the model with this estimator using Adam with Ir 0.001 for 1000 epochs. We then switch the estimator to ARM with 10 samples and continue training for 500 more epochs (denoted ARM-10 correction phase). Fig. 3 top shows the training performance for different number of latent bits n. It is seen (esp. for 8 and 64 bits) that some estimators (esp. ST and det_ST) appear to make no visible progress, and even increase the loss, while switching them to ARM makes a rapid improvement. Does it mean that these estimators are bad and ARM is very good? An explanation of this phenomenon is offered in Fig. 5. The rapid improvement by ARM is possible because these estimators have accumulated a

---

Reintroducing Straight-Through Methods
11
bits
64 bits
256 bits
corretionn
Training Loos.
50-
DKL
Crecine Similarity Exquected Improvoneent
Cone-tl)
Fig. 3: Comparison of the training performance and gradient estimation accu- racy for stochastic autoencoder with different number of latent Bernoulli units (bits). Training Loss: each estimator is applied for 1000 epochs and then switched to ARM-10 in order to correct the accumulated bias. Expected improvement: lower is better (measures expected change of the loss), the dashed line shows the max- imal possible improvement knowing the true gradient. Cosine similority; higher is better, close 1 means that the direction is accurate while below 0 means the estimated gradient is not ascent direction; error bars indicate empirical 70% confidence intervals using 100 trials.
significant bias due a systematic error component, which nevertheless can be easily corrected by unbiased estimator.
To measure the bias and aligmment of directions, as theoretically analyzed in Scction 2.1, we evaluate different estimators at the same parameter points located along the learning trajectory of the reference ARM estimator. At each such point we estimate the true gradient g by ARM-1000. To measure the quality a candidate 1-sample estimator Ò we compute the expected cosine similarity and the expected improvement, defined respectively as:
ECS E (g. g) [[1l[llll@@@
El Egg g)1/ B [
(15)
The expectations are taken over 100 trials and all batches. detailed explana- tion of these metrics is given in Appendix D.2. These measurements, displayed in Fig. 3 for different bit length, clearly show that with small bit length biased estimators consistently run into producing wrong directions. Identity ST and deterministic ST clearly introduce an extra bias to ST. However, when we in- crease the number of latent. bits, the accuracy of all biased estimators improves, confirming our analysis IV, V.

---

12
A. Shekhovtsoy & V. Yanush
200
Z
X
-2
x²
X2
a²
Max Pool
BN
wh f(X2
Fig. 4: Stochastic Binary Network: first and last layer have real-valued weights. BN layers have real-valued scale and bias parameters that adjust scaling of activations relative to noise. Z are independent injected noises with chosen distribution. Binary weights Way are random +1 Bernoulli@:;) with learnable probabilities Oy. In experiments we consider SBN with a convolutional architec- ture same as [15, 27]: (2x12803) MP2 - (2x256C3) - MP2 (2x512C3) - MP2 (2x (2x1024FC) - 10FC softmax.
The practical takeaways are as follows: 1) biased cstimators may perform significantly better than unbiased but might require correction of the sys- tematically accumulated bias; 2) with more units the ST approximation clearly improves and the bias has less detrimental effect, requiring less correction; 3) Alg. 1 is more accurate than other ST variants in estimating the true gradient.
Classification with Deep SBN In this section we verify Alg, 1 with different choice noises in a deep network and verify optimization in binary weight probabilities using SGD on latent weights with Alg. 2. We consider CIFAR- 10 dataset and use the SBN model illustrated in Fig. 4. The SBN model, its initialization and the full learning setup detailed in Appendix D.3. We trained this SBN with three choices of noise distributions corresponding to proxies used by prior work in Fig. 1 (c-e). Table shows the test results in comparison with baselines.
We see that training with different choices of noise distributions, correspond- ing to different ST rules, all achieves similar results. This is contrast to em- pirical studics advocating specific proxies and is allowed by the consistency of the model, initialization and training. The identity ST applied to weights, im- plementing SMD updates, works well. Comparing to empirical ST basclines (all except Peters & Welling), 'det' column indicating that our derived ST method is on par with the well- guessed baselines. the same networks are tested the stochastic mode ('10- sample' column), there is a clear boost of performance, indicating an advantage of SBN models. Out of the two experiments of Hubara et al., randomized train- ing (rand.) also appears better confirming advantage of stochastic ST. In the differ-
that there is no significant difference in the
stochastic mode, there is small gap to Peters & Welling, who ent estiimation method and pretraining. Pretraining real valued network also seem important, e-g., [19] report 91.7% accuracy with VGG-Small using pre- training and a smooth transition from continuous to binarized model. When our method is applied with an initialization from a pretrained model, improved results (92.6% 10-sample test accuracy) can be obtained with even smaller

---

Reintroducing Straight-Througl Methods
13
Table Test accuracy for different methods on CIFAR-10 with the same/sim- ilar architecture. SBN can be tested either with zero noises (det) or using an ensemble of several samples (we use 10-sample). Standard deviations are given w.r.t. to 4 trials with random initialization. The two quotations for Hubara et al. [27] refer to their result with Torch7 implementation using randomized Htanh and Theano implementation using deterministic Htanh, respectively.
STOCHASTIC TRAINING
Method
det
10-sample
Our SBN, logistic noise
89.6 : 0.1 90.6 + 0.2
Biased approximation
Our SBN, uniform noise
89.7 + 0.2 90.5 + 0.2
Our SBN, triangular noise
89.5 = 90.0 = 0.3
Unbiased correction
Hubara et al. [27] (rand.)
89.85
Biased estimator
Peters & Welling [43]
88.61
16-sample:
trajectory
91.2
DETERMINISTIC TRAINING
True function
Rastegari et al. [45]
89.83
Hubara et al. [27] (det.)
88.60
Fig. 5: Schematic explanation of the optimization process using a biased esti- mator followed by correction with unbiased estimator. Initially, the biased estimator makes good progress, but then the value of the true loss function may start growing while the optimization steps nevertheless come closer to the optimal location in the parameter space.
network [35]. There are however even more superior results in the literature, e.g., using neural architecture search with residual real connections, advanced data augmentation techniques and model distillation [10] achieve 96.1%.
The takeaway message here is that ST can be considered in the context of deep SBN models as simple and robust method if the estimator matches the model and is applied correctly. Since we achieve experimentally near 100% training accuracy in all cases, the optimization fully succeeds and thus the bias ST is tolerable.
5 Conclusion
We have put many ST methods a solid basis by deriving and explaining them from the first principles in framework. It is well-defined what they estimate and what the bias means. We obtained two different main estimators for propa- gating activations and weights, bringing the understanding which function they have, what approximations they involve and what are the limitations imposed by these approximations. The resulting methods in all cases are strikingly simple, no wonder they have been first discovered empirically long ago. We showed how our theory leads a useful understanding of bias properties and reasonable choices that allow for more reliable application of these methods. We hope that researchers will continue to use these simple techniques, now with less guesswork and obscurity, well as develop improvements to them.

---

References
[1] Ajanthan, T., Gupta, K., Torr, H., Hartley, R., and Dokania, P. Mirror descent view for neural network quantization. arXic preprint 1rXie:1900.0822 2019.
2] Alizadeh, M., Bernandez-Marqueee J., Lane, N. D., and Gal, Y. An empirical study of binary neural networks' optimisation. In ICLR, 2019.
[3] Azizan, N., Lale, S., and Hassibi, B. A study of generalization of stochastic mirror descent algorithms on overparameterized nonlinear models. In ICASSP, pp. 3132- 3136, 2020.
[4] Bai, Y., Wang, Y.-X., and Liberty, E. Proxquant: Quantized neural networks via proximal operators. JCLR, 2019.
[5] Bengio, Y., Léonard, N., and Courville, A. Estimating propagating gradi- ents through stochastic: neurons for conditional computation. arXiv preprint arx:: 1308.3332, 2013.
66 Bethge, J., Yang, H., Bornstein, M., and Meinel, C. Back to simplicity: How to train accurate BNNs from scratch? CoRR, abs/1906 1es/1996.08677, 2019.
7 Boros, E. and Hammer, P. BeeuooBoolean optimization. Discrete Applied Mathi ematics, 1-3( 1-3(12)):155 225, 2002.
88 Bulat, A. and Tximiropoulos, G. Binarized convolutional landmark localizers for human pose estimation and face alignment with limited resources. In ICCV, Oct
2017.
9 Bulat, A., Tzimiropoulos, G., Kossaifi, J., and Pantic, M. Improved training of
binary networks for human pose estimation and image recognition. arXiv, 2019.
[10] Bulat, A., Martinez, B., and Tzimiropoulos, G. BATS: Binary architecture search, 2020.
[11] Bulat, A., Martinez, B., and Tzimiropoulos, G. High-capacity expert binary net- works. In ICLR, 2021.
[12] Chaidaroon, S. and Fang, Y. Variational deep semantic hashing for text docu- Research and Development in Information Re-
ments. In SIGIR Conference trieval, pp. 75-84, 2017.
[13] Cheng, P., Liu, C.,, Li, C., Shen, D., Henao, R., and Carin, L. Straight-through es- timator as projected Wasserstein gradient flow. arXiv preprial arXi::1910.0211 02176. 2019.
[14] Cong, Y., Zhao, M., Bai, K., and Carin, L. GO gradient for expectation-baset objectives. ICLR, 2019.
[15] Courbariaux, M., Bengio, Y., and David, J.-P. Binaryconuect: Training deep neural networks with binary weights during propagations. In NearIPS, pp. 3123
3131, 2015.
[16] Dadaneh, S. Z., Boluki, S., Yin, M., Zhou, M., and Qian, X. Pairwise supervised hashing with Bernoulli variational auto-encoder and self-control gradient estima- tor. ArXio, abs/2005.10477 2020.
[17] Dai, B., Guo, R., Kumar, S., He, N., and Song, L. Stochastic generative hashing.
In ICML, ICML'17, pp. 913-922, 922, 2017.
[18] Faser, S. K., Merolla, P. A., Arthur, V., Cassidy, A. S., Appuswamy, R., An- dreopoulos, A., Berg, D. J., McKinstry, J. L.,, Melano, T., Barch, D. R., di Nolfo,

---

Reintroducing Straight-Throuuh Methods
15
C., Datta, P., Amir, A., Taba, B., Flickner, M. D., and Modha, D. S. Convolu- tional networks for fast, energy-efficient neuromorphic computing. Proceedings of the National Academy of Sciences, 113(41):1141 11446, 2016.
[19] Gong, R., Liu, X., Jiang, S., Li, T., Hu, P., Lin, J., Yu, F., and Yan, J. Dif- ferentiable soft quantization: Bridging full-precision and low-bit neural networks. In Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV), October 2019.
[20] Grathwohl, W., Choi, D., Wu, Y., Roeder, G., and Duvenaud, D. Backpropagation through the void: Optimizing control variates for black-box gradient estimation.
In ICLR, 2018.
[21] Graves, A. Practical variational inference for neural networks. In NewrIPS, pp-
2356. 2011.
[22] Gregor, K., Danihelka, I., Mnih, A., Blundell, C., and Wierstra, D. Deep autore- gressive networks. In ICML, 2014.
[23] He, K., Zhang, X., Ren, S., and Sun, J. Delving deep into rectifiers: Surpassing
human-level performance on ImageNet classification. In ICCV, pp. 1026-1034, 2015.
[24] Helwegen, K., Widdicombe, J., Geiger, L., Liu, Z., Cheng, K.-T,, and Nusselder, R. Latent weights do not exist: Rethinking binarized neural network optimization.
In NeurIPS, pp. 7531-7542, 2019.
[25] Hinton, G. Lecture 15d Semantic hashing 3:05 3:35, 2012. URL hitps:
/ //www.cs. Lowonto.edu/ /atit///hittooooti (ooursera/lecuur155// 1esture15/lec5dd.mm
[26] Horowitz, M. Computing's energy problem (and what can do about it). In International Solid-State Circuits Conference Digest of Technicol Papers (ISSCC),
pp. 10-14, 2014.
[27] Hubara, 1., Courbariaux, M., Soudry, D., EI- El-Yaniv, R., and Bengio, Y. Binarized neural networks. In NewriPS, pp. 4107-4115, 2016.
[28] loffe, S. and Szegedy, C. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In ICML, volume 37, pp. 448 456, 2015. [29] Jang, E., Gu, S., and Poole, B. Categorical reparameterization with gumbel- softmax. In ICLR, 2017.
[30] Khan, E. and Rue, H. Learning algorithus from Bayesian principles. August 2020.
Draft v. 0.7.
[31] Kingma, D. P. and Ba, J. Adam: A method for stochastic optimization. In ICLR,
2015.
[32] Krizhevsky, A. and Hinton, G. E. Using very deep autoencoders for content-based
image retrieval. In ESANN, 2011.
[33] Lin, W., Khan, M. E., and Schmidt, M. Fast and simple natural-gradient vari- ational inference with mixture of exponential-faniiy approximatious. In ICML, volume 97, Jun 2019.
[34] Liu, Z., Wn, B., Luo, W., Yang, X., Lin, W., and Cheng, K.-T. Bi-real net: En- hancing the performance of 1-bit CNNs with improved representational capability and advanced training algorithm. In ECCV, pp. 722-737, 2018.
(35] Livochka, A. and Shekhovtsov, A. Initialization and transfer learning of stochastic binary networks from real-valued ones. In Proceedings of the IEEE/CVF Confer- ence on Computer Vision and Pattern Recognation (CVPR) Workshops, 2021.
[36] Martinez, B., Yang, J., Bulat, A., and Tzimiropoulos, G. Training binary neural networks with real-to-binary convolutions. In ICLR, 2020.
[37] Meng, X., Bachmann, R., and Khan, M. E. Training binary neural networks using the Bayesian learning rule. In JCML, 2020.

---

16
A. Shekhovtsov & V. Yanush
[38] Nanculef, R., Mena, F. A., Macaluso, A., Lodi, S., and Sartori, C. Self-supervised bernoulli autoencoders for semi-superee supervieee hashing. CoRR, abs/2007 20//2097087799, 2020. Nemirovsky, A. S. and Yudin, D. B. Problem complezity and method efficiency in optamization. 1983.
[39]
[40] Owen, A. B. Monte Carlo theory, methods and ezamples. 2013.
[11] Paszke, A., Gross, S., Massa, F., Lever, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga, L., Desmaison, A., Kopf, A., Yang, E., DeVito, Z. Raison, M., Tejani, A., Chilamkurthy, S., Steiner, B., Fang, L., Bai, J., and Chintala, S. Pytorch: An imperative style, perforrefore deep learning library.
In NewrIPS, pp. 8021 8035, 2019.
[12] Pervez, A., Cohen, T., and Gavves, E. Low bias low variance gradient estimates for boolean stochastic networks. In ICML, volume 119, pp. 7632-7640, 13-18 Jul 2020.
[43] Peters, J. W. and Welling, M. Probabilistic binary neural networks. Xrv preprinl 1rXii:1809.00333 2018.
[44] Raiko, T., Berglund, M., Alain, G., and Dinh, L. Techniques for learning binary stochastic feedforward neural networks. In ICLR, 2015.
[15] Rastegari, M., Ordonez, V., Redmon, J., and Farhadi, A. XNOR-Net: Imagenet classification using binary convolutional neural networks. In BCCV, pp. 525-542.
Springer, 2016.
[46] Roth, W., Schindler, G.,, Fröning, H., and Pernkopf, F. Training discrete-valued neural networks with sign activations using weight distributions. In European Conference Machine Learning (ECML), 2019.
[47] Shekhovtsov, A. Bias-variance tradeoffs single-sample binary gradient estima- tors. In GCPR, 2021.
[48] Shekhovtsov, A., Yamush, V., and Flach, B. Path sample-analytic gradient esti- mators for stochastic binary networks. In NewrIPS, 2020.
[19] Shen, D., Su, Q. Chapfuwa, P., Wang, W., Wang, G., Henao, R., and Carin, L. NASH: toward end-to-end neural architecture for generative semantic hashing. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics, ACL 2018, Melbourne, Australia, July 15-20, 2018, Volume Long Papers, pp. 2041-2050 2018.
[50] Srivastava, N., Hinton, G., Krizhevsky, A., Sutskever, L., and Salakhutdinov, R. Dropout: A simple way to prevent neural networks from overfitting. JML.R 15: 1929 1958, 2014.
[51] Sun, Z. and Yao, A. Weights having stable signs are important: Finding primary subnetworks and kernels to compress binary weight networks, 2021.
[2) Tang, W., Hua, G., and Wang, L. How to train compact binary neural network with high accuracy? In AAAI, 2017.
[53] Titsias, M. K. and Lázaro-Gredillas M. Local expectation gradients for black box
variational inference. In NewrIPS, pp. 2638-2646, 2646, 2013.
[54] Tokui, S. and Sato, T. Evaluating the variance of likelihood-ratio gradient estima- tors. In TCML, pp. 3414-3444 --123,,, 2017.
(55 Tucker, G., Mnih, A., Maddison, C. J., Lawson, J., and Sohl-Dickstein, J. REBAR:
Low-variance, unbiased gradient estimates for discrete latent variable models. In NewrIPS, 2017.
[56] Xiang, X., Qian, Y., and Yu, K. Binary deep neural networks for speech recogni-
tion. In INTERSPEECH, 2017. [57] Yin, M. and Zhou, M. ARM: Aygmen:RRIINFORC--merg gradient for stochas- tie binary networks. In ICLR, 2019.

---

Reintroducing Straight-Throuuh Methods
17
[58] Yin, P., Lyu, J., Zhang, S., Osher, S., Qi, Y., and Xin, J. Understanding straight- through estimator in training activation quantized neural nets. arXiv preprint arXim:1933005660 2019.
[59] Zhang, S. and He, N. On the convergence rate of stochastic mirror descent for nonsmooth nonconvex optimization. arXi:: Optimization and Control, 2018. 600] Zhou, S., Wu, Y., Ni, Z., Zhou, X., Wen, H., and Zou, Y. Dorefa-net: Training low bitwidth convolutional neural networks with low bitwidth gradients. arXiv preprint arXiv: 06160, 2016.

---

18
A. Shekhovtsoy & V. Yanush
Appendix
A Related Work
Hinton's vs Bengio's ST The name stroight-through and the first experi- mental comparison was proposed by Bengio et al. [5]. Referring to Hinton's lecture, they describe the idea as "simply to back-propagate through the hard threshold function as if it had been the identity function". In the aforementioned lecture [25], however we find a somewhat different description: "during the for- word pass we stochastically pick binory value using the output of the logistic, and then during the backward pass we pretend that we 'ue transmilled the real valued probability from the logistic". We can make two observations: 1) different variants appeared early on and 2) many subsequent works [e.g. 58] attribule these two variants in the exact opposite way, adding to the confusion.
ST Analysis Yin et al. [58] analyzes deterministic ST variants. The theoretical analysis is applicable to 1 hidden layer model with quadratic loss and the input data following a Gaussian distribution. The input distribution assumption is ar- guably artificial, however it allows to analyze the expected loss and its gradient. They show that population ST gradients using ReLU and clipped ReLU proxy correlate positively with the true population gradient and allow for convergence while identity ST does not. In Appendíx B we show that in the SBN model, a simple correction of the quadratic loss function makes the base ST estimator unbiased and all rescaled estimators including identity are ascent directions in the expectation. Also note that the approach to analyze deterministic ST meth- ods by considering the expectation over the input has a principle limitation for extending to deep models: the expectation over the input of deterministic net- work with two hidden binary layers is still non-smooth (io-diiferentiablle in the paramcters of the second layer.
Cheng et al. [13] shows for networks with 1 hidden layer that STE is approx- imately related to the projected Wasserstein gradient flow method proposed there.
On the weights side of the problem, Ajanthan et al. [1] connected mirror descent updates for constrained optimization (e.g., w E [0, 1)m") with straight- through methods. The connection of deterministic straight-througs and proximal updates was also observed in [4]. Mirror Descent has been applied to variational Bayesian learning of continuous weights e.g. in Lin et al. [33], taking the form of update in natural parameters with the gradient in the mean parameters, same as in our case.
for weights
Alternative Estimators For deep binary networks several gradient estimation approaches are based on stochastic gradients of analytically amoothed/approo imated loss [43, 46). There is however a discrepancy between analytic approx- imation and the binary samples used at the test time. Shekhovtsov et al. [48,

---

Reintroducing Straight-Through Methods
19
Fig, 4] show that such relaxed objectives may indeed significantly diverge dur- ing the training. To obtain good results, a strong dropout regularization and/or /r pretraining is needed [43, 46). Despite these difficulties they demonstrale on par or improved results, especially when using average prediction over multiple noise samples at test time.
Dai al. [17] perform a correct interchange of derivative and integral in (3) using weak (distributional) derivatives. After computing local expectations in this more complicated formalism, they are back with finite differences (6) which they also propose to linearize as in (7). Thus their distributional SGD is equivalend to common SGD with the ST estimator Alg. 1.
Bayesian Learning Bayesian learning in the form of simple update rules are recently (contemporaneouskt) studied by Khan & Rue [30]. We emphasize the interplay with the identity-ST estimator and the connection to the implicit reg- ularization. The recent work by Meng et al. [37] proposed Bayesian learning with binary weights using Gumbel-SSfftax estimator gradients. We analyze it [47] and demonstrate that it reduces to a different, non- non-Baysiann, rule when appliod in large-scale experiments.
B Analysis of ST with Hidden Layer
B.1 Invariances
We have the following simple yet desirable and useful property. It is easy observe that binary activations admit equivalent reformulations
sign(a: =1) = sign(T - T(z)))
(16)
for any strictly monotone mapping T R R. Proposition B.1. The gradient computed by Alg. invariant to equivalent transformations under sign as in (16).
Proof. Let us denote the transformed noise as 2 T(2). its odf as G and the transformed activations as ā; T(a:). The sampling probability in line 2 of Alg. 1 does not change since after the transformation it computes G(ā,) P(,; < ā. ā.) = IP(2; S a;) F(a.). The gradient returned by line does not change since we have da; G(T((,))) = Fa,)).
In contrast, empirical straight-throur designed fail to maintain this property. particular, in the deterministic straight- through approach transforms such as sagn(a,) sign (a,;)) while keeping the proxy of sign used in backprop fixed lead to different gradient estimates. This partially explains why many proxies have been tried, e.g- ApproxSign [34], and their scale needed tuning, Another pathological special case that leads to con- fusion between identity trraight-througe and other forms is as follows.
approaches where the proxy is hand-
Corollary B.1. Let F be striclly monolone. Then lelling T F leads to T(2:) being uniformly distributed. Let ā, = T(a:). In this case the backpropagation rule

---

20
A. Shekhovtsov & V. Yanush
in line 5 of Alg. 1 con be interpreted as replocing the gradient of sign(ā. (ā; - (2+)) in 0N with just identity.
Indeed, since ž; = T2;) is uniform, we have G' = 1 on (0, 1) and - F(a;) is guaranteed to be in (0, 1) by strict monotonicity. The gradient back-propagated by usual rules through a (outside of the ST Alg. 1) encounters derivative P as before. Hence we see that the description "to back prokk-pr through the hard threshold function as it had been the identity function"" could be misleading what transformations are applied
the resulting estimator crucially depends under the hard threshold despite they do not affect the network predictions in any way. We refer to the variant by [5] as identity-ST, as it specifically uses the identity proxy for the gradient in the pre-sigmoid activation.
B.2 Bias Analysis
1) Since the only approximation that we made was linearization of the objective C, we have the following basic property.
Proposition B.2. If the objective function L multilinear* in the binary vari- ables x, then Alg. is unbiased.
Proof. In this case (7) holds as equality.
While extremely simple, this is an important point for understanding the ST estimator. As an immediate consequence we can casily design counter-cxamples where ST is wrong.
Example Let a E R, x r= sign(a z) and C(x) = x². In this case the expected value of the loss is 1, independent of a. The true gradient is zero. However the expected ST gradient is B[2F" (a)2x] 4F" (a)(((()) 1) and can be positive or negative depending
a.
Example 2 (Tokui & Sato 54). Let [(x) = sin(2nz), Then the finite dif- ference C(1) (0) = 1 but the derivative ac dr = 1 2T cos(2 = 1. In this failure example, ST, even in the expectation, will point to exactly the opposite direction of the true gradient.
An important observation from the above examples is that the result of ST is not invariant with respect to reformulations of the loss that preserve its values in all binary points. In particular, we have that L = 1 in the first example and [(x) = in the second example for any E (). If we used these equivalent representations instead, the ST estimator would have been correct.
More generally, any real-valued function of binary variables has a unique polynomial (and hence multilinear) representation [7] and therefore it is possible find a loss reformulation such that the ST estimator will be unbiased. Un- fortunately, this representation is intractable in most cases, but it is tractable, e.g., for quadratic loss, useful in regression and autocncoders with Gaussian observation model.
E.g. 313223 trilinear and thus qualifies but of not multi-linear.

---

Reintroducing Straight-Through Methods
21
Proposition B.3. Let L(x) | y1? Then the multilinear equivalent
reformulation of L is given by
[(x)= = Wa - yll Σ: 2. W 1 + + W.,l,
(17)
where W., the i 'tth column of W.
Proof. By expanding the square and using the identity zī for 24 1).
Simply adjusting the loss using this equivalence and applying ST to it, fixes the bias problem.
II) Next we ask the question, whether dropping the multiplier diag(F"(a) or changing it by another multiplier, which we call an (internal) rescaling of the estimator, can lead to an incorrect estimation.
Proposition B.4. instead of diag(F'(a) (a)) any posilive semidefinite diagonal matriz A is used in Alg. the expected rescaled estimator preserves non-negative scalar producl with the original eslimator.
Proof. We write the chain (9) in a matrix form as J { (z), with the Jacobians J1 da A diag(F (a)) and J2(x:) ac(#) The modified gradient with A is then defined as JI [
We are interested in the scalar product between the expected gradient esti- mates:
(18)
where the expectation is over Since neither J1 nor A, Ao depend on æ, we move the expectations J2. Let J2 E. [6(w]] Then the scalar product between the expected estimates becomes
= (TJAAJ,
(19)
Notice that J.JT is positive semi-definite, Ag is also positive scmi-definite since it is diagonal with non-negative entries. It follows that R = JJ { Ao is positive semidefinite and that J,RJJ positive semi-definite. Its trace is non-negative.
We obtained that the use of an internal rescaling, in particular identity in- stead of F", is not too destructive: if Alg. 1 unbiased, the rescaled estimator may be biased but it is guaranteed to give ascend direction in the expectation that the optimization can in principle succeed. However, assuming that Alg, 1 is biased (when L is not multi lintirlinear) but gives an ascent direction in the expec- tation, the ascent direction property cannot be longer guaranteed for the rescaled gradient.
III) Next, we study whether the ST gradient is a valid ascent direction even when C is not multi-linear.
Proposition B.5. Let L(x) be such that its partiol derivative 9: ac function of Is is Lipschitz continuous for all i with constant L. Then the expected ST gradient is an ascent direction for any al a($) and L(x)) if and only if
[|g.]] > L for all i.
(20)

---

22
A. Shekhovtsov & V. Yanush
Proof. Sufficieccy (if part), The true gradient using the local expectation form (6)
expresses as
E Σ
aa. Bp
= E[JA],
(21)
where the expectation is w.it.. x ~ p(2; Φ) and we introduced the matrix no- lation J (oa) diag(p=(a)), and A. zi (<(())-((x)))) The ST gradient replaces A, with (z)()). Since in both cases does not depend on æ, the ex- pectation can be moved the last term. Respectively, let us define Á E[A] and 9 Elg). The scalar product between the true gradient and the expected ST gradient can then be expressed
(JA, ""(JA"""")
(22)
From the relation
1 (x(((x)- - ((xp)) = gi (x)dr;
(23)
and Lipschitz continuity of gi in x4 we have bounds
2(gi(x) - L) S x. - ((xrs)) s 2(gi(2)) + L).
(24)
follows that
2( - L) S EE A < 2(E + L),
(25)
cooddinate-wise. The outer product - is positive semidefinite iff g. 4, 2 0 for all According to bounds above, this holds true if
(Vi 0. 2 0)
2( L) 2 0
(26)
(Vi 0: < 0) 2( + L) = O,
(27)
or simply (Vi) 06 L.
Necessily (only if part). We want to show that the requirements (20), which are simultaneous for all coordinates of g, cannot be relaxed unless we make some further assumptions about L. Namely, 3f" such that ğ:- Ar- then there exists such that (Jg. < 0. Lee single wrong direction can potentially be rescaled by the downstream Jacobians to dominate the contribution of other components. This is detailed in the following steps.
Assume (3(*) Iø.-1 < L. Then exists L(x) such that the bounds (24) are tight (e.g. C(x) = .x2) and therefore there will hold ği- A,- < 0. Since A = diag(p:(a)) is positive scmi-definite, Ag A A will preserve the non-positive sign of the com- ponent (i* ( There exists (()) such that da scales down all coordinates o i äe
and scales up i* such that the Tr(JAATJ] J") is dominated by the entry (1*, The resulting scalar product between the expected gradient and the true gradient thus can be negative.

---

Reintroducing Straight-Through Methods
23
IV) Next we study, a typical use case when hidden binary variables are com- bined using linear layer, initialized randomly. A typical initialization procedure would rescale the weights according to the size of the fan-in for each output. Proposition B.6. Assume that the loss function is applied after a linear nor- malized transform of Bernoulli variables, i.e., takes the form
[(x)) = ((W,,
(28)
where E kxx a malrix of normally distributed weights, normalized satisfy k 12 vk. Then the expected Lipschitz constont of gradients of C scales O V.l.
Proof. Let Wæ and let dt be Lipschitz continuous with constant L. The gradient of L expresses as
ou
9.
dC(m) (f(u) W.
de.
du
(29)
By assumptions of random initialization and normalization, Wk, N(0 4) If we consider [gs| in the expectation over initialization we obtain that
Ew (x) - 9:(1))] Eww (W e(Wy), W..) s LEW [[ LK
v
2
(30)
Therefore It has expected Lipschitz constant LK
2
The normal distribution assumption not principal for conclusion of O dependance. Indeed, for any distribution with finite variance it would hold well, differing only in the constant factors. We obtain an important corollary. Corollary B.2. As we increase the number of hidden binary wnils n in the model, the bias of ST decreases, at least at initialization.
V) Finally, we study conditions when a deterministic version of ST gives a valid ascent direction.
aL(w) be Lipschitz continuous with Proposition B.7. Let sa) Let gi de, constant L. Let g* g(x*) and p" p(===(''pppp la). The deterministic ST gradient at x' forms a positive scolar product with the expected stochastic ST gradient if
l 2 2(1 P')L Vi.
(31)
diag(p:(a)) The scalar prod- uct between the expected ST gradient and the deterministic ST gradient given by
Proof. Similarly to Proposition B.5, let J
di
(JEgg()) Jg") Tr (Big(z))g JT)..
(32)
In order for it to be non-negative we need B[g(m))))) 2 0 Vi. Observe that E[g(#);] is sum that includes of with the weight p². We therefore need
Euter p()))) + + 0.
(33)

---

24
A. Shekhovtsov & V. Yanush
From Lipschitz continuity of gi have the bound lg(x); g. S L/x; x3 using that |2 - xz S we have
gi 2L ALSgg()) S 96 2L.
(34)
Therefore
g 2 ot²² -2
(35)
We thus can lower bound (33) as
Exsxr p(zla) 2L) + p" gf = -2L (1 p*) + 9;
(36)
This lower bound is non-negative if
l 2 2L(1 p")).
(37)
Compared to Proposition B.5, this condition has an extra factor of 2(1 - p" Since p" is the product of probabilities of units of. we expect initially p < This condition improves the same rate with the increase in the number of hidden units as the case covered by Proposition B.6. In addition it becomes progressively more accurate as units learn to be more deterministic, because in this case the factor (1 - p²) decreases. However, note that this proposition describes the gap between deterministic ST and stochastic ST. And even when this gap diminishos, the gap between ST and the true gradient remains.
We can obtain a similar sulficient condition for the scalar product between deterministic ST and the executed true gradient, that (unlike the direct com- bination of Proposition B.5 and Proposition B.7) ensures an ascent direction.
Proposition B.8. Let xx = sign(a). Let g(x); aC(e) be Lipschitz continu- D2. ous with constant L. Let g" = g(x") and p" = p(x (a). The deterministic ST gradient at x² forms a positive scalar product with the true gradient if
lof 2 2(1 P Vi.
(38)
Proof. The proof is similar to Proposition B.7, only in this case need to ensure E[A.19 2 0. Using (25) get the bounds
2(E[g) - L) s E A
<
2(E g) + L),
(39)
And using additionally (34) we get
2(p" of (1 p" (gt - 2L) L) B[A.] 2(p" + (1- + +LL + L).
(40)
Collecting the terms
2(g (11-p')2L- L) B[4] 2( + p³) 22 L).
(41)
Multiplying by of we obtain that sufficient condition for E|A 2 0 is
l N (1 2L + L.
(42)

---

Reintroducing Straight-Through Methods 25
Mirror Descent and Variational Mirror Descent
C.1 Mirror Descent
Mirror descent widely used method for constrained optimization of the form
min f(x), where X с R", introduced by Nemirovsky & Yudin [39]. Let Φ X + I be strictly convex and differentiable on A, called a märror map.
Bregman divergence (æ(æ, y) associated with is defined as
(1 y) x(x)) - ( - (V 8).
(43)
An update of MD) algorithm can be written as:
arg min Vf((')) -o(xx =EX
(44)
the unconstrained case when R or in the case when the critical point is guaranteed to be in X' (as typically ensured by the design of Dø), the solution can be found from the critical point equations, leading to the general form of iterates
v = V - =V\(=")) x (VØ) =V
(45)
Proposition 1. Common SGD in lalent weights using the identity straight- through-weights Alg. 2 implements SMD in the weight probabilities O with the divergence corresponding to F.
Proof. The proof closcly follows Ajanthan al. [1]. Differently from us, they considered deterministic ST. Their argumentation includes taking the limit in which F is squashed into the step function and which renders MD invalid. This limit is not needed in formulation.
We start from the defining equation of MD update in the form (45). In order for (45) to match common SGD on v with = F-)(0,), the mirror map & must satisfy V = F-)(0), where F-1 is coordinate-wise. We can therefore consider coordinate-wist mirror maps &; + R. The inverse F-1 exists if is strictly monotone, meaning that the noise density is non-zero on the support. Finding the mirror map & explicitly is not necessary for our purpose, however in 1D case it can be expressod simply ((x) S (n)(n) With this coordinato- wise mirror map, the MD update can be written as
r = 17' dc
(46)
0=P(n")
Thus MD on 0 takes the form of descent step with the gradient de A common SGD on n would use the gradient dc dn Bn &c Thus (46) bypasses the ae This is exactly what Alg. 2 does. More preciscly, when applying Jacobian ल.

---

26
A. Shekhovtsoy & V. Yanush
the same derivations that we used to obtain ST for activations in order to esti- mate dc since F(m) = 8;, we obtain that the factor ag pw;;; a
(w;; f), present in (6),
de
expresses as
dF(n) de
OF(F-1(0)
(47)
06
and thus can be omitted from the chain rule as defined in Alg.
C.2 Latent Weight Decay Implements Variational Bayesian Learning
In the Bayesian learning setting we consider a model with binary weights w and interested in estimating p(w|D) D), the posterior distribution of the weights given the data D and the weights prior p(w). In the variational Bayesian (VB) formulation, this difficult and multi-modal posterior is approximated by a sim- pler one ((w), commonly a fully factorized distribution. The approximation is achieved by minimizing (L(((w)) p(w[[)) Let q(w) = (er(w;; 0) and p(w) = Ber(wr w: }), both meant component-wei wise, i.e. fully factorized. Then the VB prob- lem takes the form
arg min { (- -B ay)mdaan (er()) [logply x w)]] 1 KL Ber (
(48)
where we have rewritten the data likelihood expectation and hence the coef- ficient 1/N in front. of the KL term appeared. This problem is commonly solved by SGD taking one sample from the training data and one sample of w and applying backpropagation [21]. We can in principle do the same by applying an estimator for the gradient in
The trick that we apply, different from common practices, is not to compute the gradient of the KL term but to keep this term explicit throughout to the proximal step leading to a composite MD [59]. With this have
Proposition 2. Common SGD in latent weights n with weight decay and identity
Alg. is equivalent to optimizing factorized variational approzimation to the weight posterior p(w) data) using a composite SMD method.
Proof. Expanding data log-likelihood as the sum over all data points, we get
logp(D w) = E, pog w) = 4(w).
(49)
When multiplying with N: the first term becomes the usnal expected data like- lihood, where the expectation is in training data and weights w ~ g(w). Ex- panding also the parametrization of q(w) = Ber(w w 0), the variational inference reads
arg min - Eur-Ber(0) [ E, ((w)] + {KL(g())lp((w)) + const).
(50)

---

Reintroducing Straight-Througl Methods
27
We employ mirror descent to handle constraints 0 E [0, 11th similar to the above but now we apply it to this composite function, lincarizing only the data part and keeping the prior KL part non-linear. Let
Σ SE
g
T
be the stochastic gradient of the data term the weight probabilities 0 using a min-batch I. The SMD step subproblem reads
ming {g KT. (O)BBerr()]] (e)l + +N (TT((er()))
(51)
We notice that KL((err()) (B)r((0)[Ber(t)))) = ( also introduce the prior scaling coefficient X = N in front of the entropy, which may optionally be lowered to decrease the regularization effect. With these no- tations, the composite proximal problem becomes
-H((err(O)) the negative entropy, and
ming {g T (Ter(r(0)) Ber((")) (H((Br())))
(52)
The solution is found from the critical point equation in 0:
Ve 1 + (Ke(Be)(O) (O)[|Br(())) - AH (Ber(()))
(53a)
9i + llog 9. - log
0r 1-0:
+ A log 0. 1-4; =
(53b)
I 1-0;
(e) + 1) log 1-11 = log
1-0 Eg:
0,
(53c)
0 log 1-0; et+l log 1f eA+1 Di-
(53d)
For the natural parameters we obtain:
n'-29 7 ex+1
=n
extI (2n +g) 5
(54)
We can further drop the correction of the step size ex+1 since εA 1 and the step size will need to be selected by cross validation anyhow. This gives us an update of the form
7 1 - + An
(55)
which is in the form a standard step in any SGD or adaptive SGD optimizer. The difference is that the gradient in probabilities @ is applied to make step in logits v and the prior KI. divergence contributes the logil decay X, which in this case is the latent weight decay, Since the ST gradient in 0 differs from the ST gradient in by the factor diag( (F), the clain of Proposition 2 follows.
D Details of Experiments
D.1 MNIST VAE
Here we give specification of the experiment in Fig. 2, which illustrates the point that mismatching the constant factor in front of ST estimator leads to poor performance when the gradient is to be combined with other gradients, in this case with the analytic gradient of KL divergence in VAE.

---

28
A. Shekhovtsoy & V. Yanush
Dataset We MNIST data set It contains 60000 training and 10000 test images of handwritten digits. We used 50000 images for trainig, the reminder was kept as a validation set, however not utilized in this experiment.
Preproccssing No preprocessing or augmentation was performed. The grayscale image intensities in [0, 1] are interpreted target Bernoulli probabilities for the decoder.
Model We used {0, } encoding of hidden states æ. Closely following experiment design of [22, 42], we used the following network as encoder:
Linear(784,200) + tanh + Linear(200,200) - tanh + Linear (200,200).
The output of the encoder defines logits 7 of the encoder Bernoulli model p(z;=1ly) = o (n:). The decoder has the reverse architecture:
Linear(200,200) - tanh + Linear(200,200) + tanh + Linear
and outputs logits v of conditionally independent Bernoulli generative model p des (y==1 = (vs)). The data images t E RR7 are interpreted as target prob- abilities, and the negative conditional log- lig-liiel becomes
= (1: log (yx=1(()) + (1 - 44) log p (y:=0)z))
(56)
We optimize the negative lower bound on the log-likelihood:
L = Eywdataa Beent [ [L(((<])))l](>)))
(57)
where p(æ) is the uniform prior: p(a;)
=
We compute the KI. term analytically for mini-batch and its exact gradient. The gradient of the expectation of И is estimated. We used Adam optimizer with a learning rate in {0.001, 0.0003, 0.0001}.
Optimization
D.2 Stochastic Autoencoder
It shown in the literature that semantic hashing using binary hash codes can achieve superior results using learned hash codes, in particular based on variational autoencoder (VAF) formulation, 6.g-, recent works [12, 16, 38).
We propose series of experiments that targets measuring the accuracy of gradient estimators through Bernoulli units and studying the dependence of this accuracy on the number of hidden units. is appropriate to study here the plain stochastic autoencoder (2) and not variational autoencoder (57)
http://yaam wwtp://yyyammmunn.como/ lecun. wwwp://wwwwwww.o//e//////.oooeee /en////d/////// mmistt/

---

Reintroducing Straight-Through Methods
29
for the following reasons: 1) the gradient of prior KL term is known and need not be estimated, 2) VAE usually finds solutions in a partial posterior collapse (efficiently selecting the number of hidden units to use) which is in contradiction with our goal to study the dependence on the number of hidden units. In practice, the KL prior often needs to be tuned (in the public implement ation of Nanculef al. [38] one can find 3 0.015 is used), which is complicating and irrelevant for our goals.
Dataset The 20Newsgroups data set is a collection of approximately 20,000 text documents, partitioned (nearly) evenly across 20 different nowsgroups. In our experiments we do not use the partitioning. We used the processed version on the dataset's web site. Tt contains
of the dataset denoted as Matlab/Octe bag-of-words representations of documents given by one sparse word-docunent count matrix. We worked with the training set that contains 11269 documents in the bag of words representation.
Preprocessing We keep only the 10000 most frequent words in the training set reduce the computation requirements. Each of the omitted rare words occurs not more than in 10 documenis.
Reconstruction Loss Let y E No be the vector of word counts of a document and æ E (0.1)* x be a latent binary code representing the topic that we will learn. The decoder network given the code æ deterministically outputs word frequencies f E [o, 1J,, Σ, and the reconstruction loss - log ( (yla: 0)
is defined as
- - log
(58)
i.e., the negative log likelihood of a generative model, where word counts y follow multinomial distribution with probabilities f and the number of trials equal to the length of the document. The encoder p(æ) () obtains word frequencies form y and maps them deterministically Bernoulli probabilities p(z:)f:o)
The loss of the autocncoder (2) is then
E Eayda [Bz-p(a)p) [- log p (3) |0 0)]]
(59)
Networks The encoder network takes on the input word frequencies f E Rd and applics the following stack: FC(d x 512), ReLU, FC(512 x n), where FC is a fully connected layer. The output is the vector of logits of Bernoulli latent bits. The decoder network symmetric: FC(n 512), ReLU, FC(512 x d), Softmax. Its input binary latent code and output is the word probabilities f. Standard weight initialization is applied to all linear layers W setting W., u[-1/Vk, 1/VR), where l is the number of input dimensions to the layer. This is a standard initialization scheme [23], which is consistent with the assumptions we make in Proposition B.6 and hence important for verification of our analysis.
http://qwone.com hwt.wooe.coom///oo /oomm//asso///eeweee/ss /2www/gruss

---

30
A. Shekhovtsoy & V. Yanush
Table D.1:
List of estimators evaluated in the stochastic autoencoder experi-
ment.
Name
Details
ARM
State-of-the-art unbiased estimator [57].
(umbel(T)
estimator [29) with temperature parameter т. Straight-Throug' Alg. 1.
ST
det_ST Deterministic version of ST setting the noise 2 = during training.
identity_ST Identity ST variant described by [5].
Estimators Estimators evaluated in this experiment described in Table D.1. As detailed in Section 2, in the identity ST we still draw random samples in the forward pass like in Alg. 1 but omit the multiplication by F' Alg. is correctly instantiated for the {0, } rather than #1 encoding in all cases. For the ARM-10 correction phase and ARM-1000 ground truth estimation, the average of ARM estimates with the respective number of samples taken.
Optimizer We used Adam (31] optimizer with fixed starting learning rate Ir 0.001 in both phases of the training. When switching to the ARM-10 correction phase, we reinitialize Adam in order to reset the running averages.
Evaluation For cach bit length we save the encoder and decoder paramcter vectors Φ every 100 epochs along the ARM training trajectory. At each such first apply ARM-1000 in order to obtain
point, offline to the training, accurate estimate of the true gradient g. We then evaluate each of the I-sample estimators, including ARM itself (= ARM-1).
The next question we discuss is how to measure the estimator accuracy. Clearly, we just consider the expected local performance such as El(g g)l, unbiased estimators win regardless of their variance. This therefore not ap- propriate for measuring their utility in optimization. We evaluate three metrics tailored for comparison of biased and unbiased estimators.
Cosine Similarity This metric evaluates the expected cosine similarity, mea- suring alignment of directions:
E[ g) [[[(1)])))))
(60)
where the expectation is over all training data batches and 100 stochastic trials the estimator ğ. This metric well aligned with our theoretical analysis Sec- tion 2.1. It however does not measure how well the gradient length estimated. If the length has a high variance, this may hinder the optimization but would not be reflected by this metric.
Expected Improvement To estimate the utility of the estimator for opti- mization, we propose to measure the expected optimization improvement using

---

Reintroducing Straight-Through Methods
31
the same proximal problem objective that is used in SGD SMD to find an optimization step. Namely, let V V be the true gradient at the current point. Common SGD step is defined as
Φ+ Φ¹ + arg min ((g, AØ) + + 11
(61)
AΦ
The optimal solution is given by AΦ eg. Since instead of only an approx- imation is available to the optimizer, we allow it to use the solution áΦ -ag. where 9 is an estimator of and a one scalar parameter to adopt the step size. We then consider the expected decrease of the proxy objectives:
(g.-og)
a² 2. |
(62)
The parameter correspond to lcarning rate that be tuned adapted during learning. We set it optimistically for each estimator by minimizing the expected objective (62), which is simple quadratic function in a. One scalar a is thus estimated for one measuring point (i.e. e. for one expectation over all training batches and all 100 trials). As such, it is not overfitting to each estimator. The optimal a is given by
a = sEE (g. |
(63)
and the value of the objective for this optimal a
Eg /B(l@lI1
(64)
For the purpose of comparing estimators, - is irrelevant and the comparison can be made on the square root of (64). We obtain an equivalent metric that is the expected loss decrease normalized by the RMS of the gradients:
El /
(65)
Confer to common adaptive methods which divide the step-length exactly by the square root of rumning average of second moment of gradients, in particular Adam (applied per-coordinate there). This suggests that this metric is more tailored to measure the utility of the estimator for optimization. For brevity, we refer to (65) as expected improvement. Note also that in (65) we preserve the sign of B((g.))) and if the estimator systematically in the wrong direction, we expect measure a positive value in (65), i.e. predicting objective ascent. rather than descent.
Root Mean Squared Error It is rather common to measure the error of biased estimators as
RMSE /Ellg 9l
(66)
This metric however may be less indicative and less discriminative of the utility of the estimator for optimization. In Fig. D.1 it is seen that RMSE of ARM estimator can be rather high, especially with more latent bits, yet it performs rather well in optimization.

---

32
A. Shekhovtsoy & V. Yanush
RMSE
Fig. D.1: Root Mean Squared error of different estimators for the samne reference trajectories as Fig. 3.
D.3 Deep Stochastic Binary Networks
The verification of ST estimator in training deep neural networks with mirror descent conducted on CIFAR-10 dataset?.
Model Our deep SBN model with L binary layers is defined
wh sign(n) {h), h == 1....L x* sign(a" xb-1)) 2t), 1=1..... L.
(67a)
(67b)
where a are pre-activations, i.e. linear mappings of preceding layer states xx with weights w² Injected noises gh x* are independent for all units. The weights w in each inner layer are +1 Bernoulli with probability Fę(n). Weights in the first and last layers are real-valued. Pre-activations a consist of linear operation and batch normalization [28]:
a BN(Linear(a**11 w>)));
(68)
where Linear is a binary fully connected convolutional transform and BN has real-valued affine terms (scale, bias) enabled. In several layers also Max Pooling is applied on top. The architecture specification and illustration of the model are given in Fig. 4.
The role of the affine parameters (s, b) in BN to reintroduce the scale and bias degrees of freedom removed by the normalization [28). In our model these degrees of freedom are important as they control the strength of pre-activation relative to noise. With the sign activation, they could be indeed equivalently represented learnable bias and variance parameters of the noise since sign(x;s;+ -2) sign (z,- =b-b) assuming 8; > 0. Without the BN layer, the result of Linear(x* w²) is an integer a range that depends on the size of If the noise variance is set 1, this will lead vanishing gradients in large network. With BN and its affine transform, the right proportion can be learned, but it is important to initialize it so that the learning can make progress. We propose the following initialization. We set s; 1 and b, = 0 (as default for BN)
Initialization
https:/ htaps://wwww..o www.:cssttroooo.ccoo wtt.utttooddeeoiii///eee/ /ariiz/cifar html

---

Reintroducing Straight-Through Methods
33
and normalize the noise distribution that it has zero mean and F*(0) 2 This choice ensures that the Jacobian (a) in Line of Alg. 1 at the mean value of pre-aclivations is the identity matrix and therefore gradients do not vanish.
We want to initialize weight probabilities 0, = Fe(n) as uniform in [0, 1]. The corresponding initialization of latent weights is then 7/ = Fg (0:) (which would be completely non-obvious choice to propose empirically for deterministic ST methods).
Dataset The dataset consists of 60000 32x32 color images divided in 10 classes, 6000 images per class. There predefined training set 50000 examples and lest set of 10000 examples.
Preprocessing During training use standard augmentation for CIFAR-10 10, namely random horizontal flipping and random cropping of 32x32 region with a random padding of 0-4 px on each side.
Optimizer We use Adam optimizer [31] in all the experiments. The initial learning rate y 0.01 is used for 300 epochs and then we divide it by 10 epochs 300 and 400 and stop epoch 500. This is fixed for all models. All other Adam ppper-paraeetess such as B1, 32,8 are set to their correspondent default values in the PyTorrh [41] framework.
Training Loss Let the network softmax prediction on the input image x. with noise realizations in all layers z be denoted as v(=lz,>)) The training loss for the stochastic binary network is the expected loss under the noises:
data [E[[-
log pog2(,
(69)
The training procedure is identical how the neural networks with dropout noises trained [50]: one sample of the noise is generated alongside each ran- dom data point.
Evaluation At the test time we can either set z = 0 to obtain a deterministic binary network (denoted as 'det'.. We can also consider the network as a stochas- tic ensemble and obtain the prediction via the expected predictive distribution
Eg [x(p(a/2, x")],
(70)
approximated by several samples. In the experiments we report performance in this mode using 10 samples. We observed that increasing the number of samples further improves the accuracy only marginally. We compute the mean and stan- dard deviation for the obtained accuracy values by averaging the results over 4 different random learning trials for each experiment.


Reviews:
[{"review_id": "pf--6UYltq", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "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": "\n\t1. Summary & contributions\nThis paper analyzes a number of existing straight through (ST) estimators and connects them using a unified view as estimators for stochastic binary networks (SBNs) with Bernoulli weights. Different estimators can be seen as design choices, either relating to the model or optimization procedure. This provides insights in the specific assumptions (implicitly) made by these estimators and allows to analyze their bias and performance.\n\nThe paper proposes an extension of ST for deep SBNs to binary weights and conducts experiments to evaluate the quality of ST gradient estimates, showing that the reliability increases with the size of the (boolean) latent space for a VAE, and providing optimization results for a Deep SBN.\n\n\t2. Strengths & weaknesses\nStrengths:\n\nThis paper unifies a number of straight through estimators under a common framework which helps in motivating previously considered 'ad-hoc' rules for gradient backpropagation, and helps understanding of the conditions which may affect the bias/performance of the estimators.\n\nThe paper is technical but written in such a way that it is still relatively easy to follow, by keeping notations simple (yet clear) and deferring detailed derivations/proofs to the appendix (which I did not go through in detail). \n\nThe paper shows theoretically and experimentally that different design choices for the estimator are possible, as long as different parts (model, initialization and training) are well aligned.\n\nWeaknesses:\n\nAs a weakness, the paper feels a bit as an enumeration of related but separate contributions (summed up in the paragraph 'contributions'). The experiments mainly concern section 4 and show somewhat the effect of Bias Analysis IV), but it would improve the paper if (toy) experiments would have been conducted relating to the other analysis in section 2.2 as well, which could then justify the practical relevance of these results.\n\nWhile the paper motivates the reintroduction of ST as principled methods, the experiments give some insights but do not fully convince of the practical use of the proposed extensions.\n\nIt is positive that the paper is largely self-contained, but this makes it a bit difficult to distinguish novel derivations from recapitulations of results from previous work. Also, the paper lacks a discussion section and as a result feels a bit unfinished.\n\n\t3. Recommendation\nMy current recommendation is to accept the paper.\n\n\t4. Arguments for recommendation\nThis paper helps in the theoretical understanding and unifying view of a variety of straight through estimators, which may help advancing these estimators for training networks with binary weights and activations, which is a relevant and difficult problem.\n\n\t5. Questions to authors\n- Why is a discussion section omitted?\n- Figure 1: looking at the y-axis for the top row, it seems that both ARM and ST get worse results with 256 bits than 8 or 64 bits, which hints at underfitting. How does this affect the conclusions?\n\n\n\t6. Additional feedback\nMinor comments\n- Line 152: where does the symbol f for loss come from?\n- Line 305: a reference is missing: ??\n- Line 331,5: reminder -> remainder?\n- Line 372: ELOB -> ELBO? Or -ELBO (negative ELBO)?\n- Some grammar could be improved, e.g. in abstract 'we … obtains, …, explains'\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "Y-OrkOz4Egv", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "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: The paper presents a principled derivation and analysis of the straight-through (ST) estimator, which is often used to train networks with binary weights and activations.\n\nA strong point of the paper is that the ST estimator is often used to train networks with binary weights and activations. Hence, a more theoretical investigation can be helpful to better understand the ST estimator. Furthermore, the paper seems theoretically sound. However, my assessment is unconfident due to lacking expertise in this area. The empirical experiments confirm that the ST performance improves as the number of latent bits is increased as suggested by the theoretical analysis. Another strong point is that the paper will make code available on Github, which can improve the reproducibility of the experiments.\n\nA weak point of the paper might be its limited potential impact on future works since it mainly provides an analysis of prior empirical ST approaches. Furthermore, a substantial amount of content is only described in the supplementary material. A venue that allows longer submission may be a better fit for this work.\n\nMinor important points:\n- Missing reference in Line 305.", "extra_scores": {}, "extra_text": {}}, {"review_id": "R5awjTpq2J", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "#####################################################\n\nSummary:\nThis paper presents a systematic way of analysing straight through estimators and derive ST estimators for Stochastic Binary Networks. \n#####################################################\n\n\nPros:\n\n1. The paper is theoretically strong.\n2. The paper covers a large body of relevant work, covering theory behind straight through estimators and stochastic binary networks. \n\n\n\n#####################################################\n\n\nCons:\n1. The novelty of the paper isn't clear, if this paper is an analysis paper, the empirical evidence is weak. \n2. The paper is very hard to read, and it is difficult to understand the clear motivation. The paper is too dense while missing any key takeaway point. It misses key details in the experiment section. \n3. The utility of the proposed MD estimator is unclear,  it would be helpful if the authors would clarify the interpretation of Table 1 with their write up under \"Classification with Deep SBN\": the authors state that their method performs as well as the empirical ST, while the table shows it performs worse than their baselines. \n4. Overall, the experiment section is scattered, with hard to understand goals. For example, the takeaway from Figure 1 bottom is difficult to understand. \n\n\n#####################################################\n\n\nTypos:\nLine 305 ??\nThe paper needs major revisions in terms of notation issues: the vectors should be bold, to distinguish the from scalars.\n#####################################################\n\n\nQuestions:\nPlease address the cons mentioned above. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "3-Gu-7KGd3l", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper reintroduces the straight-through estimator with bias-variance analysis. It further discusses its relationship with some constrained optimization methods in convex optimization and \n\nIn general, the novelty of the paper on the methodology side is not high. Its value may lie in the theoretical analysis of an existing method. However, the current theoretical analysis is not clear for the following issues:\n\n- On page 3, it says \"cannot interchange the gradient and the expectation in z\". But z is a continuous variable, why it cannot?\n- There is no clear explanation of what does dL(x)/dx mean. x is discrete, so this notation without re-definition is incorrect. \n- On page 3, it is unclear what \"define now dx/da = 2F'(a)\" mean. Why should it be defined in this way?\n- On page 4 III), why g(x) is assumed to be Lipschitz continuous? \n- On page 8, eq (18), this metric seems strange since the ratio of expectation is not the expectation of ratio. And it only measures the angle between two vectors. Why the L2 norm cannot be used here?\n\nIn general, the main paper lacks formal theory statements, while the informal statement does not clearly answer the questions it comes up with.  Another major issue is the writing. The paper does not have a conclusion/discussion part which makes it incomplete. And the main paper has several missing citations/references with (??). In figure 1 caption, it is ELBO not ELOB.  With the concerns listed above, the paper in its current version looks not fully ready for publication. \n\n\n=====POST-REBUTTAL UPDATES======== \n\nThanks to the authors for the response and the efforts in the updated draft. The updated paper improves writing. The response resolves a part of the queries.  The viewer yet believes the page limits should not be a good excuse to squeeze necessary information into the appendix, otherwise, as AR2 suggests, it may be more proper for other venues.  I raised my rating according to the author's response. ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper collects a variety of results that cast straight-through estimators as arising as principled methods that make a linearization assumption on the loss for functions with binary arguments. R1 & R3 recommended against acceptance, citing clarity concerns and a lack of novelty. R2 & R4 recommended acceptance, but had low confidence. This paper had uncharacteristically low confidence on behalf of the reviewers, and this is my fault. I apologize to the authors for this. 

I have read the paper myself. I believe that this paper contains many interesting ideas, but I agree with R1 & R3 that the paper suffers from clarity issues. Unfortunately, these issues persist in the recent revisions, despite having been asked by R1 & R3 to improve the clarity. The authors asked for concrete reference points. Here are some:

- "proxy function" is not well-defined, despite being critical to the arguments.
- deterministic ST is not defined clearly before it is discussed.
-  The section structure of Sec 2 could be improved. At the moment it seems to flow from the loss function to the standard ST algorithm through to a disjointed list of questions addressed in the paper.
- The section titles are not particularly informative.
- It is difficult to know which results are known and which results are new.

In general, I believe this work could benefit from a significant restructuring. It would be best to delineate preceding work in its own section, then lay out the new results, making sure that all of the important concepts are clearly defined. I think many of these results are valuable for the community, but the current draft makes it challenging for these great ideas to reach their full potential.

Decision: Reject