Computing Higher Order Derivatives of Matrix and Tensor Expressions

Sören Laue, Matthias Mitterreiter, Joachim GiesenNeurIPS 2018 · OpenReview

Introduction

Optimization is an integral part of most machine learning systems, and most numerical optimization schemes rely heavily on the computation of derivatives. While modern Automatic Differentiation (AD) frameworks excel at computing first-order gradients for scalar-valued functions, they struggle significantly with higher-order derivatives of matrix and tensor expressions.

This paper introduces a novel algorithmic framework capable of computing higher-order derivatives (such as Hessians) directly at the matrix and tensor level. By leveraging Ricci calculus instead of standard matrix notation, the authors generate compact, highly efficient code that outperforms state-of-the-art frameworks like TensorFlow and PyTorch by up to 1,000x on GPUs.

The Challenge: Scalarization and Expression Explosion

The core issue with existing tools is that they typically "scalarize" the problem, treating a matrix as a collection of individual scalar variables. For a simple function like $f(x) = x^T Ax$, the Hessian is simply $A^T + A$. However, standard frameworks often generate massive, inefficient expression graphs to compute this.

For a matrix of size $n=1000$, a traditional framework might create a computational graph with over a million nodes just to compute a Hessian. This "expression explosion" results in code that runs hundreds or thousands of times slower than a direct matrix evaluation. Consequently, second-order optimization methods (like Newton’s method) become impractical for many problems where they would otherwise be superior.

A Tensor-First Approach with Ricci Calculus

To bridge the gap between high-level matrix math and efficient computation, the authors propose a three-step pipeline:

  1. Translation to Ricci Calculus: Standard matrix notation is often ambiguous for differentiation, failing to clearly distinguish between linear maps and bilinear forms. The authors translate these expressions into Ricci calculus, a notation that uses precise indices (upper for contravariant, lower for covariant) to track how tensors behave under transformations.
  2. Tensor-Level Differentiation: They apply forward and reverse mode automatic differentiation directly at the tensor level within the Ricci representation. Unlike standard AD, which works on scalars, this approach treats tensors as atomic units.
  3. Back-Translation: The resulting derivative—still a compact tensor expression—is translated back into standard matrix notation and mapped to highly optimized BLAS (Basic Linear Algebra Subprograms) calls.
Computational graph illustrating tensor-level differentiation using Ricci calculus notation.

By staying at the tensor level, the framework avoids creating millions of nodes in a computational graph, keeping the mathematical structure intact and the resulting expressions compact.

Benchmarks and Key Results

The framework was evaluated on three representative "classical" machine learning optimization benchmarks:

  • Quadratic Functions: The simplest case with a non-vanishing Hessian ($x^T Ax$).
  • Logistic Regression: A staple of classification.
  • Matrix Factorization: A common problem in recommender systems where the Hessian is a fourth-order tensor.

The proposed method was compared against TensorFlow, PyTorch, Theano, and HIPS autograd, yielding dramatic improvements:

  • CPU Performance: The framework demonstrated a speedup of up to two orders of magnitude (100x) over state-of-the-art frameworks when evaluating Hessians.
  • GPU Performance: The performance gap widened to three orders of magnitude (1,000x). GPUs are particularly sensitive to the memory access patterns and "for-loop" overhead found in the large, fragmented expression graphs of traditional AD.
  • Graph Construction Time: While frameworks like TensorFlow took several seconds to even generate the expression graph for a second-order derivative, this tensor-first approach required only about 20 milliseconds.
Performance comparison across three classical machine learning benchmarks, demonstrating up to a 1,000x speedup over standard frameworks.

Because the output is a compact matrix expression, it can be executed using standard, highly-tuned linear algebra libraries that utilize CPU vectorization (SSE/AVX) and GPU parallelism much more effectively than a scalar graph.

Limitations and Future Work

While groundbreaking for specific applications, the authors acknowledge that Hessians are rarely used in large-scale deep learning, where first-order SGD variants dominate. This work is most immediately impactful for "classical" ML (e.g., logistic regression, LASSO, Gaussian processes) where Newton-style optimization is both feasible and efficient.

Currently, the paper presents a standalone framework (available at MatrixCalculus.org). Integrating this "tensor-first" differentiation logic into mainstream deep learning libraries would be a significant next step, making these massive speedups accessible to the broader machine learning community.

Summary updated

Abstract

Optimization is an integral part of most machine learning systems and most numerical optimization schemes rely on the computation of derivatives. Therefore, frameworks for computing derivatives are an active area of machine learning research. Surprisingly, as of yet, no existing framework is capable of computing higher order matrix and tensor derivatives directly. Here, we close this fundamental gap and present an algorithmic framework for computing matrix and tensor derivatives that extends seamlessly to higher order derivatives. The framework can be used for symbolic as well as for forward and reverse mode automatic differentiation. Experiments show a speedup between one and four orders of magnitude over state-of-the-art frameworks when evaluating higher order derivatives.
BibTeX
@inproceedings{laue2018computing,
  author = {Sören Laue and Matthias Mitterreiter and Joachim Giesen},
  title = {{Computing Higher Order Derivatives of Matrix and Tensor Expressions}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2018},
  url = {https://openreview.net/forum?id=H1bQ0PZuWS},
}

Loading related content...

Figure