A Simple and Efficient Tensor Calculus

Sören Laue, Matthias Mitterreiter, Joachim Giesen

Abstract

Modern deep learning frameworks excel at computing gradients for scalar loss functions but often falter when tasked with higher-order derivatives like Jacobians and Hessians. This paper introduces a provably correct tensor calculus based on standard Einstein notation that achieves speedups of up to three orders of magnitude. By bridging the gap between rigorous differential geometry and practical machine learning implementations, this approach makes high-performance second-order optimization feasible for a much broader range of models.

Introduction

The efficiency of modern machine learning relies heavily on Automatic Differentiation (AD). While frameworks like TensorFlow, PyTorch, and JAX are highly optimized for first-order gradients, they frequently struggle with non-scalar functions. Computing the Jacobian of a vector or the Hessian of model parameters often defaults to inefficient entry-by-entry calculations, which can be 1,000 times slower than theoretically possible.

A previous breakthrough solved this speed issue but relied on Ricci notation, which introduced mathematical complexities (like co- and contravariant tensors) that are incompatible with the multi-dimensional array structures used in standard ML frameworks. This research proposes a coherent tensor calculus using Einstein notation, proving that high performance does not require the overhead of Ricci notation.

Methodology: A Unified Tensor Calculus

The core of the proposed method is a flexible multiplication operator ($*$) that unifies inner, outer, and element-wise products. This operator is proven to be associative, commutative, and distributive, providing a stable foundation for AD.

Computational graph illustrating the proposed tensor calculus notation and the propagation of derivatives through various operations.

Advanced AD Modes

Beyond standard forward and reverse modes, the authors introduce:

  1. Cross-Country Mode: A hybrid approach that reorders multiplications to prioritize lower-order tensors (e.g., vectors) first. This heuristic significantly reduces the size of intermediate results and computational complexity.
  2. Derivative Compression: Higher-order derivatives often contain redundant "unit tensors" (like identity matrices). By identifying and "compressing" these out, a 4th-order Hessian can be represented and computed as a much smaller 2nd-order matrix.

Experimental Evaluation

The method was evaluated using synthetic, dense data across three benchmarks:

  • Logistic Regression: A baseline classification task.
  • Matrix Factorization: Focusing on large-scale non-regularized scenarios.
  • Small Neural Network: A 10-layer fully connected network with ReLU activations.

Synthetic data allowed for the measurement of raw computational efficiency, isolating the performance of the calculus from external factors like data sparsity or specific distributions.

Key Results and Performance

The proposed calculus consistently outperformed existing frameworks by 2 to 3 orders of magnitude when computing Hessians on both CPU and GPU.

Performance comparison across various tasks and frameworks showing significant speedups achieved by the proposed modes.

Key findings include:

  • Efficiency: In logistic regression, "cross-country" mode provided a 30% speedup over standard reverse mode on the CPU.
  • Feasibility: Computing the full Hessian for neural networks, previously considered computationally prohibitive, is now feasible.
  • Comparison with JAX: While JAX (via XLA) is faster than older frameworks, the proposed method remains superior, particularly in large-scale problems where JAX's vmap often encounters memory limitations.

Conclusion and Future Work

This paper demonstrates that a simple shift in notation and a smarter ordering of operations can unlock massive performance gains in tensor AD. By aligning with the Einstein notation already used in the industry, this calculus is primed for integration into existing deep learning ecosystems. Future research will explore optimal multiplication ordering—an NP-hard problem—and specialized optimizations for sparse tensor structures.

Summary updated

Abstract

Computing derivatives of tensor expressions, also known as tensor calculus, is a fundamental task in machine learning. A key concern is the efficiency of evaluating the expressions and their derivatives that hinges on the representation of these expressions. Recently, an algorithm for computing higher order derivatives of tensor expressions like Jacobians or Hessians has been introduced that is a few orders of magnitude faster than previous state-of-the-art approaches. Unfortunately, the approach is based on Ricci notation and hence cannot be incorporated into automatic differentiation frameworks like TensorFlow, PyTorch, autograd, or JAX that use the simpler Einstein notation. This leaves two options, to either change the underlying tensor representation in these frameworks or to develop a new, provably correct algorithm based on Einstein notation. Obviously, the first option is impractical. Hence, we pursue the second option. Here, we show that using Ricci notation is not necessary for an efficient tensor calculus and develop an equally efficient method for the simpler Einstein notation. It turns out that turning to Einstein notation enables further improvements that lead to even better efficiency.
BibTeX
@inproceedings{laue2020simple,
  author = {Sören Laue and Matthias Mitterreiter and Joachim Giesen},
  title = {{A Simple and Efficient Tensor Calculus}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.1609/aaai.v34i04.5881},
}
Figure