Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes a novel way to construct low-variance gradient estimators for differentiating through the output of recursive algorithms. By using random variables present in intermediate steps of the algorithm (called "the trace"), the authors propose a low-variance score function estimator formed using the gradient of the density of the trace. They explore this empirically in several settings and demonstrate improved performance.
main_review: Originality: To my knowledge, the idea is original.

Clarity and Quality: The main issue with this paper is its lack of clarity and polish. There are numerous things that were poorly explained or not explained at all. Here is a list:

* When introducing the algorithm, the definition of T is not given explicitly or implicitly. After reading the paper several times I have come to think that it is the 'key' of the item that is removed from the set at each recursive step, but that is not stated anywhere explicitly.
* Similarly, X is not explained well. 
* I think a better introduction to section 3 (lines ~102) would go a long way if you introduced each of the objects and the overall framework instead of diving in immediately to discuss the exponential variables.
* The need for partitioning the indices in algorithm 2 is not explained or really referenced elsewhere.
* f_split, f_combine, and f_stop are not defined or really explained in depth.

These issues and more combine to make it very difficult to understand specifically what is being proposed.

In addition to the clarity issues, there is an overall lack of polish. There are several spelling and grammatical errors, and the title is also a bit awkward. I would recommend "Latent structure learning through stochastic invariance" or "latent structure learning through a stochastic invariant", but the current phrasing doesn't sound right to my ear.

Finally, the experimental evaluation of these methods leaves a bit to be desired. Because the authors are proposing a gradient estimator, test-set performance is only part of the picture. To clearly make the case for the estimator I would like to see comparisons of the variance of these different gradient estimators over training, as well as train-set performance over time. The reason for seeing the training set performance is that better gradient estimators should result in better optimization, and test set results can be clouded with issues like overfitting.

Additionally, the current experimental results don't seem to strongly recommend the authors' proposed method.

If the authors substantially revise their draft to make it more clear and add the additional metrics I requested, I will update my score to reflect the new paper.

EDIT: After rebuttal I have raised my score.
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The authors propose score-function gradient estimators for structured latent variable models in which the structured variables are described as the output of a stochastic invariant perturbed algorithm. They derive different score-function estimators based on the algorithm's input $E$ and execution trace $T$ which can be computed even if the standard score function $\nabla_\lambda \log p_X(X=x; \lambda)$ is not available.

main_review: **Originality:**
To the best of my understanding the presented work is novel and methodologically significantly differs from existing work. Most notably seems to be the work by Paulus et. al. [1], which combines the perturbation model framework and relaxation for gradient estimation. While the authors take inspiration from [1] they take a different approach in that they do not make use of relaxations but develop score-function gradient estimators for a class of 'stochastic invariant' perturbation models.

**Clarity:**
While the technical aspects of the paper are described in a clear manner I found it challenging to navigate and understand. After reading the first half of the paper I was under the impression that the authors develop lower variance score function estimators based on the Gumbel-Max trick as an alternative to continuous relaxations, but also as an alternative to standard score function estimators, which often have high variance.
Hence, after the authors explain in section 4 that the variance of the standard score function estimator is actually superior to the proposed variants I was a bit confused at first.
My current understanding is that the paper offers a way to compute score function estimators for 'stochastic invariant' discrete variable models even when the standard score-function estimator can not be computed, i.e. when $\nabla_\lambda \log p_X(X=x; \lambda)$ is not available/is intractible.
If this is indeed the case, I'd strongly encourage the authors to make this clear and motivate this early on in the paper.
To this end, it might also be a good idea to move the related work section right after the introduction. This way the presented work can be put into context and it's clear what the actual contributions over existing work are right from the start.

Another source of confusion was that the authors started using the acronym 'SST' in the experiment section and 'SST (Our Impl.)' in Table 2 without introducing it. Based on the label in the table I was wondering if there is a variant of the proposed estimator with the acronym SST that I somehow missed. After checking some of the related work, I discovered that [1] also uses the acronym 'SST', which stands for 'stochastic softmax tricks', and that it's indeed a baseline.

I also found the notation in Algorithm 1. confusing.
In the algorithm block $T = \arg \min E_j$ seems to denote an index, while in the writing and caption $T$ denotes an execution trace. I do not understand how these two notions would map onto each other. If they don't, using different letters might be more clear.


**Quality:**
To the best of my knowledge the paper is technically sound and the empirical results support the authors claim that the proposed method achieves results competitive with their relaxation-based counterparts.

**Significance:**
Many systems and generative processes incorporate or can be described in terms of discrete latent variables, e.g. discrete control flow in probabilistic programming models.
The presented work offers a technically interesting approach which allows to compute score-function estimators and corresponding baselines for 'stochastic invariant' perturbation models. Moreover, the presented results show that these estimators can perform on par with reparameterized relaxation-based estimators. As such, I do believe that this work is of interest to the broader probabilistic machine learning community.
My concern is that the current manuscript is challenging to read and understand and as a result readers might not pick up on the idea.


**Typos I noticed**
  - Line 149: function of *the* trace
  - Line 152: Lemma 2 -> Lemma 1?
  - Line 307: For *the* encoder
  - Line 321: *small*

*[1] Max B Paulus, Dami Choi, Daniel Tarlow, Andreas Krause, and Chris J Maddison. Gradient estimation with stochastic softmax tricks. arXiv preprint arXiv:2006.08063, 2020*



limitations_and_societal_impact: adequate
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper cleverly uses the Exponential-min trick in Lemma 1 to derive a score-function based gradient estimator for learning latent variable models. It is applicable to a special class of latent variable generation (in settings where we learn a generative model-recognition model pair, the proposed method puts constraints on the recognition model) described in Algorithm 2, which successively transforms a sequence of Exponential random variables to a set of "trace" variables which are used to finally obtain the desired latent variables. This function is recursive and the "stochastic invariant" refers to the fact that each recursive call gets as arguments stochastic variables that always have an Exponential distribution. The proposed method is supposed to be useful especially when we cannot directly evaluate the score function of the latent variables (which would have lower variance) -- this occurs for example, when it is produced by an implicit generative process. There are 4 experiments comparing the different versions of the proposed gradient estimator with the recently proposed "stochastic softmax tricks" gradient estimator.
main_review: **Originality**: Are the tasks or methods new? Is the work a novel combination of well-known techniques? (This can be valuable!) Is it clear how this work differs from previous contributions? Is related work adequately cited?

The method is new. The work is a novel combination of the Exponential-min trick to a score function estimator. I'm not an expert in perturbation methods, but as far as I understand, this work differs from previous perturbation methods applied to latent variable model learning in that it's used to improve a score function based estimator. And yes, the related work provides enough pointers to the most important related work.

**Quality**: Is the submission technically sound? Are claims well supported (e.g., by theoretical analysis or experimental results)? Are the methods used appropriate? Is this a complete piece of work or work in progress? Are the authors careful and honest about evaluating both the strengths and weaknesses of their work?

The method is technically sound and well explained. I particularly appreciated the min-k example in Algorithm 1.

One thing that isn't completely clear to me is the family of latent variable models to which this method is applicable.
1) In lines 38-40 and in the paragraph in lines 56-62, it is explained why the computation of the score function is difficult -- is it really that difficult in most cases? If I were to write a complex generative model with discrete latent variables, I would define how those discrete latent variables are ancestrally sampled and so even if the space of all possibilities is combinatorial, I'd end up knowing how to evaluate the probability of the sampled variables alongside their score function.
2) The family of generative processes this is applicable to seems restricted on the surface:  I need to use exponentials, and then I need to make sure I do an argmin, and then to subtract the minimum exponential from the others, and then have a recursive call.

Together a discussion of the generality of the method would be really helpful!

**Clarity**: Is the submission clearly written? Is it well organized? (If not, please make constructive suggestions for improving its clarity.) Does it adequately inform the reader? (Note that a superbly written paper provides enough information for an expert reader to reproduce its results.)

The paper is clearly written (except the point above) and well organized.

**Significance**: Are the results important? Are others (researchers or practitioners) likely to use the ideas or build on them? Does the submission address a difficult task in a better way than previous work? Does it advance the state of the art in a demonstrable way? Does it provide unique data, unique conclusions about existing data, or a unique theoretical or experimental approach?

The results are important as it pushes the limits of learning discrete latent variable models. These are potentially important for more interpretable, explainable and generalizable systems. Yes, other researchers can definitely build on these ideas. It performs better than the recent "stochastic softmax tricks" method in most cases (inclusion of "failure" cases is appreciated as it paints a more realistic expectation of how this algorithm performs). As a side note, I found it cool that a simple leave-one-out estimator is better than a complex action-dependent RELAX-based estimator, is there any intuition behind this?

I notice that there is only one baseline algorithm (the SST). Are they the only one applicable? Or are they already the best of all the ones applicable? Would wake-sleep methods like reweighted wake-sleep be applicable?
limitations_and_societal_impact: Yes, 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: The authors propose an approach to learn structured latent variables through score function estimators. This approach would add the possibility of incorporating prior knowledge on deep learning models. The results with respect to RELAX are better on a number of different applications. However, the baseline SST is shown to still outperform in particular in structure recovery.
main_review: The paper is very dense from a theoretical point of view and not always clear to non-familiar audience. While I'm not familiar with the literature and did not check every mathematical detail, I appreciate the effort of the authors in being complete as much as possible.

It is very hard to read the experiments section. I appreciate the effort of the authors to report each application they tested their method on, but the results for each are not properly explained and I had to resort to the supplementary material to understand them. Also I understand the baseline is the RELAX algorithm, while the other rows in table 2-3-4 are the variants of the proposed methods, is that correct? Further, the authors mention that "Overall, score function methods performed better than their relaxation-based counterpart, achieving higher values of ELBO on the test set, but slightly worse performance in terms of structure recovery metrics." Is there any reason why the structure recovery of the score function is worse? I thought that one benefit of the score function was to incorporate prior knowledge on the problem, which would more better benefit the structure recovery more than better likelihood.

I understand the approach allows to incorporate additional prior knowledge in the model. However, I'm not sure how this translates when applying the method, especially for each application. The algorithm requires an additional variable R, which is an auxiliary variable accumulating the information from the recursive calls. How this relates with the prior knowledge that the method allows to include in the inference algorithm?


limitations_and_societal_impact: None
review_title: null

Meta-review: This is an interesting paper that introduces a method for taking gradients in models containing discrete structured latent variables.  The approach is based on using the exponential-min trick and a score function estimator that is carefully applied using intermediary "trace" variables in the generation process, allowing the intractability of the score function estimator for the output variables to be overcome, while providing lower variance than applying the score trick to the "raw" random variables.

Overall the reviewers were generally positive about the paper, praising its novelty, quality, and potential significance, and all backing its acceptance.  The main question marks were over the clarity of the paper, which indeed could certainly do with some non-negligable work, but I feel that these issues are not so fundamental that they cannot be addressed in time for the camera-ready version of the paper, a viewpoint which the reviewers seem to agree with.  As such, I recommend its acceptance to the conference, but strongly encourage the authors to work on refining the paper as per the reviewers' feedback.

Some comments of my own from reading the paper that may assist further with making improvements:
- Though not discussed in the response, Reviewer ZnaB is correct that “stochastic invariant” is grammatically incorrect and I agree that it should be “stochastic invariance”.  The term does not seem to be used entirely consistently as well, as it is mostly discussed as a property, but then Eq 8 seems to suggest another meaning (though maybe this is a typo?).
- It would be good to use a formal definition for “stochastic invariant” on lines 131-132 as it is easily missed in passing that this is where it actually being defined.  This definition possibly also needs to come earlier in the paper as well as the term is used a few times before its defined.
- Though the low-level writing of the paper is generally fine, there is definitely quite low of room for improvement on more high-level aspects.  In particular, the writing could be improved by making clear why things are being introduced before they are (in the context of the overall goals of the paper): at the moment many things are just explained without introduction and the reason we care about them (or indeed exactly what they are) only comes later.  This makes it difficult to follow as the reader is being fed technical information before they appreciate the context.  An example of this is Algorithm 2, which is discussed at length without a clear statement of what it actually is, while how both Algorithms 2 and 3 fit into the high-level aims of the paper is never stated explicitly.  More generally, the writing regularly falls into the trap of explaining things as if the reader already understands what is going on and knows what is coming later in the paper; it misses a lot of the “glue” that keeps the reader on track about where the paper is going, how things fit together, and how the low-level ideas link into the high-level aims.  It also often leaves too much implicit (e.g. what the baselines are and what the proposed models are in the experiments — note I would consider E-REINFORCE to be a baseline here, which should be made clear), rather than directly and explicitly stating what things are and what they are used for.  Some repetition of key points would also help, as there are a few key things that are only briefly stated once, and if you miss them the paper quickly becomes difficult to understand.
- Related to the above, and as noted by the reviewers, the paper could also do a better job of making clear what its contributions are in the introduction and why these are useful.  The motivation at the moment is a bit back and forth, and the contributions need stating explicitly and directly (as per the discussions with Reviewer EF5a), rather than in the implicit manner they are currently conveyed.
- One potential application I envisage of the work that is not mentioned in the paper is probabilistic programming, as here one often has complex branching behaviour that prohibits relaxation-based approaches. It might be good to add some mention of this if space can be found, while the concept of a “trace” the paper used is commonplace in the probabilistic programming literature and may be worthy of mention in the related work.
- I think it would strengthen the paper to include more baselines.  Even if SST is considered the “best”, this would still provide more evidence and make the competitiveness of the approach clear.  More discussion of the tested approaches is also needed in general and some repetition of exactly what everything is (e.g. what RELAX is can be difficult to immediately see, and the fact a previous approach has this name can be misleading), without which it can be surprisingly difficult to figure out what everything is.
- A possible missing reference you may wish to add: “Reparameterization Gradient for Non-differentiable Models” Lee et al. NeurIPS 2018.
Decision: Accept (Poster)