This paper, published in the IMA Journal of Numerical Analysis in 1992 (originally a 1990 technical report), is a foundational contribution to the field of Automatic Differentiation (AD). It describes an efficient way to compute second-order derivatives (the Hessian matrix) using an extension of the "reverse mode" technique.
TL;DR
The paper presents an algorithm to automatically calculate the Hessian matrix of a function using an extension of reverse accumulation. It demonstrates that a directional second derivative can be computed for roughly twice the cost of a gradient, enabling efficient, parallelizable extraction of the full Hessian.
What Problem Does This Paper Address?
In numerical optimization, knowing the Hessian matrix (the matrix of second-order partial derivatives) is incredibly useful for methods like Newton’s method, which converge much faster than simple gradient descent. However, calculating the Hessian is traditionally expensive.
If a function has $n$ variables, a naive approach might require $O(n^2)$ work. While "reverse accumulation" (the ancestor of modern backpropagation) made calculating gradients ($O(n)$ variables) very efficient—costing only a small constant multiple of the function evaluation itself—extending this efficiency to second derivatives was a significant challenge. The author seeks a method that is both computationally efficient and compatible with modern programming practices like operator overloading.
Methods
The author proposes an extension to the standard reverse accumulation algorithm:
- Computational Graph Construction: Using operator overloading (implemented in Ada), the program builds a "linearized" version of the function's computational graph at runtime. Each "atomic" operation (addition, multiplication, sine, etc.) is recorded as a node in a list.
- Directional Second Derivatives: Instead of trying to compute the whole Hessian at once, the method focuses on computing the product $(Hf)u$, where $H$ is the Hessian and $u$ is an arbitrary constant vector.
- The "Reverse-of-Reverse" Approach: The algorithm essentially "unfolds" the gradient accumulation process and applies the logic of reverse accumulation to that unfolded graph.
- Pre-accumulation: To manage the high memory overhead of reverse mode, the paper discusses "pre-accumulating" sub-graphs (like user-defined subroutines), effectively treating them as single atomic operations to save space.
Datasets
The paper does not use "datasets" in the modern machine learning sense. Instead, it evaluates the algorithm using a complex mathematical benchmark:
- The Helmholtz Energy Function: A non-linear function used in thermodynamics, tested with $n=100$ independent variables.
- Hardware/Software Environment: The implementation was tested on a Sun 3/160 (using VADS 5.5 Ada) and a VAX/VMS system to compare how software-based vs. hardware-based floating-point operations affect performance.
Key Insights and Ideas
- The 2W/3S Rule: The most significant insight is the theoretical bound. The author shows that a directional second derivative can be calculated in about 2W time units and 3S space units, where $W$ and $S$ are the time and space required for a gradient evaluation.
- Parallelism by Design: Because each row of the Hessian is simply a directional derivative where the direction $u$ is a unit vector, all $n$ rows of the Hessian can be computed simultaneously on $n$ processors with zero communication/interlocking required between them.
- Tightness of Bounds: The author provides a specific example function—$f(x) = (x \cdot x)^2$—to prove that their computational complexity bounds are "tight" (within a constant factor of the theoretical minimum).
- Graph Re-use: If the structure of the function doesn't change between iterations (e.g., in an optimization loop), the computational graph can be built once and "re-used" by simply updating the values in the nodes, drastically reducing overhead.
Key Results
- Empirical Efficiency: On the Sun 3/160, calculating the gradient took about 3x the time of the basic function evaluation. Calculating a directional second derivative took about 2.1x the time of the gradient evaluation, closely matching the theoretical "2W" prediction.
- Overhead Observations: The paper notes that when hardware floating-point support is enabled, the "administrative" overhead of AD (pointer manipulation and graph traversal) becomes more prominent, as the actual math happens so much faster.
- Normalization: In the Ada implementation, the total time to accumulate a directional second derivative was roughly 6x the time of a standard function evaluation—a very impressive result for second-order information.
Limitations and Future Work
- Memory Intensity: Reverse accumulation is notoriously memory-hungry because it must store the entire computational graph. While "pre-accumulation" helps, the space requirements remain a hurdle for extremely large problems.
- Language Limitations: The author notes that Ada (at the time) did not allow overloading the assignment operator, requiring explicit type conversion calls which made the code less "transparent" than it could be in a language like C++.
- Sparsity: The method described is "dense." For problems where the Hessian is mostly zeros (sparse), the author acknowledges that a great deal of time is wasted and suggests that future work should integrate "explicitly sparse" accumulation techniques.
- Hardware Suggestions: The paper concludes by suggesting that computer architects should design systems that better support "pointer-oriented" data structures (like pre-fetching chains of pointers) to make AD even faster.
Summary updated