Categorical Reparameterization with Denoising Diffusion models
Samson Gourevitch, Alain Durmus, Eric Moulines, Jimmy Olsson, Yazid Janati · 2026
Read Categorical Reparameterization with Denoising Diffusion models by Samson Gourevitch, Alain Durmus, Eric Moulines, Jimmy Olsson, Yazid Janati (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-00781.txt.
Introduction
Samson Gourevitch, Alain Durmus, Eric Moulines, Jimmy Olsson, and Yazid Janati improve how machine learning models learn with categorical variables. Optimizing over discrete choices is awkward because sampling a category has no usable gradient. The standard workaround replaces the discrete distribution with a smooth relaxation, so gradients can flow through a reparameterization trick.
Their method, ReDGE, builds that relaxation on denoising diffusion, yielding a flexible family of gradient estimators that includes the widely used straight-through estimator as a special case. Experiments cover latent variable models and reward-guided generation in discrete diffusion models. Across those settings ReDGE matches or beats existing gradient-based approaches, offering a drop-in upgrade for training models with discrete structure.
Catalog record
| CREATOR | Samson Gourevitch, Alain Durmus, Eric Moulines, Jimmy Olsson, Yazid Janati |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 129 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-00781
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Categorical Reparameterization with Denoising Diffusion models Samson Gourevitch, Alain Durmus, Eric Moulines, Jimmy Olsson, Yazid Janati Abstract Learning models with categorical variables requires optimizing expectations over discrete distributions, a setting in which stochastic gradient-based optimization is challenging due to the non-differentiability of categorical sampling. A common workaround is to replace the discrete distribution with a continuous relaxation, yielding a smooth surrogate that admits reparameterized gradient estimates via the reparameterization trick. Building on this idea, we introduce ReDGE , a novel and efficient diffusion-based soft reparameterization method for categorical distributions. Our approach defines a flexible class of gradient estimators that includes the Straight-Through estimator as a special case. Experiments spanning latent variable models and inference-time reward guidance in discrete diffusion models demonstrate that ReDGE consistently matches or outperforms existing gradient-based methods. The code is available at https://github.com/samsongourevitch/redge . 1 Introduction Many learning problems involve discrete choices, such as actions in reinforcement learning, categorical latent variables in variational inference, token-level decisions in sequence modeling, or combinatorial assignments in structured prediction and discrete optimization. A common primitive in these settings is the minimization of an objective of the form \mathbb{E}_{\pi_{\!\theta}}[f(X)] , where \pi_{\!\theta} is a categorical distribution corresponding to the law of L independent discrete random variables each taking values in a vocabulary of size K . The function f represents a downstream loss or constraint penalty evaluated on discrete samples, typically through one-hot encodings. Computing \nabla_{\!{\theta}}\mathbb{E}_{\pi_{\!\theta}}[f(X)] exactly is generally intractable: in the absence of exploitable structure in f , it requires summing over K^{L} configurations. The challenge, therefore, is to construct gradient estimators that are both computationally feasible and have a low mean squared error. Existing estimators exhibit a standard bias–variance trade-off. Score-function estimators, such as Reinforce ( Williams, 1992 ; Greensmith et al., 2004 ) , are unbiased but often suffer from high variance, which motivates the use of variance-reduction techniques most often using learned control variates ( Tucker et al., 2017 ; Grathwohl et al., 2018 ) ; they often yield useful gradients in practice but are biased with respect to the true discrete objective, with recent refinements such as ReinMax improving the approximation ( Liu et al., 2023a ) . Continuous relaxations based on approximate reparameterizations, most notably the Gumbel-Softmax / Concrete construction ( Maddison et al., 2017 ; Jang et al., 2017 ) , replace \pi_{\!\theta} by a smooth family on the simplex controlled by a temperature parameter. While this enables pathwise differentiation, taking the temperature small to reduce bias drives the sampler towards an argmax map and typically leads to ill-conditioned or vanishing gradients, while higher temperatures provide well-behaved gradients but correspond to optimizing a more relaxed objective. In this work, we revisit continuous relaxations through the lens of denoising diffusion models ( Sohl-Dickstein et al., 2015 ; Song and Ermon, 2019 ; Ho et al., 2020 ) . Diffusion models generate data by transforming a Gaussian sample into a sample from the target data distribution through iterative denoising dynamics explicitly constructed as the reverse of a chosen forward noising process. In practice, implementing the sampler requires only access to a denoiser; that is, a function that, given a noisy input and its noise level or time index, returns the expected clean signal. Contributions. We exploit the key observation that for a categorical distribution supported on simplex vertices, the denoiser at each noise level can be computed in closed form. This enables us to construct a training-free, diffusion-based, differentiable, and approximate sampling map from Gaussian noise to the categorical distribution \pi_{\!\theta} . We then analyze the small-noise regime, which serves as the temperature parameter, and characterize the emergence of nearly constant transport regions and sharp decision boundaries, explaining when and why gradients become uninformative as the relaxation approaches the discrete target. We derive practical gradient estimators, including hard variants, that recover the hard Straight-Through ( Bengio et al., 2013 ) and ReinMax ( Liu et al., 2023a ) as special cases when using a single diffusion step. We also propose a parameter-dependent initialization that improves performance while keeping the diffusion overhead small. Empirically, we find that our diffusion-based reparameterization yields strong results across a diverse set of benchmarks, including polynomial programming, variational inference, and inference-time reward guidance, typically matching or improving upon prior estimators. Notation. For any positive integer n , let [n]\coloneqq\{1,\ldots,n\} . We denote the K -simplex by \Delta^{K-1}=\{w\in{\mathbb{R}}^{K}_{+}\,:\,\sum_{k=1}^{K}w^{k}=1\} . For a matrix x\in{\mathbb{R}}^{L\times K} , we write x^{i}\in{\mathbb{R}}^{K} for its i -th row and x^{ij} for the (i,j) -th element. Besides, we identify any x\in{\mathbb{R}}^{L\times K} as a vector using the row-major order in which the matrix elements are ordered by row. The softmax operator on a matrix x\in{\mathbb{R}}^{L\times K} is defined row-wise by \text{softmax}(x)\in{\mathbb{R}}^{L\times K} with entries \text{softmax}(x)^{ik}=\exp(x^{ik})/\sum_{j=1}^{K}\exp(x^{ij}) for (i,k)\in[L]\times[K] . For a map f:{\mathbb{R}}^{d}\to{\mathbb{R}}^{m} , we write \operatorname{J}_{x}\!f\in{\mathbb{R}}^{m\times d} for its Jacobian matrix. To write Jacobians for maps f:{\mathbb{R}}^{L^{\prime}\times K^{\prime}}\to{\mathbb{R}}^{L\times K} conveniently, we implicitly identify matrices with their vectorized forms. Gradients and Jacobians are taken with respect to these vectorized representations, and we do not distinguish notationally between a matrix and its vectorization. 2 Background We consider optimization problems where the objective is an expectation with respect to a discrete distribution over a finite vocabulary \mathsf{X} , of the form F(\theta)=\mathbb{E}_{\pi_{\!\theta}}[f_{\theta}(X)]\coloneqq\sum_{x\in\mathsf{X}}f_{\theta}(x)\,\pi_{\!\theta}(x)\;, (1) where f:\mathsf{X}\times\Theta\to{\mathbb{R}} , \Theta\subseteq{\mathbb{R}}^{m} , and \{\pi_{\theta}:\theta\in\Theta\} is a parameterized family of probability mass functions (p.m.f.) over \mathsf{X} . Without loss of generality, we assume that \mathsf{X}=\mathsf{V}^{L} for some L\in\mathbb{N} , where \mathsf{V}\coloneqq\{e_{k}\}_{k=1}^{K} denotes the set of K one-hot encodings, and e_{k}\in{\mathbb{R}}^{K} is the one-hot vector with 1 at position k . We also assume that the distribution \pi_{\!\theta} factorizes according to this categorical structure: for any \theta\in\Theta and x=(x^{1},\ldots,x^{L})\in\mathsf{X} , \pi_{\!\theta}(x)=\prod_{i=1}^{L}\pi^{i}_{\!\theta}(x^{i}),\;\pi^{i}_{\!\theta}(x^{i})\coloneqq\frac{\exp(\langle x^{i}\;,\varphi_{\theta}^{i}\rangle)}{\sum_{j=1}^{K}\exp(\varphi_{\theta}^{ij})}\;,\!\! (2) where \theta\mapsto\varphi_{\theta}\in{\mathbb{R}}^{L\times K} is such that \varphi^{i}_{\theta} are the logits of the i -th categorical component. The factorization ( 2 ) is standard and is used in reinforcement learning to model policies ( Wu et al., 2018 ; Berner et al., 2019 ; Vinyals et al., 2019 ) , in training Boltzmann machines ( Hinton, 2012 ) , in VQ-VAEs ( Van Den Oord et al., 2017 ) , and more recently for modelling transitions in discrete diffusion models. ( Hoogeboom et al., 2021 ; Austin et al., 2021 ; Campbell et al., 2022 ; Lou et al., 2023 ; Shi et al., 2024 ; Sahoo et al., 2024 ) . Under mild regularity assumptions on f and \varphi_{\theta} , the gradient of ( 1 ) is given by \textstyle\nabla_{\!{\theta}}F(\theta)=\mathbb{E}_{\pi_{\!\theta}}[\nabla_{\!{\theta}}f_{\theta}(X)]+\sum_{x\in\mathsf{X}}f_{\theta}(x)\nabla_{\!{\theta}}\pi_{\!\theta}(x) (3) and is intractable as the sum ranges over K^{L} states. Furthermore, while the first term can be approximated via Monte Carlo, the second term has to be estimated separately. One option is to use the reinforce estimator. ( Williams, 1992 ) However, it is well known that the vanilla forma of this estimator suffers from high variance ( Sutton and Barto, 2018 ) and has be to combined with baselines or other control-variate techniques to reduce variance ( Greensmith et al., 2004 ; Mnih and Gregor, 2014 ; Mnih and Rezende, 2016 ; Tucker et al., 2017 ; Titsias and Shi, 2022 ; Grathwohl et al., 2018 ) . Other estimation methods have been proposed, such as the Straight-Through estimator ( Bengio et al., 2013