Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper presents a variance reduction technique that improves the Straight-Through version of the Gumbel-Softmax estimator by taking the zero-temperature limit. The paper further shows that the proposed estimator could be decomposed into a sum of straight-through estimator and DARN. The superior performance of the proposed estimator using 1 or 2 sample(s) is demonstrated through experiments on MNIST, by comparing against an unbiased categorical estimator ARSM, and Gumbel-Rao with large number of Monte-Carlo samples. 


strength_and_weaknesses: Strength:
The paper idea is simple but sharp: inspired by the analysis of Gumbel-Rao (GR) estimator (Paulus et al., 2021) that the estimator performs better at lower temperature, they push the estimator to the zero temperature limit, and found superior performance. Another major contribution is that the paper identifies the connection between GR with Straight-Through (ST) and DARN at the zero temperature limits, for both binary and categorical cases. The insights and analysis are incremental but very important, in terms of both theoretical understanding and improving applicability of the estimator. 

Weakness:
There are some minor problems / questions:

1. Questions:
  - In Figure 1, the author compares the computational time across different estimators, is this comparison based on the numbers from different implementations, or are all the estimators implemented in the same code base? Instead of shown the comparison of time, it would be great to include a discussion about complexity analysis on each algorithms, which is not subject to the difference in the implementation and helps the readers / reviewers to better understand how the estimator scales with increasing number of categories. E.g. ARSM requires $\mathcal{O}(C^2)$ evaluations, where $C$ is number of categories.  
  - The author(s) discussed the multi-sample version, ZGR s = 2, in experiment section. How does it formulated? Taking average of two estimations from each samples?
  - Is there any analysis for scaling the number of categories? Would the relative performances of different estimators hold for larger / smaller number of categories?
  - MNIST is a standard yet simple task. It would be good to extend the analysis on other benchmarks as well, e.g. FashionMNIST and Omniglot.
  - The author(s) claimed that the bias is very small comparing to the variance, based on the bias and variance estimations at "an evaluation point" "after 100 epochs of training with ARSM". It would be nice if this analysis could be done at an early stage of the training. 
  - A side question: instead of setting the temperature to zero or a finite number, how performant is the model if one makes the temperature learnable?

2. Missing baselines:
  - Binary case: as the paper considers the binary case in 3.1. In this case, it's worth to compare against the latest unbiased gradient estimators for binary variables, ARM (Yin et al. 2019) and DisARM (Dong et al. 2020). Both are using antithetical sampling to improve REINFORCE, and DisARM is Rao-Blackwellized ARM by analytically integrating out the randomness. 

  - Categorical case: ARSM is a categorical version of ARM. However, previous research (Dong et al. 2021) found ARSM underperform simpler REINFORCE Leave-one-out (RLOO, Kool et al. 2019) baselines by significant amount with comparable number of samples. Also, Dong et al. 2021 proposed Rao-Blackwellized ARSM with binary reparameterization, further improves RLOO. 

3. Missing References and things to be fixed:
  - line below Eq (1) "It has proven efficient in practice to ..." Please add reference for this. Also the sentence should be "It has been proven ..."
 
  - Eq (2), in general, especially for VAE, as the paper considered in experiments, "x" the latent variable, therefore it is usually sampled from posterior distribution. In this case, $\mathcal{L}(x)$ will also depends on $\eta$. Correct derivation should include two terms, e.g. Dong el at. 2021 Eq (2) and relevant discussions, but the term with gradients of $\mathcal{L}(x)$ can typically be estimated with a single Monte Carlo sample and neglected from discussion. 

  - Broken sentence: line below Theorem 2: "By quadratic functions we understand quadratic functions .. with arbitraty coefficients"

  - paragraph above 4.2, "GR-MC with K = 10 or K=100 MC samples", it's better to use "M" instead of "K", as the paper used "K" for number of categories. 

  - Please try to make the main text self-contained. E.g. Eq (10) mentioned $p_Z(\eta)$, and it is the logistic density. Writing an expression for it, would help the reader to easily reproduce the results.


Reference:
  - Yin, M. and Zhou, M. (2019). ARM: Augment-REINFORCE-merge gradient for stochastic binary networks. ICLR 2029
  - Dong, Z., Mnih, A., and Tucker, G. (2020). DisARM: An antithetic gradient estimator for binary latent variables. NeurIPS 2020
  - Kool, W., van Hoof, H., and Welling, M. (2019). Buy 4 reinforce samples, get a baseline for free! Deep RL Meets Structured Prediction ICLR Workshop.
  - Dong, Z., Mnih, A., and Tucker, G. (2021). Coupled gradient estimators for discrete latent variables. NeurIPS 2021


 
clarity,_quality,_novelty_and_reproducibility: The paper is well written with minor things that are fixable. The work is solid. Even though the work is incremental on top of ST-GR, but the insights and idea are sharp and useful for the community. 
summary_of_the_review: The paper did thorough theoretical analysis on the proposed gradient estimator, with good explanation. The author(s) did good evaluations in experiment section. The reviewer thinks that the experiment section could be improved with better baselines and more analysis on different benchmarks and ablations as mentioned in "Weaknesses" section.  
I would raise the score, if the author(s) could help address some of the concerns in Weaknesses section.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper introduces a new estimator called ZGR aimed for the stable and accurate use of discrete random variables as part of approximate inference pipelines.
strength_and_weaknesses: Strengths:
  i) The studied problem is important for the probabilistic machine learning community
  ii) The paper reports comprehensive experiments that span many critical cases where such an estimator could be useful.

Weaknesses:
 i) The technical novelty is limited.
 ii) Experiment results are weak. ZGR does not appear to show an improvement over for instance ST. I understand that it outperforms the GR family, but what that family can do ST cannot is not clear from the experiments.
clarity,_quality,_novelty_and_reproducibility: The paper is written in a rather obscure and indirect language. The state of the hard is comprehensively provided but their key weaknesses and the solution strategy proposed in the paper are not clarified. As a minor point, the acronym of the main contribution of the paper ZGR is defined nowhere in the paper.
summary_of_the_review: This is a promising paper, but gives the impression of unfinished work. The proposed method is a very close variant of what already exists. The results are also not strong, although the experiments are comprehensive.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper proposes a gradient estimator for distributions over discrete variables, following in the tradition of the Gumbel-softmax estimator. In this paper, the proposed estimator is the zero-temperature limiting value of the Gumbel-Rao estimator. Interestingly, this is shown to be the same as an average of the DARN and classic Straight-Through (ST) estimator. The authors show that their proposed estimator has zero bias on quadratic objectives, and compare its performance on several downstream tasks.
strength_and_weaknesses: Strengths
+ The theoretical results are nice. It is very interesting to see that the zero-temperature limit of the GR estimator is given by such a simple combination of the DARN and ST estimator.
+ The experimental results are fairly comprehensive, and presented quite fairly, as far as it is possible to judge.
+ The bias and variance properties of the new estimator are clearly described, and illustrated in the experiments. 

Weaknesses
+ The experimental results ultimately do not clearly show superiority of the proposed ZGR estimator. For instance, across table 1 and Figure 2, the Gumbel-Rao estimator performs similarly or better than the ZGR. Similarly in figure 2, the GS-ST(t=2) strictly dominates the ZGR. The experiments do show that the ZGR is a decent enough estimator in practice, but there is still enough variation between all the different estimators that the best bet for the practitioner is to just do a hyperparameter sweep including all the available estimators.
+ Similarly to the previous point, I think there needs to be more discussion about the connection between the bias and variance of the estimator itself, and the error in the optimization process, particularly when combined in with the particular problem of training a neural network with an adaptive optimizer. As the authors point out, simply considering the MSE in the gradient is not necessarily that relevant for the actual question of how well an NN will convergence. For instance, an interesting experiment could be to train the VAE with all the different estimators, using both an adaptive optimizer and regular SGD, to see if the bias might be worse than variance as the authors hypothesise.
+ Minor points: 
  + In page 3, shouldn't the CDF of the Gumbel be $e^{-e^{-u}}$?
  + 'unique amongst single-sample categorical estimators' isn't REINFORCE unbiased? Or you need to define what you mean by single-sample estimator
  + Can you not just get in touch with people to get the MNIST dataset you need?
clarity,_quality,_novelty_and_reproducibility: Clarity
+ The paper is very clear, contextualizing the previous work in the area while accurately differentiating their own work.

Quality
+ The work is relatively high quality. There is a substantial derivation to get the low-$\tau$ behavior of the GR estimator, as well as a thorough experimental evaluation of all of the competing gradient estimators. It is pretty polished.

Novelty
+ The novelty is somewhat limited for me. At this point we have so many estimators for discrete random variables it's unclear what utility is gained by introducing another one. Without a clear argument as to why this estimator's place on the bias-variance curve is uniquely novel, this does not seem very novel overall.

Reproducibiltiy
+ I don't see any provided code, but since the estimator is so simple I can't imagine there would be concerns about reproducibility
summary_of_the_review: This paper is a nice piece of work, containing a derivation of the zero-temperature limit of the Gumbel-Rao estimator. However, the experimental comparisons don't currently justify the novelty of the work for me. As it stands, the experiments demonstrate that some gradient estimators are better than others at different tasks, and different combinations of bias and variance are useful for different tasks. This paper provides a new option on the bias-variance curve, but it's not obvious to me that this actually translates to real gains on any downstream task. 

Update after the rebuttal: 
I'm impressed by the authors' additional experiments and will raise my recommendation to 6.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper proposes Zeroed Gumbel-Rao (ZGR) stochastic gradient estimators for the discrete random variables. The authors prove that the limiting the temperature to zero in the Gumbel-Rao results in closed-from solution. They also show that the proposed ZGR estimator is in the middle of two well-known stochastic gradient estimators, namely Straight-Through estimator and DARN estimator. They argue that the proposed ZGR has merits both the low bias & variance perspective (when the temperature is less than 0.1), and the low computational complexity, based on their experimental results.

strength_and_weaknesses: The paper is theoretically grounded and the proposed ZGR surprisingly filling the gap between ST and DARN.

Error bars are missing in some tables and figures. Also, the authors did not explore various temperatures (and temperature scheduling) for the baselines, which makes unfair comparison. Finally, the experimental result in Table 1 is not very promising.

clarity,_quality,_novelty_and_reproducibility: This paper is neatly written and theoretically qualitative, and therefore has originality.

However, the source code is not available at the moment. 

Here are some questions to the authors.

- What do you think complemented ST and DARN, each other?

- In Figure 1, does temperature annealing utilized in the baselines? Or, is it just a figure from bunch of fixed temperatures?

- Same question on Figure 2. Does GS variants utilized the temperature annealing? If not, I think is unfair not to utilize the temperature annealing since it is crucial hyper-parameter is the GS variants.

- Perhaps, there is an inconsistency of temperature variable.

summary_of_the_review: I am very neutral on this paper. The work is theoretic and seems to be correct. However, the concern on the fair comparison in the experiment section needs to be resolved, since the GS variants are sensitive to the temperature tuning.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper proves the zero temperature limit of the Rao-Blackwellized Straight-Through Gumbel-Softmax Gradient Estimator exists, calculates it, proves a few interesting properties (e.g., being unbiased for quadratic loss functions), finds its relations with other estimators, and performs experiments to validate the method, called ZGR. The reviewers agreed that the theoretical part is rigorous, novel and interesting. 

However, they had some concerns regarding its practical significance of this new estimator, because of the experimental results. Specifically, the authors showed results in two areas: VAEs and quantization. In VAEs, the main takeaway was supposed to be that ZGR has similar accuracy as GR-MC, but is x2-x3.5 faster. However, as known empirically and as suggested by Figure B.2, initially it is better to use higher temperatures ("temperature annealing"). Therefore, it is not clear if how significant would be the total acceleration in this VAE case, since it seems it would be beneficial to use ZGR only late in training. The quantization experiments also do not convincingly showcase an instance where ZGR is useful (the aim of this section also seems somewhat orthogonal to the rest of the paper). 

Though not every paper should break the state-of-the-art, I believe any paper that proposes a new estimator for usage in ML should at least demonstrate convincingly one ML-related case where the estimator is clearly useful, and this was not done here. I hope the authors can correct this resubmit. 

justification_for_why_not_higher_score: The reviews were initially borderline, but after the authors' response and some discussion the overall opinions leaned to the negative, with two reviewers quite negative [3,3] because of the weaknesses mentioned above, one reviewer was marginally positive [6] and wrote "The main concern I have is just the added utility of yet another categorical gradient estimator" and did not defend the paper in the discussion, while the most positive reviewer [8] did not respond during the discussion period. 

Ultimately, as I wrote above, this paper does not have one clear case where it is shown the suggested method is practically useful overall, and therefore cannot be published in its current form.
Decision: Reject