Parallel Complexity of Forward and Backward Propagation

Maxim Naumov

Abstract

We show that forward and backward propagation in neural networks can be formulated as the solution of lower and upper triangular systems of equations. For standard feedforward (FNNs) and recurrent neural networks (RNNs), these triangular systems are block bi-diagonal, while for general directed acyclic graphs (DAGs), they exhibit more complex triangular sparsity patterns. By applying direct and iterative parallel algorithms, we demonstrate that model parallelism can be achieved with significant complexity reductions. Specifically, for FNNs with $k$ layers and RNNs with $\tau$ time steps, backward propagation can be performed in $O(\log k)$ and $O(\log k \log \tau)$ steps, respectively. This framework provides a mathematical foundation for scaling deep learning beyond the sequential layer-by-layer bottleneck.

Introduction: The Sequential Bottleneck

Training deep neural networks is traditionally a sequential process. In both forward and backward passes, the computation of layer $k+1$ is strictly dependent on the output of layer $k$. While data parallelism—distributing different chunks of a data batch across multiple GPUs—is widely used, model parallelism remains a challenge. Splitting the layers of a single network across multiple processors usually results in low hardware utilization because most processors remain idle while waiting for the sequential dependency chain to reach them.

As networks grow deeper and recurrent architectures unfold over longer sequences, this linear dependency ($O(k)$) becomes a major hurdle. This paper, authored by Maxim Naumov, reframes these dependencies as a problem of numerical linear algebra, allowing for the application of parallel solvers that can process multiple layers simultaneously.

Formulating Propagation as Linear Systems

The core innovation of this research is the representation of the entire neural network pass as a single, large matrix equation.

1. Triangular System Formulation

Forward propagation can be expressed as a block bi-diagonal lower triangular system: $$L\bar{z} = \bar{b}$$ Conversely, backward propagation is represented as an upper triangular system: $$R\bar{v} = \bar{c}$$ In an FNN or RNN, these matrices are sparse and structured, which is the key to unlocking parallel efficiency.

2. Handling Non-linearity

Linear algebra typically struggles with the non-linear activation functions (e.g., ReLU, Sigmoid) central to neural networks. Naumov addresses this by "hiding" these non-linearities within the diagonal elements of the matrices. These are treated as scaling factors that can be updated or estimated.

Interestingly, the backward pass is even better suited for this method than the forward pass. Because the forward pass is completed first, the derivatives of the activations are already known constants. This transforms the backward pass into a "true" linear system that can be solved exactly and in parallel.

Parallel Algorithms and Complexity

Once the network is expressed as a matrix system, we can apply two classes of parallel algorithms:

  • Direct Methods (Cyclic Reduction): This is a divide-and-conquer approach that recursively breaks the triangular system into smaller, independent sub-problems. This allows for the $O(\log k)$ complexity.
  • Iterative Methods: Algorithms such as Jacobi or BiCGStab can approximate the solution through repeated parallel matrix-vector multiplications. These are particularly useful in the later stages of training when the model parameters are near convergence.

Complexity Results

The theoretical impact on computational complexity is significant. By using a Parallel Random Access Machine (PRAM) model, the paper proves:

  • FNNs: Backward propagation complexity drops from $O(k)$ to $O(\log k)$.
  • RNNs: Complexity for $\tau$ time steps drops to $O(\log k \log \tau)$.

Practical Considerations and Limitations

While the mathematical speedup is impressive, the paper notes several practical trade-offs:

  1. Computational Overhead: Direct parallel methods involve matrix-matrix multiplications, which carry an $O(n^3)$ cost (where $n$ is layer width). This overhead means the parallel approach is most beneficial when the mini-batch size is large or the network is exceptionally deep.
  2. Memory Efficiency: The proposed direct methods require approximately double the memory of standard sequential propagation. While an increase, this remains within the feasible range for modern hardware.
  3. Forward Pass Approximation: Since the forward pass is inherently non-linear, the parallel version requires estimating values from previous iterations. This suggests the method might be most effective as a fine-tuning or late-stage training optimization.

Conclusion

By framing neural network propagation as a solution to triangular systems, this work transitions model parallelism from a heuristic engineering challenge into a well-defined problem of numerical linear algebra. The proof that backward propagation can be achieved in logarithmic time opens new avenues for training massive-scale models that were previously limited by the sequential depth of their architecture.

Summary updated

Abstract

We show that the forward and backward propagation can be formulated as a solution of lower and upper triangular systems of equations. For standard feedforward (FNNs) and recurrent neural networks (RNNs) the triangular systems are always block bi-diagonal, while for a general computation graph (directed acyclic graph) they can have a more complex triangular sparsity pattern. We discuss direct and iterative parallel algorithms that can be used for their solution and interpreted as different ways of performing model parallelism. Also, we show that for FNNs and RNNs with $k$ layers and $τ$ time steps the backward propagation can be performed in parallel in O($\log k$) and O($\log k \log τ$) steps, respectively. Finally, we outline the generalization of this technique using Jacobians that potentially allows us to handle arbitrary layers.
BibTeX
@misc{naumov2017parallel,
  author = {Maxim Naumov},
  title = {{Parallel Complexity of Forward and Backward Propagation}},
  year = {2017},
  eprint = {1712.06577},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1712.06577},
}
Figure