Deep learning owes much of its success to backpropagation, an algorithm that relies on the chain rule to propagate gradients through continuous, differentiable layers. However, many real-world problems are inherently discrete. Whether a model is selecting a word from a vocabulary, routing a packet through a network, or turning a neuron on or off via dropout, it must make hard, non-differentiable choices.
Because the derivative of a step function or a discrete sample is either zero or undefined, standard backpropagation fails. To train these models end-to-end, researchers must find a way to estimate gradients through discrete operations. This challenge has sparked a major research direction focused on the fundamental trade-off between gradient bias and gradient variance.
The Core Dilemma: Score Functions vs. Relaxations
To understand why this research area is so active, we must look at the two classical ways to estimate gradients through a stochastic discrete variable $z \sim p_\theta(z)$.
The first approach is the score function estimator (or REINFORCE). It keeps the model strictly discrete and uses a mathematical identity to estimate the gradient of an expectation:
$$\nabla_\theta \mathbb{E}_{z \sim p_\theta(z)} [f(z)] = \mathbb{E}_{z \sim p_\theta(z)} [f(z) \nabla_\theta \log p_\theta(z)]$$
As noted by Tapani Raiko et al. in their work on Techniques for Learning Binary Stochastic Feedforward Neural Networks, this estimator is entirely unbiased—it targets the exact discrete objective. However, because it relies on a single scalar reward $f(z)$ to scale the gradient direction, its variance is notoriously high. Training often destabilizes or stalls because the gradient updates are incredibly noisy.
The second approach is continuous relaxation. Instead of sampling a hard discrete variable, we replace the discrete operation with a smooth, continuous approximation. The most prominent example of this is the Gumbel-Softmax (or Concrete) distribution, a comprehensive overview of which is provided by Iris A. M. Huijben et al. in A Review of the Gumbel-max Trick and its Extensions for Discrete Stochasticity in Machine Learning. By utilizing the reparameterization trick, gradients can flow directly through the continuous samples.
The Temperature Tightrope
Continuous relaxations rely heavily on a temperature hyperparameter ($\tau$) to control the sharpness of the approximation. This parameter creates a strict mathematical trade-off:
- High Temperature ($\tau \to \infty$): The relaxed distribution becomes highly smooth and approaches a uniform distribution. Gradients flow easily, and their variance is low. However, the approximation is highly biased because the smooth mixtures look nothing like the true, sharp discrete choices the model is supposed to make.
- Low Temperature ($\tau \to 0$): The relaxed distribution behaves almost exactly like the true discrete distribution, reducing bias. However, as the distribution becomes sharper, the gradients begin to explode or vanish, leading to massive variance that makes optimization highly unstable.
This sensitivity is a recurring theme across diverse domains. For instance, Aditya Grover et al. encountered this exact barrier in Stochastic Optimization of Sorting Networks via Continuous Relaxations, where relaxing discrete permutation matrices required careful temperature tuning to prevent vanishing gradients. Similarly, in Differentiable Feature Selection, a Reparameterization Approach, Jérémie Donà et al. demonstrated that poorly tuned temperatures cause feature selection models to either fail to produce sparse binary masks or suffer from optimization collapse.
The Cost of Bias: The Train-Test Mismatch
Why not simply train with a high-temperature, stable relaxation and call it a day? The danger lies in the optimization bias.
When we use a continuous relaxation, the model optimizes a proxy objective rather than the true discrete objective. As Zhe Dong et al. explain in Coupled Gradient Estimators for Discrete Latent Variables, this creates a fundamental discrepancy between the model optimized during training and the discrete model deployed at test time.
For example, during training, a model might exploit the "softness" of a relaxation, passing a fractional mixture of multiple categories downstream. But at inference time, when forced to make a hard arg max choice, the model collapses because it never learned to operate under strict discrete constraints. Guy Lorberbom et al. address this directly in Direct Optimization through arg max for Discrete Variational Auto-Encoder, arguing that bypassing soft relaxations entirely in favor of direct loss minimization is often necessary to prevent this train-test mismatch.
This bias manifests across several specialized architectures:
- Regularization: In Learnable Bernoulli Dropout for Bayesian Deep Learning, Shahin Boluki et al. showed that continuous approximations of binary dropout masks allow models to bypass the intended regularization effects, degrading uncertainty estimates.
- Structured NLP: Chuanqi Tan et al. noted in Latent Template Induction with Gumbel-CRFs that while relaxations stabilize text generation templates, the theoretical impact of the introduced bias remains a persistent concern for final model generalization.
Unbiased and Low-Variance: Having Your Cake and Eating It Too
To escape this trade-off, a major subfield focuses on constructing estimators that are simultaneously unbiased and low-variance.
1. Control Variates (REBAR)
The breakthrough insight of George Tucker et al. in REBAR: Low-variance, unbiased gradient estimates for discrete latent variable models was that we can use a continuous relaxation without letting its bias corrupt our model.
REBAR uses the continuous relaxation as a control variate (a baseline). It computes a biased gradient along the smooth relaxation path, but then subtracts a conditional correction term. Because the expectation of the correction term exactly matches the bias introduced by the relaxation, the resulting gradient is strictly unbiased, yet it retains the smooth, low-variance tracking properties of the continuous relaxation.
2. Antithetic Multi-Sampling
Another powerful way to beat down variance without introducing bias is through structured multi-sampling. If you draw multiple independent samples to estimate a gradient, variance decreases linearly with the sample size. However, if you draw negatively correlated (antithetic) samples, the variance drops much faster.
Aleksandar Dimitriev et al. developed this intuition for binary variables in ARMS: Antithetic-REINFORCE-Multi-Sample Gradient for Binary Variables. By ensuring that pairs of samples balance each other out across the probability space, they drastically reduce the noise of the unbiased REINFORCE estimator. Alek Dimitriev later extended this concept to multi-class scenarios in CARMS: Categorical-Antithetic-REINFORCE Multi-Sample Gradient Estimator, proving that unbiased categorical estimation could achieve competitive convergence speeds without systematic errors.
3. Variable Augmentation and Swapping
Instead of evaluating the discrete distribution directly, we can augment the probability space with continuous variables and perform exact algebraic manipulations on them before mapping them back to discrete choices.
Mingzhang Yin et al. leveraged this in ARSM: Augment-REINFORCE-Swap-Merge Estimator for Gradient Backpropagation Through Categorical Variables. ARSM uses the Gumbel-Max trick to map continuous Dirichlet-allocated variables into categories, and then applies a "swap and merge" operation on the coordinates to cancel out variance. Because it operates on an augmented space, it avoids the systematic errors of soft relaxations while navigating complex optimization landscapes more effectively.
4. Rao-Blackwellization
When dealing with discrete distributions, the variance often stems from the rare, high-surprise samples in the tail of the distribution. Jeffrey Regier et al. proposed a solution in Rao-Blackwellized Stochastic Gradients for Discrete Distributions by analytically summing out the probabilities of the most likely discrete categories and only sampling from the remaining tail. This mathematical reduction guarantees lower variance while preserving perfect unbiasedness.
Scaling to Complex Combinatorial Structures
The frontier of this research direction lies in moving beyond simple independent binary or categorical choices into highly constrained combinatorial spaces.
When a model must enforce strict structural rules—such as picking exactly $k$ items, sorting a sequence, or traversing a graph—a naive continuous relaxation will break the constraints. Researchers are adapting these bias-variance mitigation strategies to handle these complex structures:
- Subset Selection: In SIMPLE: A Gradient Estimator for $k$-subset Sampling, Kareem Ahmed et al. demonstrated that enforcing strict constraints (like picking exactly $k$ items) amplifies the bias-variance conflict, requiring specialized estimators to maintain accurate gradient directions.
- Graph Operations: Alessandro Manenti et al. scaled continuous relaxations to graph structures in SWING: Unlocking Implicit Graph Representations for Graph Random Features, relaxing discrete random walks into continuous "space walks" while managing the multi-hyperparameter tension between representation accuracy and gradient stability.
Ultimately, this research direction shows that continuous relaxations are not a silver bullet on their own. Instead, they serve as a foundational mathematical scaffolding. By understanding and correcting for the bias and variance they introduce, modern architectures can successfully bridge the gap between continuous optimization and discrete logic.
Key Foundational Work
Techniques for Learning Binary Stochastic Feedforward Neural Networks (2015) — contributed 1 concept elements to this direction.
REBAR: Low-variance, unbiased gradient estimates for discrete latent variable models (2017) — contributed 1 concept elements to this direction.
Categorical Reparameterization with Gumbel-Softmax (2017) — contributed 1 concept elements to this direction.