# Diagonalisation SGD: Fast & Convergent SGD for Non-Differentiable Models via Reparameterisation and Smoothing

arXiv: https://arxiv.org/abs/2402.11752 · HTML: https://mlsanity.com/paper/2402.11752/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 19 of its 48 references that are in the map.
- First posted on arXiv 19 Feb 2024.

## Builds on (most cited first, 19 of 19)

- [Categorical Reparameterization with Gumbel-Softmax](https://mlsanity.com/paper/1611.01144/) (2016)
- [Variational Inference: A Review for Statisticians](https://mlsanity.com/paper/1601.00670/) (2016)
- [The Concrete Distribution: A Continuous Relaxation of Discrete Random Variables](https://mlsanity.com/paper/1611.00712/) (2016)
- [Pyro: Deep Universal Probabilistic Programming](https://mlsanity.com/paper/1810.09538/) (2018)
- [Black Box Variational Inference](https://mlsanity.com/paper/1401.0118/) (2013)
- [Monte Carlo Gradient Estimation in Machine Learning](https://mlsanity.com/paper/1906.10652/) (2019)
- [Advances in Variational Inference](https://mlsanity.com/paper/1711.05597/) (2017)
- [Gradient Estimation Using Stochastic Computation Graphs](https://mlsanity.com/paper/1506.05254/) (2015)
- [Neural Variational Inference and Learning in Belief Networks](https://mlsanity.com/paper/1402.0030/) (2014)
- [REBAR: Low-variance, unbiased gradient estimates for discrete latent variable models](https://mlsanity.com/paper/1703.07370/) (2017)
- [An Introduction to Probabilistic Programming](https://mlsanity.com/paper/1809.10756/) (2018)
- [Variance reduction properties of the reparameterization trick](https://mlsanity.com/paper/1809.10330/) (2018)
- [Automated Variational Inference in Probabilistic Programming](https://mlsanity.com/paper/1301.1299/) (2013)
- [On Graduated Optimization for Stochastic Non-Convex Problems](https://mlsanity.com/paper/1503.03712/) (2015)
- [The Generalized Reparameterization Gradient](https://mlsanity.com/paper/1610.02287/) (2016)
- [Reparameterization Gradient for Non-differentiable Models](https://mlsanity.com/paper/1806.00176/) (2018)
- [Densities of Almost Surely Terminating Probabilistic Programs are Differentiable Almost Everywhere](https://mlsanity.com/paper/2004.03924/) (2020)
- [Multilevel Monte Carlo Method for Statistical Model Checking of Hybrid Systems](https://mlsanity.com/paper/1706.08270/) (2017)
- [Fast and Correct Gradient-Based Optimisation for Probabilistic Programming via Smoothing](https://mlsanity.com/paper/2301.03415/) (2023)

## Abstract (arXiv)

It is well-known that the reparameterisation gradient estimator, which exhibits low variance in practice, is biased for non-differentiable models. This may compromise correctness of gradient-based optimisation methods such as stochastic gradient descent (SGD). We introduce a simple syntactic framework to define non-differentiable functions piecewisely and present a systematic approach to obtain smoothings for which the reparameterisation gradient estimator is unbiased. Our main contribution is a novel variant of SGD, Diagonalisation Stochastic Gradient Descent, which progressively enhances the accuracy of the smoothed approximation during optimisation, and we prove convergence to stationary points of the unsmoothed (original) objective. Our empirical evaluation reveals benefits over the state of the art: our approach is simple, fast, stable and attains orders of magnitude reduction in work-normalised variance.