Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: Summary:
The authors analyze the bias in the straight-through gradient estimator using the framework of harmonic analysis of boolean functions. Based on this analysis, they propose three methods to reduce the bias of the straight-through estimator, resulting in a less-biased estimator that is the same computational complexity as the original. They evaluate this estimator on a series of generative modeling tasks where they demonstrate improvements over existing methods, including the ability to train a very deep stochastic network.

I enjoyed this paper -- the exposition is clear, the ideas are (to my knowledge) novel and make sense, and the experimental evaluation is thorough and convincing. I recommend an accept. 

I skimmed through the proofs in the appendix so cannot with absolute confidence vouch for their correctness.

One small piece of feedback: I found the most confusing part of the paper was the section on the 'bernoulli splitting trick'. It might be helpful to pull some of the appendix material into this section to make it a little less sparse.

review_title: Official Blind Review #1

final_score: rating: 3: Weak Reject
review_content: ------------- updated after rebuttal -------------------

I thank the authors for clarifying and correcting the notations in Lemma 3. Though I still think the current state of the derivation is presented in a suboptimal way, and as a result, can be misleading to people.

The Fourier analysis used to give the results that the exact gradient equals $2\hat{f}^{(p\to 1/2)}(i)$ (eq. 5) is totally unnecessary: Despite it might seem fancy as a Fourier coefficient, it is just another way of writing the local expectation estimator (Tokui, S., & Sato, I., 2017), if we expand it using the definition $\hat{f}^{(p)}(S) = E_{p(z)}[f(z)\phi_S(z)]$.

The authors argue that the Fourier analysis is essential to show the bias of the estimator. However, the only conclusion they draw from Fourier analysis is eq.5. And all the bias analysis follows by using Taylor expansions of it. The paper can be greatly simplified if they remove all boolean analysis parts and start from eq. 5 (which has a straightforward proof), using the conventional notation instead of Fourier coefficients. 

During writing this, I read the bias correction section again and had another concern, the bias correction effect is only justified for functions with small mixed degree terms:

"For functions with small mixed degree terms, this can lead to bias
reduction, at the cost of an increased variance because of sampling an auxiliary variable"

For general multivariate functions, it is even not clear whether the proposed estimator has a smaller bias than the straight-through one. This weakness has a deep reason behind it because they are trying to generalize a bias reduction technique from a univariate function to multivariate functions, which, if done natively, would require K evaluations of the function (K is the number of input dimensions) (as I pointed out in the original review).

Overall, I argue rejecting the paper in its current form.

----------------------------------------------------------------

This is not my first time reviewing this paper. Previous concerns on clarity has been addressed and the paper is now more readable. Though I still believe that the boolean analysis part is unnecessary for deriving the final estimator (which can be easily derived from the exact local-expectation estimator E_p[f(z_i=1) - f(z_i=0)] and applying f(1) - f(0) = \int_0^1 f'(x) dx \approx f(e), e~Unif[0,1].) plus some importance sampling trick.

I think the proof of Lemma 3 is incorrect (though the conclusion is correct). f is never multi-linear in the continuous space. It is only for the boolean space, that f has an multi-linear form with Fourier expansion. So the claim that f is multi-linear then

E_{p(z}}[f(z_1, ..., z_n)] = f(\mu_1, ..., \mu_n)

is incorrect. This can only be true when f is also linear in the continuous space (which is not true for typical vaes).


review_title: Official Blind Review #3

final_score: rating: 6: Weak Accept
review_content: ***Score updated to weak accept after the rebuttal.***

Straight-Through is a popular, yet not theoretically well-understood, biased gradient estimator for Bernoulli random variables. The low variance of this estimator makes it a highly useful tool for training large-scale models with binary latents. However, the bias of this estimator may cause divergence in training, which is a significant practical issue. The paper develops a Fourier analysis of the Straight-Through estimator and provides an expression for the bias of the estimator in terms of the Fourier coefficients of the considered function. Motivated by this expression, the paper proposes two modifications of Straight-Through which may reduce the bias of the estimator, at the cost of the variance. The experimental results show advantage of this improved estimator over Gumbel-Softmax and DARN estimator.

While I really like the premise of the paper, I feel that it needs a significant amount of additional work. The text is currently fairly hard to read. The theoretical part of the paper does not quantify the variance of the estimator. The experiments are a bit unfinished and do not include ablations of the proposed modifications of Straight-Through. Most importantly, I think that in the current form the theoretical and the empirical parts of the papers are not well-connected. Because of this, I believe that the paper should currently be rejected, but I encourage the authors to continue this line of work.

Pros:
1. Theoretical analysis and empirical improvement of the Straight-Through estimator is an important avenue of work.
2. The paper makes a solid contribution of deriving the Fourier expansion of the Straight-Through estimator bias.
3. Based on this expansion, the paper proposes an algorithm with reduced bias. The algorithm is simple to implement, practical and appears to work slightly better than DARN.

Cons:
1. The key weakness of the theoretical part of the paper is that it focuses on the bias of the estimator, but does not quantify the variance, especially after the modifications. If reducing the bias was the only goal, one could use unbiased (but high-variance) estimators such as REINFORCE or VIMCO.
2. The final algorithm appears to be the DARN estimator combined with relaxation by uniform noise (“Bernoulli splitting uniform”) and scaling. The paper does not have an ablation showing how the uniform noise and scaling perform on their own.
3. There are a few incorrect statements that I’ve noticed.
* “As a side contribution, we show that the gradient estimator employed with DARN (Gregor et al., 2013), originally proposed for autoregressive models, is a strong baseline for gradient estimation.” - MuProp paper compared to this estimator under the name 1/2-estimator
* In Lemma 1 the “REINFORCE gradient” is just the exact gradient of the expectation, not a stochastic REINFORCE gradient.
* “ To the best of our knowledge, FouST is the first gradient estimate algorithm that can train very deep stochastic neural networks with Boolean latent variables.” This paper uses up to 11 latent variable layers, while [1] has trained models with >20 latent variable layers (although their “layers” have just one unit).
4. The derivation of “Bernoulli splitting uniform” trick is confusing and contains a lot of typos. For instance, the text before eqn. (14) implies that the distribution of u_i is U[-1, 1], which cannot be right and does not correspond to Algorithm 1. The statement that this trick does not lead to a relaxation is odd, since the function is being evaluated at non-discrete points.
5. There are generally many typos and some poor formatting in the math. For example, in eqn. (6) the coefficients are off by one: it should be c0 + c1 z1 + c2 z2^2 + … . The equations (10) and (11) are poorly formatted. The notation \partial_z1 f(u_1, u_2) in eqn. (14) is strange. In many places p^{i->½} is denoted as p^{1->½}.
5. I don’t think I understood the idea of representation scaling (Section 4.4). The eqn. (16) would suggest that the scaling should optimally be set to zero, which is just saying that the gradient is unbiased when the model does not use the latents. There is no other practical guidance on choosing this coefficient. Furthermore, one can always absorb the global scaling factor into the succeeding weights layer of the model, so this trick can probably be replaced by a modification of the weights initialization.
6. The experiments are missing a comparison to the Straight-Through Gumbel-Softmax estimator, introduced in the original Gumbel-Softmax paper. This is a popular biased estimator for Bernoulli latents, e.g. used in [1] [2]. Another interesting comparison would be [3] which proposes a lower-bias version of Gumbel-Softmax.
7. Figure 2 is missing the line for REBAR, even though this line is referred to on Page 8. Figure 2 and Figure 4 are both labeled as training ELBOs, despite the plots being different.

[1] Andreas Veit, Serge Belongie “Convolutional Networks with Adaptive Inference Graphs” ECCV 2018
[2] Patrick Chen, Si Si, Sanjiv Kumar, Yang Li, Cho-Jui Hsieh “Learning to Screen for Fast Softmax Inference on Large Vocabulary Neural Networks” ICLR 2019 https://openreview.net/forum?id=ByeMB3Act7
[3] Evgeny Andriyash, Arash Vahdat, Bill Macready “Improved Gradient-Based Optimization Over Discrete Distributions” https://arxiv.org/abs/1810.00116
review_title: Official Blind Review #2

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

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