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

arXiv: https://arxiv.org/abs/2107.03356 · HTML: https://mlsanity.com/paper/2107.03356/

## Key facts

- Cited by 54 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 59 references that are in the map.
- First posted on arXiv 7 Jul 2021.

## Builds on (most cited first, 26 of 26)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [ImageNet Large Scale Visual Recognition Challenge](https://mlsanity.com/paper/1409.0575/) (2014)
- [GLUE: A Multi-Task Benchmark and Analysis Platform for Natural Language Understanding](https://mlsanity.com/paper/1804.07461/) (2018)
- [MobileNets: Efficient Convolutional Neural Networks for Mobile Vision Applications](https://mlsanity.com/paper/1704.04861/) (2017)
- [Wide Residual Networks](https://mlsanity.com/paper/1605.07146/) (2016)
- [Know What You Don't Know: Unanswerable Questions for SQuAD](https://mlsanity.com/paper/1806.03822/) (2018)
- [Optimizing Neural Networks with Kronecker-factored Approximate Curvature](https://mlsanity.com/paper/1503.05671/) (2015)
- [To prune, or not to prune: exploring the efficacy of pruning for model compression](https://mlsanity.com/paper/1710.01878/) (2017)
- [Variational Dropout and the Local Reparameterization Trick](https://mlsanity.com/paper/1506.02557/) (2015)
- [The State of Sparsity in Deep Neural Networks](https://mlsanity.com/paper/1902.09574/) (2019)
- [New insights and perspectives on the natural gradient method](https://mlsanity.com/paper/1412.1193/) (2014)
- [Learning to Prune Deep Neural Networks via Layer-wise Optimal Brain Surgeon](https://mlsanity.com/paper/1705.07565/) (2017)
- [Limitations of the Empirical Fisher Approximation for Natural Gradient Descent](https://mlsanity.com/paper/1905.12558/) (2019)
- [ADAHESSIAN: An Adaptive Second Order Optimizer for Machine Learning](https://mlsanity.com/paper/2006.00719/) (2020)
- [Soft Threshold Weight Reparameterization for Learnable Sparsity](https://mlsanity.com/paper/2002.03231/) (2020)
- [A Kronecker-factored approximate Fisher matrix for convolution layers](https://mlsanity.com/paper/1602.01407/) (2016)
- [EigenDamage: Structured Pruning in the Kronecker-Factored Eigenbasis](https://mlsanity.com/paper/1905.05934/) (2019)
- [Faster gaze prediction with dense networks and Fisher pruning](https://mlsanity.com/paper/1801.05787/) (2018)
- [On the interplay between noise and curvature and its effect on optimization and generalization](https://mlsanity.com/paper/1906.07774/) (2019)
- [Large-Scale Distributed Second-Order Optimization Using Kronecker-Factored Approximate Curvature for Deep Convolutional Neural Networks](https://mlsanity.com/paper/1811.12019/) (2018)
- [meProp: Sparsified Back Propagation for Accelerated Deep Learning with Reduced Overfitting](https://mlsanity.com/paper/1706.06197/) (2017)
- [Neumann Optimizer: A Practical Optimization Algorithm for Deep Neural Networks](https://mlsanity.com/paper/1712.03298/) (2017)

## Built on by (most cited first, 30 of 54)

- [GPTQ: Accurate Post-Training Quantization for Generative Pre-trained Transformers](https://mlsanity.com/paper/2210.17323/) (2022)
- [SparseGPT: Massive Language Models Can Be Accurately Pruned in One-Shot](https://mlsanity.com/paper/2301.00774/) (2023)
- [Optimal Brain Compression: A Framework for Accurate Post-Training Quantization and Pruning](https://mlsanity.com/paper/2208.11580/) (2022)
- [The Optimal BERT Surgeon: Scalable and Accurate Second-Order Pruning for Large Language Models](https://mlsanity.com/paper/2203.07259/) (2022)
- [Compressing LLMs: The Truth is Rarely Pure and Never Simple](https://mlsanity.com/paper/2310.01382/) (2023)
- [How Well Do Sparse Imagenet Models Transfer?](https://mlsanity.com/paper/2111.13445/) (2021)
- [ZipLM: Inference-Aware Structured Pruning of Language Models](https://mlsanity.com/paper/2302.04089/) (2023)
- [Scaling Laws for Sparsely-Connected Foundation Models](https://mlsanity.com/paper/2309.08520/) (2023)
- [The Emergence of Essential Sparsity in Large Pre-trained Models: The Weights that Matter](https://mlsanity.com/paper/2306.03805/) (2023)
- [Fast as CHITA: Neural Network Pruning with Combinatorial Optimization](https://mlsanity.com/paper/2302.14623/) (2023)
- [SPDY: Accurate Pruning with Speedup Guarantees](https://mlsanity.com/paper/2201.13096/) (2022)
- [GuidedQuant: Large Language Model Quantization via Exploiting End Loss Guidance](https://mlsanity.com/paper/2505.07004/) (2025)
- [Sparsity May Cry: Let Us Fail (Current) Sparse Neural Networks Together!](https://mlsanity.com/paper/2303.02141/) (2023)
- [On Efficient Training of Large-Scale Deep Learning Models: A Literature Review](https://mlsanity.com/paper/2304.03589/) (2023)
- [Visual Prompting Upgrades Neural Network Sparsification: A Data-Model Perspective](https://mlsanity.com/paper/2312.01397/) (2023)
- [CAP: Correlation-Aware Pruning for Highly-Accurate Sparse Vision Models](https://mlsanity.com/paper/2210.09223/) (2022)
- [Pruning Foundation Models for High Accuracy without Retraining](https://mlsanity.com/paper/2410.15567/) (2024)
- [MicroAdam: Accurate Adaptive Optimization with Low Space Overhead and Provable Convergence](https://mlsanity.com/paper/2405.15593/) (2024)
- [4-bit Shampoo for Memory-Efficient Network Training](https://mlsanity.com/paper/2405.18144/) (2024)
- [Towards Faster Training of Diffusion Models: An Inspiration of A Consistency Phenomenon](https://mlsanity.com/paper/2404.07946/) (2024)
- [Is Complexity Required for Neural Network Pruning? A Case Study on Global Magnitude Pruning](https://mlsanity.com/paper/2209.14624/) (2022)
- [VENOM: A Vectorized N:M Format for Unleashing the Power of Sparse Tensor Cores](https://mlsanity.com/paper/2310.02065/) (2023)
- [Junk DNA Hypothesis: Pruning Small Pre-Trained Weights Irreversibly and Monotonically Impairs "Difficult" Downstream Tasks in LLMs](https://mlsanity.com/paper/2310.02277/) (2023)
- [Self-calibration for Language Model Quantization and Pruning](https://mlsanity.com/paper/2410.17170/) (2024)
- [Bias in Pruned Vision Models: In-Depth Analysis and Countermeasures](https://mlsanity.com/paper/2304.12622/) (2023)
- [Preserving Deep Representations In One-Shot Pruning: A Hessian-Free Second-Order Optimization Framework](https://mlsanity.com/paper/2411.18376/) (2024)
- [Accurate Neural Network Pruning Requires Rethinking Sparse Optimization](https://mlsanity.com/paper/2308.02060/) (2023)
- [Position: Curvature Matrices Should Be Democratized via Linear Operators](https://mlsanity.com/paper/2501.19183/) (2025)
- [Nystrom Method for Accurate and Scalable Implicit Differentiation](https://mlsanity.com/paper/2302.09726/) (2023)
- [The Cost of Down-Scaling Language Models: Fact Recall Deteriorates before In-Context Learning](https://mlsanity.com/paper/2310.04680/) (2023)

## Abstract (arXiv)

Efficiently approximating local curvature information of the loss function is a key tool for optimization and compression of deep neural networks. Yet, most existing methods to approximate second-order information have high computational or storage costs, which can limit their practicality. In this work, we investigate matrix-free, linear-time 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. We propose two new algorithms as part of a framework called M-FAC: the first algorithm is tailored towards network compression and can compute the IHVP for dimension d, if the Hessian is given as a sum of m rank-one matrices, using O(dm2) precomputation, O(dm) cost for computing the IHVP, and query cost O(m) for any single element of the inverse Hessian. 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, as required for preconditioned SGD. We give an algorithm with cost O(dm + m2) for computing the IHVP and O(dm + m3) for adding or removing any gradient from the sliding window. These two algorithms yield state-of-the-art results for network pruning and optimization with lower computational overhead relative to existing second-order methods. Implementations are available at [9] and [17].