Diagonalisation SGD: Fast & Convergent SGD for Non-Differentiable Models via Reparameterisation and Smoothing
This addresses a bottleneck in gradient-based optimization for non-differentiable models, offering a fast and stable method with broad applicability in machine learning.
The paper tackled the problem of biased gradient estimators in non-differentiable models by introducing Diagonalisation SGD, which uses piecewise definitions and smoothing to achieve unbiased gradients, resulting in orders of magnitude reduction in work-normalised variance and proven convergence to stationary points.
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.