Differentiable Sampling of Categorical Distributions Using the CatLog-Derivative Trick
Authors: Lennert De Smet
Emanuele Sansone
Pedro Zuidberg Dos Martires
Venue: NeurIPS 2023 poster (2023)
Keywords: gradient estimation
categorical random variables
probability theory
discrete distributions
TL;DR: Differentiable sampling with Rao-Blackwellised multivariate categorical distributions.

Abstract: Categorical random variables can faithfully represent the discrete and uncertain aspects of data as part of a discrete latent variable model. Learning in such models necessitates taking gradients with respect to the parameters of the categorical probability distributions, which is often intractable due to their combinatorial nature. A popular technique to estimate these otherwise intractable gradients is the Log-Derivative trick. This trick forms the basis of the well-known REINFORCE gradient estimator and its many extensions. While the Log-Derivative trick allows us to differentiate through samples drawn from categorical distributions, it does not take into account the discrete nature of the distribution itself. Our first contribution addresses this shortcoming by introducing the CatLog-Derivative trick -- a variation of the Log-Derivative trick tailored towards categorical distributions. Secondly, we use the CatLog-Derivative trick to introduce IndeCateR, a novel and unbiased gradient estimator for the important case of products of independent categorical distributions with provably lower variance than REINFORCE. Thirdly, we empirically show that IndeCateR can be efficiently implemented and that its gradient estimates have significantly lower bias and variance for the same number of samples compared to the state of the art.

Differentiable Sampling of Categorical Distributions Using the CatLog-Derivative Trick
Lennert De Smet KU Leuven
Emanuele Sansone KU Leuven
Pedro Zuidberg Dos Martires Örebro University
Abstract
Categorical random variables faithfully represent the discrete and uncertain aspects of data as part of a discrete latent variable model. Learning in such mod- els necessitates taking gradients with respect the parameters of the categorical probability distributions, which is often intractable due to their combinatorial na- ture. A popular technique estimate these otherwise intractable gradients is the Log-Derivative trick. This trick forms the basis of the well-known REINFORCE gradient estimator and its many extensions. While the Log-Derivative trick allows to differentiate through samples drawn from categorical distributions, it does not take into account the discrete nature the distribution itself. Our first con- tribution addresses this shortcoming by introducing the CatLog- Liiioo---eriivvvvee trick- a variation of the -erivvviaeevve trick tailored towards categorical distributions. Secondly, we use the and unbiased gradient estimator for the important case of products of independent categorical distributions with provably lower variance than REINFORCE. Thirdly, we empirically show that IndeCateR can be efficiently implemented and that its gradient estimates have significantly lower bias and variance for the same number samples compared to the state of the art.
trick to introduce IndeCateR, novel
Introduction
Categorical random variables naturally emerge many domains in AI, such language modelling. reinforcement learning and neural-symbolic AI [10]. They are compelling because they can faithfully represent the discrete concepts present in data sound probabilistic fashion. Unfortunately, infer- ence in probabilistic models with categorical latent variables is usually computationally intractable due to its combinatorial nature. This intractability often leads to the use of sampling-bast approxi- mate inference techniques, which in turn poses problems to gradient-based learning as sampling is an inherently non-differentiable process.
In order to bypass this non-differentiaaiiliy. two main classes of gradient estimators have been developed. On the one hand, there is range of unbiased estimators based on the Log-Derivative trick and the subsequent REINFORCE gradient estimator [40]. On the other hand, we have biased estimators that use continuous relaxations to which the reparametrisation trick [33] can be applied, such as the GumbellSSffunn trick [16, 22].
clear advantage of the REINFORCE estimator over relaxation-basel estimators is its unbiased nature. However, REINFORCE tends to be sample-inefficient and its gradient estimates exhibit high variance in practice. To resolve these issues, methods have been proposed that modify REINFORCE by. for instance, adding control variates [31, 37J. These modified estimators have been shown to deliver more robust gradient estimates than standard REINFORCE.
Instead of modifying REINFORCE, we take a different approach and modify the Sog-Deriva trick by explicitly taking into account that are working with multivariate categorical distributions.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

We call this first contribution the CatLog- CatLog-Derivative trick. Interestingly, we show that our CatLog- Derivative trick leads wao-Blaakwellisedd estimators [4], immediately giving us a guaranteed reduction in variance. The Catl oo-Deervvtevve trick can also be seen generalisation of the Local Expectation Gradients (LFG) [36] capable of exploiting more structural, distributional properties. This connection to LEG will be clarified throughout the paper.
As a second contribution, we propose IndeCateR (read as 'indicator'), gradient estimator for the special case of independent categorical random variables. IndeCateR is a hyperparameter- free estimator that can be implemented efficiently by leveraging parallelisation on modern graphical processing units (GPUs). Thirdly, we empirically show that IndeCateR is competitive with comparable state-of-the-ars gradient estimators on range of standard benchmarks from the literature.
Notation and Preliminaries
Throughout this paper, we consider expectations with respect to multivariate categorical probability distributions of the form
Ex~p(x) [s()]= = E p(x)S(x),
(2.1)
XER(X)
where we assume this expectation to be finite. The symbol X denotes random vector (X x XD) of D categorical random variables while p(X) denotes multivariate probability distribution. The expression X ~ p(X) indicates that the random vector X is distributed according to p(X). X. On the right-hand side of Equation (2.1) we write the expectation as an explicit sum over S2(X), the finite sample space of the random vector X, using x = (Z1...., zD) for the specific assignments of the random vector
Given an order of the random variables in X, we can induce a factorisation of the joint probability distribution follows
D p(X) = II P(x Xed).
(2.2)
Here, Xed denotes the ordered set of random variables (X1, Xd-1). Similarly, X will denote the ordered set (Xa+1....., .D) in subsequent sections.
When performing mudicntt-bssed learning, we are interested in partial derivatives of the expected value in (2.1), i.e., 0xExx~pXx [f[X] Here, we take the partial derivative of the expectation with respect the parameter À and assume that the distribution p( () and the function f(X) depend set of parameters A with A. For probability distributions to which the reparametrisation trick does not apply, we can rewrite the partial derivative using the Log-Derivative trick.
Theorem 2.1 (Log-Derivane Trick [40]). Let ((X) be probability distribution and fXX) such that its expectation is finite, with both functions depending on a set of parameters A. Then, it holds that
d Ex=p(X) [f(X)] = Ex-p(x) [X) + Ex~p(x) [f lx)]
(2.3)
In general, both expectations in Equation (2.3) are intractable and often estimated with a Monte Carlo scheme. The most immediate such estimation is provided by the REINFORCE gradient estimator [40]
N
a ExEx [f(X) =0
Σ n=1
(Das(x((n)) + f(x(1))), log ((x(())
(2.4)
N
The superscript (") denotes that it is the nhth sample vector drawn from p(X).
well-known problem with the REINFORCE gradient estimator is the high variance stemming from the second term in Equation (2.4). A growing body of research has been tackling this problem by proposing variance reduction techniques [11, 31, 37, 39]. what follows we will focus on estimating this second term and drop the first term, since it can be assumed to be unproblematic.

---

3 The CatLog-Derivative Trick
The standard Der--eeivteive trick and its corresponding gradient estimators are applicable both discrete and continuous probability distributions. However, this generality limits their usefulness when it comes to purely categorical random variables. For example, the REINFORCE gradient esti- mator suffers from high variance when applied to problems involving high-ding -ith-dimnnsioaal multivariate categorical random variables. In such setting there are exponentially many possible states to be sampled, which makes it increasingly unlikely that specific state gets sampled. We now introduce the CatLog-Derivativv Derivative trick that reduces the exponential number of states arising a multivariate categorical distribution by exploiting the distribution's 's factorisation.
Theorem 3.1 GaaLLogDDrrvvttin Trick). Let p(X) be multivariate categorical probability distribu- tion that depends a set of parameters A and assume Ex~p(X) [f(X]] is finite. Then, it holds that 0x F xxx(() [f() is equal to
Σ
Σ d= ExE((Xa))
Excexpix (xpllrs
(f 4d xs)]]
(3.1)
Proof. We start by applying the standard Log-Dew -og-Derivative trick and fill in the product form of the categorical distribution followed by pulling this product out of the logarithm and the expectation
D
Ex-r(x ([ = Ex=p(x)
f(x)a) log II P(x Xea)
(3.2)
Σ Ex>p(x) (S()) logp(Xa X X<a)]-
(3.3)
To continue, we write out the expectation explicitly and write the sum for the random variable Xa separately, resulting in
D Σ Σ d=1 xER(E 4a) mbER(X,))
x8 logp( xxa)-
(3.4)
Next, factorize the joint probability p(x,d, 28) as p(x>d V8, xca((() x<d)p(x<a)= Multi- plying the second of these factors with 0* log xxd) gives us Oxp(Ess Xea). Finally, plugging Oxp(as x<a) into Equation (3.4) gives the desired expression.
Intuitively, the CatLLog-Dervvan trick decomposes the Log-Derivaate trick into an explicit sum of multiple Log-Derivative tricks, one for each of the categorical random variables present in the multivariate distribution. Next, we use the CatLog- -eee---vvveevvee trick to define a novel gradient estimator that exploits the structure of a probability distribution by following the variable ordering of the distribution's 's factorisation and effectively Lao-Blackwellisse [4] REINFORCE.
Definition 3.2 (The SCateR gradient estimator). We define the Structured Categorical REINFORCE
(SCateR) estimator via the expression
N
O ExEx~p(x) [f(x)]
Σ
Σ (
Σ n==11
Oxp(as
(na)) of fx Is. Is. x
(ma)
(ma))
(3.5)
N
(nz) where the sample x-d is drawn while conditioning that different samples can drawn for every d.
and
x (mg), The subscript on indicates
Proposition 3.3. The SCateR estimator Rao- aho-Blackwellises REINFORCE.
Proof. We start from Equation (2.4) for the REINFORCE estimator, where we ignore the first term and factorize the probability distribution similar to Equation (3.3)
N f(x (n))) (o))(a(")). (3.6)
02 Ex=p(X) [(()) 2
Σ n=1
N
n=1
3

---

For notational conciseness, we drop the subscript on na and simply use to identify single samples. Now we compare Equation (3.5) and Equation (3.6) term-wise for N
00
N
N Six
Σ E Xxxp((xax())
(n) [(x Xa, x)xx)) log log
a xx log log
In the equation above, we see that SCateR takes the expected value for Xa (left-hand side) and computes exactly using an explicit sum over the space 9(Xa), whereas REINFORCE (right-hand side) uses sampled values. This means, in turn, that the left-hand side is Rao-Blackwellised version of the right-hand side. Doing this for every gives us a Bho-Blackwellised version for REINFORCE, i.., the SCateR estimator.
Corollary 3.4 (Bias and Variance). The SCateR estimator is unbiased and its variance is upper- bounded by the variance of REINFORCE.
Proof. This follows immediately from Proposition 3.3, the law of total expectation and the law of total variance [3, 29].
Computational complexity. Consider Equation (3.5) and observe that none of the random variables has sample space larger than performing three nested sums with lower bound 1 and upper bounds equal to D, K and N, respectively. These summations result in a time complexity of (D- ..N.. Leveraging the parallel implementation of prefix sums on GPUs [19), time complexity of Olog D + log K + log N) can be obtained, which allows for the deployment of SCateR in modern deep architectures.
max, (I5(x,) Computing our gradient estimate requires
Function evaluations. The main limitation of SCateR is the number of function evaluations it requires to provide its estimates. Indeed, each term in the three nested sums of Equation (3.5) involves a different function evaluation, meaning overall number of at most D (- (Xa)) -N function evaluations is necessary for every estimate. Fortunately, these evaluations can often be parallelised in modern deep architectures, leading to positive trade-off between function evaluations and performance in our experiments (Section 6).
Connection to Local Expectation Gradients (LEG). LEG [36] was proposed as gradient estimator tailored for variational proposal distributions. Similar to the CatLog-Derivative trick, it also singles out variables from target expectation by summing over the variables' domains. However, does so one variable at a time by depending on the Markov blanket of those variables. This dependency has the disadvantage of inducing a weighted expression, a singled-ous variable X; are sampled independently of the values assigned to X,. In this sense, LEG can intuitively be related to Gibbs sampling where variable is marginalised given possible assignments to its Markov blanket instead of being sampled.
variables downstream of
In contrast, the GuLLo--errvaatie trick is applicable to any probability distribution with a known factorisation, even in the case where different factors share parameters. sums out variables by following the variable ordering of this factorisation rather than depending on the Markov blanket. Following the topology induced by the distribution's is factorisation naturally avoids the disconnect between summed-out and downstream variables for which LEG required weighting term and makes the -erivvvvtie trick more related to ancestral sampling. Morcover, computing these LEG weights adds additional computational complexity. A more technical and formal comparison between LEG and the Derivaaive trick can be found in the appendix.
4 The IndeCateR Gradient Estimator
Using the CatL-og--eed Derrvvvvte trick derived in the previous section we now going study a promi- nent special case of multivariate categorical distributions. That is, we will assume that our probability
distribution admits the independent factorisation p(X) -I Pa(Xa). Note that all D different distributions still depend on the same set of learnable parameters A. Furthermore, we subscript the individual distributions pa as they can no longer be distinguished by their conditioning sets. Plugging in this factorisation into Theorem 3.1 gives us the Independent Categorical REINFORCE estimator, or IndeCateR for short.

---

Proposition 4.1 (IndeCateR), Let p(X) be a multivariate categorical probability distribution that depends set of parameters A and factorises as p(X) ITa= Pd(Xx)) then the gradient of finite expectation (x))(X) [f(X) can be estimated with
D
N (nd) pd Iz);
Σ
Σ
Oxpa(IS)
Σ n1=1
(4.1)
N
d=1 ma
(na) where xdd are samples drawn from p X (X)
Proof. We start by looking the expression in Equation (3.1). Using the fact that we have a set of independent random variables, we can simplify p(zs) xxaa) to Pa(xs). As a result, the gradient of the expected value can be rewritten as
D Σ
0,Ex OxEx~ [f(X)]
Σ
Ex Exxx>p(Xes)
(4.2)
d=1 xxE(((aa)
(xx (f(X (0(x))
Σ
Σ
(4.3)
Drawing N samples for the D independent random variables X and for each term in the sum over d then gives us the estimate stated in the proposition.
Example 4.2 (Independent Factorisation). Let us consider a multivariate distribution involving three 3-ary independent categorical random variables. Concretely, this gives us
p(X1, X2, X3) P1 (X, (X2))))))
(4.4)
where X1. X2 and X3 can take values from the set S2(X) (1,2,3). Taking this specific distribution and plugging it into Equation (4.1) for the IndeCateR gradient estimator gives us
Σ
Oxpales) 1 (1..33
Σ
Σ m==1
f(x xx))
(ox) 28).
(4.5)
N
In order to understand the difference between the -eo--eeivettvv trick and the CatLog-Derivative trick, we are going to look at the term for d 2 and consider the single-sample estimate
Derivative
(1P2(1)f(21 1, 13) +
xs) + (3) (21,
(4.6)
where I1 and are sampled values for the random variables X, and X3. These samples could be different ones for d + 2. The corresponding single sample estimate using REINFORCE instead of IndeCateR would be @xp2(12) (2,
We see that for REINFORCE we sample all the variables whereas for IndeCateR perform the explicit sum for each of the random variables in turn and only sample the remaining variables.
In Section 6, we demonstrate that performing the explicit sum, as shown in Example 4.2, leads to practical low-variance gradient estimates. Note how, in the case of reduces to the exact gradient. With this in mind, we can interpret IndeCateR as computing exact gradients for each single random variable Xa with respect an approximation of the function Ex (x 44) [X(xe,, Xa)].
1. Equation 14.1)
LEG in the independent case. The gap between the LEG and CatLog- Deriivvtteee trick gradient estimates grows smaller in the case the underlying distributions factorises into independent factors. The additional weighting function for LEG collapses to 1, resulting in similar expressions. However, two main differences remain. First, LEG does not support factors with shared parameters, although this problem can be mitigated by applying the chain rule. Second, and more importantly, LEG does not allow for different samples to be drawn for different variables. While this difference seems small, will provide clear evidence that it can have significant impact performance (Section 6.4).
5

---

Related Work
Apart from LEG, another closely related work is the RAM estimator [38]. RAM starts by reparametris- ing the probability distribution using the Gumbel-Max trick followed by a marginalisation. We show in Section 3 that this reparametrisation step is unnecessary. allowing SCateR to explicitly retain the conditional dependency structure. Here we also see the different objectives of our work and Tokui and Sato's. While they proposed RAM in order to theoretically study the quality of control variate techniques, we are interested in building practical estimators that can exploit the structure of specific distributions.
Moreover, just like LEG, Tokui and Sato [38] did not study the setting of a shared parameter space A between distributions, although this being the most common setting in modern deep-discrete and neural-symbolic architectures. Hence, an experimental evaluation for this rather common setting is missing in Tokui and Sato [38]. By providing such evaluation, implemented Rao- Blackwellised gradient estimators for categorical random variables are a viable option in practice when compared to variance reduction schemes based control variates.
show that efficiently
Such variance reduction methods for REINFORCE aim reduce the variance by subtracting a mean-zero term, called the baseline, from the estimate [2, 28]. Progress in this area is mainly driven by multi-sample, i.e., sample-dependent, baselines [11, 12. 13, 25, 30, 37, 39] and leave-one-out baselines [17, 18, 26. 31, 34, 35j. Variance can further be reduced by coupling multiple samples and exploiting their dependencies [6. 7, 8, 9, 43, 44, 45J. These latter methods usually introduce bias, which has to be resolved by, for instance, importance weighing step [8].
general drawback of baseline variance reduction methods is that they often involve a certain amount of computational overhead, usually in the form of learning optimal parameters or computing statistics. This computational overhead can be justified by assuming that the function in the expectation is costly to evaluate. In such cases, it might pay off to perform extra computations if that means the expensive function evaluated fewer times.
Another popular, yet diametrically opposite, approach to low-variance gradient estimates for cate- gorical random variables is the concrete distribution [22]. The concrete distribution is continuous relaxation of the categorical distribution using the Gumbel-Softtax trick [16]. Its main drawback is that it results in biased gradient estimates. Even though this bias can be controlled by temperature parameter, the tuning of this parameter is highly non-trivial in practice.
6 Experiments
In this section we evaluate the performance of IndeCateR on a set of standard benchmarks from the literature. Firstly, two synthetic experiments (Section 6.1 and Section 6.2) will be discussed. In Section 6.3, discrete variational auto-encoder (DVAE) experiment is optimised on three standard datasets. Lastly, we study the behaviour of IndeCateR standard problem taken from the neural- symbolic literature (Section 6.4).
We mainly compare IndeCateR to REINFORCE leave-one-out (RLOO) [17, 34] and to the Gumbel- Softmax trick. The former is a strong representative of methods redueing variance for REINFORCE while the latter is a popular and widely adopted choice in deep-discrete architectures [15].
We implemented IndeCateR and RLOO in TensorFlow [1], from where we also took the implemen- tation of the concrete distribution.' Furthermore, all gradient estimators were JIT compiled. The different methods were benchmarked using discrete GPUs and every method had access to the same computational resources. A detailed account of the experimental setup, including hyperparameters and hardware, given in the appendix.
In the analysis of the experiments we are interested in four main quantities: 1) the time it takes to perform the gradient estimation, 2) the number of drawn samples, 3) the number of function evaluations and 4) the value of a performance metric such as the ELBO. The number of function calls matters in as far that they might be expensive. Note, however, that evaluating the function, is comparatively cheap and trivially parallelisable the standard benchmarks.
'Our code is publicly available at https: /tle:///gttttt wtt.://.....oo/---O/Leeeeee/////

---

05.
35-
5.-
10-1
0.5
23
0.3
10
01-
31-
01-
(a) D == 12 and [S((x)) =3
(h) D 6 and [9((2)) 10
(c) D 3 and [[(Xa)] 100
Figure 1: We report the empirical bias and variance for the different estimators and distributions in comparison the exact gradient. The left y-axis in each plot indicates the bias while the right one shows the variance. Bias and variance results are averages taken over 1000 runs.
6.1 Synthetic: Exact Gradient Comparison
For small enough problems the exact gradient for multivariate categorical random variables can be computed via explicit cnumeration. Inspired by Niepert et al. [27]. we compare the estimates of
D Σxx. bal
Og Bx
(6.1)
to its exact value. Here, 0 are the logits that directly parametrise categorical distribution p(X) I1 p(Xa) and ba denotes arbitrarily chosen element of ((Xa). We compare the gradient estimates from IndeCateR, REINFORCE, RLOO, and Gumbel-Softmax (GS) by varying the number of distributions D and their cardinality.
In Figure we show the empirical bias and variance for the different estimators. Each estimator was given 1000 samples, while IndeCateR was only given single one. Hence, IndeCateR has the fewest function evaluations as D - K is smaller than 1000 for each configuration. IndeCateR offers gradient estimates close the exact ones with orders of magnitude lower variance for all three settings. RLOO exhibits the smallest difference in bias, yet can not compete in terms of variance. Furthermore, the computation times were of the same order of magnitude for all methods. This in stark contrast to the estimator presented by Tokui and Sato [38], where a two-fold increase in computation time of RAM with respect REINFORCE is reported.
6.2 Synthetic: Optimisation
We now study an optimisation setting [37], where the goal is to maximise the expected value
(xx
1
X: 0.499)² -X.99))
(6.2)
D
and p(X) factorizes into D independent binary random variables. The true maximum is given by p(Xa = 1) = 1 for all d. This task is challenging because of the small impact of the individual values for each X, the expected value for higher values of D. We set D = 200 and report the results in Figure 2, where we compare IndeCateR to RLOO and Gumbel-Softtaxx
In Figure 2 and subsequent figures we use the notation RLOO-F and RLOO-S, which we define as follows. If IndeCateR takes N samples, then it performs D K function evaluations with K maxa [S((X))l. As such, we define RLOO-S drawing the same number of samples as IndeCateR, which translates to N function evaluations. For RLOO-F we match the number of function evaluations, which means that it takes D K N samples. We give analogous meaning to GS-S and GS-F for the Gumbel-Sofftax gradient estimator.
IndeCateR distinguishes itself by having both the lowest variance and quickest convergence across all methods, even compared RLOO-F. Additionally, the time to compute all gradient estimates does not differ significantly for the different methods and leads to the same conclusions. It is striking to see that the Humbel-Soffmaal estimator struggles in this task, which is likely due to its bias in combination with the insensitive loss function.
7

---

IndeCateR
RLOO-F
RLOO-S
GS-F
Dreedient
0290
0280
0.60
Berations
Time 551
Figure 2: We plot the function value for different estimators against iterations (left) and time (middle). the right, we plot the variance of the gradients against iterations. Statistics were obtained by taking the average and standard error over 10 runs. IndeCateR and RLOO-S both use samples, while RLOO-F and Gumbel-Softmax (GS) use 800 samples. The number of function evaluations equal for IndeCateR, RLOO-F. and GS-F. We performed hyperparameter search for the learning rate and the temperature of GS-F Parameters were optimised using RMSProp.
6.3 Discrete Variational Auto-Encoder
As third experiment analyse the ELBO optimisation behaviour of discrete variational auto- encoder (DVAE) [32]. We optimise the DVAE on the three main datasets from the literature, being MNIST [21], F-MNIST [42] and Omniglot [20]. The encoder component of the network has two dense hidden layers of sizes 384 and 256 ending in a latent 200-dimensional Bernoulli variable. The decoder takes samples from this variable followed by layers size 256, 384 and 784. IndeCateR again uses two samples, hence we can compare to the same configurations of RLOO and Gumbel- Softmax as Section 6.2. That is, equal samples (GS and RLOO-S) and equal function evaluations (GS-F F and RLOO-F).
As evaluation metrics, we show the negated training and test set ELBO in combination with the variance of the gradients throughout training. We opted to report all metrics in terms of computation time (Figure 3), but similar results in terms of iterations are given in the appendix.
first observation is that IndeCateR performs remarkably well in terms of convergence speed as it beats all other methods all datasets in terms of training ELBO. However, can observe disadvantage the quick convergence in terms of generalisation performance when looking at the test set ELBO. RLOO-F and IndeCateR both exhibit overfitting the training data for MNIST and F-MNIST, resulting in an overall higher negative test set ELBO compared to the other methods. We speculate that the relaxation for the humbel-Softman regulariser for the network. As one would ideally like to separate discrete sampling layers from feature and not drawback of IndeCateR.
the higher variance [41] of RLOO-S act as
network regularisation, we this overfitting
IndeCateR additionally is competitive in terms of gradient variance, especially considering the number of samples that are drawn. Across all datasets, the gradient variance of IndeCateR is comparable to that of RLOO-F, even though IndeCateR takes only samples compared to the 800 RLOO-F. The only method with consistently lower gradient variance is the Gumbel-Softman trick, but only for equal function evaluations. However, that case, the Humbel-Softmas trick takes ze 1.6 times longer than IndeCateR to compute its gradient estimates.
6.4 Neural-Symbolic Optimisation
A standard experiment in the neural-symbolic literature is the addition of MNIST digits [23]. We will examine an alternative version this experiment, that is, given a set of D MNIST digits, predict the sum of those digits. During learning, the only supervision provided is the sum and not any direct label of the digits. The difficulty of the problem seales exponentially, as there are 10 states the sample space. Note that there only 10D possible labels, resulting in only very sparse supervision.
In the field of neural-symbolic AI such problems are either solved exactly [23] or by simplifying the underlying combinatorial structure [14, 24]. Exact methods scale very poorly while simplifying the

---

IndeCateR
RLOO-S
GS-S
RLOO-F
GS-F
10-1
Gradient Varfance
Training
23
101
327-
1110
1930
2902
2030
1095
5000
6930 1300 8930
0-11
1007
LCOD 2000 2006
4200 5000
9000 7300 5000
Timm855)
Timols)
Timetsi
609417
14212
384227
Gradient Varlance
6334357
Test ELGO
220 020-177
Training
10-
Timets)
Timets)
Timelsi
14.50
16.10
30x00
Gradlent Vorlancc
Triinin 11
Test ELBO
0P
202
250
302
732
1200 Time(s)
1250
1200
3750
232
150
1200 1000 Timets)
1000
1752
230
200
1000
1250
1520
3750
Time(s)
Figure 3: The top shows negated training ELBO, negated test ELBO and gradient variance for the DVAE on MNIST, each plotted against time. Rows 2 and 3 show the same plots for F-MNIST (middle) and Omniglot (bottom).
combinatorics introduces problematic biases. In contrast, we will study neural-symbolic inference and learning using sampling and unbiased gradient estimators. The overall architecture is as follows, imitating inference in general neural-symbolic system. Each of the D different MNIST images is passed through a neural classifier, which gives probabilities for each class. These probabilities used sample number between 0 and for each image. The numbers summed up and compared to the label using binary cross-entropy loss, as logical supervision is either true or false.
The hard part of this problem is the sparse supervision. In neural-symbolic AI, this sparsity is resolved by relying on classic search algorithms. However, these are not amenable to be run on parallel computing hardware, such GPUs. In turn, training has to either occur entirely on the CPU or a hefty time penalty has to be paid for transferring data from and to the GPU.
Using IndeCateR in neural-symbolee setting we achieve two things. On the one hand, we use sampling as stochastic yet unbiased search, replacing the usual symbolic search. On the other, we render this stochastic search differentiable by estimating gradients instead of performing the costly exact computation. To make this work, we exploit feature of IndeCateR that we have ignored so far.
In Equation (4.1) we can draw different samples for each of the D different terms in the sum Ed=1 corresponding to the D different variables. While drawing new samples for every variable does increase the total number of samples, the number of function evaluations remains identical. We indicate the difference by explicitly mentioning which version of IndeCateR draws new samples per variable. Note that this modification of the estimator would not have been possible following the work of Tokui and Sato [38] or Titsias, Michalis and Lázaro-Gredilla, Miguel [36].

---

IndeCateR
IndeCateR (sampling per variaalel
RUDO-F
RLOD-S
Reference
0.4
0.4
06
0.2
0.2
0.2
042
Spochs
Spachs
Epochs
Epochs
Figure 4: Test set accuracy of predicting the correct value versus number of epochs for the MNIST addition. From left to right, the plots show curves for the different estimators for 4, 8, 12, and 16 MNIST digits. We compare IndeCateR with and without sampling per variables to RLOO-F and RLOO-S. As the function f has a zero derivative almost everywhere in this case, we can not compare to the Gumbel-Softmal trick. The dashed, grey line at the top of each plot represents a hypothetical sum-classifier that has access to a 99% accurate MNIST digit classifier. The z-axis is in log-scale.
In Figure we show the empirical results. We let IndeCateR without sampling per variable draw 10 samples such that IndeCateR with sampling per variables draws D 10 samples. The number of function evaluations of both methods stays the same at D 10. In comparison, RLOO-F uses
D 10 10 samples and function evaluations. We see that IndeCateR is the only method capable of scaling and consistently solving the MNIST addition for 16 digits when taking new samples for every variable. In particular, these results show how the DiiLoo--ervvvtveeee trick estimates can significantly outperform the LEG and RAM estimates by drawing different samples for different variables, even in the independent case.
Conclusion
derived a Baoellaakwelllsatioon scheme for the case of gradient estimation with multivariate categorical random variables using the -gDerivvDevv trick. This scheme led straightforwardly to a practical gradient estimator for independent categorical random variables the IndeCateR estimator. Our experimental evaluation showed that IndeCateR produces faithful gradient estimates, especially when the number of samples is the main concern, and can be run efficiently on modern GPUs. Furthermore, IndeCateR constitutes the only hyperparameter-ffre. low-variance estimator for (conditionally) independent categorical random variables.
Three main axes can be identified for future work. First and foremost, we aim to analyse the more general case of a non-independently factorising probability distribution by applying SCateR to more structured problems, such as differentiable planning and reinforcement learning. Secondly, we plan to further study both IndeCateR and SCateR in the neural-symbolic setting and develop estimators for multivariate discrete-continuous distributions containing symbolic structures [5]. Finally, the combination control variates with the Catl-og--erivatii further improvements in variance reduction. Considering the Gumbel-Softmax Trick generally still exhibits lower variance for an equal amount of function evaluations, such combination could put REINFORCE-basCe methods on equal footing with those based on the Gumbel-Softmax Trick.
trick seems to fertile ground for
Acknowledgements
This research received funding from the Flemish Government (AI Research Program), from the Flanders Research Foundation (FWO) under project G097720N and under EOS project No. 30992574, from the KU Leuven Research Fund (C14/18/0)) (14/1) and TAILOR, project from the EU Horizon 2020 research and innovation programme under GA No. 952215. It is also supported by the Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg- Foundation.
10

---

References
[1] Martín Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg S. Corrado, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, lan Good- fellow, Andrew Harp. Geoffrey Irving, Michael Isard, Yangqing Jia, Rafal Jozefowicz, Lukasz Kaiser, Manjunath Kudlur, Josh Levenberg, Dandelion Mané, Rajat Monga, Sherry Moore, Derek Murray, Chris Olah, Mike Schuster, Jonathon Shlens, Benoit Steiner, Ilya Sutskever, Kunal Talwar, Paul Tucker, Vincent Vanhoucke, Vijay Vasudevan, Fernanda Vié- gas, Oriol Vinyals, Pete Warden, Martin Wattenberg, Martin Wicke, Yuan Yu, and Xiaoqiang Zheng. TensorFlow: Large-scale machine learning on heterogeneous systems, 2015. URL https: /www. tensorflow org/ Software available from tensorflow.org
[2] Yoshua Bengio, Nicholas Léonard, and Aaron Courville. Estimating or propagating gradients through stochastic neurons for conditional computation. arXiv, 2013.
[3] David Blackwell. Conditional expectation and unbiased sequential estimation. The Annals of Mathematical Statistics, 1947.
[4] George Casella and Christian P Robert. Rao-blackwellisationn of sampling schemes. Biometrika, 1996.
[5] Lennert De Smet, Pedro Zuidberg Dos Martires, Robin Manhaeve, Giuseppe Marra, Angelika Kimmig, and Luc De Readt. Neural probabilistic logic programming discrete-continuous domains. UAI, 2023.
[6] Alek Dimitriev and Mingyuan Zhou. Carms: Caregoricalamiihherrerreenneoo multi-sample gradient estimator. NeurlPS, 2021.
[7] Aleksandar Dimitriev and Mingyuan Zhou, Arms: Antiheeii-ernffore-mlliiaaaaa gradient for binary variables. ICML, 2021.
[8] Zhe Dong, Andriy Mnih, and George Tucker. Disarm: An antithetic gradient estimator for binary latent variables. NeurlPS, 33, 2020.
[9] Zhe Dong, Andriy Mnih, and George Tucker. Coupled gradient estimators for discrete latent variables. NeurIPS, 2021.
[10] Artur d' Avila Garcez, Sebastian Bader, Howard Bowman, Luis C Lamb, Leo de Penning, BV Illuminoo, Hoifung Poon, and COPPE Gerson Zaverucha. Neural-symbolic learning and reasoning: a survey and interpretation. Neuro-Symbolic Artificial Intelligence: The State of the Art, 2022.
[11] Will Grathwohl, Dami Choi, Yuhuai Wu, Geoffrey Roeder, and David Duvenaud. Backpropa- gation through the void: Optimizing control variates for blxck-box gradient estimation. ICLR, 2018.
[12] Karol Gregor, Ivo Danihelka, Andriy Mnih, Charles Blundell, and Daan Wierstra. Deep autoregressive networks. JCML, 2014.
[13] Shixiang Gu, Sergey Levine, Ilya Sutskever, and Andriy Mnih. Muprop: Unbiased backpropa- gation for stochastic neural networks. arXiv, 2015.
[14] Jiani Huang, Ziyang Li, Binghong Chen, Karan Samel, Mayur Naik, Le Song, and Xujie Si. Scallop: From probabilistic deductive databases to scalable differentiable reasoning. NeurIPS, 2021.
[15] Iris AM Huijben, Wouter Kool, Max B Paulus, and Ruud JG Van Sloun. A review of the gumbel-max trick and its extensions for discrete stochasticity machine learning. IEEE TPAMI, 2022.
[16] Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparameterization with gumbel-softmax. ICLR, 2017.
[17] Wouter Kool, Herke van Hoof, and Max Welling. Buy reinforce samples, get baseline for free! ICLR Deep RL Meets Structured Prediction Workshop, 2019.

---

[18] Wouter Kool, Herke van Hoof, and Max Welling. Estimating gradients for discrete random variables by sampling without replacement. ICLR, 2020.
[19] Richard E Ladner and Michael J Fischer. Parallel prefix computation. Journal of the ACM (JACM), 27(4):831-836 1980.
[20] Brenden M Lake, Ruslan Salakhutdinov, and Joshua B Tenenbaum. Human-level concept learning through probabilistic program induction. Science, 35066266):1332-3333 2015.
[21] Yann LeCun. The mnist database of handwritten digits. http://yann. lecun. com/exdb/nnist/, 1998.
[22] Chris J Maddison, Andriy Mnih, and Yee Whye Teh. The concrete distribution: A continuous relaxation of discrete random variables. ICLR, 2017.
[23] Robin Manhaeve, Sebastijan Dumancic, Angelika Kimmig, Thomas Demeester, and Luc De Raedt. Deepproblog: Neural probabilistic logic programming, advances in neural informa- tion processing systems, 31, 2018.
[24] Robin Manhaeve, Giuseppe Marra, and Luc De Raedt. Approximate inference for neural probabilistic logic programming. KR, 2021.
[25] Andriy Mnih and Karol Gregor. Neural variational inference and learning in belief networks. ICML, 2014.
[26] Andriy Mnih and Danilo Rezende. Variational inference for monte carlo objectives. Interna- tional Conference on Machine Learning, 2016.
[27] Mathias Niepert, Pasquale Minervini, and Luca Franceschi. Implicit mle: backpropagating through discrete exponential family distributions. NeurlPS, 2021.
[28] John Paisley, David M Blei, and Michael Jordan. Variational bayesian inference with stochastic search. ICML, 2012.
[29] Radhakrishna Rao. Information and accuracy attainable in the estimation of statistical parameters. Bulletin the Calcutta Mathematical Society, 1945.
[30] Rajesh Ranganath, Sean Gerrish, and David Blei. Black box variational inference. AISTATS, pages 214-822,22 2014.
[31] Lorenz Richter, Ayman Boustati, Nikolas Nüsken, Francisco Ruiz, and Omer Deniz Akyildiz. Vargrad: a low-variance gradient estimator for variational inference. NeurlPS, 2020.
[32] Jason Tyler Rolfe. Discrete variational autoencoders. ICLR, 2017.
[33] Francisco J. R. Ruiz, Michalis K. Titsias, and David M. Blei. The generalized reparametcrizztioo gradient. NeurlPS, 2016.
[34] Tim Salimans and David A Knowles. On using control variates with stochastic approximation for variational bayes and its connection to stochastic linear regression. arXiv, 2014.
[35] Jiaxin Shi, Yuhao Zhou, Jessica Hwang, Michalis Titsias, and Lester Mackey. Gradient estimation with discrete stein operators. NeurIPS, 2022.
[36] Titsias, Michalis and Lázaro-Gredilla, Miguel. Local Expectation Gradients for Black Box Variational Inference. NeurIPS, 2015.
[37] Titsias, Michalis and Shi, Jiaxin. Double control variates for gradient estimation in discrete latent variable models. AISTATS, 2022.
[38] Seiya Tokui and Issei Sato. Evaluating the variance of likelihood-ratio gradient estimators. (CML,2017
[39] George Tucker, Andriy Mnih, Chris J Maddison, John Lawson, and Jascha Sohl-Dickstein. Rebar: Low-variance, unbiased gradient estimates for discrete latent variable models. NeurIPS, 2017.
12

---

[40] Ronald J. Williams. Simple statistical suudient-followiig algorithms for connectionist reinforce- ment learning. Reinforcement learning, 1992.
[41] Jingfeng Wu, Wenqing Hu, Haoyi Xiong, Jun Huan, Vladimir Braverman, and Zhanxing Zhu. On the noisy gradient descent that generalizes as sgd. In ICML. PMLR, 2020.
[42] Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: novel image dataset for benchmarking machine learning algorithms. arXiv preprint 770.77777 2017.
[43] Mingzhang Yin and Mingyuan Zhou. Arm: Augment-reinfforc-mmerrg gradint for stochastic binary networks. ICLR, 2019.
[44] Mingzhang Yin, Yuguang Yue, and Mingyuan Zhou, Arsm: Augment-reinforce swap-merge estimator for gradient backpropagation through categorical variables. ICML, 2019.
[45] Mingzhang Yin, Nhat Ho, Bowei Yan, Xiaoning Qian, and Mingyuan Zhou. Probabilistic best subset selection gradient-basel optimization. arXiv, 2020.
13


Reviews:
[{"review_id": "1Sbrprq6p6", "reviewer": "Reviewer_Z21m", "summary": "This paper develops a new efficient estimator for gradients of an expectation computed over a multivariate discrete random variable. The gradients are computed wrt the continuous parameters of the discrete distribution of interest.\n\nPrevious work consists of two major threads\n- unbiased estimators, such as REINFORCE (aka the score function trick or log-derivative trick)\n- biased estimators, such as relaxed Gumbel-softmax trick aka \"concrete\" random variables [refs 15,20]\n\nTo build on these, this paper presents an approach that is:\n* formally unbiased (like REINFORCE, unlike GS) \n* has low variance (unlike REINFORCE)\n* no free hyperparameters (other than the number of Monte Carlo samples), unlike control variate extensions of REINFORCE\n\nIn Sec 3, the general approach, called CateR, is presented.\nThe big idea is to Rao-Blackwellize REINFORCE across each dimension of the multivariate discrete vector X being sampled. See Eq 3.1 for the estimator. \n\nIn Sec 4, a straightforward specialization of the estimator to a model that assumes each dimension is *independent*, caled IndeCateR, is presented. Example 4.2 gives nice intuition. This requires nested sums over the dimensions D, the K possible values of each variable, and N sampled values of remaining variables, with runtime O(DKN).\n\nExperiments in Sec 6 assess:\n* empirical bias/variance on synthetic problems (Fig 1)\n* performance in optimization on a toy problem (Fig 2)\n* performance in training of discrete VAEs (Fig 3)\n* a \"neuro-symbolic\" model that tries to compute the sum of 10 MNIST digit images, by sample a predicted digit label (discrete value in 0-9) for each image then adding\n\nAcross the board, the experiments suggest the estimator is competitive in performance when computation cost is similar to its alternatives.", "questions": "\n### Q1: How did you compute bias and variance in Fig 1?\n\nPresumably your estimated gradient is a vector, not a scalar.\nDid you just add or average each component's bias/variance to get the scalar metrics reported here?\n\n### Q2: Can you try to give insight into why IndeCateR has lowest variance in Fig 1 and 2, but GS has lower variance with DVAEs in Fig 3?\n\nWhat is the key difference here?\n\n\n### Q3: Why do we need sampling at all in Sec 6.4? And why frame as a binary classifier?\n\nI'm fine with what's presented in Sec 6.4 as a proof of concept that your approach can work on this problem.\n\nBut is there an *advantage* to formaluating the problem by requiring each per-image predictor to produce a random sample, that is then summed? Why not just have each per-image classifier produce the expected value of the categorical distribution over digits 0-9, and sum that across images?\n\nAlso, why use a binary (right/wrong) signal to supervise? Why not use a more continuous error metric, since if the true sum is 33 but I predict 32 I'd probably prefer that vastly compared to predicting 0.\n\n\n\nMinor questions\n\n* Why isn't GS-S shown in Fig 2?", "limitations": "Could say more about limitations in Sec 7. There's at least 1 paragraph worth of room for it.\n\n", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "\nI found a lot to like about this paper.\n\n+ Attacks a significant problem: many models need such a gradient estimator and current methods (like REINFORCE) are known to be difficult due to high variance\n+ Elegant yet simple method: derivable from first principles and interpretable as Rao-Blackwellization\n+ Comprehensive experiments on toy data help gain intuition about when/why the method works\n+ Overall message and formal mathematics are both clearly communicated throughout\n+ Effort to make costs fair for all methods (in terms of num func evaluations and/or num samples) is appreciated\n\nThanks to the authors for their hard work\n", "weaknesses": "\nOverall I don't think there are show-stopping weaknesses here. I'll list some issues below, but I'd overall rate these as definitely worth addressing but minor.\n\n### Improve discussion of AI accelerators\n\nThe paper throughout refers to \"modern AI accelerators\" without much elaboration or citation, leaving unfamiliar readers in the dark. I think there could be many different kinds of hardware accelerator the authors are thinking of... \n\n* What does it mean that this approach can be implemented on a modern AI accelerator? Would this be true of alternatives? like REINFORCE or GS?\n* How would such accelerators improve the runtime of IndeCateR from O(DKN) to O(log D + log K + log N)? Aren't they just reducing constant factor runtime by moving computation from software to hardware?\n\n### Claim that temperature hyperparameter of GS methods is difficult to tune needs elaboration\n\nIn line 172-173, GS / concrete methods are criticized because \"tuning of this [temperature] hyperparameter\" is \"highly non-trivial in practice\".\n\nCan you provide some evidence for this claim?\nI don't doubt that it *could* be sensitive, but I wonder if your experiments could reveal more about this. For example, in Fig 1 or Fig 2 you could show GS with tuned hyperparameter compared to GS with a reasonable default value.\n\n### Is there recent work extending GS/concrete that's worth discussing/comparing?\n\nThe concrete distribution / GS methods [refs 15,20] were published about 6 years ago, in 2017.\n\nSeems like the current related work discussion doesn't really touch on any progress that might have been made since 2017. I'm not aware off the top of my head of such work, but I plan to dig in more during discussion period to see if there's relevant work.\n\nIf so, definitely seems worth citing a few more papers. If not, perhaps highlighting the lack of further progress there is interesting.\n\n\n### Presentation quality decent but needs refinement to catch isolated issues\n\nAt a few spots there are incomplete thoughts or awkward phrasings, such as \n* line 41\n* line 177\n\nIn further revision, please read carefully to catch such issues and spare a future reader any confusion.\n\n\n### DVAE experiments need more details/elaboration\n\n* Need to motivate why the DVAE is an interesting model\n* Does the original DVAE recommend a specific gradient estimator? If so, what?\n* For encoder arch, are there really 3 *hidden* layers, or just 2 hidden layers and one output layer?\n* Why 2 samples for IndeCateR instead of just 1 or many more? How sensitive is this choice?\n* Can you define the probabilistic model and the optimization problem? (perhaps in supp.). In particular, is your likelihood treating the pixels as unconstrained real floats, as floats in 0.0 - 1.0, or binary values?\n* Can you clarify the optimization algorithm used (SGD? ADAM?)? \n* Where methods compared using the same initial parameter values? Or similar sampling scheme for initialization?\n* Is there any regularization applied? (e.g. L2 penalty on encoder/decoder parameters)\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the detailed and thoughtful review and the extra effort to provide feedback aiming at improving the quality of the presentation and at sharpening some statements. Please, find below a discussion to your raised points and the answers to your questions.\n\n# Discussion about weaknesses\n\n**AI accelerators**\n\nWe acknowledge that the statements are too vague. The main AI accelerators that we have in mind are GPUs. We are going to modify the text in the following way:\n\n- Line 44: \"can be implemented efficiently by leveraging parallelisation on modern graphical processing units (GPUs).\"\n\n- Line 139-141: \"Leveraging the parallel implementation of prefix sums [1] on GPUs [2], the practical runtime can be reduced to $\\mathcal{O}(\\log D + \\log K + \\log N)$,....\"\n\n- Line 271: \"these are not amenable to be run on parallel computing hardware, such as GPUs.\"\n\n- Line 294: \"modern GPUs.\"\n\n[1] https://en.wikipedia.org/wiki/Prefix_sum\n\n[2] Ladner, Richard E., and Michael J. Fischer. \"Parallel prefix computation.\" Journal of the ACM (1980).\n\n**Tuning of hyperparameters of GS**\n\nExperimental support for this claim was not explicitly provided for simplicity of exposition. However, we did encounter the difficulties of temperature tuning during our experimental process, for instance in the benchmarks in Figure 2. In particular, many of the values in the tested range $[10, 1, 0.1, 0.01]$ led to almost random optimisation behaviour due to the sensitivity of the loss. We picked the best performing value of 0.1 and made this clearer in the appendix.\n\n\n**Recent related work**\n\nThe page limit did prevent us from providing a more extensive overview of possibly related work. We have added a more complete related work section to the appendix (Appendix B.1).\n\n**Isolated issues**\n\nThanks for spotting them! We replaced them as follows:\n- Line 41: “reparametrisation for categorical distributions, which we discuss further in the related work (Section 5)”\n\n- Line 176-177: “Firstly, two synthetic experiments (Section 6.1 and Section 6.2) will be discussed.”\n\n**DVAE experiments**\n\n* The DVAE is a classical benchmark for gradient estimation methods, as it can easily scale in dimensionality [1, 2]. Moreover, the neural components introduce a complex loss landscape to optimise over.\n\n* The encoder architecture indeed has 2 true hidden layers and one output layer, we rephrased the statement as follows:\nLine 233-235: “The encoder component of the network has two dense hidden layers of sizes 384 and 256 ending in a latent 200-dimensional Bernoulli variable.”  \n* Two samples were chosen for IndeCateR in order to perform a sample equivalent comparison to RLOO, which requires at least two samples. This information was added to Appendix A.1 (Hyperparameters). It is an interesting question to analyse the sensitivity of IndeCateR to the number of samples in future work. \n* Our likelihood training is treating the pixels as floats (probabilities) between 0.0 and 1.0.\nWe have adjusted our explanation by adding the following to Appendix A.2, Modelling:\n“Finally, following the literature, the output of the decoder is interpreted as the logits for 784 binary random variables and optimised using an ELBO loss function, which is an expected value. The correct probabilities are given by the normalised and binarised pixel values of the original image.”\n\n\n* We only applied the same sampling scheme and also did not use any regularisation, as this could further obscure the impact of using different estimates. These details were also added to the appendix (Appendix A.2, Hyperparameters).\n\n[1] \"Categorical Reparameterization with Gumbel-Softmax.\" ICLR (2016).\n\n[2] \"VarGrad: a low-variance gradient estimator for variational inference.\" NeurIPS (2020).\n\n\n# Questions\n\n**Q1: bias/variance Fig. 1**\n\nWe followed the methodology proposed in [3], namely the cosine distance between the estimated and true gradient vector was computed to obtain a scalar metric. This follows the intuition that, during optimisation, we are mainly interested in the direction of the computed gradients.\n\n\n[3] \"SIMPLE: A Gradient Estimator for k-Subset Sampling.\" ICLR 2022.\n\n**Q2: comparison between IndeCateR and GS in terms of variance**\n\nThat is indeed a good observation, we speculate that the reason lies in the landscape of the loss function. In Figure 1 and 2, the loss is a direct function of the discrete random variables and behaves more erratically for different instantiations of the variables. In Figure 3, the neural decoder of the DVAE ‘smoothens’ the optimisation, which seems to favour GS.\n\n**Q3: Why sampling? Why binary classifier?**\n\nRegarding the question about sampling. In principle, it is possible to formulate this specific addition problem as suggested. However, our setup is more conceptual in nature. The symbolic component in a neural-symbolic system reasons over the domain of each random variable and the probabilities of those domain elements, not over a statistic. We want to showcase that it is possible to apply sampling in combination with gradient estimation to scale probabilistic neural-symbolic inference and learning tasks. These tasks are known to be hard due to their combinatorial nature [4, 5].\n\nRegarding the question about binary classifier. It is possible to formulate the problem as a “regression” task (where the sum is regarded as a real value). However, our purpose is again different here. The experimental setup for 6.4 mimics exactly how inference and learning would be in a neural-symbolic setting [6]. Such systems are trained on example logical statements that are true or false with a given probability, which translates to our binary supervision signal.\n\n[4] \"Scallop: From probabilistic deductive databases to scalable differentiable reasoning.\" NeurIPS (2021).\n\n[5] \"A-nesi: A scalable approximate method for probabilistic neurosymbolic inference.\" arXiv (2023).\n\n[6] \"Deepproblog: Neural probabilistic logic programming.\" NeurIPS (2018).\n"}, {"review_id": "wK2wiJcztK", "reviewer": "Reviewer_JDGY", "summary": "The authors derive a gradient estimator for discrete random variables that sums out one dimension while keeping a sample for the other dimensions fixed. Their estimator works for generally fully factorised distributions, and they derive a variant for fully independent distributions, with which they perform experiments on the discrete VAE and a neurosymbolic task.", "questions": "- Experiments: Why not compare to RAM, as it is closest to the method? \n- Figure 1: What are the 2 y-scales?\n- Line 199: Do you assume one-hot encoded X_d? \n- Line 235: You claim IndeCateR uses two samples, but I do not see how that works. There are 200 dimensions, so you will get 200 samples if you resample per dimension. Or do you set N=2, and use a pivot like in LEG? \n- Did you evaluate the MNIST experiments on multiple runs? I do not see error bars here. These MNISTAdd experiments can have significant variance between runs, so I believe having at least 10 runs is necessary before claiming IndeCateR is the only method that can scale to 16 digits.\n- Clarify that the MNIST experiments are different from the multi-digit MNISTAdd experiments discussed in [1] (it's not $100x_1 + 10x_2 + x_3+100x_4+10x_5+x_6$, but rather $\\sum_i x_i$). These have quite different optimisation properties (the multi-digit MNISTAdd problem has $10^{2/D}-2$ labels rather than $10D+1$)\n\n[1] Manhaeve, R., Dumančić, S., Kimmig, A., Demeester, T., & De Raedt, L. (2021). Neural probabilistic logic programming in DeepProbLog. Artificial Intelligence, 298, 103504.\n\nTypos:\n- Line 177: Unfinished sentence\n- Line 207: RLOO-F mentioned before its introduction\n- Line 219: Comma after samples\n- Line 265: Comma instead of point", "limitations": "I would say the limitations are adequately addressed.", "rating": 4, "confidence": 5, "soundness": 3, "presentation": 4, "contribution": 1, "strengths": "The paper is very easy to follow and well-motivated. The estimator is quite interesting and competitive with the strong RLOO estimator. The experiments are useful to the community, and especially showing that likelihood-ratio-based methods work for neurosymbolic methods is a useful insight.\n", "weaknesses": "I'm afraid that the paper is very limited in novelty. The approach presented is almost the same as Local Expectation Gradients (LEG) [1], but LEG is not discussed in the paper. From my understanding, this is how they compare:\n\nSimilarities:\n- The CatLog-Derivative Trick (Eq 3.5) is the LEG (Eq 9) under a fully factorised distribution / autoregressive model.\n- The IndeCateR (Eq 4.1) is precisely the simplification of LEG for fully independent distributions in Eq 11\n- LEG also connects the estimator to Rao-Blackwellization\n\nDifferences:\n- LEG uses a 'pivot' sample and then sums over dimensions, while CatLog resamples for each dimension\n- LEG (like RAM) did not study the shared parameter setting, although, in my opinion, this is a trivial extension by backpropagation\n\nTherefore, I don't think the paper can claim a new trick, as (at best) it slightly modified an established work. That is not to say the results of this paper are not useful but need to be recontextualised, given that the method is not novel. Suggestions are a more thorough experimental setup or a focus on neurosymbolic tasks (which are somewhat understudied in the literature on discrete gradient estimation). \n\n[1] Titsias, M.K., & Lázaro-Gredilla, M. (2015). Local expectation gradients for black box variational inference. Advances in neural information processing systems, 28.\n\nEDIT: The author rebuttal showed that CatLog indeed has some novelty in its sampling mechanism, and I increased my score from 3 to 4. I still think this paper lacks novelty: While CatLog has some novelty, there are no experiments that use it. The only experiments are with IndeCateR, but that method is not novel (LEG and REM on independent distributions are the same as IndeCateR as the authors acknowledge in their rebuttal). IndeCateR-D has some novelty compared to LEG and REM in sampling, but this method is only tested in a single experiment and is not highlighted in the writing as the focus of the paper. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the dedicated time and for bringing the related work on local expectation gradients (LEG, NeurIPS 2015) [1] to our attention. We also thank them for their appreciation about the clarity, significance and quality of our work. Please, find below a discussion on the relation between CatLog and LEG and the answers to your questions.\n\n# Comparison between CatLog and LEG\n\nThanks for pointing us to LEG! Indeed, LEG and IndeCateR are related. However, CatLog and LEG are two substantially different tricks/methods for the following reasons:\n\n1. LEG does not make full use of the autoregressive parametrisation of the distribution, as it obtains samples (aka pivots) by first instantiating all variables and subsequently performing evaluation through the computation of a weighted average based on the Markov blanket. CatLog instead makes full use of the autoregressive parametrisation by interleaving sampling and evaluation. LEG is based on three distinct stages: sampling, evaluation and weighted averaging. In contrast, CatLog has only two intertwined stages based on sampling and evaluation. Another way/analogy to look at them is that LEG is inspired and related to Gibbs sampling, whereas CatLog is based on ancestral sampling. Please, refer to the detailed analysis of LEG in the attached PDF, which will be included in the Appendix of our paper and also the table underneath summarizing the main differences.\n\n2. The two methods have different computational complexity. Indeed, computing the weighted average in LEG requires an additional $O(D)$ cost, which contributes to an overall computational complexity of $O(ND^2K)$. Therefore, the CatLog-Derivative trick makes a better use of the structure, resulting in improved efficiency over LEG, as scaling only linearly with the number of variables.\n\n3. As the reviewer mentioned, the sampling per dimension introduced by CatLog is different from the pivot samples used by LEG. This theoretical difference also yields significant practical differences in performance, even in the case of an independently factorising distribution. This difference can be seen in Section 6.4. There, the ‘IndeCateR’ estimator corresponds to pivot samples (LEG), while ‘IndeCateR-D’ draws new samples per dimension (CatLog). IndeCateR-D is the only estimator that can consistently tackle the problem when increasing the dimensionality, showing that CatLog is both theoretically and practically different from LEG. \n (RESAMPLING STUFF? SEE ALSO DOUBTS BELOW)…\n\n**Table summarizing the main differences**\n\n| Name  |  Trick | Computational Complexity | Relation to Sampling | \n|---|---|---|---|\n| LEG  | $\\sum_{d=1}^D E_{(X_{<d},{\\color{red}X_d'},X_{>d})\\sim p(X_{<d},{\\color{red}X_d'},X_{>d})} \\{ E_{X_d\\sim {\\color{blue}p(X_d\\mid X_{\\neq d})}}[f(X)\\partial_\\lambda \\log p(X_d\\mid X_{<d})] \\}$  | $O(ND^2K)$  | Gibbs sampling  | \n| CatLog  | $\\sum_{d=1}^D E_{(X_{<d},{\\color{red}X_d},X_{>d})\\sim p(X_{<d},{\\color{red}X_d},X_{>d})} \\{ [f(X_{\\neq d}, X_d)\\partial_\\lambda \\log p(X_d\\mid X_{<d})] \\}$ |  $O(NDK)$ | Ancestral sampling | \n\nWe made the following modifications to the text:\n\nThe attached PDF containing the formal proof of the theoretical difference between CatLog and LEG is added to the Appendix (Appendix B.2).\nWe highlight the difference between taking samples per dimension (CatLog) and not doing so (LEG) in Section 6.4 by further detailing the difference between IndeCateR and IndeCateR-D following our above answer.\n\n# Answers to Questions\n\n**Experiments: Why not compare to RAM, as it is closest to the method?**\n\nWhen not taking new samples per dimension, CatLog, LEG and RAM all collapse to the same estimate for an independently factorising distribution. In Section 6.4, we look at both cases with (IndeCateR-D) and without sampling per dimension (IndeCateR, RAM and LEG) per dimension and observe that drawing new samples essentially makes the difference between being able to solve the problem or not. As such, CatLog does provide a measurable improvement over RAM and LEG.\n\n**Figure 1: What are the 2 y-scales?**\n\nThe left y-scale concerns the bias while the right one looks at variance. We have added these labels to the figure for clarity.\n\n**Line 199: Do you assume one-hot encoded X_d?**\n\nWe do not use one-hot encoded vectors throughout the paper, only direct elements of the categorical domains.\n\n**Line 235: You claim IndeCateR uses two samples, but I do not see how that works. There are 200 dimensions, so you will get 200 samples if you resample per dimension. Or do you set N=2, and use a pivot like in LEG?**\n\nWe use IndeCateR without drawing new samples every dimension in the binary DVAE experiment. In essence, we take 2 samples of the joint distribution and for dimension $d$, we use the components $\\neq d$ to perform the estimation. This choice was made based on the empirical observation that drawing new samples per dimension in the case of binary random variables did not give a measurable improvement.\n\n**Did you evaluate the MNIST experiments on multiple runs? I do not see error bars here. These MNISTAdd experiments can have significant variance between runs, so I believe having at least 10 runs is necessary before claiming IndeCateR is the only method that can scale to 16 digits.**\n\nWe did evaluate the MNIST experiment across 5 runs and error bars are reported in Figure 4. It does seem that, depending on the PDF viewer, these error bars do not render properly on certain zooming levels. Please try using a different PDF viewer to see the error bars that confirm IndeCateR-D consistently beats the competitors. We will also rasterize the image in the final version of the paper to avoid the potential visualisation issue.\n\n**Clarify that the MNIST experiments..**\n\nThanks for the suggestion, we will add this clarification to the main paper. \n\n# Final Comments\n\nPlease, let us know if your concerns have been addressed and if you have any further question, we would be happy to answer.\n"}, {"review_id": "DRMR86DIBA", "reviewer": "Reviewer_i3wk", "summary": "In this paper the authors provide an alternative to the log derivative trick, e.g. the REINFORCE estimator, for categorical distributions, which is unbiased and has provably lower variance than the REINFORCE estimator; the estimator is called the CatLog-Derivative trick. For the case D-dimensional multivariate categorical distributions, where each dimension is independent, the authors introduce a simplification of the CatLog-Derivative trick called IndeCateR.", "questions": "- There are a couple of typos in the paper and sentences that aren't complete, i.e. beginning of line 177\n- Figure 1 missing y labels, making it hard to parse without reading\n- It would be great to have a section in the appendix doing a brief overview of alternative methods\n- Figure 4 seems to have problems rendering. I suggest rasterizing the figure and putting it back in the appendix.\n- In general, all line plots are hard to read. I suggest increasing the thickness of the lines.", "limitations": "Yes, they have addressed the limitations of the method.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The proposed idea is elegant and simple and the authors did a great job explaining it! Actually, I'm surprised they were able to fit the proofs inside the main text, which speaks to the conciseness of the paper. I also think the authors did a good job explaining the limitations of the base CatLog trick approach and the variety of experiments were great as well.", "weaknesses": "The major weakness is that there is no experiment demonstrating the performance of the CatLog trick. While emphasis is placed on the IndeCateR trick, it would be great the CatLog trick in action. As a suggestion, maybe a variational hidden markov model?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the enthusiasm and the constructive suggestions. Please find below a comment about the weaknesses and the answers to your questions.\n\n# Comment\n\nWe acknowledge that we have primarily devoted attention to IndeCateR, instead of the more general CateR. Our primary focus was on the most expected benchmarks from the gradient estimation literature [1, 2], which turned out to all be cases of fully factorising distributions. We really like the suggestion of a variational HMM as a testbed for CateR and look forward to adding this to an extension of this work!\n\n# Questions\n\n**Typos**\n\nThanks for spotting them ! We have made the following modifications:\n- Line 41: “reparametrisation for categorical distributions, which we discuss further in the related work (Section 5)”\n- Line 176-177: “Firstly, two synthetic experiments (Section 6.1 and Section 6.2) will be discussed.”\n\n**Figure 1**\n\nThis was indeed not clear and labels were added to the figure.\n\n**Appendix about brief overview**\n\nThe page limit did prevent us from providing a more extensive overview of possibly related work. We have taken this suggestion into account and added a more complete related work section to the appendix (Appendix B.1).\n\n**Figure 4 seems to have problems rendering**\n\nThanks for the suggestion! Indeed, there was a problem with the rendering.\n\n**In general, all line plots are hard to read. I suggest increasing the thickness of the lines**\n\nThanks for the suggestion to improve the readability of the figures. We have taken it into account and modified them accordingly.\n\n[1] Jang, Eric, Shixiang Gu, and Ben Poole. \"Categorical Reparameterization with Gumbel-Softmax.\" ICLR (2016).\n\n[2] Richter, Lorenz, et al. \"VarGrad: a low-variance gradient estimator for variational inference.\" NeurIPS (2020)."}, {"review_id": "j7kMQkppNR", "reviewer": "Reviewer_szeH", "summary": "The paper discusses improved gradient estimation through multivariate categorial probability distributions. A special case of independent random variables is discussed more thoroughly and experiments are conducted only for this case. To summarize for independent variables i.e. $p(X) = \\prod_{i \\in [N]} p(X_i)$ following is my understanding: \n\n1. Assume for applying REINFORCE trick one would use $N$ many $d-$dimensional samples $x^{(n)}$ drawn from $p(X)$.\n2. This paper proposes the following: \n* Create $N$ many $d-$dimensional samples similar to 1.\n* For each variable $i$ in $[D]$ enumerate all possible values (assuming $K$ many) of variable $i$ and replace $X_i$ in each  $x^{(n)}$. Thus creating $K$-times additional samples for each variable. \n", "questions": "9. How does time complexity change due to parallelization in line 140?\n10. Line 138 end: respectively w.r.t. what?\n11. What about training accuracy for Figure 4?", "limitations": "12. Overall the method falls short of its promise. It needs much computational complexity to create additional samples and REINFORCE trick does sometimes even better than proposed method if tested on equal footing. ", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 1, "strengths": "1. The idea of looking 'inside' a joint probability distribution instead of treating it as a black-box is interesting. For independently distributed variables the paper makes use of this factorization. \n2. Experiments (Fig. 2, 3, 4) indicate that proposed method _only sometimes_ produces better gradient estimates than REINFORCE on equal footing. ", "weaknesses": "3. It would have been great to have an illustration of the case discussed in Example 4.2 to see things (and symbols) pictorially. Preferably at the start of paper. \n4. As discussed in line 139, the computational complexity of this approach is $\\mathcal{O}(D \\cdot K \\cdot N)$. This looks much expensive than what REINFORCE has which is just $\\mathcal{O}(N)$. Although for a fair comparison in experiments the authors do allow REINFORCE to have more samples which is termed as RLOO-F. Therefore in following I will only compare with such baselines.\\\na. First two rows in Figure 2 has only positive results of the proposed approach although only with slight improvements over RLOO-F.  \\\nb. In last row of Figure 2, GS-F is better (gumbel softmax on equal footing) with RLOO-F not so far behind. \\\nc. In Figure 4 the proposed method does far worse than RLOO-F! Unless it is allowed to sample $x^{(n)}$ individually for each $d$ in $[D]$. This is a serious shortcoming.  \n5. Figure 1 does not contain RLOO-F, why?\n6. The discussed benchmarks are too small and old. It would have been better to discuss a more practical and large-scale problem to solve. \n7. In Example 4.3 it will be good to not have $K = D = 3$ as it makes it more difficult to parse. Possibly make $K=2$ (i.e., binary variables).\n8. Can there by any benefits of proposed approach on cases where variables are not independent? Possibly experiments can be added to put estimator in eq. 3.5 to test in a future submission. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the time dedicated to review our paper. Please, find below a discussion about the mentioned weaknesses and the answers to the questions.\n\n# Discussion\n\nThe improvements with respect to RLOO-F are statistically significant, as can be seen from the reported standard error bars shown in all graphs. We also want to emphasise that the improvements over RLOO-F seem to increase with increasing K (domain size of categorical distributions). This can be seen both from Figure 1 and 4. In the former, the bias for RLOO-F increases with increasing K. In the latter, IndeCateR-D is the only method capable of providing consistent solutions to the MNIST addition problem. While regular IndeCateR does not beat RLOO-F in experiment 6.4, it has to be taken into account that RLOO-F also takes $10\\cdot D \\cdot N$ samples in contrast to just $10$ samples for IndeCateR. IndeCateR-D equalises both number of samples drawn and function evaluations and is as such the main competitor for RLOO-F. In the other experiments, due to the mainly binary domain of each variable, IndeCateR-D did not give meaningful improvements over IndeCateR. In the binary cases, IndeCateR takes fewer samples than RLOO-F and still manages to significantly outperform it.\n\nWith respect to the last row of Figure 3, IndeCateR does lose out to GS-S. However, the Omniglot dataset was run on an older GPU (GTX 1080 Ti) in contrast to the MNIST and F-MNIST datasets. We have rerun Omniglot on the same GPU (RTX 3080 Ti) as MNIST and F-MNIST and can see that IndeCateR can make better use of the power of newer AI accelerators as it now again outperforms all other methods while all methods exploit parallelisation where possible. We have added this figure to the paper.\nIn Figure 1, all methods were given 1000 samples while IndeCateR was only given 1. This choice was made to show that even when competitors are given more function evaluations and more samples, IndeCateR can still outperform them. In short, Figure 1 compares IndeCateR to an even stronger estimator than RLOO-F.\nThe choice of benchmarks follows the general and expected experimental setup from the gradient estimation literature [1, 2]. We would argue that the DVAE experiment in particular presents a significant challenge for gradient estimators as it has relatively high dimensionality in conjunction with a neural optimisation component.\nRegarding benchmarks. Our primary focus was on the most expected benchmarks from the gradient estimation literature, which turned out to all be cases of fully factorising distributions [1, 2]. Does the reviewer have any other particular benchmark in mind?\n\n[1] Jang, Eric, Shixiang Gu, and Ben Poole. \"Categorical Reparameterization with Gumbel-Softmax.\" ICLR (2016).\n\n[2] Richter, Lorenz, et al. \"VarGrad: a low-variance gradient estimator for variational inference.\" NeurIPS (2020).\n\n# Questions\n\n**How does time complexity change due to parallelisation in line 140?**\n\n\nOur summations can be cast as special cases of the prefix sum [3], which has a parallel implementation with complexity $O(\\log N)$ [4] when summing over $N$ terms.\n\n[3] https://en.wikipedia.org/wiki/Prefix_sum\n\n\n[4] Ladner, Richard E., and Michael J. Fischer. \"Parallel prefix computation.\" Journal of the ACM (1980).\n\n**Line 138 end: respectively w.r.t. what?**\n\n\nThe respective upper bounds are for each of the three nested sums.\n\n**What about training accuracy for Figure 4?**\nWe are interested in the generalisation performance of the classifiers, which is quantified by the test set accuracy. Training accuracy is generally not considered interesting for classification problems as it is sensitive to overfitting, hence we left it out for clarity of exposition.\n\n# Final Comments\n\nWe hope that we have addressed all of your concerns. Please, let us know if there is anything else you want to discuss.\n"}, {"review_id": "YH1aCXewIT", "reviewer": "Reviewer_8h59", "summary": "This paper proposes a variance-reduced statistic for $\\mathbb{E}_{x \\sim p(x)} [f(X)]$, which could be the gradient of a loss for example. The main idea (known as Rao-Blackwellization) is simple to understand and can be summarized thusly: the quantity can be rewritten to distinguish any dimension $d$:\n\n$E_{(x_d, x_{\\neq d}) \\sim p(x_{d} | x_{\\neq d}) p(x_{\\neq d})} [f(X)]$ = $E_{x_{\\neq d} \\sim p(x_{\\neq d})} E_{x_{d} \\sim p(x_{d} | x_{\\neq d})} [f(X)]$ \n\nNotationally, the difference in both sides is how $x_d$ is drawn. On the left hand side, $x_d$ is drawn jointly with the other dimensions on the right side: this means a one-to-one ratio of $x_d$ to $x_{\\neq d}$. On the right hand side, $x_d$ is drawn separately from the other dimensions: this allows for a many-to-one ratio of $x_d$ to $x_{\\neq d}$. In fact, when $x_d$ has finite outcomes, all of them can be used and the inner expectation (right hand side) can be computed exactly. The extra computation from the \"many-to-one\" sampling on the right hand side, is the price to pay for the variance-reduction that comes from using (averaging over) more $x_d$. And that computational price is acceptable for a categorical variable. \n\nThe authors show that the variance reduction is effective for a variety of tasks, whether it is the actual estimation of  $\\mathbb{E}_{x \\sim p(x)} [f(X)]$, or other tasks (e.g. optimization) that use the statistic for some other purpose such as stochastic optimization of a loss function. \n\n", "questions": "It is not very clear from the text, that the statistic for  $\\mathbb{E}_{x \\sim p(x)} [f(X)]$ is sometimes the gradient of a loss (e.g. ELBO). For example, line 133 refers to a gradient without a loss without explicitly making the connection to $f(X)$. Could the authors clarify this in the text?\n", "limitations": "No specific concern on negative societal impact. ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The exposition is simple and clear, and the results are varied and convincing. \n\nFigure 2 is also appreciated, as it empirically links the variance of the gradients (right panel) to the speed of the optimization (left and middle panels), which although it is common wisdom that has motivated certain algorithms (e.g. SVRG) is not a proven result for any optimizer. \n", "weaknesses": "No major weaknesses to indicate so far. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the concise explanation of our method and the positive assessment. Please, find below a remark about the formulas summarizing our method and the answer to your question.\n\n**Remark**\n\nPlease, note that the CatLog-Derivative trick can be expressed in the following way (using your same notation):\n$E_{(x_{<d},x_d,x_{>d})\\sim p(x_{<d},x_d,x_{>d})} \\{ [f(X)] \\}=E_{x_{<d}\\sim p(x_{<d})} E_{x_d\\sim p(x_d\\mid X_{<d})} E_{x_{>d}\\sim p(x_{>d}\\mid x_{<d},x_d)} \\{ [f(X)] \\}$\n\nThis emphasizes the relation to ancestral sampling, thus differentiating from other approaches like the local expectation gradients [1]\n\n[1] Titsias, M.K., & Lázaro-Gredilla, M. (2015). Local expectation gradients for black box variational inference. NeurIPS.\n\n\n**Question**\n\nWe have added the following additional details to the appendix to clarify our optimisation setup for both the DVAE and neural-symbolic experiment.\n\n1. Clarified that the loss function is the ELBO, which is itself an expected value. Additionally, the predicted probabilities used for the computation of the ELBO are clarified as well (Appendix A2, Modelling, end of paragraph).\n\n2. We explicitly added the target loss function $-\\log P(\\sum_{i = 1}^D d_i = s)$ for the neural-symbolic optimisation to the appendix and expressed it using an expected value (Appendix A.3, Modelling, end of paragraph + Eq. A.1).\n\n# Final Comments\n\nPlease, let us know if there is anything you want to discuss.\n"}]

Author rebuttal:
We thank all reviewers for their valuable feedback and want to specifically draw attention to the comparison between CatLog and Local Expectation Gradients (LEG) [1] as brought up by reviewer JDGY. Please find our theoretical analysis that formally proves the differences in the added pdf.

Indeed, LEG and IndeCateR are related. However, CatLog and LEG are two substantially different tricks/methods for the following reasons:

1. LEG does not make full use of the autoregressive parametrisation of the distribution, as it obtains samples (aka pivots) by first instantiating all variables and subsequently performing evaluation through the computation of a weighted average based on the Markov blanket. CatLog instead makes full use of the autoregressive parametrisation by interleaving sampling and evaluation. LEG is based on three distinct stages: sampling, evaluation and weighted averaging. In contrast, CatLog has only two intertwined stages based on sampling and evaluation. Another way/analogy to look at them is that LEG is inspired and related to Gibbs sampling, whereas CatLog is based on ancestral sampling. Please, refer to the detailed analysis of LEG in the attached PDF, which will be included in the Appendix of our paper and also the table underneath summarizing the main differences.

2. The two methods have different computational complexity. Indeed, computing the weighted average in LEG requires an additional $O(D)$ cost, which contributes to an overall computational complexity of $O(ND^2K)$. Therefore, the CatLog-Derivative trick makes a better use of the structure, resulting in improved efficiency over LEG, as scaling only linearly with the number of variables.

3. As reviewer JDGY also mentioned, the sampling per dimension introduced by CatLog is different from the pivot samples used by LEG. This theoretical difference also yields significant practical differences in performance, even in the case of an independently factorising distribution. This difference can be seen in Section 6.4. There, the ‘IndeCateR’ estimator corresponds to pivot samples (LEG), while ‘IndeCateR-D’ draws new samples per dimension (CatLog). IndeCateR-D is the only estimator that can consistently tackle the problem when increasing the dimensionality, showing that CatLog is both theoretically and practically different from LEG. 

| Name  |  Trick | Computational Complexity | Relation to Sampling | 
|---|---|---|---|
| LEG  | $\sum_{d=1}^D E_{(X_{<d},{\color{red}X_d'},X_{>d})\sim p(X_{<d},{\color{red}X_d'},X_{>d})} \{ E_{X_d\sim {\color{blue}p(X_d\mid X_{\neq d})}}[f(X)\partial_\lambda \log p(X_d\mid X_{<d})] \}$  | $O(ND^2K)$  | Gibbs sampling  | 
| CatLog  | $\sum_{d=1}^D E_{(X_{<d},{\color{red}X_d},X_{>d})\sim p(X_{<d},{\color{red}X_d},X_{>d})} \{ [f(X_{\neq d}, X_d)\partial_\lambda \log p(X_d\mid X_{<d})] \}$ |  $O(NDK)$ | Ancestral sampling | 

[1] Titsias, M.K., & Lázaro-Gredilla, M. (2015). Local expectation gradients for black box variational inference. NeurIPS.


Meta-review: Reviewers agreed that this paper is a nice contribution. The relationship to LEG needs to be clarified early in the paper.
Decision: Accept (poster)