Continuous Relaxations for Differentiable Discrete Optimization

This direction is merged into another direction: differentiable discrete sampling (differentiable categorical sampling). Its last version stays readable and citable here.

Version 1 of 1113 papers124 conceptsfrozen 2026-10-04

Neural networks are built on the bedrock of gradients. To learn, a model must understand how a tiny change in its parameters affects its output. This works beautifully for continuous values—like the intensity of a pixel or the weight of a connection—but it fails for discrete choices. If a model must choose between "Category A" and "Category B," there is no "tiny change" that smoothly transitions between them. This "differentiability gap" has historically forced researchers to use high-variance reinforcement learning techniques or slow combinatorial searches to train models with discrete components.

A powerful family of solutions has emerged: continuous relaxations. By treating discrete switches as "dimmer switches" during training, researchers can use standard backpropagation to optimize everything from neural architectures to molecular structures.

The Gumbel-Softmax Trick

The most influential mechanism for bridging this gap is the Gumbel-Softmax (or Concrete) distribution. Introduced independently by Shixiang Gu and Eric Jang in Categorical Reparameterization with Gumbel-Softmax, this technique provides a differentiable approximation of categorical sampling.

In a standard model, sampling a category is a "hard" operation that stops gradients. Gumbel-Softmax replaces this with a "soft" sample. It adds Gumbel-distributed noise to the model's logits and then applies a softmax function with a temperature parameter ($\tau$).

  • At high temperatures, the output is a blurry, uniform distribution.
  • As the temperature approaches zero, the output becomes a "one-hot" vector, effectively making a hard discrete choice.

By starting with a high temperature and "annealing" it down during training, the model can explore different discrete paths using gradients before eventually committing to a specific structure. This mechanism is now a staple in Bayesian Variational Optimization for combinatorial spaces, as explored by Tony Wu and Daniel Flam-Shepherd.

Learning Structure and Sparsity

One of the most compelling uses of relaxations is in learning the architecture of a network rather than just its weights. Instead of manually deciding which neurons to connect, researchers use "binary inclusion variables" that are relaxed into continuous probabilities.

Aliaksandr Hubin and Geir Storvik demonstrate this in Variational Inference for Bayesian Neural Networks under Model and Parameter Uncertainty. Their Latent Binary Bayesian Neural Networks (LBBNNs) use the Concrete relaxation to learn which weights are necessary, effectively "pruning" the network during training. Similarly, Shira Lifshitz uses Gumbel-Softmax in Unsupervised Feature Selection Through Group Discovery to learn discrete mappings from features to latent groups, allowing for end-to-end discovery of data structure.

Generative Composition and Disentanglement

In generative modeling, relaxations allow models to reason about discrete objects and categories within a continuous visual world. Emilien Dupont developed JointVAE in Learning Disentangled Joint Continuous and Discrete Representations, which uses relaxations to separate continuous factors (like the rotation of a digit) from discrete factors (like the identity of the digit).

This compositional approach is taken further in scene generation. Michael Tschannen and colleagues introduced SB-GAN, which uses a "semantic bottleneck." The model first generates a discrete layout (e.g., "tree here," "car there") and then renders it. Because the layout is discrete, the model requires a continuous relaxation to allow gradients to flow from the final image back to the layout generator. This same logic allows Titas Anciukevičius and Paul Henderson to factorize depth and location in object-centric models.

Adversarial Robustness and Tabular Data

Continuous relaxations have also become a vital tool for attacking and defending models that handle discrete data, such as text, DNA, or tabular records. Standard adversarial attacks rely on moving "uphill" along a gradient to find a failure point. For categorical data, there is no "up."

Han Xu and Xu Han solved this in Probabilistic Categorical Adversarial Attack by mapping discrete inputs into a continuous probabilistic space. This allows them to use gradient ascent to find optimal perturbations. This approach is mirrored in Tabular Diffusion Counterfactual Explanations by Brian Barr, where Gumbel-Softmax enables gradient-based guidance to "nudge" categorical features (like "Job Title") toward a desired outcome in a diffusion model.

Beyond Simple Relaxations

While Gumbel-Softmax is the workhorse of the field, new methods are addressing its limitations, such as high variance at low temperatures.

  • Marginalization: Instead of sampling, some models "sum out" the discrete choices. Hyoung-Jin Lim uses this in Differentiable Algorithm for Marginalising Changepoints to make time-series models fully differentiable.
  • Diffusion Paths: Eric Moulines recently proposed REDGE, which treats the transition from noise to a discrete category as a multi-step diffusion path. This provides a smoother, more stable gradient than the single-step Gumbel-Softmax.

By turning hard choices into smooth landscapes, these techniques allow neural networks to reason about the structured, categorical nature of the real world without losing the power of the gradient.

Papers in this version

Showing 60 of 113 papers.

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_continuous_relaxations_for_differentiabl_3647f491,
  title = {Continuous Relaxations for Differentiable Discrete Optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/continuous-relaxations-for-differentiable-discrete-optimization/rdr_3647f491e95d4ee7bfbc96e129068253},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_continuous_relaxations_for_differentiabl_3647f491_v1,
  title = {Continuous Relaxations for Differentiable Discrete Optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/continuous-relaxations-for-differentiable-discrete-optimization/rdr_3647f491e95d4ee7bfbc96e129068253/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}