Introduction
M-FAC (Matrix-Free Approximate Curvature) is a novel framework that allows deep learning models to leverage second-order "Hessian" information—the local geometry of the loss function—without incurring prohibitive memory and compute costs. By treating the Hessian as a sum of rank-one matrices, M-FAC enables linear-time computation of inverse-Hessian vector products, achieving state-of-the-art results in both neural network pruning and optimization.
The Problem: The Curse of Dimensionality
In deep learning, knowing the "curvature" of the loss function (represented by the Hessian matrix) is incredibly valuable. It reveals which weights are unimportant (crucial for pruning) and how to adjust learning steps to converge faster (crucial for optimization).
However, the Hessian is a $d \times d$ matrix, where $d$ is the number of model parameters. For a standard ResNet-50, storing the full Hessian would require roughly 2.5 Petabytes of memory, making direct usage impossible. Existing approximations either sacrifice accuracy by relying on diagonal methods, are limited to specific layer types (like K-FAC), or remain too slow for large-scale models. M-FAC bridges this gap by providing an exact, matrix-free way to compute the Inverse-Hessian Vector Product (IHVP) in $O(d)$ time and space.
The M-FAC Approach
The core of M-FAC relies on the empirical Fisher information matrix, which approximates the Hessian as a sum of $m$ rank-one matrices (outer products of gradients). The authors leverage the Woodbury-Sherman-Morrison formula, a mathematical identity for inverting matrices that have been updated by a low-rank term.
Their primary innovation lies in two specific algorithms that avoid ever forming the massive $d \times d$ matrix, instead storing only $m$ gradients and small $m \times m$ scalar matrices:
- The Static Algorithm (Pruning): Designed for a fixed model, this algorithm unrolls the Woodbury recursion to work exclusively with vectors and scalars. It can compute an IHVP in $O(dm)$ time and query any single element of the inverse Hessian in $O(m)$ time.
- The Dynamic Algorithm (Optimization): Designed for preconditioned SGD, this approach maintains a "sliding window" of the last $m$ gradients. As new gradients arrive, it updates the inverse estimate in $O(dm + m^3)$ time without recomputing the entire history.
Key Insights
- Linear Complexity is Possible: The most significant breakthrough is demonstrating that block-wise approximations are not strictly necessary for large models. If the Hessian is a sum of rank-one matrices, the inverse-vector product can be computed in time linear to the model dimension $d$.
- Efficiency Enables Accuracy: Because M-FAC is vastly faster than previous methods like WoodFisher (often $100\times$ faster under the same settings), researchers can use much larger values for $m$ (the number of gradients). Incorporating more gradients leads to a significantly more accurate approximation of the Hessian.
- Preconditioning vs. Momentum: In optimization tests, M-FAC (without momentum) often outperformed standard SGD with momentum. This suggests that a high-quality second-order preconditioner can effectively compensate for the lack of first-order momentum heuristics.
Results: Pruning and Optimization
Network Pruning: M-FAC sets a new standard for model compression. On MobileNet-V1 (ImageNet), M-FAC achieved 65.01% Top-1 accuracy at 89% sparsity, significantly outperforming the previous state-of-the-art WoodFisher (63.87%) and STR (62.10%). Furthermore, as shown in the performance tables, M-FAC drastically reduces compute time. For instance, computing the inverse Hessian approximation for MobileNetV1-STR took M-FAC only 0.5 minutes compared to WoodFisher's 60 minutes.
Optimization Speed and Convergence: Visualized in the composite charts above, M-FAC demonstrates superior performance across both domains. In pruning (panels a and b), it maintains higher accuracy at extreme sparsity levels compared to layer-wise and global magnitude baselines. In optimization (panels c and d), M-FAC accelerates training convergence on WRN-40-2 / CIFAR-100, reaching lower training loss and higher test accuracy faster than Adam or SGD.
Remarkably, M-FAC's computational overhead during optimization is only 5%–55% relative to vanilla SGD, which is substantially lower than other second-order optimizers like AdaHessian or GGT. When applied to NLP tasks, M-FAC consistently outperformed the Adam baseline across almost all GLUE tasks when training BERT models, yielding up to a ~15 point gain on STS-B for BERT-tiny.
Limitations and Future Work
While M-FAC successfully avoids the $O(d^2)$ storage of the full Hessian, it still requires storing $m$ gradients of dimension $d$. For the largest modern architectures (like GPT-scale models), this $O(dm)$ requirement could still pose a significant memory burden.
Future work may focus on optimizing this gradient storage through parallelization or gradient compression techniques. Additionally, while M-FAC performs robustly with default settings, more extensive grid-searching of learning rates and dampening constants could unlock even greater performance gains.
Summary updated