Better SGD using Second-order Momentum
Authors: Hoang Tran
Ashok Cutkosky
Venue: NeurIPS 2022 Accept (2022)
Keywords: second-order optimization
non-convex
hessian
sgd
optimal convergence rate

Abstract:  We develop a new algorithm for non-convex stochastic optimization that finds an $\epsilon$-critical point in the optimal $O(\epsilon^{-3})$ stochastic gradient and Hessian-vector product computations. Our algorithm uses Hessian-vector products to "correct'' a bias term in the momentum of SGD with momentum. This leads to better gradient estimates in a manner analogous to variance reduction methods. In contrast to prior work, we do not require excessively large batch sizes and are able to provide an adaptive algorithm whose convergence rate automatically improves with decreasing variance in the gradient estimates. We validate our results on a variety of large-scale deep learning architectures and benchmarks tasks.

Better SGD using Second-order Momentum
Hoang Tran Boston University tranhp@bu. edu
Ashok Cutkosky Boston University ashok@cutkosky.com com
Abstract
We develop new algorithm for non-convex stochastic optimization that finds 6-critical point in the optimal Oc--a) stochastic gradient and Hessian-vector product computations. Our algorithm uses Hessian-vector products to "correct" a bias term in the momentum of SGD with momentum. This leads to better gradient estimates in manner analogous to variance reduction methods. In contrast to prior work, we do not require excessively large batch sizes, and able to provide an adaptive algorithm whose convergence rate automatically improves with decreasing variance in the gradient estimates. We validate our results variety of large-scale deep learning architectures and benchmarks tasks.
Introduction
In the last couple of decades, first-order algorithms such as Stochastic Gradient Descent (SGD) or Adam [Kingma and Ba 2014) have emerged the main workhorse for modern Machine Learning (ML) tasks. They achieve good empirical results while being easy to implement and requiring relatively few computational resources. When the objective function is convex, SGD's convergence well-understood [Zinkevich] 2003). However, the results are much less favorable for the non-convex setting in which modern deep learning models operate. In fact, the problem of optimizing non-convex function is NP-hard in general, so instead analysis often focuses on finding a critical point - that is, a point at which the gradient of the loss is zero. SGD is well-known to find c-approximate critical point in at most ((e=t) !) total stochastic gradient evaluations (Ghadimi and Lan 2013). In an effort to improve upon SGD, many different algorithms and heuristics have been proposed, including various advanced learning rate schedules [Loshchilov and Hutter 2016 Goyal et al. 2017 Xie et al. 22020]
or per-coordinate learning rates and adaptive algorithms Duuchi et al.) 2011 McMahan and Streeter 2010 Kingma and Ba 2014, Reddi et al. 2018). All of these methods have enjoyed practical success, but none of their convergence rates has shown any asymptotic benefit over the O rate SGD, which is to be expected because this rate is in fact optimal in the worst-case for first-order methods operating on smooth losses (Arjevani et al. 2019 Thus, order make improved algorithms, we need additional assumptions. In this work, we consider the case in which our algorithm is not pure first-order method, but has some limited access to second-order information.
Second-order algorithms such as Newton's 's method are among the most powerful methods in opti- mization theory. Instead of using a linear approximation for the objective via the gradient, Newton's method employs a quadratic approximation using both the gradient and the Hessian. This quadratic approximation hugs the curvature of the error surface and allows each iteration make much faster progress. Unfortunately, second-or implement. The cost forming the Hessian matrix (dd²) and the cost of a Newton step is typically (dd)), thus rendering such algorithms largely impractical for large-scale learning problems [Bottou] and Bousquet 2007].
algorithms are also much more complex and expensive to
The good news is we may not have to explicitly compute the Hessian matrix to be able to take advantages of the nice properties of second-order methods. In particular, is possible to compute a Hessian-vector product, that is a vector of the form F(r(e for arbitrary r and v, in roughly
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

the same time it takes to evaluate (z(x) [Pearlmutter, 1994]. In this paper, we develop novel second-order SGD-based algorithm that uses a stochastic gradient and Hessian-vector product oracle to expedite the training process. Our algorithm not only enjoys optimal theoretical properties, it also practically effective, as demonstrated through our experimental results across various deep learning tasks. Importantly, our method works well on variety of tasks in different domains, while standard practice is to employ different optimizers for different domains (e.g. AdamW for NLP, SGD for computer vision).
1.1 Contributions
We present novel algorithm based on SGD with momentum (SGDHess) that uses Hessian-vector products to "correct" a bias term the momentum. Through our theoretical analysis, we show that algorithm requires the optimal O(E-3) oracle calls for finding stationary points [Arjevani et al. 2020b]. In contrast to previous algorithms with this property (c.g. [Arjevani et al. (0200b), ). we do not require excessively large batch sizes, and we also feel that our algorithm and analysis is relatively more straightforward: our method is a simple modification to SGD that could easily be applied to any momentum- baasd optimizer.
also provide a variant of our algorithm based on normalized SGD, which dispenses with a Lipschitz assumption on the objective, and another variant with an adaptive learning rate that automatically improves to a rate of O( when the noise in the gradients is negligible.
Finally, we test our algorithm on multiple learning tasks on different deep architectures. In all of these tasks, our algorithm consistently matches or exceeds the best algorithms for the task. Further, the tuning process of our algorithm is reasonably simple; in many cases, we can use the exact parameters of SGD for the new algorithm.
1.2 Related works
Although second-order methods have many attractive theoretical properties, making these methods practical is challenging. There have been multiple efforts to develop efficient second-order algorithms. One popular approach the Broyden-Fletcher- Fletcher-Goldiae
Shanno algorithm (BFGS) [Keskar and
Wächter 2019 Liu and Nocedal 1989 Bollapragada et al. 2018 Pan et al. 2017 which provides a faster approximation to the Newton step using only a first-order oracle. Although BFGS and similar methods have been applied with some success to deep learning tasks (Bollapragada et al.) 2018 Ma 2020), we stress that such methods are fundamentally incapable of matching the convergence guarantees available to algorithms that truly use the Hessian in the stochastic non-convex setting [Arjevani et al. 2019].
More recent attention has focused on the use of Hessian-vector products as a way to achieve some of the benefits of second-order information without incurring significant computational overhead [Carmon et al. [2018] (Agawaal et al. 2017]. (Tripuraneni et al. [2017) uses Hessian-vecton products to approximate the cubic regularized Newton method Nesterov and Polyak 2006], converging in only ( 3.5) stochastic oracle calls. (Zhou et al. 2019] leverages both Hessian information and
variance-reduction techniques to achieve convergence rate of O
4/6
for finite-sum problems with
2372
n summands. However, both algorithms fail to achieve the optimal (c=3)) rate and to our knowledge none of these have been tested extensively on deep learning benchmarks. The first algorithm achieving the optimal (e) using Hessian-vector products rate was introduced in [Arjevani et al. 2020a However, their algorithm requires the batch size to be roughly OTT1/3), which excessively large for practical use-cases. On the other hand, our algorithm will work with any batch size.
Finally, variance-reduction based algorithms Johnson and Zhang 2013 can also achieve this same 133 rate for non-convex optimization [Fang et al. 2018 Zhou et al. 2018 Cutkosky and Orabona 2019 Tran-Dinh Dinh et al. 2019]. Despite favorable theoretical guarantees, variance- reduccion algorithms often rely on stronger smoothness assumptions, are tricky to implement properly, and seem to not perform as well expected in practice [Defazio and Bottou 2018). Comparison between veriatoe-reducttin algorithms and our algorithm (SGDHess) will be further discussed the end of the paper.

---

1.3 Problem setup
We are interested in minimizing a function F given by:
F
[f(2,)]
z-PP
Where [(Σ,=) =) is differentiable function of T. H indicates the model parameters (e.g. the weights of some neural networks), indicates an example data poin A E IR by:
[I We are also given a point #1 and define
sup F( - F (T) =A
(1)
ZER"
Further, we assume F is L-smooth. That is, for all E and y7:
[VF(E) - VF & L|| -
(2)
To design second-order algorithm, also assume access to second-order stochastic oracle. Given any Ø and vector पř, we are allowed to sample = ~ P₂ and compute V z) and V f 2)... We assume that for all I' and W::
ff - VF & E J
(3)
F S o 1
(4)
In addition, we will also need the assumption of second-order smoothness. For all o y. and
[( V k1)) pl |
(5)
Finally, in two of our algorithms, we need to assume f is G G-Lipschitz
<
(6)
2 SGD with Hessian-corrected momentum
In this section, we provide our SGD-based second-order algorithm. Before we into the analysis, let us compare our algorithm to SGD to see why adding the Hessian- vector product term to the momentum update is a good idea. The standard SGD with momentum update is the following:
gz (1 a)9.-1 + (V)(t,
E+ F, 79.
To gain some intuition for this update, let us suppose that 9:-1 VF(I-1). Then, viewing 9e an estimate of FāT)), define the error as:
é ge Vz
Intuitively, SGD will converge rapidly if this error is small. We can write:
é = a
VF(T.)
The second term is fairly benign: is zero in expectation and multiplied by potentially small value a. However, the first term is bit trickier to bound since (F & FFG.). Our approach is to leverage the sedond-order oracle to improve this estimate. Specifically, we modify the momentum update to:
ge- = (1 - ()- + V'J(T, - - #)
Now, if 9c-1 VF (F we would have
+ V2 =+ 8 V2 21) F(-1) VF()) + 0 + - 12-
-.-1) =
lz could also indicate minibatch of examples
3

---

Further, we have:
-(-1)) (V(Vf(E; VF(2))
so that the first term is now bounded by 0 - 2) which can be controlled through the learning rate 7) and the second term is again easy control via tuning Without this second-order correction, we need to rely on - (Z, + O( _z-1 D. Thus, by using another term of the Taylor expansion, corresponding reduction in our final error. Of course, the case 91-1 = VF(T-1) above is examined
have improved the dependency to O -z1 111). which will create
for intuition only. In our analysis, we do not make any such assumption.
Note that this approach is morally similar to the methods Cutkosky and Orabonal (2019] Tran- Dinh al. [2019), which themselves similar the recursive variance reduction Nguyen et al. [007]]
algorithm for stochastic convex optimization. In these algorithms, the Hessian- vector product is
replaced with gradient evaluations with the same example 24 f 2x) (f 2)). So long as the individual functions f 2,) are L-smooth, this will eventually have similar correction effect. However, past empirical work suggests that variance reduction may not be effective in practice on deep learning tasks Defazio and Bottou| (2018), while the use of Hessian-vector products has not been extensively tested our knowledge.
Our SGD with Cressian-correcte momentum is described in Algorithm| and its analysis is presented in Theorem I Note that only need to make small modification to the standard SGD update, which allows for streamlined analyses. Concretely, we avoid the large batch-size requirement of Arjevani al. 2020a and extend the analysis to adaptive learning rates in Section
Algorithm SGD with Hessian-corresd correctee Momentum (SGDHess)
Input: Initial Point Z1, learning rates T/, momentum parameters a,, time horizon T, Lipschitz
parameter G.
Sample 21 ~ Pz.
91 + 91 + V Vf(īi,
T2 E. 7191 dip
for t = 2... do
Sample 2, P..
9: - (1 0z 1) (0 V2 ( 2) F)-1))
- a:-1 V (Z),
9. + 9: if ال < G; otherwise, 9t t G å
clipp
Z+41 + - clip
end for
Return & uniformly at random from Tt,
ör (in practice à = .T).
Theorem 1. Assume 1
2
44
5
6
Then Algorithm with 1}: C073 04 = 24744 with
C 2 22K and C 2 4I,
x²
and
24 K + 25 guarantees
16C
-007 +
1o Ao
5
T
20CA + G
20G D(1 + log(T))
E
T
T2/3
C2T2/3
t=1
To see why we want to use clipped gradient, let us consider the error term with unclipped gradient:
?+1 =
+ (1 (1- (1- - z.) -FF(E+1)) + asch
- - -z))
+ (1 V'
where G Vf - 2
V F(T+1)) It is easy to see that we could bound the second and the
fourth term using assumption and ( and the first term is simply (1 az)é,, which we can use analyze how the error changes over each iteration. However, the third term is a bit trickier to control.
Let 6, FF + F2F(
Fz)
F((++1) from second-order smoothness have:
Ø² [ Eell < p²
1|6/11 <
4 1ló 4
4

---

Intuitively, if we let Jr be unbounded, 1| might be difficult to control since we only assume bound on the variance of the (ā,, 2x) rather than the fourth moment. Therefore, by enforcing some bound on the norm of Gr (using clipping), we make sure that we can control this term properly.
In order prove this Theorem, will require two Lemmas. The first (Lemma 2 is due Cutkosky and Orabona (2019), and provides a bound on the progress of one iteration of stochastic gradient descent without making any assumptions (such as unbiasedness) about the gradient estimates. The second (Lemma 3). is technical result characterizing the quality of the gradient estimates o. generated by Algorithm
Lemma 2. (Cutkosky and Orabona (2019 Lemma 1] Define:
& 9t cciip V FZt)
Suppose ni is a deterministic and non-increasing choice of learning rate. Then, so long as S 1
4
71t E 1 F(+.)) -
B[IVF(
37,
Lemma 3. Suppose that f(E,2) satisfies
and
Define:
é ccpi
V F (
Now, for some constant C and hH, set K
2G
Po The
Cura with C v2K, and
-2 + 4o
ag = 2K Then we have:
6
B[|lé++1||
11
3//t B[]le=11*]
The
B[IVF( + ( KG
24 160
5K Me+1
5km
4
25K2
Let us look into how Lemma
3 is used in our analysis. To prove Theorem
the Lyapunov
function defined as Q, F(1)) + 5km
|| to bound the ElIVF((Z))) term. Then:
6
6
E 0
F F( F( +
12++111
||&:11
5K
7--1
5KT.
3T) |
E V (2
+ 5km++
||e,+ 11
||
(7)
5K').
able simplify the bound of 77) by canceling the positive error term 3n ||& 1|2 while keeping the coefficient
where the inequality comes from Lemma Now if plug in the result of Lemma
of V (i,) 2 negative. Then,
move the negative term to the left hand side and derive bound for E VF (T)) With Lemma and Lemma in hand, we are now ready to prove Theorem
1
Proof of Theorem
7
We define the potential:
Φ F(T.)
5Km | ||
We will then show that d roughly decreases with / at rate that depends on [[,)( Specifically:
E - 2.] = E F(Z++1) - F(Tz) + 5K 1K+1
11
|
5Km m
applying Lemmas and
1/t 4
Elll ((()))))))))
3r
3np
" E|
B[IVF(EE)
4
5
16C6
62 K
25K2
+ 16C
BII
21
+ G2
K
20
25K2
5

---

Let D = 24 K + 160
25K
1/ E VEIIVF(Z))
+
D
20
Now sum over t, and use 2 mr for all t:
T
T G Σ
B B[Pr+1
D1 -
17
E V
m/
20
t=1
1=1
20
20G D > mi
E V
11
r
+
7/
7/
Now, observe that:
6
E $
PT+1
F(T1) F(ār+1) + 5km
||
lr 11
5kmr++
24G
24CG²
A
$ A +
5km
5K
where in the second line we used Ei|lå
1| < 4G Also, we have:
T
T
1 + log(T)
3
C
C
t=1
Putting all this together yields:
T
20
20G D >i=1 me
E
4 +
T
T'f
Tur
20CA + G26
20G D(1 + (T)(
T2/3
C2T2/3
L
3 Normalized SGD with Hessian-corrected momentum
Algorithm 2 Normalized SGD with Hessian-correeted Momentum (N-SGDHess)
Input: Initial Point J learning rates 17, momentum parameters a, time horizon T:
Sample ~ P.. Φ1 < Vf 21) 42 - J 7 Tigh
for t = 2... do
Sample 2, Ps.
-: - (1 - -a)a)rrr1 f
2)) -Z.-()))))) + a. VVV (Tt,
51 Zet1 f- T4. 17 [
end for
Return f uniformly at random from Ti...., Zr (in practice = FT).
In this section, we introduce algorithm that dispenses with the assumption ( required by Algorithm[] T This method (Algorithm 2 uses SGD with normalized updates and Hessian-vector significantly simplify the analysis
product-baseee momentum. We will show that normalization from section 2 while still maintaining O convergence rate. Indeed, the technical term in the analysis of Algorithm [ that required not appear because the updates are automatically bounded by 7).
enforce a bound on the updates via clipping simply does
The new convergence bound is presented in Theorem

---

Theorem 4. Assuming
7
and 5 hold (but not assuming (6), with
min(maxf 12/30
A pa15
(2 2/3
|. ] and yy min V/5a
VT(LVa+oon) (pT) /3 Algorithm
(Da)tis
T
6/5t
T2/30 4473
guarantees
60G + 54 (AO
1/3 1/3
60 A p
V9AL + T2AOT
6 p
B]IVF(E))I
T1/3
T2/5
VT
T2/3
V18AOH
3A2/3
T3/2
T5/3
In words, Algorithm achieves O with large σи and oG, and achieves O(1/VT) in noiseless case, without requiring a Lipschitz bound on the objective.
The proof of Theorem is provided in the appendix.
Adaptive SGD with Hessian-corrected Momentum
Algorithm 3 Adaptive learning rate for SGD with
Momentum Input: Initial Point ø1, parameters w, time horizon T', parameter G:
Sample 21 Pz.
91 + 91 (
G1 + (
71 - w1/3
T2 Jं -1 clip
71.11 for 1 = 2... do
Sample 2, ~ Ps.
G1 + [V 2t]l
9: +- (1 az-1) (0, Gr.hip + V f(t, ( Tz-1)) + a:-1 V V(
9, clip + 9. @ S G: otherwise, Jt clip t G â
T
f- (w+E 07/1/3
(set 172 1/33)
clip ē++1 + ū 7:::
end for
Return & uniformly at random from T....., Ør (in practice = ZT).
In previous sections, have presented two different versions of our algorithm. Both algorithms achieve the worst-case optimal /3) convergence rate. However, the bound in Section 2 is non-adaptive and remains to be 031/T1/3) even in noiseless settings (e.g. if of 0). The bound for the normalized SGD algorithm of Section is better in the sense that when the noise negligible, the algorithm can achieve O(1/VT) with explicit tuning of the learning rate, but this requires us to set the parameters 7) and based on prior knowledge of og. In this section, we will describe an adaptive version our algorithm that has the best of both worlds (Algorithm B3. The algorithm does not require the knowledge of og but still automatically improves to tighter bound whenever dg is small.
Theorem
With K
400 + 167 AF TJt
2G
(w+ E Lis Gayass with S
2G4/3 JK
and w
max( 3GG a = 2K Algorithm guarantees:
T
1/6 w2/6/2M 2M/3/4
20 1/3
E
(F
T
VT
1/
Where M 1 (20 A
G/g SKc
192K In (T+1)
64G 5 In T).
In words, algorithm converges with 0 ( rate in noisy case and automatically improves to Ô in noiseless case. We defer the proof Theorem the appendix.

---

5 Experiments
5.1 Setup
Our algorithm is a simple extension of the official SGD implementation in Pytorch. The Hessian- vector products can be efficiently computed using the automatic differentiation package/Paszke Paszkee et al. [2017]: f² z)u = Vh(z²) where h(z)) = (V fæ, 2), Since Pytorch allows backprogation through the differentiation process itself, this is straightforward to implement. To validate the effectiveness of our proposed algorithm, we perform experiments in two tasks: image classification and neural machine translation on popular deep learning benchmarks. The performance of SGDHess (unclipped version- we found that the clipped version had similar results but was slightly slower) compared to those of commonly used optimizers such as Adam and SGD as well as AdaHessian, another algorithm that incorporates second information. All experiments are run on NVIDIA v100 GPUs. The link to the code is provided in the appendix.
3. Resnet20 on Cifar10
b. Resnet32 on Cifar10
Test Accuricy
88
ScoHess Adallessian
ScCHlss
92
Adsilession
80
Adam
80
300
120
340
100
00
100
120
340
160
Epacch
Epach
Figure (a) SGDHess (Red) achieves the best accuracy among all optimizers (92.46 +0.07%). (b) Similar to the experiment on Resnet20, SGDHess also converges to the best accuracy (93.19 +0.08%). For the full plot, refer to the appendix.
5.2 Image Classification
Our Cifar10 experiment is conducted using the official implementation of AdaHessian. For AdaHessian, we use their recommended values for the same task for all the parameters. For the rest of the optimizers, we performed grid search on the base learning rate 1/ (0.001, 0.000, 0.01, 0.05, 0.1, 0.5, }} to find the best settings. Similar to the Cifar10 experiment of AdaHessian, reported the average best accuracy as well as the standard deviation (detailed results in the appendix). As we can see from the results in Figure [ SGDHess outperforms all other optimizers (0.32% and 0. 11% better than the next best optimizer in Resnet20 and Resnet32 respectively).
also trained models
160 epochs and we ran each optimizer 5 times and
Table I: Top accuracy on Imagenet
SGD
SGDHess AdaHessian
70.36
70.58
69.89
We also train SGD, SGDHess, and AdaHessian with Imagenet Deng et al. 2009 on Resnet18 to see how well SGDHess perform on a larger-scale benchmark. We use standard parameter values for SGD (Ir 0.1, momentum 0.9, weight decay = le-4) for both SGD and SGDHess and the recommended parameters values for AdaHessian. For the learning rate scheduler, we employ the plateau decay scheduler that was used in Yao et al. 2020). We train our model 90 epochs as usual. Even without extensive tuning, SGDHess not only still outperforms SGD (as shown in Table T but also comes close the otate-of-the-art accuracy (70.7%) on this particular task Redmon 2013 2016. even though these settings were chosen with SGD in mind rather than SGDHess.
8

---

Table Bleu Score on IWSLT' 14
SGD
SGDHess
Adam
AdaHessian
29.75
33.73
33,95
33.62
5.3 Neural Machine Translation
We use the IWSLT" 14 German to English dataset that contains 153k/7k/7k in the train/validationnnest set. Our experiments are run using all the default values specified in the official implementation of Fairseq Ott al. [201]] We use BLEU Papineni et al.] [2002] as the evaluation metrics for our experiment. For AdaHessian, we use the parameters specified in Yao et al. [2020]. For other optimizers, we again run grid search to find the best learning rate for the task. The best bleu scores are reported in Table It is worth stressing that SGDHess is algorithm based SGD, which consistently performs much worse than adaptive algorithms such as AdaHessian and Adam W in this type of task. Still, SGDHess is able to produce comparable results to those of AdaHessian and AdamW, thus significant bridging the gap between SGD and other adaptive algorithms (an almost points increase compared to SGD's s in BLEU score, which is significant for the task).
Conclusion and Future Work
In this paper, we have presented SGDHess, a novel SGD-based algorithm using Hessian-correeted momentum. We show that when the objective is second-order smooth, our algorithm can achieve the optimal ( -3) bound, and we provide a variant that automatically adapts to the level of noise provide experimental results on computer vision and neural machine
in the gradients. Finally, translation. In both tasks, SGDHess consistently performs better or comparable to other commonly used optimizers such SGD and Adam. It is our hope that this work demonstrates that Hessian- based optimization can combine both theoretical and practical improvements for large-scale machine learning problems. Our algorithm is one of the first second-order method that is able to achieve the optimal theoretical convergence rate and compete with first-order methods on large-scale tasks in terms of performance and runtime.
Our modification the standard momentum formula is also extremely simple, and so we suspect that is possible to make similar modifications to other popular optimization algorithms that use momentum, but we did not investigate this possibility. For example, one might hope that an appropriate per-coordinate or per-layer adaptaptation a la Adam Kingma and Ba [2014), AMSGrad Reddi et al. or LAMB You et al. [019 might improve performance. On the theoretical side, our adaptive results require Lipschitz losses, which may not be truly necessary.
Limitations:
References
Naman Agarwal, Zeyuan Allen-Zhu Brian Bullins, Elad Hazan, and Tengyu Ma. Finding approximate local minima faster than gradient descent. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 1195-11999 199, 2017.
Yossi Arjevani, Yair Carmon, John C Duchi, Dylan J Foster, Nathan Srebro, and Blake Woodworth. Lower bounds non-convex stochastic optimization. arXiv preprint urXiv:1912.02366 2019.
Yossi Arjevani, Yair Carmon, John C Duchi, Dylan J Foster, Ayush Sekhari, and Karthik Sridharan. Second-order information in non-convex stochastic optimization: Power and limitations. In Conference on Learning Theory, pages 242-299, 2020a.
Yossi Arjevani, Yair Carmon, John C. Duchi, Dylan J. Foster, Ayush Sckhari, and Karthik Sridharan. Sccond- order information non-convex stochastic optimization: Power and limitations. In Jacob Abernethy and Shivani Agarwal, editors, Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pages 242-299. PMLR, 09-12 Jul 2020b. URL http 7/ //proceedings.not mml. mlr, hit.eeddigge.m....rees//////////
httm html
Raghu Bollapragada, Jorge Nocedal, Dheevatsa Mudigere, Hao-Jun Shi, and Ping Tak Peter Tang. A progressive batching I-bsgs method for machine learning. In International Conference on Machine Learning, pages 620 629, PMLR, 2018

---

Leon Bottou and Olivier Bousquet. The tradeoff's of large scale learning. In Proceedings of the 20th International Conference on Neural Information Processing Systems, pages 161-168, 2007.
Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. Accelcrated methods for nonconvex optimization. SIAM Journal on Optimization, 28(2): 1751-172, 2018.
Ashok Cutkosky and Francesco Orabona. Momentum- based variance reduction in non-convex sgd. Advances in neural information processing systems, 32, 2019.
Aaron Defazio and Léon Bottou, On the incffectiveness of variance reduced optimization for deep learning. arXiv preprint 182::2181..04599. 2018.
Jia Deng, Wei Dong, Richard Socher. Li-Jia Li, Li, Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In 2009 JEEE conference on computer vision and pattern recognition, pages 248-255, leee, 2009.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12(7). 2011.
Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. Spider: Near-optimal non-convex optimization via stochastic path integrateed differential estimator. In Advances in Neural Information Processing Systems, pages 689-699, 2018.
Saeed Ghadimi and Guanghui Lan. Stochastic first-and -eroth-order methods for nonconvex stochastic program- ming. SIAM Journal on Optimization, 23(4):2341-235 2013.
Priya Goyal, Piotr Dollár, Ross Girshick, Picter Noordhuis, Lukasz Wesalowski, Aapo Kyrola, Andrew Tulloch, Yangqing Jia, and Kaiming He. Accurate, large minibatch sgd: Training imagenet hour. arXiv preprint 1rXiv:1706.0266 2017.
Rie Johnson
Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In Proceedings of the 26th International Conference on Neural Information Processing Systems- Volume I, NIPS' 13, page 31 315-323, Red Hook, NY, USA, 2013. Curran Associates Inc.
Keskar and Andreas Wächter. limited-memory quasi-newton algorithm for bound-constrained non-smooth optimization. Optimization Methods and Software, 34(1):150-17) 171, 2019.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations, 2014.
Dong C. Liu and Jorge Nocedal. On the limited memory bigs method for large scale optimization. MATHEMAT- ICAL PROGRAMMING, 45:503-528. 528, 1989.
Ilya Loshchilov and Frank Hutter. Sgdr: Stochastic gradient descent with warm restarts. arXiv preprint 1608.0068 2016.
Xuezhe Ma. Apollo: An adaptive aarameter-wise diagonal quasi- nuasinnewton method for nonconvex stochastic optimization, arXiv preprint arXiv:2009. 13586, 2020.
H. Brendan McMahan and Matthew J. Streeter. Adaptive bound optimization for online convex optimization. In Conference on Learning Theory, pages 244-256, 2010.
Yurii Nesterov and Boris T Polyak. Cubic regularization newton method and its global performance. Mathematical Programming, 108(1):177-055, 2006.
Lam M Nguyen, Liu, Katya Scheinberg, and Martin Takáč. Sarah: A novel method machine learning problems using stochastic recursive gradient. In International Conference on Machine Learning, pages PMLR, 2017.
Myle Ott, Sergey Edunov, Alexei Baevski, Angela Fan, Sam Gross, Nathan Ng, David Grangier, and Michael Auli. fairseq: A fast, extensible toolkit for sequence modeling. In Proceedings of NAACL-HILT 2019: Demonstrations. 2019.
Wenyong Pan, Kristopher Innanen, and Wenyuan I Liao. Accelerating hessian-free gauss-newton full- waveforrm inversion via I-bfgs preconditioned unnjugate-gradien algorithm. Geophysics, 82(2): 2017.
Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. Bleu: a method for automatic evaluation of machine translation. In Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics, pages 311-318. Philadelphia, Pennsylvania. USA. July 2002. Association for Computational Linguistics. doi: 0.3115/107308311031111
https://::/ww aclweb. .wwo wwrg//anthollggy/22-0000
10

---

Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. 2017.
Barak A. Pearlmutter. Fast exact multipiiattion by the bessian. Neural Computation, 6:147-160, 1994.
Sashank Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. In International Conference on Learning Representations, 2018.
SJ Reddi, S Kale, and S Kumar. On the convergence of adam and beyond. arxiv 2019. arXiv preprint WVX227794.009337.
Joseph Redmon. Darknet: Open souree neural networks in
2013-2016.
Quoe Tran-Dinh. Nhan H Pham, Dzung T Phan, and Lam M Nguyen. A hybrid stochastic optimization framework for stochastic composite nonconvex optimization. arXiv preprint arXiv:1907.03799 2019.
Nilesh Tripuraneni, Mitchell Stem, Chi Jin, Jeffrey Regier, and Michael I Jordan. Stochastic cubic regularization for fast nonconvex optimization. arXiv preprint arXiv:1711.02838, 2017.
7eke Xie, Issei Sato, and Masashi Sugiyama. Understanding and scheduling weight decay. arXiv preprint 1.X1:2011.11152. 2020.
Zhewei Yao, Amir Gholami, Sheng Shen, Kurt Keutzer, and Michael W Mahoney. Adahessian: An adaptive second order optimizer for machine learning, arXiv preprint arXiv:2006.0077 00719, 2020.
Yang You, Jing Li, Sashank Reddi, Jonathan Hseu. Sanjiv Kumar, Srinadh Bhojanapalli, Xiaodan Song, James Demmel, Kurt Keutzer, and Cho-Jui Hsieh. Large batch optimization for deep learning: Training 76 minutes, arXiv preprint arviv: Siiv:190: 1904,0096,, 2019.
Dongruo Zhou, Pan Xu, Quanquan Gu. Stochastic nested variance reduction for nonconvex optimization. In Advances Neural Information Processing Systems, pages
2018.
Dongruo Zhou, Pan Xu, and Quanquan Gu. Stochastic variance-reduccdd cubic regularization methods. Journal of Machine Learning Research, (0(13)):147) 2019. URL [RLppttp://jml1 org/ prggpppprs/v////////// 19-200099555511 html
Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th international conference on machine learning (ICML), pages 928-936, 2003.
Checklist
The checklist follows the references. Please read the checklist guidelines carefully for information how to answer these questions. For each question, change the default [TODO] to [Yes], [No], or [N/A]. You are strongly encouraged to include justification to your answer, either by referencing the appropriate section of your paper or providing a brief inline description. For example:
Did you include the license the code and datasets? [Yes]
Did you include the license the code and datasets? [No] The code and the data proprietary.
Did you include the license to the code and datasets? [N/A]
Please do not modify the questions and only the provided macros for your answers. Note that the Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below.
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [No] the paper a theoretical paper, has no negative social impacts
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]

---

2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (c.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes] see the appendix
(c) Did you include any new assets either in the supplemental material or as a URL? [Yes]
(d) Did you discuss whether and how consent
obtained from people whose data you'
using/curating? [No] the data is open source
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [No] the data contains no personally identifiable information
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
12


Reviews:
[{"review_id": "fnfI_ZQR-nt", "reviewer": "Reviewer_nnCX", "summary": "The paper introduces a Hessian-based correction term in SGD with momentum to reach $\\epsilon$ critical point in $\\mathcal{O}(\\epsilon^{-3})$ stochastic gradient and Hessian-vector product computations. The authors extend the benefit of the correction term to normalized SGD and adaptive algorithms. Finally, they showcase the benefits of their proposed algorithm with an experimental study on CIFAR-10, ImageNet, and neural machine translation.", "questions": "Here are my major questions:\n1. It would be great to have a discussion on why Arjevani et al. [2021] require large batch sizes and how the authors can tackle the necessity with momentum. The algorithm of Arjevani et al. [2021] (algorithm 1) uses K Hessian vector products (similar to the one being used in the current paper) per gradient step to reduce the variance. However, the algorithm of Arjevani et al. uses different samples for the K Hessian vector products, while the authors can get away with a single Hessian vector product update in the momentum. Why?\n \n\n2. There seems to be a mismatch between the theoretical claims and the experimental results. The theoretical claims show that SGDHess can reach a stationary point with $\\mathcal{O}(\\epsilon^{-3})$  stochastic gradient and Hessian calls, compared to $\\mathcal{O}(\\epsilon^{-4})$ stochastic calls for SGD. However, the experiments talk about achieving better generalization with SGDHess. \n\na) How is the result connected to generalization? \n\nb) Isn't it better to compare the loss behavior for the two algorithms, and show faster convergence for SGDHess? \n\n3. ResNet models use the ReLU activation function and maximum pooling layers. Hence, the global smoothness and the second-order smoothness are undefined, which are necessary for the theoretical claims. One suggestion to modify the experiments will be to use smooth activation functions like GeLU and tanh, and average pooling layers.\n\n", "limitations": "The authors have jotted down one of the main limitations of their work, which is assuming that the function is Lipschitz. However, it would be great to also include a discussion on the viability of the other assumptions, which are L-smoothness (Eq. 2), second-order smoothness (Eq. 6), and the upper bound on the variance of the gradient and the Hessian (Eqs. 3 and 4). Since one of the major ambitions of the paper is to show the benefits of the proposed algorithm in neural networks, it would be great to see some ablations for these assumptions in the deep learning architectures. ", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The major strength of the work is in the simplicity of the correction term introduced in momentum, which achieves the same complexity to reach an $\\epsilon$-critical point, compared to Arjevani et al. [2021], which requires a larger batch size (and a more complicated Hessian vector product calls). Moreover, the authors can show better performance of SGDHess compared to SGD in various vision and NLP settings. The theorem statements are clearly written and easy to understand.\n\n\nThe major issue with this is that the global smoothness and second-order smoothness constants may be very large for the theoretical bounds to turn vacuous for the deep neural networks. Moreover, there is a mismatch between the theoretical claims and the experimental results as pointed out later.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "2_TFUG2DuLP", "reviewer": "Reviewer_mZiQ", "summary": "The paper proposed a supposed novel way of using the Hessian-vector product as a momentum vector instead of the traditional momentum vector. The gradient is computed as a linear combination of the past gradient, which is also supposedly clipped, and the current gradient.", "questions": "1. Why is $z_t$ appearing everywhere ? If the gradients are not computed with respect to $z_t$, it is recommended to remove it.\n2. What is G-Lipschitz ? The formulation in equation (6) is very different from the one the reviewer has seen. Can the authors share a reference ?\n3. What is L ? Is this the constant term of the Lipschitz continuity equation ? If so, how is it determined ?\nEditorial:\n4. Why are only equations 1-6 numbered ?", "limitations": "1. The paper does not identify any convergence criterias.\n2. It is not performing better than state-of-the-art. It might seem in Figure 1(a) and (b) that they might reach maximum accuracy, but the sharp increase is also indicative of overtraining \n3. Equation with the gradient update (please use number for the main equations) can literally be boiled down to a linear combination of the past gradient and the current gradient.  $\\hat{g}_t = (1-\\alpha)\\hat{g}_{t-1} + \\alpha g_t$", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. Used the Hessian vector product is computed efficiently.\nWeaknesses:\n1. There is no convergence guarantee for the current method\n2. The computation expense is higher for the proposed approach, but the improvement in accuracy is limited. Especially in the case of Imagenet.\n3. The authors mention that the level of noise is limited in the conclusion section. However, no evidence of this is provided.\n4. Upon closer inspection in the appendix material, the results do no show improvement to \n\nEditorial:\n1. The paper is very hard to read. A lot of the derivations and lemmas can be moved to the supplementary section.\n2. The presentation needs improvement. Give more importance to the convergence proofs and the results. All of the derivations seem to reduce the credibility of the paper.\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "1ObxLJ6VdjU", "reviewer": "Reviewer_EDoL", "summary": "This paper derives an improved momentum SGD method based on Hessian-vector products. It achieves optimal theorical rates on non-convex problems, and high-accuracy performance on deep learning tasks. ", "questions": "The introduction says that the optimal rate of convergence is T=O(eps^-3), however, the rate of Theorem 1 seems to be faster than that (eps = logT/T^(2/3)), could you explain more on this optimality?\n\nA discussion on the related work by Cutkosky,Mehta 2022 (Momentum Improves Normalized SGD) is needed I think in Section 3, which seems to be too short. \n\nWhat is the practical performance of Algorithm 3? Some discussions are welcome. What is tilde O on line 196?\n\nWhat is the batchsize used in the experiment (section 5.1 setup)? It is not clear. A numerical comparison or at least some more discussions with the method Cutkosky et al. 2020  (Momentum-based variance reduction in non-convex sgd) is needed in Section 5 to support the claim in the introduction that recursive variance reduction requires large batches, as numerical results in that paper seem to work well on CIFAR.\n\nWhy the top 1 test accuracy, bleu score are higher with SGDHess compared to SGD in Table 1 and 2? Is that due to a higher training accuracy or some form of implicit regulization?\n\n", "limitations": "NA", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The strength of this paper is to introduce a correction to reduce the bias in the classical momentum SGD method (section 2). An algorithm SGDHess is proposed for this purpose, with theorical convergence analysis. Although there is a gap between the theorical version of the algorithm, and its practical version (i.e. return hat x in theory, and x_T in practice), numerical results are convincing about its improved accuracy compared to momentum SGD. One weakness is that I do not fully understand why it works better in practice, could this be explained better (see questions below)?", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}]

Author rebuttal:

Decision: Accept