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 proposes a method to compute a derivative of stochastic programs which have discrete dependencies on their parameters. The paper introduces stochastic triples generalizing dual numbers to programs with discrete randomness. The resulting AD method is shown to produce unbiased derivative estimates with lower variance compared to score function methods. A working implementation is developed in Julia. Forward mode and reverse mode AD (using the smoothing technique) is demonstrated on 3 examples. The experiments demonstrate the utility of stochastic triples for unbiased, lower-variance derivates in forward and reverse mode AD on 3 examples.

---

UPDATE: I thank the authors for their detailed responses. After reading the other reviews and author responses, I'm more positively inclined towards the paper and have upgraded my score to "Accept".
strengths_and_weaknesses: Strengths
  + The paper tackles an important and challenging problem of AD in programs with discrete randomness. 
  + The paper makes novel algorithmic contributions (stochastic triples, smoothing) as far as I can tell.
  + The paper includes working code and demonstrates the unbiased and low-variance properties empirically.
  + The paper is intuitively clear and well written.

Weaknesses
  - The novelty of the technical contributions compared to existing AD frameworks could be made a bit clearer. Also, a deeper discussion of which program classes or constructs are not differentiable by popular reverse-mode AD frameworks might help make the contributions clearer.
  - A deeper empirical investigation would have been good to see. In particular, I'd have liked to see experiments demonstrating the limits of the proposed approach as well as the use of "larger" applications instead of the toy examples.

Overall, this seems like a nice paper making progress on a hard problem. I didn't detect any technical issues with the paper but I don't have a deep background in this research area. I'm open to adjusting my scores based on the other reviews.
questions: 1. Can you provide more detail about how the proposed implementation compares with existing popular reverse-mode AD libraries? What classes of popular applications of reverse-mode AD can StochasticAD.jl be used / not used?




limitations: Yes
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper introduces a technique named “stochastic derivative” that helps construct a stochastic program whose expectation is the derivative of the expectation of a given stochastic program, which might include discrete random variables. The technique is then shown to give unbiased estimators and low variance (compared to the baseline score-function method) through three examples: inhomogeneous random walk, stochastic game of life, and particle filter.
strengths_and_weaknesses: Overall, I think this is an important paper which introduces a novel technique but needs a major revision for clarity.

The paper is technically sound. I really like that the authors provide detailed motivations and illustrations for each idea and want to thank the authors for that. However, the structure is a bit hard to follow. For example, Section 2 talks about “composable stochastic derivatives” but I only get what “stochastic derivatives” means until Theorem 2.3. Or the section 2.4 talks about Smoothing but lacks background for why it is needed (is this related to Smoothed perturbation analysis mentioned in the introduction?)

I’m not familiar with Julia but would like to reproduce some results in the Demonstrations section in Python to better understand the technique. However, the paper lacks an outline on how to design that stochastic AD system.

The proposed approach is only compared to the score-function method in the inhomogeneous random walk example, showing that using stochastic triples the variance of unbiased gradient estimates. Could the author also provide empirical comparisons to the score-function method in other examples?

**Updated:** I'm happy to increase my score given that the writing quality has been much improved in the last revision.
questions: + It would be helpful if the authors give a list of parameterizations of distributions used in the main paper, like Exp, Bin.
+ Line 87: I wonder what is the definition of Z?
+ Line 105: Why the value of dX(z) is O(eps), I thought this quantity is -eps * log(1-z) which is not bounded when z near 1?
+ Figure 2: The red dashed line indicates a sample obtained by black-box finite differences. What does O(1) imply at this dashed line?
+ Lines 119-120: Why the variance of those independent samples z1, z2 is of order infinity? In addition, it might be more consistent with the introduction section to use X(p + eps) - X(p), rather than X(p + eps/2) − X(p − eps/2).
+ Line 145: Does f need to be bounded? In later examples, I’m seeing f(x) can be x^2 or x^3, which are not bounded.
+ Line 152: typo: infinitely. What does “infinitely close to 1” mean? Why is the importance weight close to 1 here?
+ Line 162: typo: occurring
+ Lines 160-164: I don’t understand this paragraph. Could the author add more details? What does “event of two finite perturbations occurring simultaneously” mean?
+ Line 172: typo: parameterized
+ Line 173: please provide which section in the supplemental that we should look at
+ Figure 4: how can we interpret the output in this figure?

limitations: Nothing to report.
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 proposes a novel approach for both forward- and reverse-mode automatic differentiation of probabilistic programs with discrete RVs. Since the derivative $\frac{dX}{dp}$ of a program $X$ with respect to the parameters $p$ of a discrete distribution is not well-defined, the authors circumvent the problem by finding the derivative of the expectation of $X$, i.e. $\frac{d\mathbb{E}(X)}{dp}$.
The technique results in an unbiased estimator, exhibiting lower variance with respect to prior approaches. 

strengths_and_weaknesses: The problem considered in this work is a relevant one.
While the paper is generally well-written, I found it hardly accessible for nonexperts in AD, like myself. 
I wish that the paper included some more examples, for instance a figure showing how these stochastic triples are propagated in a simple program. In this sense, Figures 3 and 4 are not that useful in my opinion. I can't really assess the soundness of the proposed approach, but I didn't spot any major issues. Similarly, I am not familiar with the existing literature and it is possible that I missed some relevant work. I think that the experimental evaluation could be improved (see questions below).

**Update after rebuttal** The authors addressed my points effectively and submitted a significantly improved version of the manuscript.
questions: 
1- In 4.1, what value(s) of $p$ were used? Why not showing in Fig.5  (center) the standard deviation over multiple values of $p$?

2- In 4.2 the program is almost deterministic with $p=0.05$. What happens as $p$ approaches $0.5$?

3- Why not applying the score-function method to the tasks 4.2 and 4.3? It is also not clear to me why some approaches mentioned in the Related Work section were not considered (REBAR, RELAX, or the reparametrization trick with Gumbel-softmax).

4- In Fig.6 (center), why not reporting both forward and reverse mode AD, possibly using the same colors in Fig.6 (right)?

5- The paper mentions some additional complications when dealing with multivariate functions. Why not reporting experiments in that sense?

---

**Minor comments**

- Fig.1: I don't get it. $X'(p + \epsilon)$ with random number sequence
  z(2) (bottom) in the caption is $X(p + \Delta p)$ in the figure. What
  is the relation between $\Delta p$ and $\epsilon$?
---
"This variance issue can be alleviated if one could run the perturbed program with the same set of random numbers, i.e. directly compute $\mathbb{E}[X(p + \epsilon) − X(p)]$" 

- Shoudn't it be 'solved' rather than 'alleviated'?
---
- Def. 2.2 "right (left) derivative" 'stochastic' is missing.
---
- When is a stochastic program "sufficiently regular"?
---

"It is convenient to assume probability densities [...]  and transition probability densities [...] all depending on the parameters $\theta$." 

- Why? You mean from a notational perspective?
---

**Typos**

- "algorithm. enabling"
- "an weighted"
- "with parametrized by"
- "particle filterunbiasedness"





limitations: Mostly yes, although the empirical evaluation could be improved in this sense (see above).
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper provides a new method to compute the gradient of the expected output of a stochastic computation graph (SCG) w.r.t one of the input parameters of the graph even when the graph contains discrete randomness. 

In a well known method for computing gradients of stochastic computation graphs when they contain only continuous valued variables all the stochastic variables are reparameterized which allows for the gradient of the expectation to be sampled for any parameter by simply propagating the primal value of the graph variables as well as the forward gradients. This paper extends this well-known method by additionally propagating an alternate value for one of the discrete stochastic nodes in the graph (plus the alternate values of all the children of that flipped node) as well as the gradient of the probability of that alternate value.

This method has been shown to greatly reduce the variance of the estimated gradient of the expectation as opposed to standard methods such as the score function estimator which is typically used to estimate such gradients for graphs with discrete randomness.

strengths_and_weaknesses: The method is clearly original. There are a number of papers in the literature which attempt to solve this particular problem (estimate gradients of SCG with discrete random variables) such as reinforce, concrete, score function estimator, path wise gradients etc. But they are all rather different from the current paper and those methods all suffer from some form of high variance issues that are explicitly addressed in this paper.

This paper's key contribution is the realization that simply estimating gradients along multiple independent paths may introduce excessive variance in the estimate and it is better to look for correlated paths.

The work is very signification since estimating gradients in SCGs are an important problem in various branches of AI in particular Reinforcement Learning and Bayesian Inference. There are a number of papers routinely published every year in NeurIPS which make some reference or the other to this problem and use one of the aforementioned methods. So, an improved solution to this problem is hugely impactful.

The weakness of the approach is that it is only defined for forward mode gradients and the authors only spend any effort to describe the gradient computation for a single input. In most machine learning applications reverse mode gradients are preferable to compute since we have one loss function which we want to differentiate w.r.t. multiple parameters. 

The quality of the technical writing is somewhat patchy though and that is why I hesitate to give a higher rating than would be deserved for work that has provided such an interesting breakthrough.

The experiments have been selectively picked for examples with a single parameter, but that seems a bit contrived. There are a number of reinforcement learning papers in the literature which rely on SCG differentiation. Using one of them in this paper would have been more impactful than the game of life example. The resampling example on the other hand was interesting as that is a common use case.

questions: In lines 311-312 the authors say that the method is only applicable when control flow is independent of random parameters. What does this mean exactly? Does this mean that if the SCG has if-statements and it can take completely different paths based on random values then the method doesn't work. Why?

In Figure 1 why does it show 3 alternate paths when pruning has been defined to only allow one alternate path?

In definition 2.2, it seems to me that `w` is the gradient of the probability of the output of the SCG flipping from X to Y (where the gradient is w.r.t. p). Is this an accurate charaterization?

In lines 151-159 there seems to be some confusion as to whether w is a vector or a scalar based on the description. Could you please give a clearer description?

In line 181 where does the $\delta$ come from? The statement of the proposition has $\delta_1$ and $\delta_2$? This proof is also hard to follow in the supplement. Could you provide the key points of the proof here? I would give a higher rating and confidence if I can convince myself that these composition propositions are correct.

The description of smoothed stochastic duals is very vague. Could you give a more mathematical definition?

In Figure 5 what does `rand(Categorical(probs[X]))` mean?

# Minor points

- Line 142 "program with parameterized" seems to be missing something?
 
- Figure 6 left figure takes very long to render. Please consider alternate image formats.

- Line 242 typo: "filterunbiasedness" 

- In equation 4.1 can x be negative? If yes then the probabilities don't make sense.


limitations: No known negative societal impact.
review_title: null

Meta-review: metareview: The topic of this paper is interesting, and I wanted to get the basic idea, so I looked at the paper myself.  Had I been a reviewer I would have recommended rejection.  However, as the existing reviews are positive, and the authors will not have a chance to respond to my objections, I will recommend acceptance (in spite of the low confidence scores of the reviewers where the high scores have confidence 2.) For the sake of the authors I will list my complaints.

My fundamental complaint is about clarity.  The central problem is the notation X(p).  In the main text this is only defined as a "stochastic program".  But what is it allowed to be a distribution on?  What is the allowed dimension of the parameter (vector?) p? If X(p) is an arbitrary stochastic program what is E[X(p)]?  If X(p) defines a distribution on a finite abstract set then clearly E[X(p)] CANNOT mean the expectation of a random value.  The first sentence of appendix B.2 need to appear before any appearance of the notation E[X(p)] in the main text. Even if that is done, the authors are assuming a fixed embedding of each random value of x in a Euclidean space.  But in the vast majority of modern applications that embedding must be learned.  For example, in a VAE model of grammar induction one must learn an embedding of the grammar nonterminal symbols. The formal set up would be greatly clarified by explicitly introducing a "loss function" f as part of the given data and write, for example E_{x \sim X(p)} [f(x)].  The main body of the text needs more intuition about the meaning of w and Y in theorem 2.2 and some kind of sketch of a proof.  The paper would be significantly simpler if limited it to the case where X(p) is entirely discrete.  This is the interesting case and there is then no need for X'(p). The technically hard issue is w and Y in theorem 2.2.  If a mixed stochastic-continuous case is needed for the general case then it could come later where it is well motivated.    An explicit form for w and Y should appear in the body of the paper rather than a naked claim that they exist.  Any implementation must construct w and Y so the proof needs to be constructive.  Examples are nice, but they are no substitute for the proof of the general case.  Some sketch of that proof needs to appear in the body of the text --- most importantly a computable solution for w and Y. As it stands it appears that the authors are trying to hide the artificial nature of their technical set-up --- the use of a-priori fixed embeddings of abstract tokens.


confidence: Less certain
Decision: Accept