Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper introduces a control variate scheme for REINFORCE-type estimators based on the Stein operators for discrete distributions. Discrete Stein operators generate zero-mean functions under the discrete sampling distribution; therefore, they can be used to construct control variates if a suitable function is chosen. Based on this insight, the authors propose RODEO, a CV scheme based on discrete Stein operators for the REINFORCE leave-one-out (RLOO) estimator. RODEO contains to adaptive function $H$ and $H^*$ that are optimised by minimising the variance of the estimator. RODEO is validated on binary VAE models and is shown to be effective in reducing the variance and inducing faster convergence.
strengths_and_weaknesses: To the best of my knowledge, the use of Stein operators in gradient estimation in discrete settings is novel. The authors attempt to place their work within the literature, and they make a sufficient argument for the originality of their contribution.

The development and explanation of the methodology is very clear, even for someone who is not previously familiar with Stein operators. That being said, I found the build-up leadin to equation (14) somewhat confusing. How does a Markov chain generate i.i.d samples? This section is important for developing the estimator, so I think the authors should improve the clarity of this derivation (or expand it in the appendix).

Overall, I think this is a good paper. There are no major concerns with regards to the motivation and the development of the idea. The empirical evaluation can be improved by further comparisons. e.g. vanilla RLOO with different number of samples, and an illustration of the limitation of this method when the number of samples increases (this point was acknowledged in the conclusion). It is lacking a discussion of the practicality of this estimator given its complexity.

In my assessment, the main strengths of this work are its originality and clarity in the motivation and the development of the methodology, as well as its potential impact on future research. Its main weaknesses are the limited evaluation and discussion on its practicality.

questions: * What is the wall-clock time performance of this method compared to RLOO? I am especially interested in comparing its wall-clock performance compared to simply increasing the number of samples in RLOO. I know that this is dependent on the architecture of $H$ and $H^*$, but it is good to have some indication to its practical feasibility.
* Can this type of estimator benefit from a parallel architecture? For instance, running the model on one GPU and $H$ and $H^*$ on another? $H$ and $H^*$ seem to take $f$ and its gradients as inputs, so this might be challenging at a first glance. Can the authors comment on this point?
* When is it practically feasible to use this estimator? Are the extra implementation and computation overheads worth it compared to simply increasing the number of MC samples in RLOO or even vanilla REINFORCE? I think it good to add a discussion of its practicality to final section.
* What is the effect of the architecture of $H$ and $H^*$ on the variance reduction? Is bigger always better? And is there any trade-off in terms of computation vs variance reduction?
limitations: Some limitations of this work are addressed in the conclusion and their discussion was, in my opinion, sufficient. There is no potential negative societal impact in my assessment.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: In this work, the authors propose a new type of control variate (CV) for discrete distributions. The proposed method is based on Stein operators. 
The authors further incorporate the double CV into this proposed framework. 
Experiments are shown to support the claim. 
strengths_and_weaknesses: Strengths:
* 1 A new type of control variate (CV) for discrete distributions.
* 2 The proposed method is sound.
* 3 The proposed method can be used to train deep NNs. 
* 4 Many empirical results are given to support the claim.

Weaknesses:
* 1 Discuss whether the proposed method can be applied to a discrete distribution with infinite support such as a Poisson distribution.
* 2 The authors should discuss the iteration cost (computational budge) of the proposed method. It will be great if the authors discuss the iteration cost of all related methods including baseline methods.
* 3 The running time instead of the number of training steps should be included in at least one of the plots.
 
questions: See the weaknesses section.
limitations: N/A
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper studies the design of control variates for REINFORCE-type gradient estimators in discrete expectation optimization problems. The paper proposes a general class of control variates using discrete Stein operators, and a practical unbiased gradient estimator RODEO with Stein-inspired control variates. Experiments on Bernoulli VAEs show the proposed method achieves lower gradient variance and better performance compared to a variety of baselines. 
strengths_and_weaknesses: Strengths:

- The paper is well-written and gives a clear introduction to previous variance reduction methodologies of relevance. 
- The theory is well-substantiated and well-explained. The simplifications made in (14) and (16) are justified, and the intuition that $h$ serves as a surrogate for $f$ is clearly built by relating to Rao-Blackwellization. 
- A number of Stein operators are cited, with practical guidelines for choosing suitable operators based on numerical stability. 
- Experiment results are comprehensive and inclusive of the best introduced baseline methods. The comparisons are performed fairly under similar computational costs, and the slightly increased cost for RODEO due to evaluating auxiliary functions is clearly highlighted and justified. Ablation studies clearly demonstrate the effect of different components of the proposed method. 

Weaknesses:

- While the proposed methodology is original and novel, similar ideas based on Stein’s methods exist for REINFORCE-type gradients of continuous distributions and as general control variates for evaluating expectations. Nonetheless, this has been clearly detailed in the related works section. 
- The method is evaluated only using VAE with binary latents, which has similar problem structure across different experiments, and may or may not favor the proposed methodology. In particular, the binary state space is relatively simplistic, albeit in a relatively high dimension of 200. 

questions: There are no major questions the reviewer would like to raise. There are 2 minor questions of interest:

- Equation (14) is built under the intuition of an “optimal” Markov chain, but in practice the Markov chain is clearly not optimal with limited transition neighborhood especially in high dimensions. In the latter case, it would be helpful to analyze its implications for (14). Alternatively, it would be helpful to study the amount of variance reduction given by Rao-Blackwellization when $h=f$ exactly as dimension increases?
- On page 7, it is mentioned that “RELAX was often observed to have very strong performance in prior work”. Why is it comparatively worse than all baselines in this paper?

limitations: The authors adequately addressed the limitations of their work and proposed interesting future directions of study. The authors did not discuss any potential negative societal impacts of the work, but as the work is mostly theoretical it is unlikely to have immediate negative societal impacts.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper introduces discrete Stein operators for gradient estimation applied to Bernoulli variational autoencoders. As is widely known, gradients play a crucial role in training machine learning algorithms and taking gradients with respect to a discrete variable is non-trivial. Existing approaches tend to produce gradients with a high variance which then requires control variate approaches to manage the variance of the gradient. In this paper, the authors address this problem with a variance reduction technique based on Stein operators for discrete distributions. 

The authors test the efficacy of their approach on three variations of the binary latent variable VAE. In the experiments, the authors show that their discrete Stein operator is competitive with existing state-of-the-art approaches. 
strengths_and_weaknesses: Originality - The paper proposes a new approach to variance-reduced gradient estimation for discrete variables using Stein operators. As far as I am aware, this is a novel contribution to the research area. A potential weakness in terms of originality is perhaps that the main benefit of this approach, in terms of its efficiency, is likely to stem from the variance-reduction aspect, which is based on the reinforce leave-one-out (RLOO) estimator and a critical perspective might suggest that this paper is taking RLOO and plugging it into a Stein operator, which may reduce the novelty slightly. 
Quality - The paper is of high quality and well-placed in the NeurIPS community. 
Clarity - The paper is very well written and the methodology is clearly presented. There are no obvious weaknesses in the presentation that the authors could aim to improve. 
Significance - The paper nicely addresses the existing literature in the field which helps to place this work in the wider field. The problem addressed in the paper is significant in the ML community and the contribution of this paper is significant for both its contribution to latent variable VAEs and Stein method. In theory, the paper could be applied to general discrete variables, but in the paper, only VAE-type examples are considered. Is this a limitation of the approach?
questions: - In the algorithm box $x^{(1:K)} \sim q_\eta$ are iid. Is this necessary or can they be generated from a Markov chain?
- Is requiring $\nabla_\theta f(x)$ a restriction of this approach compared to the other approaches discussed in the paper?
- It feels like the choice of the function $H$ (i.e. eq. 16) is important for the efficiency of the control variate. Can more be said about the choice of the neural architecture in H?
- What is the computational cost for the algorithms in Table 2?
- The gradient $g_gamma$ isn't clearly defined.

limitations: The limitations of the approach are discussed in the conclusion section. There are no obvious negative societal issues.
review_title: null

Meta-review: metareview: Thanks to the authors for this submission.  The reviewers all agreed that this is a novel and effective method for reducing gradient estimates in a discrete setting.  The reviewer-author discussion was fruitful, and changes to the manuscript have improved the submission.  

confidence: Certain
Decision: Accept