SFESS: Score Function Estimators for $k$-Subset Sampling
Authors: Klas Wijk
Ricardo Vinuesa
Hossein Azizpour
Venue: ICLR 2025 Poster (2025)
Keywords: subset
top-k
differentiable
gradient estimation
score function estimator
variance reduction
Primary area: unsupervised, self-supervised, semi-supervised, and supervised representation learning
TL;DR: We revisit score function estimators in the setting of k-subset distributions, comparing them to existing methods based on approximate pathwise gradients and relaxed sampling.

Abstract: Are score function estimators a viable approach to learning with $k$-subset sampling? Sampling $k$-subsets is a fundamental operation that is not amenable to differentiable parametrization, impeding gradient-based optimization. Previous work has favored approximate pathwise gradients or relaxed sampling, dismissing score function estimators because of their high variance. Inspired by the success of score function estimators in variational inference and reinforcement learning, we revisit them for $k$-subset sampling. We demonstrate how to efficiently compute the distribution's score function using a discrete Fourier transform and reduce the estimator's variance with control variates. The resulting estimator provides both $k$-hot samples and unbiased gradient estimates while being applicable to non-differentiable downstream models, unlike existing methods. We validate our approach experimentally and find that it produces results comparable to those of recent state-of-the-art pathwise gradient estimators across a range of tasks.

Published as a conference paper at ICLR 2025
SFESS: ScORE FUNCTION ESTIMATORS FOR k SUBSST SAMPLING
Klas Wijk 1.2 Ricardo Vinuesa Hossein Azizpour' 1,3,3
KTH Royal Institute of Technology
2 Swedish o-Science Research Centre
Science for Life Laboratory
kwi jkkkkk. se zvinuesalmech.ktin kt... azizpour@kth.se
ABSTRACT
Are function estimators viable approach to learning with h-subset sam- pling? Sampling k-subsets is a fundamental operation that is not amenable to differentiable parametrization, impeding gradient-based optimization. Previous work has favored approximate pathwise gradients or relaxed sampling, dismissing score function estimators because of their high variance. Inspired by the suc- cess of score function estimators in variational inference and reinforcement learn- ing, we revisit them for k-subset sampling. We demonstrate how efficiently compute the distribution's 's score function using discrete Fourier transform and reduce the estimator's variance with control variates. The resulting estimator pro- vides both k-hot samples and unbiased gradient estimates while being applicable to non-differentiable downstream models, unlike existing methods. We validate our approach experimentally and find that it produces results comparable to those recent state-of-ther pathwise gradient estimators across a range of tasks.
INTRODUCTION
Subsets are essential in tasks such as feature selection (Balin et al. 2019: Huijben et al. 2019
Yamada et al. 2020), optimal sensor placement (Manohar al. [2088), learning explain CCen et al. 2018), stochastic k-nearest neighbors (Grover et al. al.] 2019), and system identification (Brunton al. 2016). Therefore, understanding and effectively manipulating subsets an important step in improving machine methods that model discrete phenomena.
cornerstone of modern machine learning is efficient learning, typically achieved through differ- entiable models optimized via stochastic gradient descent. However, not all operations useful in modeling are differentiable, necessitating gradient estimation be compatible with gradient-based optimization. For instance, discrete sampling. including k-subset sampling, is not amenable to the reparametrization trick (Kingma & Welling 2014).
Gradient estimation for Bernoulli and categorical distributions has been extensively studied (Bengio ct al. 2013 Jang et al.) 2017] Maddison et al.) Dimitriev & Zhou 2021 De Smet et al. [0223] Liu et al.] (023). These distributions are less structured than subset distributions and do not share their combinatorially large support. A Bernoulli distribution has a support size of 2, categorical n, and Æ-subset (?). Still, the methods employed in their optimization serve a blueprint for more structured distributions. Existing approaches for differentiable subset sampling (Xie & Er-
mon 2019 Ahmed al. 2023 Pervez al. 2023) use either approximate pathwise estimators relaxed sampling. While these methods are effective, they produce biased estimates and relaxed
samples respectively (see Figure []. This paper seeks address these limitations by revisiting score function estimators (Glynn 1990; Williams 1992; Klejjnen & Rubinstein, 1996). technique well-established in reinforcement learning (Sutton
1999) and variational inference (Ranganath et 2014), but overlooked for subset sampling. In this work, we cover the aforementioned research gap by posing the following question:
Can score function estimators compete with approximate and relaxed pathwise gradient estimators in s-subtet sampling despite their weaker assumptions?

---

Published as a conference paper at ICLR 2025
Morto-Carlo
Szore function esimator
REINFORCE Wiiliams 1992)
(4)
I
f
VIMCU (Mrth and Recende 2011)
basal
BLO0 [Kook 2019)
Apginimmae
Approximate pathwise gradient
ST [Bengio et 2013]
/
STGS (Jang stud. 20177]
RemMax 2001)
S
Gumbel-Sufmss [Madliison (Namada 2020)
Facation
sampling
Fr
f
Rebsced
Figure I: Gradient estimation for discrete distributions. Three prominent approaches to gradient estimation for discrete distributions: (a) approximate score function estimator, (b) pathwise gradient estimator, and (c) relaxed sampling. The examples listed estimate the gradients of Bernoulli samples, categorical samples, both. We propose score function estimator for k-subset sampling complement existing methods based on approximate pathwise derivatives and relaxed sampling (see Section 5). Because does not use pathwise gradient, it is applicable in cases when f' is non-differentiable
We propose score function estimators for k-subset sampling (SFESS) as complement to existing methods]] Our proposed approach fundamentally differs from prior works on k-subset sampling (see Table offering both exact samples and unbiased gradient estimates. Furthermore, it does not as- sume differentiable downstream models, broadening the possible applications of k-subset sampling to cases when the downstream model's gradient is unavailable or computationally expensive.
In addition to the complementary advantages of our proposed approach, research question holds significant relevance the field, as previous work advises against the use of score function esti- mators for k-subset selection due to their high variance (Xie & Ermon 2019 Niepert et al., 2021 Ahmed et al. 2023). Thus, illustrating the potential of this family of methods could facilitate further progress in direction that currently overlooked in the field.
To realize our proposal, we develop an efficient method for computing the score function based on the discrete Fourier transform (DFT) for computing the Poisson binomial distributions' PMF (Fernandez & Williams, 201O). Furthermore, we use control variates to significantly reduce the high variance the vanilla score function estimator, In summary, our contributions are the following:
Research gap We identify and address a significant research gap in k-subset sampling where score function estimators are being considered despite their conceptual simplicity, desirable properties, and broad applicability.
Approach
We propose a score function estimator for the k-subset distribution featuring an efficient DFT-based score function calculation and reduced variance using multi-sample control variates.
Results We validate our approach in multiple experimental settings and find comparable results to state-of-the oo-tth--ttt-tttt relaxed and approximate pathwise gradient methods, signifying the potential of score function estimators for k-subset selection.
2 PROBLEM STATEMENT AND MOTIVATION
The gradient estimation problem following gradient:
We are interested in learning with k-subset sampling using the
VolE (=)
(1)
where Pe. parameterized distribution over subsets with size i and f is downstream function of the subset samples. In practice, f will often be parameterized function with additional inputs besides z. The discrete distribution over subsets not amenable to the reparametrization trick
Kingmma & Welling 2014) which motivates the development of alternative gradient estimators for
Eq. (I).
"Code available wttttpp://giiiee com/klask//kkkoko wwtawiijk//eeeeeeee fk/ss
2

---

Published as a conference paper at ICLR 2025
Table 1: Method comparison. Comparison of methods for learning with k-subset sampling based the criteria: producing exact (k-hot) samples, having unbiased gradient estimates (a desirable property statistical estimators), compatibility with non-diffierntiaable objectives f, and being free from parameters requiring tuning (c.g., relaxation temperature, which may require multiple training runs to adjust). Insensitive parameters like the number of samples used for variance reduction not considered tuned.
Method
Exact samples
Unbiased
Allows non-differentiable f Tuning-free
GS (Xi & Ermon
2019
STGS
(Xie & Ermon.
2019
X
I-MLE
Niepert ct al.
2021
X
X
SIMPLE
Ahmed et al.
2023
NCPSS
Pervez al.
2023
H
SFESS (Ours)
Existing approaches and their limitations Existing approaches to learning with k-subset sam- pling generally fall into one of two categories: approximate gradient methods or relaxed sampling.
Approximate pathwise gradient methods directly modify the gradient calculation. The best known example is the straight-through estimator (Bengio et al.] (2013) which treats the sampling as an identity function during the backward pass. Recently, Liu et al. (2023) showed that straight-through estimation works first-order approximation of the gradient for Bernoulli and categorical samples. However, these approximate estimators tend to produce biased gradients.
Relaxed sampling methods replace the distribution with relaxed distribution that the reparametrization trick (Kingma & Welling, 2014) can be used to obtain a gradient. These are gradients of the relaxed samples, these gradients can be used to train model can be used with discrete samples at test time. Although this approach can often be effective, has two significant limitations. One that it requires using relaxed samples instead of discrete ones (which may not be possible depending on f), and the other that there is a discrepancy between training and test time: the model trained with relaxed sam- pling is not guaranteed to generalize to discrete samples at test time. The error of this discrepancy difficult account for.
the discrete samples of the original distribution. Regardless,
Common to both approximate pathwise gradients and relaxed sampling is the reliance on differen- tiable f. which limits their applicability to, e.g., non-differentiable settings in reinforcement learning or black-box functions. Figure I shows the forward and backward passes of the two approaches and how they differ from score function estimators. For in-depth reviews of Conte-Carlo gradient esti- mators and the Gumbel-max trick, we refer the reader to Mohamed et al. (2020) and Huijben et al. 2023) respectively.
Why use black-box gradient estimates? A natural question to ask is what potential benefits black-box gradient estimates like score function estimators provide. Although discarding the path- wise gradient theoretically reduces the dimensionality of gradient information by one (Metz et al., 2021 Liu al. 2023), also allows for non-differentiable downstream functions. Interestingly, Metz et al. (2021) find that the variance of black-box estimates is not necessarily higher than for pathwise estimators. Furthermore, score function estimators have been used extensively settings like variational inference (Ranganath et al. 2014) and reinforcement learning (Sutton et al., 1999) where they form the basis for algorithms like PPO (Schulman et al. 2017). We summarize some desirable properties of our proposed method, that stem from it being score function estimator, and compare it to existing methods in Table It is also worth noting that score function estimators have successfully been combined with pathwise estimators for Bernoulli and categorical distributions Tucker et al. 2017: Grathwohl et al. 2018).
*NCPSS draws h-hot samples, but relaxes the subset size k such that varies slightly. UUsin conditional Poisson samples in the forward pass.
Ignoring the number of samples used for variance reduction, which only needs be sufficiently high.
3

---

Published as a conference paper at ICLR 2025
0.6
0.150
1.25
Variance
0.5
1.00
0.4
0.100
0.75
0.3
0.075
0.2
0.050
0.025
0.25
0.000
SFESS
Exact
SIMPLE
SFESS
Figure 2: Toy problem comparison. Bias and variance (left) and error (right) of gradient estimates toy problem (Ahmed al. 2023) with known ground-trun gradients. methods use single sample estimates, except SFESS + VR, where control variates are computed using 32 samples. Estimates are computed using 10,000 samples, with error bars (1 std) from 10 repetitions with different random seeds.
METHOD
We are interested in devising a black-box gradient estimator for k-subset sampling with efficacy similar to the existing techniques. Here, we describe our method including how to compute the score function and reduce variance with control variables. The resulting algorithm is presented in Algorithm 2 along with Gumbel top-k sampling (Kool et al. 2019b) in Algorithm 1 for k-subset sampling.
Overview We are interested in sampling subsets of size ls given set of variables. We consider the following distribution:
(0, po (b
Σ i== = Pe (Σ b, k) Σn b, = k2
where b E {0, 13 is independently Bernoulli distributed withf parameters 0 E 1) and 1 denotes the indicator function. This equation induces a particular distribution over the (*) possible subsets using only parameters and is naturally only of many ways to do so. In sampling design, this particular approach is known as conditional Poisson sampling (Tillé 2006).
Previous work has explored approximate pathwise derivatives of various s-subset distributions' sam- ples (Xie & Ermon 2019) Ahmed et al., (023). In this work, we instead consider score function estimators that exact in expectation. Hence, want compute the score function defined the region where Σí=1 by === k;
Vo log = Vo (ob)) Vo log po (E==1 by
Bernoulli
Poisson binomial
Computing the first term is casy, since each pb(b,) is Bernoulli distributed. The second term ap- pears more challenging. is the score function of a Poisson binomial distribution, a generalized binomial distribution where the samples are not necessarily identically distributed. Several efficient methods for computing the Poisson binomial's PMF have been proposed, including approximate and recursive methods (Le Cam 1960 Wadycki al., 1973 Ahmed et al., 2023 We follow Fer- nandez & Williams (2010) and compute it using an FFT (Cooley & Tukey 1965). leveraging its
On logn) n) time-compp complexty and efficient implementation on modern hardware The gradient of the log probability is computed using automatic differentiation.
Now, being able compute the score function in Eq. 3), we can write the following score function estimator:
V pe pe, (=){ = (z) lo ~
Ve log
(4)
where N is the number of k-subset samples z ()) ~ (z) used in the Monte-Carlo estimate of the expectation. For completeness, we derive the standard score function estimator in Appendix A
We the Nvidia cuFPT implementation in PyTorch. See Appendix for pseudocode.
4

---

Published as a conference paper at ICLR 2025
Algorithm Subset sampling using Gumbel top-k
Require: Subset parameters O and size k
1:
Sample noise 9: ~ Gumbel(O, 1) for i = .,...,n
2: Compute - ArgTopK(log 0 g. k)
> A k-hot vector
3: return
Algorithm SFESS VR: Score function estimator for k-subset sampling with variance reduction
Require: Initial subset parameters and size k; and number of variance reduction samples N
repeat
2: Sample (
(z) for i I,...,N
Or conditionally with, e.g., (z|zz
3: Compute the
likelihood log Pe
i== 6(0) using Eq. (6)
4: Compute the score function Vo log (,, (2(() using Eq. and autodiff
5: Evaluate f= (x) for i ,,...,NN
Or with additional inputs, e.g. f(z, x)
6: Optimize parameters 0 using the variance-reduced gradients in Eq.
7: until convergence
b Number of steps, threshold, etc.
8: return
Efficiently computing the score function The second term of Eq. distribution. The likelihood of which can be written as:
3 follows Poisson binomial
po C b; k)
Σ po (b(1 Ei (0.0.))
(5)
Computing the PMF using Eq. 5) requires iterating all 2 binary vectors b which is prohibitively expensive. Instead, we look for more efficient method. Eq. (5) in Fernandez & Williams) (2010) gives this closed-form expression:
EE 1==1 by =
2nd
II m=1
(o Rri + pe po((m)))
(6)
1m0
where 2010 )
I.
The corresponding discrete Fourier transform (Eq. (6) in Fernandez Williams
12
DFT II
(b (bm)) )
po
25c + po (pmb)
.,....n.
efficiently solved for all & using an FFT Cooley Tukey 1965). Note that the PMF function of 0 and & so it does not need to be recomputed when evaluating Eq. (3) for different samples z. This is useful for computing the control variate in Eq. (7) where draw multiple samples with the same O.
Reducing variance with control variates The vanilla score function estimator generally suffers from high variance. While many variance reduction techniques have been proposed (Mnih & Gregor 2014 Gu et al., 2016 Tucker et al., 2017 Shi et al. 2022). we choose to employ control variates using multiple samples (Mnih & Rezende 2016 Kool et al. 2019a) in this work due its simplicity, unbiasedness, and lack of additional assumptions. In Section 4 we will see that this straightforward
approach proves highly effective. The estimator with reduced variance is shown below:
Σ Ve lolo (F(SLM)
(e [f))) v
Σ [(2()))
N
Drawing approximate Having designed our gradient estimator for samples following the distribution in Eq. ( now turn to the sampling operation in the forward pass. Sampling from

---

Conditional distributions and varaints of f Conditional k-subset distributions po(x(<) are useful extension of the model presented above that do not change the gradient estimator (the es- timated gradients are simply backpropagated through the conditioning variable). Similarly, down- Published as a conference paper at ICLR 2025
Wall dock time (ms)
Fireort
k-mmbbett
K
Decoder
Feusure selection
1PLE
SINYLE
SPESS
(b) Wall-clock time. The average wall clock time of single training step of the methods in Table 3 Despite drawing 32 samples for variance reduction, the increase in wall time from SFESS to SFESS + VR is minor.
Ar-ubbett
Facadder
{4, C
Decoder
5
(i) Vatittonal auscenooder
1.00
Fronderr
0.75
Lande
0.50
lil) Stcchatic k-nzurest neighlioes
0.25
0.00
N6 VR
VR
(2)
VR (41
VR (8) (..0..) VR (R4IV 1128)
(a) Experimental settings. We consider three main experi- mental settings in Sections 4.22 4.4 where k-subset selec- tion used before, between, and after the model's main neu- ral network component(s): i) feature selection uses ls-ubbset sampling to subsample the imput, ii) variational autoencoders uses lo-subset sampling in to Ieam discrete representation of data, and fii) k-ncarest neighbors uses susubt sampling select the nearest (labeled) neighbors an unlabeled ex- ample and classify using them.
(c) Variance reduction and gradient error. The cosine difference of the true gradient and estimated gradient using SFESS VR with different numbers of variance reduction sam- ples on the toy problem with known gradients. No VR corresponds timator. Estimates are computed using 10,000 samples, with error bars (1 std) from repe- titions with different random seeds.
the vanilla SFESS es-
the distribution described by Eq. 2 i.e., conditional Poisson sampling, presents two challenges. First, sampling procedures for generating conditional Poisson samples assume parameters such that Σ 0, = k. Second, drawing samples efficiently is more challenging than, c.g.. Gumbel top-k sampling, with most procedures using rejection sampling. In practice, we find that bypassing these problems by using Gumbel-top-k samples as approximate conditional Poisson samples gives satisfactory results and makes for a simple and efficient forward pass.
stream functions with additional inputs, e.g., f(z, x), and parameterized functions, c.g. fo. are easily incorporated and optimized alongside the k-subset distribution's parameters. We investigate both conditional distribution and neural- network parameterized functions in our experiments (Sec- tion
EXPERIMENTS
In this section. we validate our proposed estimator in three main experimental settings: feature se- lection, variational autoencoders (VAE), and stochastic k-nearest-neighhors (k-NN). In this set of problems, the k-subsse distribution is used in various ways: as the first operation in feature selec- tion. the mid-point bottleneck in VAE, and in computing the final loss in stochastic k-NN (see Figure Ba).
We use MNIST (LeCun et al., 1998) and FASIIOON MNIST (Xiao al., 2017) with the canonical train and test splits. We withhold 10,000 samples from the train set for validation. For all training, batch size of 128 and train for 50,000 steps using the Adam optimizer (Kingma & Baj 2015) with learning rate of le-4 and parameters 3, 0.9 and Bn = 0.999. We compare our proposed method with variance reduction (SFESS VR) using 32 variance reduction samples to

---

Published as a conference paper at ICLR 2025
relaxed subset sampling (GS) and its traiihh-throuuhh variant (STGS) (iie & Ermon 2019), implicit maximum likelihood estimation (I-MLE) NNeeerrt et al. 2021). SIMPLE (Ahmed et al. 2023), and SFESS without variance reduction. For ST and STGS
use the the relaxation temperature
r = 0.5, which gave the best overall results out of r E {0.1, 0.5, 1.0). For I-MLE, we set both the input and target noise temperature 1.0. As noted in Table T SIMPLE and our method have hyperparameters in need of tuning.
4.1 TOY PROBLEM
First, we consider simple toy setting with known ground-truth gradients. We adapt the toy problem
in Ahmed et al. (2023 where the gradient estimator is used to minimize Bpg(>)]]== 0- where 0 are the ground truth parameters sampled from a standard normal distribution. Using = 10 and = 5 lets us enumerate all (5) = 256 subsets and compute the ground-truth gradient. Figure shows the estimated bias, variance, and error (1 cosine similarity compared to ground-truth) of the different estimators. Figure shows the decreasing error of SFESS + VR as the number variance reduction samples increases.
4.2 FEATURE SELECTION
Sampling subset of inputs and estimating the gradients (Balm et al. 2019 Huijben et 2019 Yamada et al., 2020) is an intuitive approach to differentiable feature selection. By being differen- tiable, the selection can be jointly optimized alongside downstream network. We consider feature selection for reconstruction and where reconstruction network (28² - 200 + 200 - 28 dense ReLU network) predicts the full set of input features inputs masked by the sampled subset and both the subset parameters and reconstruction network are optimized using the reconstruction loss (binary cross entropy). Table 2 shows our results and Figure the convergence of the validation loss.
4.3 VARIATIONAL AUTOENCODERS
Variational Autoencoders (Kingma & Welling 2014) with latent variables distributed over k-subsets has been used benchmark previous work on learning with k-subset sampling (Niepert al., 2021 Ahmed et al. 2023). We use the approximate ELBO and network architecture of Nicpert et al. 2021). The encoder (28² - 512 + 256 + nd dense ReLU network) encodes the input. The outputs are reshaped to (d x d). Then, d k-subset sample of length n are drawn and decoded by the decoder (d2 > 256 > 512 > 28 dense ReLU network). The loss is the sum reconstruction loss (binary cross entropy) and the KL-divergence between each latent distribution and uniform prior. Table 3 shows our results and Figure the convergence of the validation loss. Finally, the wall-clock time is shown in Figure 3b
4.4 STOCHASTIC A- N-NEARRST-NEIGHHORR
Our final experiment stochastic k-NN (Grover al 2019). Here, we learn an embedding that opti- mizes the classification accuracy of k-NN. During training, we sample a query point {zquery, Equery } and a batch of neighbors (ax(t) neighbor: y neightoo 2= (we use n 128 our experiments) and encode them using encoder Iø (282 + 512 + 256 + d dense ReLU network). Then, we compute the Euclidean distances from the query point embedding to all neighbor candidates' embeddings (1) (2query) - 96 (1neighhtrr)))) ) and sample k-subset of neighbors using the distances as unnor- malized logits. Finally, the negated proportion of the k-subset with the same label as the query point used as a loss. The algorithm is slightly different at test time: we use the entire training set as candidate neighbors and compute the k-nearest- -eiihbrss deterministically instead of sampling k-subset. Table 4 shows the results. The convergence of accuracy on the validation set is shown in Appendix C Embeddings of the validation sets are shown in Figure 6
(8)
"Code available http:tttp///// pttttpa://iihhui wtt.c/cc/////// /tt///CAAAASSSSAAAAS Starri/aaaSS.... MMPMMMPLL M

---

Published as a conference paper at ICLR 2025
Table 2: Feature selection results. BCF on test split. The parameters n and & are the number inputs and the number of selections respectively. The means and standard deviations are computed from 5 repetitions with different random seeds. The best mean result is shown in bold and the second best mean result is underlined.
MNIST
FASHION MNIST
Method
Mean
Sid
Mean
Std
GS Xic & Ermon 2019
784
50
0.147
0.005
0.320
0.002
STGS (Xie & Ermon
2019
784
50
0.146
0.001
0.318
0.002
I-MLE Niepert et al.
2021
784
50
0.182
+ 0.010
0.323
+ 0.001
SIMPLE Ahmed ct al.
2023
784
50
0.133
+ 0.001
0.311
= 0.001
SFESS (Ours)
784
50
0.189
0.011
0.326
0.002
SFESS + VR (Ours)
784
50
0.132
0.002
0.307
0.001
GS (ie & Ermon
2019
784
30
0.168
0.004
0.336
0.002
STGS (Xic & Ermon
2019
784
30
0.173
0.005
0.335
0.004
I-MLE NNeeeet et al.
2021
784
0,206
0.010
0.341
0.005
SIMPLE Ahmed et al.
2023
784
30
0.160
0.002
0.327
0.002
SFESS (Ours)
784
30
0,214
+ 0.011
0.343
+ 0.004
SFESS + VR (Ours)
784
30
0.154
+ 0.003
0.320
+ 0.002
Table 3: VAE results. BCE KL-divergence on the test set. The parameters d, n. and are the number of latent subsets, their dimensionality, and size respectively. The means and standard deviations are computed from 5 repetitions with different random seeds. The best mean result is shown in bold and the second best mean result underlined.
MNIST
FASHION MNIST
Method
n
Mean
Std
Mean
GS (Xie & Ermon, 2019
10
10
5
97.36
- 2.08
241.72
+ 1.57
STGS (Xie Ermon
2019
10
95.05
1.57
233.68
0.53
I-MLE NNcepert al.
2021
10
10
99.74
0.77
234.88
+ 0.36
SIMPLE (Ahmed et al.
2023
10
10
5
81.90
0.10
225.19
i 0.11
SFESS (Ours)
10
10
5
205.72
+ 0.15
384.27
+ 1.20
SFESS + VR (Ours)
10
10
5
90.04
+ 2.79
227.73
+ 0.12
GS XXie & Ermon. 2019
20
20
10
86.25
= 1.03
248.63
+ 1.87
STGS Xie & Ermon.
2019
20
20
10
73.90
= 0.24
225.06
+ 0.55
I-MLE Niepert et al.
2021
20
20
10
84.55
+ 0.45
238.13
+ 1.95
SIMPLE (Ahmed et al.
2023
20
67.96
0.14
218.82
1 0.29
SFESS (Ours)
20
20
10
205.86
0.05
384.81
+.11
SFESS VR (Ours)
20
20
10
68.83
0.15
218.39
- 0.15
Table 4: I--N results. Accuracy on the test set. The parameters d, n, and are the dimensionality the embedding, the number of neighbors sampled in the training steps, and the parameter of k-NN respectively. The means and standard deviations are computed from 5 repetitions with different random seeds. The best result shown in bold and the second best mean result is underlined.
MNIST
FASHION MNIST
Method
k
Mcan
Std
Mcan
Std
GS (ic Ermon 2019
128
10
0.950
+ 0.002
0.873
- 0.002
STGS Xie & Ermon
2019
128
10
0.950
+ 0.002
0.873
+ 0.002
I-MLEE (Niepert al.
2021
128
10
0.740
+ 0.037
0.696
+ 0.023
SIMPLE (Ahmed et al. 2023
2
128
10
0.949
+ 0.002
0.871
+ 0,002
SFESS (Ours)
2
128
10
0.938
+ 0.009
0.778
0.010
SFESS + VR (Ours)
2
128
10
0.949
+ 0.002
0.869
+ 0.001
8

---

Published as a conference paper at ICLR 2025
Fashion MINIST
0.300
65
0.44
0.275
0.42
STGSS
I-LE
SIMPLE F
0.225
0.38
SFESS
STESS
0.200
0.36
0.175
0.34
0.150
0.30
10000
20000
30000
40000
50000
10000
20000
30000
40000
50000
Step
Step
Figure 4: Feature selection validation loss. Convergence BCE on validation set feature selection
with k = 30 selections (see Appendix C for & = 50) averaged over 5 repetitions with different random seeds. The results follow the trend in the toy experiment (see Figure 2
MNIST
Fashion MNIST
BGt Kt dvergeeee
STGS
I-MLE
350
375
I-MLE
STGS
SPLSS
SPESS
SFESS
300
100
75
225
10000
20000
10000
40000
50000
0
10000 20000
30000
40000
50000
Step
Step
Figure 5: VAE validation loss. Convergence of BCE + KL-divergence on the validation set with d = 20, 20, and l 10 (see Appendix C for d = 10. = 10, and k 5) averaged over 5 repetitions with SFESS is evident going from failure leam
different random seeds. The effect of variance reduction useful representations second best among the methods tested.
4.5 ADDITIONAL RESULTS
We provide few additional studies shedding light on the various empirical aspects of SFESS. First, we explore the benefit of variance reduction. Figure shows the improved alignment of the gradients with ground truth on the toy dataset. This improvement comes at the cost of increased sampling which could affect the computational burden of SFESS. Figure 35 shows the wall-clock time of SFESS and other baselines, indicating only minor increase in the total wall-clock time due to the additional sampling. Finally, while the quantitative evaluation metrics indicate the efficacy of SFESS+VR compared baselines, in Figure 6 we illustrate the quality of learned embedding.
RELATED WORK
In this section, we provide an overview of existing methods for k-subset sampling. Table Table[sshove shows qualitative comparison of the methods' different properties.
Relaxed Subset Sampling (Xie & Ermon 2019) extends the Gumbel-Softmax distribution to dis- tributions over subsets. Despite elegance, relaxed subset sampling inherits biased gradient estimation of the Gumbel-Softtax estimator. Furthermore, the top-k sampling procedure sequen- tially applies the softmax function & times, which limits scalability with respect to and potentially degrades performance (Pervez al. 2023). The temperature parameter ation strength. The relaxed samples approach uniform as 7 - oo and k-hot as T + 0.
R>0 controls the relax-
SIMPLE (Ahmed al. 2023
approximates the pathwise gradient of the sample using its exact marginals, achieving both lower bias and variance than ST Gumbel- top-k.
Neural Conditional Poisson Subset Sampling (NCPSS) (Pervez et al. 2023 relaxes k-subset
sampling in a manner different from relaxed subset sampling (Xie & Ermon 2019), allowing subset sizes slightly smaller and larger subsets than k. Then, pathwise gradient estimates used for

---

Published as a conference paper at ICLR 2025
Figure 6: Stochastic k-NN embeddings. Two-dimensional embeddings (d of the MNIST (left) and FASHION MNIST (right) validation sets Icarned by optimizing the stochastic lc-NN objective with = 10 for 30,000 training steps. The resulting embeddings form clusters of the same class. Note that some of the samples placed between clusters are indeed ambiguous examples.
differentiable optimization. The authors show that NCPSS is more scalable than relaxed subset sampling and that the subset size can be optimized alongside the distribution's 's parameters.
Implicit Maximum Likelihood Estimation (I-MLE) (Niepert et al. 1021 uses perturb-and- MAP approach that is applicable to general optimization problems, with subset sampling as a special case.
Other methods some settings, subset distribution can be modeled either the concatenation of n Bernoulli variables or the sum of & categorical variables. This way, host of gradient esti- mates for Bernoulli and categorical variables can be used (Yamada et al., 2020 Paulus al. [02T] Dimitriev & Zhou 2021; Shi et al., 2022: De Smet et al., 2023 Liu Liu et al. (023). However, neither option directly models k-subset sampling. Bernoulli variables require some constraint (e.g., loss term) limiting the subset size, and a sum of categoricals requires nk parameters and runs the risk of duplicate inclusions (Nilsson et al. 22024). Finally, there are techniques for relaxed sampling of other discrete structures like permutation matrices, trees, graphs (Paulus al. 2020
CONCLUSION
In this work, identified research gap explore the viability of score-function estimators for learning with k-subbset sampling. We devised a simple approach and showed its efficacy in a variety of tasks achieving comparable results to existing state-of-the-arr. This is significant finding not only due to the complementary properties and wider applicability of our approach but also due to its dismissal in the current literature. The main limitation of our proposed estimator is the need to draw multiple samples for variance reduction. This means we need to evaluate f multiple times, which can be costly or impossible in some settings. Another limitation is using Gumbel top-k samples as approximate conditional Poisson samples in the forward pass, which introduces some bias in practice. We believe our work paves the way for future research in differentiable k-subset sampling, such combining score-function and pathwise estimators similarly to what was done for Bernoulli and categorical distributions. (Tucker al. 2017 Grathwohl et al. 2018).
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
The authors would like thank Denis Korzhenkov for bringing our attention the differences be- tween Gumbel top-k sampling and conditional Poisson sampling. We would also like to thank Luca Franceschi for valuable feedback and for connecting us with Andrei-Marian Manolache, Ahmed Kareem, and Mathias Niepert who assisted greatly with applying SIMPLE.
This work was partially supported by the Swedish e-Science Research Centre (SeRC) and KTH Digital Futures. The computations were enabled by resources provided by the National Academic Infrastructure for Supercomputing in Sweden (NAISS), partially funded by the Swedish Research Council through grant agreement no. 2022-06725 as well the Berzelius resource provided by the Knut and Alice Wallenberg Foundation at the National Supercomputer Centre.
REFERENCES
Kareem Ahmed, Zhe Zeng, Mathias Niepert, and Guy Van den Broeck. SIMPLE: A Gradient Esti- mator for k-Subset Sampling. In International Conference on Learning Representations, 2023.
Muhammed Fatih Balm, Abubakar Abid, and James Zou. Concrete Autoencoders: Differentiable Feature Selection and Reconstruction. In International Conference on Machine Learning, 2019.
Yoshua Bengio, Nicholas Léonard, and Aaron Courville. Estimating Propagating Gradients Through Stochastic Neurons for Conditional Computation. arXiv preprint 1rXiv:1308.3432 2013.
Steven L. Brunton, Joshua L. Proctor, and J. Nathan Kutz. Discovering Governing Equations from Data by Sparse Identification of Nonlinear Dynamical Systems. Proceedings of the National Academy of Sciences, 113:3932-39313 2016.
Jianbo Chen, Le Song, Martin Wainwright, and Michael Jordan. Learning to Explain: An Information-Theoreii Perspective on Model Interpretation. In International Conference on Ma- chine Learning. 2018
James W. Cooley and John W. Tukey, An Algorithm for the Machine Calculation of Complex Fourier Series. Mathematics of Computation, 19:297-301, 1965.
Lennert De Smet, Emanuele Sansone, and Pedro Zuidberg Dos Martires. Differentiable Sampling of Categorical Distributions Using the Carloog-erivatiie Trick. In Advances in Neural Information Processing Systems, 2023.
Aleksandar Dimitriev and Mingyuan Zhou, ARMS: Mnttheic-EENNORRREMMMiii--- ent for Binary Variables. In International Conference on Machine Learning, 2021.
Gradi-
Manuel Fernandez and Stuart Williams. Closed-Form Expression for the -innomal Proba- bility Density Function. IEEE Transactions on Aerospace and Electronic Systems, 46:803-817, 2010.
Peter W. Glynn. Likelihood Ratio Gradient Estimation for Stochastic Systems. Communications of the ACM, 33:75-84, 84, 1990.
Will Grathwohl, Dami Choi, Yuhuai Wu, Geoffrey Roeder, and David Duvenaud. Backpropagation through the Void: Optimizing control variates for black-box gradient estimation. In International Conference on Learning Representations, 2018.
Aditya Grover, Eric Wang, Aaron Zweig, and Stefano Ermon. Stochastic Optimization of Sorting Networks via Continuous Relaxations. In International Conference on Learning Representations, 2019.
Shixiang Gu, Sergey Levine, Ilya Sutskever, and Andriy Mnih. MuProp: Unbiased Backpropagation for Stochastic Neural Networks. In International Conference on Learning Representations, 2016.
Iris A. M. Huijben, Bastiaan S. Veeling, and Ruud J. G. van Sloun. Deep Probabilistic Subsampling for Adaptive Compressed Sensing. In International Conference on Learning Representa- fions, 2019.
11

---

Published as a conference paper at ICLR 2025
Iris A. M. Huijben. Wouter Kool, Max B. Paulus, and Ruud J. G. van Sloun. A Review of the Gumbel-mat max Trick and its Extensions for Discrete Stochasticity Machine Learning. IEEE Transactions Pattern Analysis and Machine Intelligence, 45:1353-1374 202.
Eric Jang, Shixiang Gu, and Ben Poole. Categorical Reparameterization with Gumbel-Softmax. In International Conference on Learning Representations, 2017.
Diederik Kingma and Jimmy Ba. Adam: A Method for Stochastic Optimization. In International
Conference on Learning Representations, 2015.
Diederik P. Kingma and Max Welling, Auto- Auto-Encoding Variational Bayes. In International Confer- ence on Learning Representations, 2014.
Jack P. C. Kleijnen and Reuven Rubinstein. Optimization and Sensitivity Analysis of Computer Simulation Models by the Score Function Method. European Journal of Operational Research, 88:413-427, 1996.
Wouter Kool, Herke van Hoof, and Max Welling. Buy 4 REINFORCE Samples, Get a Baseline for Free! In ICLR Workshop Deep Reinforcement Learning Meets Structured Prediction, 2019a.
Wouter Kool, Herke Van Hoof, and Max Welling. Stochastic Beams and Where To Find Them: The Gumbel-Top-k Trick for Sampling Sequences Without Replacement. In International Conference Machine Learning, 2019b.
Lucien Le Cam. An approximation theorem for the Poisson binomial distribution. Pacific Journal of Mathematics, 10: 181-1197, 1960.
Yann LeCun, Corinna Cortes, and Chris Burges. The MNIST Database of Handwritten Digits, 1998. URL http::/yann. lec.n.eecnnncmm com/ www.////////nn/t//oeeeoo
Liyuan Liu, Chengyu Dong, Xiaodong Liu, Bin Yu, and Jianfeng Gao. Bridging Discrete and Backpropagation: Straigh-TThougee and Beyond. In Advances in Neural Information Processing Systems, 2023.
Chris J. Maddison, Andriy Mnih, and Yee Whye Tch. The Concrete Distribution: A Continuous Relaxation of Discrete Random Variables. In International Conference on Learning Representa- fions, 2017.
Krithika Manohar, Bingni W. Brunton, J. Nathan Kutz, and Steven L. Brunton. Data-Driven Sparse Sensor Placement for Reconstruction: Demonstrating the Benefits of Exploiting Known Patterns. IEEE Control Systems Magazine, 38:63-86, 2018.
Luke Metz, C. Daniel Freeman, Samuel S. Schoenholz, and Tal Kachman. Gradients Not All You Need. arXiv preprint arXiv:2111.05803 2021.
Andriy Mnih and Karol Gregor. Neural Variational Inference and Learning in Belief Networks. In International Conference Machine Learning, 2014.
Andriy Mnih and Danilo J. Rezende. Variational Inference for Monte Carlo Objectives. In Interna- tional Conference on Machine Learning, 2016.
Shakir Mohamed, Mihaela Rosca, Michael Figurnov, and Andriy Mnih. Monte Carlo Gradient Estimation in Machine Learning. Journal of Machine Learning Research, 21:1-62, 2020.
Mathias Niepert, Pasquale Minervini, and Luca Franceschi. Implicit MLE: Backpropagating Through Discrete Exponential Family Distributions. In Advances Neural Information Pro- cessing Systems, 2021.
Alfred Nilsson, Klas Wijk, Sai bharath chandra Gutha, Erik Englesson, Alexandra Hotti, Carlo Saccardi, Oskar Kviman, Jens Lagergren, Ricardo Vimuesa, and Hossein Azizpour. Indirectly Parameterized Concrete Autoencoders. In International Conference Machine Learning, 2024.
Max B. Paulus, Dami Choi, Daniel Tarlow, Andreas Krause, and Chris J. Maddison. Gradient Esti- mation with Stochastic Softmax Tricks. In Advances in Neural Information Processing Systems, 2020.
12

---

Published as a conference paper at ICLR 2025
Max B. Paulus, Chris J. Maddison, and Andreas Krause. Bhoo-Baakweelizingg the Straight-Through Through Gumbel-Softmas Gradient Estimator. In International Conference on Learning Representations, 2021.
Adeel Pervez, Phillip Lippe, and Efstratios Gavves. Scalable Subset Sampling with Neural Condi- tional Poisson Networks. In International Conference on Learning Representations, 2023.
Rajesh Ranganath, Sean Gerrish, and David Blei. Black Box Variational Inference. In International Conference on Artificial Intelligence and Statisties, 2014.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov, Proximal Policy Optimization Algorithms. arXiv preprint /rxivv/707.00000
2017.
Jiaxin Shi, Yuhao Zhou, Jessica Hwang, Michalis Titsias, and Lester Mackey. Gradient Estimation with Discrete Stein Operators. In Advances in Neural Information Processing Systems, 2022.
Richard S Sutton, David McAllester, Satinder Singh, and Yishay Mansour, Policy Gradient Methods for Reinforcement Learning with Function Approximation. In Advances in Neural Information Processing Systems, 1999.
Yves Tillé. Sampling Algorithms. In Sampling Algorithms.. Springer New York, 2006.
George Tucker, Andriy Mnih, Chris J. Maddison, Dieterich Lawson, and Jascha Sohl-Dickstein. RE- BAR: Low-variance, unbiased gradient estimates for discrete latent variable models. In Advances in Neural Information Processing Systems, 2017.
Walter J. Wadycki, B. Shah, P. Ghangurde, Edward J. Dudewicz, Nathan Mantel, Charles C. Brown, Harold J. Larson, Donald R. Barr, James W. Frane, Bernard Saperstein, I. J. Good, and Howard L. Jones. Letters to the Editor. The American Statistician, 27:123-127, 1973.
Ronald Williams. Simple Statistical
Algorithms for Connectionist Reinforce- ment Learning. Machine Learning, 8:229-256, 1992.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-MNIST: Novel Image Dataset for Bench- marking Machine Learning Algorithms. arXiv preprint arXiv:1708.07747 2017 2017.
Sang Michael Xie and Stefano Ermon. Reparameterizable Subset Sampling via Continuous Relax- ations. International Joint Conference on Artificial Intelligence, 2019.
Yutaro Yamada, Ofir Lindenbaum, Sahand Negahban, and Yuval Kluger. Feature Selection using Stochastic Gates. In International Conference Machine Learning, 2020.
13

---

Published as a conference paper at ICLR 2025
A DERIVING THE SCORE FUNCTION ESTIMATOR
In this appendix, we derive the score function estimator (Williams) 1992) which provides a Monte-
Carlo estimate of the objective's gradient. We adapt the proof from Mohamed al. (2020) (with annotations added):
VoL
Ve Σ pe (=(=){(z)
By definition of IE
(opo(z){(z))
Interchange gradient and summation
Σ Vo Vogooo(()))
By log derivative rule
(x) (f) logpoo
By definition of IE
(9)
f(z() log (z
Monte-Carlo estimate
(10)
By the law of large numbers, the Monte-Carlo estimator in Eq. (00) converges to the expected value in Eq. (9) N oc, which is exactly the value of the true gradient in Eq. (8). Hence, the estimator is an unbiased estimator of the true gradient.
B SCORE FUNCTION CALCULATION
key component of SFESS is calculating the score function in Eq. (3). The unconditional indepen- dent Bernoulli distribution renormalized by the Poisson binomial distribution. This renormaliza- tion factor is calculated following Fernandez & Williams/ (201)). Listing I outlines this calculation pseudocode.
Listing 1 PyTorch-style pscudocode for calculating the Poisson-Binomial PMF (Fernandez &
Williams 2010).
import torch
import cmath
def batbbinnprobbttee (theta, k)
n = theta. (0)
i corch.arange (n + 1) unsqueeeee (-1)
c = cmath. (2j * torch.pi / (n + 1)) prod torch. prod (theta
cxii + (1 theta), dim=1) probs = torch. fft. fft (prod) real / (n + 1)
return probs [k]
14

---

Published as a conference paper at ICLR 2025
C ADDITIONAL LOsS CURVES
MNIST
Fashion MNIST
0.300
0.450
0.275
STGS
STGS
0.225
SFESS
SFESS
0.200
SPESS
SPESS
0.150
0.125
Step
Step
Figure 7: Feature selection validation loss. Convergence of BCE the validation for feature selection with for averaged over repetitions with different random seeds.
MNIST
Fashion MNIST
220
400
GS
GS
UCE Ki-ivergence
200
STGS
180
350
SIMPLE
SIMPLE
160
SFESS VR
300
SFESS
120
80
50000
Step
Stap
Figure 8: VAE validation loss. Convergence of BCE KL-divergence the validation with d 10, v 10, and averaged over repetitions with different random seeds.
MNIST
Fashion MNIST
1.0
1.0
GS
GS
MIMEE
FIMLE
SIMPLE
SIMPLE
Acaracy
0.8
0.8
SPESS AR
SPESS VR
0.7
0.7
0.5
0.5
10000
20000
30000
40000
Stap
Step
Figure 9: k-NN validation accuracy. Convergence accuracy on validation set with 2, 128, and & = 10 averaged over 5 repetitions with different random seeds.
15


Reviews:
[{"review_id": "UNwsGpQAbx", "reviewer": "Reviewer_kBPo", "summary": "The paper proposes a black-box gradient estimator for $k$-subset sampling using a score function estimator. \nIn this approach, the discrete Fourier transform (DFT) is employed to compute the density function of the Poisson binomial distribution, and control variates is used to reduce variance.\nThe method is evaluated through multiple experiments, where it is compared against existing approaches.", "questions": "Please see Weaknesses part.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The use of a score function to address the gradient estimation problem is straightforward yet effective. To compute the probability density of the Poisson binomial distribution, the paper leverages a closed-form expression based on the discrete Fourier transform (DFT). A variance reduction technique is then applied to enhance estimation efficiency.\n2. The paper is well-written, providing a clear overview of the background, challenges, and gaps in the field, along with a detailed summary of $k$-subset sampling methods.\n3. The proposed method is validated on both synthetic and real-world dataset.", "weaknesses": "1. While the paper proposes a score function estimator for $k$-subset sampling, Equation (4) appears to be a well-established technique, commonly known as the score function estimator (SFE) [1]. \nThis suggests that the primary contribution may lie in the application of variance reduction within the Monte Carlo approximation. \nMy main concern is that the novelty of this work may be insufficient for acceptance at a top-tier conference main track.\n\n2. SFESS does not appear to demonstrate a consistently superior performance in the experimental results compared to other methods (e.g., SIMPLE). Could you clarify the specific advantages of SFESS and provide more insight into scenarios where it outperforms alternative approaches?\n\n[1]. Kareem Ahmed, Zhe Zeng, Mathias Niepert, and Guy Van den Broeck. SIMPLE: A Gradient Estimator for k-Subset Sampling. In International Conference on Learning Representations, 2023.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "le2ES5ouQN", "reviewer": "Reviewer_W34X", "summary": "This paper introduces a method for computing the score function of the k-subset distribution using a discrete Fourier transform and employs control variates to address the high variance of the vanilla score function estimator.", "questions": "1. Choice of Hyperparameter k: How do you select the hyperparameter k for different tasks? How does performance vary if k is adjusted? A deeper discussion on the choice of k would be beneficial.\n\n2. Selection of Random Seeds: How did you choose your random seeds? It would be helpful to list the specific seeds used to facilitate reproducibility and to confirm that your choices were not made deliberately.\n\n3. Performance Comparisons in Tasks: In the VAE task, it appears that SIMPLE outperforms SFESS+VR (Table 3), while for the kNN task, GS and STGS perform better (Table 4). What is the intuition behind these results, and what advantages does SFESS+VR offer in these contexts?\n\nI would be willing to increase the score if the questions above are thoroughly addressed and if more in-depth theoretical results are provided.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "SFESS broadens the potential applications of k-subset sampling, particularly in scenarios where the downstream model’s gradient is unavailable. The algorithm’s effectiveness is demonstrated through several experiments.", "weaknesses": "This paper appears to fall slightly below the standard expected at ICLR for several reasons:\n\n1. A primary concern is the lack of a solid theoretical foundation; the paper focuses mainly on numerical results without a deeper mathematical analysis. For example, there is no mathematical description or convergence rate guarantee for Algorithm 2.\n\n2. In terms of experiments, the explanations of the architecture design and choice of hyperparameters require more clarity and justification. I will outline these concerns in greater detail in the questions below.\n\n3. Additionally, the paper would benefit from further polishing. For instance, on line 204, p_{theta}(b) is introduced without prior definition. On line 206, the phrase should be “Naively.” Also, on line 221, the operation ArgTopK(log(theta+g), k) would benefit from further explanation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "49yTCNegSu", "reviewer": "Reviewer_6UyM", "summary": "This paper studies the k-subset sampling and proposes a differentiable estimator that enjoys the benefits of score function estimators and the relaxed approperiate pathwise estimator. The proposed method extends the existing differentiable optimization of Bernoulli and categorical distributions and serves as a complement to existing methods.", "questions": "In Table 1: Method Comparison, the author lists four properties (Exact Samples, ...). Can the author explain why these properties are important or preferred to have? What will happen, for example, if the estimator is non-differentiable?  \n\nWhen we need to have the gradient of some methods such as GS, STGS, or SIMPLE, can I simply use a gradient estimation approach to approximate their gradient? Does it make any difference from this method? \n\nA minor issue:\n\nI probably disagree that the variance reduction using some control variates can be considered as any contribution, since it has been well-known in the literature. However, if the VR is not employed in the SFESS method, its performance in Figure 5, is nearly the worst among all methods. How should I understand this figure?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "I am not very familiar with the topic but I believe this work has made significant contributions. In traditional k-subset sampling methods, the score function estimators are rarely considered. This paper fills this gap by proposing the proposed method. The results are validated on diverse experiments and match the SOTA relaxed and approximate pathwise gradient methods. Therefore, the method is original and significantly improves the existing approaches.", "weaknesses": "The backgrounds and introduction to the studied topic are not very friendly. It is hard for me to understand why the k-subset sampling is needed and why the existing methods (which may not be based on the score function and potentially non-differentiable) are not sufficient to the related community. I hope the author could add more examples, explicitly stating where the k-subset sampling is used and why the existing methods fail to satisfy the demond.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)