WoodFisher: Efficient Second-Order Approximation for Neural Network Compression

Sidak Pal Singh, Dan AlistarhNeurIPS 2020 · OpenReview

TL;DR

WoodFisher is an efficient method for estimating the inverse Hessian matrix—the "second-order" information of a loss function—to intelligently prune neural networks. By leveraging the Woodbury matrix identity and the Empirical Fisher matrix, it achieves state-of-the-art compression results on large-scale models like ResNet-50, significantly outperforming standard magnitude-based pruning.

The Challenge of Network Pruning

As deep learning models grow to include billions of parameters, deploying them on edge devices or in real-time applications becomes a massive computational challenge. Pruning—the process of removing redundant weights—is the standard solution to reduce model size and inference time.

The simplest approach is "magnitude pruning," which removes the smallest weights. However, this method ignores how different weights interact with one another. The theoretical "gold standard" for pruning is the Optimal Brain Surgeon (OBS) framework, which uses second-order information (the Hessian matrix) to determine which weights are truly least important to the loss function.

Unfortunately, the Hessian for a modern network is astronomical in size. Calculating its inverse is computationally prohibitive, scaling at $O(d^3)$ complexity for $d$ parameters. Existing shortcuts, like diagonal approximations or Kronecker-factored (K-FAC) methods, often sacrifice too much accuracy or are limited to specific network architectures. WoodFisher aims to provide a faithful and efficient estimate of this inverse Hessian that scales to industry-standard models.

The WoodFisher Method

The authors introduce WoodFisher, a method that combines three key mathematical and structural insights to bypass the $O(d^3)$ bottleneck:

  1. The Empirical Fisher as a Proxy: The authors demonstrate that the Empirical Fisher Information Matrix (built from first-order gradients) is a structurally accurate proxy for the Hessian, even early in training. While it may not match the exact scale, it captures the critical correlation structure between weights.
Comparison of Hessian and Empirical Fisher blocks
  1. The Woodbury Identity: Instead of inverting a giant matrix from scratch, WoodFisher uses the Woodbury matrix identity (specifically the Sherman-Morrison formula). This allows the algorithm to update the estimate of the inverse Hessian iteratively, one data sample at a time, effectively turning a cubic-time problem into a quadratic-time one.
  2. Block-wise Approximation: To scale to millions of parameters, the Hessian is treated as a "block-diagonal" matrix. By calculating the inverse for smaller "chunks" of weights (e.g., 1,000 parameters at a time), the computation becomes linear ($O(d)$) relative to the total number of parameters.

The resulting "pruning statistic" allows the algorithm to decide which weights to cut across the entire network simultaneously, rather than requiring researchers to manually set sparsity targets for every single layer.

Key Insights

  • Structure Matters More Than Scale: The Empirical Fisher might not match the exact values of the Hessian, but it captures the correlation structure between weights remarkably well. This structural fidelity is what makes it so effective for pruning.
  • Sample Efficiency: WoodFisher does not require the entire dataset to understand parameter importance. It produces excellent results using only a few hundred data samples (e.g., just 400 samples for a ResNet-50).
  • One-Shot Dominance: WoodFisher excels at "one-shot" pruning—pruning a pre-trained model in a single pass without any retraining. This is a severe stress test for pruning methods, and WoodFisher significantly outperforms magnitude pruning and K-FAC in this regime.
  • Automatic Layer-wise Sparsity: Because WoodFisher estimates the global importance of parameters, it automatically identifies which layers can be pruned heavily and which are sensitive, removing the need for tedious manual tuning.

Experimental Results

The authors evaluated WoodFisher across several standard benchmarks, including MNIST (MLPNET), CIFAR-10 (ResNet-20), and ImageNet ILSVRC (ResNet-50 and MobileNetV1).

  • ImageNet (ResNet-50): At 80% sparsity, WoodFisher achieved 76.73% Top-1 accuracy, nearly matching the dense model baseline (77.01%) and outperforming the popular STR method (76.19%).
  • Extreme Compression: At 95% sparsity on ImageNet, WoodFisher maintained 72.16% accuracy, while other state-of-the-art methods like STR dropped to 70.40%.
  • Real-world Speedups: When combined with specialized CPU inference engines, WoodFisher-pruned models demonstrated significant speedups over dense baselines with minimal accuracy loss.

Limitations and Future Directions

While highly effective, WoodFisher's block-diagonal assumption ignores correlations between different blocks or layers. Exploring cross-layer correlations could yield even higher accuracy at extreme sparsity levels. Additionally, while much faster than a full Hessian inversion, WoodFisher remains more computationally intensive than simple magnitude pruning.

The authors also briefly introduce WoodTaylor, an extension that incorporates first-order (gradient) information for models that haven't fully converged, opening a promising path for pruning during training. Beyond compression, the WoodFisher approximation shows potential for calculating "influence functions" (determining which training images most affected a prediction) and aiding in continual learning tasks.

Summary updated

Abstract

Second-order information, in the form of Hessian- or Inverse-Hessian-vector products, is a fundamental tool for solving optimization problems. Recently, there has been significant interest in utilizing this information in the context of deep neural networks; however, relatively little is known about the quality of existing approximations in this context. Our work considers this question, examines the accuracy of existing approaches, and proposes a method called WoodFisher to compute a faithful and efficient estimate of the inverse Hessian. Our main application is to neural network compression, where we build on the classic Optimal Brain Damage/Surgeon framework. We demonstrate that WoodFisher significantly outperforms popular state-of-the-art methods for one-shot pruning. Further, even when iterative, gradual pruning is allowed, our method results in a gain in test accuracy over the state-of-the-art approaches for popular image classification datasets such as ImageNet ILSVRC. Further, we show how our method can be extended to take into account first-order information, and illustrate its ability to automatically set layer-wise pruning thresholds, or perform compression in the limited-data regime.
BibTeX
@inproceedings{singh2020woodfisher,
  author = {Sidak Pal Singh and Dan Alistarh},
  title = {{WoodFisher: Efficient Second-Order Approximation for Neural Network Compression}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=PmOQRomD46Y},
}
Figure