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

Kyle R. Chickering

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 to arbitrarily many derivatives. $n$-TangentProp computes the exact derivative $d^n/dx^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.

Introduction: The Exponential Wall

Physics-Informed Neural Networks (PINNs) have emerged as a powerful paradigm for solving differential equations. However, they face a significant computational bottleneck: the calculation of higher-order derivatives. Standard automatic differentiation (autodiff) frameworks, like those in PyTorch or TensorFlow, are optimized for first-order gradients used in backpropagation. When applied recursively to compute 3rd, 5th, or 9th-order derivatives—required for complex physical systems like fluid dynamics or quantum mechanics—autodiff encounters an "exponential wall."

The runtime and memory requirements for standard autodiff scale as $O(M^n)$, where $M$ is the number of parameters and $n$ is the derivative order. This scaling makes high-order PINNs computationally untenable for large models, often exhausting GPU memory or requiring prohibitive computation times. The core inefficiency lies in autodiff building a massive computational graph for all partial derivatives, even though PINN training typically only requires derivatives with respect to network inputs.

Methodology: $n$-TangentProp

To overcome this, we introduce $n$-TangentProp, an extension of the TangentProp formalism. Instead of relying on recursive backpropagation, $n$-TangentProp differentiates the network directly during the forward pass.

The algorithm utilizes Faà di Bruno’s formula, a generalization of the chain rule for higher-order derivatives. By applying this formula layer-by-layer:

  1. All $n$ derivatives are computed in a single forward pass.
  2. Runtime complexity is reduced to $O(e^{\sqrt{n}} M)$, which is quasilinear relative to the derivative order.
  3. Memory complexity scales linearly, $O(nM)$, a massive improvement over the exponential scaling of standard autodiff.

Empirical Evaluation

We evaluated $n$-TangentProp against standard autodiff using synthetic benchmarks and the Self-Similar Burgers Equation. The benchmarks involved feed-forward networks with varying depths and widths to verify theoretical scaling laws.

The ratio of autodifferentiation runtime to $n$-TangentProp runtime across various network depths, widths, and derivative orders.

As shown in the figure above, while standard autodiff can be faster for low-order derivatives (1st or 2nd) due to highly optimized C++ implementations, $n$-TangentProp becomes significantly more efficient as the derivative order increases. At 8 derivatives, the runtime ratio (autodiff / $n$-TangentProp) reaches values between 10 and 20 across various architectures.

Key Results and Discussion

The empirical results confirm that $n$-TangentProp successfully bypasses the exponential scaling of traditional methods.

Comparison of average runtime between $n$-TangentProp and standard autodifferentiation as the number of derivatives increases. The bottom plot uses a log scale to highlight the exponential growth of autodiff.
  • Significant Speedups: For a standard PINN architecture, $n$-TangentProp was 2.5x faster for 3 derivatives and 7x faster for 5 derivatives.
  • Enabling High-Order Physics: We computed a profile requiring 7 derivatives in under an hour, a task estimated to take over 25 hours with standard autodiff. We successfully ran 45,000 epochs for a 9th-order derivative profile in 90 minutes—a task previously considered "untenable."
  • Memory Efficiency: Linear memory scaling allowed $n$-TangentProp to handle 9th-order derivatives easily on hardware where standard autodiff failed due to memory exhaustion.

Limitations and Future Work

Despite its advantages, $n$-TangentProp currently has higher overhead for low-order derivatives, likely due to its Python-based implementation compared to PyTorch's C++ backend. Future work will focus on implementing the core logic in C++ and further optimizing vectorized computations of Faà di Bruno coefficients. Additionally, while the algorithm computes high-order derivatives efficiently, the challenge of ensuring PINN convergence at extreme orders remains an open research problem.

The code for this paper is available at https://github.com/kyrochi/n_tangentprop.

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 \cite{simard1991tangent} to arbitrarily many derivatives. $n$-TangentProp computes the exact derivative $d^n/dx^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 \ntp 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.
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},
}

Loading related content...

Figure