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:
- 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.
- 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.
- 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.
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.
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