Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: 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.
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.

Moreover, 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.

The 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) 
Stochastic Gradient Descent. 

I have only one major question with the experimental results on optimization algorithms: 
It 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. 


Some minor remarks:

1. 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)$.

2. line 110: Hessian of 'theta' -> Hessian of 'L' at 'theta' ?

3. line 249: Theorem 1 - the inverse of F in the beginning is redundant.

4. line 342: 'overhead over SGD' - I think it is worth to add more description on this measure (is it computational time or arithmetical operations?)
limitations_and_societal_impact: -
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.
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.

--------------------------------------------------

Overall 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!

Concerns:
Most 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:
-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.
-It would also be useful to report the exact tuning ranges/grids used.
-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?
-Fig 1d would be much more readable if zoomed in more (showing only accuracies above ~60%?)
-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?

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

Writing:
Nit: (8) and (11) are both missing a \nabla in front of \ell

Additional feedback:
-Table 2 is a great direct comparison.
-It’s great to see the provided CUDA kernel code.
-Appendix D.11 is very interesting, it would be useful to reference it from the main text!
-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
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_title: null

final_score: rating: 7: Good paper, accept
review_content: 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. 
- 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. 
- 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.
main_review: This paper is well-organized. The literature, algorithms, novelty, costs/limitations, and experiments are clearly explained.
The 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.

---------------

Comments on pruning DNNs with the static algorithm
- M-FAC is a natural, reasonable improvement over the WoodFisher. 
  - It allows the use of a larger sample size $m$ and the information of the full empirical Fisher, which is a clear advantage. 
  - As shown in the experiments, M-FAC can achieve a better accuracy-sparsity trade-off. 
- However, as discussed by the authors, the cost of storing the $m$ gradients is a problem that we cannot ignore in practice.
  - If a model has massive parameters (and this is why we want to prune them), we can only use a very small $m$.
  - The goal of the OBD/OBS framework is to measure the sensitivity of each parameter to the empirical loss (with training set).
  - 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).

Comments on optimization with the dynamic algorithm
- No error bars (by varying initialization points) are reported, so it is unclear whether M-FAC shows better accuracy by chance.
- Regarding the evaluation of second-order methods
  - 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. 
  - But no such fast convergence is observed in the experiments.
  - 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]).
  - 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.
- 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.
- Applying M-FAC to fine-tuning a sparse model (less dimensionality) is indeed efficient.
  - However, as mentioned above, there is no convincing theoretical reason to achieve better test accuracy. 

Other comments
- L67: “exactly computing the IHVP”
    - I feel that it is inappropriate to call it “IHVP” (in many parts of the paper)
    - What M-FAC calculates is inverse empirical Fisher vector products.
- L79: $\hat{F}_m^{-1}v$ -> $(\hat{F}_m+\lambda I)^{-1}v$

References:
1. Ashia C. Wilson et al.. The Marginal Value of Adaptive Gradient Methods in Machine Learning
, 2017. https://arxiv.org/abs/1705.08292.
2. 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.


=========================
Update after the discussion

Most 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.
limitations_and_societal_impact: The authors adequately addressed the limitations of the presented work.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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. 
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.

Specifically, 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.

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

It 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). 

Overall, this paper is well-written. Here are a few detailed suggestions:
* (Line 249) Should the first "\hat{F_i}^{-1}" be "\hat{F_i}" ?
* (Section 3) More explanations to the different application scenarios of the static and dynamic algorithms would help readers understand their differences. 
* (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. 
* (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.
* (Table 4 Right) Add experiments with another second-order method (like K-FAC) would help readers understand the real improvement of the M-FAC. 

After reading the detailed rebuttal, I am still concerned on the efficiency and the difference to WoodFisher.

limitations_and_societal_impact: No obvious societal impact can be predicted
review_title: null

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)