Training neural networks with discrete latent variables—such as binary switches, categorical labels, or graph structures—is a fundamental challenge in machine learning. Unlike continuous variables, discrete samples are non-differentiable, meaning the "gradient" cannot flow through them to update the model. For years, researchers have navigated a difficult trade-off: use biased "tricks" that are easy to compute but mathematically incorrect, or use unbiased estimators that are theoretically sound but suffer from extreme variance.
Recent research has focused on bridging this gap, creating estimators that are both unbiased and stable enough for deep learning.
The Problem of Exploding Variance
The standard tool for discrete gradients is the score function estimator (also known as REINFORCE). While it provides an unbiased estimate of the gradient, it is notoriously noisy. As Adeel Pervez notes in A Fourier View of REINFORCE, this instability often stems from higher-order terms in the objective function that act as noise.
This noise becomes catastrophic when probability parameters approach 0 or 1. In Gradient Estimation for Binary Latent Variables via Gradient Variance Clipping, Russell Kunes and colleagues identify an "exploding variance" problem where importance sampling weights diverge near the boundaries of the parameter space, causing training to stall exactly when the model should be converging.
Continuous Relaxations and Control Variates
One of the most influential solutions is the Gumbel-Softmax (or Concrete distribution), introduced independently by Eric Jang, Shixiang Shane Gu, and Ben Poole in Categorical Reparameterization with Gumbel-Softmax. It replaces the discrete "jump" with a smooth, differentiable approximation.
However, these relaxations are biased. To fix this, George Tucker and Andriy Mnih developed REBAR (REBAR: Low-variance, unbiased gradient estimates for discrete latent variable models). REBAR uses the continuous relaxation as a control variate—a baseline that subtracts out the common noise between the approximation and the true discrete sample, leaving a clean, unbiased gradient signal.
Beyond Simple Categories: Permutations and Sets
The field has recently expanded these techniques to more complex combinatorial structures.
- Permutations: Artyom Gadetsky and Dmitry Vetrov extended variance reduction to the Plackett-Luce distribution in Low-variance Black-box Gradient Estimates for the Plackett-Luce Distribution, enabling models to learn rankings and causal structures.
- Sampling Without Replacement: Wouter Kool and Max Welling introduced the unordered set estimator in Estimating Gradients for Discrete Random Variables by Sampling without Replacement, which reduces variance by ensuring the model doesn't waste computation on redundant samples.
Modern Applications: Diffusion and RL
These low-variance estimators are now critical for the next generation of generative models. In Information-Theoretic Discrete Diffusion, Albert No and his team show that rigorous information-theoretic identities can stabilize the training of discrete diffusion models for text and biology. Similarly, Oussama Zekri uses policy gradient methods in Fine-Tuning Discrete Diffusion Models with Policy Gradient Methods to align these models with complex, non-differentiable rewards, a task previously hindered by the "jagged" nature of discrete sampling.