Efficient Distributed Auto-Differentiation

Bradley T. Baker, Vince D. Calhoun, Barak A. Pearlmutter, Sergey M. Plis

Abstract

Although distributed machine learning has opened up many new and exciting research frontiers, fragmentation of models and data across different machines, nodes, and sites still results in considerable communication overhead, impeding reliable training in real-world contexts. The focus on gradients as the primary shared statistic during training has spawned a number of intuitive algorithms for distributed deep learning; however, gradient-centric training of large deep neural networks (DNNs) tends to be communication-heavy, often requiring additional adaptations such as sparsity constraints, compression, quantization, and more, to curtail bandwidth. We introduce an innovative, communication-friendly approach for training distributed DNNs, which capitalizes on the outer-product structure of the gradient as revealed by the mechanics of auto-differentiation. The exposed structure of the gradient evokes a new class of distributed learning algorithm, which is naturally more communication-efficient than full gradient sharing. Our approach, called distributed auto-differentiation (dAD), builds off a marriage of rank-based compression and the innate structure of the gradient as an outer-product. We demonstrate that dAD trains more efficiently than other state of the art distributed methods on modern architectures, such as transformers, when applied to large-scale text and imaging datasets. The future of distributed learning, we determine, need not be dominated by gradient-centric algorithms.

Introduction

Training large-scale deep neural networks (DNNs) in a distributed fashion typically relies on data-parallelism, where model updates are synchronized across nodes by sharing gradients. As models scale, these gradient matrices become a significant communication bottleneck. Traditional approaches attempt to mitigate this by compressing or quantizing gradients after they are computed. However, this "gradient-centric" paradigm ignores the underlying mathematical structure of the gradient itself. We propose a shift in perspective: by examining the auto-differentiation (AD) process, we can identify a more efficient way to share training statistics across a network.

Methodology: Distributed Auto-Differentiation

In reverse-mode auto-differentiation (backpropagation), the gradient of a layer's weights is computed as the outer product of two smaller matrices: the input activations and the partial derivatives (errors) from the output. Our proposed method, Distributed Auto-Differentiation (dAD), leverages this by sharing these smaller component matrices instead of the full, massive gradient matrix.

Comparison of existing gradient-centric approaches (A) with our proposed dAD (B) and rank-dAD (C) methods.

Building on dAD, we introduce rank-dAD, which further compresses these components along the batch dimension to a target rank $r$. To perform this efficiently, we developed Structured Power Iterations (SPI). Unlike standard SVD which operates on the full $O(h^2)$ gradient, SPI computes low-rank approximations directly from the component matrices in $O(h \times N)$ time, making it linear with respect to layer width. For recurrent networks, we extend this via BPTT by stacking time and batch dimensions, avoiding expensive reductions over sequence lengths.

Experimental Results

We evaluated rank-dAD across diverse architectures, including Feed-Forward Networks (MNIST), GRU-RNNs (UEA Time Series Archive), and Vision Transformers (CIFAR-10).

Test AUC performance of rank-dAD compared to power-SGD across different ranks for MNIST and Spoken Arabic Digits.

Key findings include:

  • Performance Parity: rank-dAD matches the accuracy (AUC) of state-of-the-art baselines like PowerSGD and standard distributed SGD (dSGD) across multiple datasets.
  • Significant Speedups: On MNIST, rank-dAD achieved a 15x speedup with 4 sites and up to a 25x speedup with 18 sites compared to dSGD.
  • Bandwidth Efficiency: Communication costs are reduced from quadratic $O(h_i \times h_{i+1})$ to linear $O(r \times h_i)$ per layer.

Insights and Future Directions

A core insight of this work is that gradients are inherently low-rank, with their rank bounded by the batch size ($N$). Since $N$ is typically much smaller than the hidden layer dimensions ($h$), the gradient is naturally a low-rank outer product. Furthermore, we observed that the "effective rank" of gradients tends to decrease as training progresses, suggesting that communication can become even more efficient over time.

While highly effective for Feed-Forward, RNN, and Transformer layers, applying dAD to Convolutional Neural Networks (CNNs) remains a challenge because activation sizes can exceed parameter counts. Future work will explore heuristics for CNNs and extend the dAD framework to other gradient-based optimization tasks, such as Bayesian inference or generic optimization with Hessians.

Summary updated

Abstract

Although distributed machine learning has opened up many new and exciting research frontiers, fragmentation of models and data across different machines, nodes, and sites still results in considerable communication overhead, impeding reliable training in real-world contexts. The focus on gradients as the primary shared statistic during training has spawned a number of intuitive algorithms for distributed deep learning; however, gradient-centric training of large deep neural networks (DNNs) tends to be communication-heavy, often requiring additional adaptations such as sparsity constraints, compression, quantization, and more, to curtail bandwidth. We introduce an innovative, communication-friendly approach for training distributed DNNs, which capitalizes on the outer-product structure of the gradient as revealed by the mechanics of auto-differentiation. The exposed structure of the gradient evokes a new class of distributed learning algorithm, which is naturally more communication-efficient than full gradient sharing. Our approach, called distributed auto-differentiation (dAD), builds off a marriage of rank-based compression and the innate structure of the gradient as an outer-product. We demonstrate that dAD trains more efficiently than other state of the art distributed methods on modern architectures, such as transformers, when applied to large-scale text and imaging datasets. The future of distributed learning, we determine, need not be dominated by gradient-centric algorithms.
BibTeX
@misc{baker2021efficient,
  author = {Bradley T. Baker and Vince D. Calhoun and Barak A. Pearlmutter and Sergey M. Plis},
  title = {{Efficient Distributed Auto-Differentiation}},
  year = {2021},
  eprint = {2102.09631},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2102.09631},
}
Figure