Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The paper proposed a novel gradient estimator for categorical stochastic hidden variables, named Categorical-Antithetic REINFORCE Multi-Sample (CARMS), which is a categorical extension of ARMS (Dimitriev and Zhou, 2021). CARMS reduces the variance of LOORF (Kool et at., 2019) by the means of importance weighted sampling. Using copula, where Dirichlet copula was employed in the experiments, CARMS generates the antithetic categorical samples to reduce variance. The paper compares two versions of the estimator, using inverse CDF sampling and Gumbel max sampling, against UNORD, LOORF and ARSM for categorical VAE and structured prediction tasks on Dynamic MNIST, Fashion MNIST and Omniglot. They find slightly better results compared to other estimators on both tasks.
main_review: ### Originality: 
There are a variety of approaches proposed in the past few years for unbiased gradient estimators over binary stochastic hidden variables. The paper introduces a natural extension for one of previously proposed estimators, ARMS, to categorical variables. Background and related works are adequately cited. 
### Quality: 
The authors did a great job in derivation of the estimators, design and implementation of the experiments. By closely checking the details, the methods are well-grounded. 
### Clarity: 
The paper, especially the method section, is clearly written and well explained. 
### Significance: 
The method proposed can be directly applied to interpretable models and modeling natural systems with discrete variables, e.g. sparse computing.  

## Typos and potential places to improve: 
* Ln 95, which both -> both of which
* Ln 148, adding a definition of Z^{-d}
* Eq 7, for l_i^o, the upper limit for the summation should be i-1, instead of j-1
* Figure 1, how many samples are used for estimating the correlation matrix? Also, how to interpret the numbers on two-axis of the matrices, as z[i] and z[j] should be categorical variables?
* Ln 198, “For CARMS-G, we clip the empirical ratio values to avoid numerical instabilities.” It is a bit unclear to me: 1. What is “the empirical ratio values”? Is it the sampled value for the ratio tensor R? 2. How did you clip it? E.g. clipping range, etc. I didn’t find the relevant information in either the main text or the appendix.
* In Figure 2 and 3, there are labels of “CARMS” and “ECARMS”, while in other places of the paper, the proposed methods are mentioned as CARMS-I and CARMS-G. Which CARMS-? Is “CARMS” referring to, and what does “ECARMS” stand for? 

## Questions:
* In Ln 199 of the Experiment results section, it mentioned that the Dirichlet copula is used for the experiments? I am wondering whether there are results by trying Gaussian copula. To my limited knowledge, I find the Dirichlet copula introduces a limited dependence structure, while the Gaussian copula seems more flexible. Is there any insight into which copula to choose?
* In Ln 234 of the Categorical VAE section, it was mentioned that “an individual run took 5-8 hours” and it was on CPUs. This is surprisingly fast. Based on the description follows, it seems this holds for all estimators in Table 2 other than UNORD with C=10. Does this speed number also hold for ARSM? Also, in Line 245, it mentioned the number of evaluations is limited to 2C for ARSM, but in the original ARSM paper, it requires C(C-1)/2 evaluations for the swapping matrix. How does it (using 2C evaluations rather than the C(C-1)/2) impact the performance of ARSM as a baseline?
* The experiments show that CARMS-I/G “result in slightly higher log likelihood than other methods”. Is there any insight or result for the case when the number of categories is growing larger? It is common to have a model with C >> 10. I am curious, when C grows larger, shall I expect to see a larger gap between LOORF and CARMS or smaller?
* Eq 5 introduces a very general form of couplings of categorical variables p(z, z’). In Figure 1, the author compares correlation matrices of 5 different couplings. It seems inverse CDF sampling and Gumbel max sampling favor quite different sets of joint samples. Is there any insight on what kind of correlation structure is better? 
* Based on the results, it seems LOORF is almost as good as the estimators using coupled samples. Does it mean that using the independent samples is good enough? Or putting the question in another way, in what situation, shall we expect a big improvement by using coupled samples?


limitations_and_societal_impact: The authors adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: **Summary**
- The paper introduces a multi-sample gradient estimator for categorical variables. 
- The estimator is based on the score-function and uses correlated samples to achieve a variance reduction. 
- The estimator extends several recently proposed estimators naturally. 
- The estimator yields marginal improvements over baselines in the experimental evaluations. 

**Edit after Author Response**
- Thank you for replying to the points I raised. I think the changes you do improve the draft. However, because I find the experimental improvements fairly marginal, I have kept my score unchanged. I believe the paper is above the acceptance threshold.
main_review: **Strengths**
- Originality. The contribution is a natural extension of existing work. 
- Quality. To me, the contribution appears technically sound. The derivations and arguments are clear.  
- Clarity. The paper is well-written. I enjoyed reading it and was able to follow the line of argument and the derivations. 
- Significance. Gradient estimator for categorical distributions has wide-spread applications and draws interest from the community.

**Weaknesses**
- Quality/ Significance The improvements demonstrated in the experimental evaluation are marginal.

**Decision**
- Weak Accept. I think the paper is above the acceptance threshold, but I wished the experimental results were more convincing. 

**Suggestions**

*Are duplicate samples really a significant issue?*
- Based on the paper, I suppose that the benefit of using this estimator instead of LOORF are most significant, when the duplicate sampling issue is acute. Based on the experiments presented, I am not convinced that duplicate samples are a significant issue in most practical applications. 
- I would recommend to the authors to seek applications where the duplicate sampling issue is more acute to clearly demonstrate the utility of their estimator. Speculative: Maybe, as models converge, the entropy of the latent distributions shrinks. If this is the case, one could consider an experiment, where the estimators are used for fine-tuning a model which has been trained for significantly more iterations than the models presented in 4.2 (10^6 iterations).  

*I am concerned about the statistical significance of the improvements.*
- The improvements appear very marginal, and I am not sure what the bolding scheme is indicating. Is this based on the standard errors, shout it actually be based on confidence intervals? I am unsure. 
- Rather than bolding, would it be possible to carry out a hypothesis test (t-test) to test whether the means of the proposed method are significantly different from the baselines? 

*Isn't it better to tune hyper-parameters exhaustively for each method separately?*
- I believe it is better to tune hyper-parameters individually for each method rather than choosing a fixed set of hyper-parameters on which all methods are compared against (which is what I understand, the paper did). 
-It may be acceptable in this case though, because all methods are fairly similar anyway, and the optimal hyper-parameters might be similar/ the same as a result. 

*What is ecarms in the plots?*
- The experimental set-up promised Carms-I and Carms-G. Maybe, I missed it, though. 

*There is more related work on Rao-Blackwellization for gradient estimation for discrete distributions.*
- The authors survey related work on Rao-Blackwellization to improve gradient estimation, e.g. Titsias and Lazaro-Gredilla (2015) and Dong et al. (2021).  Rao-Blackwellization is increasngly being used for improving gradient estimators for discrete distributions and I think it's worth highlighting also other work in this area, e.g. Liu et al. (2018), Kool et al. (2020) or Paulus et al. (2021). 

**References**
- Liu et al. (2018). Rao-Blackwellized stochastic gradients for disccrete distributions. 
- Kool et al. (2020) Estimating gradients for discrete random variables by sampling without replacement. 
- Paulus et al. (2021). Rao-Blackwellizng the Straight-Through Gumbel-Softmax estimator. 
limitations_and_societal_impact: N/A.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper proposes a categorical version of ARMS, namely CARMS.
By utilizing REINFORCE together with copula sampling, CARMS remains an unbiased estimator and non-duplicated samples reduce the variance of gradients.
The authors verify the proposed model through toy example, VAE, and the structured output prediction task.

main_review: Originality:
I do not think the natural extension from the previous idea harms the originality or the novelty of the paper "in general".
However, in this case, since CARMS is an extension of ARMS over the number of categories, I think the paper also needs to focus on the obstacle which follows from the natural extension which is discussed in the significance part.
Therefore, I will suspend the judgment on the originality until the authors' response.


Quality and Clarity:
The paper is grounded by theorems and the proofs are provided in the appendix.
It will be helpful for readers if the authors add a minimum introduction on the copula in the background section.
Also, the paper is written in a clear manner.


Significance:
- While the binary version (ARMS) may not suffer from the complexity, it can be a huge drawback for the proposed CARMS when the number of categories grows. However, there is no specific discussion about the complexity, nor the report on the running time in the experimental section. ARMS is a good estimator for the binary variable, however, CARMS, which is the natural extension of ARMS, seems that it needs to break through the complexity issue. Also, the performance gap is too marginal even though the proposed theorems are grounded. If the complexity really matters, why not use the comparable baselines? (which are simple and powerful) Or, CARMS needs to find a suitable application that CARMS outperforms other baselines with meaningful performance gaps.
- There are some missing baselines: RELAX, REBAR, etc.
- As a minor comment, the code is not available for reproducibility.


Questions:
- What does ECRAMS stand for?
- How does the experimental result change for the toy example if we sample the probabilities from Dir(\alpha) \alpha << 1? I'm wondering about the behavior of the proposed and baseline methods when the probability is extreme.
- Similarly, how does the performance change for the non-trivial or extreme prior in the VAE case?
- The complexity seems problematic. What is the exact computational complexity, and how does the complexity changes from ARMS to CARMS? (if there are the same number of latent dimensions) Also, could you compare the running times of the experiments? How does the running time change as the number of categories grows, for examples, C = 100, 200?

limitations_and_societal_impact: The authors pointed out the limitation, the complexity, of their work in one line in the conclusion.
However, my thought is that the complexity is somewhat crucial to the proposed method as the number of categories grows so that it should be dealt with in a separate subsection.
Meanwhile, the work seems that it does not have any potential negative societal impact.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper tackles the problem of differentiating expectations of discrete random variables. Specifically, this paper proposes a generalization of the recent ARMS approach to more than two categories. The CARMS gradient estimator uses multiple samples from a categorical distribution. Unlike e.g. LOORF, CARMS uses samples that are dependent (typically negatively correlated), hoping to further reduce estimator variance. The authors prove how to construct an unbiased gradient from these dependent samples using importance sampling. The authors propose several joint distributions (copulas) to actually generate such dependent samples. Experimental results are provided on several problems such as a categorical latent VAE. 
main_review: Novelty: This work constitutes a natural extension of ARMS. To the best of my knowledge, this exact approach has not appeared before in the literature. This paper does a very good job of summarizing recent connected work in the field (Sections 1 and 2).

Quality: The core concept (Theorem 1) is well built up to and well explained. It’s clear where the estimator comes from and why it’s unbiased (from the preceding few lines). The approach and maths follows naturally from ARMS. Theorem 2 adds justification for the CARMS approach, the variance can be provably lower. 

One thing that could make the paper better is a more thorough discussion of how to generate antithetic categorical variables (Sec 3.2), because this is more involved than in the 2-category case.
- I would like more details on the random reordering and the statement “Unfortunately, keeping to one specific ordering does not allow for all possible pairs to have non-zero probabilities”. It’s not clear to me why we cannot have distributions on [0,1]^2 which have positive density across the entire square, have uniform marginals and are not independent. Such a pair of variables, when discretized as per (8) would surely assign positive probability to every pair. Going further, can’t we transform the u, u’ distribution under a reordering by suitably shuffling the joint density between the different sub-rectangles of [0,1]^2? (Maybe this is something obvious that I missed, but it would be nice to have an explanation).
- How restrictive / how general is the inverse CDF method with uniforms? Is it possible that there exist more “natural” joint distributions for N dependent samples of a categorical?
- Is it clear why the Gumbel max approach seems to give more strongly negatively correlated samples than the Inverse CDF method? Or is this an artifact of the estimation of the joint distribution of the Gumbel method?

For both ARMS and CARMS, the benefit of antithetic sampling decreases as we add more samples. Does this decay happen more slowly for CARMS? For example, with a uniform categorical on C items we can make a coupling with N=C samples (e.g. by cycling one sample) that guarantees z_i != z_j. Discussion on this point might further add to the paper.

For the experiments, I think it’s good to consider a fair range of baselines, which the authors appear to have done. The results are not strong improvements over existing methods, but they do offer marginal improvements in most cases. The presentation of Fig 3 could be improved because it is impossible to visually disentangle most of the methods.

The computational complexity is mentioned in the discussion, but it could be worth explicitly quantifying it, e.g. in Sec 3.1 to mathematically explain the benefit of only using N evaluations of f we could write out the total cost of a gradient step of CARMS and compare to LOORF. This could also aid a theoretical comparison with UNORD and ARSM, as the intro suggests both are costlier than CARMS.

Clarity: the paper is mostly clear. Particularly earlier sections. I have made a few suggestions / queries about Sections 3.1 and 3.2 which would also benefit clarity. Overall, I find the exposition to be clear and helpful.

Significance: this paper touches on an interesting and relevant area of ML research: differentiating through categorical random variables. It forms a natural step in the logical progression of previous ideas (ARMS) and would therefore be a welcome and valuable component of the literature in this area. The fact that CARMS gets (slightly) better empirical results that previous methods also indicates that it can transfer to the practical setting well. On the other hand, the paper is natural next step with modest empirical improvements, rather than a seminal work.

Explanation of score
----------------------
I was torn between Accept and Weak Accept. Whilst I enjoyed reading the paper, the paper makes a modest step from ARMS, and has modest empirical results. It is great to have a more technically focused paper, but with that in mind, I think a bit more detail in Secs 3.1 and 3.2 would step things up to Accept for me.

Typos
-------
135: errant full stop

(7) : l_i^{(o)} should sum to i-1 not j-1

limitations_and_societal_impact: The authors have adequately addressed limitations and societal impact. For more details, see the main review.
review_title: null

Meta-review: The submission proposes a low-variance gradient estimator for discrete random variables, extending recent work on binary to categorical. Whilst the reviewers raised concerns around the marginal improvement over existing methods, all agreed that the submission is clearly written and is a theoretically grounded, novel extension of ARMS. Overall, this is a good contribution to NeurIPS and should be accepted.
Decision: Accept (Poster)