Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: Summary: This paper introduces an gradient estimator for loss functions that are expectations over discrete random variables. The basic idea is that an estimator over a discrete distribution can be Rao-Blackwellized by conditioning on the event that the discrete realization was produced by being the first sample drawn from an unordered set of samples drawn with replacement. Much of the paper is spent showing how this Rao-Blackwellized estimator can be computed in practice and how it compares to other known estimators.

Originality: This idea is original and quite nice.

Clarity: The paper is very easy to understand and well-written.

Quality:
- The derivations are all correct from what I can tell, and easy to read.
- The experiments are all reasonably well done, but I could not find where the authors report which optimizer was used and how the hyperparameters were set. If I missed it, could the authors point that out in the rebuttal? If it is missing, then I strongly suggest that the authors include that in the paper. Even if the training protocol is taken from another code base, I think this paper should be reasonably self-contained. How the hyperparameters are tuned and which optimizer was used could affect the interpretation of the results. Additionally, if overfitting is an issue, I recommend the authors consider the use of regularizers, like weight decay. I see no reason that this would violate the spirit of the paper, and might make their results more compelling.

Significance: 
-This paper has some interesting ideas, and it is written well. So, it may inspire future work. Yet, from the experiments it is not obvious that this estimator adds much to the existing literature. In all experiments at least one known estimator matches the performance of the unordered set estimator. 
- All of these estimators, which require multiple evaluations of the gradient, are generally less common in practice. 
review_title: Official Blind Review #1

final_score: rating: 6: Weak Accept
review_content: Summary: In this paper, an unbiased estimator for expectations over discrete random variables is developed based on a sampling-without-replacement strategy. The proposed estimator is shown to be a Rao-Blackwellization of three existing unbiased estimators with guaranteed reduction in estimation variance. The connections of the method to other gradient estimators are discussed. Experimental results on several toy and real-data DL/RL problems are reported to demonstrate the applicability of the proposed estimators in the practice of machine learning. 

Strong points:

-S1. The addressed topic is interesting and timely in deep/reinforcement learning.

-S2. The numerical results show some promise of the proposed estimator in reducing the gradient estimation variance in practice.  

Weak points:

-W1. A formal and detailed problem statement is missing. The paper quickly jumps from a high-level problem setup description in the introduction section into some technical details in the preliminary & methodology sections, without any formal definition of the so called unordered set policy gradient estimation problem provided. What is the input/output of the estimator? Why this problem is important and challenging? It will be better to provide one or two concrete examples such as those studied in the experiments to give a more complete picture of the problem in study. 

-W2. The motivation of study is not clearly elaborated. There are several existing options to reduce the gradient estimation variance via Rao-Blackwellization [see, e.g., Liu et al. 2019]. In which regimes the current method is more preferable than those prior ones and why? The justification of using the without-replacement-sampling strategy so far remains largely unconvincing. 

-W3. The overall novelty of theory is limited. It makes sense that gradient estimators based a mini-batch of sample under without-replacement-sampling should tend to have smaller variance than the single-sample stochastic gradient estimation. Although a guarantee of variance reduction from the perspective of Rao-Blackwellization looks promising, the proof technique is fairly standard and more importantly, the quantification of such a variance reduction remains largely unaddressed. Therefore, the overall degree of novelty in theory is still relatively low. 

-W4. The paper presentation quality can be improved. As another consequence of the above mentioned issues with problem statement and motivation, I found the paper a bit hard to follow smoothly. Particularly, too much space is spent on presenting the technical details while the principles/intuitions behind these fancy mathematical treatments are lacking in explanation. There are three theorems established in the paper, but none of them come up with sufficient discussions on the main messages conveyed by these results. 

=== update after author response ===

Thank you for your response. I find my concerns on motivation and presentation properly addressed in the feedback and the revised paper as well.  Concerning the strength of theory, however, I am still not convinced that the current analysis is strong enough to thoroughly justify the benefit of the proposed estimator. All in all, the paper is substantially improved in presentation and the proposed gradient estimator seems to be a novel and more attractive alternative to the existing ones in a number of popular DL/RL applications. I thus would like to increase the rating to weak accept.

review_title: Official Blind Review #2

final_score: rating: 8: Accept
review_content: Edited after rebuttal:
I'm satisfied with the clarifications provided by the authors about where they see this work being applicable. I think they have correctly identified a setting that is of interest to a broad audience and where their approach is more attractive than the alternatives. I now recommend accepting this paper.

The authors develop a generic method for estimating expectations under discrete distributions based on sampling without replacement and apply it to the task of estimating gradients for training models with discrete latent variables. The proposed estimator is unbiased and the authors prove it has lower variance than the naive Monte Carlo estimator.

I weakly recommend rejecting the paper. While the derivations and theorems presented in the paper are correct, the experiments are sensible and support the claims made, my impression is that the range of applications where the proposed method is a better alternative to the existing algorithms is extremely narrow. I would be willing to raise my rating to Weak Accept if the authors convince me that their method is useful more broadly than I think it is.

The method derivation is generally well-written and easy to follow. However, the account of the sum-and-sample estimator is somewhat misleading. As is, it suggests that it is natural to sum over k-1 elements and only draw one sample, while in fact choosing how many elements to sum over (I'll call this number S in my review) and how many samples to draw from the remaining set is the crucial step needed to make this algorithm work well. This is discussed by Fearnhead and Clifford [1] in the context of resampling in particle filters and I believe is also addressed by Liu et al. (2019). I understand that the authors are guiding the presentation towards a version of sum-and-sample they can compare with in theory and in experiments, but in the process they're doing a disservice to the reader. I think the authors should state the importance of choosing S well early on and then either compare with methods that attempt to set S optimally throughout experiments, or clearly explain that they restrict their discussion to a particular setting where S is difficult to optimize and explain why.

There are also additional baselines that should be considered. This includes methods such as stratified or systematic sampling, which are often discussed within the context of resampling [2]. Another strong but somewhat obscure baseline is given by Duffield et al. [3]. While it is possible that none of those methods are applicable in the experimental setting chosen in the paper, the authors should be very clear about how broadly they claim superiority of their method.

On the topic of experimental evaluation, the authors seem to have focused on the setting where sampling is done using stochastic beam search, presumably because in such a setting some of the strong baselines mentioned above, including sum-and-sample with the optimal choice of S, are not applicable. If that's true, I would like to see a detailed discussion about what it is about the problem setting that makes alternative baselines inapplicable. My current impression is that the proposed method is only worth considering when used with a stochastic beam search and I don't think such settings are particularly common. This is my main complaint about the paper.

On the subject of applicability, the experiments only test the proposed method in very low k settings, where the exponential algorithm for computing the leave-one-out ratio can be applied. While the appendix mentions that there is a faster alternative based on numerical integration, the claim that it can be efficiently integrated is not substantiated anywhere.

The plots could use some improvement. It took me a lot of squinting at Figures 2 and 3 to figure out what's going on, since the lines overlap too much - I couldn't even find the Unordered line in Figure 2 at first. Also I'm confused about why lines for sum-and-sample in Figure 1 extend beyond 8 evaluations, and VIMCO does not. Also figure captions could be a little more self-contained.

Finally, I would recommend stating Theorem 1 in more concrete terms, such as "estimator A has lower variance than estimator B".

[1] P. Fearnhead and P. Clifford. On-line inference for hidden Markov models via particle filters. Journal of the Royal Statistical Society, 65:887–899, 2003.
[2] R. Douc, O. Cappé, and E. Moulines. Comparison of resampling schemes for particle filtering. In ISPA, 2005.
[3] N. Duffield, C. Lund, and M. Thorup. Priority sampling for estimation of arbitrary subset sums. Journal of the ACM, 54, 2007.
review_title: Official Blind Review #3

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

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

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


Decision: Accept (Spotlight)