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

By Elias Frantar, Eldar Kurtic, Dan Alistarh. 2021

66 citations recorded by the source corpus.

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(dm^2)$ 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 + m^2)$ for computing the IHVP and $O(dm + m^3)$ 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].

Subfields: Artificial Intelligence, Computational Mathematics, Computational Mechanics, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mathematics

In Computational Mechanics

In Optimization & Training

Citations in the corpus

GPTQ: Accurate Post-Training Quantization for Generative Pre-trained Transformers (2022, background): “Finally, Optimal Brain Quantization (OBQ) (Frantar et al., 2022) generalizes the classic Optimal Brain Surgeon (OBS) second-order weight pruning framework (Hassibi et al., 1993; Singh & Alistarh, 2020; Frantar et al., 2021) to apply to quantization.”
SparseGPT: Massive Language Models Can Be Accurately Pruned in One-Shot (2023, methodology): “To motivate our algorithm, we first have to look at the row-wise weight reconstruction from a different iterative perspective, using the classic OBS update [19, 43, 10].”
How Well Do Sparse ImageNet Models Transfer? (2021, methodology): “Second-order pruning methods, e.g. [16, 24, 42, 63, 65] augment this basic metric with second-order information, which can lead to higher accuracy of the resulting pruned models, relative to GMP. Regularization Methods are usually applied during model training, via sparsity-promoting mechanisms.”
Optimal Brain Compression: A Framework for Accurate Post-Training Quantization and Pruning (2022, unknown): “Thus, the matrix of the A i blocks must be the inverse of the B i block matrix, which is exactly what we wanted to calculate.”