Gradient Estimation for Discrete Latent Variables

189 concepts157 papers1 proposal

Deep learning thrives on the reparameterization trick. As explained by Kingma et al., continuous latent variables can be expressed as a deterministic function of parameters and independent noise, allowing gradients to flow smoothly via standard backpropagation. However, many real-world problems require discrete choices: selecting a category, routing an input through a decision tree, or modeling binary dropout masks (Boluki et al.).

When a model draws a discrete sample—such as using an arg max or a step function—the mathematical landscape changes. The derivative of a step function is zero everywhere except at the boundary, where it is undefined. This non-differentiability means standard backpropagation cannot pass through the void, leaving parameters before the discrete choice without a learning signal (Choi et al.; Lorberbom et al.).

To bridge this gap, researchers have developed several distinct paradigms to estimate gradients or optimize directly through discrete latent layers.

The Score-Function Estimator and the Variance Problem

To optimize an expectation over a discrete distribution $\mathbb{E}_{z \sim p_\theta(z)} [f(z)]$, we can use the score-function estimator (commonly known as the REINFORCE algorithm). By using the log-derivative trick, we rewrite the gradient as:

$$\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)]$$

This formulation allows us to estimate gradients without needing the function $f(z)$ to be differentiable. The intuition is simple: if a discrete sample $z$ results in a good outcome (a high reward or low loss $f(z)$), the gradient pushes the parameters $\theta$ to make that specific sample more likely in the future.

However, because $f(z)$ acts as a raw scaling factor, this estimator suffers from cripplingly high variance (Dimitriev et al.). Training can feel like searching for a needle in a haystack, often leading to slow convergence or model collapse into a deterministic state (Raiko et al.).

Variance Reduction via Control Variates

The standard way to tame the variance of the score-function estimator is by introducing a control variate (or baseline) $b$. We rewrite the gradient as:

$$\mathbb{E}_{z \sim p_\theta(z)} [(f(z) - b) \nabla_\theta \log p_\theta(z)]$$

As long as $b$ does not depend on the specific sample $z$, the expectation remains mathematically unchanged (unbiased). However, if $b$ closely tracks the expected value of $f(z)$, the variance drops dramatically because the multiplier becomes the deviation from the baseline rather than the raw value.

Choi et al. introduced the LAX and RELAX frameworks, which train a surrogate neural network to act as a learned control variate for black-box functions. To achieve even tighter variance bounds, Tucker et al. proposed REBAR, which utilizes a continuous relaxation of the discrete distribution as a control variate, combining it with conditional marginalization to keep the estimator completely unbiased. Building on these baselines, Titsias introduced Double Control Variates, layering a Taylor-expansion baseline over a leave-one-out estimator to achieve state-of-the-art precision without extra computational overhead.

Continuous Relaxations

Instead of trying to fix the score-function estimator, another major paradigm replaces the discrete sampling step entirely during training with a smooth, continuous approximation. The most common approach uses the Gumbel-Softmax or Concrete distribution, where a temperature parameter controls how closely the relaxation mimics a hard discrete choice. During training, the temperature is gradually lowered, hardening the continuous vectors into discrete choices.

The authors of several papers have extended this idea to more complex latent structures:

  • Boltzmann Priors: Khoshaman et al. introduced GumBolt to extend the Gumbel trick to powerful Boltzmann Machine priors. Similarly, Vahdat et al. developed DVAE# and DVAE++ (Vahdat et al.), which smooth out discrete transformations using mixtures of overlapping continuous distributions.
  • Correlated Variables: To handle dependencies between discrete variables, Wang proposed RelaxedMVB, combining a continuous Bernoulli relaxation with a Gaussian copula.
  • Structured Sequences: For structured sequence modeling, Tan et al. introduced Gumbel-CRFs, allowing pathwise gradients to flow through latent sentence templates.

Antithetic Sampling

A highly effective strategy for variance reduction without relying on continuous relaxations is antithetic sampling. The intuition is to draw pairs (or sets) of samples that are perfectly negatively correlated. If one sample randomly fluctuates far above the mean, its antithetic counterpart will fluctuate below the mean, causing the random noise to cancel out when averaged.

Yin et al. introduced the Augment-REINFORCE-Merge (ARM) estimator for stochastic binary networks. Dong then developed DisARM, which significantly reduces variance by analytically integrating out the underlying continuous noise from the ARM framework. To scale this benefit, Dimitriev et al. proposed ARMS, which leverages multiple jointly antithetic samples, while Dimitriev et al. extended this framework to categorical variables with CARMS.

Direct Optimization and Alternative Paradigms

Some researchers argue that both score-function estimators and continuous relaxations have fundamental flaws—either high variance or optimization bias. Consequently, alternative paradigms bypass standard gradient estimation entirely.

Lorberbom et al. proposed a direct loss minimization approach that optimizes directly through the non-differentiable arg max operation, avoiding biased softmax relaxations. Taking a reinforcement learning perspective, Drolet introduced DAPS, which treats the training of a discrete encoder as a policy search problem to maximize reconstruction quality. Finally, Crucinio developed a mirror descent approach combined with Sequential Monte Carlo, completely eliminating the requirement for calculating gradients with respect to the latent variables themselves.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 158 papers
  2. Version 1 · 2026-10-04 · 235 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_discrete_latent_variable_optimization_38cd4308,
  title = {discrete latent variable optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/discrete-latent-variable-optimization/rdr_38cd4308d12a4ee8a7af777f60eb399c},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 2, frozen text):

@misc{lacuna_discrete_latent_variable_optimization_38cd4308_v2,
  title = {discrete latent variable optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/discrete-latent-variable-optimization/rdr_38cd4308d12a4ee8a7af777f60eb399c/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake