In modern machine learning, we often optimize objectives that involve expectations, such as the ELBO in variational inference or the expected reward in reinforcement learning. Because these expectations are usually intractable, we rely on Monte Carlo sampling to estimate gradients.
However, sampling comes with a "noise tax." High-variance gradient estimates lead to unstable training, slow convergence, and a need for tiny learning rates. To combat this, researchers have increasingly turned to a classic statistical principle: Rao-Blackwellization.
The intuition is simple: Never sample what you can calculate analytically. If you can "average out" some of the noise in your estimator by computing a conditional expectation, the Rao-Blackwell theorem guarantees that your new estimator will have lower (or equal) variance than the original.
The Core Mechanism of Conditional Expectation
At the heart of this research direction is the Rao-Blackwell theorem. If we have an unbiased estimator $\hat{\theta}$ of a parameter, and we condition that estimator on some variable $Y$, the new estimator $E[\hat{\theta} | Y]$ is also unbiased but has lower variance.
In the context of stochastic gradients, this means identifying parts of the model's noise that don't need to be random. As Michalis Titsias and Miguel Lazaro-Gredilla demonstrate with Local Expectation Gradients (LeGrad), we can often perform an exact expectation over a single latent variable while sampling the rest. This "black box" approach leverages the model's conditional structure to smooth out the gradient signal without requiring complex, model-specific tricks.
Strategy 1: Summing the Heavy Tail
One of the most direct applications of Rao-Blackwellization is in models with discrete latent variables, such as categorical choices or word tokens. Standard REINFORCE-style estimators sample a single category, which is highly noisy if there are many options.
Jeffrey Regier and Michael I. Jordan propose a "meta-procedure" for these cases. Instead of sampling one category, they analytically sum the gradient over the most probable categories (where most of the probability mass lives) and only sample from the remaining "tail." By replacing the high-probability samples with their exact expectations, they provide a cleaner gradient signal that speeds up convergence in tasks like hard attention and semi-supervised learning.
Similarly, Lennert De Smet and colleagues show that replacing random samples with exact expectations over categories is highly compatible with modern parallel hardware, making it a computationally efficient way to achieve the "gold standard" of minimum variance.
Strategy 2: Marginalizing Noise Configurations
Sometimes the noise isn't in the latent variable itself, but in the process used to sample it. For example, the Gumbel-Softmax trick uses Gumbel-distributed noise to sample discrete variables. Many different noise configurations can lead to the same discrete outcome (the "argmax" operation is many-to-one).
Max B. Paulus and Chris J. Maddison introduced the Gumbel-Rao (GR) estimator to exploit this. By marginalizing over all noise configurations that would have resulted in the same sampled decision, they "average out" the irrelevant noise. This reduces the mean squared error of the gradient without requiring any additional evaluations of the expensive neural network.
A similar logic applies to the REBAR estimator by George Tucker and Andriy Mnih. They use a continuous relaxation as a control variate and condition it on the specific discrete choice made by the model. This "conditional marginalization" allows for the analytical integration of noise, providing much stronger variance reduction than standard baseline subtraction.
Strategy 3: Conditioning on Sufficient Statistics
In continuous models, Rao-Blackwellization can be applied by conditioning on intermediate values or symmetries.
- Reparameterization: Kevin H. Lam and Yee Whye Teh show that conditioning gradient estimators on intermediate "pre-activations" filters out stochastic noise that doesn't actually contribute to the gradient signal.
- Symmetry: When modeling data with rotations or reflections, Vinh Tong and Mathias Niepert apply Rao-Blackwellization by taking the conditional expectation of the gradient over a symmetry group. This leads to smoother loss curves in diffusion models for drug design and material science.
- Divergence Estimation: Afra Amini and Ryan Cotterell apply this to KL divergence estimation between language models. By conditioning a noisy Monte Carlo estimator on the full output logits, they produce a provably more stable signal for RLHF.
Why It Works: The Intuition of "Averaging Early"
To understand why Rao-Blackwellization is so effective, imagine you are trying to estimate the average height of people in a building.
- Standard Sampling: You pick one person at random and use their height.
- Rao-Blackwellization: You pick one room at random, and instead of picking one person, you use the known average height of everyone in that room.
Both methods are unbiased. However, the second method is much less sensitive to the "luck of the draw." If you happen to pick a room full of basketball players, you'll still get a high estimate, but you've eliminated the extra variance of picking the single tallest or shortest person within that room.
By identifying "rooms" (conditional structures) in our probabilistic models where we can compute averages analytically, we move from noisy, high-variance "point" estimates to more stable "group" expectations. As shown by Herke van Hoof and Max Welling with unordered set estimators, even the act of sampling without replacement can be viewed as a form of Rao-Blackwellization—averaging over all possible orderings of a set to ensure every unique sample contributes its maximum information to the gradient.