Super-Acceleration with Cyclical Step-sizes
Authors: Baptiste Goujaud
Damien Scieur
Aymeric Dieuleveut
Adrien Taylor
Fabian Pedregosa
Venue: NeurIPS 2021 Submitted (2021)
Keywords: Heavy ball
momentum
cyclical step-sizes
acceleration
convex optimization
first-order
quadratic optimization

Abstract: Cyclical step-sizes are becoming increasingly popular in the optimization of deep learning problems. Motivated by recent observations on the spectral gaps of Hessians in machine learning, we show that these step-size schedules offer a simple way to exploit them. More precisely, we develop a convergence rate analysis for quadratic objectives that provides optimal parameters and shows that cyclical learning rates can improve upon traditional lower complexity bounds. We further propose a systematic approach to design optimal first order methods for quadratic minimization with a given spectral structure. Finally, we provide a local convergence rate analysis beyond quadratic minimization for the proposed methods and illustrate our findings through benchmarks on least squares and logistic regression problems.

Super-Acceleration with Cyclical Step-sizes
Anonymous Author(s)
Affiliation
Address
email
Abstract
Cyclical step-sizes are becoming increasingly popular the optimization of deep learning problems. Motivated by recent observations on the spectral gaps of Hessians in machine learning, we show that these step-size schedules offer a simple way to exploit them. More precisely, we develop convergence rate analysis for quadratic objectives that provides optimal parameters and shows that cyclical learning rates can improve upon traditional lower complexity bounds. We further propose a systematic approach to design optimal first order methods for quadratic minimization with given spectral structure. Finally, provide a local convergence rate analysis beyond quadratic minimization for the proposed methods and illustrate findings through benchmarks least squares and logistic regression problems.
7
11
Introduction
12
13
One of the most iconic methods in first order optimization is gradient descent with momentum, also known as the heavy ball method [Polyak, 1964]. This method enjoys widespread popularity both in 15 its original formulation and in stochastic variant that replaces the gradient by stochastic estimate, method that is behind many of the recent breakthroughs deep learning [Sutskever al., 2013].
14
16
17 variant of the stochastic heavy ball where the step-sizes are chosen in cyclical order has recently come the forefront of machine learning research, showing state-of-the art results different deep learning benchmarks [Loshchilov and Hutter, 2017, Smith, 2017]. Inspired by this empirical success, aim study the convergence of the heavy ball algorithm where step-sizes ho, hı,-. not fixed or decreasing but instead chosen in cyclical order:
19
21
Algorithm 1: Cyclical heavy ball HB x (ho, ... -i
Input: Initialization Fo, momentum m (0, 1), step-sizes (ho....,hy, hk-13
ho (x(o))
31 + for t 1, 2, ....dd.. do
Fe+1 = Tt - (mod(t Vs(xz) + m(xx - xe-1)
end
The heavy ball method with constant step-sizes enjoys a mature theory, where it is known for example
23 achieve optimal black-box worst-case complexity quadratic convex optimization [Nemirovsky,
24 1992]. In stark contrast, little is known about the the convergence of the above variant with cyclical
25 step-sizes. Our main motivating question is
28
Do cyclical step-sizes improve convergence of heavy ball?
Submitted to 35th Conference on Neural Information Processing Systems (NeurIPS 2021). Do not distribute.

---

Our main contribution provides a positive answer to this question and, more importantly, quantifies the speedup under different assumptions. In particular, we show that for quadratic problems, whenever Hessian's s spectrum belongs to two or more disjoint intervals, the heavy ball method with cyclical step- 29
27
28
30 sizes achieves faster worst-case convergence rate. Recent works have shown that this assumption on the spectrum is quite natural and occurs in many machine learning problems, including deep neural networks [Sagun et al., 2017, Papyan, 2018, Ghorbani et al., 2019, Papyan, 2019]. More precisely, we list our main contributions below.
31
32
34
sections 3 and 4, we provide a tight convergence rate analysis of the cyclical heavy ball method (Theorems 3.1 and 3.2 for two step-sizes, and Theorem 4.8 for the general case). This analysis highlights regime under which this method achieves faster worst-case rate than the accelerated rate of heavy ball, phenomenon convergence rate analysis results to non-quadratic objectives.
36
refer to apperaacceleaation Theorem 5.1 extends the (local)
38
39
As a byproduct of the convergence-rate analysis, we obtain an explicit expression the optimal parameters in in the case of cycles of length two (Algorithm 2) and an implicit expression in terms system of equations in the general case.
41
42
Section presents numerical benchmarks illustrating the improved convergence the cyclical approach on 4 problems involving quadratic and logistic losses on both synthetic and a handwritten digits recognition dataset.
43
44
Finally, conclude in Section 7 with discussion of this work's limitations.
2
Notation and Problem Setting
46
47
Throughout the paper, we consider the problem of minimizing quadratic functions of the form
min f(r), with f CA - {f f(x) = 2xx x.)² Hx x.) + f., Sp(H) CA}. (OPT) zERd
48 where CA is the class of quadratic functions whose spectrum Sp(H) is localized in A S [n, L] S Ryo-
49 We discuss more general settings beyond quadratic minimization in Section
50
The condition A S [u. L) implies all quadratic functions under consideration are L-smooth and --strongly convex. For this function class, define the (inverse) condition number, and p, the ratio between the center of A and its radius, as
51
52
53 Finally, for method solving (OPT) that generates sequence of iterates {2t}, we define its worst-case 54 rate r and its asymptotic rate factor as
Ix1 x.
Tt
sup To Edd SEC, I F.Il"
1 - A lim sumsup VTr
(2)
t+000
3 Super-aaceleration with Cyclical Step-sizes
Algorithm 2: Cyclical (K = 2) heavy ball with with optimal parameters
Input: Initialization Ho. 141 < L1 112 L2
(where L1 - pI L2 - 112)
2
Lata Set: L--p
R 14- m 12-pi
vp--1² ne- -e----11
V1-12
2 = I (s(o))
for f 1, ....dd do
h4 = 1+m L
(if is even),
h4 1+m pg
(ift odd)
It+1 h V((ee) + m(x: x(-1)
end

---

58 In this section we develop one of our main contri-
103
57 butions, convergence rate analysis of the cyclical
11 L1
U22
58 heavy ball method with cycles of length 2. This analy-
L2 -1
59 sis crucially depends on the location of the Hessian's
12 -L
60 eigenvalues; we assume that these are contained in a
density
61 set A that the union of intervals of the same size
42
10
L2
A = jun, Liju[ue, L2], - = L2 - 142. (3)
62
By symmetry, this set is alternatively described by
0.0
0.5 eigenvalue magnitude
1.0
P2 L1 L2
p1,
L L L2 and R
(4)
11
where R is the relative length of the gap n42 L 64 with respect to the diameter L μ4l (see Figure 1).
68
Figure I: Hessian eigenvalue histogram for quadratic objective on MNIST. The outlier eigenvalue at L2 generates a non-zero rela- tive gap R 0.77. Under these conditions, the 2-cycle heavy ball method has a faster asymptotic rate than the single-cycle one (see Section 3.1).
65 This parametrization will reveal very convenient as the relative gap will play crucial role in the conver- gence rate analysis. Note also that the gap assumption comes without loss of generality,
67
allow R 0.
69
Through a correspondence between optimization methods and polynomials that we expand upon in Section 4, we can derive a worst-case analysis for the cyclical heavy ball method. The outcome of this analysis is in the following theorem, that provides the asymptotic convergence rate of Algorithm
70
71
73
1 for cycles length two. All proofs of results in this section can be found in Appendix D.3.
Theorem 3.1 (Rate factor of Hho, hi; m)). Let CA and ho; h1, m 2 0. The asymptotic rale factor of Algorithm I with cycles of length two is
75
mm
Taup S 1,
m
Ssup
+
V
Sup
Ssup
E (1,
1+m2 2m
(5)
1+m² if
2 1 (no convergence)
< Osup:
2m
Aho
1 m Ah1
with
Sup
sup de
2
(6)
2/m
2/m
xe
20ghi }n
77 This theorem gives the convergence rate for all triplets (m, ho, h1). By evaluating this expression over grid of step-sizes, Figure 2 shows how the rate changes as a function of both step-sizes:
10
10
10
Secord step siep-sizely b
optimal parameters
0.8
5
7
5
0-044, 0.5.1
5
7.
asymptotic ptoticc
optimal parameters
optimal parameters optimal parameters
0.6
oplima parameters
0.4
%
5 First step-size ho
10
%
5 First step-size ho
10
%
10
First step-size size An
Figure 2: Asymptotic rate of cyclical (K 2) heavy ball in terms of its step-sizes ho h across different values of the relative gap R. the left plot, the relative gap is zero, and so the step-sizes with smallest rate coincide (hg hj). For non-zero values of R (center and right), the optimal method instead alternates between two different step-sizes. In all plots the momentum parameter m set according Algorithm 2.
78
3

---

79 From the asymptotic rate expression of Theorem 3.1 we can optimize over the parameters (hu, h1, m)) obtain the method with smallest convergence rate. This leads to our other main contribution of this section, the asymptotically optimal Algorithm 2. This algorithm enjoys the following rate:
80
81
Corollary 3.2. The worst-case (asymptotic) rates Als. and 1 A of Algorithm 2 over CA
Alg. (1+W
122 100-------11
1 A-g. v R
p²
for even.
R
V1-R R22
v1 R2
as
3.1
Comparison with Polyak Heavy Ball
84 In the absence of eigenvalue gap (R = 0 and A = [u, L),, Algorithm 2 reduces to Polyak heavy 85 ball (PHB) [Polyak, 1964]. whose worst-case rate detailed in Appendix Since the asymptotic rate
86 of Algorithm 2 is monotonically decreasing in R. it is always better equal than PHB. Furthermore,
87 in the ill-conditioned regime (small k), comparison particularly simple: the optimal 2-cycle
86 algorithm has vI R2 relative improvement over PHB, as provided by the next proposition. A more thorough comparison for different support sets A is discussed in Table 1.
89
90
Proposition 3.3. Let R E 1). The rate factors of respectively Algorithm and PHB verify Alg
+ +(vK)), k-0 VI-RZ
1 -
2/xx
1 1 1-T PHR
1 - 2v/ + o(vR).
Relative gap R
Set A
Rate factor T
Speedup T/>
R E 10,1)
1u. + R(L [)] UI. R(L p))
2VG
(1- R2)-2
VI-R² R22
R = 1 - VK/22
14 Vill U [T. $ L.]
v/L
2 2/R
k=
R = 27
+ (1++1)))) U 7/4, [.]
indep. of K. O(Vk)
Table Case study of the convergence of Algorithm as a function of R, in the regime k 0. The first line corresponds to the regime where I is independent of K, and we observe constant gain w.r.. PHB. The second line considers setting which R depends on VR, that is, the two intervals in A are relatively small. The asymptotic rate reads (1 2 2/) beating the classical (1 - 2 R)) lower bound, unimprovable when R = 0. Finally, in the third line, R depends on k, the two intervals in A are so small that the convergence becomes ((),, i.e., is independent of
91 4 A constructive Approach: Minimax Polynomials
82 This section presents a generic framework (Algorithm 3) that allows designing optimal momentum and step-size cycles for given sets A and cycle length K.
Algorithm 3: Optimal momentum method with eyclical step-sizes
Input: Eigenvalue localization A, cycle length K, initialization 27. Preprocessing:
1. Find the polynomial o such that satisfies (16).
2. Set step-sizes (he [h=).=o...,K- and momentum m that satisfy resp. equations (21) and (22).
Set 21 = 3o
ho
V((x))
+
for t = 1, 2, ...... do
F++1 Ft Amod(t.K) V + m(at x4-1)
end
34 We first recall classical results that link optimal first order methods on quadratics and Chebyshev polynomials. Then, generalize the approach by showing that optimal methods can be viewed as

---

98
combinations of Chebyshev polynomials, and minimax polynomials ox of degree K over the set A. 97
Finally, we show how to recover the step-size schedule from ox
96
4.1
First Order Methods on Quadraties and Polynomials
99 A key property that we will use extensively in the analysis is the following link between first order methods and polynomials (see [Hestenes and Stiefel, 1952]).
100
101
Proposition 4.1. Let f E CA. The iterates It satisfy F1+1 E Fo + span(V
V(()))
where vo is the initial approximation of x., if and only if there exists a sequence of polynomials (Pi)LeN each of degree at most 1 more than the highest degree of all previous polynomials and Po of degree 0 (hence the degree of Pt is at most t), such that
103
Vt Tt - 2, = (Z - -x), Pa(0)= =
(9)
105
Example 4.2 (Gradient descent). Consider the gradient descent algorithm with fixed step-size h, applied to problem (OPT). Then, after unrolling the update, we have
106
Ft+1 2, -T Tx fV = It -I, hH( xx) (I - (H) h+) (No xx). (10)
In this case, the polynomial associated to gradient descent is P:(A)
- hA)
The above proposition can be used to obtain worst-case rates for first order methods by bounding their associated polynomials. Indeed, using the Cauchy-Schwand inequality in (9) leads to
109
|| x4 sup [P()) || - x. xyλ
Ft sup P((A)), where P(0) 1. (11)
xEλ
Therefore, finding the algorithm with the fastest worst-case rate can be equivalently framed as the problem of finding the polynomial with smallest value on the eigenvalue support A, subject to the normalization condition (0) 1. Such polynomials
111
referred to minimax. Throughout the paper, we use this polynomial based approach to find methods with optimal rates.
113
114
An important property of minimax polynomials is their equioscillation on A (see Theorem C.I and 115 its proof for a formal statement).
118
Definition 4.3. (Equioscillation) A polynomial Ps equioscillates on A if it verifies P(( = 1 and there exist λo < ... A E A such that
117
Pa(Aa) = (-1)² max (A()) XEA
(12)
118
Example 4.4 (A an interval). The t-th order Chebyshev polynomials of the first kind T. satisfy the equioscillation property on [-1, 1]. It follows that minimax polynomials on A = L] can be obtained by composing the Chebyshev polynomial T, with the linear transformation of:
119
120
T. (o (A)) 7i (o))
L + 1 I,
2 X,
arg min [E),[ XEA
pup)) with af
(13)
where of maps the interval [M, L] to 11. The optimization method associated with this minimax polynomial is the Chebyshev semi-terative method [Flanders and Shortley, 1950, Golub and Varga, 1961] (described also in Appendix B.1). This method achieves the lower complexity bound for smooth strongly convex quadratic minimization, see for instance [Nemirovsky, 1995, Chapter 12] or [Nemirovsky, 1992, Nesterov, 2003].
121
123
125
126
The next proposition provides the main results in this subsection, which is key for obtaining Algo- rithm 2. It characterizes the even degree minimax polynomial in the setting of Section that is, when A is the union of 2 intervals of same size. In this case, the minimax solution is also based on Chebyshev polynomials, but composed with a degree-two polynomial o...
127
128
129
Proposition 4.5. Let A = [1n, L1] U [μz, Lz] be an union of two intervals of the same size (L,- #1 L. (42) and let m be as defined in Algorithm 2. Then the minimax polynomial (solution
130
to (12)) is, for all 2n, E No.
132
Tn (o2 (A))
-arg min su)) with x =2 ( /1+m) ) (eR, AEa P(0)=1
(1
(1
1.
T, (0)
2
L,
142
5

---

133
4.2
Generalization to Longer Cycles
The polynomial in Example 4.4 uses a linear link function of to map [-1, In Proposition 4.5,
134
135
we see that a degree two link function 02 can be used to find the minimax polynomial when A is the union of two intervals. This section generalizes this approach and considers higher-order polynomials
136
for Øk- We start with the following parametrization, with an arbitrary polynomial ox of degree K,
137
p(():oR) Tn (A)) T, (ox (0)(
AI = Kn, n E N
(14)
138
As we will see in the next subsection, this parametrization allows considering cycles of step-sizes. Our goal now find the оg that obtains the fastest convergence rate possible. The next proposition quantifies its impact on the asymptotic rate and its proof can be found in Appendix D.I.
139
140
Proposition 4.6. For given σ such that suPxEA xx(()] 1, the asymptotic rate factor TTk " of the method associated to the polynomial (14) is
142
T
lim 1-000
sup P. (, = (0o - Vog -
with 00 - (0)
(15)
AEA
143 For a fixed K, the asymptotic rate (15) is decreasing function of du- This motivates the introduction of the "optimal" degree K polynomial o as the one that solves
144
o e arg max (0) s.t. suplo =1 r
(16)
AEA
Using the above definition, we recover the of and of from Example 4.4 and Proposition 4.5.
145
146
Finding the polynomial. Finding an exact and explicit solution for the general K and case is unfortunately out of reach, as it involves solving potentially difficult system of K non-linear equations. Here we describe an approximate approach. Let o (z) Ei We propose to discretize A into N different points {1 then solve the linear problem
148
149
max do s.t. -1 o 1
=j=1... N.
(17)
To check the optimality, it suffices to verify that the polynomial o satisfies the equioscillation property (Definition 4.3), as depicted in Figure 3.
150
151
152
Remark 4.7 (Relationship between optimal and minimax polynomials). For later reference, we note that the optimal polynomial & is equivalent to finding minimax polynomial on A and to rescale it. More precisely, o is optimal if and only if / (0) is minimax.
153
155
4.3
Cyclical Heavy Ball and (Non-)asymppotic Rates of Convergence
We now describe the link between o and Algorithm 3. Using the recurrence for Chebyshev polynomials of the first kind in (14), we have Vt Kn, Nt.
Tati ( (A)
(A))
T (0)) (o (0))
T, (a (A))
T (o- T T (
T (0)) (0)
To (0))
x
158 It still remains to find an algorithm associated with this polynomial. To obtain one in the form of
159 Algorithm 1, one can use the stationary behavior of the recurrence. From [Scieur and Pedregosa, 2020], the coefficients a, and bn converge
+ oo to their fixed-points a.c and boo. We therefore consider here an asymptotic polynomial Pr(A; x ), whose recurrence satisfies
161
)(();a))= = 20 o (2:o() b P
(18)
Similarly to K = 1, where this limit recursion corresponds to PHB, this recursion corresponds to an instance of Algorithm 3 (see Proposition 4.9 below), further motivating the cyclical heavy ball algorithm.
163
165
The following theorem the main result of this section and characterizes the convergence rate of Algorithm 1 for arbitrary momentum and step-size sequences (h. (h.)eej.KK] By optimizing over these parameters, we obtain a method associated to (18), whose rate is described in Proposition 4.9. All proof' can be found in Appendix D.2.
166
167

---

Balanced intervals with R=0
Balanced intervals with R=0.6
Unbalanced intervals with R=O
(A)
-2
-2
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0.75
1.00
À
À
of
02
oz
Figure 3: Examples of optimal polynomials o from (16), all them verifying the equioscillation property (Definition 4.3). The "*" symbol highlights the degree of o that achieves the best asymptotic rate > in (15) amongst all K (see Section 4.4). (Left) When A is an unique interval, all 3 polynomials are equivalently optimal -" = = (Center) When A is the union of two intervals of the same size, the degree polynomial is optimal 7 >T >n" This is expected given the result in Proposition 4.5. (Right) When A is the union of two unbalanced intervals, the degree polynomial instead achieves the best asymptotic rate T3 >7 2 >r
(see Section 4.4).
Theorem 4.8. The worst-case rate of convergence of Algorithm on CA with an arbitrary momentum 170 m and an arbitrary sequence of step-sizes {h,}
vm,
if Ssu S
1/K
+ m
mm
Gsup +
sup -
if asup E
1,
1-T=
2 (Vm))
(19)
1 + m
2 (no convergence)
sup 2
2(mm)*
171 where sup
- suplo(A; {ha}, m)), and oAA; {hi), m) the Kedegree polynomial
dEA
(A: (hi), m) $ Tr ([
11+--Ax-A AN-IA
1+ 4m--kx-2
And
0 -))). (20)
v/m
mm
m
172 Proposition 4.9. Let (A; {ha), m) be the polynomial defined by (20), and ob be the optimal link
173 function of degree defined by (16). If the momentum m and the sequence of step-sizes {h1} satisfy
(A; (hi), m) - o
(21)
174 then 1) the parameters are optimal, in the sense that they minimize the asymptotic rate factor from Theorem 4.8, 2) the optimal momentun parameter is
m = = 11) 2/K
where on = o
(22)
178 the iterates from Algo. with parameters {hi} and m form a polynomial with recurrence (18). Ale. and the asymptotic rate rate factor Alg.
177 and 4) Algorithm achieves the worst-case rate r
=0 (100
Alg. - 1/K
Alg. 3 =0
Važ
(23)
178 Solving the system (21) The system is constructed by identification of the coefficients in both
polynomials o and o\); (h4).m) which can be solved using a naive grid-search for instance. We
180 are not aware of any efficient algorithm solve this system exactly, although it is possible to use iterative methods such steepest descent Newton's 's method.
7

---

182
4.4
Best Achievables Worst-case Guarantees on CA
185
This section discusses the (asympiotic) optimality of Algorithm 3. In Section 4.2, the polynomial Pa( :ook) was written as composition of Chebyshev polynomials with o defined in (16). The best K is chosen as follows: we solve (16) for several values of K, then pick the smallest K among the minimizers of (15). However, following such steps does not guarantee that the polynomial P, is minimax, it is not guaranteed to minimize the worst-case rate suPA (P(()) (see (11)).
185
187
188
We give here an optimality certificate, linked to a generalized version of equioscillation. In short, we can find K non overlapping intervals (more formally, whose interiors are disjoint) Ag in A such that & (A.) = [-1,1] 1] then PA is minimax for all I = nK, n E N The detailed result provided by Theorem C.2. A direct consequence of this result is the asymptotic optimality of Algorithm 3, i.e. there cxists no first order algorithm with a better asymptotic rate 1 T for the function class CA-
190
192
193
It is possible that such o does not exist for given A. A complete characterization of the set A for which there exists such o is out of the scope of this paper. A partial answer is given in [Fischer, 201 ]] when A is the union of two intervals. However, the problem remains open in the general case.
194
195
5
Local Convergence for Non-Quadratic Functions
196
197
When f is twice-differentiall,, is possible to show local convergence rates when 2o is close enough to x. [Polyak, 1964]. We give here similar result that applies Algorithm (see proof in Appendix E). Those results are only local, as it is possible to find pathological counter-examples for which even PHB does not converge globally, for some specific initialization [Lessard al., 2016].
198
199
200
Theorem 5.1 (Local convergence). Let f Rd + R be a (potentially non-quadratic) twice continu- ously differentiable function, x, a local minimizer, and H be the Hessian of f at x, with Sp(H) C A.
201
202
203
Let it denote the result of running Algorithm I with parameters h1, h2... ,.g, m, and let 1 T be the linear convergence rate on the quadratic objective (OPT). Then we have
204
V Open set Ve Tu. I. E V = || x.1 || O(1 - ((1 + -x.ll
(24)
In short, when Algorithm I is guaranteed to converge rate 1 on (OPT), then the convergence 206 rate on a nonlinear functions can be arbitrary close to 1 1-1 when Tg is sufficiently close to T..
6 Experiments
208
In this section we present an empirical comparison of the cyclical heavy ball method for different length cycles across 4 different problems. We consider two different problems, quadratic and logistic regression, each applied two datasets, the MNIST handwritten digits [Le Cun et al., 2010] and a synthetic datasct. The results of these experiments, together with a histogram of the Hessian's s eigenvalues are presented in Figure 4 (see caption for discussion).
209
211
212
213
Dataset description. The MNIST dataset consists of data matrix A with 60000 images of hand- written digits each one with 28 x 28 = 784 pixels. The synthetic dataset is generated according to a spiked covariance model [Johnstone, 2001]. which has been shown to be an accurate model of covariance matrices arising for instance in spectral clustering [Couillet and Benaych-Georges, 2016] and deep networks [Pennington and Worah, 2017, Granziol et al., 2020]. In this model, the data matrix A = X is generated from a m X n random Gaussian matrix X and an m x m deterministic matrix Z. In our case, we take n = 1000, m = 1200 and Z is the identity where the first three entries multiplied by 100 (this will lead to three outlier cigenvalues). We also generate n-dimensional target vector b as b = Az or b = sign(Au Ax) for the quadratic and logistic problem respectively.
214
215
217
219
221
222
Objective function For each dataset, we consider quadratic and a logistic regression problem. leading to different problems. All problems are of the form mingeR Er {(A! xx b,) + >||x||? where l is a quadratic or logistic loss, A is the data matrix and b are the target values. We set the regularization parameter to \= = 10 [|-3 l|a For logistic regression, since guarantees only hold at neighborhood of the solution (even for the 1-cycle algorithm), we initialize the first iterate as the result of 100 iteration of gradient descent. In the case of logistic regression, the Hessian eigenvalues computed at the optimum.
223
224
225
227
8

---

10r
Quadratic Loss (MNIST)
Logistic Loss (MNIST)
Quadraric oss (Synthetic)
Logistir Lass Lass (Synthetir)
eigartaluee der Sky
A1
41
10
4
10
10
R-0.77
101
R-0.75
10
R-0.74
10'
R-0
0.5
eigerivalu aluervalueeeee mugnitude
egennvllue magriludee
eigervalue magnitude
elgenvalue magritude
10
10
10
70
10--
10
10
10"
10
10th
10
10-12
10"13
10
200
1000
herations
Iterations
Iteratons
Polyak heavy ball
Cyclical heavy with optimal parameters (K=2)
Figure Hessian Eigenvalue histogram (top row) and Benchmarks (bottom row). The top row shows the Hessian eigenvalue histogram at optimum for the 4 problems consider, together with the interval boundaries μ4, < L1 < 242 L2 for the two-interval split of the eigenvalue support described in Section 3. In all cases, there's s a non-zero gap radius R. This is shown in the bottom row, where we compare the suboptimality
terms of gradient norm as a function the number of iterations. As predicted by the theory, the non-zero gap radius translates into faster convergence of the cyclical approach, compared to PHB in all cases. The improvement is observed on both quadratic and logistic regression problems, even through the theory for the latter is limited to local convergence.
229
7
Conclusion
230
This work is motivated by two recent observations from the optimization practice of machine learning. First, cyclical step-sizes have been shown to enjoy excellent empirical convergence [Loshchilov and Hutter, 2017, Smith, 2017]. Second, spectral gaps are pervasive in the Hessian spectrum of deep learning models [Sagun et al., 2017, Papyan, 2018, Ghorbani et al., 2019, Papyan, 2019]. Based on the simpler context of quadratic convex minimization, we develop a convergence-rate analysis and optimal parameters for the heavy ball method with cyclical step-sizes. This analysis highlights the regimes under which cyclical step-sizes have faster rates than classical accelerated methods. Finally, we illustrate these findings through numerical benchmarks.
231
233
235
237
Main Limitations. In Section 3 we gave explicit formulas for the optimal parameters in the of the 2-cycle heavy ball algorithm. These formulas depend not only on extremal eigenvalues-al is usual for accelerated methods but also on the spectral gap R.. The gap sometimes be computed after computed the top cigenvalues (e.g. top-2 eigenvalue for MNIST). However, in general, there no guarantee how many eigenvalues needed estimate it. Moreover, global convergence result rely heavily on the quadratic assumption.
239
241
243
Another limitation regards long cycles. For cycles longer than 2, we have only given implicit formula to set the optimal parameters (Proposition 4.9). This involves solving a set of non-linear equations whose complexity increases with the cycle length. That being said, cyclical step-sizes might significantly enhance convergence speeds both in terms of worst-case rates and empirically, and this work advocates that new tuning practices involving different cycle lengths might be relevant.
245
247
249
Broader Impact. This work is mostly theoretical, and as such we believe it does not present direct societal consequences. However, the methods described in this paper can be used to train machine learning models which could themselves have societal consequences. For example, the deployment of machine learning models in decision-making has been shown to suffer from gender and racial bias and to amplify existing incqualities, see for instance [Hutchinson and Mitchell, 2019, Barocas et al.,
251
253
2017, Obermeyer et al., 2019].

---

References
255
256
Solon Barocas, Moritz Hardt, and Arvind Narayanan. Fairness in machine learning. Nips nutorial, 2017.
258
Dimitri P. Bertsekas. Nonlinear programming. Journal of the Operational Research Society, 1997.
259
Romain Couillet and Florent Denaych-GGeorges Kernel spectral clustering of large dimensional data. Electronic Journal of Statistics, 2016.
260
Bernd Fischer. Polynomial based iteration methods for symmetric linear systems. SIAM, 2011.
262
Donald A. Flanders and George Shortley. Numerical determination of fundamental modes. Journal of Applied Physics, 1950.
263
Behrooz Ghorbani, Shankar Krishnan, and Ying Xiao. An investigation into neural net optimization via hessian eigenvalue density. In International Conference on Machine Learning (ICML), 2019.
265
286
Gene H. Golub and Richard S. Varga. Chebyshev ceni-iterative methods, successive overrelaxation iterative methods, and second order Richardson iterative methods. Numerische Mathematik, 1961.
268
Diego Granziol, Xingchen Wan, Samuel Albanie, and Stephen Roberts. Explaining the Adaptive Generalisation Gap. arXiv preprint arXiv:201 1. 108181, 2020.
269
270
Magnus R. Hestenes and Eduard Stiefel. Methods of conjugate gradients for solving linear systems, volume 49, NBS Washington, DC, 1952.
271
272 Ben Hutchinson and Margaret Mitchell. 50 years of test (un) fairness: Lessons for machine learning. In Proceedings of the Conference on Fairness, Accountability, and Transparency, 2019.
274
lain M. Johnstone. On the distribution of the largest eigenvalue in principal components analysis. Annals of statistics, 2001.
275
276
Yann Le Cun, Corinna Cortes, and Chris Burges. MNIST handwritten digit database. ATT Labs [Online], 2010.
277
278
Laurent Lessard, Benjamin Recht, and Andrew Packard. Analysis and design of optimization algorithms via integral quadratic constraints. SIAM Journal on Optimization, 2016.
280
Ilya Loshchilov and Frank Hutter. SGDR: stochastic gradient descent with warm restarts. In International Conference on Learning Representations (ICIR), 2017.
281
282
Arkadi S. Nemirovsky. Information-based complexity of linear operator equations. Journal of
283
Complexity, 1992.
284
Arkadi S. Nemirovsky. Information based complexity of convex programming. Lecture Notes, 1995.
285
Yurii Nesterov. Introductory Lectures on Convex Optimization. Springer, 2003.
Ziad Obermeyer, Brian Powers, Christine Vogeli, and Sendhil Mullainathan. Dissecting racial bias in an algorithm used to manage the health of populations. Science, 2019.
287
286
Vardan Papyan. The full spectrum of deepnet hessians at scale: Dynamics with SGD training and sample size. arXiv preprint (tfi::/811.000000 2018
290
Vardan Papyan. Measurements of Three-Level Hierarchical Structure in the Outliers in the Spectrum of Deepnet Hessians. International Conference on Machine Learning (ICML), 2019.
291
Jeffrey Pennington and Pratik Worah. Nonlinear random matrix theory for deep learning. In Advances on Neural Information Processing Systems (NIPS), 2017.
293
294
Boris T. Polyak. Some methods speeding up the convergence of iteration methods. USSR computational mathematics and mathematical physics, 1964.
296
Levent Sagun, Utku Evci, V. Ugur Guney, Yann Dauphin, and Leon Bottou. Empirical analysis of the Hessian of over wee-parametrriee neural networks. arXiv preprint arXiv: 04454, 2017.
297
Damien Scieur and Fabian Pedregosa. Universal Asymptotic Optimality of Polyak Momentum. In International Conference on Machine Learning (ICML), 2020.
289
300
Leslie N. Smith. Cyclical learning rates for training neural networks. In 2017 IEEE Winter Conference Applications of Computer Vision (WACV). IEEE, 2017.
302
Ilya Sutskever, James Martens, George Dahl, and Geoffrey Hinton. On the importance of initialization and momentum in deep learning. In International Conference on Machine Learning (ICML), 2013.
303
10

---

Checklist
304
305
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] The Introduction (Section 1) details where all results can be found.
307
309
(b) Did you describe the limitations of your work? [Yes] There is a paragraph "Main Limitations" in the Conclusion (Section 7).
310
(c) Did you discuss any potential negative societal impacts of your work? [N/A] As stated in the "Broader Impact" section, this work is mostly theoretical and as such we believe it doesn't ' present a direct societal impact.
312
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
315
316
2. If you are including theoretical results...
317
(a) Did you state the full set of assumptions of all theoretical results? [Yes] In each and every statement we make.
318
(b) Did you include complete proofs of all theoretical results? [Yes] All proofs are available in the supplementary material.
320
321
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either in the supplemental material or as a URL)? [Yes] URLs are provided in the supplementary material.
323
325
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] In the experiments section (Section 6).
326
(c) Did you report error bars (c.g., with respect the random seed after running experi- ments multiple times)? [No].
328
329
(d) Did you include the total amount of compute and the type of resources used (e.g.. type of GPUs, internal cluster, or cloud provider)? [Yes]. in Appendix F
330
4. If you using existing assets (e.g., code, data, models) or curating/releasing new assets....
332
(a) If your work uses existing assets, did you cite the creators? [Yes] In the "Dataset description" " paragraph of the Experiments section 6.
333
334
(b) Did you mention the license of the assets? [N/A]
335
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A] There is no new asset. We used MNIST existing Dataset as well synthetic dataset whose construction is described in papers cited in the Experiments section 6.
336
337
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
339
340
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
343
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
344
345
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
348
11


Reviews:
[{"review_id": "Uij3m6aXbce", "reviewer": "Reviewer_a5zh", "summary": "This paper studies using cyclical step-sizes of Heavy Ball for solving strongly convex quadratic problems. The authors first study setting the step size to two specific values periodically (period=2), where the values are related to the spectrum (i.e. the eigenvalues) of the underlying quadratic matrix. Assuming the spectrum can be divided into two groups. The authors prove that the resulting asymptotic rate of using the cyclical step size can be faster than that of the standard step size of Heavy Ball. Then, the authors discuss the extension to the case that the step size can have K values and the step size is set to the possible step sizes in a cyclical fashion.\n", "questions": "", "limitations": "", "rating": 5, "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": "I have some challenges for the authors.\n\n \n\n\n=== 1. The paper missed a highly relevant reference: Samet Oymak. \"Super-Convergence with an Unstable Learning Rate\" arXiv:2102.10734 February. 2021. \n\nThe result of showing that if the spectrum of the Hessian can be grouped into two clusters, then using a cyclical Learning Rate can lead to a faster convergence compared to using the standard step size has been shown in [Oymak 2021]. Though I understand [Oymak 2021] is for gradient descent while this paper is for Heavy Ball, the novelty of this paper is not very high from this perspective.\n\n\n=== 2. The intuition behind the acceleration result due to the cyclical step sizes seems not be explicitly described in the paper.\n\n\nAfter reading the paper, I'm still not sure where exactly did the authors provide an explanation why the cyclical step sizes help faster convergence. It will be more helpful for the readers if the authors can be more transparent about their acceleration result.\n\nOn the other hand, [Oymak 2021] conveys a very clear message that periodically setting a large step size can help the progress on directions that correspond to small eigenvalues, while a small step size help to prevent divergence, and hence shows the benefit of using cyclical step sizes.\n\n\n=== 3. The theoretical results are hard to interpret. \n\n\n\n(3.a) The work makes an assumption that the eigenvalues are located in a way so that there are two intervals of the same size (line 61). It appears to be a strong assumption so the authors might want to discuss if it is an artifact of analysis.\n\n(3.b) (Theorem 3.1) It is not easy to tell what would be the optimal momentum parameter $m$ and what would be the optimal step sizes of $h_1$ and $h_2$ from Theorem 3.1. Also, the choice of the momentum parameter $m$ and the step sizes $h_1$ and $h_2$ determines $\\sigma_{\\sup}$ in a seemingly complicated way. The authors might want to explain the interaction between these parameters. It would be better to present Theorem 3.1 in a more user-friendly fashion.\n\n(3.c) (Section 4.2 and 4.3) The authors consider using cyclical step sizes with a longer cycle than 2 in the later parts of this paper. Does the result there show any benefit of using a longer cyclical step size? If so, can the authors provide a discussion here? If not, what would be the point of showing the result?\n\n\n\n\n=== 4. Significance\n\n\nThe result in this paper seems to be very specific to the strongly convex quadratic problems, where the Hessian is a fixed matrix. If the Hessian changes a lot, then the analysis/techniques in this paper would likely be useless. So it is unclear if this work really makes an important step towards theoretically understanding the success of cyclical step sizes in practice.   \n\nA relevant question: Does the insight from the theoretical results in this paper leads to any new heuristic in optimization? \n\n\n************* after rebuttal **************\n\nI decided to leave the score as it is, because I think the idea has a great similarity to [Oymak 2021], and the proof techniques are not particularly novel and/or are standard for Heavy Ball (e.g. [Pedregosa 2021]). It is unclear to me if this paper makes another important step towards understanding cyclical step sizes in practice, compared with [Oymak 2021]. I don't think if the insights of this paper lead to any practical heuristics, and the practical contributions seem not central to the paper.\n\nAlso, the concern about the interaction of the parameters which was also raised by Reviewer 9ZCq is lingering. \n\nRef:\n[Pedregosa 2021]\nhttp://fa.bianp.net/blog/2021/hitchhiker/", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors adequately addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "IijP2nOkHIA", "reviewer": "Reviewer_9ZCq", "summary": "The authors study a variant of the heavy ball method, where the stepsizes are chosen in a cyclical order. The paper considers the problem of minimising quadratic functions (there is a paragraph on local analysis for more general functions, but this is reduced to  the quadratic case  by linearisation). In the case where the cycle is 2 and the intervals of the eigenvalues of the quadratic functions are known, the authors show how this cyclic stepsize choice can lead to acceleration. In the more general setting of cycle $K$, their analysis is subject to some polynomial.\n\n\n", "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": "\nOverall, I found this paper interesting, and the theoretical study of good stepsize choices is important for stochastic algorithms.\nHowever, in general, I'm not sure how practical/useful the results here actually are, Algorithm 3 requires finding a polynomial which may not exist and involves solving a difficult system of $K$ nonlinear equations. The $K=2$ scheme also requires not just estimating the largest and smallest eigenvalue, but also the eigenvalue gap. This is in contrast to  existing analysis into cyclical stepsizes in descent methods, see last paragraph. \n\nI'm also a  confused about the statement in Theorem 3.1, it refers to Algorithm 1 where $h_0$ and $h_1$ are given explicitly in terms of the eigenvalue bounds and $m$, but you mention immediately after this theorem about optimising $h_0$ and $h_1$, so are these values fixed as in the Algorithm or are they arbitrary? If they are arbitrary, what the corresponding optimal $h_0$ and $h_1$ are which give the optimal rate in  corollary 3.2 (otherwise, after estimating the eigenvalue bounds, would one need to apply something like Newton's method to optimise for these step sizes? This could be potentially more costly than the acceleration obtained?) ?\nFinally,  another question I have is: the motivation given in the introduction is from the use of restarts in stochastic algorithms, while the analysis here is in the deterministic setting, do the authors expect the results here to apply also in the stochastic? Perhaps some numerical illustrations on this would be helpful? \n\nThere is  a related strand of work on the use of cyclical stepsize for descent methods (with  many results appearing in the later 1990's and early 2000's)  -- the analysis into acceleration in  convergence rates  has also been studied in many works. These works make connections to the relationship between eigenvalues of the Hessian (similar to the analysis in this work), and also provide guidance on practical choices of stepsizes based on past iterates. Some examples: Friedlander et al, SIAM Journal on Numerical Analysis, Vol. 36, No. 1 (1999), pp. 275-289; Dai and Fletcher, Math. Program., Ser. A 103, 541–559 (2005); Dai et al, IMA Journal of Numerical Analysis (2006) doi:10.1093/imanum/drl006. See also the more recent work by Kalousek, Found Comput Math (2017) 17:359–42, DOI 10.1007/s10208-015-9290-8. Since this body of work very close to the results presented, the authors should  reference appropriately  and provide some discussions on the relation to their work.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "HVxFfYv6K3c", "reviewer": "Reviewer_ao6p", "summary": "This paper studies cyclical step sizes for heavy ball momentum. It is shown that under some conditions, it is possible to improve the convergence rate of heavy ball by relying on cyclical step sizes with K = 2. The result is obtained by a careful examine of the spectrum of the Hessian. The cases for larger K are also discussed. In general, the results are nice but also has its own limitation.", "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": "Strength:\n\n(+) This work demonstrates that cyclic step sizes are useful and theoretically improves over HB under certain conditions. I believe the results are of interests in the community.\n\n(+) The paper is well written and easy to follow.\n\n\nWeakness\n\n(-) Though theoretically appealing, it is unclear that the improvement comes from. In particular, is it possible to tighten the HB convergence as well assuming (3) is true? This is a critical question since without demonstrating it, it is not possible to conclude cyclic step sizes are helpful. \n\n(-) For quadratic problems, it is relative easy to find L2 and mu2, but is it common in e.g., logistic regression or other loss functions to find these parameters? ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This is mainly a theoretical work. The Societal impact depends on how it is applied to solve real problems.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "0LyD_Qjtowy", "reviewer": "Reviewer_HKjc", "summary": "This paper studies the cyclicial step-sizes to improve the worst-case convergence of the heavy ball method (deterministic version). More precisely, the authors 1) achieve a faster asymptotic worst-case convergence  rate compared to the polayk heavy ball method for the strongly convex and L-smooth quadratic objectives,  2) show how to select the optimal momentum and step-size cycles, and 3) extend the local convergence to the non-quadratic case. Furthemore, numerical experiments on quadratics and logistic regressions have been conducted to demonstrate the main strength of the cyclicial heavy ball method.", "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": "Overall, the paper is well-written and the proof is solid. The novelty of  this paper is that the authors take advantage of the cyclical step-size strategies which recently have been widely used in the stochastic optimization setting, to improve the worst-case convergence of the traditional heavy ball method. The strong points of this paper are its theoretical parts: 1) the cyclicial heavy ball  for example with 2 cycles has a faster worst-case convergence over the traditional polyak heavy ball method (see Table 1); 2) provide a systematic approach to select the optimal parameters for momentum and step-size cycles if given the spectrum interval of Hessian $\\Lambda$ and cycle length $K$.  I like the results, however 1) their analysis heavily relies on the distribution of the Hessian's eigenvalues which makes it uneasy to be extended to other general settings; 2) the algorithm needs to estimate some extra eigenvalues which may be expensive for large scale problems. I have the following detailed concerns or comments on this paper:\n\n1) From Figure 2, we can see that when the eigenvalue gap $R \\neq 0$, you have two choice for the optimal step-sizes $(h_0, h_1)$: 1) $h_0 > h_1$ and 2) $h_0 < h_1$. In Algorithm 2, the authors use the first choice that $h_0 > h_1$. If you choose another one i.e., $h_0 < h_1$,  could you get similar results? How will it affect your numerical results?\n2) The cyclicial step-sizes indeed have been widely used in deep learning. However, it is not very clear why the cyclicial step-size strategy proposed in this paper helps to improve the traditional heavy ball method. Could you try to explain it a little bit?\n3) The theoretical results for the cyclicial heavy ball method heavily rely on the location of the Hessian’s eigenvalues and also the quadratic assumption. Is it possible or easy to extend this idea to e.g., the general convex problems and nonconvex problems, especially in deep learning, or stochastic heavy ball method?\n4) In Figure 4, from the first and the last pictures of the bottom row, we can see that the cyclicial heavy ball with optimal parameters performs worse than the polyak heavy ball method at the beginning. Could you clarify why this happens?\n5) The computational cost: except the smallest ($\\mu$) and largest ($L$) eigenvalues as polyak heavy ball, the proposed algorithm also needs to know the distribution of the eigenvalues, 1) if the eigenvalues of Hessian are clustered (the best situation) around the smallest or largest eigenvalues for example MNIST dataset (see the first picture of Figure 4), we still need to estimate other two top eigenvalues except the extremal eigenvalues (i.e., $\\mu$ and $L$). So it will be costly and impractical for the large scale optimization problems. Especially, for the datasets in which the distribution of the Hessian’s eigenvalues is dense (not clustered), the computational cost will be highly increased but the improvements seem to be less because in this case the eigenvalue gap $R$ is smaller.  Could you summary in what kinds of situations the increasing of the computational cost can be ignored compared to its improvements. \n\nOther Comments:\n1) There are some mistakes in Table 1: 1) in the first line ($R \\in [0,1)$), the value  of \"Set $\\Lambda$ \" is wrong, it should be $[\\mu, \\mu + (L-\\mu)(1-R)/2] \\cup [L-(L-\\mu)(1-R)/2, L]$;  2) in the third line and the fourth column($R=1-2\\gamma \\kappa$), the speedup should be “ $O(\\kappa^{-1/2})$ ” instead of “$O(\\kappa^{1/2})$”. \n2) In the theoretical part, the authors use $m$ and $\\lambda$, which appear frequently, to denote the momentum parameter and the eigenvalue of Hessian, respectively. But in the numerical part, $m$ is also used to denote the dimension of the data matrix and $\\lambda$ is used to denote the regularization parameter. This easily leads to misunderstandings to the readers. \n3) There is an additional \"with\" in the name of Algorithm 2. \n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "In general, the authors have adequately addressed the limitations and potential negative societal impact of their work.  ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "18 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Given the reviewers comments and after thorough discussion, it has been decided that this paper will not be accepted at NeurIPS 2021. The relationship to previous work and comments about parameter selection should be taken into consideration by authors when considering revisions of this manuscript.
Decision: Reject