M-FAC: Efficient Matrix-Free Approximations of Second-Order Information
Authors: Elias Frantar
Eldar Kurtic
Dan Alistarh
Venue: NeurIPS 2021 Poster (2021)
Keywords: second-order methods
Fisher information matrix
efficient numerical methods
sparsity
optimization
pruning
matrix-free algorithms

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. 


M-FAC: Efficient Matrix-Free Approximations of Second-Order Information
Elias Frantar
Eldar Kurtic
Dan Alistarh IST Austria & Neural Magic dan www.aaathhiisstt.mmm ac.ar
IST Austria
IST Austria
elias. www.fffratrriss.aa
eldar, kwrkiciist.ac..a.
Abstract
Efficiently approximating local curvature information of the loss function is 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 limits their practicality. In this work, we investigate matrix-free, linear-time approaches for estimating Inverse-Hessian Hessian Vector Products (IHVPs) for the case when the Hessian can be approximated as sum of rank-one matrices, as in the classic approximation of the Hessian by the empirical Fisher matrix. We propose two new algorithms: the first is tailored towards network compression and can compute the IHVP dimension d, if the Hessian is given sum of m rank-one matrices, using (ddm²) precomputation, (dd)) cost for computing the IHVP, and query cost ((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, required for preconditioned SGD. We give an algorithm with cost (ddm + m²) ) for computing the IHVP and ((dm + m²) for adding removing any gradient from the sliding window. These two algorithms yield state-of-the-an results for network pruning and optimization with lower computational overhead relative to existing second-order methods.
Implementations are available at 9 and
Introduction
Given the recent success and increasing impact of deep learning, there has been significant work improving the fundamental technical tools underpinning its progress. One such tool is the ability to estimate the local geometry of the loss function for deep models, which often comes in the form of estimates for second-order (Hessian) information. Such information is critical in several settings, such neural network optimization and pruning.
Directly using Hessian information in the context of deep learning is infeasible: for example, just storing the Hessian matrix for the standard ResNet50 model [1] would occupy 2.5 Petabytes. These constraints have inspired significant work on efficient numerical approximations of the Hessian for deep neural networks, such as the line of work on the K-FAC approximation
49] or One of the classic approaches, which we focus in 13 approximation to the Hessian, written as:
[9
efficient block-wise approximations 47 37 this paper, the empiricul Fisher
N
VL, VLT 1=1
where is the number of samples, Vl, denotes the gradient w.r.t. the ith sample at the given point, and is the outer product of individual gradients, which we view column vectors.
The empirical Fisher approximation fairly standard, e.g. B useful in variety of practical settings where exact estimation of the Hessian of the true Fisher information matrix is not feasible. At the same time, there is still active research in the community
and has been recognized to be
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

on the conditions for its applicability 27 40). A useful property of this approximation is that it also allows estimate the inverse of the Hessian, which essential in many applications.
Specifically, the fact that the empirical Fisher can be written as sum of rank-one matrices allows the use of the Woodbury-Sherman Miterman-Moorioon inversion formula [46] to exactly compute its inverse, by recursively integrating terms corresponding to each gradient into the inverse. (Please see Equation 2 for an exact derivation.) This approach was independently proposed by [13 31. for pruning and optimization, respectively, where it was validated small networks, with hundreds of weights.
The idea was adapted to deep neural networks (DNNs) by [77, through approximation of the inverse in small diagonal blocks. The authors show improved approximation quality for the Hessian inverse relative to a simple diagonal approximation, and that this leads to state-of-the-arr pruning results in terms of accuracy. Yet, this approach is limited by the block-wise approximation: for block size B and dimension d, it requires (Bdm) time to recursively build the block-wise Fisher approximation using m gradients, and (Bd) time and memory for computing the Heeerss-eesii--VVe Dressian-Vector Vector-Produee (IHVPs) necessary for estimating pruning statistics. Clearly, the ideal B = d case is still intractable still unknown whether efficient algorithms are possible for computing
at scale, and generally IHVPs in this context.
Contribution. We address this question by introducing two efficient algorithms for computing IHVPss under the empirical Fisher approximation, with computational and storage costs that are linear in the dimension of the model, without the need for block-wise approximations, assuming that the number of samples yn in the approximation is constant. Concretely, we provide exact matrix-free algorithms to compute products of the form F-lv, where F-1 is the inverse empirical Fisher, and is an arbitrary vector. We show that these algorithms can be implemented efficiently, and that they can match or improve the state-of-the-art results for both neural network pruning and optimization.
The Static Algorithm. Our first algorithm assumes a static scenario, which is standard in neural network pruning: we are given a fully-trained model 0*, for which we wish to estimate IHVPs and diagonal elements of the inverse Hessian, in order to determine the "optimal" pruning update using e.g. the Optimal Brain Surgeon (OBS) framework (24 13). For this, we first compute m gradients at 0", which we will use to estimate IHVPs via the empirical Fisher and compute pruning statistics.
The main idea is that, since we only wish to compute products between the inverse and an arbitrary vector (IHVPs), we can rewrite the Woodbury recursion such that we work exclusively with individual vectors and scalars, and never with full d x d or d x B matrices. Given model dimension and m gradients, each defining a rank-one component of the empirical Fisher, the algorithm uses Odmm²) creeommputaioon time, and will have (dm) cost for exactly computing the IHVP. Further, we can specialize the algorithm to directly query elements of the Hessian inverse, at cost of ((m) time per element. This provides efficient, linear-in-t implementations for all operations required by the OBS pruning framework. Finally, we note that the static algorithm manner without any change in the total compute and memory costs.
also be applied in bisck-wise
The Dynamic Algorithm. Our main contribution is in extending this idea to preconditioned SGD) optimization, i.c. to precondition stochastic gradients by our estimate of the inverse Hessian. We start from the classic idea of bootstrapping the approximation by leveraging previous gradients: the preconditioner at time è is built from gradients obtained during a "sliding window" over the last 21 1 optimization steps. This requires a dynamic representation, allowing addition and removal of gradients without full recomputation of second-order statistics.
We show that this can be achieved, with approximately (dm) time and space complex- ity. The key idea is that, for any ordered set (VG)) of gradients, and any vector v, it is possible to represent the corresponding IHVP estimate F.rly as a linear combination of terms corresponding to individual gradients Ve, and v, of the form F-lv vv --1v 5 where À > 0 is a dampening constant.
Crucially, we ensure that the coefficients cj"l can be computed just via dot products V Vly, where i J in the ordering, and V..Tv v. Then, to replace a given gradient Vl, from this representation. we just have to compute m scalar products with the new gradient vector (as well as update some intermediate information). Hence, the entire update operation has computational cost O(dm + m²) for replacing any gradient in the sliding window, and O(dm + m²) for computing the IHVP.
Implementation and Experiments. We provide efficient vectorized implementations for the above algorithms, called M-FAC, for Matrix-Free Approximate Curvature. Specifically, M-FAC consists of

---

For pruning, our implementation provides order-of-magnitude improvements over the wise approximation of [37] for classic benchmarks such as pruning ResNer50 and MobileNet on the ImageNet dataset. This allows us to obtain more accurate sparse models by exploring higher parameter settings and increasing the total number of pruning steps. while remaining practical in terms of memory and compute even for larger models. What is more, our preconditioned SGD (even without momentum) can be competitive in terms of validation accuracy with state- of-the-rrt optimizers on models of moderate size, including compact vision architectures and Transformer relative to vanilla SGD on Pytorch [34] implementations of pruning and optimization library. Our implementation introduces several additional optimizations, in particular GPU acceleration via custom CUDA kernels, and minimizes the cost of memory transfer between the GPU and main memory via memory paging.
language models [42]. Its computational overheads are of standard CNN architectures.
2 Preliminaries and Related Work
General Definitions. We now briefly introduce the setting and notation; we refer the reader to standard texts 29 27 for complete introduction. We start from the standard setting in which we are given a dataset D = yx), and wish to identify d-dimensional model 6 E R to minimize empirical loss L Rd IR defined L(0) twice-differentiable loss L, the Hessian is the matrix of second-order derivatives of L. w.r.t. 6, i.e. H = L.L In the probabilistic view, each input example x has some probability of being assigned a given label y. Given input examples x drawn from a distribution Qx and corresponding outputs drawn from a conditional distribution Qy x- the goal is minimize the distance between the target joint distribution Qx.y Qx Qylx. and Iearned joint distribution Px,y (0), where 0 is the model.
N Σ (yy,, (x,; 0)). For
The Fisher Matrix. Assuming the probabilistic view, it can be shown that the Fisher information matrix F of the model's joint distribution satisfies F = Ep,,, x. [ log px.y where Px.y (0) is the density function. If the model's output conditional distribution matches the conditional distribution of the data, then the Fisher and Hessian matrices are fact equivalent if the model has high accuracy, we can approximate the Hessian of L at I with the Fisher matrix.
(27). Roughly. this means that,
sometimes useful to consider an approximation to the Fisher, where the distribution Px, is replaced with the empirical training distribution Qx.y, leading to the empirical Fisher matrix:
F- -EE. E
[
[1
1 N
Ve (y f (x;; 0) Vely.. (x;0))
VE,
The Sowabury-Sherman--Moe matrices has the benefit that it allows efficient exact computation of the Fisher inverse. Specifically, one can apply the classic Sawtur--Shermaa--ie
Trick. The fact that this approximation is a sum of rank-one
formula to compute the inverse recursively as Pxi, ( f-1 -ー=-ー--- P-1 N-1 N V F VeN F-1-
where the recursion is over samples, and the base step is F >- with À being small positive constant. This approach was independently introduced by Hassibi and Stork [13] for pruning, and Amari (3] for natural gradient. Singh and Alistarh (37 showed that it can be scaled to DNNs by block- wise approximation. and that it provides better approximations of the loss than K-FAC-based [44). or diagonal (39] approximations [7], leading to more accurate pruning. The main shortcoming of directly applying (2) is the prohibitive computational cost of ((dm)) even when reduced to MdBB)) by B-block-wir -iie approximation. Our method proposes matrix-free approach for exactly calculating IHVPs and querying individual elements of the inverse Hessian, of cost (dm) after O(d?²) precomputation. Our method is numerically equivalent to the direct computation above.
common approximation, both for optimization, e.g. 20 18 but also for pruning (39), is to assume that the Fisher matrix is diagonal. In our notation, this method has setup cost (dm), and diagonal query cost (d). However, as evident from the experimental results of [37] this provides lower approximation quality relative to both block- wise methods or K-FAC (4).
Diagonal Approximations.
K-FAC Approximations. This approach observes that the entries of the true Fisher corresponding to blocks "between" two layers, which can be written as the expectation of a Kronecker product
3

---

between two matrices, can be upproximated as the Kronecker product of the expectations of those two matrices (reversing the order between the product and the expectation). This approximation has been leveraged for both pruning and for optimization, and it allows efficient computation of the inverse [5] 33
23]; however, is known to not always hold [3I]. Another relative drawback is that the Kronecker factorization only occurs naturally for funny-connected layers; but there is work on extensions to other layer types [I] 30), via additional approximations. We compare against K-FAC-based optimizers and pruners, and find that our method yields better results.
Additional Approaches. Our approach is similar in spirit to matrix- free methods [32 25| 28],
but the algorithms we present new. Hessian-free optimization (28] also forgoes the explicit computation of Hessians in favor of computing an IHVP with a vector V. However, this estimation is for some given
performed by iteratively approximating the solution to the linear system Hx without ever explicitly forming H. One disadvantage of this method in practice is that it requires tuning and several very costly iterations converge (for a single v), as the underlying Hessian can be ill-conditioned. The L-OBS pruning method 77 approximates second-order information by defining independent layer-wise objectives, which allows the direct approximation of the layer-wise Hessians via a carefully- cercuffllfffeedd block structure. In contrast, our approach allows for fully-global Hessian estimation and it also yields better pruning results scale.
Full-matrix adaptive regularization has similar goals, but in the context of adaptive optimizers g Agarwal et al. [2] proposed GGT, which allows the efficient computation of the inverse square root of the low-rank matrix resulting from the sum of gradient outer products over a sliding window. At its core, this procedure requires an digen-decomposition (implemented via SVD) of an m X m matrix at every time step, which is reasonably efficient for small values of m.
Our dynamic algorithm solves a similar, but slightly simpler problem, as we only want to invert the matrix, without computing its square root. We do not perform any eigen-decompositinn:: instead, we carefully maintain intermediate information that allows an efficient explicit computation of the scalar coefficients in Equation [ At the end of Section 3.22 we discuss how this approach is more efficient in practice and allows executing at larger window sizes (with small overhead), which leads to improved model accuracy as we show in our experiments. Additionally, our dynamic algorithm S
has per-step cost O + m,²), relative to (dm + m²) reported by GGT (2: this can result in lower overhead versus GGT, even when the SVD cost is negligible (e.g. if m is small).
Yao et al. [47 recently provided an alternative method for approximating the diagonal of the inverse Hessian, using Hutchinson's 's randomized algorithm for estimating the diagonal. To mitigate the variance, the authors introduce non- coniiaiiial smoothing heuristics. Their approach has theoretical per-iteration cost of least 2x versus SGD, as it requires a second backward pass over the network; and this cost is usually higher in practice. Experimentally, our algorithm often matches their accuracy, and, unlike AdaHessian, its cost depends exclusively on the model size, irrespective of the underlying structure. Thus, as we show in the experimental section, our average practical overhead is less than 50% for dense models, and less than 10% for sparse ones.
Approximation Quality. Künstner et al. 21 performed in-depth analysis of the empirical Fisher, making the point that, in theory, the approximation could become meaningless all sample gradients zero. Similarly to (37, we did not find that this occurs in practice for deep neural networks, as sample gradients are never zero The latter reference provides detailed comparisons of diagonal, K-FAC, and other approximations, and finds that the empirical Fisher can provide competitive approximation quality for DNNs. Further, they demonstrate that better loss approximation implies better accuracy for neural network pruning. We therefore do not repeat their loss analysis, and mainly compare methods in terms of application performance.
3
Algorithm Descriptions
3.1 The Static Algorithm
As a warm-up, we first describe the IHVP algorithm given a static set of gradients. While our notation is customized for the empirical Fisher, all our techniques are applicable to any matrix that can be written as the sum of m rank-one components. Specifically, we are given m vectors, which we assume to be the gradient vectors (VL) and must compute quantities related to the inverse of the matrix resulting from the sum (more precisely, the average) of their outer products, which we denote by F..1. The main idea is to rewrite the recursive description of F-11 such that, after some precomputation, the matrix nnttix-vector-peee proctutt-rruuttttc 1 x can be computed efficiently for any vector Using

---

the Sherman- Morrison formula applied to the partial empirical Fisher matrix F. corresponding to the first gradients (and scaled by 1/m), we obtain the following recursion:
- ( ( x-
x, with Fy x= - and À > 0. (3)
m + Ve. ve:
For simplicity, let us set Vi = - V4 and unroll the Sherman-Morriso recursion, which gives:
-- -
x = -
Vj x m V
m + Ve.vi
IHVP Computation. Assuming that we have already computed all the vectors Vj. the above expression can be calculated in (ddm) time without any intermediate d x d matrices: first compute the scalar fractions in 44), and then evaluate the resulting linear combination of x and Vj. Since
v; = | Vl,, can be computed in exactly the same way given all Vj for j < i. Thus, all m vectors vi of dimension d can be precomputed in increasing order of i using (dd²² total time. As an additional optimization (to cut the required memory in half), we also precompute all qj = m+ VV Vj-
Querying the Inverse. To extract individual elements [F.m. 'le of the inverse Hessian approximation, we can write ei Fmmle ej in the form of (4) where e, and ej are indicator vectors
e TF ej = T ee E
m
C
V
Vk ej
(5)
qk
As e; T Vic and Vk Tej can both be realized as constant time indexing operations, the above turns into sum scalars. Hence, method admits (m) access any element of Fi using the same precomputed Vk and qk as for the efficient calculation of F, Additional Optimizations. The algorithm admits fast vectorized implementation, and several optimizations, which we describe in the Appendix. For example, we perform several memory-saving optimizations, well as explicit page swapping between CPU and GPU memory to mitigate the gradient transfer costs. Furthermore, the static algorithm can be applied independently to each block of block-wiss approximation: for block size B, the computation and memory costs per block are reduced by B/ d. but since there are now d/ B blocks, the overall costs will stay the same irrespective of B. Thus, as long < B, our method is B/ B/m times faster (and less memory intense) than the direct implementation of the Woodbury inverse.
3.2 The Dynamic Algorithm
We now describe the dynamic algorithm, which assumes that gradients arrive in an online fashion and must be integrated into the Fisher estimate. We first present the algorithm itself, i.e. the setup update/ / IHVP computations, and perform a complexity analysis. Next, we show how the algorithm can be derived and finally we conclude with notes on an efficient practical implementation.
High-Level View. The main idea of the dynamic algorithm is to write the IHVP
172
m x
Vly
(6)
1=1
where the scalar coefficients C. can be computed efficiently from just the scalar products Ve, Vl, and VeT x. Then, any gradient V&, can replaced by updating just ((m) of the stored scalar product values. In the following, we use G = [VeT; ; Vem] to denote the row-wise m x d matrix of the m gradients for which we wish to compute the inverse empirical Fisher. Further, for each from I to m, let b' be a vector with m components (bj, bs...., ),,), such that
m
F-1v4 = X 'v
VC,
VL,
1=1
ie. containing the scalar coefficients of P- Vl,. This means that bj = af when j < i, by = -
and by O otherwise.
Initial Precomputation Update. The dynamic algorithm maintains three m x m matrices:
GG D and B. The first is the symmetrie gradient scalar product matrix [GG ly Vl, Vlz.
5

---

The second is an upper triangular matrix and stores the precomputed values [D]; = V4
for i S j. The third is the row-wise matrix of the coefficient vectors BBa bj. which makes it lower triangular with a diagonal of X- We now discuss how to compute those matrices.
The initial setup of the dynamic algorithm begins by evaluating GG in a straightforward fashion. Next, D can be computed for S j according the following recursion:
Diy = (V F Vey) and (Ve] Fo V(x) = A [G 1/A
(8)
(ve = (V - V
P P
(9)
++ (VL. P. VG)
Given D, we can then conclude the precomputation by calculating B for i 2 j recursively as:
D
B si
X and B = Σ
B kj-
(10)
DDAK
After the initial setup, gradient V4a can be replaced with gradient V by first updating row k of G and then replacing row and column l in GGT with GV Afterwards, the recomputation of columns j 2 k of D and rows i 2 & of B completes the update.
Multiplication. Once GG D and B have been precomputed, one can perform efficient IHVPs of the form F x with arbitrary vectors x. This is done by first evaluating Gx and then computing all m values qi by the following recursion:
(Ve,
9:
[Di and (VE) Rx*x) x) -
(11)
m
D
(V (Ve x
(Ve F
(12)
m. [
Eventually, the final result of the IHVP is obtained by:
372
m
Po x
2 BBa))
(13)
Complexity Analysis. The dynamic algorithm stores gradients of dimension d as well as three m x m matrices, and thus has an overall memory complexity of Odm + m²).
Next, we analyze the time complexity of all important operations. Initially, GGT must computed once, which takes Odm?²) time. Then, the recursion of D has three indices with 1 S Ki,j, k < m and each step takes constant time. Thus, can be computed in O(m)) time with dynamic programming. Further, since values for index depend only values for index i 1, the dynamic programming can be implemented in O(m²) space. B has two indices 1 < i.j I m and every recursion takes Om) time, meaning that it can also be fully computed in O(m²) through dynamic programming. Hence, the overall initial setup cost is Odm2² + m²).
To replace one gradient with V we have compute GVE as well as (partially) recalculate D and B, which takes at worst Odm + m²) time. An IHVP requires two matrix-vector products involving G and recursion with two indices and therefore has complexity of O(dm + m²)
Algorithmic Derivation. The dynamic algorithm can be derived directly from Theorem I which we state here in a simplified form (using the definitions of B and D). and prove in the Appendix.
Theorem 1. Let F. Al 1/m Σj= Vh, VC]. then F:-1 'x can be calculated as:
(VL 1
x x
Vi and of -
B kjj.
(14)
D
Equation (4) with m is exactly equal to the IHVP computation (3) as the fraction in the innermost sum corresponds to 9k- Similarly, index shifting = i and setting x Vl, thus turning dj into - BBi as well as the fraction's numerator to [D]r.. recovers the precomputation formula of B given by 110 for j. The formulas for D and y follow directly from an expansion of the Woodbury formula followed by an appropriate recursive evaluation that avoids any matrix / vector operations except in the base case (we indicate the corresponding recursive calls by brackets).

---

Efficient Implementation. Directly implementing the discussed recursive formulas in a modern machine learning framework would result in very slow code. Fortunately, it is possible to implement all computations required for the dynamic algorithm very efficiently on GPU. We describe how to do this in the Supplementary Material and provide a full implementation [9. Specifically, we provide complete sample code that is able to perform the calculation of D and B, i.e. the ((m²) component of the overall update cost, in < 10 milliseconds (on an NVIDIA RTX 2080 Ti) for values of m as high as 1024 (and the code can still be further optimized). For reference, this is > 10x faster than the highly-optimized m X m SVD computation done at every step by GGT (2). We emphasize that this O(m)) computation being very fast in practice is crucial to reach low overheads, especially when dealing with a models where the (dm) matrix-vector products are not the bottleneck.
4 Experimental Validation
4.1 Application 1: Pruning DNNs using the Static Algorithm
Background. Given trained model 0*, the goal of pruning is to find the weight 0g, or the set of weights, whose setting to 0 would lead to a minimal increase in the training loss. Under a local quadratic approximation of the loss functionn the OBD framework (24) shows that the "optimal"
weight to be removed is the one with the lowest value of the saliency metric p(0.)
2 and
of
proposed to estimate [ks by diagonal approximation. The OBS framework [3] observed that the remaining weights 0 should also be updated via the optimal perturbation 50 = --eF-eee// [//["'/a. where e, is the ith basis vector. Our algorithm efficiently supports both these operations.
Wang et al. [4 raised the valid point that applying the OBS update above to multiple weights being removed at once may be incorrect, since it ignores possible correlations between those weights. We considered this point in detail, comparing results between OBD pruning (24) the OBS update [3]. and an augmented version of OBS which disentangles the correlations by solving a corresponding linear system (37]. The results, presented in the Appendix, suggest that the OBS update is quite beneficial even in its approximate form, and that the effect of correlation is small for unstructured find that the OBS pruning mask in each step is usually very similar to the one
pruning. In fact, obtained by simple magnitude pruning, suggesting that the final accuracy improvements are primarily due to the updates of the remaining weights, facilitating better recovery.
Experimental Setup. We prune CNNs (ResNet-50 [5) and MobileNet-VI (16) on the ImageNet dataset (36). These models are standard in the pruning literature [IO], and therefore several strong baselines exist. Timing experiments are run on a machine with NVIDIA RTX 2080 Ti GPUs, a 48-core Intel CPU, and 512 GB of RAM. Following [37], we used batched gradients (of size 16) as single samples inside the Fisher approximation. This does not alter results, but reduces variance.
We compare against Global Magnitude Pruning (GMP) [12), Layer-wise Optimal Brain Surgeon (L-OBS) [7]. Soft Threshold Reparametrization (STR) 222, and WoodFisher (WF) [37] The latter two methods are state-of-the-ard for gradual pruning. WF numerically equivalent to our method at the same parameter settings, but has significantly higher computational and storage cost. Relative to it, we therefore focus on executing at higher parameter values. We compare against their public implementation. The Appendix contains full hyper- pareenetraeeerss ablations with respect to block size and number of gradients, and a comparison with K-FAC pruning in a simpler setting [49].
We first perform one-shot comparison to evaluate the "raw" per step pruning performance of M-FAC relative to other methods. Next, we evaluate how simply increasing M-FAC parameter values (but keeping everything else exactly the same in WF's experiments (37 which follow (50) improves over state-of-the-ar gradual pruning results by WF, GMP and STR. Finally, we demonstrate how M-FAC's high per-step efficiency can be utilized craft practical pruning schedules with little computational overhead relative to GMP and only moderate extra memory consumption, which at the same time yield significantly better results than WF's state-of-the-art numbers.
Oneshot Pruning. Figure Ia shows the Top-5 accuracy of one-shot ResNet50 pruned models for L-OBS, GMP, WoodFisher, and M- M-FAC, where our method is executed with a parameter setting that is infeasible for WoodFisher due to the required computational and storage costs. (We use Top-5 accuracy to compare with 77.) We note the improved aceuracy of global methods relative to layer-wise, and that the Fisher approximation yields consistently better results relative to global magnitude. This suggests that a better approximation of the Fisher inverse also yields better pruning results, and is in line with the loss approximation study of [37].
7

---

90
Test accuracy (Top-5
Test accuracy (Top-)
60
35%
80
-50
70
Layawwise Magnitude
Layawise Optimal Brain Surgeon
60
Global Magnitude
30
WoodFisher
20
Global Magninade
50
M-FAC (10K,
WoodFisher (10K, 400)
M-FAC (128 64)
M-FAC (10X. 4K)
0.0
0.1
0.2
0.3
0.4
0.7
60
100
Sparsity
Epoch
prining ResNe150.
(b) Gradual pruning MrhhleNeeVI1.
Adam
Training loss
without
Test accuracy
M. FAC
50
30
Adamm
SGD
SGD without momentum
M-FAC
0
10
20
50
10
30
40
Epoch
Epoch
(c) Training loss for WRN 40-2/ CIFAR-IOO 100.
(d) Text accuracy for WRN 2/
Figure I: (a) Accuracy vs. sparsity for one-shot pruning on ResNet50 / ImageNet. (b) Accuracy during gradual pruning for the MobileNetVI-STR, ImageNet experiment. (c) and (d) Comparison of different optimizers on short WRN-40-2 CIFAR-IO0 100 schedule.
Generally, we found that estimation using more gradients always improves results, until saturation. Interestingly, increasing the block size does not necessarily improve results, for some models, smaller block sizes sometimes yield better results for a fixed number of gradients.
Figure Tb examines the effect of the improvement in one-shot pruning accuracy at each step of pruning, on the final result, when pruning MobileNetV] --STR gradually to 89% sparsity. WoodFisher uses block size 10K, and m 400 gradients, while M-FAC uses the same block size but m = 4000 gradients. Executing WoodFisher with the same parameters would be extremely slow. Note the gap in one-shot accuracy following each pruning step: this translates the final accuracy gap more than 1% even after the extensive fine-tuning phase.
Gradual Pruning Comparisons. Table I presents gradual pruning results for MobileNetV1- STR/ImageNet 89% sparsity and ResNet50/lmageNe art methods. M-FAC outperforms previous methods in the case of MobileNetV 1-STR by more than 1.5% T accuracy. Further, despite using 10x more gradients estimate the empirical Fisher, the per-step pruning cost of M-FAC is > 6x lower than WoodFisher's as can be seen in Table 2 (for the same parameters settings M-FAC is > 100x faster). The ResNet50 results show smaller gains.
95% sparsity, relative other state-of-the-
Table 1: Gradual pruning results (top-1 accuracy) for Table Minutes per pruning step compared
NobileNetVI-STR ImageNet 89% sparsity and with WoodFisher (WF), OOM denotes out of memory system with 512GB RAM.
ResNet50/ ImageNet at 95% sparsity.
Method
MBvl Top-1 (%)
RN50 Top- (%)
Model
B
WF
M-FAC
Dense haseline
72.00
77.01
MBv1-STR
10k
400
60m
0.5m
MBv1-STR
10k
4k
0OM
8.7m
STR 22
62.10
70.40
MBv1-STR
all
1k
0OM
1.2m
Global Magnitude
62.94
71.72
ResNet50
2k
400
35m
2.5m
WoodFisher 37
63.87
72.12
ResNet50
10k
1k
0OM
14.0m
M-FAC
65.01
72.32
ResNet50
all
512
00M
4.7m
Practical Pruning. Due to the computational cost of a WF step, the previous schedules used only small number of pruning steps. However, M-FAC makes it possible to prune much more frequently. In this case, the cost of extracting and storing several thousand gradients may still be bottleneck.

---

We find that M-FAC already performs well with low parameter settings, especially when coupled with recomputations (i.e resampling gradients and rebuilding the M-FAC approximation after partial pruning steps). We now perform MobileNet and ResNet50 gradual pruning runs using M-FAC with block size B = 128, 64 gradients and 16 recomputations per step. A single M-FAC pass takes less than few seconds at these settings. Details about the pruning schedule can be found in the Appendix. This is a practical setup, which can scale to larger models. At the same time, Table 3 shows that leads to significantly improved pruning results, sometimes even by several percent accuracy, compared to WF and the M-FAC results in Table
MBv1-0%
MBv1-75%
MBv1-899
RN50-0%
RN50-95%
RN50-98%
WoodFisher
72.0
70.1
63.9
77.0
72.1
65.6
M-FAC
72.0
71.0
67.3
77.0
72.6
67.5
Table 3: M-FAC performance with optimized practical scttings.
4.2 Application 2: Optimization using the Dynamic Algorithm
Matrix-Free Preconditioned SGD. The dynamic algorithm can provide an efficient implementation for the following variant of SGD. Let be the current iteration index, and A t be the length of the sliding window during which the estimation of the inverse Hessian is performed. Consider the iteration 0.+1- 0.- T) Pr A.- Vl,, where T)t is the learning rate. Let Vl Vl, be the gradients obtained at steps (1 (1-++1), +1), ..... I, respectively. Then, we define the preconditioning matrix as Fi-a.1 = > + 1/4 EA- ve_r- Ve, that is, an empirical Fisher matrix generated with respect the sliding window of A gradients. At each step, our dynamic algorithm replaces V4-A++ with Vl, in the inverse estimate, and then computes Pi--A. Vl,. This corresponds to full-matrix natural gradient SGD 3 under the extra assumption that gradients do not change too quickly during training. This assumption has been validated in the K-FAC literature [5] and we also provide additional experimental justification in the Appendix. Finally, to better study the effect of the preconditionier, we do not apply momentum to M-FAC in any of the experiments below.
Initial Test. We begin by verifying that the M-FAC optimizer actually behaves as one would expect from second-order method, i.e. learning faster than standard first-order techniques, especially in the early epochs. For that purpose, we run M-FAC, SGD with and without momentum and Adam on WideResNet 40-2/ / CIFARIO with a compressed 50 epoch schedule. The corresponding Figures and indeed showcase the expected behavior. Interestingly, they also show that SGD without momentum performs poorly in this setup, which further highlights the major impact of the M-FAC preconditioner, which seems to be able to make up for the lack of momentum.
Second Order Comparison. Next, we work with the common ResNet20 and ResNet32 mod- els 15 and compare against standard optimizers such as SGD with momentum, Adam [18 and Adam W [26). but also against approximate second-order methods such as K-FAC (30], GGT and AdaHessian [47] For the former two, use the implementations contributed to TensorFlow the authors, while for the latter we use the authors' Py Torch implementation. For fairness, we always follow the settings recommended by the authors, although this makes overheads harder to compare: we used specific learning rates, and grid-searched the weight-decay values for each method in turn.
by
Since implementations have slightly different framework requirements, is overhead over SGD, measured in each algorithm's 's environment, on an NVIDIA RTX 3090 GPU for PyTorch and Titan RTX for TensorFlow. For all second-order methods, we compute the preconditioner at each step-reducing the frequency reduces overheads proportionally for each method, but introduces additional papae-parameter and generally results in lower final accuracy. We provide additional information in the Supplementary.
main performance metric
Our first results are presented in Table 4 (left), where we examine the best Top-1 test accuracy obtained by each method, as well as its overhead relative to SGD. For K-FAC, the best accuracy is obtained with batch size 1000, while all other methods operate on batch size 128. Similarly, GGT's best results are achieved with window size
100, while for M-FAC larger window sizes improve results; we use m = 512. Due to these discrepancies, we measure overheads with the "best accuracy" setting for each method but also in the same setup as M-FAC; the latter is given in brackets.

---

ResNet20
RosNot32
Method
Acc.
Overhead
Acc.
Overhead"
Model
SGD
Adam
M-FAC (Overh.)
SGD
91.78
1.00x
92.80
1.00x
WRN 22-2
69.93
66.90
69.76 (1.40x)
Adam
89.67
x.05x
90.56
1.10x
WRN 40-2
71.75
70.14
72.42 (1.35x)
AdamW
91.78
1.03
92.58
1.10x
WRN 22-4
73.13
72.52
74,06 (1.43x)
MBvl Dense
68.06
67.92
68.96 (1.25x)
K-FAC
91.65
1.21 x (2.35x)
90.09
x.50x (3.05x)
GGT
88.38
1.05x (8.35%)
89.14
1.05x (8.88x)
MBv1 Sparse
64.11
64.78 (1.03x)
AdaHessian
92.17
x.50x
92.81
3.30x
RN50 Sparse
74.78
75.10 (1.05x)
M-FAC
92.34
1.55x
92.65
1.50x
Table 4: Left: Comparison of M-FAC against first- and second-order optimizers with individual tuning and weight decay. Right: Additional experiments with no tuning and weight decay. Sparse results are from finetuning after the last step of gradual pruning to z 90% sparsity. For K-FAC GGT we indicate in parentheses the overhead in comparable setting to M A-FAC with the same batchsize/ / the same number of gradients.
SQv2
SST-2
MRPC
STS-B
QQP
MNLI-m
MNLI-mm
QNLI
1.
Adam M-FAC
48.41
80.11
69.90
64.39
81.09
65.36
67.78
77.85
49.80
81.86
72.94
80.15
84.20
68.28
68.98
81.17
m Adam
54.80
85.46
76.57
82.09
86.45
73.30
74.85
83.85
m M-FAC 58.02
84.20
78.87
84.66
86.75
74.59
75.95
83.70
Table 5: Average of rums performance of Adam and M-FAC for tiny (t) and mini (m) BERT on SQuADv2 and GLUE benchmark tasks, Due to space, we only show accuracy for SQuADv2 QQP and the Pearson correlation for STS-B, see Appendix for full results. Models are hosted at httpp::/hugginggfce. CO/M-FAC
In terms of accuracy, M-FAC scores highest in the ResNer20 experiment, and comes third, to tuned SGD and AdaHessian (performing almost the same), on ResNet32. The overhead of M-FAC is around 50%, which is lower than AdaHessian, on par with K-FAC, but higher than GGT. However, comparable only when GGT uses 5x less gradients (surprisingly, larger window sizes yield worse results for GGT). On the same settings, M-FAC provides up to 5x lower overhead. This is due (a) better performance of our dynamic algorithm relative to SVD and (b) the (dm²² term in GGT, versus our (dm) term.
these overheads
Image Classification. Table (right) provides a scenario where we run SGD with momentum, Adam, and M-FAC without tuning or weight-decay on Wide Residual Networks (WRN) (48) for CIFAR-100, as well as on MobileNetV1/ ImageNet, and examine test accuracy. M-FAC achieves the highest accuracy on most runs, even on ImageNet. We emphasize that these results can probably be improved by parameter tuning. Another interesting application is fine-tuning sparse models. We fine-tune 90% sparse MobileNet / ResNet50 models for 30 epochs starting from the last gradual pruning step and find that M-FAC reaches higher final accuracy than SGD in both cases. At the same time, it is only negligibly slower (< 5% overhead) since algorithm's 's complexity (compute and memory) is linear in the model densiry. At last, we note that M-FAC achieving higher test accuracy is generally well correlated with lower final training loss.
Language Modelling using Transformers. Finally, we test the M-FAC optimizer for smaller Transformer models. We use the default values
1024 gradients (unless the dataset has less than this number of total samples), dampening À = 10-6 learning rate 10-4 and no weight decay. We then train BERT (6) tiny and mini models [4]] on SQuADv2 (35) and the GLUE benchmark suite 433. comparing against HuggingFace s (5) Adam baseline. For M-FAC, we use exactly the same training setup and only replace the optimizer. The results in [ that M-FAC performs better than the Adam baseline on almost all tasks, on several even by considerable margins. We provide more detailed results in the Appendix, including hyperparameters and a comparison with Adam W.
5 Discussion
We presented static and dynamic algorithms for computing IHVPs when the Hessian matrix can be approximated by sum of rank-1 matrices. We used the classic empirical Fisher approximation, but our results can apply more broadly. The main limitation the cost of storing m additional gradients. For the static algorithm, we can efficiently leverage system memory, as described in the Appendix. The dynamic algorithm could parallelize gradient storage, or perform gradient compression (38). We plan to investigate this in future work and perform larger-scale study of optimization performance.
10

---

Acknowledgements
We gratefully acknowledge funding the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No 805223 ScaleMI.), as well as computational support from Amazon Web Services (AWS) EC2.
References
[1] Martín Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthicu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, et al. Tensorflow: A system for large-scale machine learning. In 12th USENIX symposium on operating systems design and implementation (OSDI 16), pages
2016.
[2] Naman Agarwal, Brian Bullins, Xinyi Chen, Elad Hazan, Karan Singh, Cyril Zhang, and Yi Zhang. Efficient full-matrix adaptive regularization. In International Conference on Machine Learning, pages 102-110. PMLR, 2019.
[3] Shun-ichi Amari. Natural gradient works efficiently in learning. Neural Computation, 10(2):511
276, 1998.
[4] Shun-ichi Amari. Information geometry and its applications, volume 194. Springer, 2016.
[5] Jimmy Ba, Roger Grosse, and James Martens. Distributed second-order optimization using kronecker-factored approximations. 2016.
[6] Jacob Devlin, Ming-Was Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding, 2018.
[7] Xin Dong, Shangyu Chen, and Sinno Jialin Pan. Learning prune deep neural networks via layer-wise optimal brain surgeon, 2017.
[8] John C. Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. J. Mach. Learn. Res., 12:2121-2159 2010.
[9] Elias Frantar and Eldar Kurtic. M-FAC implementation: https://gi thub com/ IST IST-DASLab/M-FAC 2021.
[10] Trevor Gale, Erich Elsen, and Sara Hooker. The state of sparsity in deep neural networks, 2019.
[11] Roger Grosse and James Martens. A Kronecker-factored approximate fisher matrix for convolu- tion layers, 2016.
[12] Masafumi Hagiwara. A simple and effective method for removal of hidden units and weights. Neurocomputing, 6(2):207 218, I 1994. Backpropagation, Part IV.
[13] Babak Hassibi and David G. Stork. Second order derivatives for network pruning: Optimal brain surgeon. In Advances in Neural Information Processing Systems 5, INIPS Conference), page 164-171, San Francisco, CA, USA, 1992. Morgan Kaufmann Publishers Inc.
[14] K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 770-778, 2016.
[15] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. 2016 IEEE Conference Computer Vision and Pattern Recognition (CVPR), Jun 2016.
[16] Andrew G. Howard, Menglong Zhu, Bo Chen, Dmitry Kalenichenko, Weijun Wang, Tobias Weyand, Marco Andreetto, and Hartwig Adam. Mobilenets: Efficient convolutional neural networks for mobile vision applications, 2017.
[17] Neural Magic Inc. Sparseml framework: httpe:e//gthha..cccmm//mmmamggge 2021.
[18] Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization, 2014.

---

[19] Diederik P Kingma, Tim Salimans, and Max Welling. Variational dropout and the local reparameterization trick. In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 28, pages 2575-2583 Curran Associates, Inc., 2015.
[20] Shankar Krishnan, Ying Xiao, and Rif A Saurous. Neumann optimizer: A practical optimization algorithm for deep neural networks. arXiv preprini
2017.
[21] Frederik Kunstner, Philipp Hennig, and Lukas Balles. Limitations of the empirical fisher approximation for natural gradient descent. In Advances in Neural Information Processing Systems, pages 4156-4167, 2019.
[22] Aditya Kusupati, Vivek Ramanujan, Raghav Somani, Mitchell Wortsman, Prateek Jain, Sham Kakade, and Ali Farhadi. Soft threshold weight reparameterizatioo for learnable sparsity, 2020.
[23] César Laurent, Thomas George, Xavier Bouthillier, Nicolas Ballas, and Pascal Vincent. An evaluation of fisher approximations beyond kronecker factorization, 2018.
[24] Yann Le Cun, John S. Denker, and Sara A. Solla. Optimal Brain Damage, page 598 605. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1990.
[25] Dong C Liu and Jorge Nocedal. On the limited memory bfgs method for large scale optimization. Mathematical programming, 45(1):003-523 1989.
[26] Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. In Proceedings of the Seventh International Conference on Learning Representations, 2019.
[27] Alexander Ly, Maarten Marsman, Josine Verhagen, Raoul Grasman, and Eric-Jan Wagenmakers.
A tutorial on fisher information, 2017.
[28) James Martens. Deep learning via hessian-free optimization. In Proceedings of the 27th International Conference on International Conference on Machine Learning, ICML'10, page 735-742, Madison, WI, USA, 2010. Omnipress.
[29] James Martens. New insights and perspectives on the natural gradient method. arXiv preprint arXiv: 2014.
[30] James Martens, Jimmy Ba, and Matt Johnson. Kronecker-factored curvature approximations for recurrent neural networks. In International Conference on Learning Representations, 2018.
[31] James Martens and Roger Grosse. Optimizing neural networks with kronecker-factored approx- imate curvature, 2015.
[32] Jorge Nocedal and Stephen Wright. Numerical optimization. Springer Science Business Media, 2006.
[33] Kazuki Osawa, Yohei Tsuji, Yuichiro Ueno, Akira Naruse, Rio Yokota, and Satoshi Matsuoka. Large-scale distributed second-order optimization using conneckr--fcctoee approximate curva- ture for deep convolutional neural networks. 2019 IEFF/CVF Conference on Computer Vision and Pattern Recognition (CVPR), Jun 2019.
[34] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, perforpeformnnce deep learning library. arXiv preprint arXiv: 1et..01723. 2019.
[35] Pranav Rajpurkar, Robin Jia, and Percy Liang. Know what you don't know: Unanswerable ques- tions for squad. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), pages 784-789, 2018
[36] Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, et al. Imagenet large scale visual recognition challenge. International Journal of Computer Vision, 115(3):111-52,, 2015.
[37] Sidak Pal Singh and Dan Alistarh. Woodfisher: Efficient second-order approximation for neural network compression, 2020.
12

---

[38] Xu Sun, Xuancheng Ren, Shuming Ma, and Houfeng Wang. meProp: Sparsified back propaga- tion for accelerated deep learning with reduced overfitting, Proceedings of the Thirty-Fourty International Conference on Machine Learning. 2017.
[39] Lucas Theis, Iryna Korshunova, Alykhan Tejani, and Ferenc Huszár. Faster gaze prediction with dense networks and fisher pruning, 2018.
[40] Valentin Thomas, Fabian Pedregosa, Bart Merriënboer, Pierre-Antoine Manzagol, Yoshua Bengio, and Nicolas Le Roux. On the interplay between noise and curvature and its effect on optimization and generalization. In International Conference on Artificial Intelligence and Statistics, pages 3503-3513, PMLR, 2020.
[41] Iulia Turc, Ming-Wet Chang, Kenton Lee, and Kristina Toutanova. Well-read students learn better: On the importance of pre-training compact models. arXiv preprint arXiv:1908.08963 2019.
[42] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need, 2017.
[43] Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel R Bowman. Glue: A multi-task benchmark and analysis platform for natural language understanding. In International Conference Learning Representations, 2018.
[44] Chaoqi Wang, Roger Grosse, Sanja Fidler, and Guodong Zhang. Eigendamage: Structured pruning in the kronecker--actored eigenbasis, 2019.
[45] Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, Joe Davison, Sam Shleifer, Patrick von Platen, Clara Ma, Yacine Jernite, Julien Plu, Canwen Xu, Teven Le Scao, Sylvain Gugger, Mariama Drame, Quentin Lhoest, and Alexander M. Rush. Transformers: State-of-the- art natural language processing. In Proceedings of the 2020 Conference Empirical Methods Natural Language Processing: System Demonstrations, pages 38 45, Online, October 2020. Association for Computational Linguistics.
[46] Max A Woodbury. Inverting modified matrices. Statistical Research Group, 1950.
[47] Zhewei Yao, Amir Gholami, Sheng Shen, Kurt Keutzer, and Michael W Mahoney. Adahessian: An adaptive second order optimizer for machine learning. arXiv preprint arXiv:2006.00719, 2020.
[48] Sergey Zagoruyko and Nikos Komodakis. 1605.0060..7114 2016.
Wide residual networks.
arXiv preprint
[49] Wenyuan Zeng and Raquel Urtasun. MLPrune: Multi-layer pruning for automated neural network compression, 2019.
[50] Michael Zhu and Suyog Gupta. To prune, or not to prune: exploring the efficacy of pruning for model compression, 2017.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them?
[Yes]
2. If you including theoretical results...
(a) Did you state the full of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments...
Did you include the code, data, and instructions needed reproduce the main experimental results (either in the supplemental material or as a URLY? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running experiments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you using existing assets (c.g., code, data, models) curating/releasing assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [No] Assets are open-source with standard permissive licenses.
(c) Did you include any new assets either in the supplemental material or as a URL? [Yes]
(d) Did you discuss whether and how consent obtained from people whose data you'ne 're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsoureing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable?
[N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "xEnFgwayjRB", "reviewer": "Reviewer_zd2D", "summary": "This paper concentrates on the fast implementation of computing IHVPs (Inverse-Hessian Vector Products, and the expression here means \"Inverse-Empirical-Fisher Vector Products\") in training DNN, whose high time and memory costs remain a core problem. This paper is mainly based on the WoodFisher method. The WoodFisher uses the SMW (Sherman-Morrison-Woodbury) formula to compute the inverse of Fisher. This paper proposes a new algorithm (M-FAC) to accelerate this process. With two algorithms (static and dynamic, which correspond to gradients from single and multiple epochs), M-FAC can avoid matrices operations and decrease the time and storage costs, and the final time complexity is linear-in-dimension. In real practice, M-FAC outperforms K-FAC and has a similar performance with AdaHessian. Besides, when pruning DNNs, M-FAC also shows an improvement compared with WoodFisher. ", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper starts the discussion from the rank-one matrix updating rule of the  empirical Fisher matrix's inverse, which is deduced directly from the SMW formula. This updating rule is discussed by the WoodFisher method. This SMW trick may be intractable due to the prohibitive time cost O(d^2*m) (d denotes the dimension of the parameter space and m denotes the number of gradients), and M-FAC can alleviate this cost by storing the intermediate information when updating the inverse vector product. Moreover, M-FAC can also be applied to any situation where the rank-one matrix updating rule exists.\n\nSpecifically, M-FAC includes the static algorithm and the dynamic algorithm. The static algorithm is for the common mini-batch situation within a single epoch, and the dynamic algorithm is used when the curvature information is updated by the new gradient. The result is that the time complexity can be decreased to linear-in-dimension. These algorithms are correct, and the derivation process is clear and natural. One problem may be that the algorithm would still be time-consuming when the dimension(d) is very large, and M-FAC is based on the recursion and may accomplish by for loops, which can be slow in real practice without distribute computing. Another possible problem of the dynamic algorithm may be that it is limited to the process of updating only one gradient. This might lead to the lack of flexibility when tuning, as other second-order methods can decrease the frequency of updating the curvature information.\n\nIn the experiments part, M-FAC performs better than WoodFisher when pruning DNNs. However, this may be a little confusing, because M-FAC and WoodFisher both use the SMW trick and the computation is exact. In Appendix D.8, \"The only parameters we change are the ones which pertain to our algorithm, in particular block size and number of gradients m\", so maybe the difference is from this change. If the settings of two methods are the same, would M-FAC still outperform WoodFisher? If so, what is the reason behind? Besides, M-FAC outperforms K-FAC and has a similar performance with AdaHessian. Nevertheless, K-FAC can be better than SGD in some cases, as shown in \"A Kronecker-factored approximate Fisher matrix for convolution layers (2016) \" (http://proceedings.mlr.press/v48/grosse16.pdf). As the M-FAC paper shows the results with \"Epoch\" instead of \"wall clock time\", the result that K-FAC is obviously slower than SGD is confusing. Another problem is that the paper also conduct experiments with GGT, and it performs badly. This may not be consistent with the results shows in \"Efficient Full-Matrix Adaptive Regularization (2019)\"(http://proceedings.mlr.press/v97/agarwal19b/agarwal19b.pdf). As the performance of M-FAC is similar to SGD in Figure 1(b), this numerical result is not show strong improvement. Furthermore, while some experiments are accomplished on Pytorch and others are accomplished on TensorFlow, the comparison might not be persuasive. Additionally, the experiments are accomplished on the ResNet20/Cifar-10, and the author need to add more experiments on other large datasets.  \n\nIt is recommended to add more related works, because the work on the updating rank-one matrix rule may be studied before. Some related works are also worth attention, like another approach to compute IHVPs in \"Sketchy Empirical Natural Gradient Methods for Deep Learning(2020)\"(https://arxiv.org/pdf/2006.05924.pdf). The algorithm containing the rank-one updating rule have been studied in \"Scalable Adaptive Stochastic Optimization Using Random Projections (2016)\"(https://arxiv.org/pdf/1611.06652.pdf). \n\nOverall, this paper is well-written. Here are a few detailed suggestions:\n* (Line 249) Should the first \"\\hat{F_i}^{-1}\" be \"\\hat{F_i}\" ?\n* (Section 3) More explanations to the different application scenarios of the static and dynamic algorithms would help readers understand their differences. \n* (Section 3.2) When showing the complexity analysis, it may be better to put the results in a table and add some comparisons with other second-order methods. \n* (Section 4.2) As the M-FAC changes the computing rule in one epoch, the improvement of the time cost within one epoch compared with other methods may be more persuasive. The result with \"wall clock time\" can also help.\n* (Table 4 Right) Add experiments with another second-order method (like K-FAC) would help readers understand the real improvement of the M-FAC. \n\nAfter reading the detailed rebuttal, I am still concerned on the efficiency and the difference to WoodFisher.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No obvious societal impact can be predicted", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical problem has been found", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "12 hours"}, "extra_text": {}}, {"review_id": "nxAEoiG3yqj", "reviewer": "Reviewer_YzjZ", "summary": "In this work, the authors propose efficient techniques for computing inverse of a matrix that is represented as a sum of rank-1 matrices. The basic idea is to use recursively well-known Sherman-Morrison formula for computing inverse of rank-1 update. The authors show that their technique can be applied for computing inverse of the empirical estimate of the Fisher Matrix and thus can be used in optimization algorithms and for so-called prunning of a trained model.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well-written and it is pleasant to read. Based on the Sherman-Morrison formula, the authors propose efficient update formulas that can be used for computing the inverse of a static matrix represented as a sum of 'm' rank-1 matrices in time O(d * m^2), where 'd' is the dimension of the problem. Hence, this technique can be efficient when the dimension of the problem is very big.\n\nMoreover, the authors show how to update inverse matrix, replacing just one component in the sum of rank-1 matrices, which requires O(dm^2 + m^3) time on preprocessing and O(dm + m^3) for one update. Taking into account that 'm' (the batch size) can be chosen to be small, these estimates seem to be quite reasonable for using in high-dimensional setting.\n\nThe authors provide efficient implementation of these methods and show that it can be used for two problems: static estimation of inverse of Fisher matrix at the optimum for prunning a trained model, and dynamic estimation of inverse of Fisher matrix for its usage in (preconditioned) \nStochastic Gradient Descent. \n\nI have only one major question with the experimental results on optimization algorithms: \nIt is not clear to me, whether the presented graphs and numerical results in the table demonstrate better performance of the new method (M-FAC). Indeed, in Figure 1(c), we see that the best performance has the Adam algorithm, in terms of the Training loss vs. Epochs. The performance of M-FAC is not significantly better than the perforamnces of K-FAC and SGD. In Figure 1(d) with the Test accuracy vs. Epochs we see the similar picture. Moreover, I am not sure that comparison only in terms of the number of Epochs is fair: the computational time among different methods can be quite different, and as we see in Table 4 the overhead of M-FAC is bigger than the overhead of K-FAC and significantly bigger than Adam/SGD. Hence, it looks to me that the Adam algorithm demonstrates the best performance in the provided experiments, from the optimization perspective. \n\n\nSome minor remarks:\n\n1. line 107: It is worth to mention that $p_{ \\theta }(x, y)$ is density function. Also, it is confusing that the arguments (x, y) and \\theta are swapped, comparinng with the joint distribution $P_{(x, y)}(\\theta)$.\n\n2. line 110: Hessian of 'theta' -> Hessian of 'L' at 'theta' ?\n\n3. line 249: Theorem 1 - the inverse of F in the beginning is redundant.\n\n4. line 342: 'overhead over SGD' - I think it is worth to add more description on this measure (is it computational time or arithmetical operations?)", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "-", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "HTXoErtzMw", "reviewer": "Reviewer_JscG", "summary": "The authors propose a compute-/memory- efficient implementation of inverse empirical Fisher vector products (IEFVPs) for deep neural networks, called M-FAC, based on the Woodbury-Sherman-Morrison inversion formula. They use IEFVPs as estimations of inverse Hessian vector products (IHVPs) used in model compression (e.g., Optimal Brain Damage) and second-order optimization. M-FAC is similar to the previous method, WoodFisher (Singh and Alistarh, 2020), which uses the WSM inversion formula to calculate inverse empirical Fisher. Unlike WoodFisher (calculates matrices), M-FAC directly calculates IEFVPs (vectors) and thus requires less compute/memory cost. This allows M-FAC to calculates IEFVPs with the full empirical Fisher and a larger number of samples ($m$) than WoodFisher. \n- The static algorithm (with a fixed set of samples) of M-FAC is tested on the one-shot/gradual pruning with trained CNNs on ImageNet. It shows a better accuracy-sparsity trade-off than WoodFisher and other magnitude-based methods. \n- The dynamic algorithm (with the fixed size sliding window of samples) of M-FAC is tested on training CNNs on CIFAR-10 and fine-tuning sparse CNNs on CIFAR-100 and ImageNet with preconditioned SGD. It shows a better computational overhead (vs. SGD) than existing second-order optimization methods in training and better accuracy than first-order methods in fine-tuning.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper is well-organized. The literature, algorithms, novelty, costs/limitations, and experiments are clearly explained.\nThe proposed M-FAC is a clear improvement over the previous WoodFisher algorithm for pruning DNN models.  However, I feel that there are intrinsic limitations of M-FAC (and methods based on the WSM inversion formula in general) regarding scalability and practicality, as I will describe below. For this reason, I believe this work does not contain enough ideas to be appreciated by the community, especially for practitioners. For the improvements, I would suggest exploring empirical/theoretical justification/insight of using a small sample size $m$ in pruning and optimization.\n\n---------------\n\nComments on pruning DNNs with the static algorithm\n- M-FAC is a natural, reasonable improvement over the WoodFisher. \n  - It allows the use of a larger sample size $m$ and the information of the full empirical Fisher, which is a clear advantage. \n  - As shown in the experiments, M-FAC can achieve a better accuracy-sparsity trade-off. \n- However, as discussed by the authors, the cost of storing the $m$ gradients is a problem that we cannot ignore in practice.\n  - If a model has massive parameters (and this is why we want to prune them), we can only use a very small $m$.\n  - The goal of the OBD/OBS framework is to measure the sensitivity of each parameter to the empirical loss (with training set).\n  - But we need to limit the sample size $m$ (e.g., 400, 1k, 4k) much smaller than the training set size (e.g., 1.28M for ImageNet).\n\nComments on optimization with the dynamic algorithm\n- No error bars (by varying initialization points) are reported, so it is unclear whether M-FAC shows better accuracy by chance.\n- Regarding the evaluation of second-order methods\n  - Second-order optimizers with rich (not diagonal) curvature information (e.g., K-FAC) tend to show faster convergence (in terms of epochs) than first-order optimizers. \n  - But no such fast convergence is observed in the experiments.\n  - I believe the benefit of second-order optimization is a faster convergence (we have theoretical justification/insight at least in convex problems) rather than better test accuracy (actually, we have the opposite insights, e.g., [1][2]).\n  - I feel it is not appealing to claim that the proposed second-order method achieves better test accuracy without theoretical justification/insight because it doesn't ensure success in general settings.\n- Due to the recursive nature of M-FAC (and the WSM inversion formula), it doesn't have much benefit to reuse the stale second-order information, which is an essential approach to reduce the frequency of evaluating the inverse and to make second-order methods practical.\n- Applying M-FAC to fine-tuning a sparse model (less dimensionality) is indeed efficient.\n  - However, as mentioned above, there is no convincing theoretical reason to achieve better test accuracy. \n\nOther comments\n- L67: “exactly computing the IHVP”\n    - I feel that it is inappropriate to call it “IHVP” (in many parts of the paper)\n    - What M-FAC calculates is inverse empirical Fisher vector products.\n- L79: $\\hat{F}_m^{-1}v$ -> $(\\hat{F}_m+\\lambda I)^{-1}v$\n\nReferences:\n1. Ashia C. Wilson et al.. The Marginal Value of Adaptive Gradient Methods in Machine Learning\n, 2017. https://arxiv.org/abs/1705.08292.\n2. Neha S. Wadia et al., Whitening and second order optimization both make information in the dataset unusable during training, and can reduce or prevent generalization, 2020. https://arxiv.org/abs/2008.07545.\n\n\n=========================\nUpdate after the discussion\n\nMost of my concern came from my misunderstanding: (1) M-FAC cannot achieve fast convergence due to the limited sample size and the low-quality estimate of the curvature, and (2) the authors claim that M-FAC can somehow achieve a better test accuracy. But these points turned out not to be the case, and now I appreciate this paper's “optimization part” (dynamic algorithm) as well as the \"pruning part\" (static algorithm). Given the results in the \"pruning part\" and \"optimization part,\" I am convinced that the techniques (i.e., static algorithm and dynamic algorithm) presented in this paper are indeed useful to evaluate the inverse-empirical-Fisher-vector product and interesting to the community. Therefore, I am happy to raise my score from 5 to 7 and recommend accepting.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors adequately addressed the limitations of the presented work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5.5 hours"}, "extra_text": {}}, {"review_id": "9n8NR75cZ65", "reviewer": "Reviewer_6ujH", "summary": "In this paper the authors derive a routine for calculating inverse fisher vector products, mostly based on the Woodbury-Sherman-Morrison Trick. They then demonstrate this routine by using it to compress and optimize neural network models.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "After reviewing the answers to my review and seeing the author commitments to including additional details and Transformer experiments, I am raising my score from a 6 to a 7.\n\n--------------------------------------------------\n\nOverall I believe this is a useful and interesting paper. It is well written and sufficiently novel, with comparisons to a few appropriate prior works. Hopefully, with useful implementations and more thorough comparisons, it could be a useful deep learning optimizer and compressor. For example, the paper would be made much stronger by including any sort of model architecture besides a CNN on images, such as a Transformer based model, or better yet a model which one believes could particularly benefit from additional optimization preconditioning. I am willing to change my score to a more decisive value after a discussion with the authors!\n\nConcerns:\nMost of my concerns are regarding the optimization section. In general, for the optimization experiments, is your goal to demonstrate that MFAC improves final test accuracies, or training speed? Given that this is a preconditioner, I would think training speed would be a more useful metric to show, therefore it is more useful to also include the wallclock time it takes to reach some target test accuracy (for example, show the number of seconds it takes to reach 92% CIFAR test accuracy). It’s very useful to clearly state what it means to “improve” upon baselines in optimization, as some training algorithms tune/optimize for regularization, training speed, final test accuracy, or other different objectives. Some other questions:\n-The appendix has good details for tuning the optimizers! One question that I still have is, were a similar number of hparam trials used for each method? I think it’s fine (and actually even a better idea) to use more tuning compute on baselines compared to a proposed method, so any extra tuning of GGT/KFAC is fine.\n-It would also be useful to report the exact tuning ranges/grids used.\n-What damping values were used for GGT/KFAC/MFAC? If one is much larger than others then that could be more like sgd. You say you used “an initial dampening of ≈ 0.1887” for KFAC, did you use a damping decay schedule or keep it fixed?\n-Fig 1d would be much more readable if zoomed in more (showing only accuracies above ~60%?)\n-Fig 1d seems to imply that an LR decay drop at 50/75% of training is very beneficial to the methods that used it; would it be possible to include one in the GGT/KFAC LR schedules? You could either reuse the same schedule as GGT/KFAC and add the decays in, or try more tuning on the initial LR but keeping the other hyperparameter adjustments?\n\nCorrectness:\n-For the TF KFAC baseline, did you set invert_every=1 if using kfac.PeriodicInvCovUpdateKfacOpt? If not, how did you set up the frequency of the covariance/inversion ops?\n-Did you use a validation set for the CIFAR experiments? For ImageNet it is unfortunately more common to tune on the test set because everyone uses the validation set as the test set (but I believe one should still carve out a slice of a training set), but for CIFAR there is a common convention to use 10% of the CIFAR10 training set as a validation set. Of course, you can always retrain on the full training set after selecting hyperparameters! While this may not change the ranking of baselines because (presumably) the same tuning budget and the same number of hyperparameters were used for each optimizer.\n-Was weight decay not used with Adam (no value was listed in Table 6 in the appendix. If not it would be useful to include it as another baseline for a fairer comparison, especially on CIFAR where overfitting is a big concern.\n\nWriting:\nNit: (8) and (11) are both missing a \\nabla in front of \\ell\n\nAdditional feedback:\n-Table 2 is a great direct comparison.\n-It’s great to see the provided CUDA kernel code.\n-Appendix D.11 is very interesting, it would be useful to reference it from the main text!\n-I’m surprised that you don’t need momentum to get MFAC to be competitive, it isn’t necessary but adding momentum would be an interesting addition", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I agree with the authors that I do not believe there are relevant societal impacts of this work that are useful to discuss at this time.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper uses a recursive Woodbury formula to maintain a low-rank approximation of the empirical Fisher information matrix, and uses this for parameter pruning and preconditioning in stochastic training. While this approach is a somewhat obvious application of the Woodbury formula, it appears to be the first time it has been seriously applied in the context of curvature matrix approximations for deep neural networks.

The reviewers found the paper to well-written and thorough, and the method to be a (potentially) useful tool. Therefore I'm recommending acceptance. 

However, I agree with many of the concerns raised by the reviewers, but am less convinced by the rebuttals than they were. The main one for me is that this method will not scale to large networks due to the need to store m parameter-shaped vectors. Relatedly, I found the claim made by the paper that this method has storage costs "linear in the dimension of the model" to be highly misleading, since m is not really a constant (and is anyway quite large even if it were just a constant). In reality, the storage costs of this method are a lot higher than pretty much every other method compared to.

I also don't view the optimization experiments as meaningful, and largely agree with the points raised by Reviewer JscG. It is known that preconditioning doesn't really accelerate training of residual networks at small/medium batch sizes (see https://arxiv.org/abs/1907.04164). This means that all optimizers will perform similarly on such problems, and any small differences in test accuracy are incidental and have nothing to do with faster optimization. It would be much more interesting to try these methods on problems where stronger optimizers are already known to make a substantial difference (or on ResNets at very large batch sizes as in https://arxiv.org/abs/1811.12019). I would also recommend that the authors remove the graph comparing training performance for the different optimizers, since they aren't even optimizing the same objective function. (And even if they were, it's not really meaningful to compare training accuracy curves using hyperparameters that were tuned for best final test accuracy.)

Decision: Accept (Poster)