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