mlsanityData to 7 Oct 2026

Estimating Gradients for Discrete Random Variables by Sampling without Replacement

arXiv 2002.06043 ↗First posted 14 Feb 2020cs.LG stat.MLcited by 29

Not on the map. Why?

Abstract (arXiv)

We derive an unbiased estimator for expectations over discrete random variables based on sampling without replacement, which reduces variance as it avoids duplicate samples. We show that our estimator can be derived as the Rao-Blackwellization of three different estimators. Combining our estimator with REINFORCE, we obtain a policy gradient estimator and we reduce its variance using a built-in control variate which is obtained without additional model evaluations. The resulting estimator is closely related to other gradient estimators. Experiments with a toy problem, a categorical Variational Auto-Encoder and a structured prediction problem show that our estimator is the only estimator that is consistently among the best estimators in both high and low entropy settings.

Key facts. Cited by 29 papers in the map (data through 7 Oct 2026). First posted on arXiv 14 Feb 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 8; 2022: 9; 2023: 3; 2024: 1; 2025: 4; 2026: 4.

29 papers.

Sort:

By area:

  1. 2021Implicit MLE: Backpropagating Through Discrete Exponential Family Distributionscited by 97
  2. 2021A Review of the Gumbel-max Trick and its Extensions for Discrete Stochasticity in Machine Learningcited by 82
  3. 2024Self-Improvement for Neural Combinatorial Optimization: Sample without Replacement, but Improvementcited by 32
  4. 2025KL-Regularized Reinforcement Learning is Designed to Mode Collapsecited by 29
  5. 2022Gradient Estimation with Discrete Stein Operatorscited by 22
  6. 2022Sparse Graph Learning from Spatiotemporal Time Seriescited by 22
  7. 2023Differentiable Sampling of Categorical Distributions Using the CatLog-Derivative Trickcited by 13
  8. 2022Adaptive Perturbation-Based Gradient Estimation for Discrete Latent Variable Modelscited by 12
  9. 2021Storchastic: A Framework for General Stochastic Automatic Differentiationcited by 11
  10. 2021Conditional Poisson Stochastic Beam Searchcited by 11
  11. 2021Coupled Gradient Estimators for Discrete Latent Variablescited by 9
  12. 2022Bayesian Nonparametrics for Offline Skill Discoverycited by 5
17 more
  1. 2022Learning Group Importance using the Differentiable Hypergeometric Distributioncited by 5
  2. 2022Calibrate and Debias Layer-wise Sampling for Graph Convolutional Networkscited by 5
  3. 2021CARMS: Categorical-Antithetic-REINFORCE Multi-Sample Gradient Estimatorcited by 4
  4. 2026Asymmetric Prompt Weighting for Reinforcement Learning with Verifiable Rewardscited by 3
  5. 2021Scaling Structured Inference with Randomizationcited by 2
  6. 2022Learning Discrete Structured Variational Auto-Encoder using Natural Evolution Strategiescited by 2
  7. 2022Unbiased and Efficient Sampling of Dependency Treescited by 2
  8. 2023Revisiting the Gumbel-Softmax in MADDPGcited by 2
  9. 2021An Efficient Combinatorial Optimization Model Using Learning-to-Rank Distillationcited by 1
  10. 2022On Many-Actions Policy Gradientcited by 1
  11. 2025Rao-Blackwellised Reparameterisation Gradientscited by 1
  12. 2025Replacing thinking with tool usage enables reasoning in small language modelscited by 1
  13. 2023DBsurf: A Discrepancy Based Method for Discrete Stochastic Gradient Estimationcited by 0
  14. 2025Beyond Softmax: A Natural Parameterization for Categorical Random Variablescited by 0
  15. 2026Scaling GraphLLM with Bilevel-Optimized Sparse Queryingcited by 0
  16. 2026Scoring Is Not Enough: Addressing Gaps in Utility-fairness Trade-offs for Rankingcited by 0
  17. 2026Rank-Conditioned Sample Reuse for the Plackett--Luce Best-of-K Objectivecited by 0