# Differentiable Sampling of Categorical Distributions Using the CatLog-Derivative Trick

arXiv: https://arxiv.org/abs/2311.12569 · HTML: https://mlsanity.com/paper/2311.12569/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 53 references that are in the map.
- First posted on arXiv 21 Nov 2023.

## Builds on (most cited first, 30 of 33)

- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Categorical Reparameterization with Gumbel-Softmax](https://mlsanity.com/paper/1611.01144/) (2016)
- [Estimating or Propagating Gradients Through Stochastic Neurons for Conditional Computation](https://mlsanity.com/paper/1308.3432/) (2013)
- [The Concrete Distribution: A Continuous Relaxation of Discrete Random Variables](https://mlsanity.com/paper/1611.00712/) (2016)
- [Neural Probabilistic Logic Programming in DeepProbLog](https://mlsanity.com/paper/1907.08194/) (2019)
- [Black Box Variational Inference](https://mlsanity.com/paper/1401.0118/) (2013)
- [Monte Carlo Gradient Estimation in Machine Learning](https://mlsanity.com/paper/1906.10652/) (2019)
- [Neural-Symbolic Learning and Reasoning: A Survey and Interpretation](https://mlsanity.com/paper/1711.03902/) (2017)
- [Discrete Variational Autoencoders](https://mlsanity.com/paper/1609.02200/) (2016)
- [Neural Variational Inference and Learning in Belief Networks](https://mlsanity.com/paper/1402.0030/) (2014)
- [Backpropagation through the Void: Optimizing control variates for black-box gradient estimation](https://mlsanity.com/paper/1711.00123/) (2017)
- [Implicit MLE: Backpropagating Through Discrete Exponential Family Distributions](https://mlsanity.com/paper/2106.01798/) (2021)
- [Variational inference for Monte Carlo objectives](https://mlsanity.com/paper/1602.06725/) (2016)
- [A Review of the Gumbel-max Trick and its Extensions for Discrete Stochasticity in Machine Learning](https://mlsanity.com/paper/2110.01515/) (2021)
- [REBAR: Low-variance, unbiased gradient estimates for discrete latent variable models](https://mlsanity.com/paper/1703.07370/) (2017)
- [VarGrad: A Low-Variance Gradient Estimator for Variational Inference](https://mlsanity.com/paper/2010.10436/) (2020)
- [Deep AutoRegressive Networks](https://mlsanity.com/paper/1310.8499/) (2013)
- [Memory Augmented Policy Optimization for Program Synthesis and Semantic Parsing](https://mlsanity.com/paper/1807.02322/) (2018)
- [MuProp: Unbiased Backpropagation for Stochastic Neural Networks](https://mlsanity.com/paper/1511.05176/) (2015)
- [Rao-Blackwellizing the Straight-Through Gumbel-Softmax Gradient Estimator](https://mlsanity.com/paper/2010.04838/) (2020)
- [Estimating Gradients for Discrete Random Variables by Sampling without Replacement](https://mlsanity.com/paper/2002.06043/) (2020)
- [The Generalized Reparameterization Gradient](https://mlsanity.com/paper/1610.02287/) (2016)
- [DisARM: An Antithetic Gradient Estimator for Binary Latent Variables](https://mlsanity.com/paper/2006.10680/) (2020)
- [Neural Probabilistic Logic Programming in Discrete-Continuous Domains](https://mlsanity.com/paper/2303.04660/) (2023)
- [Rao-Blackwellized Stochastic Gradients for Discrete Distributions](https://mlsanity.com/paper/1810.04777/) (2018)
- [Gradient Estimation with Discrete Stein Operators](https://mlsanity.com/paper/2202.09497/) (2022)
- [Probabilistic Best Subset Selection via Gradient-Based Optimization](https://mlsanity.com/paper/2006.06448/) (2020)
- [ARSM: Augment-REINFORCE-Swap-Merge Estimator for Gradient Backpropagation Through Categorical Variables](https://mlsanity.com/paper/1905.01413/) (2019)
- [ARMS: Antithetic-REINFORCE-Multi-Sample Gradient for Binary Variables](https://mlsanity.com/paper/2105.14141/) (2021)
- [Coupled Gradient Estimators for Discrete Latent Variables](https://mlsanity.com/paper/2106.08056/) (2021)

## Built on by (most cited first, 14 of 14)

- [Neurosymbolic Diffusion Models](https://mlsanity.com/paper/2505.13138/) (2025)
- [A Probabilistic Neuro-symbolic Layer for Algebraic Constraint Satisfaction](https://mlsanity.com/paper/2503.19466/) (2025)
- [ULLER: A Unified Language for Learning and Reasoning](https://mlsanity.com/paper/2405.00532/) (2024)
- [On the Hardness of Probabilistic Neurosymbolic Learning](https://mlsanity.com/paper/2406.04472/) (2024)
- [Data-Efficient Learning with Neural Programs](https://mlsanity.com/paper/2406.06246/) (2024)
- [Dolphin: A Programmable Framework for Scalable Neurosymbolic Learning](https://mlsanity.com/paper/2410.03348/) (2024)
- [Generalizing Stochastic Smoothing for Differentiation and Gradient Estimation](https://mlsanity.com/paper/2410.08125/) (2024)
- [Revisiting Score Function Estimators for k-Subset Sampling](https://mlsanity.com/paper/2407.16058/) (2024)
- [The Gradient of Algebraic Model Counting](https://mlsanity.com/paper/2502.18406/) (2025)
- [CTSketch: Compositional Tensor Sketching for Scalable Neurosymbolic Learning](https://mlsanity.com/paper/2503.24123/) (2025)
- [Zero-Variance Gradients for Variational Autoencoders](https://mlsanity.com/paper/2508.03587/) (2025)
- [EM-NeSy: Expectation Maximization for Neurosymbolic Learning](https://mlsanity.com/paper/2606.14463/) (2026)
- [Parallel Noising in Neural Markov Logic Networks](https://mlsanity.com/paper/2607.19126/) (2026)
- [Variance-Optimal Control Variates for Learning with Black-box Feedback](https://mlsanity.com/paper/2610.04766/) (2026)

## Abstract (arXiv)

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.