Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper addresses the problem of using second-order information in large-scale machine learning tasks (e.g. training neural networks). It proposes a Kronecker-factored Approximate Curvature (KFAC)-approximated, Tikhonov regularized Gauss-Newton (GN) update step. Instead of a single regularization parameter ($\lambda$), the update step in the paper uses two independent regularization parameters ($\lambda_g$ and $\lambda_a$). The paper relates different settings of $\lambda_a$ and $\lambda_g$ to other algorithms (i.e. classical GN and gradient descent). It shows that allowing $\lambda_g$ grows to infinity gives a computationally efficient update step. It provides empirical results on their proposed method.
strengths_and_weaknesses: Strengths:
1. The update step $\xi^*$ is interesting and practical. The paper provides experiments to show that using $\xi^*$ can lead to lower computation time without sacrificing performance. Experiments are thorough and tested on some fairly large neural network architectures.
2. The update step $\xi$ is a nice, compact way to describe an algorithm for training neural networks. The analysis of $\xi$ provides various ways of interpreting the algorithm in terms of different regularization parameter settings. The properties of $\xi$ are interesting. The analysis is relatively thorough (e.g. showing that any combination of $\lambda_g$ and $\lambda_a$ will still result in a descent direction).
3. Paper is well-written and clear. 

Weaknesses
1. Some of the experiments are not benchmarked to SOTA (which is acknowledged by the paper). This might affect people's willingness to adopt the method in practice.  
questions: 1. Line 70 refers to $H$ in Equation 6. Typo?
2. Is there an intuitive interpretation of the preconditioner $M$ in Remark 2? Does this preconditioning help in terms of reducing the number of iterations needed to reach a solution?
limitations: This work does not appear to me to have negative social impact.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: Inspired by the KFAC approximation and the Tikhonov regularization of the Newton method, this paper proposes a regularized K-FAC approximated Gauss-Newton type method called ISAAC. The proposed method is based on only the input to a respective layer, therefore does not suffer from a substantial computational overhead. Numerical experiments show the advantages of the proposed method compared to both first-order type and second-order type methods. 

strengths_and_weaknesses: Strengths:

Regularization parameters is crucial for second-order type methods.  The authors first approximate the GGN matrix as a kroncker product of two matrices, and then view two regulation parameters independently. By letting the two regularization parameters vanish or go to infinity, one can obtain new directions and therefore new methods. The proposed method is more efficient than KFAC since only one matrix should be inverted and no need extra propagation to compute $g$.  

Weaknesses:

This paper should be polished to make it easier to read. 

Some related literatures on second-order methods should be mentioned, such as Shampoo[1], KBFGS[2], NG+[3] and SENG[4]. 

Some theoretical properties is natural and trivial. It is better to formalize an algorithm and give a convergence result.

It is better to add some large numerical examples, such as Resnet50 with Imagenet-1k and make a comparison with other second-order methods Shampoo[1], KBFGS[2], NG+[3] and SENG[4]. 

[1] Gupta,V.,Koren,T., Singer,Y.:, Shampoo: Preconditioned stochastic tensor optimization. In: International Conference on Machine Learning.

[2] Goldfarb, D., Ren, Y., Bahamou, A.:, Practical quasi-Newton methods for training deep neural networks. In:Advances inNeural Information Processing Systems.

[3] Yang, M., Xu, D., Cui, Q., Wen, Z., & Xu, P. (2021). NG+: A Multi-Step Matrix-Product Natural Gradient Method for Deep Learning. arXiv preprint arXiv:2106.07454.

[4] Yang, M., Xu, D., Wen, Z., Chen, M., & Xu, P. (2020). Sketch-based empirical natural gradient methods for deep learning. Journal of Scientific Computing.
questions: line 60: change [14],[15] to [14.15]. It is better to put multiple references in the same brackets. Please check other places.

It is better to add the discussion between GGN matrix and Fisher matrix, which can refer to [1,2] and related literatures.

It is better to add a left brackets after $\eta$ and a right bracket before the gradient in eq.(16). Please also add brackets in a suitable place in eq. (17).

In eq.(19), the gradient should be $\mathrm{g}^\top a /b$ where the $b$ is missed. In eq.(19), the authors use the same batch to approximate the GGN matrix and compute the gradient. Can the batches for approximation of the GGN and the computation of the gradient be different? In that case, what the related theoretical properties will be?

When the objective function is convex, the GGN matrix is positive semi-definite matrix. Adding a regularization parameter in GGN, It is t easy to show that $\zeta$ is an ascent direction, which means Theorem 2 is trivial.

The authors consider the fully-connected neural network in this paper. I believe this method can be extended to convolutional neural networks. And in numerical part, the authors have done some experiments. I wonder can we obtain some explanation from theory for this case? 

For the kronecker approximation of the GGN matrix, $\mathrm{a}\mathrm{a}^\top$ is more important than $\overline{g}^\top\overline{g}$ part. I once validate it numerically. One reason is that each value of the matrix $\overline{g}^\top\overline{g}$  is very small so that the $\lambda_g$ domains. I have noticed one related work recently. The work is named NG+[3].

[1] Botev, Aleksandar, Hippolyt Ritter, and David Barber. "Practical gauss-newton optimisation for deep learning." International Conference on Machine Learning. PMLR, 2017.

[2] Martens, James. "New insights and perspectives on the natural gradient method." The Journal of Machine Learning Research 21.1 (2020): 5776-5851.

[3] Yang, M., Xu, D., Cui, Q., Wen, Z., & Xu, P. (2021). NG+: A Multi-Step Matrix-Product Natural Gradient Method for Deep Learning. arXiv preprint arXiv:2106.07454.
limitations: Yes
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper proposed a KFAC variant to improve the computation efficiency. It introduces two Tikhonov regularization terms into KFAC, and makes gradient conditioning more efficient by force $\lambda_g$ go to infinity. The authors present a theoretical guarantee that the optimization still goes in the right direction even with such an adaptation. The authors also show ISAAC is more computation efficient in small-batch stochastic regimes.

However, I feel contributions in this paper are rather limited, and some motivations might need further justification.

strengths_and_weaknesses: Strength:

The paper is well written. Preliminaries and methods are clearly explained. 

Weaknesses:

1, Contributions are limited. Reducing the compute costs of KFAC is a good problem. However, I am not convinced that separating the regularization term and using a large regularization is a novel and effective solution. It only makes the optimizer behave more and more like SGD. As the authors stated in Theorem 1, small $\lambda_a, \lambda_g$ leads to KFAC, while large $\lambda_a, \lambda_g$ leads to vanilla gradient descent. 

2, Empirical results need to be enhanced. The authors use several empirical results to support the claim that ISAAC still behaves like KFAC even though using a strong regularization factor. However, I do not think current results are strong enough to support the claim. The issues in the empirical evaluations also make me doubt the contributions in the paper. 

- 2.1, The author should provide more baselines (Adam, SGD with momentum) so that we can really have a fair evaluation. 

- 2.2, For Figure 1, my understanding is that the authors are trying to show ISAAC still obtains good results (loss and accuracy) even with large regularization. If so, I do not think it is necessary. As the authors stated in Theorem 1, larger regularization makes ISAAC behave more like SGD. Therefore, getting similar loss and accuracy is no surprise.
    
- 2.3, For Figure 2, there are several issues. First, hyper parameters are not fully revealed. For instance, what is the weight decay for each optimizer since weight decays large affects training convergence?  Second, only the training curve is reported. The author really should present both a training and validation curve. In many cases, we can have faster convergence on training dataset, but not for validation dataset. 

- 2.4, For Figure 6, the reported accuracy is obviously lower compared to results we usually have on CIFAR-10. The reason might be that the authors use SGD without momentum. However, I am not convinced under such a setting. SGD with momentum is a default setting in many training tasks. Without momentum, I do not think the results will provide meaningful comparisons and conclusions.

3, Training with small batches should be further justified. I understand the authors stress the compute benefits of ISAAC in a small-batch regime (Theorem 3-ii). However, considering more general settings, the authors should well justify it: is it worth accelerating the training using small batches given the fact that large batches can also improve convergence performance even using SGD. Therefore, I think not only should the author provide results in small-batch regimes, training using large batches should also be evaluated and compared with other baselines.
questions: See my comments above.
limitations: No
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: In unconstrained optimisation, Newton's method uses inverse Hessian to determine the step size of the update. When applied to deep learning, the sheer size of the Hessian matrix makes Newton's method intractable. Among existing attempts to address this challenge, K-FAC is a promising approach. In practice, Tikhonov regularization/damping is used to avoid divergence.

In this paper, the authors introduced an extension to the standard Tikhonov damping for K-FAC. The main idea is to use two independent damping parameters (hyper-parameters for regularisation) instead of one damping parameter, one for the gradient factor and one for the activity factor, as shown in Equation (17). The authors explored special cases where the two parameters are either 0 or infinity. They also discussed the special case of setting one parameter to infinity, effectively removing the gradient factor in K-FAC. One major claim was that this activity-only form has an advantage in reduced computational complexity, although I don't find a theoretical comparison with K-FAC in this aspect. 

The claim for computational efficiency was mostly supported via empirical evaluation.
strengths_and_weaknesses: Strengths:

1. The paper addresses an important problem: efficient approximation of Gaussian-Newton approximation
2. The exposition is mostly clear, especially if you are already familiar with the existing literature.
3. The experiments seem comprehensive.

Weaknesses:

1. It is not clear what is the main contribution of this paper. Is it the two-parameter damping mechanism (What advantage do we gain)? Or is it the special case mentioned in Remark 3 (Why this is a still good approximation without $g^{\top}g$)? 
2. Many theoretical results presented look rather trivial.
questions: What is the intuition behind Eq (21)? Compared with Eq (13), why is it a good approximation?
limitations: N/A
review_title: null

Meta-review: metareview: The paper adds two regularization parameters that creates a method that interpolates between gradient descent and KFAC. The authors then prove the method interpolates, then several numerical experiments are presented on MNIST, and training BERT, and resnets. But the reviewers were not convinced by the experimental results, which did not benchmark the methods against SOTA, or lacking large scale experiments, and also lacking comparisons against other second order methods, for which there are now many.

In addition to this, though the paper cites broadly, it does not review, cite or cover the recent efforts on improving KFAC.  For example the missing reference [1]. Though this is a quasi-Newton approach, they also employ a type of regularization to aa^T term. Finally, I think the introduction of these two regularization parameters needs to be slightly better motivated. For now, the motivation is to interpolate between SGD and KFAC. But this is not enough. One can always generate new methods by interpolating between existing methods by adding a parameter. I recommend exploring the LM (Levenberg Marquardt) viewpoint of this type of regularization. This may gives other viewpoints and motivation for using these two regularization parameters.

[1] Goldfarb, D., Ren, Y., Bahamou, A.:, Practical quasi-Newton methods for training deep neural networks. In:Advances inNeural Information Processing Systems.
confidence: Less certain
Decision: Reject