Dithered backprop: A sparse and quantized backpropagation algorithm for more efficient deep neural network training

Simon Wiedemann, Temesgen Mehari, Kevin Kepp, Wojciech Samek

Introduction

Training state-of-the-art deep neural networks (DNNs) is a computationally intensive process, with the backpropagation algorithm accounting for approximately two-thirds of the total training time. As model complexity grows, the environmental impact and hardware requirements for training become significant barriers to entry. While model compression techniques like quantization and pruning are well-established for inference, applying them during training is challenging due to the accumulation of biased errors that can lead to model divergence.

In this work, we discuss Dithered Backprop, a method that utilizes Non-Subtractive Dithering (NSD) to transform dense, high-precision gradients into sparse, low-precision tensors. This approach achieves significant computational efficiency without compromising final model accuracy.

Methodology: Non-Subtractive Dithering

The core of Dithered Backprop is the application of stochastic quantization to the gradients of preactivation values ($\delta_z^l$). Unlike deterministic rounding, which introduces systematic bias, NSD adds a uniform random noise signal (dither) to the gradient before quantization.

Unbiased Quantization and Sparsity

Mathematically, NSD ensures that the expected value of the quantized gradient is equal to its original high-precision value, making the quantization error "white noise" rather than a systematic bias. By setting the quantization step size ($\Delta$) relative to the standard deviation of the gradients, the method effectively pushes a large majority of values to zero.

Mechanism of NSD: Increasing the scale parameter shifts the probability mass toward zero, inducing sparsity while maintaining an unbiased estimate.

This mechanism allows for high levels of sparsity (averaging 92%) while representing non-zero values with low bit-widths (typically 8-bit). The method is designed to be "plug-and-play" with existing 8-bit training frameworks, offering potential speedups in both forward and backward passes.

Experimental Results

The proposed method was evaluated on standard computer vision benchmarks, including MNIST, CIFAR-10, CIFAR-100, and ImageNet, using architectures such as LeNet, VGG11, AlexNet, and ResNet18.

Accuracy and Sparsity Trade-offs

Dithered Backprop consistently achieved high sparsity with negligible impact on test accuracy. For instance, on CIFAR-10 with a VGG11 model, the method reduced gradient density to roughly 5% (95% sparsity) while maintaining a test error curve nearly identical to the full-precision baseline.

Training performance of VGG11 on CIFAR-10: (a) Test error is comparable to the baseline, (b) while gradient density is significantly reduced.

Across all tested models, the average sparsity was 92%, with accuracy drops typically remaining below 0.3%. Notably, Dithered Backprop outperformed existing deterministic sparsification methods like meProp, achieving higher accuracy at greater sparsity levels (e.g., 98.14% accuracy at 99.15% sparsity on MNIST).

Discussion and Conclusion

Dithered Backprop demonstrates that gradients are inherently amenable to sparsification and quantization when handled with stochastic methods. A key advantage of this approach is its behavior in distributed training: dithering noise tends to cancel out when gradients are averaged across multiple nodes, potentially allowing for even more aggressive compression in large-scale clusters.

While the theoretical energy and computational savings are substantial (up to 5x), real-world speedups are currently limited by the lack of hardware support for unstructured sparsity in standard GPUs. Future research will focus on optimizing software kernels and exploring applications in communication-constrained environments like Federated Learning.

Summary updated

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 backpropagation (backprop) algorithm, which roughly accounts for 2/3 of the computational complexity of training. In this work we propose a method for reducing the computational cost of backprop, which we named dithered backprop. It consists in 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 in a distributed training setting, where both communication as well as compute efficiency may increase simultaneously with the number of participant nodes.
BibTeX
@inproceedings{wiedemann2020dithered,
  author = {Simon Wiedemann and Temesgen Mehari and Kevin Kepp and Wojciech Samek},
  title = {{Dithered backprop: A sparse and quantized backpropagation algorithm for more efficient deep neural network training}},
  booktitle = {Workshops @ CVPR},
  year = {2020},
  url = {https://openreview.net/forum?id=PQiAxO0GILI},
}
Figure