Eigencurve: Optimal Learning Rate Schedule for SGD on Quadratic Objectives with Skewed Hessian Spectrums
Authors: Rui Pan
Haishan Ye
Tong Zhang
Venue: ICLR 2022 Poster (2022)
Keywords: optimization
learning rate schedule
optimal convergence rate

Abstract: Learning rate schedulers have been widely adopted in training deep neural networks. Despite their practical importance, there is a discrepancy between its practice and its theoretical analysis. For instance, it is not known what schedules of SGD achieve best convergence, even for simple problems such as optimizing quadratic objectives. In this paper, we propose Eigencurve, the first family of learning rate schedules that can achieve minimax optimal convergence rates (up to a constant) for SGD on quadratic objectives when the eigenvalue distribution of the underlying Hessian matrix is skewed. The condition is quite common in practice. Experimental results show that Eigencurve can significantly outperform step decay in image classification tasks on CIFAR-10, especially when the number of epochs is small. Moreover, the theory inspires two simple learning rate schedulers for practical applications that can approximate eigencurve.
 For some problems, the optimal shape of the proposed schedulers resembles that of cosine decay, which sheds light to the success of cosine decay for such situations. For other situations, the proposed schedulers are superior to cosine decay.

Published as a conference paper at ICLR 2022
EIGENCURVE: OPTIMAL LEARNING RATE SCHEDULE FOR SGD ON QUADRATIC OBJECTIVES WITH SKEWED HESSIAN SPECTRUMS
Rui Pan'r, Haishan Ye *t, Tong Zhang' *t
The Hong Kong University of Science and Technology
2ii an Jiaotong University rpan@ccnnect.. ust. yeha edde
ABSTRACT
Learning rate schedulers have been widely adopted in training deep neural net- works. Despite their practical importance, there is discrepancy between its prac- tice and its theoretical analysis. For instance, it is not known what schedules of SGD achieve best convergence, even for simple problems such optimizing quadratic objectives. In this paper, we propose Eigencurve, the first family of learning rate schedules that can achieve minimax optimal convergence rates (up to constant) for SGD on quadratic objectives when the eigenvalue distribution the underlying Hessian matrix skewed. The condition is quite common practice. Experimental results show that Eigencurve can significantly outperform step decay in image classification tasks on CIFAR-IO, especially when the num- ber of epochs is small. Morcover, the theory inspires two simple learning rate schedulers for practical applications that can approximate eigencurve. For some problems, the optimal shape of the proposed schedulers resembles that of cosine decay, which sheds light to the success of cosine decay for such situations. For other situations, the proposed schedulers are superior cosine decay.
INTRODUCTION
Many machine learning models can be represented as the following optimization problem:
min f(w) A S((w).
(1.1)
such as logistic regression, deep neural networks. To solve the above problem, stochastic gradient descent (SGD) (Robbins & Monro [95I) 1) has been widely adopted due its computation efficiency in large-scale learning problems [Bottou & Bousquet 2008), especially for training deep neural networks.
Given the popularity of SGD in this field, different learning rate schedules have been proposed to further improve its convergence rates. Among them, the most famous and widely used ones are inverse time decay, step decay (Goffin) 1977p, and cosine scheduler (Loshchilov & Hutter 2017). The learning rates generated by the inverse time decay scheduler depends on the current iteration number inversely. Such scheduling strategy comes from the theory of SGD on strongly convex functions, and extended to non-convex objectives like neural networks while still achieving good performance. Step decay scheduler keeps the learning rate piecewise constant and decreases it by a factor after a given amount of epuchs. It is theoretically proved in Ge et al. (2019) that when the objective is quadratic, step decay scheduler outperforms inverse time decay. Empirical results are also provided in the same work to demonstrate the hetter convergence property of step decay in training neural networks when compared with inverse time decay. However, even step decay
"Equal contribution. 1 "ooresponding author is Haishan Ye. Jointly with Google Research.

---

Published as a conference paper at ICLR 2022
is proved to be near optimal on quadratic objectives, it is not truly optimal. There still exists Io gap away from the minimax optimal convergence rate, which turns out to be non- trivial in a wide range of settings and may greatly impact step decay's ' empirical performance. Cosine decay scheduler (Loshchilov & Hutter, 2017) generates cosine-like learning rates in the range [o, 7), with T being the maximum iteration. is heuristic scheduling strategy which relies on the observation that good performance in practice can be achieved via slowly decreasing the learning rate in the beginning and "refining" the solution in the end with very small learning rate. Its convergence property on smooth non-convex functions has been shown in Li et al. (2021), but the provided bound is still not tight enough to explain its success in practice.
Except cosine decay scheduler, all aforementioned learning rate schedulers have (or will have) a tight convergence bound on quadratic objectives. In fact, studying their convergence property on quadratic objective functions is quite important for understanding their behaviors in general non- convex problems. Recent studies Neural Tangent Kernel (NTK) (Arora al. 2019] Jaccot et al. 2020) suggest that when neural networks are sufficiently wide, the gradient descent dynamic of neural networks can be approximated by NTK. In particular, when the loss function is least-square loss, neural network's inference is equivalent to kernel ridge regression with respect to the NTK in expectation. In other words, for regression tasks, the non-convex objective in neural networks resembles quadratic objectives when the network is wide enough.
The existence of log T gap in step decay's s convergence upper bound, which will be proven to be tight in wide range of settings, implies that there is still room for improvement in theory. Meanwhile, the existence of cosine decay scheduler, which has no strong theoretical convergence guarantees but pos- sesses good empirical performance in certain tasks, suggests that its convergence rate may depend on some specific properties of the objective determined by the network and dataset in practice. Hence it is natural to ask what those key properties may be, and whether it is possible to find theoretically- optimal schedulers whose empirical performance are comparable to cosine decay if those properties are available. In this paper, we offer an answer to these questions. We first derive novel eigenvalue- distribution- learning rate scheduler called e gencurve for quadratic functions. Combining with eigenvalue distributions of different types of networks, new neural-network- based learning rate schedulers can be generated based on our proposed paradigm, which achieve better convergence properties than step decay in Ge et al. (2019). Specifically, e eigencurve closes the log T gap in step decay and reaches minimax optimal convergence rates if the Hessian spectrum is skewed. We summarize the main contributions of this paper as follows.
1. To the best of our knowledge, this is the first work that incorporates the eigenvalue distribu- tion of objective function's 's Hessian matrix into designing learning rate schedulers. Accord- ingly, based on the eigenvalue distribution of the Hessian, we propose a novel eigenvalue distribution based learning rate scheduler named e eigencurve.
2. Theoretically, eigencurve can achieve optimal convergence rate (up to constant) for SGD on quadratic objectives when the eigenvalue distribution of the Hessian is skewed. Furthermore, even when the Hessian is not skewed, eigencurve can still achieve no worse convergence rate than the step decay schedule in/Ge al, 2009), whose convergence rate are proven to be sub-optimal in wide range of settings.
3. Empirically, on image classification tasks, e eigencurve achieves optimal convergence rate for several models on CIFAR-10 and ImageNet if the loss can be approximated by quadratic objectives. Moreover, it obtains much better performance than step decay on CIFAR-10, especially when the number of epochs is small.
4. Intuitively, our learning rate scheduler sheds light on the theoretical property of cosine decay and provides a perspective of understanding the reason why it can achieve good performance on image classification tasks. The same idea has been used to inspire and discover several simple familics of schedules that works in practice.
Problem Setup For the theoretical analysis and the aim to derive our eigenvalueeddepedden learn- ing rate schedulers, we mainly focus on the quadratic function, that is,
1 = (()) b(E)TT w,
min f(w) e Eg [f (f), where f(w, {)
(1.2)
2
where& & denotes the data sample. Hence, the Hessian of f(w) is
H Eg (E))
(1.3)
2

---

Published as a conference paper at ICLR 2022
Letting us denote b [B [e][b(E), obtain the optima of problem (.2
W = H HH- "b.
(1.4)
Given an initial iterate wo and the learning rate sequence } the stochastic gradient update is
Wh+1 = We T7 V = ( (H( - b(E)).
(1.5)
We denote that
Hw; (E) -(E)), _ (min L Amax (H),, and, x L/μ. (1.6)
In this paper, assume that
Eg [ 1 o²²H.
(1.7)
The reason for this assumption is presented in Appendix G.5
Related Work In convergence anal- ysis, one key property that separates SGD from vamilla gradient descent is that in SGD, noise in gradients domi- nates. In gradient descent (GD), con- stant learning rate can achieve linear convergence O(c²') with 0 < c < 1 for strongly convex objectives, i.e. obtain- ing (w)(()) f(w") I c in O(log())) iterations. However, in SGD, (() cannot even be guaranteed to converge to f(w") due to the existence of gra- dient noise (Bottou et al.) 2018). In- tuitively, this noise leads to a variance proportional the learning rate size, so constant learning rate will always intro- duce a O(x)) = M(m)) gap when com- pared with the convergence rate of GD.
Table I: Convergence rate of SGD with common sched- ulers on quadratic objectives.
Scheduler
Convergence rate of SGD
quadratic objectives
Constant
Not guaranteed converge
Inverse Decay
do
log T
Step Decay
2019
2021 Thenrem
This work
de 7
with skewed Hessian spectrams,
Rigenn
O
do
log
in worst case Corollary
(This work Theorem
2
Fortunately, inverse time decay scheduler solves the problem by decaying the learning rate inversely proportional the iteration number t, which achieves ((+) convergence rate for strongly convex objectives, specifically, O do? x). However, this is sub-optimal since the minimax optimal rate
for SGD is O ((4)) Ge et al., 2019 Jain et al. 2018). Moreover, practice, K can be very big for large neural networks, which makes inverse time decay scheduler undesirable for those models. This is when step decay (Goffin 1977) comes to play. Empirically, it is widely adopted bascline for lot of models. Theoretically, it has been do² -log T) for strongly con-
tasks
such image classification and serves
proven that step decay can achieve nearly optimal convergence rate O D(do" vex least square regression (Ge et al. 2019). A tighter set of instance-dependent bounds in a recent work (Wu al. 202T), which carried out independently from ours, also proves near optimal- ity. Nevertheless, step decay is not always the best choice for image classification tasks. In practice, cosine decay (Loshchilov Hutter 2017) can achieve comparable or even better performance, but the reason behind this superior performance is still unknown in theory (Gotmare al. 2018). All the aforementioned results are summarized Table T along with our results in this paper. It is worth mentioning that the minimax optimal rate O dor can be achieved by iterate averaging meth- ods (Jain et al. 2018: Bach & Moulines] 2013) Défossez Bach 2015): Frostig et al.) 2015) Jain al. 2016, Neu & Rosasco 22188), but it is not common practice use them in training deep neural networks, so only the final iterate (Shamir 2012) behavior of SGD is analyzed in this paper, i.e. the point right after the last iteration.
Paper organization: Section describes the motivation of our eigencurve scheduler. Section presents the exact form and convergence rate of the proposed eigencurve scheduler, along with the lower bound of step decay. Section g shows the experimental results. Section discusses the discovery and limitation of eigencurve and Section gives our conclusion.
3

---

Published as a conference paper at ICLR 2022
2 MOTIVATION
In this section, we will give the main motivation and intuition of our e gigncureee learning rate scheduler. We first give the scheduling strategy to achieve the optimal convergence rate in the case that the Hessian is diagonal. Then, we show that the inverse time learning rate is sub-optimal in most cases. Comparing these two scheduling methods brings up the reason why we should design eigenvalue distribution dependent learning rate scheduler.
Letting H be diagonal matrix diag (1, λ2, ,.,,..)) and reformulating Eqn.
d2)) Wc+1 - W. W - w. T/e ()) - -b())
L.5 we have
=w W+ (:HHu b) + (H Wi b (H())w; - b(())
=w wt (HoHHrr - - (Hw, - b)) + nu (Hw, b- (H b(E)))
(I H) (wa -w,) mene-
follows,
E (w - w.,)²
2 Xj { ;) 2 [wvr. - ww,) ] n// [melil]]]
(2.1)
m)2,)² 2 [wi, - w. + n X320
Since H is diagonal, we can set step size scheduling for each dimension separately. Letting us choose step size Th. coordinately with the step size T7t,j 1,(++I being optimal for the j-th coordi- nate, then we have the following proposition.
Proposition 1. Assume that H is diagonal matrix with eigenvalues X1 2 A 2 d.. 2 0 and Eqn. holds. If we set step size Th. = X,(E+15. holds that
(wit1y-way) - wan) Ej N,(Wi - -
2E if (w(+1) f(w))( =E
Σ X (wi+1s-
t (t 1)2
do
(++
(2.2)
The leading equality here is proved in Appendix G.I with the followed inequality proved in Ap- pendix [E] From Eqn. (2.2). we can observe that choosing proper step sizes coordinately can achieve the optimal convergence rate (Ge et al. 2019) Jain et al. 2018). Instead, if the widely used inverse time scheduler ÿe = 1/([I++ + μt) is chosen, we can show that only sub-optimal convergence rate can be obtained, especially when Xラ vary from each other.
Proposition 2. If we set the inverse time step size
[L+ then we have
2E (f(w++1) - [[w.)] E
Σ Ng (10+11 wa
(2.3)
L 1 L pul
X²
1
X302
> (w1. w)
+
d²
2X,
-
L pl
(L+ nr)²
Remark 1. Eqn. (.22) shows that if one can choose step size coordinate-wise with step size Tt.j = X7(+4] then SGD can achieve a convergence rate
d T
B[f(w-1)- 5o
0²
(2.4)
which matches the lower bound (Ge et al. 2019 Jain et al. and μ Xa in Proposition 2 obtain that the convergence rate of SGD being
2018 In contrast, replacing L = Au
d
1
X
E [[f(wr+1) - (w 5o
O
02
(2.5)
T
Xd
Since it holds that X, 2 Xa- the convergence rate in Eqn. 2.4) is better than the one in Eqn. 2.5 especially when the eigenvalues of the Hessian (H matrix) decay rapidly. In fact, the upper bound in Eqn. (2.5) is tight for the inverse time decay scheduling, as proven in Ge et al. (211
4

---

Published as a conference paper at ICLR 2022
Main Intuition The diagonal case H (A1, ,g...., A4) provides an important intuition for designing eigenvalue dependent learning rate scheduling. fact, for general non non-diagonal H, letting H UAU be the spectral decomposition of the Hessian and setting w U w, then the Hessian becomes a diagonal matrix from perspective of updating w', with the variance of the stochastic gradient being unchanged since U is unitary matrix. This is also the core idea of Newton's 's method and many second-order methods (Huang et al. 2020). However, given our focus in this paper being learning rate schedulers only, we move the relevant discussion of their relationship to Appendix H
Proposition and imppl that good learning rate scheduler should decrease the error of each co- ordinate. The inverse time decay scheduler only optimal for the coordinate related to the smallest eigenvalue. That's 's the reason why it is sub-optimal overall. Thus, we should reduce the learning rate gradually such that we can run a optimal learning rate associated to X to sufficiently drop the error of j-th coordinate. Furthermore, given the total iteration T and the eigenvalue distribution of the Hessian, we should allocate the running time for each optimal learning rate associated Xz.
EIGENVALUE DEPENDENT STEP SCHEDULING
Just as discussed Section 2 to obtain better conver- gence rate for SGD, we should consider Hessian's 's eigen- value distribution and schedule the learning rate based on the distribution. In this section, we propose novel learn- ing rate scheduler for this task, which can be regarded as piecewise inverse time decay (see Figure Tp. The method is very simple, we group eigenvalues according to their value and denote 8; be the number of eigenvalues lie in the range R, = [1= 2", 2 1, that is,
Figure I: Eigencurve: piecewise in- verse time decay scheduling.
8; = # E [e 2-, 2
(3.1)
Then, there most mmax log2 K such ranges. By the inverse time decay theory, the optimal learning rate associated to eigenvalues in the range R; should be
m =
) with to t to
tima T.
(3.2)
2
Our scheduling strategy is to run the optimal learning rate for eigenvalues in each R; for period to sufficiently decrease the error associated eigenvalues in R2
To make the step size sequence (n } monotonely decreasing, we define the step sizes
17t
if t [ti-1,
(3.3)
++ 1 A,2 + 2 1p(1-14400 1 4-1)
where
0 lo < 11 < 22 < 41 = A. = 44 -1-1, and Iaxx = loga K.
(3.4)
To make the total error, that is the sum of error associated with R, to be small, we should allocate A, according to 1;-1's. Intuitively, a large portion of eigenvalues lying in the range R2 should allocate a large portion of iterations. Specifically, propose to allocate A as follows:
A
T. with s; = #λ, E [N 24 2
(3.5)
Vsy
In the rest of this section, we will show that the step size scheduling according to Eqn. 3.3 and (355 can achieve better convergence rate than the one in Ge et al. (2019) when 8; non-uniformly distributed. In fact, better A, allocation can be calculated using numerical optimization.
3.1 THEORETICAL ANALYSTS
Lemma 1.
Let objective function f(x) be quadratic and Assumption (1.7 hold. Running SGD for T-steps starting from wn and a learning rate sequence {11, ) defined in Eqn. (3.3) the final iterate
5

---

Published as a conference paper at ICLR 2022
WT+1 satisfies
E [f(ur+1) - f(ww)] S(f(wo) - f(w,))
k²
+
15
o
Imax
Σ
2
A
2
L p Dj=1
A 2
i=0
(3.6)
Since the bias term is a high order term, the variance term in Eqn. (36) dominates the error for WT+11 For simplicity, instead of using numerical methods to find the optimal {4;}, we propose to use A; defined in Eqn. (3.5). The value of A; is linear to square root of the number of eigenvalues lying in the range Ju- 2 . -2). Using such A,, eigencurve has the following convergence property.
Theorem 1. Let objective function f(x) be quadratic and Assumption hold. Running SGD for T-stpps starting from wo, a learning rate sequence {1h J defined in Eqn. Eqn. (.5), the final iterate W1+1 satisfies
3.3 and Ds defined in
x²2
(E/mo=*
mmex-
V
15
Σ
2i=0
Janx
E [/(W++)) [ww)] ((f(wn) f(w.))
0².
8o
Please refer to Appendix D and G for the full proof of Lemma I and Theorem The variance
term 15(2/ v=.)
in above theorem shows that when s;'s vary largely from each other,
T
then the variance can be close to O (# -²)) which matches the lower bound (Ge et al. 2019 For 0.01 d. we can obtain that example, letting Imax 100, 0.99d and 8; 99
E T
d
4d 0² <
0² = (v0.99 + 99 x v0.01/99)2
0².
T
T
We can observe that the variance of s;'s large, the variance term in Theorem can be close to do² /T. More generally, as rigorously stated in Corollary 2 e eigencurve achieves minimax optimal convergence rate if the Hessian spectrum satisfies an extra assumption of "power law": the density of eigenvalue À is exponen- tially decaying with increasing value in log scale, i.e.
10a-
y- y-70-1.7x 1.7x
10
Donstyy (Lag
Ix).. This assumption comes from the observation of estimated Hessian spectrums in practice (see Figure 2). which will be further illustrated in Section
10-1
Eggewaluue
Corollary 2. Given the same setting in Theorem when Hessian H's eigenvalue distribution p(X) satisfies "power law", i.e.
Figure 2: Power law observed in 18 on ImageNet, both eigen- value (x-axis) and density (y-axis) are plotted in log scale.
1 p(A) 7 exp(-a(ln(A) - In(n)))
1 7
(4)
(3.7)
for some >> 1, where 7 S- (u/X)) there exists
constant C(a) which only depends on a, such that the final iterate wr+1 satisfies
E E[f(wr+1) f(ww)] S ((F(w)) f(w)))
k²
do²
TT
-C(a).
72
Please refer to Appendix G.3 for the proof. As for the worst-case guarantee, is easy to check that only when s;'s are equal to each other, that is, 8; d/ I//mx d/ loga (K), the variance term reaches its maximum.
Corollary 3. Given the same setting in Theorem [ when s; d/ log2(k) for all 0 s i Imax 1, the variance term in Theorem]] T reaches its maximum and WT+1 satisfies
E [f - f(w.) S (f(wo) - f(w.)) x²2 log k
15d log
0
T
T

---

Published as a conference paper at ICLR 2022
When s; ss's vary from each other, our eigenvalue dependent learning rate scheduler can achieve faster convergence rate than eigenvalue independent scheduler such as step decay which suffers from extra (T) term (Ge et al. 2019). Only when 8; 's equal to each other, Corol- lary] 3 shows that the bound of variance matches to lower bound up to log K. which is same to the one Proposition 3 of al. (2019).
Remark 2.
Furthermore, we show that this log I gap between step decay and eigencurve certainly exists for problem instances of skewed Hessian spectrums. For simplicity, we only discuss the case where H is diagonal.
Theorem 4. Let objective function fx) be quadratic. We run SGD for T-steps starting from we and
step decay learning rate sequence {ne Y?- defined in Algorithm I of Ge et al. (2019) with m S 1/L. L. As long as (1) H is diagonal, (2) The equality in Assumption (1.7) holds, i.e. Eeg [nmm [
x² and (3) >j (wos - w) # for Vj = 1, ,,2,...,d, d, the final iterate WT+1 satisfies,
[do²
E ([(())))) - [(ww)]
log
The proof is provided in Appendix G.4 Removing this extra log T term may not seem to be big deal in theory, but experimental results suggest the opposite.
EXPERIMENTS
To demonstrate e eigencurve 's practical value, empirical experiments are conducted on the task of image classification Two well-known dataset are used: CIFAR-10 (Krizhevsky et al. 2009) and ImageNet (Deng et al. 2009). For full experimental results on more datasets, please refer to Appendix A
4.1 HESSTAN SPECTRUM'S S SKEWNESS IN PRACTICE
According to estimated cigenvalue distributions of Hessian on CIFAR-10 10 and ImageNet, as shown in Figure 3. it can be observed that all of them are highly skewed and share similar tendency: A porfion of small eigenvalues and a tiny portion of large eigenvalues. This phenomenon has also been observed and explained by other researchers in the past(Sagun al., [017]] Arjevani & Field, 2020). On top of that, when we plot both eigenvalues and density in log scale, the "power law" arises. Therefore, if the loss surface be approximated by quadratic objectives, then eigencurve has already achieved optimal convergence rate for those practical settings. The exact values of the extra constant terms are presented in Appendix A.2
4.2 IMAGE CLASSIFICATION ON CIFAR-10 10 WITH EIGENCURVE SCHEDULING
This optimality in theory induces ei gencurve 's superior performance in practice, which is demonstrated Tablee[and Figure The full set of figures are available in Appendix A.8 All mod- els are trained with stochastic gradient descent (SGD), momentum, batch size 128 and weight decay wd = 0.0005. For full details of the experiment setup, please refer to Appendix B
4.3 INSPIRED PRACTICAL SCHEDULES WITH SIMPLE FORMS
By simplifying the form of eigencurve and capturing some of its key properties, two simple and practical schedules are proposed: Elastic Step Decay and Cosine-power Decay, whose empirical performance are better than at least comparable to cosine decay. Due to page limit, we leave all the experimental results in Appendix A.5 A.6
A.7
Elastic Step Decay: ?) = 7//22 if E (1-7~)1T (1 (1- (1-+++1)T)
(4.1)
Cosine-power Decay: 7/- 7min + (No 7mmn)
(1 cosl
(4.2)
max
'Code: https:://ithuu: wwtp//cwwww......cce..eec
Please refer to Appendix B.2 for details of the estimation and preprocessing procedure.

---

Published as a conference paper at ICLR 2022
107
Denato Lang S:3
10
Lom
y y.20
20-2.
y yo- 1.7x
Sclt)
Crate]
Denstry Gog Scaaet
10-4
20"2
10
10-4
20
10
10
10
10"
10
10
10
10
10m4
10
100
10"
10"
10
10:9
15"
12m4
10"
10"
10"
10
Egerrnauue
Eigenvaluue
Eigennele
Figure 3: The estimated eigenvalue distribution of Hessian for R8 on CIFAR-10, GoogLeNet on CIFAR-10 and ResNet-18 on ImageNet respectively. Notice that the density here is all shown in log scale. First row: original scale for cigenvalues. Second row: log scale for preprocessed eigenvalues.
Table 2: CIFAR-10: training losses and test accuracy of different schedules. Step Decay denotes the scheduler proposed in Ge et al.] (2019) and General Step Decay means the same type of scheduler with searched interval numbers and decay rates. "** before number means at least one occurrence of loss explosion among all trial experiments.
#Epoch
Schodule
ResNet-18
GoogLeNet Acc(SE)
VGG16 Acc(S))
Acc(S)
Inverse Time Decay
1.58:10.02
7..45:11.00
2.61:10.00
86.54:10.94
2.26:10.00
84.47:10.74
Decay
1.82:00.4
13.77=+1.48
2.59::0.02
87.04110.48
2.42:1::45
82.98:10.27
General Step Decay
1.52:10.22
81.99:10.35
1.93:t:0003
88 88.32:+:.32
2.14::0.42
86.79::0.36
Decay
142:100011
84.23:10.07
1,94:10.000
90.56:10.31
2:03:1:0000
31 segeencuvee
1.36:10.01
85.62.10.28
1.33.11.000
90.65.10.15
1,77 187-10.00
88.73-10.11
Inverse Time Decay
0.73:10.00
90.2210.43
0.62:1:002
92.05:10.69
1.32:10.62
173724:113.77
Step Decay
0.26.10.01
91.39
0.28.10.00
92.8310.155
0.59110.00
91.37
-100
General Step Decay
0.17:10.00
93.97:20.21
0.13::0.00
94.18:10.18
0.20:1:000
*42.36:10..1
Cusine Decay
0.17:10.00
94,04:10,21
0.12.1..00
94.62.10.11
0.20:10.00
93.17.1..
31 gencurve
94.05-10.18
0.12:1..00
94.75:10.15
0.18:10.00
92.88.10.24
2.0
V
inverse-rime-derray
0.9/3
szep-decay
0.8
general step decay
0.950
casine-decay
0.6
Inverse- time decay
decay
0.925
eigencurve
trein
appneral-tte-decce.
0.900
cosine-decay
0.4
eigencurve
0.875
0.825
0.0
0.800
5000
10000
25000 30000 35000 num ber of iterations
55000
20000 number Reeationn
Figure 4: Example: CIFAR-10 results for ResNet-18, with #Epoch 100. Left: training losses. Right: test accuracy. For full figures of this experiment, please refer to Appendix A.8
8

---

Published as a conference paper at ICLR 2022
5 DISCUSSION
Cosine Decay and Eigencurve For ResNet-18 on CIFAR-10 dataset, e eigencurve scheduler presents an extremely similar learning rate curve to cosine decay, especially when the number of training epochs is set to 100, shown in Figure 5 This directly links cosine decay to theory: the empirically superior performance of cosine decay is very likely to stem from the utilization the "skewness" among Hessian matrix's 's eigenvalues. For other situations, especially when the number of iterations is small, as shown in T eigencurve presents a better performance than cosine decay.
1.50
1.50
1.50
1.25
rosine-deray
1:25
cosine-decay
1.25
rosine-deray
1.00
learning rate
1.00
1.00
0.75
0.75
0.75
0.50
0.25
0.00
therations
Figure 5: Eigencurve 's learning rate curve generated by the estimated eigenvalue distribution for ResNet- 18 on CIFAR-18 after training 50/100/200 epochs. The cosine decay's learning rate curve (green) is also provided for comparison.
Sensitiveness to Hessian's Eigenvalue Distributions One limitation of e eigenncuree is that requires precomputed eigenvalue distribution of objective functions's Hessian matrix, which can be time-consuming for large models. This issue can be overcome by reusing the estimated eigen- value distribution from similar settings. Further experiments on CIFAR-10 suggest the effective- ness of this approach. Please refer to Appendix A.33 for more details. This evidence suggests that ei eigencurve's 's performance is not very sensitive estimated eigenvalue distributions.
Relationship with Numerically Near-optimal Schedulers In Zhang et al. (2019). dynamic programming algorithm was proposed to find almost optimal schedulers if the exact loss of the quadratic objective is accessible. While it is certainly the case, e gencurve still possesses several additional advantages over this type of approaches. First, e sigencurree can be used to find simple- formed schedulers. Compared with schedulers numerically computed by dynamic programming, eigencurve provides an analytic framework, so it is able to bypass the Hessian spectrum estima- tion process if some useful assumptions of the Hessian spectrum can be obtained, such as "power law". Second, e eigencur cuncuvvee has a clear theoretical convergence guarantee. Dynamic programming can find almost optimal schedulers, but the convergence property of the computed scheduler still unclear. Our work fills this gap.
6 CONCLUSION
In this paper, novel learning rate schedule named eigencurve proposed, which utilizes the "skewness" of objective's Hessian matrix's eigenvalue distribution and reaches minimax optimal convergence rates for SGD on quadratic objectives with skewed Hessian spectrums. This condition of skewed Hessian spectrums is observed and indeed satisfied in practical settings of image classifi- cation. Theoretically, e eigencurve achieves no worse convergence guarantee than step decay for quadratic functions and reaches minimax optimal convergence rate (up to constant) with skewed Hessian spectrums, e.g. under "power law". Empirically, experimental results on CIFAR-10 10 show that e eigencurve significantly outperforms step decay, especially when the number of epochs is small. The idea of ei eigencurve offers a possible explanation for cosine decay's s effectiveness in practice and inspires two practical families of schedules with simple forms.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGEMENT
This work is supported by GRF 16201320. Rui Pan acknowledges support from the Hong Kong Phl) Fellowship Scheme (HKPFS). The work of Haishan Ye supported in part by National Natural Science Foundation of China under Grant No. 12101491.
REFERENCES
Yossi Arjevani and Michael Field. Analytic characterization of the hessian in shallow relu models: A tale of symmetry, 2020.
Sanjeev Arora, Simon S. Du, Wei Hu, Zhiyuan Li, Ruslan Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net, 2019.
Francis Bach and Eric Moulines. Non-strongly-convee smooth stochastic approximation with con- vergence rate (1/n). arXiv preprint arXiv: /33062///99 2013.
Aleksandar Botev, Hippolyt Ritter, and David Barber. Practical Gauss- Newss- optimisation for deep learning. In Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pp. 557-565. PMLR, 06-11 Aug 2017. htLhttts:/// pttttp:://proceednnge mlr press/v10/ botevl7a.bttm
Léon Bottou and Olivier Bousquet. The tradeoffs of large scale learning. In J. Platt, D. Koller, Y. Singer, and S. Roweis (eds.), Advances in Neural Information Processing Systems, vol- ume 20. Curran Associates, Inc., 2008. URL paper/2001 2010000000/00000
ngs ngs neurips..... ccc
Léon Bottou, Frank E. Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning, 2018.
Richard H Byrd, Samantha L Hansen, Jorge Nocedal, and Yoram Singer. A stochastic quasi-newton method for large-scale optimization. SIAM Journal on Optimization, 26(2):1008 1031, 2016.
Chih-Chung Chang and Chih-Jen Lin. Libsvm: a library for support vector machines. ACM trans- actions on intelligent systems and technology (TIST), 2(3):1-27, 2011.
Alexandre Défossez and Francis Bach. Averaged least-mean-squares: Bias-variance trade-offs and optimal sampling distributions. Artificial Intelligence and Statistics, pp. 205-213, PMLR, 2015.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hi- erarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pp. 248-255, leee, 2009.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL httphh/t:///aciii ics. uci www.uuieeue edu/ml
Murat A Erdogdu and Andrea Montanari. Convergence rates of sub-sampled new- methods. In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 28. Curran Asso-
ciates, Inc., 2015. URL htttps://prooeeddnngg nww..iss......i................. wwt.eersss...pppe///21111.. pctppaapee/211///ileee////////// Paper pdf
Roy Frostig, Rong Ge, Sham M Kakade, and Aaron Sidford. Competing with the empirical risk minimizer in a single pass. Conference on learning theory, pp. 728-763. PMLR, 2015.
Rong Ge, Sham Kakade, Rahul Kidambi, and Pranceth Netrapalli. The step decay schedule: A near optimal, geometrically decaying learning rate procedure for least squares. In Advances in Neural Information Processing Systems, pp. 14977-14988, 2019.
Jean-Louis Goffin. On convergence rates of subgradient optimization methods. Mathematical pro- gramming, 13(1):329-3444 1977.
10

---

Published as a conference paper at ICLR 2022
Akhilesh Gotmare, Nitish Shirish Keskar, Caiming Xiong, and Richard Socher. A closer look at deep learning heuristics: Learning rate restarts, warmup and distillation, 2018.
Priya Goyal, Piotr Dollár, Ross Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, An- drew Tulloch, Yangqing Jia, and Kaiming He. Accurate, large minibatch sgd: Training imagenet in hour, 2018.
Roger Grosse and James Martens. A kronecker-factored approximate fisher matrix for convo- lution layers. In Maria Florina Balcan and Kilian Q. Weinberger (eds.), Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pp. 573-582, New York, New York, USA, 20-22 Jun 2016. PMLR. URL mww. Texxes//48//r00/ wtt////////o.....rr///
https://proceedin wtw.eeeiiiinnn....es....e.
Sepp Hochreiter and Jürgen Schmidhuber. Long Short-Term Memory. Neural Computation, 18):1735-7780 11 1997. ISSN 0899-7667. doi: (ee11112/eco.1990 199.999..11777. URL https:
//doi.org/10/ 112.0...11........ 1997.9..9 1735
Xunpeng Huang, Xianfeng Liang, Zhengyang Liu, Lei Li, Yue Yu, and Yitan Li. Span: A stochastic projected approximate newton method. Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 1520-1527, 2020.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and gen- eralization in neural networks, 2020.
Prateek Jain, Sham M Kakade, Rahul Kidambi, Pranceth Netrapalli, and Aaron Sidford. Par- allelizing stochastic approximation through mini-batching and tail-averaging. arXiv preprint 1r0:0::610.03377, 2016.
Prateek Jain, Sham M. Kakade, Rahul Kidambi, Praneeth Netrapalli, and Aaron Sidford. Acceler- ating stochastic gradient descent for least squares regression, 2018.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Xiaoyu Li, Zhenxun Zhuang, and Francesco Orabona. A second look exponential and cosine step sizes: Simplicity, adaptivity, and performance, 2021.
lyy Loshchilov and Frank Hutter. SGDR: stochastic gradient descent with warm restarts. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings, 2017.
Mitchell P. Marcus, Beatrice Santorini, and Mary Ann Marcinkiewicz. Building a large annotated corpus of English: The Penn Treebank. Computational Linguisties, 19(2):313-33) 1993. URL
https: /tatss:/aclll antho logy .rgg/orrg/bo 000i//93-2000
Gergely Neu and Lorenzo Rosasco. Iterate averaging as regularization for stochastic gradient de- scent. In Conference On Learning Theory, pp. 3222-3242. PMLR, 2018.
Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of mathemati- cal statistics, pp. 400-407, 1951.
Levent Sagun, Leon Bottou, and Yann LeCun. Eigenvalues of the hessian in deep learning: Singu- larity and beyond, 2017.
Nicol N Schraudolph. Fast curvature matrix-vector products for second-order gradient descent. Neural computation, 14(7):1723-1738 2002.
Ohad Shamir. Is averaging needed for strongly convex stochastic gradient descent. Open problem presented at COL.T, 2012.
Ohad Shamir and Tong Zhang. Stochastic gradient descent for non-smooth optimization: Conver- gence results and optimal averaging schemes, 2012.

---

Published as a conference paper at ICLR 2022
Jingfeng Wu, Difan Zou, Vladimir Braverman, Quanquan Gu, and Sham M Kakade. Last iterate risk bounds of sgd with decaying stepsize for overparameterized linear regression. arXiv preprint arXi::2110.061900 2021.
Minghan Yang. Dong Xu, Hongyu Chen, Zaiwen Wen, and Mengyun Chen. Enhance eurvature information by structured stochastic quasi-newton methods. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 10654-10663, June 2021.
Zhewei Yao, Amir Gholami, Kurt Keutzer, and Michael Mahoney. Pyhessian: Neural networks through the lens of the hessian, 2020.
Wojeiech Zaremba, Ilya Sutskever, and Oriol Vinyals. Recurrent neural network regularization, 2015.
Guodong Zhang, Lala Li, Zachary Nado, James Martens, Sushant Sachdeva, George E. Dahl, Christopher J. Shallue, and Roger Grosse. Which algorithmic choices matter at which batch sizes? insights from a noisy quadratic model, 2019.
12

---

Published as a conference paper at ICLR 2022
A MORE EXPERIMENTAL RESULTS
A.1 RIDGE REGRESSION
We compare different types of schedulings ridge regression
f(w) - 11l2 al1w0l12
This experiment only an empirical proof of our theory. In fact, the optima ridge regression has closed form and can be directly computed with
w. (x xxx) XTY
Thus the optimal training loss f(w.) can be calculated accordingly, In all experiments, use the loss gap fww") -ww,) as our performance metric.
Experiments are conducted on a4a datasets (Chang & Lin 2011 Dua & Grafi 2017 (https:// www. csie. ntu edu. tw/ tw/-cjllst maiiinniisttttooooo..mmmmm which contains 4, 781 samples and 123 features. This dataset is chosen majorly because it has moderate number of samples and features, which enables us to compute the exact Hessian matrix H 2(X X/n + af) and its corresponding eigenvalue distribution in acceptable time and space consumption.
html #a4a/),
In all of our experiments, set 10-3 The model is optimized via SGD without momentum, with batch size 1, initial learning rate 7/o E (0.1, 1, 0.06, 0.03, 0.02, 0.01, 0.006, 0.003, 0.002, 0.001, 0.0006, 0.0003, 0.0002, 0.0001 and learning rate of last iteration Maain {0.1, 0.01, 0.001, 0.0001, 0.00001, O, "UNRESTRICTED"), Here "UNRESTRICTED" denotes the case where Mmmi is not set, which is useful for sigencurve, who can decide the learning rate curve without setting 7min- Given and Mmin. we adjust all schedulers as follows. For inverse time decay 7/: 70/ + Ynot) and exponential decay ÿ) 7 y'no, the hyperparameter y computed accordingly based on nu and 7min For cosine decay, T7o and Mmin is directly used, with no restart adopted. For e eigencurve, the learning rate curve is linearly scaled to match the given 7/min-
In addition, for eigencurve, we use the eigenvalue distribution of the Hessian matrix, which is directly computed via eigenvalue decomposition, as shown in Figure
10a
Demsity (Log Scale)
10-1
Density (Log Scale!
10-2
10-2
10-1
1
10-9.
10
10
0.0
2.5
7.5
10.0
12.5
15.0
10-1
109
10a
10a
Eigenvalue
Eigenvalue
Figure 6: The eigenvalue distribution of Hessian for ridge regression on a4a. Left: original scale for eigenvalues. Right: log scale for eigenvalues. Notice that the density here is shown in log scale.
All experimental results demonstrate that eigencurve can obtain similar or better training losses when compared with other schedulers, shown in Table
13

---

Published as a conference paper at ICLR 2022
Table 3: Ridge regression: training loss gaps of different schedules over 5 trials.
Training loss optimal training loss: f(w") f(wra)
Schedule
#Epoch =
#Fpoch 5
Constant
0.014963310.00169
0.00478710.00011
Inverse Time Decay
0,007284_0.000190
0.002098100.00116
Exponetial Decay
0.008351=00000:60
0.000931100000100
Cosine Decay
0.007767=00000006
0.001167#0.001142
Eigencurve
0.006977:00000197
0.000676+0.000069
Schedule
#Epoch
#Epoch =
Constant
0.001351::0000179
0.000122:000000000
Inverse Time Decay
0.000637:00000143
0.00001 0.00000
Exponetial Decay
0.000048:00000007
0.0000001100000000
Cosine Decay
0.000054400000005
0.00000010.0000000
# gencuurv
0.000045=0000000
0.000000+10000000
A.2 EXACT VALUE OF THE EXTRA TERM ON CIFAR- 10 EXPERIMENTS
have already given the qualitative evidence that shows eigencurve 's op- timality for practical settings on CIFAR-10. Here we strengthen this argument by providing the quantitative evidence as well. The exact value of the extra assume CIFAR-10 10 has batch size 128, number of epochs 200 and weight decay 5 10 while ImageNet has batch size 256, number of epochs 90 and weight decay 10 10-4
In Section 4.1
presented in Table 4 where
Table 4: Convergence rate of SGD with common schedulers given the estimated eigenvalue distri- bution of Hessian, assuming the objective is quadratic.
Value of the extra term
Convergence
rate of SGD quadratic functions
CIFAR-10 ResNet18
CIFAR-10 Googl eNet
CIFAR-I0 VGGI6
ImageNet
Scheduler
ResNar18
Inverse Time Decay
3.39 10
4.92 10
6.50 10
6.80 10
Step Decay
d
log 2
16.25
16.25
16.25
18.78
(> s/mase- v
da²
gencurve
5..7
7.12
logg 6s 8: #Ag [a 22, 12-22111
where Tanax
Minimax optimal rate
is worth noticing that the extra term's value of e eigencurve is independent from the number of iterations I', since the value (E/ma> Imax- / only depends on the Hessian spectrum. So basically constant) for models and
eigencurve has already achieved the minimax optimal rate (up datasets listed in Table 4] if the loss landscape around the optima can be approximated by quadratic functions. For full details of the estimation process, please refer to Appendix B
A.3 REUSING BIGENCURVE FOR DIFFERENT MODELS ON CIFAR-10 10
For image classification tasks CIFAR-10, we check the performance of reusing ResNet- 18's eigenvalue distribution for other models. As shown in Table experimental results demonstrate that Hessian's 's eigenvalue distribution of Resnet-1 18 CIFAR-10 can be applied to GoogLeNetVGGG1 and still achieves good peformance. Here the experiment settings are exactly the same as Section 4.2 in main paper.
14

---

Published as a conference paper at ICLR 2022
Table 5: CIFAR-10: training losses and test accuracy of different schedules over trials. Here all e1 eegenuuree schedules are generated based on ResNet-18's Hessian spectrums. before number means least one occurrence of loss explosion among all trial experiments.
#Epoch
Schedule
GoogL.eNet
VGG16
Loss
Acc(%)
Loss
Acc(%)
Inverse Time Decay
2.61110.00
86.54:10,94
2.26110.00
84.4710.774
Step Decay
2.59:10.02
87.04:10.48
2.42:10.45
82.9811.27
=10
General Step Decay
1.93+0.03
88.32:t1.32
2.14:0..42
86. 06.3
Cosine Decay
1.94++0.00
90.56++0.1
2.03++0000
87.99+0.13
El Eigencurve (transferred)
1.65++0.00
91.17=00.00
1.89=0.000
88.17=0.32
Inverse Time Decay
0.62.10.02
92.05-10.69
1.32.10.62
17.724113.77
Step Decay
0.28110.00
92.83110.15
0.59110.00
91.37110.00
=100
General Step Decay
0.13#0.00
94.18+0.18
0.20=#0.00
"92.36=10:40
Cosine Decay
0.12+10.00
94.62:t0.11
0,20+00.0
03.17
Eigencurve (transferred)
0.11::0.00
94.8110119
0.20:10.00
93.17:10.09
A.4 COMPARISON WITH EXPONENTIAL MOVING AVERAGE ON CIFAR-10
Besides learning rate schedules, Exponential Moving Averaging (EMA) method
Wr = a _ = WR
Wr = Ort; + (1 -
k=0
is another competitive practical method that is commonly adopted in training neural networks with SGD. Thus, it is natural to ask whether e eigencurve can beat this method as well. The answer is yes. In Table O we present additional experimental results on CIFAR-10 to compare the perfor- mance of e rigenuuree and exponential moving averaging. can be observed that there is large performance gap between those two methods.
Table 6: CIFAR-10: training losses and test accuracy of Exponential Moving Average (EMA) and e eigencurve with #Epoch = 100 over trials. For EMA, we search its constant learning rate Vh 77 E (1.0, 0.3, 0.2, 0.1} and decay E {0.9, 0.95, 0.99, 0.995, 0.999). Other settings remain the same as Section 4.2
Method/Schedule
R8
GoogLeNet
VGG16
Acc(%)
Loss
Acc(%)
Loss
Acc(%)
EMA
0.30+00.0
90.09+t0.82 94.05-+0.18
0.33++0.01 0.12+:0.00
93.42-H0.26
0.49+00.00 0.18=0.00
91.87=0.82
Eigencurve
0.14+:0.00
94.75++0.15
92.88=00244
A.5 IMAGENET CLASSIFICATION WITH ELASTIC STEP DECAY
One key observation in CIFAR-10 experiments the existence of "power law" shown in Figure Also, notice that in the form of eigencurve specifically Eqn. (3.5), iteration interval length A; proportional to the square root of eigenvalue density s; in range [u-22,, 1u 12-2+1). Combining those two facts together, it suggests the length of "learning rate interval" should have lengths exponentially decreasing.
Based on this idea, Elastic Step Decay (ESD) is proposed, which has the following form,
N n if E [(1 -1-
Compared to general step decay with adjustable interval lengths, elastic step decay does not require manual adjustment for the length of each interval. Instead, they are all controlled by one hyper- parameter (0, 1), which decides the "shrinking speed" of interval lengths. Experiments
15

---

Published as a conference paper at ICLR 2022
CIFAR-10, 10, CIFAR-100 and ImageNet demonstrate its superiority in practice, as shown in Table Table g
For experiments CIFAR- CAAAR-OO/IIFR--II 100, adopt the same settings eigencurve except we only use common step decay with three same-length intervals + decay factor 10.
Table Elastic Step Decay on CIFAR- CAAAR-O//CIAA-III test accuracy(%) of different schedules over
5 trials. "*** before number means at least occurrence of loss explosion among all 5 trial experiments.
#Epoch
Schodule
ResNet-18
GoogLeNet
VGGI6
CIFAR-10
CIFAR-10
CIFAR-100
CIFAR-10
CIFAR-100
Inverse Time Decay
79.45:1:1.00
48.73:11.66
86.54=00.44
$7.90:11.27
84.47.10.74
50.04.10.83
Step Decay
79.67:10.74
54.54:10.26
18.37=0.13
63.05.10.35
85.18:10.06
45.86.10..11
Cosine Decay
84.23-20.07
61.26:::111
90.56=0.31
69.09::0.27
87.99 13
$5,42:0.22 28
ESD
85,38=00.38
64.17:00.57
91.23-0.33
70.46::0.41
88.67:00.21
57.23-10.39
Inverse Time Decay
90.82:10.45
69.82:00.77
92.05=0.60
73.544:0.28
13.244113.77
67.70:1::49
Step Decay
93.68.10.07
73.13.10112
94.13
76.80.10.16
92.62.10.15
70.02.10.41
Cosine Decay
94.04-1..21
74.65:0041
94.62-0.11
18:13:5
93.17:1.088
12.47:10.28
ESD
94.06=0.111
74.76::0.33
94.65=0.11
78.23440.20
93.25-0012
72.50-:0.26
For experiments on ImageNet, we use ResNet-50 trained via SGD without momentum, batch size 256 and weight decay wnd = 10-1 Since no momentum used, the initial learning rate is set to Vo = 1.0 instead of 0.1. Two step decay baselines are adopted. "Step Decay [30-60]" is the common choice that decays the learning rate folds at the end epoch 30 and epoch 60. "Step Decay [30-60-80]" is another popular choice for the ImageNet setting (Goyal et al. 2018), which further decays learning rate 10 folds at epoch 80. For cosine decay scheduler, the hy hyperparameter Mmin is set to be O. As for the dataset,
the common ILSVRC 2012 dataset, which contains 1000 classes, around 1.2M images for training and 50,000 images for validation. For all experiments, we search E (1/2,1/vl for ESD, with other hyperparameter search and selection process being the same e gencurve.
Table 8: Elastic Step Decay on ImageNet-Ik: Losses and validation accuracy of different schedul- ings for ResNet-50 with #Epooch990 over trials.
Top-1 validation acc(%)
Top-5 validation acc(%)
Schedule
Training loss
Step Decay [30-60]
1.4726 000057
73.55:10.13
92.63:10.008
Step Decay [30-60-80)
1.4738=0.000
76,05=10.33
92.83=0.115
#Epoch=90
Cosine Decay
1.4697=10.004
76.57=00.07
93.25=10.05
ESD (r 1/v2)
1.4317=10.0227
76.79-10.10
93.31
A.6 LANGUAGE MODELING WITH ELASTIC STEP DECAY
More experiments on language modeling are conducted to further demonstrate Elastic Step Decay's superiority over other schedulers.
For all experiments, we follow almost the same setting in Zaremba et al. (2015). where a large regularized L.STM recurrent neural network (Hochreiter Schmidhuberi 1997) is trained on Penn Treebank (Mareus et al. 1993) for language modeling task. The Penn Treebank dataset has a training set of 929k words, a validation set 73k words and a test set of 82k words. SGD without momentum adopted for training, with batch size 20 and 35 unrolling steps in LSTM.
Other details are exactly the same, except for the number of training epochs. In Zaremba et al. (2015), uses 55 epochs train the large regularized LSTM, which is changed to 30 epochs in setting, since we found that the model starts overfitting after 30 epochs. We conducted hyperparam- eter search for all schedules, shown in Table
16

---

Published as a conference paper at ICLR 2022
Table 9: Hyperparameter search for schedulers.
Scheduler
Form
Hyperparameter choices
Yo {100, 10 1000" 1000), and set A, that
Inverse Time Decay
1=
Unin E (10-?, 10 .10 10100 10
=1
General Step Docay
K (3. 4,5, [log T J. [oggT++ +
if E [R,, to 1)
7 (2 10)
Yo E {20", 10 1, 1.10 2, 2,10 3
Cosine Decay
+ (rjo Tinin (1 + cas (FF)
qoin {10 10 10100000 ,0
Te = 10/22" (1]
Elastic Step Decay
if
TT, (1 +y))
(2- 1, 1/2 2 1/3
2 1/0 2 1/20].
Baseline
?0 1.15
for first 14 epochs for epoch lo
110
Experimental results show that Elastic Step Decay significantly outperforms other schedulers, as shown in Table I0
Table 10: Scheduler performance LSTM Penn Treebank over trials.
Scheduler
Validation perplexity
Test perplexity
Inverse Time Decay
114 82.4
112.7
General Step Decay
79.1+0.2
Baseline (Zaremba al. 2015)
82.2
78.4
Cosine Decay
82.4+:0.4
78.5+004
Elastic Step Decay
81.1:10.2
77.4
17

---

Published as a conference paper at ICLR 2022
A.7 IMAGE CLASSIFICATION ON IMAGENET WITH COSINE-POWER SCHEDULING
Another key observation in CIFAR-I0 experiments is that e eieecurve 's learning rate curve shape changes in fixed tendency: more "concave" learning rale curves for less training epochs, which inspire the cosine-power schedule in following form.
[
Cosine-powee Pawner-pwwer:: 1); Mmmi + (70 Mmmin)
(1 + cos(
T)) mmax
2
Results in Table 11 show the schedulings' performance with a 0.5/1/2, which are denoted as /Coosne/Cosine/Cooine"" respectively. Notice that the best scheduler gradually moves from small ar to larger when the number of epochs increases. For #cpoch=270, since the number of epochs is large enough to make model converge, it is reasonable that the accuracy gap between all schedulers small.
For experiments on ImageNet, we use ResNet-18 trained via SGD without momentum, batch size 256 and weight decay wd 10- Since no momentum used, the initial learning rate is set to Vo = 1.0 instead of 7/- = 0.1. The hyperparameters Thmin is set to be 0 for all cosine-power scheduler. the common ILSVRC 2012 dataset, which contains 1000 classes, around 1.2M images for training and 50,000 images for validation.
As for the dataset,
Table 11: Cosine-powee poweer Decay on ImageNet: training losses and validation accuracy (%) of different schedulings for ResNet- 18 over trials. Settings #Epoch only have trial due to constraints of resource and time.
Training loss
Top-1
Top-5
#Epoch
Schedule
validation acc (%)
validation acc (%)
Cosine
5.0085510.0000
30.01:10.21
Cosine
5.4330=20.1066
26.43=0.31
50.85++0.43
Cosine?
5.4939:t0.0157
21.81:00211
44.53::0.09
Cossne
2.9515=10:007
57.27:10.15
80.71:1:0.12
5
Cusine 2.8389
$5.67:10.08
79.46.1.0.16
Cosine? 2.9160:10.0099
52.75:10.20
77.11:10.08
Cosine
2.1739::0.0046
67. 07.56=20.03
87.82:10.09
30
Cosine 2.0402:10.0031
67.97=10.10
88.12::00.03
Cosine 2.0525:0000322
67.41:20.05
87.70=t0.10
Cosine
1.9056
69.85
89.46
Cosine
1.7676
70.46
89.75
Cosine
70.42
Cusine
1.7188
71.37
90.31
Cosine
1.5250
71.69
90.37
1.50
cosine-power-2
1.25
cosine-power-1
log(leaming rate)
leam ng rale
1.00
cosine-power-0.33
10
0.50
cosine-power-2
10
0.25
cosine-power-1
cosine-power-0.55
0.00
10
100000 200000 300000 400000
100000 200000 300000 number of iterations
number of iterations
Figure 7: Learning rate curve of three cosine-power schedulers. Top: original scale; Bottom: log scale.
18

---

Published as a conference paper at ICLR 2022
A.8
FULL FIGURES FOR EIGENCURVE EXPERIMENTS SECTION 4.2
Please refer to Figure
10
and
13
3.00
0.95
Everse-iims decay
inverse,ame decay
2.75
decay
9.90
alep-deray
general iitt--decyy
general-step-duee
cosina-deray
0.85
cosine-decay
tain losa
2.25
gencurve
0.00
eigencurvv
0.75
1.75
0.70
1.25
500
1000
1500
2000
2500
3000
3500
500
:000
15000
2000
2500
3000
3500
number of Ieerations
number Iterations
Figure 8: CIFAR-10 results for ResNet-18, with #Epoch 10. Left: training losses. Right: accuracy.
2.75
train 8055
2.25
0.80
0.75
1.75
decay xtp decay
decay step decay general-ezep-decay cosine-decay elgencurve
0.70
genaral seall-ste-decce
casine-decce
0.65
elgencurve
1.00
3.60
1000
1500 2000 2500
5000
3500
500
1000
1500
2000
2500
3000 3500
number of meretonn
number Iterationn
Figure 9: CIFAR-10 results for GoogLeNet, with #Epoch 10. Left: training losses. Right: test accuracy.
Inverse-timeddee decayy
2.75
step-deray
general-step-decay
cosins-decay
Brain Joss
2.25
9.00
wigencur ve
2.00
0.75
1.75
decay step decay
0.70
1.50
generel step decey
cosine decay
3.62
eigencurve
1.00
0.60
1000 1500
2000
3000
3500
500
1000
1500
2000
2500
3000
number of Ieeeeiro
number Iterations
Figure 10: CIFAR-10 results for VGG16, with #Epoch 10. Left: training losses. Right: test accuracy.
19

---

Published as a conference paper at ICLR 2022
Inverse-imeedeca deiasy
0.975
general-step-dese
0,950
cosine decay
trann loss
0.6
stop dacay
vvars--ima-ddeaa
0.925
eigencurve
general--tenederray
0,900
cosine-decas
0.4
gencurve
0.875
3.850
0.2
9.825
0.0
0,80
5000
10000 15000 20000 25000 30000 25000
5000
10000
15000 20009 25009 30000 35000 number of terations
number Itarations
Figure 11: CIFAR-10 results for ResNet-- 18, with #Epoch 100. Left: training losses. accuracy.
Right: test
0.975
0.8
train loss
0.6
step desay
Aire decay
0.92%
step-detay cesine decay
0.4
gencurve
0.875
inverse dime-decay step-decay gereral-step--eecny cosine detay eigencurve
0.850
0.2
0.825
0.0
9,000
5000
10000 15000
20000 25000 30000 25000
5000
10000
15000 20000 25000 30000 35000 number of terations
number iterations
Figure 12: CIFAR-10 results for GoogLeNet, with #Epoch 100. Left: training losses. Right: test accuracy.
1.0
1.000
ir everse-time-deccn diccy
inverse-imeedenn decay
diecey
3.975
decay general stteral-stepdee sell-stteedaaaaa decay
0.8
general step stea-decay decey
3.950
Drain loss
0.6
www.w
gencurve
0.925
eigencurve
0.4
0.875
0.825
MN
3000
10000 15000 20000 23000 30000 35000
5000
10000 15000 20000 25000 30000 35000 number of terations
number Itarations
Figure 13: CIFAR-10 results for VGG16, with #Epoch 100. Left: training losses. accuracy.
Right: test
B DETAILED EXPeriMENTAL SETTINGS FOR IMAGE CLASSIFICATION ON CIFAR-1O/CIFAR-I1
B. BASIC SETTINGS
As mentioned in the main paper, all models trained with stochastic gradient descent (SGD), no momentum, batch size 128 and weight decay wd = 0.0005. Furthermore, we perform grid search choose the best hyperparameters of all schedulers, with validation set created from 5,00
20

---

Published as a conference paper at ICLR 2022
samples in the training set, i.e. one-tenth of the training set. The remaining 45, 000 samples are then used for training the model. After obtaining hyperparameters with the best validation accuracy, we train the model again with the full training set and test the trained model test set, where 5 trials of experiments are conducted. The mean and standard deviation of the test results are reported.
Here the grid search explores hyperparameters ?o E (160, 0.3, 0.2, 0.1} and Mmii {0.01, 0.001, 0.0001, 0, "U,,"""U "UNRESTRICTED"), where ?oo denotes the initial learning rate and Mmin stands for the learning rate of last iteration. "UNRESTRICTED" denotes the case where 7mmn is not set, which is useful for eigencurve, who can decide the learning rate curve without setting Mnnin- Given ?7u and Mmin. we adjust all schedulers as follows. For inverse time decay, the hy- perparameter is computed accordingly based on 170 and Mminn- For cosine decay, To and Maiia is directly used, with no restart adopted. For general step decay, we search the interval number in f3, 4,5, [log JJ [log TJ + }} and decay factor in (2, 5, 10]. For step decay proposed in Ge et al. (019),, the interval number is fixed to be [log Tj. along with a decay factor For eigencurve. two major modifications are made to make it more suitable for practical settings:
1/L
770
Th
1+
2i=1
2,20
2
4--
1+
1 4,
gi-1 (t (1-11-1)
Here change 1/L. to no so that it is possible adjust the initial learning rate of di eigencurve. We also change the fixed constant 2 to a general constant B > 1. which is aimed at making the learning rate curve smoother. The learning rate curve of eigencurve is then linearly scaled to match the given T/min.
Notice that the learning rate i/u can be larger than 1/L, while the loss still does not explode. There are several explanations for this phenomenon. First, in basic non-smooth analysis of GD and SGD with inverse time decay scheduler, the learning rate can larger than 1/L if the gradient norm is bounded (Shamir& & Zhang] 2012). Second, deep learning has non-convex loss landscape, espe- cially when the parameter is far away from the optima. Hence it common to use larger learning rate at first. As long as the loss does not explode, it is okay. So we still include large learning rate To in our grid search process.
B.2 SETTINGS FOR EIGENCURVE
In addition, for our e gencurve scheduler, we use PyHessian (Yao et al. 2020) to generate Hes- sian matrix's eigenvalue distribution for all models. The whole process consists of three phases, which are illustrated as follows.
1) Training the model Almost all CNN models on CIFAR-10 have non-convex objectives, thus the Hessian's is eigenvalue distributions are different for different parameters. Normally, we want the this distribution to reflect the overall tendency of most parts of the training process. According to the phenomenon demonstrated in Appendix E, figure A.11-A.17 of Yao et al. (2020), the eigenvalue distribution of ResNet's Hessian presents similar tendency after training 30 epochs, which suggests that the Hessian's eigenvalue distribution can be used after sufficient training.
In all CIFAR-10 experiments, we use the Hessian's 's eigenvalue distribution of models after train- ing 180 epochs. Since the goal here is to sufficiently train the model, not obtain good perfor- mance, common bascline settings are adopted for training. For all models used for eigenvalue distribution estimation,
adopt SGD with momentum wd = 0.0005 and initial learning rate 0.1. On top of that, we use step decay, which decays the learning rate by a factor of 10 at epoch 80 and 120. All of them are default settings of the PyHessian code (https:/ https://tii //ggttuubbb....// com/ ami r httph///w//...eessaaaaa////a/aaa
0.9, batch size 128, weight decay
py] commit: f4c3f77).
ImageNet adopts similar setting, with training epochs being 90. SGD with momentum = 0.9, batch size 256, weight decay wd 0.0001, inital learning rate 0.1 and step decay schedule decays learning rate by a factor of 10 at epoch 30 and 60.
2) Estimating Hessian matrix's eigenvalue distribution for the trained model After obtaining the checkpoint of sufficiently trained model, then run PyHessian estimate the Hessian's
21

---

Published as a conference paper at ICLR 2022
eigenvalue distribution for that checkpoint. The goal here is to obtain the Hessian's eigenvalue distribution with sufficient precision. To be more specific, the length of intervals around each esti- mated eigenvalue. PyHessian estimates the eigenvalue spectral density (ESD) of a model's s Hessian, in other words, the output is a list of eigenvalue intervals, along with the density of each interval, where the whole density adds up 1. Precision means the interval length here.
is natural that the estimation precision is related to the complexity of the PyHessian algorithm, e.g- the better precision it yields, the more time and space it consumes. More specifically, the algorithm has a time complexity of (NNndd) and space complexity O (BBd + n,,d), where d is the number of model parameters, N is the number of samples used for estimating the ESD, B is the batch size and ny is the iteration number of Stochastic Lanczos Quadrature used in PyHessian, which controls the estimation precision (see Algorithm of Yao al. (2020))
In our experiments, we use = 5000 for ResNet-18 and = 3000 for GoogLeNe/VGG11, which gives an eigenvalue distribution estimation with precision around 10-5 10-4, 4, N and are both set to 200 due to GPU memory constraint, i.e. we use one mini-batee to estimate the eigenvalue distribution. turns out that this one-batch estimation is good enough and yields similar results to full dataset settings shown in Yao et al. (2020).
However, space complexity is still a bottleneck here. Due to the large number of n, and space complexity O(Bd + n.dd of PyHessian, the value of d cannot be very large. In practice, with NVIDIA GeForce 2080 Ti GPU, which has around 11GB memory, the maximum acceptable pa- rameter number d is around 200 400K. This implies that the model has to be compressed. In our experiments, we reduce the number channels by a factor C' for all models. For ResNet-18 C c= 16. For GoogLeNet, C 4. For VGG16, C 8. Notice that those compressed models only used for eigenvalue distribution estimation. In experiments of comparing different scheduling, we still use the original model with no compression.
One may refer to
wwtp:ueedddsttttuuudeee for generated eigenvalue distributions.
3) Generating eigencurve scheduler with the estimated eigenvalue distribution After ob- taining the eigenvalue distribution, we do preprocessing before plug it into our eigencurve scheduler.
First, we notice that there are negative cigenvalues in the final distribution. Theoretically, if the parameter right at the optimal point, no negative eigenvalues should exist for Hessian matrix. Thus we conjecture that those negative eigenvalues are caused by the fact that the model is closed to optima w., but not exactly at that point. Furthermore, the estimation precision loss can be another cause. In fact, most of those negative eigenvalues are small, e.g. 98.6% of those negative eigenvalues lie in [-0.1, 0), and can be generally ignored without much loss. In our case, we set them to their absolute values.
Second, for a given weight decay value wd, we need to take the implicit L2 regularization into account, since it affects the Hessian matrix well. Therefore, for all eigenvalues after the first step, we add wd to them.
After preprocessing, plug the eigenvalue distribution into our eigencurve scheduler and gen- erates the exact form e eigencurve.
1/L
170
1/:
2
A 23
+ 2
(t 1-11)
1 +
2jj j= A
31-1 (t
(;-1
For experiments with 100 epochs, we set 8 = 1.000005, so that the learning rate curve is much smoother. For experiments with 10 epochs, we set / 2.0. In our experiments, serves fixed constant, not hyperparameters. So no hyperparameter search is conducted on 3. One can do that in practice though, if computation resource allows.
22

---

Published as a conference paper at ICLR 2022
B.3 COMPUTE RESOURCE AND IMPLEMENTATION DETAILS
All the code for results in main paper can be found in hot.eeeee2..5ttt/.ooooo.eeeeee. MIT license.
com/
which released under the
All experiments on CIFAR-IOCCIFAR-I00 are conducted on a single NVIDIA GeForce 2080 GGGG takes around #0mins990mins40mins to train 100 epochs, respectively. High-precision eigenvalue distribution estimation, e-g. n, 2 3000, requires around 1-2 days to complete, but this is no longer necessary given the released results.
Ti GPU, where
The ResNet-18 model is implemented in Tensorflow 2.0. We use tensorflow ansoorlow-gpuu 2.3.1 in our code. The GoogLeNet and VGG16 model is implemented in Pytorch, specifically, 1.7.0tcu101.
B.4 LICENSE OF PYHESSIAN
According
to
https: htt///gttttt cow com/amirrhoo ami http::/h...../......a///a//a/aaa
LICENSE
PyHessian Yao et al. 2020) is released under the MIT License.
C DETAILED EXPERIMENTAL SETTINGS FOR IMAGE CLASSIFICATION ON IMAGENET
One may refer to httpt::///ww/t image-net.t.... www.:etl..or//wwoooo/oooo for specific terms of access for ImageNet. The dataset can be downloaded from htt ntttps: htt//mmaee-aae net. .ore cha lenges/ LSVRC/2012/ 201222012 2012-dowwlmmmm cads. php) with training set being "Training images (Task & 2)" and validation being "Validation images (all tasks)". Notice that registration and verification of institute is required for successful download.
ResNet- 18 experiments ImageNet conducted two NVIDIA GeForce 2080 Ti GPUs with data parallelism, while ResNet-50 experiments are conducted on 4 GPUs similar fashion. Both models take around days to train 90 epochs, about 20mins -iminss-3mins per epoch. Those ResNet models on ImageNet are implemented in Pytorch, specifically, 1.7.0 1.7.0+cu101.
D IMPORTANT PROPOSITIONS AND LEMMAS
Proposition 3. Letting (xx be a monotonically function the range (oo D then holds that
Σ f(t) S I f(x) dx.
i-1
(D.1)
k=
If fz) is monotonically decreasing in the range [tu, E). then it holds that
H-1 S. ((x) dr E(() S E10) 100 f(to) + (( f(x) dr.
(D.2)
k=ta
k=to
Lemma 2. Function [(xx) ex)(-oa)=² with 0 < a and x E (0, 1 is monotone decreasing in
the range (2, +00) and monotone increasing in the range x [0, 21.
Proof. We can obtain the derivative of / fxx as
oz)). Thus, holds that (z(x) 2 0 when x E [0, 2). This implies that f fxx is monotone increasing when
Vʃ(x)
I E [0, 2.. Similarly, we can obtain that fxx is monotone decreasing when z E (2, +00).
Lemma 3. It holds that
f exp((oax) dx - (xex((oxx) +a eep((-ar)).
-a
(D.3)
23

---

Published as a conference paper at ICLR 2022
Proof.
exp(-aax)x dr= = - aa / x dexp(-ax) = -a - (xexp(-ax) - -f
= (x ax) + ta (r-ppp((aaa))
E PROOF OF SECTION 2
Proof of Proposition 7 By iteratively applying Eqn. 22. can obtain that
R (> (12+1. Wos) 2
21) 2 >3 (wis 3)
1=1
+X302 Σ
II (1 m,.d)))
k-1 1i
2 ,u - w2
1 (k + 1)2
1
+
(t+ 1)2
(t+ (++1)²
(Is + 1)2
kml
X, (w1 - w ++
+ (t 11²
.2. 0².
Summing up each coordinate, we can obtain the result.
Proof of Proposition
Let us denote of =230². By Eqn. 2.1 we can obtain that
E X (we+1. - 2
<11 (1- - mp.ddj} N,(W1s - w2,))++
11 x1 - m
k=1
<exp
2
naidd//
22( w2ns) +
Σ exp
Mi.jdj
2 o
i=1
km/
im
1
exp
-2
>1(W115 - w.
exp
-2Xj
Σ
+ ui)
L + pi
i=1
i=k
2X In
1 + 11
I + (++++a ) 25(111 -wa,)² +
(2dj In
[ ++tuk juk)
[ jut ))
<exp
exp
14
(L + 2k)
1=1
221
24y
T. + 4
(I. + juk)
>y(w1s - -wa,)² +
L + jt)
221
3
k=1
(L + jut)
24 >y(wis -waa)²
2h
L+
03
(L + jut)
-1
of
T jul
2d 1
(T. 1ul
(L + pt)
2h1 #
+ 1 L jt)
1
03
25(111 - w2,))2 ww,)) + 2xj - 1 + jt
o3
(L+ + μat
The third inequality is because function F(x) = 1/(1. (I. + ur) [1, oo), and it holds that
monotone decreasing in the range
1
1 In
L +tt L puli
di
L uu
Ji=k
L pú
l
24

---

Published as a conference paper at ICLR 2022
The last inequality is because function F(x) (L / 22y/m=2 is monotone increasing in the range [0, oo), and it holds that
23 Σ L + pk)
$ 1"
(L+ ph)
23
dkk (L + ut)
23
22
k=1
((+t)))
(u)) ut)
23
24. 11)
+ (L ul) -
24, -1)
1
2 - (I. nt) 23
+ (I. + jut) -2
By μ S 03 X30?. and summing up from i d. we can obtain the result.
F PRELIMINARIES
Lemma 4. Let objective function fx) be quadratic. Running SGD for Ttsppp starting from wa and a learning rate sequence {T, 1==1, the final iterate WT+1 satisfies
17
E [WT++1 w-) H(WT+1 -w,)]
=
[ww w+) Prr... ... PoHPo ... Pr (wo w-)]
(F.I)
T
E m Pr... Pr+ HP++1... ... Pr Pr.n7]:
where P. = I H.
Proof. Reformulating Eqn.
1.5
we have
W++1 W. =w: (E))((E):; b(E))
=w - W. Te(Hu wt b)) + 1t. (Hw:
w; - b(g)))
The mHHH: - b- (Hw, - b)) + n (Hw, b- (H())); b(E))
= (1 - 11 (w, - -w) + 7e
=P.(w- w.) + Tp-
Thus, we can obtain that
Wr+1 - W. = Pt... Polwo -w.) +
Σ P.... Pr+1
(F2)
r=0
We can decompose above stochastic process associated with SGD's update into two simpler pro- cesses as follows:
wh 2++
(r wa), and wf41 w. =P.(w) w.) + mete, with wy Wa, (F.3)
w.
which entails that
w P.... Po(wù w.) Pi w.)
h
(F.4)
wh+1
Σ Pr ..... 1,410 Σ P:+1... ... Pmn +=0
(F.5)
==0
32
Wy+1
W4 (w/+1 w.,) ) + (wi+1 w.)
(F.6
where the last equality in Eqn.
F.4) and Eqn. F.5) because the commutative property P,P.- = (I t HT T/ H) up n H Per P. holds for Vl,
25

---

Published as a conference paper at ICLR 2022
Thus, have
[WT+1] - w.) ".."..HTTTTH
(WT++1 - w.))
E [wu+1 ww.) "..)"Huur H( w.) + 2(2 -w.) H(w w.)
(wir+1 -w.) (ww++1 w.]l
24
[(ug] w.) Po Pr(wβ w.) + 2(w - -w.) w.)'HPP ... Pr(wg w.)
+ +wT++1 -w.) H( (( ww.]
E [uug -w.) PollPo... w.)
2
Pr ... Pr-1 Σ
HPo HPP...Pr(uß w.)
r=
Σ 7=0
Pr Pr P1+14/7117
H Pr.... Pr....r+iTTn
(==
[(ug] w.) "T.)TPr.P. Pr...P P.....r w.)]
+E
Σ
!|d n Pr... .... Pr+1 H Pr+t... PTn..
T=0,7'=0
=E [wn w.) Pr... PoHPo Pr(wg w.)]
E [
Pr. P+ Pr mr.
where the last equality is because when and r' are different, it holds that
Bin Pr... Hr+1 Pr n.l 0
due to independence between n, and Ryt.
Lemma 5, Given the assumption that Beg [nin.] 3 ²2,, then the variance term satisfies that
Σ
E [n P HP ... Pr. nr.nn] < 02
Σ m
II (1 n,2z)² (F.7)
T=0
k=
i=k+1
where P. =I II= H.
Proof. Denote A, ......+HHH, then
A = (Pr... P.. - (Hz) PT ........ P.. - -H.P.41...PP
(F8)
where the second equality is entailed by the fact that H Prtty..., Pr are symmetric matrices.
26

---

Published as a conference paper at ICLR 2022
Therefore, have,
T
B n T .r....P4.ll.. Pr1.H .p. Pr.
==0
T
B n T A, A n+]
Σ
E tr (n, A,A, n.)l = Σ B [tr (ATm,nTAA))
==U
T=0
T
7 (E
[A,
Ar)
Σ
1tt (A
[n. Ar)
T
T
<0²
Σ
ftr (A, = 02 Σ
1 (A,
r=0
7=0
T
Σ
tr PriiHPrt Hr
T=0
Σ
II (1 (1- i=k+1
O=
where the third and sixth equality come from the cyclic property of trace, while the first inequality is because of the condition Eg [nen,]] 3 o²H, where
Ya. x Elu-m J 0oxx Hx.
vz, =T A T. n |A,= (A+2) ((n =( -22T HA,
B A 3 2 HA,
tr 1A,) s ar (A) HA,).
Lemma 6. Letting >; be the smallest positive eigenvalue of H, then the bias term satisfies that
E [[wo ww)) Pr... PoHPo... Pr (wo w-)]
S(wo w.)) H w.) exp -21g
7k
(F.9
Proof. Letting H = T be the spectral decomposition of H and uj be j-th column of U, we obtain that
E (wo w.) .r... PoHPo Pr (wo w-)l
Aj (u,] (wo -w.))²
II (1 k=0
(1-m)) nz2y)²
T
Σ Ø=1
Aラ [u]] T (wo w.)) exp
-2xj
k=
Since Xラ is the smallest positive eigenvalue of H, it holds that
d Ag (w] .exp
T
T
exp
-2g
Σ
Xj (u] (wo - w.))² exx
-21
Σ
7/k
k=
j
k=0
T
=(wo w.) H(wo - -..) expp
-21
Σ
1/k
k=
27

---

Published as a conference paper at ICLR 2022
G PROOF OF THEOREMS
Lemma 7. Let learning rate is defined in Equ. T, the sequence Vir satisfies that
3.3
Assuming & E (1) with sis
141-1
1
a
TJ
2 26-1
In
0:-1
In
av-1
20-11(( (11
(G.1)
1=k
1=/+1
where 0n is defined
j=1 a₁
- L p
Σ
2,20-1=
1
(G.2)
Th
Proof. First, we divide learning rates into two groups: those who are guaranteed to cover a full interval and those who may not.
4
4-1
Σ t=
T==
Σ
The
m==
m=
Σ
t=yy
t=
i=
t=t,
Furthermore, because 7/t is monotonically decreasing with respect f, by Proposition 3 we have
i+1
nett + 1." nidt
1=141
7+1
dt
L+ j==1 2,20 1 22--1122--11 1:-1p(t - f(-1)
1=
j-=1 2,20-1 22' ((-11 dl
L
1
1+1
L Σ 2,20-1 2 uu(t; 1;-1)
1
21-14
1+ 4,20
1=7+1
L L 1+ A,20
u(te 4-1
In
2111
L + 11 اj D A 1u(k (1-1)
7+1
E+ 4,20-1
Σ
In
24-14
L Eド 4,21
1=/+1
L 1 Σ 2,2 20
2 2--1 ln
L+ 1j=1 2,21 2 11ckk 11-
7+1
a²
In
In
2 4
21
2 1u 11-1)
a:
0v
$=/+1
Lemma 8. Letting sequence {ai} be defined in Eqn.
G.2 given 5 it holds that
21-1+27
01-1
2
142
(a. + 2 11(p (--1) 2i-12-2
a
aj
1=1
j=++1
k=h-1
(G.3)
1+1
i+1
2i-s+2
1
aj-1
2
gi-1t2-1
-2i-112
<2
a
-0,11
2
#=++1
0jj
28

---

Published as a conference paper at ICLR 2022
Proof. Notice that g(k) = (as-1 + 22-+/1( 1111))² 12)1))2-113-2 is monotonically increasing func- tion, we have,
21-3+2
fi-1
aj-1
2 i+2
(at-1 +2-1
-((k u(k 1)-1)) 11-1))2
k=4-11
21-312
aj-1
2 it2
- 1))
0
02
14-1
2--5+2
Pj-1
2
((2- 1) 1) 11) (a²
//-11-311 2i-142-1
00
ai-1
21
03-1
2 21-42 42
2i-112-1
2i-1+2-1
00
(2i+1 22-11)1 1)ps
IME
21-
1
2--
2i-1+2-1
9
(20+1 - 2
ai
-;-1
24-J+2
112
1
22
i12_1
27 112_1
2i+1 11
1
1
a
a
8-1
2111+2
2
21-
a
Oj
2 3127
Øj-1
21-1+2
2-1112-1)
211-
0
0
ai
2
aj
Lemma 9, Letting {as) be a positive sequence, given 1 & ā, it holds that
27-++2
aj-1
a
2
0,-1 a;
21-142-1)
-2--142
S a i+1'
-1
(G.4)
Proof. First, have
1+1
24-5+2
aj-1
2 1-422_1
2i-it2
21-12
a.
a,
0jj
jiitl
2i-142
2--12_11
aj
0
0j
a
2
212
21-1
0j-1
0j-1
0
24-142
i+1
2i-512
i+
i+1
21-1+2
0j-1
05ー1
0
aj
aj
21-+2
29

---

Published as a conference paper at ICLR 2022
2--
Furthermore, we reformulate the term Σ
[[
a--1
0 as follows
1=1
aj
itl
2'-1+2
G+1
21-3-2
2'-141
0/-1
aj-1
04
a
(G.5)
aj
a(+1
1mi+2
2+1
2
2 2i-it1_1
0--1
(G.6)
27-141
jj
1
2--122
27 1
0j-1
(G.7)
0j
2 +2
2
0j-1
(G.8)
jj
0
21-1+
Combining above results, we can obtain that
22-+22
2/-142-1
0;-1
a,
02
27 21-
21-142-
0r-1
Ojj
f=++1
i+1
24-
2
0j-1
aj
2411+
-=
[+1
2i-1+2
1
a--1
aq
a 2
aj
1=2
<a-
141'
Lemma 10. Letting us denote 1tt A Σl k= nh Ii (1 -nndds with ni defined in Eqn. 3.3
for 1 < tt S l, it holds that
er < max(ves; me/
(G.9)
Proof. If Ut41, I max(" //>,)) holds for Vt 2 1, then it naturally follows that
Je S max (V-11 nV-1) < max 22 ), A3
NM-2 7 ))
1/c X,"
AU-2 TW-11 Aj
< max
Ut.j
Aj
Vt. T/t X,
max
where the last equality is entailed by the fact that t < and n, defined in Eqn. 3.3 is monotonically decreasing. We then prove 0441. max(vi. (e/ holds for Vt 2 1.
30

---

Published as a conference paper at ICLR 2022
For Vtt 2 1, we have
(1 n:
k=
1-1
-1
1
II
- 7;
(G.10)
k=
k=k+1
-1/
2 + (1 nイ> 3
1/2
2
II (1- m,,1 1=k+1
k=
- + (1 ni ne>g) ) vts
1) If 0141,j I Ut.j. then it naturally follows r1+1, I max(v 1//2))
2) If Ut+1. > Vz.. denote a (1 (1-mmA,)) 2b A m/. have v4+1.5 avr + b, where [0,1) and 2 0. It follows,
Utti. Ut.j
avi, + Ut
b
Utd 1-
b
Ut+1j = avt,j
b < a
+
1 - a
a
Therefore,
11ē
1- (1 d
1)t
T
Utii < 1-a a
< max
Ur
1 1 (1 )3
1)11))
X
where the second inequality is entailed by the fact that 1 nedg [0, 1).
Lemma 11. Letting Vt, be defined as Lemma 10 and index ī satisfy X9 E [4c 24 U4 has the following property
p. 2 then
7711
ot W S 15
(G.11)
X2
Proof. By the fact that (1 x) < exp(-2) we have
<
exp
-2 E
nod;
nh.
k=0
#=k+1
Setting / 4441 1 in above equation, we have
-1
2 1
exp
Σ
nh-
(G.12)
k=0
w=
31

---

Published as a conference paper at ICLR 2022
Now we bound the variance term. First, we have
f12-1
2 411-1
f1111
5
5
Σ exp
Σ
1/
Σ
exp
2
Thd
exp(2nn
1=++1
t=k
444
-1
f141 -1
22g
exp
-
Σ
exp
2
L
0=0
t=k
1:+1-1
< exp(2)
exp
-2
T1dg
2
k=0
t=
where the first inequality is because 77 1 L. Hence, we can obtain
h41
1
Σ
exp
-2
Σ
ntdy
K=
(=
4+1-1
4:4111
Sexp(2)
exp
-
Tody
Tik
2
k=0
t=k
i+1 4-1
li+1 11
= cxpp(2)
exp
2
Σ
Mids}
n
km
Am
Furthermore, combining with Eqn.
G.I and the condition dy E juc 23, 12- 2(t1), we can obtain
l -
i+ 4-1
l
exp
2
Σ
11
Σ
exp -2
Σ
Tell 2
mh
1=
t=k
f=1
k=tı-
t=k
7+1
exp
2
2--1+1 In
aj -2 2. 2.22- In
0;-1 + 2 1i-1 - t
ai
0j-1
1
1=1
i+1
+ 2 In 0;-1 + 2' 2--11((k ti-1)
exp
Σ
2
2i-
In
0j-1
1k
2
0jj
Oi
22-122
2
0;-1 + 2' ju(k k (1-1)
0j-1
m
aj
a₁
|=++1
2i-s+2
4-1
0j-1 + 24- 1u(1 1 (4-1)
2i-
9--1
7
ajj
k=1-1
2--5+2
0--1
aj
0:-1 + 2i
2:-1
-(a--t) tq-1)
21-142
i-1
-2
L L+ p Σ 2 + 2
+ 2 to-1)
04
i+1
2i-1+2
aj-1
Ojj
2-112 :12
Σ
0:-1 + 2
pl(k
((kk) 1(-1)
(ai- 12-1+2-110 u((k -(-1)) -2
12--1u(k
k=t
32

---

Published as a conference paper at ICLR 2022
27-1+2
aj-1
22
O3
gmi+1
(a + 2 pl(k - 1)-1)) 2)- 2/-
22-1 uu(h - t(-1))
k=4-1
2--1+2
aj-1
22
(0+-1+2"
+ 2 "p(k- 1i-1) )) 2)
k=t
2 3127
Oj-1
2/-143 - (111 -2i-143
a
a,
21+1 1
jj
i=1
7i+1
2
2 y
i41
where the last inequality is because of the condition Xg E L 2", n 2i+1) and the definition of oz. Therefore, we have
Mh41 Ue S 22exp(2).
< 15
Ag
Lemma 12. Let objective function f(x) be quadratic and Assumption 1.7 hold. for Tteeps starting from we and a learning rate sequence 12' iterate wr+1 satisfies
Running SGD
defined Eqn.
3.3). the final
E [[WT+1- w.) H -w.]] S(wo -w.) H(w w.) exp
22p
T|k
Jmax -
2 s;
+ 150 r
L
L+
4,20
2+1
Proof. The target of this lemma is to obtain the explicit form to bound the variance term. By the definition of Ut41. in Lemma 10 we can obtain that
E
T Pr... P P ... Pr n
UT+1.
Mart
max
A
j=1
d
741111
74 141111
max
15
j=1
Imax -1
150
Xj
1tt S 1502
$ 1502
p
2
87 777117
j=1
j=1
7=
where the last inequality is because Ag [2'nu, 2 p1) and there are 83 such Xy's lie in this range. By Eqn. (3.3) we have
11141
(G.13)
b+ Ei 2
33

---

Published as a conference paper at ICLR 2022
Therefore, have
mun
2
Σ E [ Pr.... Prt1 ... Pr nz] S 150
(G.14)
L L+ - 2,21
T=0
Combining with Lemma and Lemma 6 we can obtain that
T
E [WTT+] - w.) "H - w.)] S(w0 - w.)" H(w w.) exp
-211
k=0
maax
2 83
+ 150 μ
L pa Dj=1
2
1=0
Lemma 13. For Vt 2 O, the learning rate sequence {n:)i=1 defined in Eqn.
3.3
satisfies
ne S
(G.15)
L + pt
Proof. For Vt 2 0, there Bi 2 1, where E (.). Given the form defined in Eqn. 3.3 we have,
" D f-1 2,20 2 22-1 pl(t 1
1
1+ E Aj + plll - 4111)
1+ (t. -1-1) + plt - t
1
L 1+p((t_111 - to) + plt - 1
L+ ju(t - to)
LL+ jut
Lemma 14. Let objective function f(x) be quadratic and Assumption for T-steps starting from we and a learning rate sequence {Te)² defined in Eqn. 3.3). the final iterate WT41 satisfies
L.7 hold. Running SGD
n²
E [WT+1 w.) HH)T++ -w.)] S(wo w.) H H(wo w.)
A7
Imax -1
2i+1 b3
+ 1502 4
i+1 2,21-1 L I+
7
Proof. The target of this lemma obtain the explicit form to bound the bias term.
34

---

Published as a conference paper at ICLR 2022
First, by Eqn. (..I)
and the condition X, E [K 2", 1 22t1), we have
1+1 -1
i+1
a3
exp
22,
?l
S exp
-
ThA
I exp
In
M1
2
a9-1
i+1
2i-142
exp
2 2
142
In
0j-1
(G.16)
0i-1
ai
i+1
0i-1
01
1,2
M1711
O4
01+1
i=1
For >3- = since μ E [1- 2¹, p 1)+1) for = 0, it follows,
exp
2/ k=0
T
77
L
G.15
+ ptl
3.4
L
2
A
R²
(G.17)
Combining with Lemma 12 we obtain that,
R² E [WT++ - -w) H"TH((+++ - -w.)] 5(w0 -w,) Hww w.)
A
max
2 sg
150 P
i+1 2,21 1
1=0
G.1 PROOF OF LEMMA
Lemma 1.
Let objective function fx) be quadratic and Assumption (17 hold. Running SGD for T-steps starting from we and a learning rate sequence {n 1T WT+1 satisfies
defined in Eqn. 3.3.
the final iterate
x²
15
Imax -1
2 87
E. [f([+++) - f(wa)] <(S(wo) - [(ww))
02
A
L
L+
2,21-1
i=u
(3.6)
Proof. For Vt 2 0, we have
f(w)) (w.
1.2
2 w. H()) b(E) ((E))
1
E
[ T H())w. -(E)TTT w/
w
wi E[H(E))w: -E((EE) We
1. E[H E(((E)] w.
mi T Hw: bT bTwe))
w. T Hw. bT bTw..)
bT H-26 1 TT (11)² $b b--b
wi T Hw:, - bT We
1 1TTH-1 - DTH-1D)
w/ H bT we -Teee)
H - bTw:
We
+
6T H
2
2
w. H b Wi
T Wi
+ T -
2
2
2
35

---

Published as a conference paper at ICLR 2022
1i H Hw;
1
b
1
T
+ b 11 11
1
2
2
2 Wi Hw:
2 1 Hw,
1
w. T Hwr + w. Hw,
2
2
2 (w) w.) H [1 w+),
where the 5th equality is entailed by the fact that H H is a symmetric matrix, and the 9th equality uses both H H and Eqn 1.4
Combine the above result with Lemma 14
we obtain that
B[f(wr+1) f(c.)) ((f(wo) f(w.))
R²
+
15
0² p
max
Σ
2 $
A
2
L + 11
トΣ 2
i+1
i=0
G.2 PROOF OF THEOREM
Theorem 1. Let objective function fxx) be quadratic and Assumption Ttsepps starting from wo, a learning rate sequence {n= defined in Equ. Eqn. (35), the final iterate WT41 satisfies
1.7 hold. Running SGD for
3.3 and D defined in
n²2
(E/m
Imax i=0
15
Σ
i=0
Imax
Via
2
E [f(T++)) f(w-)] S(f(wo) f(w.))
0²
8o7
T
Proof. We have
Ianx
2 st
Iuax
2
2 8/
3.5
Taax
Sj
</
0=0
L 14
j==1 ,
i=0
122
i+1
7=0
2
v
T
Imax -
Amase
2
Σ
Jmay -1
1=0
3
T
T
Combining with Lemma Jand the definition of A,, we can obtain that
x²
Σ
1=0
Imax-1 1
15
i=0
Tmax
V8
E [f((T++1) f(w-)] S(f(wo) f(w.))
G.3 PROOF OF COROLLARY
Corollary 2. Given the same setting in Theorem when Hessian H's eigenvalue distribution p()) satisfies "power law", i.e.
1 p(A) 7 exp(-<aln(A) - In(x))) Z
(4)
(3.7)
for some > 1, where Z = Stt (n/A)adx there exists constant C(a:) which only depends on such that the final iterate WT+1 satisfies
E E[f(wr+1) [(wa)) (I(w))) - f(ww))
x² do² T
+ -T]
C(aa.
36

---

Published as a conference paper at ICLR 2022
Proof. According to Theorem
|
E E[f(wr+1) f(w+)]
1²
[ Amar-1 -1
v
15
Σ
1=0
Amar
v
<(f(wo) -((w))
0²
$o
T
k
Imax-1 i=
Vii
2
do²
15
1mar-
Vi
2
=(f(wo) -((w))
T
50
T
The key terms here are C
Σ
Di=0
Imax
S/ so and C2 15
Jmax -1 Σ
ビi=0
Vs
/d. As long as
we can bound both terms with a constant C(a), the corollary will be directly proved.
1) If < 2, then there only one interval with Sp d. By setting C(a) max ( C2) 15, this completes the proof.
2) If K 2 2, then bounding C1 and C2 done by computing the value of s under power law. For all interval except the last interval, we have,
f22
3.1
A1y
E [p
2', 1.p.2% 2(+t))=
p(A)dA
1.22
2
11:2F/1
11
a dx
1
1.a0
1.
1-21
H22
yp
A
1
1.)
11
a
1.24
1.25
(x-- (2(+1)
1_ (2 )-)
(2t+1) 1-a
11-00 (2)) 1-o
(2 --a (2
1i-a x==aa
к-ーa 1
22-a -
-1(1-a)
xl a
Therefore, we have
21-a - kl-a d.
21-a
5; d- 2((-a))
2((1-a)
(G.18)
xl-a
holds for all interval except the last interval i' = Imax - = log, K 1 > 0. This last interval may not completely covers [n 2",, μ 22' due to the boundary truncated by L, but we still have
21-a 2
8y < d.
xI-a -
37

---

Published as a conference paper at ICLR 2022
It follows,
moox
2
2
max
d. 2 - 1
Amax
8/
<d.
24(1-a)
Σ
2
x 1--0-
kl-a
k=0
21-a
mmxx
i(a 11/2
=d 1 1-
2
1=0
2 21-a
1)/2
d 21 -1
<d
Σ
xl-a
2
kl-a -
1//-1)/2
0=1
1=0
2 -
2 21aa
2
=d.
K
2 1372
k kl-a-
1 -
221-a)/2
Thus,
Σ
V8i
d
2'
2 -11-20
x-
2
C1
80
d
2 21-0-1
20(1-aa
2(1 201-2)/2
x 1-
15
Σ
2iz i=
Imax-1
V
15
21-a -
C2
d
d
xl-a
1- 1-2(1-0)) 201-1/2
1 (2) (1)a-1
1
2
=15
1 (1) a-1
1
2(1-a)/2
<15.
1 2/1-
Here the last inequality for C2 is entailed by 2 2 and 1.
By setting C(a)) = max(C1,, = 15 (1-2(-113) we obtain
B[f(wr+1]) f(w:)]
x²
Σ
Ei=
Jmas -1
Vii
do
15
Σ
Ei=o
!maa -1
<(f(wo) f(ww))
T
So
T
x²
do²
-(s(wo)- [(w))
C
+
C2
T2
T
< (UF(w)) f(w.))
2²
do²
+
C(aa.
To
T
G.4 PROOF OF THEOREM 4
Theorem 4. Let objective function fxx be quadratic. We run SGD for T-sppps starting from we and
step decay learning rate sequence {n ) defined in Algorithm I of Ge et al. (2019) with m < 1/L. L. As long as (1) H is diagonal, (2) The equality in Assumption (1.7) holds, L.e. Ee [nm!]] =
a² H and (3) Ny (Wo.5 w.,)) # f Vj 1, 1,,....,d. d. the final iterate WT+1 satisfies,
(do²
E [f((T++)) - [(w)) 52
llog T
T
38

---

Published as a conference paper at ICLR 2022
Proof. The lower bound here is asymptotic bound. Specifically, require
T
o²
max 2 16, 256 minj Xj (Wo, - w.
(G.19)
log T
In Ge al. (2019), step decay has following learning rate sequence:
? 2
T log
T log (e+1))
1/:
if E
(G.20)
where é = 0, 0,1,,..,,ooTT"" 1. Notice that the index start from t = 1 instead of t For consistency with framework, we set set//o O, which produces the exact same step decay scheduler while only adding one extra iteration, thus does not affect the overall asymptotic bound.
We first translate the general notations to diagonal cases so that the idea of the proof can be clearer.
Since f(z) quadratic, according to the proof of Lemma D in Appendix G.1
f(WT+1) - f(ww) = (WT++1 w.) H(WT+1 w.).
Furthermore, according to Lemma 4 where P. P -,
E [WT++ w.) H (WT++1 w.)]
=E [wD w.)T. Pr.... PoHPo... ... .r. (wo - w.
T
+
n P .... ........PT.................. p7
0=
T
by (wo,s w.
II (1 11
1y(1 4 2B [m
k=
T=0
k=
T
T
T
Σ
Xy (wois - )
II (1 7222)²
+
1Tr
II m[1mm:)))2.. 2y0²
/=1
k=
T=0
J=1
k=7+1
T
d
= Σ Ny (wo.s - w 2
II (1
mh
II (1 - m)dd)) k=T+1
1=1
k=
T=0
Here the second equality is entailed by the fact that H and P. are diagonal, and the third equality
comes from Be [nan o²H. H. Thus, by denoting by - Xj (wo.j w.3)² T mmA,)) and
ΣT = 7 T (1 ?2 we have,
2/
E [[s(wr+1 [[w=)]
E. [[uT+1 w.) H(WT+1 w.]]
2
]
(G.21)
1
Σ bj
2310
2
To proceed the analysis, we divide all eigenvalues {A₂} into two groups:
log T
B B= {o]s
log
A
(G.22)
Smh T
8
where group A are those large eigenvalues that the variance term 25 will finally dominate, and group are those small eigenvalues that the bias term by will finally dominate. Rigorously speaking,
a) For Vj E A::
Step decay's ss bottleneck in variance term actually occurs at the first interval that satisfies
8T
20
Aym
(G.23)
log
39

---

Published as a conference paper at ICLR 2022
We first show that interval e is well-defined for any dimension j E A. Since j E A. it follows from the definition of AA in Eqn. (G.22.
log T
8T
A
X log T
1 2
8m/ T
On the other hand, since we assume T/ log T log T 2 16, follows
2 2
in Eqn.
G.19
which implies T > 2
ST Xym log
T
Aj T L
T
Apm
S
5
2 T-1
where the second inequality comes from 7n < 1/L in assumption (1), and the third inequality is entailed by X, I L given the definition of in Eqn. (L.6p. As result, we have
ST , log T
(20, 2 1-1
thus
8T
2
2 Aym log T
will guaranteed be satisified for some interval l 1,... .....,log?? T 1. Since interval is the first interval satisifies Eqn. (..23), we also have
87
167
2 Ay
2
Aym1
(G.24)
log
log T
Back to our analysis for the lower bound, by focusing on the variance produced by interval only, we have,
(++1)
log
T
M/ Σ
1/
II (1
1
Σ
m)
2g)
k=T+1
T=t Tog T
+1
k=T+1
((+1) Ing
Σ
1/
T
- 1h>m)
(E+1) T
71
2
II
T
(1 )));)²
T=) log
k= Tog +1
T=6 Tog
k= Tog
T
?/1 2
II
(1 n,)
log
T
E Tng T +1
T
1/1
(1 - m)2g)²
log T
Xym
16T
log
k=
T
log T
II
(1 m2)
256
2
k=E log
+1
log T
1
Σ
2m
1
log T
1
2
Σ
256
T
2
256
T
X
b=t Tog
T
+1
k=t
ToxTT1 T-1 (++1) Tox
log T
1 -
2X
256
T
X3
k=
40

---

Published as a conference paper at ICLR 2022
log T - (++1)-
log T
1
lox 2
7J1
2X
256
x3
2
kmD Tog T
log T-1
log 1
22j
Σ
T
71
256
T
X3
log T
2
i=
log 7
T
- 2xj
256
T
X
log T
2
G22
log T
1
T
1/1
4xg
256
X3
log
Xym1
ST
log T
log T' 1
256
X3
log T 1
512
X3
Here the first inequality obtained by focusing variance generated in interval & only. The second inequality utilizes r 2 { T/ log T. The fourth inequality is entailed by (1 a a1)(1 a2) 01 02 + a102 2 1 - di d2 for Va,, 02 E [0, 1]. where by mathematical induction, we can
extend this inequality for more terms Il (1 04) 2 Σi=1 a, long Σ a, S 1. The
fifth inequality comes from E T-
1/2 S 2i 1/2 = 1/22-1.
b) For Vj E B:
Step decay's s bottleneck will occur in the bias term. Since j E B, follows from the definition of in Eqn. G.22.
log T
log T
X
m, S
8m11 T
8T
we have
T II
bj => (wo. w
(1 )221)²
k=0
21, (Wo.) - -w,))²
Σ k=0
T
21/111
= Ag (woss way) (1-
20 (
T 11-220
k=1
log T-1 (1+1) T
-woo -w,s)²
1
Σ
27
1=0
k=
log T-1
(++1)
Tox T
(Wo. - -w,,)²
1
Σ
2
1m0
k= log
log 1
T
->y(wo, -w,))²
1 1/1 71
log T
2
2=0
T
2d (wo.j w. )
4m
log T
log T
T
2d (wo.j w. )
4
8T
log T
=} (Wo, - w. 2
2'
where the first inequality is caused by (1 -1-00 (1 - 02) = 1 a, - 02 + a102 > 1 - ai a2
for Val, 02 E [0. 1] and applying mathematical induction for {a.) to obtain
1=1 a:) >
41

---

Published as a conference paper at ICLR 2022
1 - Ei= a, long as Σ Σ 1. The second equality is because nu 0. The sec- log--1 T-1 1/21-1 s 2:201/22-1 The last inequality follows ond inequality comes from 2i=0 7 - logT)(8T).
From assumption (3), we know A, (wos w) 0. Furthermore, as we require
o²
log T 2 256 miny A (Wo.) w.s))
in Eqn. G.19.
1 bj 2\ (wo.s - w
1
o²
2 2 min A, (wo.s - wa,)²
2
llog T.
2
512
T
In sum, have obtained
log T
1
Vj A, 8/ 2
512
T X3
0²
Vj E B,
bj 2
log T
512
By combining with Eqn. G.21) we have
E [[f(WT+1- - f(w,)]
bj
+
1500
Σ
bj
+
1303
JEB
jEA
|
d2
logT
Σ jEA
0²
X3
log T
1
1024
T
1024
T
X
02
1
a²
=|B]
log
T
+A|
log T
1024
T
1024
T
1
o²
(I.A)
[B])
log T
1024
T
1
=d-
log T
1024
T
do²
=Ω
log
T
where the first inequality is because both the bias and variance terms are non-negative, given by =
Xy (Wo.) )) IT mmd,)² 2 0 and v, = n II (1 2 2 0.
Remark 3. The requirement T/ log 1/256 o² (min, X, (wo.s wx,)²) and assumption
Aj (wo,s - = + 0 for Vj = 1, 2,..., d can be replaced with T/ Volo''r T > 1/(8mp)) since in that case A holds for Vj 1, 2, ..., d and B 0. In particular, if 1/L, this requirement on T becomes T/ log T 2 k/8.
G.5 THE REASON OF USING ASSUMPTION 1.7)
In all of our analysis, we employ assumption
1.7
Eg [nnn]]] 3 2²11 where n. Hw: - (H)()), b(E))
42

---

Published as a conference paper at ICLR 2022
which is the same as the one in Appendix C, Theorem 13 of Ge et al. (2019). This key theorem is the major difference between our work and Ge et al. (2019). which directly entails its main theorem by instantiating with specific values in its assumptions.
On the other hand, is possible to use the assumptions in Ge et 2019); Bach & Moulines 2013);
Jain al. 2016) instead of our assumption (1.7 for least square regression:
min f(w) where f(w) -
R(ED)DD [(V w x²)=
(G.25)
2
y w + with satisfying ((x,))D [c'xx' [] o H for (x. ~D
(G.26)
E
[| 2 Fxx ]]
R²H
(G.27)
By combining Lemma 1 and assumption (.7) with Lemma 5, Lemma 8 and Lemma 9 in Ge eet al. (2019), one can obtain similar results in this paper with their assumptions. For simplicity, we just use assumption [17) here.
H RELATIONSHIP WITH (STOCHASTIC) NEWTON'S METHOD
Our motivation in Proposition shares similar idea with (stochastic) Newton's method quadratic objectives
W+++1 W; T} (
where the parameters are also updated coordinately in the "rotated space", i.e. given H TAU and w' UT w. In particular, when the Hessian is diagonal and f) 1/(t + 1), the update formula is exactly the same as the one for Proposition] [
Despite this similarity, our method differ from Newton method's and its practical variants in sev- eral aspects. First of all, our method focuses on learning rate schedulers and is first-order method. This property is especially salient when we consider eigencurve 's derivatives in Section 4.3 only hyperparameter search is needed, just like other common learning rate schedulers. In addition, most second-order methods, e.g. Schraudolph (2002); Erdogdu & Montanari (2015); Grosse & Martens (2016); [Byrd al. (2016); Botev al. (2017); Huang al. (2020); Yang et al. (2021), ap- proximates the Hessian matrix or the Hessian inverse and exploits the curvature information, while eigencurve only utilizes the rough estimation of the Hessian spectrum. On top of that, this timation is only an one-time effect and can be even further removed for similar models. These key differences highlight eigencurve advantages over most second-ores -rderr methods in practice.
43


Reviews:
[{"review_id": "w45INv5STmr", "reviewer": "Reviewer_vptL", "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": "Overall, the paper is easy to follow and well-motivated. \n\nStrengths:\n- The derived learning rate schedule is theoretically sound and the intuition is well-conveyed. It also provides some justifications for the effectiveness of the cosine decay schedule.\n\nWeaknesses:\n- In terms of optimal learning rate schedule for convex-quadratics, it was previously discussed in [1] with a noisy quadratic model. In particular, [1] directly optimized the schedule as they can compute the exact loss using dynamic programming. In principle, one can get an optimal (or near-optimal) learning rate schedule in this model by plugging the Hessian spectrum, then use it to train neural networks. Given that, some discussions or comparisons would be valuable in the main paper.\n- The derived theoretical results are all about asymptotic convergence. To be honest, I’m not sure how relevant that would be. Of course, it is an interesting contribution from a theoretical perspective. But in practice, we train neural networks with fixed epochs and I would expect the learning rate schedule to depend on the gradient noise level $\\sigma$. It seems that the proposed schedule is independent of $\\sigma$. I think the authors might like to add some discussions on that.\n- As the authors mentioned in the paper, Polyak averaging is optimal for convex quadratics but is unable to handle nonconvex landscapes in practice. However, I believe the exponential moving averaging method is commonly used for training neural networks, so I encourage the authors to include the comparison with the exponential moving average.\n- The 10-epoch results are a bit artificial. With only 10 epochs, it makes little sense to decay the learning rates twice for the step-decay schedule. It seems that the authors used different parameters (e.g. \\beta) for the 10-epoch setting. Although the authors argue that \\beta is not a hyperparameter, but it is obvious to me that the value of 1.000005 is carefully tuned. Could the authors justify this particular choice?\nOverall, the improvement of using the proposed Eigencurve is marginal on image classification tasks, though this is understandable as the step-decay and cosine-decay schedules are very strong baselines.\n\nMinor points:\n- The authors could save a lot of space by reorganizing all the figures in Figure 4. And with the saved space, I suggest the authors to include the details of hyperparameter tuning in the main paper.\n\n\n[1] Which Algorithmic Choices Matter at Which Batch Sizes? Insights From a Noisy Quadratic Model. NeurIPS 2019.", "summary_of_the_paper": "This paper studies the convergence of SGD with different learning rate schedules and aims to achieve minimax optimal convergence rates on quadratic objectives. To this end, this work proposes a new learning rate schedule (named Eigencurve) based on the Hessian spectrum and provides an optimal last-iterate convergence rate.\nThe proposed Eigencurve gives rise to slightly improved performance on image classification tasks with deep neural networks. In addition, the introduced schedule is similar to the popular cosine learning rate schedule on some problems, which, to some extent, justifies the effectiveness of the cosine schedule.", "summary_of_the_review": "The paper proposed an interesting learning rate schedule that achieves an optimal asymptotic rate on strongly-convex quadratics. However, the schedule relies on first computing the Hessian spectrum and the empirical improvement is not significant. \n\nOverall, this is a borderline paper and I'm inclined to reject the paper (though I'm willing to increase my score if the authors can address my comments).", "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": {}}, {"review_id": "mqhsAoOxYoC", "reviewer": "Reviewer_7X3r", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "## Writing\n\nThe quality of the writing is generally good.\nSome sections have grammatical issues (see \"Minor Comments\" for a few examples), but these could be easily corrected by carefully proof-reading the draft. \n\n## Theory\n\n**Correctness**: I checked all of the theoretical derivations in the Appendix and believe them to be sound.\nSome of the proofs are fairly dense and written with complex notation, so it possible that I missed a mistake. \nWith that said, I commend the authors on their attention to detail in the appendices.\n\n**Novelty**: I believe the theoretical contributions to be novel.\nWhile nice, the improvement in convergence rate of step-decay from a $\\\\log(T)$ to $\\\\log(\\\\kappa)$ factor is does not seem like a major contribution.\nFor instance, depending on $\\\\kappa$ and $T$, it is still possible for step-decay to have a faster theoretical rate of convergence than Eigencurve.\n\nEigencurve does attain the idea minimax complexity for SGD on convex quadratics when the \"power power law\" condition holds.\nHowever, it is not clear that this means Eigencurve is optimal in a rigorous sense.\nIs Eigencurve minimax optimal for the restricted class of quadratic problems satisfying the power power law? \nThis restricted class may be \"easier\" than the set of all quadratic functions due to clustering of the eigenvalues.\nIt seems to me that a lower bound for this class is necessary for the claim that Eigencurve is optimal to be accurate, since it is clearly not minimax optimal for the full class of quadratics.\n\nEigencurve also requires knowledge of the complete eigenvalue spectrum. \nIn general, computing this spectrum is as computationally intensive as minimizing the quadratic objective in the first place.\nIt isn't clear from the theoretical analysis if Eigencurve is robust to miss-estimation of the eigenvalues.\nFor tractability, extensions to approximate estimation of the spectrum or perhaps partial (e.g. only the top $n$ eigenvalues) spectra are attractive, but maybe hard to prove.\nGiven this issue, I think many practitioners will be content with step-decay. \n\nFinally, it is not at all clear to me how to apply Eigencurve to non-quadratic optimization problems. \nThe discussion in the Appendix notes that, for non-convex optimization, an approximation of the Hessian at an approximate first-order critical point is used to compute the eigenvalue spectrum. \nWhy does this choice make sense?\nFirstly, the FO point may be a saddle and the Hessian will be indefinite. \nIn this case, why is using the magnitude of the spectrum justified? \nSecondly, why should the Hessian at a FO point be a good descriptor of the global function curvature? \nThe eigenvalues around a stationary point can be arbitrarily scaled for non-convex, non-smooth, non-Lipschitz models like neural networks [1].\nI think these choices must be justified more carefully than they are in the submission.\n\n\n## Experiments\n\nThe experimental evaluation in the submission is not ready for publication.\n\nThe first issue is that nearly all figures in the paper are illegible\nFor example, the labels for Figures 3, 4, and 5 are barely visible when reading the paper at a normal zoom-level. \nMoreover, the columns and rows of Figure 4 are not labeled, meaning that the figure is still difficult to interpret when zoomed-in.\nNote that the additional experiments in the appendix suffer from these same problems. \nI don't think that figures need to be perfect at submission time, but they must be legible. \n\nAnother major issue of the evaluation is that there do not appear to be any repeats over random seed.\nI searched Appendix B.1 where the experimental experimental methodology is given and did not find any mention of repetitions. \nMoreover, distribution is not reported in any figure or table in the submission.\nWhen evaluating stochastic optimization methods, it is absolutely essential that multiple repetitions be performed and distribution information included with the experimental results. \nThis is necessary for readers to judge whether or not results are a meaningful trend or a low-probability outcome.\nFor example, table 2 is just not meaningful without standard deviations or inter-quartile range.\n\nFinally, there is a problem of fairness in the comparison to step-decay. \nThe authors report in Appendix B.1 that they use the \"common settings\" for step-decay on CIFAR-10/100. \nNo reference is provided to justify that the given settings are standard.\nMoreover, the authors report that estimating the eigenvalue spectrum requires 1-2 days, which is an order of magnitude more time than required to train a single model. \nThis gives Eigencurve a huge advantage in computational budget over step-decay.\nTo be fair, I think a similar (or least substantial) attempt must be made to tune the parameters of step-decay.\n\n\n## Minor Comments\n\n- Remark 1: \"coordinately\" -> \"coordinate-wise\".\n- Line after Eq. 1.7: In fact, no real justification or explanation of this assumption is given in Appendix G.5. The only comment made there is that previous work also make the same assumption.\n- (Page 3) \"Moreover, in practice, $\\\\kappa$ can be very big for large neural networks\": (i) this remark requires some justification, (ii) to be picky, $\\\\kappa$ is not defined for neural networks because they are non-convex and typically non-smooth.\n- Proposition 1: The proof of proposition 1 is not given in Lemma 15 as stated in the text. Instead, it is given in Appendix E on page 22. \n- Page 12: what is $\\\\beta$? I don't see a description of this parameter in Eq. 3.3. Edit: I see that this is defined in Appendix B.1 *after* it is first used.\n- Figure 6: It looks like the Largest eigenvalue is not within the bounds of the left-hand plot (log-scale).\n- Appendix A.1: what is the batch size for this experiment? I don't see it reported anywhere.\n- Page 20: I don't understand why the GPU memory limit prevents you from using multiple batches to estimate the Hessian spectrum. Isn't that the point of using batching in the first place?\n- Page 20: There is no guarantee that the optimizer converges to a local minimum. It may converge to a saddle-point, resulting in the negative eigenvalues.\n- Appendix B.4: This is not correct. The README.md of the indicated repository explicitly states \"the CIFAR-10 are not my property. If used in a paper, you'll need to cite the reference paper, as indicated in the official website.\"\n- Appendix C: Again, referencing a GitHub repository for code using ImageNet doesn't mean that the ImageNet dataset is distributed under the same license  as that repo.\n    Licensing rules for ImageNet are given here: https://www.image-net.org/download.\n- Appendix G.1: Use the restatable environment from thmtools (https://ctan.org/pkg/thmtools?lang=en) to avoid creating a new Lemma (i.e. Lemma 15) when proving Lemma 1. \n\n## References:\n\n[1] Dinh, Laurent, et al. \"Sharp minima can generalize for deep nets.\" International Conference on Machine Learning. PMLR, 2017.", "summary_of_the_paper": "# === Update === #\n\nI appreciate the thorough response to my review provided by the authors. I have looked through the newest version of the submission and find it to be much improved. The inclusion of repeats for the train loss / test accuracy comparison is great to see and the updated figures are mostly fixed. The experiments now make a meaningful argument for Eigencurve as a (non)-convex optimization method.\n\nI have increased my score to 6 to reflect the improvements and the author response. \n\n# ====== #\n\nThis submission proposes a new step-size schedule for stochastic gradient descent which leverages the eigenvalue spectrum of Hessian to speed-up convergence. \nThe approach, dubbed Eigencurve, is shown to achieve the minimax optimal convergence rate for stochastic gradient descent on quadratic functions under an additional condition that the eigenspectrum of the Hessian decays according to a power law.\nWhen this decay condition is not satisfied, Eigencurve still improves upon the popular step-decay schedule; in this case, it is sub-optimal by a factor of $\\\\log(\\\\kappa)$ rather than the $\\\\log(T)$ factor of step-decay.\nA lower bound is also provided verifying that the $\\\\log(T)$ sub-optimality of step-decay is tight and cannot be improved for quadratics.\nThe submission concludes with an empirical investigation of Eigencurve for (non-convex) optimization of several popular neural network architectures on the CIFAR-10 and ImageNet datasets.", "summary_of_the_review": "\nThis is an interesting submission with a very novel (at least, to my knowledge) approach to choosing the step-size for SGD.\nEffective step-size selection for stochastic optimizers is a challenging problem with potential for great impact on current machine learning practice. \nAs such, I think this work is a good fit for ICLR.\nTheoretically, the submission is sound and I enjoyed reviewing the theoretical arguments (see \"Theory\" below).\nHowever, empirically, the work is weak and, in my opinion, essentially unfinished. \nI found the decision to focus the experiments on heuristic extensions of Eigencurve to non-convex optimization to be strange, given the theory does not even apply to general convex functions.\nThe majority of figures are completely unreadable and all results are reported without distribution information; it is to judge the significance of the experiments as a result. \nSee \"Experiments\" for more details.\n\nAlthough interesting, I recommend that the submission be rejected given the unfinished state of the empirical evaluation.", "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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "WmHNT5-TmHE", "reviewer": "Reviewer_qo4b", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "# Pros\n+ The paper is pretty clear written. \n+ Related literature from the SGD side is well explained.\n\n\n# Cons\n- I am not sure how interesting it is to embed Hessian information into the SGD stepsize design. The stepsize in Prop 1 is nothing but Newton's method in my perspective, which should be counted as a second order method, and it is unfair comparing this to SGD as a first order method. \n- Therefore, the authors should explain the difference between the proposed method with Newton's method, and cite/compare with related works from (stochastic) Newton's method.\n- More importantly, the empirical gain of using second order information is, in my perspective, marginal (see e.g., Table 2)...  which can hardly justify the extra cost of obtaining the Hessian information.\n- The following comments are from the theory side ---- first of all, I would not say this paper contributes novel techniques or surprising results based on my knowledge of SGD literature; therefore I would not consider the presented theory as a sufficient contribution to justify the value of this work. Please correct me if important points are missing here.\n- Prop 2 is only an upper bound for poly-decay stepsize, and this along cannot support the claim that poly-decay is sub-optimal. As least a minimax-lower bound is required. For such lower bounds of poly-decay stepsize, [Ge 2019] already presented a minimax version, and a more recent work [Wu 2021] has an instance-dependent lower bound. The authors should use a lower bound here & clearly cite existing results in their next verison.\n- I am not sure how useful it is to compare the minimax rate. The authors want to claim one stepsize scheme is better than another. However the argued gain only happens in the worst case, while in benign instances, it is unknown whether or not the proposed stepsize scheme can have benefits. Perhaps conduct a instance-dependent analysis, and show a (nearly) instance-wise domination of one stepsize scheme over the other is more appealing. \n- Even let us assume there are truly someone cares about minimax rates, I doubt the importance of removing a logarithmic factor... \n- A final comment is that, comparing upper bound to upper bound simply cannot prove the benefit of one method over the other. The gain could be a loose analysis. A lower bound is needed to demonstrate the tightness of the analysis.\n\n\n\n\n\n[Ge 2019] Ge, Rong, et al. \"The step decay schedule: A near optimal, geometrically decaying learning rate procedure for least squares.\" arXiv preprint arXiv:1904.12838 (2019).\n\n[Wu 2021] Wu, Jingfeng, et al. \"Last Iterate Risk Bounds of SGD with Decaying Stepsize for Overparameterized Linear Regression.\" arXiv preprint arXiv:2110.06198 (2021).", "summary_of_the_paper": "The paper studies convergence rates of SGD with different stepsize schemes, in the context of linear regression. For convergence of the last iterate of SGD, the best known result still misses a $\\\\log T$ factor compared to the minimax rate. This work aims to fill this gap with an improved stepsize scheme that utilizes the eigenvalue distribution of the Hessian. When the true Hessian is known, the proposed method successfully fills the gap, provably and in the sense of the worst problem instances. When the true Hessian is hard to know, practical variants are also proposed, and are shown to be comparable to the state-of-the-art stepsize schemes in standard deep neural network benchmarks.", "summary_of_the_review": "I think the paper is clearly below the bar of acceptance. From the theory side, many points are not well supported (e.g., comparing upper bound to upper bound, comparing the minimax rate, etc.) and little technical novelty can be found. From the practice side, the improvement is too small to justify the cost of computing second order information. ", "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": "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": "0lrJyKmhlgp", "reviewer": "Reviewer_obgH", "summary": "", "questions": "", "limitations": "", "rating": 8, "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- Eigencurve is proved to achieve the optimal convergence rate when the eigenvalue distribution is skewed. It does no worse than step decay generally.\n- In the appendix, eigencurve is verified on ridge regression setting where the exact Hessian is known. This helps validate the correctness of the theory.\n- The empirical results are strong on CIFAR-10 and CIFAR-100. The authors verify that the loss surface is well approximated by quadratics. They show lower training loss and improved validation performance.\n- Paper is clearly written and easy to follow.\n\n\nWeaknesses\n- There is no theory analyzing the non-asymptotic case.\n- One concern I have with this method is the computational cost. This is somewhat mitigated by experiments in the appendix demonstrating that the distribution of eigenvalues of the Hessian can be re-used across different models on CIFAR-10.  Other learning rate scheduler have little to no additional overhead. Perhaps it would be useful to report the wall clock time of compute the eigenvalues + training.\n- The results on ImageNet appear to be less strong than those on CIFAR and they are not emphasized in the main text. I am a bit concerned that the learning rate scheduler offers limited improvement in the standard training regime (200 epochs on CIFAR and ~100 on ImageNet).\n- The experiments are on image classification datasets. Extending these results to other domains, such as language modelling, would improve the significance of the work.\n\nMinor\n- In the appendix, it's unclear what the extra term is. Adding a sentence to two would make things more clear.\n\n----\n### Post-rebuttal\nI'm increasing my score to an 8. Small note is that I believe step decay applied on ImageNet typically decays at epoch 30, 60, and 80 (e.g. Goyal, Priya, et al. \"Accurate, large minibatch sgd: Training imagenet in 1 hour.\"), so it'd be best to compare to that as a baseline.", "summary_of_the_paper": "The authors propose Eigencurve, a new approach to learning rate scheduling that utilizes information form the eigenvalues of the Hessian. They show that this scheduler obtains the minimax optimal rate on the noisy quadratic problem. Empirically, this scheduler demonstrates faster convergence on CIFAR-10 and ImageNet, especially when the number of epochs is small.", "summary_of_the_review": "Overall this paper offers an interesting perspective and approach to learning rate scheduling on an existing quadratic setting that shows practical implications in image classification. The experiments are thorough (including various ablations in the appendix) and validate the improved performance from the approach, especially when the number of epochs is limited. ", "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": "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": {}}]

Author rebuttal:

Meta-review: The paper proposes a method to learning rate scheduling that uses information form the eigenvalues of the Hessian. It shows that this scheduler obtains the minimax optimal rate on the noisy quadratic problem; and, empirically, this scheduler demonstrates faster convergence on CIFAR-10 and ImageNet, when the number of epochs is small.  Using Hessian information in direct and indirect ways is of interest to the community, and the paper does a nice job illustrating that in a context of interest.
Decision: Accept (Poster)