Abstract
Deep Neural Networks are successful but highly computationally expensive learning systems. One of the main sources of time and energy drains is the well known back-propagation (backprop) algorithm, which roughly accounts for 2/3 of the computational cost of training. In this work we propose a method for reducing the computational complexity of backprop, which we named dithered backprop. It consists on applying a stochastic quantization scheme to intermediate results of the method. The particular quantisation scheme, called non-subtractive dither (NSD), induces sparsity which can be exploited by computing efficient sparse matrix multiplications. Experiments on popular image classification tasks show that it induces 92% sparsity on average across a wide set of models at no or negligible accuracy drop in comparison to state-of-the-art approaches, thus significantly reducing the computational complexity of the backward pass. Moreover, we show that our method is fully compatible to state-of-the-art training methods that reduce the bit-precision of training down to 8-bits, as such being able to further reduce the computational requirements. Finally we discuss and show potential benefits of applying dithered backprop on a distributed training settings, in that communication as well as compute efficiency may increase simultaneously with the number of participant nodes.
Introduction
The computational burden of training state-of-the-art Deep Neural Networks (DNNs) has significant environmental and economic costs. Backpropagation, the standard algorithm for weight updates, is responsible for approximately two-thirds of the total training workload due to intensive matrix multiplications. While quantization and sparsification are common strategies to mitigate these costs, they often introduce deterministic biases that can hinder model convergence. This paper introduces Dithered Backprop, a novel approach that utilizes stochastic quantization to achieve high sparsity and low precision without compromising the integrity of the learning process.
Methodology
The core of Dithered Backprop is the application of Non-Subtractive Dithering (NSD) to the gradients of preactivation values ($\delta_z$). Unlike standard rounding, which is biased, NSD adds a uniform random noise signal (dither) before quantization. This ensures that the quantization error is an unbiased estimate with zero mean, allowing Stochastic Gradient Descent (SGD) to converge effectively.
A key feature of this method is its ability to induce sparsity. By adjusting a global scaling factor ($s$) relative to the standard deviation of the gradients, a significant portion of small gradient values are quantized to zero.
As shown in the figure above, increasing the scale parameter directly increases the probability that a value will be quantized to zero, providing a controllable trade-off between computational savings (sparsity) and gradient precision.
Experimental Evaluation
The authors evaluated Dithered Backprop across several standard computer vision benchmarks, including MNIST (LeNet), CIFAR-10/100 (VGG11, AlexNet, ResNet18), and ImageNet (ResNet18). The method was tested for its ability to maintain accuracy while maximizing sparsity in the backward pass.
Key Results
The experiments yielded several significant findings:
- Massive Sparsity: Dithered backprop achieved an average of 92% sparsity across the tested models. In some cases, such as LeNet5, sparsity reached over 97%.
- Accuracy Preservation: The average accuracy drop was minimal, at only 0.3%.
- Convergence Stability: The training process remained stable. As illustrated in the comparison for VGG11 on CIFAR-10, the test error for dithered backprop tracks the baseline very closely throughout the training epochs.
- Low Precision Compatibility: The non-zero gradients were representable using 8-bit precision or less, making the method compatible with existing low-precision training frameworks.
Discussion and Conclusion
Dithered Backprop offers a promising path toward more sustainable AI training. By turning quantization noise into a tool for sparsity, it achieves significant computational reductions. A particularly compelling aspect is its synergy with distributed training: because the dithered noise is independent across nodes, it naturally cancels out during gradient averaging. This implies that larger distributed systems could potentially use even more aggressive quantization.
While current hardware is primarily optimized for dense operations, the high levels of unstructured sparsity demonstrated here provide a strong motivation for the development of specialized hardware accelerators. Future work will focus on exploring structured sparsity patterns and further optimizing communication efficiency in distributed environments.
Summary updated