SparseProp: Efficient Sparse Backpropagation for Faster Training of Neural Networks

Mahdi Nikdan, Tommaso Pegolotti, Eugenia Iofinova, Eldar Kurtic, Dan Alistarh

Abstract

SparseProp is a vectorized implementation of the backpropagation algorithm optimized for neural networks with unstructured sparse weights. By utilizing CPU SIMD instructions (AVX2), SparseProp achieves significant training speedups—up to 1.85x for transfer learning and 1.4x for training from scratch. This work demonstrates that unstructured sparsity can be a practical tool for accelerating training on commodity hardware, overcoming the traditional performance bottlenecks associated with irregular memory access patterns.

Introduction

While sparsity is widely used to compress models for inference, leveraging it to accelerate the training process remains a significant challenge. The primary obstacle is unstructured sparsity, where zero-valued weights are distributed randomly. Modern hardware, such as CPUs and GPUs, is optimized for dense, regular computations and typically fails to gain efficiency from these "holey" matrices. Consequently, standard deep learning frameworks often treat sparse models as dense during training, yielding no time savings. SparseProp addresses this by providing system-level support for arbitrary, unstructured sparsity on general-purpose CPUs.

Methods

SparseProp is a library of vectorized kernels designed for linear and convolutional layers, optimized for x86 CPUs using AVX2 (Advanced Vector Extensions).

SIMD Optimization and Unified Backpass

The algorithm follows a "Load-Compute-Store" paradigm to minimize memory bottlenecks. For linear layers, SparseProp implements a unified backpass, performing a single pass to calculate both the weight and input gradients. This approach significantly reduces the frequency of reading the sparse weight matrix from memory.

SparseProp vectorization logic for linear and convolutional layers.

Specialized Kernels

The library utilizes a variation of the Compressed Sparse Row (CSR) format. For convolutional layers, two specialized kernels were developed: one for small inputs and a "permuted" version (SparseConvOverON) that vectorizes over spatial dimensions to handle larger images more efficiently. These kernels are integrated into PyTorch via pybind11, allowing for seamless replacement of standard layers.

Evaluation

The researchers evaluated SparseProp across diverse tasks:

  • Computer Vision: Pre-training on ImageNet-1K, followed by transfer learning and from-scratch training on 12 datasets (e.g., CIFAR-10/100, Caltech-101/256).
  • Natural Language Processing: Fine-tuning a pruned BERT-base model on MNLI and QQP tasks from the GLUE benchmark.
  • Multi-attribute Prediction: Training on the CelebA dataset.

Key Results

A critical finding is that SparseProp’s runtime scales linearly with the number of non-zero weights, enabling proportional training time reductions as sparsity increases.

Microbenchmarks

At 99% sparsity, SparseProp achieved a 5x speedup for linear layers and a 19x speedup for convolutional layers compared to dense PyTorch baselines. Figure 5 illustrates the performance gains in the backward pass for both layer types.

Performance comparison of linear (a) and convolutional (b) backward passes across varying sparsity levels.

End-to-End Performance

  • Transfer Learning: Fine-tuning a 95% sparse ResNet50 resulted in a 1.85x total runtime speedup (3.6x speedup specifically in the backward pass).
  • Training from Scratch: ResNet18 trained at 95% sparsity achieved a 1.4x speedup with minimal accuracy loss.
  • NLP: BERT models saw a 37% speedup on a single core for inference and fine-tuning at 97% sparsity.

Discussion and Future Work

SparseProp demonstrates that optimized CPU kernels can make sparse training a viable alternative, especially for edge scenarios like local fine-tuning. However, several challenges remain:

  • Synchronization Overheads: Multithreaded speedups are currently limited by core management overhead; future work will focus on better parallelization.
  • Framework Bottlenecks: Non-mathematical operations (e.g., ReLU, Batch Normalization) still rely on standard frameworks. Integrating these into sparse kernels could further improve performance.
  • Hardware Portability: Current optimizations are specific to AVX2-enabled CPUs. Extending support to ARM architectures and specialized accelerators is a key next step.

Summary updated

Abstract

We provide a new efficient version of the backpropagation algorithm, specialized to the case where the weights of the neural network being trained are sparse. Our algorithm is general, as it applies to arbitrary (unstructured) sparsity and common layer types (e.g., convolutional or linear). We provide a fast vectorized implementation on commodity CPUs, and show that it can yield speedups in end-to-end runtime experiments, both in transfer learning using already-sparsified networks, and in training sparse networks from scratch. Thus, our results provide the first support for sparse training on commodity hardware.
BibTeX
@misc{nikdan2023sparseprop,
  author = {Mahdi Nikdan and Tommaso Pegolotti and Eugenia Iofinova and Eldar Kurtic and Dan Alistarh},
  title = {{SparseProp: Efficient Sparse Backpropagation for Faster Training of Neural Networks}},
  year = {2023},
  eprint = {2302.04852},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2302.04852},
}
Figure