A Quasilinear Algorithm for Computing Higher-Order Derivatives of Deep Feed-Forward Neural Networks

Kyle R. Chickering

Introduction

Physics-Informed Neural Networks (PINNs) have emerged as a transformative approach for solving differential equations by embedding physical laws directly into the loss function. However, as the complexity of the physical systems increases—requiring higher-order derivatives for Sobolev training or complex partial differential equations (PDEs)—researchers encounter a "computational wall." Standard automatic differentiation (AD), while efficient for first-order gradients, scales exponentially with the order of the derivative. This paper introduces $n$-TANGENTPROP, an algorithm designed to compute exact higher-order derivatives in quasilinear time, enabling the training of models on problems previously considered computationally intractable.

The Autodifferentiation Bottleneck

In the current deep learning ecosystem, AD is the standard for computing gradients. However, for an $n$-th order derivative, AD typically requires $O(M^n)$ time, where $M$ represents the number of parameters. This exponential growth leads to two primary failures in the context of PINNs:

  1. Time Complexity: Training a model requiring a 7th or 9th derivative can take days or weeks using standard methods.
  2. Memory Exhaustion: AD builds a massive computational graph. For high-order derivatives, this graph grows so large that it quickly exceeds the memory capacity of modern hardware (e.g., an NVIDIA A6000 with 48GB RAM).

Methodology: $n$-TANGENTPROP

The proposed $n$-TANGENTPROP algorithm extends the TANGENTPROP formalism to an arbitrary number of derivatives. Unlike AD, which traverses a computational graph recursively, $n$-TANGENTPROP computes derivatives directly during the forward pass.

Mathematical Foundation

The core of the algorithm is Faà di Bruno’s formula, which generalizes the chain rule to higher-order derivatives using Bell polynomials. The authors observe that in PINN training, we specifically require derivatives with respect to the input coordinates, not the entire weight matrix. By focusing on this subset, $n$-TANGENTPROP achieves:

  • Time Complexity: $O(e^{\sqrt{n}} M)$, which is quasilinear relative to the exponential scaling of AD.
  • Memory Complexity: $O(nM)$, providing linear scaling that prevents GPU memory overflows.

Experimental Evaluation

The authors validated $n$-TANGENTPROP through two distinct lenses: synthetic benchmarks and a physical "stress test."

Synthetic Benchmarks

The algorithm was tested on feed-forward neural networks with varying depths (3 to 7 layers) and widths (up to 128 neurons) using the tanh activation function. These tests confirmed that while PyTorch’s native AD scales exponentially, $n$-TANGENTPROP maintains its predicted quasilinear performance across increasing derivative orders.

The Self-Similar Burgers Equation

To demonstrate real-world utility, the authors applied the algorithm to a 1D shock formation problem in the Burgers equation. This problem requires enforcing smoothness on the 3rd, 5th, 7th, and 9th derivatives at the origin to reach a physically valid solution. This "unstable profile" serves as a rigorous test for the algorithm's accuracy and efficiency.

Key Results and Performance Gains

The empirical results highlight a widening performance gap as the derivative order increases:

  • 3rd Derivative: Achieved a 2.5x end-to-end speedup compared to standard AD.
  • 5th Derivative: The speedup increased to 7x.
  • 7th Derivative: The algorithm achieved a 25x speedup, reducing a day-long computation to under an hour.
  • 9th Derivative: $n$-TANGENTPROP completed the task in less than two hours. In contrast, standard AD was estimated to require over 100 hours, assuming it could bypass the memory limits that typically cause it to crash.

The algorithm shows particular synergy with L-BFGS optimizers. Since L-BFGS performs multiple line searches (forward passes) for every backward pass, the efficiency of $n$-TANGENTPROP’s forward-pass derivative calculation is significantly amplified.

Limitations and Future Directions

Despite its success at high orders, $n$-TANGENTPROP currently faces a "low-order gap." For 1st and 2nd derivatives, standard PyTorch AD remains faster. This is attributed to PyTorch’s highly optimized C++/CUDA backend, whereas the current $n$-TANGENTPROP implementation is written in Python. Additionally, the current version does not fully vectorize the computation of Bell polynomials, which limits performance gains for extremely large batch sizes.

Future work will focus on porting the algorithm to a C++/CUDA implementation to close the low-order performance gap and extending the framework to handle multi-dimensional, high-order PDEs more efficiently.

Conclusion

$n$-TANGENTPROP provides a scalable solution to the high-order derivative problem in neural networks. By reducing the computational complexity from exponential to quasilinear, it opens new avenues for physics-informed machine learning, allowing researchers to explore complex physical phenomena that were previously beyond reach.

Summary updated

Abstract

The use of neural networks for solving differential equations is practically difficult due to the exponentially increasing runtime of autodifferentiation when computing high-order derivatives. We propose \(n\)-TANGENTPROP , the natural extension of the TANGENTPROP formalism[1] to arbitrarily many derivatives. \(n\)-TANGENTPROP computes the exact derivative \({d^{n}/d}x^{n}f{(x)}\) in quasilinear, instead of exponential time, for a densely connected, feed-forward neural network \(f\) with a smooth, parameter-free activation function. We validate our algorithm empirically across a range of depths, widths, and number of derivatives. We demonstrate that our method is particularly beneficial in the context of physics-informed neural networks where \(n\)-TANGENTPROP allows for significantly faster training times than previous methods and has favorable scaling with respect to both model size and loss-function complexity as measured by the number of required derivatives. The code for this paper can be found at https://github.com/kyrochi/n_tangentprop. [https://github.com/kyrochi/n_tangentprop]
BibTeX
@misc{chickering2024quasilinear,
  author = {Kyle R. Chickering},
  title = {{A Quasilinear Algorithm for Computing Higher-Order Derivatives of Deep Feed-Forward Neural Networks}},
  year = {2024},
  eprint = {2412.09752},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2412.09752},
}
Figure