Super-Acceleration with Cyclical Step-sizes
Year: 2021

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

text: Cyclical step-sizes are becoming increasingly popular in the optimization of deep1 learning problems. Motivated by recent observations on the spectral gaps of2 Hessians in machine learning, we show that these step-size schedules offer a3 simple way to exploit them. More precisely, we develop a convergence rate4 analysis for quadratic objectives that provides optimal parameters and shows that5 cyclical learning rates can improve upon traditional lower complexity bounds.6 We further propose a systematic approach to design optimal first order methods7 for quadratic minimization with a given spectral structure. Finally, we provide a8 local convergence rate analysis beyond quadratic minimization for the proposed9 methods and illustrate our findings through benchmarks on least squares and10 logistic regression problems.11
1 Introduction12
One of the most iconic methods in first order optimization is gradient descent with momentum, also13 known as the heavy ball method [Polyak, 1964]. This method enjoys widespread popularity both in14 its original formulation and in a stochastic variant that replaces the gradient by a stochastic estimate,15 a method that is behind many of the recent breakthroughs in deep learning [Sutskever et al., 2013].16
A variant of the stochastic heavy ball where the step-sizes are chosen in cyclical order has recently17 come to the forefront of machine learning research, showing state-of-the art results on different deep18 learning benchmarks [Loshchilov and Hutter, 2017, Smith, 2017]. Inspired by this empirical success,19 we aim to study the convergence of the heavy ball algorithm where step-sizes h0, h1, . . . are not fixed20 or decreasing but instead chosen in cyclical order:21
Algorithm 1: Cyclical heavy ball HBK(h0, . . . , hK−1;m) Input: Initialization x0, momentum m ∈ (0, 1), step-sizes {h0, . . . , hK−1} x1 = x0 − h0
1 +m ∇f(x0)
for t = 1, 2, . . . do xt+1 = xt − hmod(t,K)∇f(xt) +m(xt − xt−1)
end
The heavy ball method with constant step-sizes enjoys a mature theory, where it is known for example22 to achieve optimal black-box worst-case complexity of quadratic convex optimization [Nemirovsky,23 1992]. In stark contrast, little is known about the the convergence of the above variant with cyclical24 step-sizes. Our main motivating question is25
Do cyclical step-sizes improve convergence of heavy ball?26
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, quantifies27 the speedup under different assumptions. In particular, we show that for quadratic problems, whenever28 Hessian’s spectrum belongs to two or more disjoint intervals, the heavy ball method with cyclical step-29 sizes achieves a faster worst-case convergence rate. Recent works have shown that this assumption on30 the spectrum is quite natural and occurs in many machine learning problems, including deep neural31 networks [Sagun et al., 2017, Papyan, 2018, Ghorbani et al., 2019, Papyan, 2019]. More precisely,32 we list our main contributions below.33
• In sections 3 and 4, we provide a tight convergence rate analysis of the cyclical heavy ball method34 (Theorems 3.1 and 3.2 for two step-sizes, and Theorem 4.8 for the general case). This analysis35 highlights a regime under which this method achieves a faster worst-case rate than the accelerated36 rate of heavy ball, a phenomenon we refer to as super-acceleration. Theorem 5.1 extends the (local)37 convergence rate analysis results to non-quadratic objectives.38
• As a byproduct of the convergence-rate analysis, we obtain an explicit expression for the optimal39 parameters in in the case of cycles of length two (Algorithm 2) and an implicit expression in terms40 of a system of K equations in the general case.41
• Section 6 presents numerical benchmarks illustrating the improved convergence of the cyclical42 approach on 4 problems involving quadratic and logistic losses on both synthetic and a handwritten43 digits recognition dataset.44
• Finally, we conclude in Section 7 with a discussion of this work’s limitations.45
2 Notation and Problem Setting46
Throughout the paper, we consider the problem of minimizing quadratic functions of the form47
min x∈Rd
f(x) , with f ∈ CΛ , { f : f(x) = 12 (x− x ∗) TH(x− x∗) + f∗, Sp(H) ⊆ Λ } , (OPT)
where CΛ is the class of quadratic functions whose spectrum Sp(H) is localized in Λ ⊆ [µ,L] ⊆ R>0.48 We discuss more general settings beyond quadratic minimization in Section 5.49
The condition Λ ⊆ [µ,L] implies all quadratic functions under consideration are L-smooth and50 µ-strongly convex. For this function class, we define κ, the (inverse) condition number, and ρ, the51 ratio between the center of Λ and its radius, as52
κ , µL , ρ , L+µ L−µ = ( 1+κ 1−κ ) . (1)
Finally, for a method solving (OPT) that generates a sequence of iterates {xt}, we define its worst-case53 rate rt and its asymptotic rate factor τ as54
rt , sup x0∈Rd, f∈CΛ ‖xt − x∗‖ ‖x0 − x∗‖ , 1− τ , lim sup t→∞ t √ rt . (2)
3 Super-acceleration with Cyclical Step-sizes55
Algorithm 2: Cyclical (K = 2) heavy ball with with optimal parameters Input: Initialization x0, µ1 < L1 < µ2 < L2 (where L1 − µ1 = L2 − µ2)
Set: ρ = L2+µ1L2−µ1 , R = µ2−L1 L2−µ1 , m =
(√ ρ2−R2−
√ ρ2−1√
1−R2 )2 x1 = x0 − 1L1∇f(x0) for t = 1, 2, . . . do
ht = 1+m L1 (if t is even), ht = 1+mµ2 (if t is odd)
xt+1 = xt − ht∇f(xt) +m(xt − xt−1)
end
In this section we develop one of our main contri-56 butions, a convergence rate analysis of the cyclical57 heavy ball method with cycles of length 2. This analy-58 sis crucially depends on the location of the Hessian’s59 eigenvalues; we assume that these are contained in a60 set Λ that is the union of 2 intervals of the same size61
Λ = [µ1, L1]∪[µ2, L2] , L1−µ1 = L2−µ2. (3)
By symmetry, this set is alternatively described by62
µ , µ1, L , L2 and R , µ2 −L1 L2 − µ1 , (4)
where R is the relative length of the gap µ2 −L163 with respect to the diameter L2 − µ1 (see Figure 1).64 This parametrization will reveal very convenient as65 the relative gap will play a crucial role in the conver-66 gence rate analysis. Note also that the gap assumption67 comes without loss of generality, as we allow R = 0.68
Through a correspondence between optimization69 methods and polynomials that we expand upon in70 Section 4, we can derive a worst-case analysis for the cyclical heavy ball method. The outcome of71 this analysis is in the following theorem, that provides the asymptotic convergence rate of Algorithm72 1 for cycles of length two. All proofs of results in this section can be found in Appendix D.3.73 Theorem 3.1 (Rate factor of HB2(h0, h1;m)). Let f ∈ CΛ and h0, h1, m ≥ 0. The asymptotic rate74 factor of Algorithm 1 with cycles of length two is75
1− τ =  √ m if σsup ≤ 1, √ m ( σsup + √ σ2sup − 1 ) 1 2 if σsup ∈ ( 1, 1+m 2 2m ) ,
≥ 1 (no convergence) if 1+m 2
2m ≤ σsup,
(5)
76
with σsup = sup λ∈ { µ1,L1,µ2,L2,
h0+h1 2h0h1
} ∩Λ
∣∣∣2(1 +m− λh0 2 √ m )( 1 +m− λh1 2 √ m ) − 1 ∣∣∣ . (6)
This theorem gives the convergence rate for all triplets (m,h0, h1). By evaluating this expression77 over a grid of step-sizes, Figure 2 shows how the rate changes as a function of both step-sizes:
78
From the asymptotic rate expression of Theorem 3.1 we can optimize over the parameters (h0, h1,m)79 to obtain the method with smallest convergence rate. This leads to our other main contribution of this80 section, the asymptotically optimal Algorithm 2. This algorithm enjoys the following rate:81
Corollary 3.2. The worst-case (asymptotic) rates rAlg. 2t and 1− τAlg. 2 of Algorithm 2 over CΛ are82 rAlg. 2t = ( 1 + t √ ρ2−1 ρ2−R2 )(√ ρ2−R2− √ ρ2−1√
1−R2
)t , 1− τAlg. 2 = √ ρ2 −R2 − √ ρ2 − 1
√ 1−R2
for t even.
3.1 Comparison with Polyak Heavy Ball83
In the absence of eigenvalue gap (R = 0 and Λ = [µ,L]), Algorithm 2 reduces to Polyak heavy84 ball (PHB) [Polyak, 1964], whose worst-case rate is detailed in Appendix B. Since the asymptotic rate85 of Algorithm 2 is monotonically decreasing in R, it is always better or equal than PHB. Furthermore,86 in the ill-conditioned regime (small κ), the comparison is particularly simple: the optimal 2-cycle87 algorithm has a √ 1−R2 relative improvement over PHB, as provided by the next proposition.88 A more thorough comparison for different support sets Λ is discussed in Table 1.89 Proposition 3.3. Let R ∈ [0, 1). The rate factors of respectively Algorithm 2 and PHB verify90
4 A constructive Approach: Minimax Polynomials91
This section presents a generic framework (Algorithm 3) that allows designing optimal momentum92 and step-size cycles for given sets Λ and cycle length K.93
Algorithm 3: Optimal momentum method with cyclical step-sizes Input: Eigenvalue localization Λ, cycle length K, initialization x0. Preprocessing:
1. Find the polynomial σΛK such that it satisfies (16). 2. Set step-sizes {hi}i=0,...,K−1 and momentum m that satisfy resp. equations (21) and (22).
Set x1 = x0 − h0
1 +m ∇f(x0)
for t = 1, 2, . . . do xt+1 = xt − hmod(t,K)∇f(xt) +m(xt − xt−1)
end
We first recall classical results that link optimal first order methods on quadratics and Chebyshev94 polynomials. Then, we generalize the approach by showing that optimal methods can be viewed as95
combinations of Chebyshev polynomials, and minimax polynomials σΛK of degree K over the set Λ.96 Finally, we show how to recover the step-size schedule from σΛK .97
4.1 First Order Methods on Quadratics and Polynomials98
A key property that we will use extensively in the analysis is the following link between first order99 methods and polynomials (see [Hestenes and Stiefel, 1952]).100 Proposition 4.1. Let f ∈ CΛ. The iterates xt satisfy101
xt+1 ∈ x0 + span{∇f(x0), . . . ,∇f(xt)} , (8) where x0 is the initial approximation of x∗, if and only if there exists a sequence of polynomials102 (Pt)t∈N, each of degree at most 1 more than the highest degree of all previous polynomials and P0 of103 degree 0 (hence the degree of Pt is at most t), such that104
∀ t xt − x∗ = Pt(H)(x0 − x∗), Pt(0) = 1 . (9)
Example 4.2 (Gradient descent). Consider the gradient descent algorithm with fixed step-size h,105 applied to problem (OPT). Then, after unrolling the update, we have106
xt+1−x∗ = xt−x∗ − h∇f(xt) = xt−x∗ − hH(xt − x∗) = (I − hH)t+1(x0 − x∗) . (10) In this case, the polynomial associated to gradient descent is Pt(λ) = (1− hλ)t.107
The above proposition can be used to obtain worst-case rates for first order methods by bounding108 their associated polynomials. Indeed, using the Cauchy-Schwartz inequality in (9) leads to109 ‖xt − x∗‖ ≤ sup
λ∈Λ |Pt(λ)| ‖x0 − x∗‖ =⇒ rt = sup λ∈Λ |Pt(λ)|, where P (0) = 1 . (11)
Therefore, finding the algorithm with the fastest worst-case rate can be equivalently framed as the110 problem of finding the polynomial with smallest value on the eigenvalue support Λ, subject to the111 normalization condition Pt(0) = 1. Such polynomials are referred to as minimax. Throughout the112 paper, we use this polynomial-based approach to find methods with optimal rates.113
An important property of minimax polynomials is their equioscillation on Λ (see Theorem C.1 and114 its proof for a formal statement).115 Definition 4.3. (Equioscillation) A polynomial Pt equioscillates on Λ if it verifies Pt(0) = 1 and116 there exist λ0 < λ1 < . . . < λt ∈ Λ such that117
Pt(λi) = (−1)i max λ∈Λ |Pt(Λ)| . (12)
Example 4.4 (Λ is an interval). The t-th order Chebyshev polynomials of the first kind Tt satisfy118 the equioscillation property on [−1, 1]. It follows that minimax polynomials on Λ = [µ,L] can be119 obtained by composing the Chebyshev polynomial Tt with the linear transformation σΛ1 :120
Tt ( σΛ1 (λ) ) Tt ( σΛ1 (0) ) = arg min P∈Rt[X],P (0)=1 sup λ∈Λ |P (λ)| , with σΛ1 (λ) = L+ µ L− µ − 2 L− µ λ , (13)
where σΛ1 maps the interval [µ, L] to [−1, 1]. The optimization method associated with this minimax121 polynomial is the Chebyshev semi-terative method [Flanders and Shortley, 1950, Golub and Varga,122 1961] (described also in Appendix B.1). This method achieves the lower complexity bound for123 smooth strongly convex quadratic minimization, see for instance [Nemirovsky, 1995, Chapter 12] or124 [Nemirovsky, 1992, Nesterov, 2003].125
The next proposition provides the main results in this subsection, which is key for obtaining Algo-126 rithm 2. It characterizes the even degree minimax polynomial in the setting of Section 3, that is,127 when Λ is the union of 2 intervals of same size. In this case, the minimax solution is also based on128 Chebyshev polynomials, but composed with a degree-two polynomial σΛ2 .129 Proposition 4.5. Let Λ = [µ1, L1] ∪ [µ2, L2] be an union of two intervals of the same size130 (L1−µ1 = L2−µ2) and letm be as defined in Algorithm 2. Then the minimax polynomial (solution131 to (12)) is, for all t = 2n, n ∈ N+0 ,132 Tn ( σΛ2 (λ)
) Tn ( σΛ2 (0) ) = arg min P∈Rt[X], P (0)=1 sup λ∈Λ |P (λ)| , with σΛ2 (λ) = 2 ( 1 +m 2 √ m )2( 1− λ L1 )( 1− λ µ2 ) − 1 .
4.2 Generalization to Longer Cycles133
The polynomial in Example 4.4 uses a linear link function σΛ1 to map Λ to [−1, 1]. In Proposition 4.5,134 we see that a degree two link function σΛ2 can be used to find the minimax polynomial when Λ is the135 union of two intervals. This section generalizes this approach and considers higher-order polynomials136 for σK . We start with the following parametrization, with an arbitrary polynomial σK of degree K,137
Pt(λ;σK) , Tn (σK(λ))
Tn (σK(0)) , ∀t = Kn, n ∈ N+0 . (14)
As we will see in the next subsection, this parametrization allows considering cycles of step-sizes.138 Our goal now is to find the σK that obtains the fastest convergence rate possible. The next proposition139 quantifies its impact on the asymptotic rate and its proof can be found in Appendix D.1.140 Proposition 4.6. For a given σK such that supλ∈Λ|σK(λ)| = 1, the asymptotic rate factor τσK of141 the method associated to the polynomial (14) is142
1− τσK = lim t→∞ t √ sup λ∈Λ |Pt(λ;σK)| = ( σ0 − √ σ20 − 1 ) 1 K , with σ0 , σK(0) . (15)
For a fixed K, the asymptotic rate (15) is a decreasing function of σ0. This motivates the introduction143 of the “optimal” degree K polynomial σΛK as the one that solves144
σΛK , arg max σ∈RK [X] σ(0) s.t. sup λ∈Λ |σ(λ)| = 1 . (16)
Using the above definition, we recover the σΛ1 and σ Λ 2 from Example 4.4 and Proposition 4.5.145
Finding the polynomial. Finding an exact and explicit solution for the general K and Λ case146 is unfortunately out of reach, as it involves solving a potentially difficult system of K non-linear147 equations. Here we describe an approximate approach. Let σΛK(x) = ∑K i=0 σix
i. We propose to148 discretize Λ into N different points {λj}, then solve the linear problem149
max σi
σ0 s.t. −1 ≤ ∑K i=0 σiλ i j ≤ 1, ∀j = 1, . . . , N . (17)
To check the optimality, it suffices to verify that the polynomial σΛK satisfies the equioscillation150 property (Definition 4.3), as depicted in Figure 3.151 Remark 4.7 (Relationship between optimal and minimax polynomials). For later reference, we note152 that the optimal polynomial σΛK is equivalent to finding a minimax polynomial on Λ and to rescale it.153 More precisely, σΛK is optimal if and only if σ Λ K/σ Λ K(0) is minimax.154
4.3 Cyclical Heavy Ball and (Non-)asymptotic Rates of Convergence155
We now describe the link between σΛK and Algorithm 3. Using the recurrence for Chebyshev156 polynomials of the first kind in (14), we have ∀t = Kn, n ∈ N+0 ,157 Tn+1(σ Λ K(λ))
Tn+1(σΛK(0)) = 2σΛK(λ)
[ Tn(σ Λ K(λ))
Tn(σΛK(0))
] [ Tn(σ Λ K(0))
Tn+1(σΛK(0)) ] ︸ ︷︷ ︸
=an
− [ Tn−1(σ Λ K(λ))
Tn−1(σΛK(0))
] [ Tn−1(σ Λ K(0))
Tn+1(σΛK(0)) ] ︸ ︷︷ ︸
=bn
.
It still remains to find an algorithm associated with this polynomial. To obtain one in the form of158 Algorithm 1, one can use the stationary behavior of the recurrence. From [Scieur and Pedregosa,159 2020], the coefficients an and bn converge as n→∞ to their fixed-points a∞ and b∞. We therefore160 consider here an asymptotic polynomial P̄t(λ;σΛK), whose recurrence satisfies161
P̄t(λ;σ Λ K) = 2a∞σ Λ K(λ)P̄t−K(λ;σ Λ K)− b∞P̄t−2K(λ;σΛK) . (18)
Similarly to K = 1, where this limit recursion corresponds to PHB, this recursion corresponds to162 an instance of Algorithm 3 (see Proposition 4.9 below), further motivating the cyclical heavy ball163 algorithm.164
The following theorem is the main result of this section and characterizes the convergence rate of165 Algorithm 1 for arbitrary momentum and step-size sequences {hi}i∈J1,KK. By optimizing over these166 parameters, we obtain a method associated to (18), whose rate is described in Proposition 4.9. All167 proofs can be found in Appendix D.2.168
Theorem 4.8. The worst-case rate of convergence of Algorithm 1 on CΛ with an arbitrary momentum169 m and an arbitrary sequence of step-sizes {hi} is170
1− τ =  √ m, if σsup ≤ 1 √ m ( σsup + √ σ2sup − 1 )1/K , if σsup ∈ ( 1, 1 +mK 2 ( √ m) K ) ≥ 1 (no convergence) if σsup ≥ 1 +mK
2 ( √ m) K
, (19)
where σsup , sup λ∈Λ |σ(λ; {hi},m)|, and σ(λ; {hi},m) is the K-degree polynomial171
σ(λ; {hi},m) , 1
2 Tr
([ 1+m−hK−1λ√ m
−1 1 0
] [ 1+m−hK−2λ√ m
−1 1 0
] . . . [ 1+m−h0λ√ m −1
1 0
]) . (20)
Proposition 4.9. Let σ(λ; {hi},m) be the polynomial defined by (20), and σΛK be the optimal link172 function of degree K defined by (16). If the momentum m and the sequence of step-sizes {hi} satisfy173
σ(λ; {hi},m) = σΛK(λ) , (21)
then 1) the parameters are optimal, in the sense that they minimize the asymptotic rate factor from174 Theorem 4.8, 2) the optimal momentum parameter is175
m = ( σ0 − √ σ20 − 1 )2/K , where σ0 = σΛK(0) , (22)
3) the iterates from Algo. 3 with parameters {hi} and m form a polynomial with recurrence (18),176 and 4) Algorithm 3 achieves the worst-case rate rAlg. 3t and the asymptotic rate factor 1− τAlg. 3177
rAlg. 3t = O ( t ( σ0 − √ σ20 − 1 )t/K) , 1− τAlg. 3 = ( σ0 − √ σ20 − 1 )1/K . (23)
Solving the system (21) The system is constructed by identification of the coefficients in both178 polynomials σΛK and σ(λ; {hi},m), which can be solved using a naive grid-search for instance. We179 are not aware of any efficient algorithm to solve this system exactly, although it is possible to use180 iterative methods such as steepest descent or Newton’s method.181

heading: 4.4 Best Achievables Worst-case Guarantees on CΛ182
text: This section discusses the (asymptotic) optimality of Algorithm 3. In Section 4.2, the polynomial183 Pt( · ;σΛK) was written as a composition of Chebyshev polynomials with σΛK , defined in (16). The184 best K is chosen as follows: we solve (16) for several values of K, then pick the smallest K among185 the minimizers of (15). However, following such steps does not guarantee that the polynomial PΛt,K186 is minimax, as it is not guaranteed to minimize the worst-case rate supλ∈Λ |Pt(λ)| (see (11)).187 We give here an optimality certificate, linked to a generalized version of equioscillation. In short, if188 we can find K non overlapping intervals (more formally, whose interiors are disjoint) Λi in Λ such189 that σΛK(Λi) = [−1, 1] then PΛt,K is minimax for all t = nK, n ∈ N + 0 . The detailed result is provided190 by Theorem C.2. A direct consequence of this result is the asymptotic optimality of Algorithm 3, i.e.,191 there exists no first order algorithm with a better asymptotic rate 1− τ for the function class CΛ.192 It is possible that such σΛK does not exist for a given Λ. A complete characterization of the set Λ for193 which there exists such σΛK is out of the scope of this paper. A partial answer is given in [Fischer,194 2011] when Λ is the union of two intervals. However, the problem remains open in the general case.195
5 Local Convergence for Non-Quadratic Functions196
When f is twice-differentiable, it is possible to show local convergence rates when x0 is close197 enough to x∗ [Polyak, 1964]. We give here a similar result that applies to Algorithm 1 (see proof in198 Appendix E). Those results are only local, as it is possible to find pathological counter-examples for199 which even PHB does not converge globally, for some specific initialization [Lessard et al., 2016].200
Theorem 5.1 (Local convergence). Let f : Rd 7→ R be a (potentially non-quadratic) twice continu-201 ously differentiable function, x∗ a local minimizer, and H be the Hessian of f at x∗ with Sp(H) ⊆ Λ.202 Let xt denote the result of running Algorithm 1 with parameters h1, h2, · · · , hK ,m, and let 1− τ be203 the linear convergence rate on the quadratic objective (OPT). Then we have204
∀ε > 0,∃ open set Vε : x0, x∗ ∈ Vε =⇒ ‖xt − x∗‖ = O((1− τ + ε)t)‖x0 − x∗‖. (24)
In short, when Algorithm 1 is guaranteed to converge at rate 1− τ on (OPT), then the convergence205 rate on a nonlinear functions can be arbitrary close to 1− τ when x0 is sufficiently close to x∗.206
6 Experiments207
In this section we present an empirical comparison of the cyclical heavy ball method for different208 length cycles across 4 different problems. We consider two different problems, quadratic and logistic209 regression, each applied on two datasets, the MNIST handwritten digits [Le Cun et al., 2010] and210 a synthetic dataset. The results of these experiments, together with a histogram of the Hessian’s211 eigenvalues are presented in Figure 4 (see caption for a discussion).212
Dataset description. The MNIST dataset consists of a data matrix A with 60000 images of hand-213 written digits each one with 28× 28 = 784 pixels. The synthetic dataset is generated according to214 a spiked covariance model [Johnstone, 2001], which has been shown to be an accurate model of215 covariance matrices arising for instance in spectral clustering [Couillet and Benaych-Georges, 2016]216 and deep networks [Pennington and Worah, 2017, Granziol et al., 2020]. In this model, the data217 matrix A = XZ is generated from a m× n random Gaussian matrix X and an m×m deterministic218 matrix Z. In our case, we take n = 1000,m = 1200 and Z is the identity where the first three entries219 are multiplied by 100 (this will lead to three outlier eigenvalues). We also generate an n-dimensional220 target vector b as b = Ax or b = sign(Ax) for the quadratic and logistic problem respectively.221
Objective function For each dataset, we consider a quadratic and a logistic regression problem,222 leading to 4 different problems. All problems are of the form minx∈Rp 1n ∑n i=1 `(A > i x, bi) + λ‖x‖2,223 where ` is a quadratic or logistic loss, A is the data matrix and b are the target values. We set the224 regularization parameter to λ = 10−3‖A‖2. For logistic regression, since guarantees only hold at225 a neighborhood of the solution (even for the 1-cycle algorithm), we initialize the first iterate as the226 result of 100 iteration of gradient descent. In the case of logistic regression, the Hessian eigenvalues227 are computed at the optimum.228
7 Conclusion229
This work is motivated by two recent observations from the optimization practice of machine learning.230 First, cyclical step-sizes have been shown to enjoy excellent empirical convergence [Loshchilov and231 Hutter, 2017, Smith, 2017]. Second, spectral gaps are pervasive in the Hessian spectrum of deep232 learning models [Sagun et al., 2017, Papyan, 2018, Ghorbani et al., 2019, Papyan, 2019]. Based on233 the simpler context of quadratic convex minimization, we develop a convergence-rate analysis and234 optimal parameters for the heavy ball method with cyclical step-sizes. This analysis highlights the235 regimes under which cyclical step-sizes have faster rates than classical accelerated methods. Finally,236 we illustrate these findings through numerical benchmarks.237
Main Limitations. In Section 3 we gave explicit formulas for the optimal parameters in the case238 of the 2-cycle heavy ball algorithm. These formulas depend not only on extremal eigenvalues—as is239 usual for accelerated methods—but also on the spectral gap R. The gap can sometimes be computed240 after computed the top eigenvalues (e.g. top-2 eigenvalue for MNIST). However, in general, there241 is no guarantee on how many eigenvalues are needed to estimate it. Moreover, global convergence242 result rely heavily on the quadratic assumption.243
Another limitation regards long cycles. For cycles longer than 2, we have only given an implicit244 formula to set the optimal parameters (Proposition 4.9). This involves solving a set of non-linear245 equations whose complexity increases with the cycle length. That being said, cyclical step-sizes246 might significantly enhance convergence speeds both in terms of worst-case rates and empirically,247 and this work advocates that new tuning practices involving different cycle lengths might be relevant.248
Broader Impact. This work is mostly theoretical, and as such we believe it does not present direct249 societal consequences. However, the methods described in this paper can be used to train machine250 learning models which could themselves have societal consequences. For example, the deployment251 of machine learning models in decision-making has been shown to suffer from gender and racial bias252 and to amplify existing inequalities, see for instance [Hutchinson and Mitchell, 2019, Barocas et al.,253 2017, Obermeyer et al., 2019].254
References255 Solon Barocas, Moritz Hardt, and Arvind Narayanan. Fairness in machine learning. Nips tutorial,256 2017.257 Dimitri P. Bertsekas. Nonlinear programming. Journal of the Operational Research Society, 1997.258 Romain Couillet and Florent Benaych-Georges. Kernel spectral clustering of large dimensional data.259 Electronic Journal of Statistics, 2016.260 Bernd Fischer. Polynomial based iteration methods for symmetric linear systems. SIAM, 2011.261 Donald A. Flanders and George Shortley. Numerical determination of fundamental modes. Journal262 of Applied Physics, 1950.263 Behrooz Ghorbani, Shankar Krishnan, and Ying Xiao. An investigation into neural net optimization264 via hessian eigenvalue density. In International Conference on Machine Learning (ICML), 2019.265 Gene H. Golub and Richard S. Varga. Chebyshev semi-iterative methods, successive overrelaxation266 iterative methods, and second order Richardson iterative methods. Numerische Mathematik, 1961.267 Diego Granziol, Xingchen Wan, Samuel Albanie, and Stephen Roberts. Explaining the Adaptive268 Generalisation Gap. arXiv preprint arXiv:2011.08181, 2020.269 Magnus R. Hestenes and Eduard Stiefel. Methods of conjugate gradients for solving linear systems,270 volume 49. NBS Washington, DC, 1952.271 Ben Hutchinson and Margaret Mitchell. 50 years of test (un) fairness: Lessons for machine learning.272 In Proceedings of the Conference on Fairness, Accountability, and Transparency, 2019.273 Iain M. Johnstone. On the distribution of the largest eigenvalue in principal components analysis.274 Annals of statistics, 2001.275 Yann Le Cun, Corinna Cortes, and Chris Burges. MNIST handwritten digit database. ATT Labs276 [Online], 2010.277 Laurent Lessard, Benjamin Recht, and Andrew Packard. Analysis and design of optimization278 algorithms via integral quadratic constraints. SIAM Journal on Optimization, 2016.279 Ilya Loshchilov and Frank Hutter. SGDR: stochastic gradient descent with warm restarts. In280 International Conference on Learning Representations (ICLR), 2017.281 Arkadi S. Nemirovsky. Information-based complexity of linear operator equations. Journal of282 Complexity, 1992.283 Arkadi S. Nemirovsky. Information-based complexity of convex programming. Lecture Notes, 1995.284 Yurii Nesterov. Introductory Lectures on Convex Optimization. Springer, 2003.285 Ziad Obermeyer, Brian Powers, Christine Vogeli, and Sendhil Mullainathan. Dissecting racial bias in286 an algorithm used to manage the health of populations. Science, 2019.287 Vardan Papyan. The full spectrum of deepnet hessians at scale: Dynamics with SGD training and288 sample size. arXiv preprint arXiv:1811.07062, 2018.289 Vardan Papyan. Measurements of Three-Level Hierarchical Structure in the Outliers in the Spectrum290 of Deepnet Hessians. In International Conference on Machine Learning (ICML), 2019.291 Jeffrey Pennington and Pratik Worah. Nonlinear random matrix theory for deep learning. In Advances292 on Neural Information Processing Systems (NIPS), 2017.293 Boris T. Polyak. Some methods of speeding up the convergence of iteration methods. USSR294 computational mathematics and mathematical physics, 1964.295 Levent Sagun, Utku Evci, V. Ugur Guney, Yann Dauphin, and Leon Bottou. Empirical analysis of the296 Hessian of over-parametrized neural networks. arXiv preprint arXiv:1706.04454, 2017.297 Damien Scieur and Fabian Pedregosa. Universal Asymptotic Optimality of Polyak Momentum. In298 International Conference on Machine Learning (ICML), 2020.299 Leslie N. Smith. Cyclical learning rates for training neural networks. In 2017 IEEE Winter Conference300 on Applications of Computer Vision (WACV). IEEE, 2017.301 Ilya Sutskever, James Martens, George Dahl, and Geoffrey Hinton. On the importance of initialization302 and momentum in deep learning. In International Conference on Machine Learning (ICML), 2013.303
Checklist304
1. For all authors...305 (a) Do the main claims made in the abstract and introduction accurately reflect the paper’s306 contributions and scope? [Yes] The Introduction (Section 1) details where all results307 can be found.308
(b) Did you describe the limitations of your work? [Yes] There is a paragraph "Main309 Limitations" in the Conclusion (Section 7).310
(c) Did you discuss any potential negative societal impacts of your work? [N/A] As stated311 in the "Broader Impact" section, this work is mostly theoretical and as such we believe312 it doesn’t present a direct societal impact.313
(d) Have you read the ethics review guidelines and ensured that your paper conforms to314 them? [Yes]315
2. If you are including theoretical results...316 (a) Did you state the full set of assumptions of all theoretical results? [Yes] In each and317 every statement we make.318 (b) Did you include complete proofs of all theoretical results? [Yes] All proofs are available319 in the supplementary material.320 3. If you ran experiments...321
(a) Did you include the code, data, and instructions needed to reproduce the main exper-322 imental results (either in the supplemental material or as a URL)? [Yes] URLs are323 provided in the supplementary material.324
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they325 were chosen)? [Yes] In the experiments section (Section 6).326
(c) Did you report error bars (e.g., with respect to the random seed after running experi-327 ments multiple times)? [No] .328
(d) Did you include the total amount of compute and the type of resources used (e.g., type329 of GPUs, internal cluster, or cloud provider)? [Yes] , in Appendix F330
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...331 (a) If your work uses existing assets, did you cite the creators? [Yes] In the "Dataset332 description" paragraph of the Experiments section 6.333 (b) Did you mention the license of the assets? [N/A]334 (c) Did you include any new assets either in the supplemental material or as a URL? [N/A]335 There is no new asset. We used MNIST existing Dataset as well as a synthetic dataset336 whose construction is described in papers cited in the Experiments section 6.337
(d) Did you discuss whether and how consent was obtained from people whose data you’re338 using/curating? [N/A]339
(e) Did you discuss whether the data you are using/curating contains personally identifiable340 information or offensive content? [N/A]341
5. If you used crowdsourcing or conducted research with human subjects...342 (a) Did you include the full text of instructions given to participants and screenshots, if343 applicable? [N/A]344 (b) Did you describe any potential participant risks, with links to Institutional Review345 Board (IRB) approvals, if applicable? [N/A]346 (c) Did you include the estimated hourly wage paid to participants and the total amount347 spent on participant compensation? [N/A]348

Review summaries:
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. 

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.

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.   

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.