Deep learning owes much of its success to the backpropagation algorithm, which relies on a simple geometric assumption: the optimization landscape is a smooth, continuous hill. If you want to minimize a loss function, you take a tiny step down the gradient.
But what happens when the decisions your model makes are fundamentally discrete?
Whether a model is choosing a word from a vocabulary, selecting a path through a graph, or turning a neural module on or off, these choices represent sharp, discontinuous steps. You cannot slide continuously from "word A" to "word B." In these discrete landscapes, standard gradients are zero almost everywhere and undefined at the boundaries. This creates a fundamental wall for end-to-end optimization.
To train these models, researchers rely on stochastic gradient estimators. However, these estimators frequently suffer from extreme variance—meaning the gradient updates swing wildly from one iteration to the next, crippling training stability and slowing convergence to a crawl. Overcoming this high variance is one of the most persistent challenges in modern machine learning.
The Core Problem: Why Discrete Gradients Explode
To understand why variance explodes, we must look at how we estimate gradients when backpropagation fails. Suppose we want to optimize the parameters $\theta$ of a distribution $q_\theta(x)$ to minimize the expectation of a cost function $f(x)$, where $x$ is a discrete random variable:
$$\min_\theta \mathbb{E}_{x \sim q_\theta(x)} [f(x)]$$
Because we cannot differentiate $f(x)$ directly with respect to $\theta$ (since $x$ is discrete), we typically fall back on the score function estimator, also known as the REINFORCE algorithm. By a simple algebraic identity, we can rewrite the gradient of the expectation as:
$$\nabla_\theta \mathbb{E}_{x \sim q_\theta(x)} [f(x)] = \mathbb{E}_{x \sim q_\theta(x)} [f(x) \nabla_\theta \log q_\theta(x)]$$
This formulation is incredibly powerful because it treats $f(x)$ as a black box—we don't need to differentiate through the discrete choice itself. Instead, we sample an outcome $x$, evaluate its cost $f(x)$, and scale the gradient of the log-probability by that cost.
However, this black-box nature is exactly why the estimator suffers from extreme variance. As noted by Yishu Miao et al. in Language as a Latent Variable: Discrete Generative Models for Sentence Compression, sampling-based gradient estimation introduces massive noise because a single sample provides a highly impoverished signal of the overall optimization landscape.
Imagine a model choosing a sequence of tokens from a large vocabulary. If the model samples a sequence that happens to get a good reward, REINFORCE aggressively increases the probability of every token in that sequence, even the bad ones. Conversely, if the sample is poor, it penalizes everything. This trial-and-error approach causes the gradient vectors to fluctuate dramatically between batches, leading to severe optimization instability, as detailed by Wilker Aziz and Philip Schulz in Variational Inference and Deep Generative Models.
Strategy 1: Continuous Relaxations and Smoothing
The most intuitive way to bypass this discontinuity wall is to smooth the terrain. If the step function can be replaced by a steep but continuous ramp, we can restore the reparameterization trick used in standard Variational Autoencoders.
In Discrete Variational Autoencoders, Jason Tyler Rolfe demonstrates how discrete latent variables can be "smoothed" by coupling them with continuous auxiliary variables. Similarly, frameworks like the Gumbel-Softmax or Concrete distribution map discrete categorical choices into a continuous space using a temperature parameter. When the temperature is high, the distribution is smooth and easy to differentiate; as the temperature approaches zero, it converges to the true discrete distribution.
However, this smoothing comes at a cost. As Yutaro Yamada et al. observe in Feature Selection using Stochastic Gates, differentiable relaxations often exhibit high variance in their gradient estimates during training. Furthermore, because the model trains on a smooth approximation but must ultimately make hard discrete choices at inference time, it suffers from optimization bias. This tension between bias and variance frequently leads to sub-optimal patterns and brittle hyperparameter sensitivity, a phenomenon also documented by Chang-Ti Huang et al. in Learning Sparse Neural Networks Through Mixture-Distributed Regularization.
Strategy 2: Control Variates and the REBAR Framework
Can we achieve the best of both worlds—an estimator that is completely unbiased yet possesses the low variance of a continuous relaxation?
The answer lies in a classic statistical technique known as control variates. Suppose we want to estimate an un-differentiable expectation $\mathbb{E}[f(X)]$. If we can find an auxiliary variable $Y$ whose expectation $\mathbb{E}[Y]$ is known analytically, and which is highly correlated with $f(X)$, we can construct a new estimator:
$$\hat{g} = f(X) - Y + \mathbb{E}[Y]$$
Because $Y$ mimics the fluctuations of $f(X)$, subtracting it strips away the shared noise, dramatically reducing the variance without introducing any bias.
In REBAR: Low-variance, unbiased gradient estimates for discrete latent variable models, George Tucker et al. realize that the continuous relaxation itself can serve as the perfect control variate. By conditioning the continuous relaxation on the discrete choice, the authors create a tightly coupled pair where the continuous gradient absorbs the high-frequency noise of the discrete sample. This allows researchers to train discrete models with the exactness of an unbiased estimator and the efficiency of backpropagation.
Strategy 3: Expliting Symmetry via Antithetic Sampling
Another elegant approach to variance reduction relies on geometric symmetry. If a single random sample causes our gradient estimate to overshoot wildly in one direction, evaluating a second sample that is perfectly mirrored across the distribution can cancel out the error.
This is the intuition behind antithetic sampling. In DisARM: An Antithetic Gradient Estimator for Binary Latent Variables, Zhe Dong et al. design an estimator for binary latent spaces where gradient components vanish independently for each dimension. By analytically integrating out unnecessary noise and evaluating pairs of negatively correlated, antithetic samples, DisARM achieves significant variance reduction without requiring any continuous relaxations.
Aleksandar Dimitriev expands this concept to multi-sample regimes in ARMS: Antithetic-REINFORCE-Multi-Sample Gradient for Binary Variables. By structuring multiple samples such that they are jointly antithetic, the author demonstrates that the gradient signal can be stabilized even further, providing a highly scalable alternative for deep generative models with massive discrete latent layers.
Strategy 4: Sampling Without Replacement
When dealing with large discrete spaces—such as a vocabulary of tens of thousands of words—standard Monte Carlo estimation often draws duplicate samples within the same batch. Drawing the same token twice is computationally wasteful and injects redundant noise into the gradient.
To solve this, Herke van Hoof et al. introduce the unordered set estimator in Estimating Gradients for Discrete Random Variables by Sampling without Replacement. By leveraging a statistical technique called Rao-Blackwellization, the authors condition the gradient estimator on the unique set of samples drawn without replacement.
Sampling With Replacement: [ Token A, Token B, Token A, Token C ] --> Redundant noise
Sampling Without Replacement: [ Token A, Token B, Token C, Token D ] --> Maximum information
By eliminating duplicate evaluations, this approach ensures that every forward pass contributes distinct information about the discrete manifold, stabilizing training in complex tasks like natural language processing and pathfinding.
The Modern Frontier: Discrete Diffusion and Score Matching
The battle against high-variance gradient estimation is not confined to variational autoencoders; it has emerged as a critical bottleneck in modern generative frameworks like diffusion models and score matching.
When training discrete diffusion models for text or biological sequences, the model must navigate a vast vocabulary of tokens without a clear directional signal. As Oussama Zekri et al. point out in Fine-Tuning Discrete Diffusion Models with Policy Gradient Methods, gradient estimation in these probability spaces suffers from extreme variance, making policy-gradient fine-tuning highly sensitive to initialization. This discretization noise is compounded because the model must learn to predict original data from highly corrupted or masked states, a challenge highlighted by Subham Sekhar Sahoo et al. in The Diffusion Duality.
Even in continuous domains, stochastic approximations can reintroduce this exact problem. For instance, sliced score matching uses random projections to bypass heavy computational costs. However, as noted by Chenlin Meng et al. in Autoregressive Score Matching and Peter Holderrieth et al. in Hamiltonian Score Matching and Generative Flows, these random projections introduce severe gradient variance at low noise levels, necessitating massive batch sizes or complex optimization schedules to prevent training collapse.
Ultimately, whether through control variates, antithetic structures, or algebraic smoothing, mitigating gradient variance remains the key to unlocking the full potential of discrete symbolic reasoning and flexible generative architectures in deep learning.