SLIM-QN: A Stochastic, Light, Momentumized Quasi-Newton Optimizer for Deep Neural Networks
Authors: Yue Niu
Zalan Fabian
Sunwoo Lee
Mahdi Soltanolkotabi
Salman Avestimehr
Venue: ICLR 2022 Submitted (2022)
Keywords: Second-Order Methods
Stochastic Optimization
Deep Neural Networks

Abstract: We propose SLIM-QN, a light stochastic quasi-Newton optimizer for training large-scale deep neural networks (DNNs).
SLIM-QN 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).
To tackle the first challenge,SLIM-QN directly approximates the Hessian inverse using past parameters and gradients, without explicitly constructing the Hessian matrix and then computing its inverse.
To achieve stable convergence, SLIM-QN introduces momentum in Hessian updates together with an adaptive damping mechanism.
We provide rigorous theoretical results on the convergence of SLIM-QN in a stochastic setting.
We also demonstrate that SLIM-QN has much less compute and memory overhead compared to existing second-order methods. 
To better understand the limitations and benefits of SLIM-QN, we evaluate its performance on various datasets and network architectures.
For instance on large datasets such as ImageNet, we show that SLIM-QN achieves near optimal accuracy $1.5\times$ faster when compared with SGD ($1.36\times$ faster in wall-clock time) using the same compute resources.
We also show that SLIM-QN can readily be applied to other contemporary non-convolutional architectures such as Transformers.

Under review as a conference paper at ICLR 2022
SLIM-QN: A STOCHASTIC, LIGHT, MOMENTUMIZED QUASI-NEWTON OPTIMIZER FOR DEEP NEURAL NET- WORKS
Anonymous authors Paper under double-blind review
ABSTRACT
We propose SLIM-QN light stochastic quasi-Newton optimizer for training large-scale deep neural networks (DNNs). SLIM-QN 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 (c.g. L-BFGS). To tackle the first challenge, SLIM-QN uses the BFGS update rule that directly approximates the Hessian inverse using past parameters and gradients, without explicitly constructing the Hessian matrix and then computing its inverse. To achieve stable convergence, SLIM-QN introduces momentum in Hessian updates together with an adaptive damping mechanism. We provide rigorous theoretical results the convergence of SLIM-QN in stochastic setting. We also demonstrate that SLIM-QN has much less compute and memory overhead compared existing second-order methods. To better understand the limitations and benefits of SLIM-QN, we evaluate its performance on various datasets and network architectures. For instance on large datasets such as ImageNet, we show that SLIM-QN achieves near optimal accuracy 1.5x faster when compared with SGD (1.36x faster in wall-clock time) using the same compute resources. We also show that SLIM-QN can readily be applied to other contemporary non-convolutional architectures such as Transformers.
INTRODUCTION
Second-order methods have been extensively investigated in the classical convex optimization literature. Indeed variants such as quasi-Newton methods are known to deliver faster convergence than gradient descent (GD) and achieve the best overall run time for many tasks (Gao & Goldfarb 2019; Rodomanov & Nesterov 202T). However, the Achilles heel of second-order methods that has impeded their wide adoption for large-scale machine learning problems is their substantial compute and memory cost, rendering them less favorable than popular stochastic first-order methods such as SGD (aadd 1998) and its variants (Duchi et al. 2011 Kingma & Ba 2014).
The aforementioned barriers stem from computing second-order information (loss Hessian w.r.t model parameters and its inverse), which typically dominates run-time, especially for large-scale models such as ResNet (He et al. (016)) and Vision Transformer (Dosovitskiy et al.) (2020a). on large datasets such as ImageNet (Deng al. 2009). To mitigate these issues, approximation methods have been developed to either approximate Fisher information matrix (expected Hessian matrix under negative log- likelihood loss) (Martens & Grosse 2015; Ba et al.) 2016, Pauloski et al. (020) or directly approximate the Hessian inverse (Fletcher 2013 Mokhtari & Ribeiro, 2015 Moritz et al.
2016, Gower et al.) 2016 Gao Goldfarb (018). 8). prominent example of the first category is KFAC (Martens & Grosse 2015 Ba et al. 2016) which utilizes gradient conditioner based on
Fisher information and also approximates the matrix as Kronecker product of small sub-matrices,
therefore simplifies matrix inversion. An example from the second category is L-BFGS (Nocedal
1980 Liu & Nocedal) 1989) which aims to directly approximate the Hessian inverse by iterating over the past parameter and gradient changes, without explicitly constructing the Hessian matrix itself.
These methods. while to some extent alleviate the compute and memory costs of second order methods, still experience performance convergence issues when used for training on large-scale

---

Under review as a conference paper at ICLR 2022
models. For instance, even though KFAC has faster per-iteration convergence compared to SGD, this gain is often significantly neutralized by the need to run backward passes multiple times to estimate Fisher information in each mini-bated iteration and then perform costly matrix inversion (Pauloski
et al. 2020). Similarly, stochastic BFGS variants (Mokhtari & Ribeiro 2015; Moritz et al. 2016)
Gower al. 2016) have yet be proven efficient in training large-scal le models such ResNet
in practice. A key challenge is that computationally intensive techniques are required to address
convergence instability issues in this literature (Mokhtari & Ribeiro, 2015 Moritz al., 2016 Chang
et al.. 2019), y. which unfortunately offset the compute benefits. More recently, authors in (Goldfarb
al. 2020) propose to lessen the computation burden of matrix inversion in KFAC via like updates with promising results on simple architectures. However the efficacy of this approach is yet to be demonstrated on practical DNNs and large-scale datasets.
To simultaneously mitigate the computation and instability barriers in second-order methods, we propose SLIM-QN M-N,, a stochastic light stable BFGS-lik method that achieves convergence advantages of second-order methods, while only using modest compute and memory cost compared to other techniques such as KFAC. SLIM-QN addresses the barriers second-order methods in two ways. To reduce compute cost while maintaining fast convergence of second-order methods, SLIM- SLIM-QN introduces momentum into the Hessian update. By utilizing momentum on past parameter and gradient changes, SLIM-QN smooths out the Hessian approximation without incurring costly variance reduction methods (e.g. a separate large batch size to estimate the Hessian). Furthermore, to ensure stable convergence, SLIM-QN uses an adaptive damping mechanism adjust gradient changes as to guarantee positive definiteness of the approximated Hessian inverse in stochastic settings. This adaptive damping scheme effectively restrains abnormal eigenvalues in the Hessian inverse and steers the optimization trajectory towards desirable directions.
SLIM-QN delivers faster convergence compared to SGD in various models and datasets. The convergence advantage is even more striking on large-scale models and datasets. Furthermore, due to its simplicity, SI.M-QN MN enjoys much better wall-clock convergence gains than other second-order methods such as KFAC.
In summary, our main contributions are as follows:
1. We develop SLIM-QN, stochastic quasi-Newton algorithm targeting large-scale models, that achieves both fast and stable convergence and low computation complexity, via introducing momen- tum and damping into the Hessian updates.
We provide a rigorous analysis for SLIM-QN showing that this algorithm converges at a linear rate for stochastic optimization problems.
We provide complexity analysis that demonstrates that SLIM-QN is lighter than other second-order methods leading to reductions in overall wall-clock training time.
Finally, we carry out comprehensive evaluations on various models and datasets that show that SLIM-QN delivers faster convergence compared to SGD, especially for large datasets such as ImageNet. For instance, to reach near optimal accuracy when training ResNet-50 on ImageNet, SLIM-QN is 1.5x than SGD (1.36x faster in wall clock time). Furthermore, when training Vision Transformer models, SLIM-QN also achieves faster convergence and higher accuracy.
2 PRELIMINARIES
In this paper we consider a typical empirical loss minimization problem of the form min L(,, =
A EN ((0, æ.)), where 0 denotes the parameters of the model be optimized. and X {x N are the training data where consists of both features and labels. The loss function is typically minimized through some variant of gradient descent, that uses the local gradients g: (o.(O.) directly to update the model parameters via iterates of the form
i=1
0 0 7/:
(1)
where 7/ denotes the step size (learning rate) at iteration t. However, such GD updates typically slow especially for ill-condtiioned problems (Nesterov 2003). To speed up the convergence, often second-order methods used. In particular, Quasi-Newton (QN) methods find approximate
Hessian inverse A-1 to pre-condition the gradient vector and apply the following update minimize
2

---

Under review as a conference paper at ICLR 2022
the loss:
0z+1 = H
In stochastic training, the gradient vector evaluated on a mini-batch input S S X' namely gt VoL(0,, St). If f-1 is the identity matrix, the update above reduces to SGD, whereas H H-1 diagonal matrix, it reduces to adaptive training algorithms such as Adagrad (Duchi et al. (011] Adam (Kingma & Ba 2014). However, to incorporate more curvature information in the optimization process, it often requires approximating H with a full symmetric matrix.
A prime challenge in QN methods is the evaluation of H and in particular its inverse. To address this Fletcher Goldfarb Shanno (BFGS) algorithm has been proposed.
challenge the well-known Broyden -eeycher BFGS approaches the Hessian inverse minimization problem:
i
S.L. 1-1 yk = Sk: 1- is symmetric,
min
where 8%
0g 0:-1 - denotes the parameter changes, and yv gh - -k-1 the gradient changes in Knowing fr from the previous update, the current f- is obtained
two consecutive updates via:
UpdateHessian: Å = pw.) (1 p + 8
(2)
where A Vi Therefore, - is constructed in an iterative manner without explicitly computing the Hessian itself. Given such update rule, methods such Greedy BFGS (Rodomanov & Nesterov 2021 show 11 can converge the real Hessian at linear rate.
In real-world problems, 0 usually consists of millions of parameters. As a result, it is infeasible to store the whole H matrix with O(10 2) memory cost. To reduce memory footprint and simplify computation, f-1 in BFGS is stored in the form of sequence of history vectors {y:) and {s;}. By exploiting the Hessian update formula equation 2 the matrix-vector product H, 9t necessary to pre-condition the gradient can be replaced by sequence of fast rector-vector products shown in Algorithm I Furthermore, limit memory and compute costs, a limited-memory memory version of BFGS, L-BFGS (Nocedal 1980) is proposed that only uses the latest M history vectors when approximating Hessian inverse.
Algorithm 1 Hessian-Vectoe in L-BFGS
Input: gr. MM :
{
Output: 9t
1: for 0,... M do
2:
Pi = yi
3: for = 0.... M. do
4:
0;
19
3 Loss
Optimal
5: gt = gi 0; YM -M----1
Exact Newton
6: 9: = Ho 1 9t Ho1
Naive BPGS
Vi WM-1
BFGS with momentum
7: for = 0, ... M- do
8, y 9
8:
9: gi St + (O-M-i-1 Bi)
P:
Figure Optimization using SGD, Naive BFGS, BFGS with momentum and Exact Newton.
SLIM-QN
While BFGS achieves faster convergence compared to GD in full-batch training, it still suffers convergence instability in the stochastic setting, especially for large-scale DNNs. Specifically. Naive BFGS, which simply uses parameter 0, and gradients gi each iteration caleulate 8 and yk. suffers from severe instability due to stochastic noise introduced by mini-batch training (See the
1"h" rather than "t" is used in the equation as parameter/gradient used might be different from the one in cquation T

---

Under review as a conference paper at ICLR 2022
Table 1: and yv for Naive BFGS and for BFGS with momentum for L = ||@
Naive BFGS
BFGS with momentum
8k
0k+1 0F
(1 (1) 0k) 0₂) + +(1+111 [2) - n2))
yk
0
0₂ + (n n2))
(0xx1
RV
20
(1- 22222
Ur -Ok
0k 1 0x
ablation study in Sec. 5.2). To stabilize the optimization, common solution is to use separate large batch data when estimating 8; and yv (Moritz al. 2016 Chang et al. 2019) in order to reduce stochastic noise. However, this dramatically increases the computation cost and negates performance gains in wall-clock time.
In order to reduce variance in 11-1 without incurring such expensive additional computation as in (Moritz et al. 2016) Chang al., 2019), propose novel Neusi-NNeton method, SLIM-QN which introduces momentum and damping to the Hessian updates. In SLIM-QN, we first obtain the momentum of and gr. from which subsequently derive parameter and gradient changes 8& and yk- To guarantee positive definiteness of Ø-1, we further introduce adaptive damping into the update of yk- With the momentumized and damped parameter and gradient changes, we can construct consistent A throughout the whole optimization process.
3.1 INTRODUCE MOMENTUM INTO THE HESSIAN UPDATE
Inspired by the success momentum in first-order methods, we demonstrate that the Hessian update in L-BFGS can be stabilized via momentum, without requiring large batch size or even full gradients to reduce stochastic noise. In particular, in this paper we apply momentum Ma, Mg. to past parameters 0, and gradients 9, during mini-batch training as follows:
0 Ma. 31 MM. + +1-13)00.
M g: = 32 MM + (1 32)9..
where 31 and 32 are the momentum coefficients for 0, and ge respectively.
Assuming that 11 11 is updated for every mini-batch iterations, 8% and gr are obtained as
8 Mo -Moz>
yk- =M- MM
This simple but effective technique works surprisingly well when gradients are noisy. To intuitively show improvements of BFGS with momentum over the naive version, we compare the stochastic optimization of simple quadratic loss function, L ||0|2 In stochastic training, write gradients each mini-batch iteration as g: = 02 + n4, where n, denotes the stochastic noise. For the sake of simplicity, model the noise i.i.d. Gaussian, that is n, ~ (0,00))
Table I lists the expression for 8ę and yı for naive BFGS and for BFGS with momentum terms and the stochastic noise. We compare the stability of yı in the two algorithms via their element- wiss Var (J)) where (j) denotes the jth element of yk. As shown Table relative variance RV, B(yx(f))
it is casy to observe that, RV mom.. using momentum is much lower than RV in naive BFGS. Hence, given a large momentum, SLIM-QN can significantly suppress noise and obtain a more consistent yı.- With less noise in yk. BFGS with momentum leads better approximation of the real Hessian. Figure S visualizes the optimization trajectory for SGD, naive BFGS, BFGS with momentum and the exact Newton method. With the initialization, BFGS with momentum is as fast as the exact Newton method, and almost twice faster than SGD. On the other hand, naive BFGS has difficulties finding the right optimization path due the noise in yk-
3.2 GUARANTEE POSITIVE DEFINITENESS OF THE HESSIAN VIA DAMPING
Even though adding momentum stabilizes the Hessian inverse, it cannot guarantee that the ap- proximated Hessian is always positive definite, especially in practical stochastic and non-convex optimization. As analysed in 5.2 negative very small positive values in the Hessian spectrum
4

---

Under review as a conference paper at ICLR 2022
harmful, and they immediately derail the optimization. To effectively prevent radical changes in the Hessian, SLIM-QU QN further introduces an adaptive damping mechanism to the Hessian update.
Positive definiteness of the Hessian hinges stable and smooth gradient change vectors {z, J. especially in non-convex and stochastic settings. Hence, we choose to dampen y; by
T. ys + - . Si,
(3)
where yJ is the damped version of yı and r is calculated as
min 1-7L TO) 1-n min n To) 70
4 <1
# oH >
(4)
otherwise
.. where af a and H are the lower and upper thresholds for restraining eigenvalues in Ā-1 and T0 < 1 a constant coefficient.
The above damping scheme prevents sudden changes of s y:, and guarantees the smoothness of f- Equivalently, equation can be considered as scaling the undamped H and adaptively shifting its spectrum by a positive constant: - + (1 --- -r) J. As result, the eigenvalues of H are well controlled.
3.3 THE OVERALL DESCRIPTION
With momentum and damping introduced above, in this section present the complete SLIM- QN algorithm. As shown in Algorithm [ for each mini-batch iteration, we use Ma, and Mg. to accumulate momentum of parameters and gradients. For every L iterations, yk. apply damping, and then update the Hessian approximation. Note that in UpdateHessian the inverse Hessian never explicitly computed, instead we only compute and store the history vectors 8% and ÿt that are necessary to perform the pre-conditioning step. Since at the first 2L iterations, A is not ready yet. we use SGD to conduct a warmup training. After 2L iterations, we use H to first pre-condition gradients 9: and then apply updates to 0. Unlike KFAC. SLIM- QN is compatible to various regularizers such as 1.2 and gradient regularization(Smin can derive gradients from them. Finally, we add momentum to the parameter update A0, after pre-conditioning following the same procedure as in SGD with momentum (which is omitted in Algorithm
compute 8І and
et al. (021), long as we
Algorithm 2 SLIM- -N algorithm
for t 1,... mer iter do
2: Randomly choose mini-batch input S; E X
3: Compute gradients g: given (((Foraard/accwwrrd)
4: Add weight decay: 9: gt + wd O,
5:
Compute momentum on 0: Ma. = 31 -M + +11 (1-1111 -1)--0 O,
MM, = 0
6:
Compute momentum g: Mg. B2 -M MMg.1 +
+(1- (1- B2) g:
.Mg 90
7:
i <
2L then
8:
Warmup: 0,+1 0. 17: 9:
9:
else
Pre-condition: 20, म g:
Algorithm 1
11:
Update: 0z-1 = 0, A0,
12:
if t%L = 0 and t L then
13:
+
14:
8: 8; MMa -Mo-r.
15:
y: yı = -Mg - -Mg
16:
Damping: ÿ) y (1 .88
from equation
n- H. UpdateHessian/ (H Sk. 9t)
> equation not explicitly computed
5

---

Under review as a conference paper at ICLR 2022
4 THEORETICAL GUARANTEES FOR SLIM-QN
In this section, first present convergence guarantees for SLIM-QN, and then discuss the compute and memory costs for SGD, KFAC, and SLIM-QN.
4.1 CONVERGENCE GUARANTEES
Following the framework of quasi-Newton method in Wang et al. (2017) in stochastic optimization, prove that SLIM-QN converges to the optimum at linear rate, under proper assumptions as follows:
AS 1. (()) is X-PL in that it satisfies Polyak-Lojasiewiez (PL) condition for a constant À > 0:
[V 2 XC()).
AS 2. (,(0) is A-smooth for Sis N. 0: 40,, 02 (02) S (2(0)) (V);(0)), 02 01)
2 |02 01112
AS 3. For every sequence 02, 02. ... such that lim, ((0,) then for all usic sish N. lim; (0,) 0
We note that compared typical strong convexity assumptions the PI. condition in AS PPolykk 1963) applies to much broader settings including when the loss is nonconvex as it only requires lower bounded variance in gradients, rather than strict positive definiteness required for the Hessian with strong convexity. AS 3 assumes that the global minima of the summands & are the same as the global minima of their sum. This is in line with what has been observed in over- wer-parameterized deep learning models (Ma et al. 2018).
Before we state our main result we require several auxiliary lemmas. First Lemma states that sf y always lies in [0L,0H] s 8,- With Lemma i place, in Lemma 2 we bound the approximation of the Hessian Hr at kth Hessian update. Lemma 3 further establishes smoothness on L()) given each Ea is smooth. While Lemma further bounds gradient variance in mini-batch training.
Lemma 1. Given damping scheme in equation OL S $
if we choose according equation
4 then
SH..
Lemma 2. Given Lemmal at the k-th Hessian update, H during the optimization is bounded by
L. El (1,1 EI, where = (M + 1) oz. and & on or. and ah is the lower and upper bound for o² in Lemma -
Lemma 3. Assume AS holds, then loss function (()) is at least A-smooth.
Lemma 4. Assume AS 23 holds, with Lemma 3 at iteration with mini-batch input S., where each sample is randomly sampled from X with replacement, gradient V VL(0,; St) satisfies
Es, Es. 2A 2((.)
With ft,"' and gradient variance bounded, we can derive the following convergence theorem.
Theorem 1. Assume AS hold each iteration of SLIM-QN with mini-batch input S, where each sample is randomly sampled from X with replacement, then the expectation of [(0:) satisfies
Es, S
where 04-1 = 1 17 + A
Proofs for the lemmas and theorem are provided in the appendix.
Remark 1. By choosing Th-1 that ar-1 < 1, SLIM-QN converges at linear rate.
Remark 2. We note that Theorem D also applies convex settings, strong convexity implies IV (()) is lower bounded by ((0) for appropriate X >> 0 and hence AS) holds.

---

Under review as a conference paper at ICLR 2022
Table 2: Computations and Memory in SGD, KFAC, and SLIM-QN
SGD
KFAC
sL-BFGS
SLIM-QN
Computation
Fwd&Bwd
a1 [0] 1b0 + (d)
( |0.11
02 ||0|| + 28C + J.by
&CB. + 03 |@||
Opt
Okg ||@||
Og
|011 + 2 (d) + d
Oo [10]] + 2M [|0]
og ||@|| 2M [|0]
Memory
Fwd&Bwd
bMn
bM + 81 ||0|| Bu |||||
bM + 82 |101| + bby
6M + 8g |@||| Bu ||0|| + 2M ||0||
Opt
& ||0||
+ 2 (dp + (2)))
6. 00 + 2M [|0]
d; input dim in layer i. b: batch size. b batch size for the Hessian approx. |0:1]: #params in layer i.
4.2
COMPUTE AND MEMORY COST
As mentioned before, SLIM-QN aims to reduce the complexity of approximating the Hessian. In this section, we summarize the compute and memory cost of SGD, KFAC, stochastic L-BFGS (sL-BFGS) CrhianssChargg ct al. 2019) and SLIM-QN, and demonstrate the cost advantage of SLIM-QN.
Given a model with parameter 0, we use Cß and Mp represent the compute and memory cost of a forward/backwart (Fwd/Bwd) pass with a batch size of b = 1. Furthermore, Copt denotes the compute cost of model updates (Opt) which consists of gradient reduction, computing the update A0, and applying it to 0.
Table 2 summarizes the compute and memory cost of SGD, KFAC, sL.-BFGS and SLIM-QN. Compared to SGD, during the forward and backward passes, SLIM-QN needs to additionally compute Mø. MMg. for which the complexity increases linearly with model size (a2 ||]]). The main extra compute SLIM-QN introduces is the Hessian-vectus product, in which we need to iterate over { i=1 and J as shown in Algorithm 1 The complexity increases linearly with the number of stored history vectors and model size (2M [T While, compared to (bCr)) complexity in forward and backward pass, such operations add relatively marginal cost.
As a comparison, KFAC though only approximates diagonal blocks of the Fisher matrix, it still adds significant additional computations through I) multiple backward passes to update factors (y6Cib (d + [1e:Il ))) for every L iterations, and 3) Matrix-vector
with 7 2 1), 2) matrix inversion
products (2 (d, + I1@:ll) [[@+]].. If the Fisher matrix is updated more frequently (that is for small L), then the amortized cost for matrix inversion is even more striking. On the other hand, sL-BFGS also resorts to computation-intensivv operations including full-batch gradients and separate large batch to estimate the Hessian, which respectively adds amortized costs of O(bC))) and 7. bb
di
As for memory usage, compared to SGD, SLIM-QN mainly needs O [[0l) store history vectors { and ( sL-BFGS needs the same storage for 8; Ui and amortized cost of bn Mn) for additional backward passes. While KFAC needs ( (af + (10e1l)))) to store mab-matricss and their inverse, where the actual memory footprint hinges on model architectures. In practice, M set to be 10 20, which ensures that memory usage is manageable in SLIM-QN.
EMPIRICAL ANALYSES
We conduct various experiments on computer vision (CV) problems, where SGD has been widely used. Methods like Adam (Kingma& & Ba 2014) and AdaGrad (Duchi et al. 2011) greatly under-perform SGD (Defazio Jelassi 2021). ). Two metrics are used to evaluate the performance: iteration-wise convergence and wall-clock convergence. The iteration wise metric shows the pure convergence promises of the optimizer; while the wall-clock convergence further captures the impacts of computa- tion complexity the run-time. Furthermore, we also conduct ablation study that investigates how the components in SLIM-QN (momentum and damping) affect the optimization process.
The current implementation in PyTorch (Paszke et al.) 2019) supports various DNN models in multi-GPU system. During training, after gradients are synchronized across GPUs, we keep updating the momentum, Mo, and Mg. on each GPU. As result, each GPU stores copy of the Hessian
7

---

Under review as a conference paper at ICLR 2022
SGD KFAU
Trining loss
Valicution aoc
60
SLIM-ON 75.95
2006
414cc
S002
20
100
Derations
Epochs
Validation acc (%6
Trining loss
40
Time
limo(hs)
Figure 2: Training loss (left) and validation accuracy (right) of SLIM-QN, KFAC and SGD on ImageNet using ResNet-50 model. The model trained with SLIM-QN benefits from faster early-stage convergence and achieve comparable generalization performance SGD, We plot the mean and standard error over runs with different random seeds.
inverse and locally performs gradient conditioning without communicating across GPUs. We test models: ResNer18, ResNet50, Vision Transformer on datasets: CIFAR- 10 Krizhiyyyy et al. 2009) and ImageNet(Deng et al. 2009). We also run SGD and KFAC as two baselines for comparison.
5.1 EXPERIMENTS ON IMAGENET CLASSIFICATION
ImageNet classification has been the gold standard for evaluating performance of different optimiza- tion algorithms for CV models. Compared to CIFAR-10, ImageNet consists of much more training and test images (~~ I. .2M training and ~50K test images), categorized into 1000 classes. Therefore, convergence on ImageNet can better reveal the optimizer's 's promises in practical problems.
During data pre-processing, resize images 256 256, and randomly crop 224 224, and then randomly flip each image. Each image is normalized using pre-computed mean and variance.
5.1.1
RESNET-50
Figure shows iteration-wise (Top) and wall-clock (Bottom) convergence ResNet-50 using SGD, KFAC and SLIM-QN. Detailed hyper-parameter settings are provided in the appendix. SLIM-QN enjoys very fast per-iteration convergence, and reaches near optimal accuracy 1.5x faster than SGD, and even 2 faster in the early-stages. Furthermore, it also generalizes well on the validation set, and finally reaches comparable validation accuracy to SGD.
The benefit of SLIM-QN is even more striking in terms of wall-clock time. Due to light compute costs, it is 1.75 x /1.36 faster in the early and late stages compared to SGD. Whereas in KFAC, the wall-clock performance is significantly neutralized by its additional compute costs.
5.1.2 VISION TRANSFORMER
As step towards understanding the efficacy of second-order optimizers on contemporary Transformer- based CV models, we perform experiments on small (10M parameters) Vision Transformer (ViT) (Dosovitskiy al. 2020b) using SLIM-QN on ImageNet. Details on hyperparameters, model architecture and experiments on further datasets are deferred to the Appendix.
As shown in Fig. SLIM- QN benefits from faster early-stage convergence compared the SGD, which is consistent with our findings for ResNet. Furthermore, we observe that SLIM-QN finds solution with good generalization achieving final validation accuracy slightly higher than SGD.
5.2 ABLATION STUDY: THE EFFECTS OF MOMENTUM AND DAMPING
In this section, we give more insight into the effects momentum and damping used in SLIM-QN, To this end, ablate two critical components in SLIM-QN: momentum and damping in the Hessian
8

---

Under review as a conference paper at ICLR 2022
SLIM QN
(35
NalileSion 6x:
9GD 20J
SLI GNNSURT B3RS
115
Ioorations
Epoclo
Vallia ANC 1962
Time (h)
Figure 3: Training loss (left) and validation accuracy (right) of SLIM-QN and SGD on ImageNet using Vision Transformer model. The model trained with SLIM-QN benefits from faster early-stage convergence and achieve better generalization performance compared to SGD. We plot the mean and standard error over runs with different random seeds.
16'
Tmining
10"
with
damping
with only momeutum
30
with only damping
with no mocacutum or damping
Decntions
Validation
60
Abuvemal cigencaluzs the Hossion
Diverges casily
Large
110
150
350
Epochs
Figure Ablation analysis for SLIM- QN on ResNet-I8/CIFAR (batch size: 256).
approximation, and then use the ablated version to train ResNet-18 18 on CIFAR-10. We focus on CIFAR-10 since we observed more convergence instability on this dataset compared to others.
Figure shows convergence using the ablated SLIM-QN with only momentum (black), with only damping (purple), and with no momentum or damping (red). Due stochastic noise, the ablated version of SLIM-QN without momentum damping diverges easily in the early stages. With momentum (black), the whole optimization is significantly stabilized. However, it still fails to converge when there is abrupt change in the loss landscape (for example, when learning rate decays). With damping (purple), the Hessian approximation is effectively restrained, especially when such sudden changes in the loss landscape happen. It is interesting to observe that while damping prevents divergence, the whole training is still largely affected by stochastic noise. Notable fluctuation in the loss and accuracy is commonly observed during training. As comparison, the complete SLIM-QN (blue) effectively addresses these issues achieving much more stable convergence.
6 CONCLUSION
In this paper, propose SLIM-QN, quasi-Newton method that simultaneously mitigates computa- tion and convergence instability barriers in second-orde -odder methods. SLIM-QN introduces momentum and damping into the Hessian update, which obviates the need for estimating the Hessian with high costs. Empirical analyses on CV models, such as ResNet-50 and Vision Transformer show that SLIM-QN achieves faster convergence in the early stages, and reaches comparable accuracy SGD.

---

Under review as a conference paper at ICLR 2022
REPRODUCIBILITY STATEMENT
Implementation of SLIM-QN in a multi-GPU platform is described at the beginning of Sec S copy of code is included in supplementary materials. Appendix lists all hyperparameters for obtaining results on ImageNet using ResNet-50 and ViT models. Moreover, Appendix C presents more results on CIFAR- 10 using ResNet- 18 and ViT models. We also describe some tips of tuning hyperparameters in Appendix F
A
For theoretical results, proofs of all lemmas and theorems are provided in Appendix
REFERENCES
Jimmy Ba, Roger Grosse, and James Martens. Distributed second-order optimization using kronecker- factored approximations. 2016.
Daqing Chang, Shiliang Sun, and Changshui Zhang, An accelerated linearly convergent stochastic I-bfgs algorithm. IEEE transactions on neural networks and learning systems, 30(1 (WM11))3338-33 3346, 2019.
Aaron Defazio and Samy Jelassi. Adaptivity without compromise: momentumized, adaptive, dual averaged gradient method for stochastic optimization. arXiv preprint arXiv:2101.11075 2021.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pp. Icee, 2009.
Jacob Devlin, Ming-Wa Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.04880 2018.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. image is worth 16x16 words: Transformers for image recognition at scale. arXiv preprint arXiv:2010. 11929, 2020a.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An image is worth 16x16 words: Transformers for image recognition at scale. arXiv preprins arXiv:2010.I 11999, 2020b.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12(7), 2011.
Roger Fletcher. Practical methods of optimization. John Wiley & Sons, 2013.
Wenbo Gao and Donald Goldfarb. Block bfgs methods. SIAM Journal on Optimization, 28(2): 1205-1231, 2018. 2018.
Wenbo Gao and Donald Goldfarb. Quasi-newton methods: searches for cof-oconcordant functions. Optimization Methods and Software, 34(1):194 217, 2019.
superlinear convergence without line
Donald Goldfarb, Yi Ren, and Achraf Bahamou. Practical quasi-newton methods for training deep neural networks. arXiv preprint 2xXiv:2006.08877 2020.
Robert Gower, Donald Goldfarb, and Peter Richtárik. Stochastic block bfgs: Squeezing more curvature out of data. In International Conference on Machine Learning, pp. 1869-1878, PMLR, 2016.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint arXiv:1412.680 2014.
10

---

Under review as a conference paper at ICLR 2022
Alex Krizhevsky, Geoffrey Hinton, al. Learning multiple layers of features from tiny images. 2009.
Dong C Liu and Jorge Nocedal. On the limited memory bfgs method for large scale optimization. Mathematical programming, 45(1):503-528 1989.
Siyuan Ma, Raef Bassily, and Mikhail Belkin. The power of interpolation: Understanding the effectiveness of sgd in modern wer-paaametrized learning. International Conference on PMLR, 2018.
Machine Learning, pp.
James Martens and Reger Grosse. Optimizing neural networks with kronecker-factored approximate curvature. In International conference on machine learning, pp. 2408-2417. PMLR, 2015.
Aryan Mokhtari and Alejandro Ribeiro. Global convergence of online limited memory bfgs. The Journal of Machine Learning Research, 16(1 (6(1):311131181, 2015.
Philipp Moritz, Robert Nishihara, and Michael Jordan. A linearly-oovvergett stochastic 1-bfgs algorithm. In Artificial Intelligence and Statistics, pp. 249-255 PMLR, 2016.
Yurii Nesterov, Introductory lectures convex optimization: A basic course, volume 87. Springer Science & Business Media, 2003.
Jorge Nocedal. Updating quasi-newton matrices with limited storage. Mathematics of computation, 35(151):773-78,, 1980.
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, high-performance deep learning library. arXiv preprint 1912v09912.01
2019.
Gregory Pauloski, Zhao Zhang, Lei Huang, Weijia Xu, and Ian T. Foster. Convolutional Neural Network Training with Distributed K-FAC. .. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, SC '20. IEEE Press, 2020. ISBN 9781728199986. doi: 10.5555/3433701..444 33333826.
Boris Teodorovich Polyak. Gradient methods for minimizing functionals. Zhurnal vychislitel noi matematiki matematicheskol fiziii, 3(4):643-653, 1963.
Alec Radford, Karthik Narasimhan, Tim Salimans, and Ilya Sutskever. Improving language under- standing by generative pre-training. 2018.
Samyam Rajbhandari, Jeff Rasley, Olatunji Ruwase, and Yuxiong He. Zero: Memory optimizations
toward training trillion parameter models. In SC20: International Conference for High Performance Computing, Networking. Storage and Analysis, pp- 1-16. IEEE, 2020.
Anton Rodomanov and Yurii Nesterov. Greedy quasi-newton methods with explicit superlinear convergence. SIAM Journal on Optimization, ((():785-811,2027
David Saad. Online algorithms and stochastic approximations. Online Learning, 5:6-3, 1998.
Samuel Smith, Benoit Dherin, David GT Barrett, and Soham De. On the origin of implicit regularization in stochastic gradient descent. arXiv preprint arXiv:2101.1211 2021.
Xiao Wang, Shiqian Ma, Donald Goldfarb, and Wei Liu. Stochastic quasi-newtor methods for nonconvex stochastic optimization. SIAM Journal on Optimization, 27(2):927-956, 2017.
11

---

Under review as a conference paper at ICLR 2022
A PROOFS OF LEMMAS AND THEOREMS
This appendix are organized as follows:
Section A. A.4
presents the proof of Lemma !
2. Section A.5 presents the proof of Theorem
A.1 PROOF OF LEMMA L
Proof. According to equation 3 8 s. = (Ty: +(--))s)))) = (1r+1- s8 8;, where of 3/
For - FT,, two cases need to be considered: 1) = To: 2) 1-11
t = To. then L-Ai 2 To, and μt + σz. If L-a, then put 1 - T = -0
I-p
I-#
Therefore, when oz of Dr 01.888
For ØL < aH
We can write - 1 is easy to show that yog 10-1--0-0------ (1-o))(1--)) >
and PTo + - OH (1 0H (1 To) < O. Therefore, when σr. < μ on, o1.8f 8; < 8 ú: < on 8,.
For μ 2 Øg similarly two cases might arise: 1) r = To: 2) r 2=-1
p-1
If T To, then _x-l 2 To. and μT
0H. I 4-1 then UT + 1 7 oH.
Therefore, when μ 2 THe sf S SHSTS:
8." -i In summary, OL < dH
of-
A.2 PROOF OF LEMMA
2
Proof. Lower bound: Å is initialized as Ho!
26 90 05 yo
I. According Lemma there exists
(0) = onl such that ÿo Ho sn-
Therefore,
-
xo. Hoso Ho (e) H H. Ho HH / ee)
1
(e] H. (H, en)
on
-1.
Then for k > 1, assuming H - ou
1 hold, based equation 2 H = (
8 + 8LaL 8% Uk.
Because (I PLu ( -1aitss)) is positive definite, we can bound Ha² as: A x
SEST a 11
* HH
Therefore, lower bound of मー . on
( H X(H 1/2 80)
Upper bound: Since (0) > aI, get
$ go
. -=
I
Mo 90
(o] H 2 H.H (H!1
oz
Similarly, for à > 1, we assume A_ - k: -
hold.
For the first part in equation
let Q = (1 - prir s Then for V x + 0, x²'
(Qa)²* fr (Qx) < oo
(Q" x.
x
Let P S DraT
UL + then Q=Q==++ 8 Uz
8 9106 ih
12

---

Under review as a conference paper at ICLR 2022
Because P is rank-1 matrix with eigenvalue -1 and eigenvector yr, we have x² QQ QTT x xx + P) x TTx
For the second part in equation 2 we can directly get Therefore, x=' H de
oya k- nn x
AL of Har
1 1 I.
xt x
Oo xT
In SLIM-QN, k at most M, which the length of history vector, therefore E (M + 1)
In summary, 1 оu 3 H (M 1)
A.3 PROOF OF LEMMA 3
Proof. Given AS hold, we have
[V,(0:)) ve,(0:)1 & A A| -22ll-
For C, we have
VC((0)) - Σ ve,(01) - V2,(02)
Then,
(V)()))) - VC(02)I 1
(e((0,) vl((22)
N
TT
[( (
N
A ||0:
021l
N
i=1
10 021
"TT" indicates triangle inequality. Therefore, least A-smooth.
A.4 PROOF OF LEMMA 4
Proof: Es, (.), Es. IVE ((1)) EEL
Expand summation and regroup,
Es, S)1 = Es, bt (E Σ E (V4(0.)) (O,(
Take expectation each sample,
Es. E)) 1 Ea. 1o2 Ei GoaitEEa.c (V (O.) (l,( (()(()))
Because æ; and ær independent, the second part be simplified as,
Es, (1.
[1 + Σh E IV
With further simplification, we get
Es, S. = E'n EL, ( (
13

---

Under review as a conference paper at ICLR 2022
Given AS 2 and Lemma have
[[,,( & 2A ((tr) and | & 2A (()))
Therefore,
1
Ex [2.), + b-1 2AC(O))
Es. 5s.1
(5)
1 2A +
b-1 b-1 2AC(0.)
(6)
b
= 2A L(),)
A.5 PROOF OF THEOREM 1
Proof. Given AS and Lemma (())) can be bounded by L(),) S ((0:-1) + (C 11-1) + A |10: 0,-11 for v0,-1,0 O2
In SLIM-QN, 0. 0111 1/--1 A ( Therefore, we can upper bound [(0.) as:
[(0,) SL(0,-1)
?/-1 VL(0,-1)
A
2
A
[
<L(O 7/-1 VL((0-1) Ar 1
A \((00-1;S
+ 2
Since it is independent with S.-1, we take expectation w.r.t S and S.
Es, Es)((())) SC(O.-1) - 7-- VL(O.-.)) (C
A=
+n
Es (
2
=[(O,-1) - 1/1 "1
AE
+ 2
Es,
2
According AS 1, we have
I(0,-1) [
According to Lemma 4, we have
Es [ 22A((0,)))
Therefore, Es, [C(0))]S:-1] < -n AE
After simply regrouping, we can get
Es.(C(0:))8:-.) i] < (1 9h N
Apply total expectation rule w.r.t S, we have
Es < (1 - 12 [[(
14

---

Under review as a conference paper at ICLR 2022
B SETTINGS FOR MODEL TRAINING ON IMAGENET
B.1 RESNET-50
We train ResNet-50 ImageNet in multi-GPU platform, which has 8 Nvidia Quadro RTX 5000 GPUs. PyTorch (2 1.8) and the Distributed Data Parallel (DDP) communication package is used during training. Table lists hyperparameters used in SGD, KFAC, and SLIM-QN. Initial learning rate is 0.1, decaying by a factor of 10 at 30, 60, 90th epoch. We use a learning warmup for in the first epochs. Batch size is 256. In SLIM-QN, weight decay when conditioning gradients. Therefore a smaller weight decay can achieve as strong regularization as SGD with wd 0.0005. For the Hessian update frequency (L), in SLIM-QN we update the Hessian for every 30 mini-batch iterations; while for KFAC, considering the compute cost, we update the Hessian for every iterations. Lower and upper threshold for restraining eigenvalues in the Hessian (L ah) is set to be (0.01, 1) in all experiments. Initial damping (1 To) is 0.05, We run random seeds for each optimizer.
smaller weight decay (wd) as SLIM-QN considers
then adapted during training according to equation 4
Table 3: Hyperparameters for SGD, KFAC, SLIM-QN on ResNet-500lmaeeNett
Optimizer
Ir
momentum
wd
damping B1/32
L
M
SGD
0.1
0.9
0.0005
KFAC
0.1
0.9
0.0002
0.001 0.05
50
SLIM-QN
0.1
0.9
0,0002
0.9/0.9
30
10
8r/32: momentum for the Hessian; L: frequency for updating the Hcssian; M: length of history vector (8, y)
B.2 VIT
We use a small Vision Transformer model with 6 layers, 8 attention heads, a patch size of 16, and both hidden and MLP dimension of 512 for total of about 10M parameters. We train for 90 epochs with linear learning rate warmup in the first 5 epochs, and decay the learning rate at 80 epochs for SLIM-QN. For SGD, train for 100 epochs, decaying the learning batch size of 1024 is used for both algorithms. We perform 3 runs with different random seeds. Table shows the selected hyperparameters.
30, 60, 90 epochs. A
Table 4: Hyperparameters for SGD and SLIM-QN on ViT/ImageNet
Optimizer
Ir
momentum
wd
damping
81/B2
L
M
SGD 0.1
0.9
0.0001
SLIM-QN
0.1
0.9
0.0
0.01
0.99/0.99
100
20
81/32: momentum for the Hessian; L: frequency for updating the Hessian; M: length of history vector (8, y)
C EXPERIMENTS ON CIFAR-10
C.I RESNET-18
Hyperparameter is shown as in Table Initial learning rate is 0.1, decaying by factor of 10 at 150th epoch. For both SGD and SLIM-QN we used a linear learning rate warmup for epochs. Batch size is 256 for both SGD and SLIM-QN. Figure shows convergence on ResNet-18 18 using SGD and SLIM-QN. On small dataset CIFAR-10, SGD and SLIM-QN both deliver fast convergence at early stages, while SLIM-QN is slightly better. Moreover, SLIM-QN achieves more faster convergence and high validation accuracy at later stages.
C.2 VIT
We use the same ViT model as in the ImageNet experiment, but with patch size of 16. Table 6 shows the hyperparameters used in the CIFAR- 10 experiments. For both SGD and SLIM-QN we used linear learning rate warmup for 5 epochs. We perform runs with different random seeds.
15

---

Under review as a conference paper at ICLR 2022
Table 5: Hyperparameters for SGD, SLIM-QN on ResNet-
Optimizer
Ir
momentum
wd
damping
81/32
M
SGD
0.1
0.9
0.0005
SLIM-QN
0.1
0.9
0.0005
0.05
0.9/0.9
100
10
8r/32 momentum the Hessian; frequency for updating the Hessian; M: length of history vector (8, y
1.00
Validation aoc.(%))
Training
0.10
SGD
SGD:94.2%....6
SLIM-QN
SLIM: 94.6%
0.01
10k
ZIkk
40k
200
lterations
Epochs
Figure 5: Convergence on ResNet-18/CIFAL using SGD and SLIM-QN.
We use a batch size of 1024 and train for 90 epochs and decay the learning rate by factor of 10 at 100 epochs for SLIM-QN. We train for 150 epochs and decay the learning Experimental results on CIFAR- 10 using Vision Transformer are depicted in Fig. 6 We observe that SLIM-QN converges
140 epochs for SGD.
solution with better generalization than SGD and in overall less iterations.
On small datasets such as CIFAR-10 10 we do not observe significant early-stage speedup on ViT, which consistent with ResNet- MOANNe--1//CA 8/CIFARRRIIII 10 experiments. Moreover, VIT is better suited for large-scale vision datasets due to the weaker implicit bias resulting from the non-convolutional architecture.
SGD
SLIM-QN
Thining loss
Vidislation
100
SGDa 1536 D118
SLD4 Q2.22.0% 1010
0.1
L.kk
2.4g
3.6%
4.8%
20
60
50
100
12n
140
Torrations
Fgocles
Figure 6: Convergence on ViT/CIFAR-10 using SGD and SLIM-QN.
Table Hyperparameters for SGD, SLIM-QN on ViT/CIFAR-10 with batch size 1024
Optimizer
momentum
wd
damping
B1/32
SGD
0.1
0.9
0.0001
SLIM-QN
0.025
0.9
0.0001
0.01
0.99/0.99
100
10
01/32: momentum for the Hessian; L: frequency for updating the Hessian; M: length of history vector (8, y)
D STOCHASTIC TRAINING USING THE CLASSICAL L-BFGS
In this section, demonstrate that the classical L-BFGS suffers convergence instability in stochastic training, even using large batch sizes. We train ResNet-18 on CIFAR-10, and vary batch size from 64 to 2048. Learning rate decays from 1 to 0.001 in 100 epochs. Weight decay is 0.0005. The Hessian approximation is updated using the L-BFGS formula for every 50 iterations, with most 10 history vectors.
Fig. shows training accuracy w.r.t iterations (log scale). We can observe that L-BFGS fails to converge under various batch sizes. Training using large batches though is little more stable than small ones at the beginning, still diverges due to stochastic noises sudden changes in loss landscape. Therefore, large batch only is not sufficient solution to address convergence instability in the classical L.BB.SS.
16

---

Under review as a conference paper at ICLR 2022
batch size:
80
batch size: 128
batch size: 256
butch
60
batch size: 1024
Accuracy (%)
batch size: 2048
40
20
100
Iterations (K)
Figure 7: Convergence on using the classical BFGS.
Backward pass
Backward pass
Loss
0 .
0
2/8
0
SL.M-QN s 1.
SLIM-QN 2/a 2/2/2
layer
2nd/3rd layer
0
0
Update model
Update model
Figure 8: Block-wise SLIM-QN for distributed systems. Models divided into blocks, which then optimized by SLIM-QN in multiple nodes.
E SLIM-QN IN DISTRIBUTED SYSTEMS
As mentioned in Sec. 4.2 SLIM-QN requires O(2M ||0 storage to store required history statistics 8y and yı.- When training models using data parallelism, each node further needs store the whole copy of these history vectors. Such high memory footprints make it difficult to be used to train very large models such as BERT and GPT (Devlin al. 2018 Radford et al. 2018). To address such limitation, we propose a block-wise SLIM-QN which is much more memory-efficiet in distributed systems.
As shown in Fig. 8 for a neural network, we divide model parameters into multiple blocks, where each block might consist one or more layers. During training, these blocks are optimized in parallel using independent SLIM-QN optimizers. In distributed system, each compute node can conduct optimization on one or more blocks, depending on its capabilities. Furthermore, the model can be divided in way such that each node can store the required statistics sy and yı for at least one block. Combining with ZeRO data parallelism design (Rajbhandari et al.) 2022)), block-wise SLIM-QN are capable of training very large models long there enough compute nodes.
17

---

Under review as a conference paper at ICLR 2022
1.7
SGD
1.5
SLIM QN
blockowise SLIM-QN
SGD:942N::2016
0.4
SLTM 94 06.00%000005
0.3
block-wise SLIM: 94.4%
lentioza
Figure 9: Convergence on ResNet- 18/CIIAR-/IIIRRI using SGD, SLIM-QN, and wise SLIM-QN
E.I CONVERGENCE GUARANTEES
In this section, we prove that bioek-wise SLIM-QN also converges in a linear rate given assumption in Sec. 4.1 Furthermore, the convergence property guaranteed in any arbitrary way of dividing models.
Theorem 2. Assume VS hold at each iteration of block-wise SLIM-QN with mini-batch input Sr, and the k-th Hessian update for block ili 1.... .P), B (B H1 during the optimization bounded by Edl B 3 EgI, then the expectation of [(O,) satisfies
Es. [c(())) S -,
where 04-1 = T1- 11 + n A min & E = max 3
Proof. The bound of B for block i is guaranteed by SLIM-QN. Then according to the proof in Theorem I if we can prove 11,11 diag(B,, (B) B2.... BB) is also bounded, then we can show block-wise SLIM-QN converges in a linear rate.
For any arbitrary vector a + O. xT HE x can be written as
(x.². B,.... "."""""""""
xp"" Bp) (at",
x²" )== Ei= x.t" B, x''
where x' is sub-vector corresponding to block i.
Let ç = min & and =-t max E,, therefore, S aT A S.
Following the same proof as in Theorem
block-wise SLIM-QN also converges in linear rate.
L
E.2 EMPIRICAL ANALYSES
We evaluate block-wise SLIM- QN on ResNet-18/CIFAN 10E.11//CIFRRRIA 10 using 5 random seeds. Layers in ResBlock are grouped into one block. Initial learning rate is 0. decaying by a factor of 10 at 1 50th epoch. We used a linear learning rate warmup for 5 epochs. Batch size is 256 for all runs. Table 7 list detailed hyper parameters settings. As shown Fig. 9 block-wise SLIM-QN achieves even slightly faster convergence performance as SLIM-QN. Both SLIM-QN and the block-wise version achieve higher validation accuracy compared to SGD.
Due to the limited time, we have not completed experiments on large models/datasets. We will add that in the future.
Table Hyperparameters for SGD, SLIM-QN and block-wise SLIM-QN on BesNet-I8/CIFAL
Optimizer
br
momentum
wd
damping
81/32
L
M
block-wise SLIM-ON 0.1
0.9
0.0003
0.01
0.9/0.9
50
10
8 /B: momentum for the Hessian: L: frequency for updating the Hessian; M: length of history vector (s, y)
18

---

Under review as a conference paper at ICLR 2022
F HYPERPARAMETER TUNING
SLIM-QN involves additional hyperparameters besides common parameters in SGD: learning rate, momentum, and weight decay. While tuning the hyperparameters is not huge burden since some parameters are fixed in all the experiments, such as lower and upper threshold for restraining eigenvalues in the Hessian: LL, HH, and length of history vectors: M. For the rest of parameters: damping (To), momentum (81, 52) and update frequency (L) for the Hessian, it is easy to conduct a grid search on small models and datasets, explore how these parameters affect optimization, then apply them to large-scale model training. For example, after training on CIFAR-10 10, we found that small improves generalization performance, and large damping stabilizes optimization but causes optimizer to behave like SGD. With these notions, is easy to tune these parameters, and then achieve optimal convergence performance and accuracy.
19


Reviews:
[{"review_id": "vWjM8JCtQN9", "reviewer": "Reviewer_bMXz", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "Strengths\n- 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).\n- 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.\n\nWeaknesses\n- The motivation of applying L-BFGS to small-batch training is not convincing.\n    - 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? \n    - 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. \n    - 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. \n    - 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]).\n- Parts of the discussion of the pros and cons of K-FAC and SLIM-QN (L-BFGS) are not appropriate.\n    - 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.\n    - 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.\n    - 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).\n- SLIM-QN’s practical usefulness is still questionable.\n    - 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. \n\nOther comments\n- 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.\n\nReferences\n- [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.\n- [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.\n- [3] T. B. Brown et al. Language Models are Few-Shot Learners. https://arxiv.org/abs/2005.14165, 2020.\n- [4] K. Osawa et al. Scalable and Practical Natural Gradient for Large-Scale Deep Learning. https://arxiv.org/abs/2002.06015, 2020.\n- [5] I. Loshchilov and F. Hutter. Decoupled Weight Decay Regularization. https://arxiv.org/abs/1711.05101, 2019.\n- [6] G. Zhang et al. Three Mechanisms of Weight Decay Regularization. https://arxiv.org/abs/1810.12281, 2018.\n", "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.", "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. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "uLawUEBZZY", "reviewer": "Reviewer_EjsS", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "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_paper": "\nIn 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).\nConveregence   results are provided in a stochastic setting. Numerical evaluations on real data  shown the advantage of in terms of  speed and accuracy. ", "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 ？\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "kTnugTGDcxY", "reviewer": "Reviewer_TATQ", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "\n### Strengths\n1. The paper is well-written and easy to follow.\n2. The proposed SLIM-QN has some computational and memory advantages.\n\n\n### Concerns\n1. 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. \n2. AS1 and AS3 are very strong assumptions.\n3. 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_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.", "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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "LZzYmaWAy5M", "reviewer": "Reviewer_aBmG", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "The paper is easy to follow and addresses an important problem. However, I have some major concerns about the assumptions and theoretical results.\n\n1- 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.\n\n2- 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.\n\n3- 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. \n\n4- 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.\n\n5- 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_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.", "summary_of_the_review": "Overall, I think the required assumptions are strong and the theoretical results are not significant. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "1-lhe_QIJ0", "reviewer": "Reviewer_doqb", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "The idea of combining momentum with L-BFGS has been explored before, e.g. in Chang et al \"An Accelerated Linearly Convergent\nStochastic 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.\n\nIn 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?\n\nThe 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_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.\n\nThe 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.\n\nThe 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.", "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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

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