M-FAC: Efficient Matrix-Free Approximations of Second-Order Information

Elias Frantar, Eldar Kurtic, Dan Alistarh

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:

  1. 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.
  2. 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

Table comparing pruning accuracy and computational costs of M-FAC against baselines.

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.

Composite results showing M-FAC's performance in pruning and optimization.

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

Abstract

Efficiently approximating local curvature information of the loss function is a useful tool for the optimization and compression of deep neural networks. Yet, most existing methods to approximate second-order information have high computational or storage costs, limiting their practicality. In this work, we investigate matrix-free approaches for estimating Inverse-Hessian Vector Products (IHVPs) for the case when the Hessian can be approximated as a sum of rank-one matrices, as in the classic approximation of the Hessian by the empirical Fisher matrix. The first algorithm we propose is tailored towards network compression and can compute the IHVP for dimension $d$ given a fixed set of $m$ rank-one matrices using $O(dm^2)$ precomputation, $O(dm)$ cost for computing the IHVP and query cost $O(m)$ for computing any single element of the inverse Hessian approximation. The second algorithm targets an optimization setting, where we wish to compute the product between the inverse Hessian, estimated over a sliding window of optimization steps, and a given gradient direction. We give an algorithm with cost $O(dm + m^2)$ for computing the IHVP and $O(dm + m^3)$ for adding or removing any gradient from the sliding window. We show that both algorithms yield competitive results for network pruning and optimization, respectively, with significantly lower computational overhead relative to existing second-order methods.
BibTeX
@inproceedings{frantar2021m,
  author = {Elias Frantar and Eldar Kurtic and Dan Alistarh},
  title = {{M-FAC: Efficient Matrix-Free Approximations of Second-Order Information}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=EEq6YUrDyfO},
}
Figure