Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: In this paper the authors propose the SLIM-QN algorithm, a stochastic, momentum-based quasi-Newton method to train deep neural networks. SLIM-QN tries to address two shortcomings of second-order methods. The first barrier is the high computational cost of calculating the Hessian matrix and its inverse. SLIM-QN tackles this by directly approximating the Hessian inverse using past parameters and gradients without explicitly constructing the Hessian and computing its inverse. The second challenge is the convergence instability caused by the stochastic training. SLIM-QN overcomes this issue by using momentum in the Hessian updates as well as an adaptive damping mechanism. The authors provide theoretical results on the convergence of SLIM-QN for stochastic convex optimization problems, for the case that the objective function is smooth and satisfies the PL condition. They further conduct numerical experiments on large dataset to show the effectiveness of SLIM-QN.
main_review: The paper is easy to follow and addresses an important problem. However, I have some major concerns about the assumptions and theoretical results.

1- The following text after equation (2) is a bit misleading. Specifically, the authors state that "By carefully choosing $s_k$, $\hat{H}_k^{-1}$ will converge to the real Hessian inverse at a linear rate for any strongly convex function (Rodomanov & Nesterov, 2021)." In (Rodomanov & Nesterov, 2021) the authors use a Greedy-based BFGS method and the nature of greedy BFGS allows the iterates to converge to the true Hessian. However, for any standard (classic) quasi-Newton method (including BFGS and L-BFGS) there is no conclusion that the Hessian inverse approximation converges to the exact Hessian inverse. All we can show for these algorithms is that the descent direction approaches the descent direction of Newton's method, i.e., $\hat{H}_k^{-1}\hat{g}_k\to {H}_k^{-1}{g}_k$. Since SLIM-QN is an L-BFGS-based quasi-Newton method we can’t expect that $\hat{H}_k^{-1}$ converges to ${H}_k^{-1}$. This point needs to be highlighted.

2- Assumption 3 is quite uncommon and strong for stochastic optimization analysis. In this assumption, the authors require the minimizer of each stochastic function to be the minimizer of the expected loss. This is indeed very strong, as it means that any stochastic descent direction (computed by a subset of samples) would move the iterates to the right minimum. Often in stochastic optimization theory we assume that in expectation we have a descent direction, but the required assumption implies that without taking expectation stochastic gradient or stochastic quasi-Newton directions will move the iterates towards the optimal solution.

3- The theoretical results, which are under some strong assumptions, do not showcase any improvement with respect to SGD or other quasi-Newton methods. To be more precise, under the considered assumption, one can easily establish a linear convergence rate for SGD or any stochastic quasi-Newton (SQN) method. The main unanswered question is whether SLIM-QN can provably outperform other stochastic methods (at least in a local neighborhood of the optimal solution) or not? Without such comparison or discussion the theoretical results are not informative and more importantly they don't improve the known bounds for SQN methods. 

4- The authors suggest that the proposed SLIM-QN method leads to a more stable QN method. Intuitively, this is a valid point as they use the idea of momentum in the update of their QN method. However, there is no rigorous study (at least for a simple quadratic problem) to show that the Hessian approximation matrices of the proposed method are more stable compared to standard SQN methods.

5- The momentum and damping techniques are used to stabilize the noise created in the stochastic setting and they don't lead to reduction of computational cost or memory. The computational complexity is the use of L-BFGS method from the previous work as stated in Algorithm 1. The authors should highlight that the use of L-BFGS idea allows them to reduce the computational cost, and the momentum and damping techniques have nothing to do with the computational cost reduction. Their impact is only on stabilizing the learning process.
summary_of_the_review: Overall, I think the required assumptions are strong and the theoretical results are not significant.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes SLIM-QN, a light stochastic quasi-Newton optimizer for training large-scale deep neural networks (DNNs). Based on previous results, SLIM-QN proposes to introduce momentum in Hessian updates to stabilize the training and adaptive damping mechanism to guarantee that the approximated Hessian is always positive definite. They prove the convergence of SLIM-QN under some assumptions. Some experimental results are also given.
main_review: 
### Strengths
1. The paper is well-written and easy to follow.
2. The proposed SLIM-QN has some computational and memory advantages.


### Concerns
1. In section 3.1, not sure why to consider $\mathcal{L} = \frac{1}{2}\left\lVert \theta \right\rVert^2$. It seems useless in practice. 
2. AS1 and AS3 are very strong assumptions.
3. SLIM-QN is a method based on L-BFGS but Table2 and experiments lask the comparisons with the same kind of methods, e.g. BFGS and L-BFGS.
summary_of_the_review: Both the theoretical and experimental results are not sufficient. The assumptions of theoretical results are too strong and experimental results lack the comparison with the same kind of methods.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: 
In this paper SLIM-QN  is proposed to  addresses two key barriers in existing second-order methods for large-scale DNNs: 1) the high computational cost of obtaining the Hessian matrix and its inverse in every iteration (e.g. KFAC); 2) convergence instability due to stochastic training (e.g. L-BFGS).
Converegence   results are provided in a stochastic setting. Numerical evaluations on real data  shown the advantage of in terms of  speed and accuracy. 
main_review: As it for me,  it seems to be a nice work in developing second order method for large scale machine learning.  And I go over the proof quickly, it also seems ok.  
summary_of_the_review: In this paper SLIM-QN  is proposed. Converegence   results are provided in a stochastic setting. Numerical evaluations on real data  shown the advantage of in terms of  speed and accuracy.  I not quite sure why SLIM is faster than sgd (as reported  the wall-clock time) ? What is the stopping rule the authors used  for SGD ？
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This work proposes techniques that stabilize the small-batch training of neural networks by L-BFGS optimizer. To reduce the stochastic noise of gradient and Hessian, they suggest taking the momentum of the parameter difference and gradient difference used to estimate the inverse-Hessian-gradient product in L-BFGS. In training Resnet models and Vision Transformer models on image classification tasks (CIFAR-10, ImageNet-1k) with small batch size, the proposed SLIM-QN method (L-BFGS + momentum + adaptive damping) achieves a faster training time than SGD.
main_review: Strengths
- This work proposes useful techniques (momentum and adaptive damping) to stabilize the L-BFGS algorithm in training neural networks with a small mini-batch size (as I will describe below, the motivation of applying L-BFGS to small-batch training is not convincing though).
- This is the first empirical result showing that the second-order optimization method can achieve faster training time than SGD for training a Vision Transformer model.

Weaknesses
- The motivation of applying L-BFGS to small-batch training is not convincing.
    - The authors motivate using/stabilizing L-BFGS in small-batch training by stating that using a separate large batch to reduce stochastic noise “dramatically increases the computation cost and negates performance gains in wall-clock time”. But what if we train a model with a large batch size? 
    - Zhang et al, 2019 [1] empirically showed that the “critical batch size”, in which the data efficiency (test accuracy vs number of examples a model consume) of mini-batch training decreases, of a second-order method (K-FAC) is larger than SGD and Adam. This means that we might be able to train a model by a second-order optimization with a large batch with the same number of epochs (i.e., the same number of total examples the model consume) as small-batch training with less stochastic noise. 
    - Note that by accumulating multiple batches of mini-batch gradients before updating parameters, it is possible to train a model with arbitrary batch sizes even with a single processor. As long as the data efficiency is constant, the total computing cost (the total number of examples to calculate gradients) is also constant. So, simply using a large batch size may eliminate stochastic noise without additional computational and memory costs. 
    - Therefore, to motivate small-batch training, it is necessary to present that L-BFGS has problems in large-batch training such as generalization performance degradation (as in large-batch SGD [2]).
- Parts of the discussion of the pros and cons of K-FAC and SLIM-QN (L-BFGS) are not appropriate.
    - In Figure 2, only the computational/memory overheads of K-FAC is highlighted by red color. However, the overheads of SLIM-QN (L-BFGS) for “Model update” is actually much larger than K-FAC for most of the case. For example, assume $d_i=\sqrt{||\theta_i||}$, the memory overhead of K-FAC in “Model update” will be $2||\theta||$ while that of SLIM-QN (L-BFGS) is $M$ times larger (actually this should be $2(M+1)$ because SLIM-QN needs to keep the momentum of the parameter difference and gradient difference). As $M=10-20$ is typically used, this is problematic especially when the model size is huge (e.g., 175B parameters of GPT-3 model [3]). Therefore, SLIM-QN (L-BFGS) is not suitable for training large models. On the other hand, the inverse matrix calculations in K-FAC can be distributed across multiple processors, thus reducing the computation time [4]. In addition to this, if K-FAC can be used with a large-batch size, the total number of parameter updates (i.e., number of inverse calculations) will be reduced. When combined with inverse frequency reduction (i.e., $1/L$), the computational overhead of K-FAC becomes even smaller. SLIM-QN (L-BFGS) can be more efficient than K-FAC if the target model is small enough to allow $M$ to be sufficiently large. However, the absence of these discussion in the current manuscript gives an unfair impression.
    - The authors state that “Unlike KFAC, SLIM-QN can easily incorporate weight decay (wd) by simply adding wd”. I assume that the authors mean L2 regularization by “weight decay” because we can easily incorporate weight decay to K-FAC as well (i.e., $g=g_{kfac}+\alpha\theta$). The previous works suggest that weight decay is better (better generalization performance, increased effective learning rate = training speed) than L2 regularization for Adam [5] and K-FAC [6]. Therefore, it is not a major problem for K-FAC that L2 regularization (the authors probably call it weight decay) is difficult to integrate.
    - The authors argue that K-FAC “need to run backward passes multiple times”. This is not the case when the empirical Fisher is used as an estimate of the Fisher information matrix in K-FAC. The empirical Fisher can be calculated during the backward pass of the empirical loss. Osawa et al. [4] showed that K-FAC with empirical Fisher can achieve the same accuracy with an estimate Fisher by one Monte-Carlo sampling from the model’s predictive distribution in training ResNet-50 on ImageNet-1k classification (the same thing does not necessarily happen in different settings, though).
- SLIM-QN’s practical usefulness is still questionable.
    - The authors state that “it is easy to conduct a grid search on a small models and datasets, explore how these parameters affect optimization, then apply them to large-scale model training”. I believe that the authors need to quantitatively evaluate how “easy” this process is. The behavior of the Hessian during training may change significantly when the model size or data size changes. 

Other comments
- The authors introduce their method as “SLIM-QN directly approximates the Hessian inverse using past parameters and gradients, without explicitly constructing the Hessian matrix and then computing its inverse”. However, this is just a description of BFGS or L-BFGS. I think it would be easier for readers to understand the differences of SLIM-QN from L-BFGS (the contribution of this work) if the explanation is something like “SLIM-QN is L-BFGS with additional techniques such as momentum and adaptive damping.” In fact, SLIM-QN is implemented as the “LBFGSOptimizer” in the author’s code.

References
- [1] G. Zhang et al. Which Algorithmic Choices Matter at Which Batch Sizes? Insights From a Noisy Quadratic Model. https://arxiv.org/abs/1907.04164, 2019.
- [2] N. S. Keskar et al. On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima. https://arxiv.org/abs/1609.04836, 2017.
- [3] T. B. Brown et al. Language Models are Few-Shot Learners. https://arxiv.org/abs/2005.14165, 2020.
- [4] K. Osawa et al. Scalable and Practical Natural Gradient for Large-Scale Deep Learning. https://arxiv.org/abs/2002.06015, 2020.
- [5] I. Loshchilov and F. Hutter. Decoupled Weight Decay Regularization. https://arxiv.org/abs/1711.05101, 2019.
- [6] G. Zhang et al. Three Mechanisms of Weight Decay Regularization. https://arxiv.org/abs/1810.12281, 2018.

summary_of_the_review: This work provides interesting empirical results that a second-order optimization method (other than K-FAC) can achieve fast training in the ImageNet scale. Also, this is the first result that a Vision Transformer model is trained by a second-order optimization method faster than SGD. These results can be a data point for future studies on more efficient optimization methods for deep neural networks. However, the motivation for small-batch training, which is the main target of this study, is not convincing. Moreover, the validity of the comparison between the proposed and existing methods (K-FAC) is questionable.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper improves L-BFGS by adding momentum to the gradients and past parameters, and adding a damping term to the Hessian to improve the condition number. This ensures that the Hessian inverse is stable (i.e. is not very much affected by individual mini-batches) and its eigenvalues are well controlled.

The authors prove the convergence of their algorithm, using standard techniques. They also provide space and time complexity estimates for their algorithm, and compare it against the estimates for SGD and KFAC.

The authors run their algorithm on Imagenet with Resnet-50, and compare its performance with SGD and KFAC. They also perform experiments to show that both damping and momentum are important for convergence: without momentum, the validation performance oscillates more, and without damping the algorithms diverges.
main_review: The idea of combining momentum with L-BFGS has been explored before, e.g. in Chang et al "An Accelerated Linearly Convergent
Stochastic L-BFGS Algorithm", 2019. I would like to see a comparison between the proposed method and that algorithm, they seem quite different. Damping to avoid very small eigenvalues of the preconditioners is also a standard technique.

In table 2, the authors compare the time and memory of SGD, KFAC against SLIM-QN. The memory requirements of the proposed method are quite high, up to 20-40 times more than SGD, this would prevent this method from being used for the large models such as BERT that are commonplace in ML practice today (Resnet-50 has 23M parameters, whereas BERT has 340M). Is it possible to sketch the historical gradients and parameters to reduce this memory significantly?

The experiments compare the proposed method against KFAC and SGD only, ignoring the more commonly used optimizers such as Adam and LAMB, and completely ignoring other second order optimizers. The new method matches SGD on Resnet-50 in 95 epochs with a batchsize of 256, and is slightly more expensive, and neither achieved the ML-Perf benchmark accuracy of 75.9, which can now be achieved in less than 50 epochs. Also, these other implementations use much larger batch-sizes like 32K or 64K (larger batches usually means larger number of epochs for the same accuracy) --- thus 95 epochs seems far too high. I would like to see the results on larger batch-sizes anyway as I suspect that the benefits of momentum and damping may not be as significant.
summary_of_the_review: Overall I feel that both the novelty and impact of the paper are somewhat limited. The key techniques proposed have been studied before, and the resulting method is only practical for small problems. Further the gains from this method are rather small compared to current optimizers, and the authors do not compare against the best optimizers.
review_title: null

Meta-review: Although the reviewers acknowledge that the paper is well-written and easy to follow, they found that the contributions of the paper are not enough to be accepted at ICLR. Some concerns from the reviewers are as follows: 

1. Assumption 3 is very strong and uncommon. It is not easy to verified even for over-parameterized setting. 
2. Both the theoretical and experimental results are not sufficient. No improvement in theoretical results compared to the previous work. Moreover, the performance of the method is no better than the baselines, which are themselves much weaker than state-of-the-art results.
3. Motivation for small-batch training, advantages over K-FAC, the practicality of SLIM-QN, and novelty compared to L-BFGS are questionable.
4. The method is essentially LBFGS with momentum and damping of the hessian, hence its novelty is questionable. 
5. The authors emphasize that "we are trying to design a practical QN method with light compute/memory cost, especially when applied to large-scale NNs". Any method that has 20-40 times as much memory requirement as SGD cannot be said to have light memory cost. 

Based on the above concerns, the paper is not ready for the publication at this moment. The authors should consider to improve the paper by addressing the reviewers' comments and implementing their suggestions and resubmit this paper in the future venues.
Decision: Reject