Accelerating SGD with momentum for over-parameterized learning
Authors: Chaoyue Liu
Mikhail Belkin
Venue:  (2020)
Keywords: SGD
acceleration
momentum
stochastic
over-parameterized
Nesterov

Abstract: 
Nesterov SGD is widely used for training modern neural networks and other machine learning models. Yet, its advantages over SGD have not been theoretically clarified. Indeed, as we show  in this paper, both theoretically and empirically, Nesterov SGD with any parameter selection does not in general provide acceleration over ordinary SGD. Furthermore, Nesterov SGD may diverge for step sizes that ensure convergence of ordinary SGD. This is in contrast to the classical results in the deterministic setting, where the same step size ensures accelerated convergence of the Nesterov's method over optimal gradient descent.

To address the non-acceleration issue, we  introduce a compensation term to Nesterov SGD. The resulting  algorithm, which we call MaSS, converges  for same step sizes as SGD. We prove that MaSS obtains an accelerated convergence rates over SGD for any mini-batch size in the linear setting.  For full batch, the convergence rate of MaSS matches the well-known accelerated rate of the Nesterov's method. 

We also analyze the  practically important question of the dependence of the convergence rate and  optimal hyper-parameters on the mini-batch size, demonstrating three distinct regimes: linear scaling, diminishing returns and saturation.

Experimental evaluation of MaSS for several standard  architectures of deep networks, including ResNet and convolutional networks, shows improved performance over SGD, Nesterov SGD  and Adam. 

Published as a conference paper at ICLR 2020
ACCELERATING SGD WITH MOMENTUM FOR OVER- PARAMETERIZED LEARNING
Chaoyue Liu
Mikhail Belkin
Department of Computer Science The Ohio State University Columbus, OH 43210
Department of Computer Science
The Ohio State University
Columbus, OH 43210 mbelkiněcse ohio state. edu
1iu. 265 265 edu
ABSTRACT
Nesterov SGD is widely used for training modern neural networks and other ma- chine learning models. Yet, its advantages over SGD have not been theoretically clarified. Indeed, as we show in this paper, both theoretically and empirically, Nesterov SGD with any parameter selection does not in general provide acceler- ation over ordinary SGD. Furthermore, Nesterov SGD may diverge for step sizes that ensure convergence of ordinary SGD. This is in contrast to the classical re- sults in the deterministic setting, where the same step size ensures accelerated convergence of the Nesterov's 's method over optimal gradient descent.
To address the non-acceleration issue. we introduce compensation term to Nes- terov SGD, The resulting algorithm, which call MaSS, converges for same step sizes as SGD. We prove that MaSS obtains an accelerated convergence rates over SGD for any mini-batch size in the linear setting. For full batch, the convergence rate of MaSS matches the well-known accelerated rate of the Nesterov's 's method.
We also analyze the practically important question of the dependence of the con- vergence rate and optimal hyper- parameters on the mini-batch size, demonstrating three distinct regimes: linear scaling, diminishing returns and saturation.
Experimental evaluation of MaSS for several standard architectures of deep net- works, including ResNet and convolutional networks, shows improved perfor- mance over SGD, SGD+Nesterov and Adam.
INTRODUCTION
Many modern neural networks and other machine learning models are over-parametrized (5). These models are typically trained to have near zero training loss, known as interpolation and often have strong generalization performance, indicated by range of empirical evidence including (23 3) Due to a key property of interpolation automatic variance reduction (discussed Section 2. stochastic gradient descent (SGD) with constant step size is shown converge to the optimum of convex loss function for wide range of step sizes (12). Moreover, the optimal choice of step size 17" for SGD that setting can be derived analytically.
The goal of this paper is to take a step toward understanding momentum-based SGD in the interpo- lating setting, Among them, stochastic version of Nesterov's acceleration method (SGD+Nesterov) is arguably the most widely used to train modern machine learning models in practice. The popular- ity of SGD+Nesterov is tied to the well-known acceleration of the deterministic Nesterov's 's method over gradient descent (15). Yet, has not not theoretically clear whether Nesterov SGD accelerates over SGD. As we show in this work, both theoretically and empirically, Nesterov SGD with any parameter selection does not in general provide acceleration over ordinary SGD. Furthermore, Nesterov SGD may diverge, even in the linear setting, for step sizes that guarantee convergence of ordinary SGD. Intuitively, the lack of acceleration stems from the fact that, to ensure convergence, the step size of SGD+Nesterov has to be much smaller than the optimal step size for SGD. This is in contrast the deterministic Nesterov method, which accelerates using the same step size as optimal gradient de- scent. As we prove rigorously in this paper, the slow-down of convergence caused by the small step

---

Published as a conference paper at ICLR 2020
size negates the benefit brought by the momentum term. We note that similar lack of acceleration for the stochastic Heavy Ball method was analyzed in
To address the non-acceleration of SGD+Nesterov, to allow convergence for the same range of step sizes as SGD. The resulting algorithm, MaSS (Momentum-addeds Stochastic Solver Jupdatess the weights and using the following rules (with the compensation term underlined):
introduce additional compensation term
Wi+1
V Up+1 F (1+7)w+41 - yw: + 77 f(..).
(1)
-12
-20
5G0
Here, V represents the stochastic gradient. The step size h. the momentum parameter y (0, 1) and the compen- sation parameter 1/2 independent of
SGD-tandaroe
3ED Houry
M455
1060
1550 2500
2000
3500
4000
We proceed to analyze theoretical convergence proper-
Figure 1: Non-acceleration of Nesterov SGD and fast convergence MaSS.
ties of MaSS in the interpolated regime. Specifically, we show that in the linear setting MaSS converges exponen- tially for the same range of step sizes plain SGD, and the optimal choice of step size for MaSS is exactly 77' which is optimal for SGD. Our key theoretical result shows that MaSS has accelerated convergence rate over SGD. Furthermore, in the full batch (deterministic) scenario. our analysis selects 0, thus reducing MaSS to the classical Nesterov's method (15). In this case our con- vergence rate also matches the well-knoww convergence rate for the Nesterov's method (15 4 This acceleration is illustrated in Figure [ Note that NeDDoNest (as well as Stochastic Heavy Ball) does not converge faster than SGD, in line with our theoretical analysis. also prove exponential convergence of MaSS in more general convex setting under additional conditions.
We further analyze the dependence of the convergence rate (mmie and optimal hyper-parameters on the mini-batch size m. We identify three distinct regimes of dependence defined by two critical values m and mž: linear scaling, di- minishing returns and saturation, as illustrated in Figure 2 The convergence speed per iteration s(m), as well as the optimal hyper-panne pareee--raeeeers, increase linearly as in the lin- ear scaling regime, sub-linearly in the diminishing returns regime, and can only increase by small constant factor in the saturation regime. The critical values m and m. are derived analytically. We note that the intermediate "dimin-
Linear Scaling
Diminishing returns
Saturation
Butthh sOB
Figure Convergence speed per it- eration s(m). Larger s(m) indicates faster convergence per iteration.
ishing terurns" regime is new and is not found in SGD (12). To the best of our knowledge, this is the first analysis of mini-batch dependence for accelerated stochastic gradient methods.
We also experimentally evaluate MaSS on deep neural networks, which are non-convex. We show that MaSS outperforms SGD, SGD+Nesterov and Adam (10) both in optimization and general- ization, on different architectures of deep neural networks including convolutional networks and ResNet 77).
The paper is organized follows: In section we introduce notations and preliminary results. In section 3] we discuss the non-acceleration SGD+Nesterov. section we introduce MaSS and analyze its convergence and optimal hyper-parameter selection. In section 5 we analyze the mini-batch MaSS. In Section we show experimental results.
1.1 RELATED WORK
ever-parameterized models have drawn increasing attention in the literature as many modern ma- chine learning models, especially neural networks, over- peraaamemttee (5) and show strong gen- eralization performance (16) 23 2}. Over parameterized models usually result in nearly perfect fit (or interpolation) of the training data 233 18 3). Exponential convergence of SGD with constant step size under interpolation and its dependence on the batch size analyzed in (12).
"oode url: http:://ittuhh.cm////62995//5
2

---

Published as a conference paper at ICLR 2020
There are few works that show or indicate the non-acceleration of existing stochastic momentum methods. First of all, the work (9) theoretically proves non non-acceleration of stochastic Heavy Ball method (SGD+HB) over SGD certain synthetic data. Furthermore, these authors provide experi- mental evidence that SGD++Nsterov also converges at the same rate as SGD on the same data. The work (22) theoretically shows that, for sufficiently small step-sizes, NelD+Nesterov and SGD+HBB is equivalent to SGD with a larger step size. However, the results in (22) do not exclude the possibility that acceleration is possible when the step size is larger. The work (II concludes that "momentum hurts the convergence within the neighborhood of global optima", based on theoretical analysis of SGD+HB. These results are consistent with our analysis of the standard SGD+Nesterro. However, this conclusion does not apply to all momentum methods. Indeed, we will show that MaSS provably improves convergence over SGD.
There is large body of work, both practical and theoretical, on SGD with momentum, includ- ing (10 8 D. Adam (IO), and its variant AMSGrad (17), are among the most practically used SGD) methods with momentum. Unlike our method, Adam adaptively adjusts the step size according to a weight-decayed accumulation of gradient history. In (8) the authors proposed an accelerated SGD algorithm, which can be written in the form shown on the right hand side in Eq 8 but with different parammerr selection. Their ASGD algorithm also has a tail-averaging step at the final stage. In the interpolated setting (no additive noise) their analysis yields convergence rate of (1, R) exp( 9/KLR )) compared to O(exp(- VRIR )) for our algorithm with batch size 1.
We provide some experimental comparisons between their ASGD algorithm and MaSS in Fig.
The work (11 proposes and analyzes another first-order momentum algorithm and derives conver- gence rates under different set of conditions - the strong growth condition for the loss function in addition to convexity. As shown in Appendix F33 on the example of a Gaussian distributed data, the rates obtained in (21) can be slower than those for SGD. In contrast, our algorithm is guaranteed to never have a slower convergence rate than SGD. Furthermore, in the same Gaussian setting MaSS matches the optimal accelerated full- aall-gradient Nesterov rate.
Additionally, in our work we consider the practically important dependence of the convergence rate and optimal parameter selection on the mini-batch size, which to the best of our knowledge, has not been analyzed for momentum methods.
2 NOTATIONS AND PRELIMINARIES
Given dataset D = ((x;; C CRd x C, we consider an objective function of the form f(w) E fi(w), where Si only depends a single data point (x;, Let Vʃ denote the exact gradient, and nf denote the unbiased stochastic gradient evaluated based on mini-batch of size m. For simplicity, we also denote ff(w) := V.f(w). We use the concepts of strong convexity and smoothness of functions, see definitions in Appendix B.I For loss function with p-strong convexity and L-smoothness, the condition number x: is defined as x = L/
In the case of the square loss, fi()) En x,x;'. Let L and μ be the largest and the smallest non-zero eigenvalues of the Hessian respectively. Then the condition number is then k = L/μ (note that zero eigenvalues can be ignored in our setting, see Section 4.
1 (W x; v1)2 and the Hessian matrix is H
Stochastic Condition Numbers. For a quadratic loss function, let im := D= X denotes mini-batch estimate of H. Define Ln be the smallest positive number such that EE [||||] L, H, and denote
2xx
L == L//m + (m - 1)L/m.
(2)
Given a mini-batch size m, we define the m-stochastic condition number as Km := Lm/Hs
Following (8), we introduce the quantity R (called statistical condition number in 8 which is the smallest positive real number such that E ||| = RH.
Remark 1. We note that L 2 L, since E ||| [ = [| = H² + E HY = H²
Consequently, according to the definition of L,m in [ we have
Im 2 L., Vm 2 1; I.m + I,, as m co.
(3)
3

---

Published as a conference paper at ICLR 2020
Hence, the quadratic loss function is also - smooth, for all m 2 1. By the definition of Km, also have
Km K. vm 2 1; Km
m +
(4)
Remark 2. is important to note that R S K1, since
[|] || XX "
E [[X]]|x>> 3 KIH.
2.1 CONVERGENCE OF SGD FOR OVER PIER-PARAMETRIEED MODELS AND OPTIMAL STEP SIZE
We consider over-parannn werrpaarmeetrieed models that have zero training loss solutions on the training data (e.g.. g.g.. (23)). A solution fs(w) which fits the training data perfectly fi(w) = 0, Vi = 1,2, n, is known as interpolating. In the linear setting, interpolation implies that the linear system {x] w yi 12 has at least one solution.
key property of interpolation is Automatic Variance Reduction (AVR), where the variance of the stochastic gradient decreases zero as the weight w approaches the optimal w
Var Var|Vnn ff (w)] = ||w (H))) H)
(5)
For a detailed discussion of AVR see Appendix B.2
Thanks to AVR, plain SGD with constant step size can be shown to converge exponentially for strongly convex loss functions (13 12). The set of acceptable step sizes is (0, 2/ Lm). where Lm is defined in Eq and m is the mini-batch size. Moreover, the optimal step size 17" (m) of SGD that induces fastest convergence guarantee is proven to be 1/ Lm (1)..
3 NON-ACCELFRAATOO OF SGD+NESTEROV
In this section we prove that SGD+Nesterov, with any constant hyper-parameter setting, does not generally improve convergence over optimal SGD. Specifically, we demonstrate setting where SGD+Nesterov can be proved to have convergence rate of (1 - O(1/k))), which same (up to a constant factor) as SGD. In contrast, the classical accelerated rate for the deterministic Nesterov's method is (1 - 1/V/)-
We will consider the following two-dimensional data-generating component decoupled model. Fix an arbitrary w' E IR² and randomly sample from NO, 2). The data points (x, y) are constructed follow:
01 C1. w.p. 0.5, 2. e2,
and y (w", x)
w.p. 0.5,
where e1, e2 E 2 are canonical basis vectors, 01 0g > 0. can be seen that L1 of #1 f and R = 6 (See Appendix F.I. This model is similar to that used to analyze the stochastic Heavy Ball method in (9)
The following theorem gives a lower bound for the convergence of SGD+Nesterov, regarding the linear regression problem on the component decoupled data model. See [opendix[[for the proof.
Theorem (Non-acceleration of SGD+Nesterov). Let {(x; 1:) be dataset generated accord- ing to the component decoupled model. Consider the optimization problem of minimizing quadratic function 2/ Ex(x 2 For any step size n 0 and momentum parameter 7 E (0,1) of *GstNesterov with random initialization, with probability one, there exists a T E NN such that Vl T.
(1 (1-2) [f(wo)- - f(w")),
[[f(w:)l-f(v)
where C' > 0 is a constant.
Compared with the convergence rate (1-1/k)* of SGD (1), this theorem shows that SGD+Nesterov does not accelerate over SGD. This result is very different from that in the deterministic gradient scenario, where the classical Nesterov's method has a strictly faster convergence guarantee than gradient descent (15).
Intuitively, the key reason for the non acceleration of SGD+Nesterov is condition on the step size required for non-divergence of the algorithm. Specifically, when momentum parameter 7 is close to
4

---

Published as a conference paper at ICLR 2020
is required be less than (((1-)))++((11>))) (precise formulation is given in Lemma in Appendix C.. The slow-down resulting from the small step size necessary to satisfy that condition cannot be compensated by the benefit of the momentum term. In particular, the condition on the step-size of SGiD+Nesterov excludes 17" that achieves fastest convergence for SGD. We show in the following corollary that, with the step size '/',, SGDD+Nsstrrov diverges. This is different from the deterministic scenario, where the Nesterov method accelerates using the same step size as gradient descent.
Corollary 1. Consider the same optimization problem as in Theorem Let step-size 1j 1 Gor and acceleration parameter o [0.6,] 1), then SGD+Nesterov with random initialization, diverges with probability I.
We empirically verify the non-acceleration of SGD+Nesterov well Corollary and Appendix F2
I in Section 6
MASS: ACCELERATING SGD
In this section, we propose MaSS, which introduces a compensation term (see [ onto SGD+Nesterov. We show that MaSS can converge exponentially for all the step sizes that re- sult in convergence of SGD, i.e., " (0,2/Lm). Importantly, we derive a convergence rate exp( -t/vKjj)) where R S for MaSS which is faster than the convergence rate for SGD exp(-t/K1). Moreover, we give an analytical expression for the optimal hyper-parameter setting,
For ease of analysis, we rewrite update rules of MaSS in Eq in the following equivalent form (introducing an additional variable v):
W+41 < u, 10a--17 f
We+1 < u 1 ((,,,,
Ve+1 < (1-a)v: au, - 8V ((r),
(8)
U++1 f + 7)++ - yw, + 72 ((:))
u4f1 t- Ita Ve+1 Ita W++1-
There is bijection between the haper-parameters (m) 1/ 7) and (7, 5), which is given by: 7= (1- a),
17, (1 / a).
Remark 3 (SGD+Nesterov). In the literature, the Nesterov's method sometimes written in similar form as the R.H.S. of 8 Since SGD+Nest has no compensation term, 8 has to be fixed as 1/aa, which is consistent with the parameter setting in (15).
Assumptions. We first assume square loss function, and later extend the analysis to general convex loss functions under additional conditions. For square loss function, the solution set W* == {w [( 0} is an affine subspace in the parameter space Rd. Given any w, we denote its closest w* Be aware that different
solution as w := arg minvew- ||w (wv. and define the error e w may correspond to different w", and that e and (stochastic) gradients are always perpendicular to W (see discussion in Appendix [B.3). Hence, no actual update happens along W For this reason, we can ignore zero eigenvalues of H and restrict our analysis to the span of the eigenvectors of the Hessian with non-zero eigenvalues.
Based on the equivalent form of MaSS in E the following theorem shows that, for square loss function the interpolation setting, MaSS guaranteed have exponential convergence when hyper-paranee param-parsmeters satisfy certain conditions.
Theorem 2 (Convergence of MaSS). Consider minimizing a quadratic loss function in the inter- polation setting. Let be the smallest non-zero eigenvalue of the Hessian matrix H. Let Lm be as defined in ? Denote kim := k/m + (m - -1//m. In MaSS with mini batch of size m, if the positive hyper-parametert 77, a. 8 satisfy the following two conditions:
a/5 S n.
adkn + 7 - 2) S 0,
(10)
then, after t iterations,
< a1= (1vo (110- w w + 5 |Wo - w w1())
E [
w-
-
||: w 1|2
Consequently,
I w < C a)',
for some constant C > O which depends on the initialization.
5

---

Published as a conference paper at ICLR 2020
Remark 4. By condition Eq for interpolated setting (12).
E 10
the admissible step size 17 is (0,2/ exactly the same SGD
Remark One can easily check that the hyper-parameter setting of SGD+Nesterov does not satisfy the conditions in Eq T0
Proof sketch for Theorem 2
Denote Ft E |llv+11 w" + 2 allwe+1 w= we show
that, under the update rules of MaSS Eq
Fit1 (1 a).Ft
(a/v 8) I
w
R8 + 811² 1o/Tm/a 2:100-22///// 2n0/aa)
|| w l
By the condition in Eq 10
S 0, C2 S 0, then the last two terms are non-positive. Hence,
Fi+1 Σ (1 - F.FF I (1 - a))
(11)
Using that [|W,-/ww 1 I aFF/6, we get the final conclusion. See detailed proof in Appendix D
Hyper-parammter Selection. From Theorem 2 we observe that the convergence rate is deter- mined by (1 (1-a)'. Therefore, larger a is preferred for faster convergence. Combining the conditions Eq TO we have
a² 22 ///m)
(12)
By setting 17" -1/Lm, which maximizes the right hand side of the inequality, we obtain the optimal selection a* 1/ Ryn- Note that this setting of 17 and a" determines unique 8* a" /p by the conditions in Eq 10 In summary,
1)"
(m(m) = Lm a (m)
v fim 5m) = a Km
(13)
By
9 the optimal selection of (y, 72, 7) would be:
1 (m) = L,m
(mm) = 1/1 V Vimmimmm Rm Ri + (1-2) (-R)
v Kmm
('m)
(14)
VKim Kim
Am is usually larger than 1, which implies that the coefficient 1/2 of the compensation term is non-negative. The non -engetttive coefficient 172 indicates that the weight u, is "over-descended" in SGD+Nesterov and needs to be compensated along the gradient direction.
important to note that the optimal step size for MaSS as in Eq 13 exactly the same as the op- timal one for SGD (12). With such hyper-parameter selection given in Eq 14 we have the following theorem for optimal convergence:
Theorem (Acceleration of MaSS), Under the same assumptions as in Theorem if we set hyper- parameters in MaSS as in T3 then after iteration of MaSS with mini batch of size m,
[ 12 < C C1- Kim Rmm)
(15)
for some constant C > O which depends the initialization.
Remark 6. With the optimal hyper-parameters in Eq 13
the asymptotic convergence rate of MaSS
is
( tt////mmnnnn (Mmmk)))
(16)
which is faster than the rate O (tem//mm) SGD (see (2)). since Km 2 Fi
Remark (MaSS Reduces the Nesterov's method for full batch). In the limit of full batch m +
0o, we have Ki + K, Ri - 1, the optimal parameter selection in Eq reduces to
vi I/L, 7" (Vr - 1)/(v=)+/// 1), n 0.
(17)
interesting to observe that, in the full batch (deterministic) scenario, the compensation term vanishes and 7/ and 7 are the same as those in Nesterov's method. Hence MaSS with the optimal hyper-parameter selection reduces to Nesterov's method the limit full batch. Moreover, the convergence rate in Theorem 3 reduces to ( (te-t//k) which is exactly the well known convergence rate of Nesterov's method (15 4)

---

Published as a conference paper at ICLR 2020
Extension to Convex Case. First, extend the definition of L1 to convex functions, L1
inf E R| |
& 2c (f(w)- - } and keep the definition of Lm the same as Eq
2
It can be shown that these definitions of L.. are consistent with those in the quadratic setting. We
assume that the smallest positive eigenvalue of Hessian (x) is lower bounded by > O, for all x.
Theorem 4. Suppose there exists a 1 -strongly convex and 1 -smoooh non-negative function g :
R + R such that g(w") 0 and (Vg(x), ff(2)) (1 c)(x w., 2 w"), vx, E R for
some > 0. In MaSS, if the hyper-parameters are set to be:
= 1/2mm))) a (1 (2km) == 1=/(2tmm)
(18)
then after iterations, there exists constant C such that, B[f(w.)) S SC. (1- 2=a)
5 LINEAR SCALING RULE AND THE DIMINISHING RETURNS
Based on our analysis, we discuss the effect of selection of mini-batch size m. We show that the domain of mini-batch size can be partitioned into three intervals by two critical points: mi min(Tn / / I. R),m) = max(I, / I, R). The three intervals/regimes are depicted in Figure and the detailed analysis is in Appendix G
m < m.. In this regime, we have Im z La/m, Km Fo R1/m and Km Fo R/m. The optimal selection of dlyper-praametes is approximated by:
Linear Scaling:
17" (m) ze -7 (1), a" (m) = a (1), (m)) ss (1),
and the convergence rate in Eq 16 is approximately O 0(e-m.//mms)) This indicates linear gains in convergence when m increases.
In the linear scaling regime, the hyper-paramens selec- tions follow Linear Scaling Rule (LSR): When the mini-batch size is multiplied by k. multiply all hyper- parameters (17, a, 8) by k. This parallels the linear scaling rule for SGD which is an accepted practice for training neural networks (6).
Convergence speed vs. mini-batch size
llass
Saturation
Dimbrishing
Moreover, increasing m results in linear gains in the con- vergence speed, i.e., one MaSS iteration with mini-batch size m is almost effective as m MaSS iterations with mini-batch size
Emriiiical
10
150
Figure 3: Convergence speed per itera- tion s (m). Larger sm) indicates faster convergence. Red solid curve: experi- mental results. Blue dash curve: theo- retical lower bound Vmmmmm- Critical mini-batch sizes: m 2 10, m² x 50.
Diminishing Returns: m E [mi, mi) In this regime, increasing m results in sublinear gains in convergence speed. One MaSS iteration with mini-batch size m is less effective than m MaSS iterations with mini-batch size 1.
Saturation: m 2 m². One MaSS iteration with mini-batch size m is nearly as effective (up to a multiplicative factor of 2) one iteration with full gradient.
This three regimes partition is different from that for SGD (2), where only linear scaling and satu- ration regimes present. An empirical verification of the dependence of the convergence speed on m is shown in Figure 3. See the setup in Appendix G
6 EMPIRICAL EVALUATION
Synthetic Data. empiricalyy verify the non-acceleration of SGD++esterov and the fast conver- gence of MaSS on synthetic data. Specifically, we optimize the quadratic function 2n
1 (x w
y: where the dataset ((x, b generated by the component decoupled model described in Section 3 We compare the convergence behavior of SGD+Nesterov with SGD, well as proposed method, MaSs, and several other methods: SGD+HB, ASGD (8). We select the best hyper-parameters from dense grid search for SGDD+Nesterov (step-size and momentum parameter),

---

Published as a conference paper at ICLR 2020
SGD+HB (step-size and momentum parameter) and SGD (step-size). For MaSS, do not tune the nyper-parameters but use the hyper- parameter setting suggested by our theoretical analysis in Section 4 For ASGD, we use the setting provided by (8).
Fig. shows the convergence behaviors of these algorithms on the setting of of 1. 1/20. We observe that the fastest convergence of SGD+Nesterov is almost iden- tical to that of SGD, indicating the non-acceleration of SGD+Nesterov. We also observe that our proposed method, MaSS, clearly outperforms the others. In Appendix [22, we provide additional experiments on more settings of the com- ponent decoupled data, and Gaussian distributed data. We also show the divergence of SGD+Nesterov with the same step size as SGD and MaSS in Appendix F22
30
500+ (iarr
1500 291
1455
120
1923
7900 1i0 1921
Figure 4: Comparison on com- ponent decoupled data. Hyper- parameters: we use optimal param- eters for SGD+Nesterov, SGD+HB and SGD; the setting in ( for ASGD; Eq. for for MaSS.
Real data: MNIST and CIFAR-10. We compare the op- timization performance of SGD, SGD+Nesterov and MaSS on the following tasks: classification of MNIST with a fully- connected network (FCN), classification of CIFAR-10 10 with a convolutional neural network (CNN) and Gaussian kernel regression on MNIST. See detailed description of the architectures in Ap- setting
pendix H.T In all the tasks and for all the algorithms, we select the best over dense grid search, except that we fix the momentum parameter = 0.9 for both SGD+Nesterov and MaSS, which is typically used in practice. All algorithms are implemented with mini batches of size 64 for neural network training.
Fig. shswwss the training curves of MaSS, SGD++Nesterov and SGD, which indicate the fast conver- gence of MaSS on real tasks, including the non-convex optimization problems on neural networks.
Fully connected Network on MNIST
CNN on CIFAR-10
Gaussion Kemel Regression
SGD
SGD
SGD- Neskerovv
SCD Nostertv
Nendaroo
Mad5
Spache
specha
Spocha
Figure 5: Comparison of SGD, SGD+Nesterov and MaSS on (left) fully-connected neural network, (middle) convolutional neural network, and (right) kernel regression.
Test Performance. We show that the solutions found by MaSS have good generalization perfor- mance. We evaluate the classification accuracy of MaSS, and compare with SGD, SGD+Nesterov and Adam, different modern neural networks: CNN and ResNet (7). See description of the chitectures in Appendix [H.] In the training processes, we follow the standard protocol of data augmentation and reduction of learning rafe, which are typically used to achieve state-of-the-an results in neural networks. In each task, we use the same initial learning rate for MaSs, SGD and SGD+Nesterov, and run the same number of epochs (150 epochs for CNN and 300 epochs for ResNet-32). Detailed experimental settings are deferred to Appendix H.2
Table compares the classification accuracy of these algorithms on the test set of CIFAR-10 (average of independent runs).
SGD
SGD+NESTEROV
MASS
ADAMŽ
CNN
0.01
81.40%
83.06%
83.97%
82.65%
0.3
82.41%
75.7956
84.48%
RESNET-32 32
0.1
91.92%
92.60%
92.77% %
92.27%
We observe that MaSS produces the best test performance. We also note that increasing initial learning rate may improves performance of MaSS and SGD, but degrades that of SGD+Nesterov. Moreover, in experiment, SGD+Nesterov with large step size 1 0.3 diverges in out of 8 runs on CNN and 2 out of runs on ResNet-32 (for random initialization), while MaSS and SGD converge on every run.
0.3
92.51%
91.13%1
92.71 %
Average of 3 runs that converge. Some runs diverge. Adam uses initial step size 0.001.
Table 1: Classification accuracy on test set of 10.
8

---

Published as a conference paper at ICLR 2020
ACKNOWLEDGEMENTS
This research was in part supported by NSF funding and a Google Faculty Research Award. GPUs donated by Nvidia were used for the experiments. We thank Ruoyu Sun for helpful comments concerning convergence rates. We thank Xiao Liu for helping with the empirical evaluation of our proposed method.
REFERENCES
[1] Zeyuan Allen-Zhu. Katyusha: The first direct acceleration stochastic gradient methods. In Proceedings of the 49th Anmual ACM SIGACT Symposium on Theory of Computing, pages 1200-1205. ACM, 2017.
[2] Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine- learning practice and classical biri-variance trade-off. Proceedings of the National Academy of Sciences, 116(32):15849-15855 2019.
[3] Mikhail Belkin, Siyuan Ma, and Soumik Mandal. To understand deep learning we need to understand kernel learning. arXiv preprint /80.0138,, 2018.
[4] Sébastien Bubeck et al. Convex optimization: Algorithms and complexity. Foundations and Trends in Machine Learning. 8(3-4)233-337, 2015.
[5] Alfredo Canziani, Adam Paszke, and Eugenio Culurciello. An analysis of deep neural network models for practical applications. arXiv preprint arXiv: 07678 2016.
[6] Priya Goyal, Piotr Dollár, Ross Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, Andrew Tulloch, Yangqing Jia, and Kaiming He. Accurate, large minibatch sgd: training imagenet in hour. arXiv preprint 17Xiv:170..0266 2017.
[7] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recogni- tion, pages 770-778, 2016.
[8] Prateek Jain, Sham M Kakade, Rahul Kidambi, Praneeth Netrapalli, and Aaron Sidford. Ac- celerating stochastic gradient descent. arXiv preprint arXiv: 704.00827,7 2017.
[9] Rahul Kidambi, Praneeth Netrapalli, Prateek Jain, and Sham M Kakade. On the insuffi ciency of existing momentum schemes for stochastic optimization. International Conference on Learning Representations (ICLR), 2018.
[10] Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint 1412.6989, 2014.
[11] Tianyi Liu, Zhehui Chen, Enlu Zhou, and Tuo Zhao. Toward deeper understanding of noncon- vex stochastic optimization with momentum using diffusion approximations. arXiv preprint arXiv:1802.05155. 2018.
[12] Siyuan Ma, Raef Bassily, and Mikhail Belkin. The power of interpolation: Understanding the effectiveness of sgd in modern over-parametrized learning. International Conference Machine Learning (ICML), 2018.
[13] Eric Moulines and Francis R Bach. Non-asymptotic analysis of stochastic approximation al- gorithms for machine learning. In Advances Neural Information Processing Systems, pages 451-459, 2.11.
[14] Deanna Needell, Rachel Ward, and Nati Srebro. Stochastic gradient descent, weighted sam- pling, and the randomized kaczmarz algorithm. In Advances in Neural Information Processing Systems, pages 1017-1025, 2014.
[15] Yurii Nesterov. Introductory lectures on convex optimization: basic course, volume 87. Springer Science & Business Media, 2013.

---

Published as a conference paper at ICLR 2020
[16] Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. In search of the real inductive bias: On the role of implicit regularization in deep learning. arXiv preprint arXiv:1412.6614. 2014.
[17] Sashank Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. International Conference on Learning Representations (ICLR), 2018.
[18] Levent Sagun, Utku Evei, Ugur Guney, Yann Dauphin, and Leon Bottou. Empirical analysis of the hessian of over-parametrized neural networks. arXiv preprint arXiv: 2017.
[19] Mark Schmidt and Nicolas Le Roux. Fast convergence of stochastic gradient descent under strong growth condition. arXiv preprint arXiv: 63300, 2013.
[20] Thomas Strohmer and Roman Vershynin. A randomized kaczmarz algorithm with exponential convergence. Journal Fourier Analysis and Applications, 15(2):262, 2009.
[21] Sharan Vaswani, Francis Bach, and Mark Schmidt. Fast and faster convergence of sgd for over-parameterized models and an accelerated perceptron. arXiv preprint arXiv:1810.07288, 2018.
[22] Kun Yuan, Bicheng Ying, and Ali H Sayed. On the influence of momentum acceleration on online learning. The Journal of Machine Learning Research, 7711)6602-6666 2016.
[23] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understand- ing deep learning requires rethinking generalization. International Conference on Learning Representations (ICLR), 2017.
10

---

Published as a conference paper at ICLR 2020
A PSEUDOCODE FOR MASS
Algorithm 1: MaSS Momentum-adeeene added Stochastic Solver
Require: Step-size 7/1 secondary step-size 722, acceleration parameter (0, 1).
Initialize: Un Wy- while not converged do
Wi+1 11, 1/1 (
Ur411 f (1 + W) TW 1/2 (u.).
end while Output: weight w.
Note that the proposed algorithm initializes the variables Wo and Ug with the same vector, which could be randomly generated.
As discussed in section MaSS can be equivalently implemented using the following update rules:
W441 + u, - fu,),
(19a)
Ve41 + - a + au, 8V (u,)
(19b)
a
0++1 I+a 1+a Wr+1-
(19c)
In this case, variables uo. and wo should be initialized with the same vector.
There is bijection between the
(711 7/: 7) and (7, a, 6), which is given by:
1
ad
11 ", 722 1+a 7 I+a'
(20)
B
ADDITIONAL PRELIMINARIES
B.1 STRONG CONVEXITY AND SMOOTHNESS OF FUNCTIONS
Definition (Strong Convexity). finn f Rdd - IR u-stroogly convex (p 0),
if
f(x) 2 f(z) + (Vf(z), 2) [x z|(2, Definition 2 (Smoothness). A differentiable function
11
(21)
RRd R. L-smooth (T. 0), if
f(x) < f(z) + (VI(z), 2) + 2
=|x 211
Vx, S Rd.
(22)
B.2 AUTOMATIC VARIANCE REDUCTION
In the interpolation setting, one can write the square loss as
f(w) = (w - w T "(w=""" = w
(23)
2
key property of interpolation that the variance of the stochastic gradient of decreases to zero as the weight w approaches an optimal solution w'.
Proposition 1 (Automatic Variance Reduction). For the square loss function f in the interpolation setting, the stochastic gradient at an arbitrary point w can be written
(w) H (w
w*) H...c
(24)
Moreover, the variance of the stochastic gradient
Var[Vm/(w)] ||e E H)
(25)
Since E((H,, H is independent of the above proposition unveils linear dependence of variance stochastic gradient on the norm square error e. This observation underlies exponential convergence of SGD in certain convex settings 20
19 14 12).
11

---

Published as a conference paper at ICLR 2020
B.3 ON IGNORING ZERO EIGENVALUES OF THE HESSIAN
Consider the square loss function, f(w) 2n Σ,
[x(x w y:)² The (stochastic) gradient
1
(w) x; (x,
14)
x (w --) = -1,m w"),
where the stochastic gradient is computed based on a randomly sampled batch size m.
Recall that the solution set W {w (') 0} is affine subspace in the parameter space, and that w is the solution in W that closest to w. Hence, w w is perpendicular to W", ie., w - w E (W*)*. Note that (W*)² is an invariant space of Hm. hence mmf(w) = Hm(ww w*) E (W*) Hence the (stochastic) gradient is perpendicular to W
C PROOF OF THEOREM
The key proof technique is to consider the asymptotic behavior of SGD+Nesterov in the decoupled model of data when the condition number becomes large.
Notations and proof setup. Recall that the square loss function based the component decoupled data D, define in Eq 6 is in the interpolation regime, then for SGD+Nesterov, we have the recurrence relation
W4+1 (1 -)(11nH)w. -nnn--
(26)
where i diag((x (x 2)) It is important to note that each component of evolves inde- pendently, due to the fact that H is diagonal.
With w w", we define for each component j = 1,2 that
] j 1,2,
E
(27)
c+1
where ebl is the j-th component of vector
The recurrence relation Eq can be rewritten as
26
b 41
= 1
(28)
with
Bil
(1+ 7
++(1+))(1 + -
-x(1 +)(17)(11 7) - n(iil)ap -7(1
7²(1
(1+ { (1 (1+7)(1 2 1
)
E
-x(1 (((b))99)
0
0
0
(1 (1+7)2A4b1 (1+))(1-0o} (1+7)(11 )0;)
-7(1 7)4b1
-1 الااا
(1 no3))
-7(1 noニ)
0
where Abl = (1 n00)²² + 5(103)2
For the ease of analysis, we define - y (0, 1] and t, := n0?.1 1,2. Without loss of
generality, we assume of = this section. In this case, ti = 17 and to = 7/k, where x is the condition number.
12

---

Published as a conference paper at ICLR 2020
Elementary analysis gives the eigenvalues of Bb]l;
A (1 (1-u)(1- 14)
21/3
Ti
1/3
22 = To 3
+2+ T3 + 4T7
1/3
3/21/3
T2 +
T2 + 47
2//3
T
1/3
A3 = To - (1-33)
+ (1+iv3)
T3 + V T3 + 47
6
T22 TTz 4T7
1/3
6 6./2/3
To+ (1++33) 1/3
Ti
1/3
+ (1-iv3) 21/3
T2 + V T2 + 4773
1/3
(22 + VT3 47
where
u²
7
To = 1- u
t
+ utj 3 nt,,
3
3
3
3
Ti = -(-3 3u - 2 + Tt, 7ut, + 2 6u + 4u² u² 10t, + 20ut, - 13u2t, 13 + ²3)ttt,
T2 = 9u 9u + 2n 72u2t, t, + 144u 141u + 69u 12 + 252t) 756ut"
+1185u213 1110 -
615u 1866 + 24u 6861) 2058ut 2646u22
+1862u 756"*13 + 168u213 16uº19.
Proof idea. For the two-dimensional component decoupled data, we have
E [f(w.)] f(w") 0 [[],, w 12 oB [Ile:19].
(30)
By definition of + in Eq 27 we can see that the convergence rate is lower bounded by the conver- gence rates of the sequences {I] (لح [] By the relation Eq 2 we have that the convergence rate of the sequence {I] [, | is controlled by the magnitude of the top eigenvalue Amaz of B, if 4, has non-
zero component along the eigenvector of with eigenvalue Amaz (B). Specifically, Amazl 1,
[| grows at rate of |mmerl'. I', indicating the divergence of SGD+Nesterov; if [Amazl < 1, then converges a rate of AAmarl".
||
In the following, We use the sigen-systems of matrices Bbl, especially the top eigenvalue, analyze the convergence behavior of SGD+Nesterov with any hyper-paramette setting. We show that, for any choice of hyper-paramen parammaaressers (i.e., step-sine size and momentum parameter), at least one of the following statements must holds:
B(U] has an eigenvalue larger than
B has eigenvalue of magnitude 1 (1/k).
This is formalized in the following two lemmas.
Lemma 1. For any u E (0, 1). if step size
17 (u) 3 2u + 2u + /9 - 84u 164r² + 100 20u
(31)
2(9 15u + 6u2)
then, B has an eigenvalue larger than 1. We will analyze the dependence of the eigenvalues on KG when & large to obtain Lemma 2. For any (0, 1). if step size
" S (u) = 3 2u + 2 /9 84u - 164x² + 100
20
(32)
2(9 - 15u + 6u2)
then, B.al has eigenvalue of magnitude 1 O (1/k).
13

---

Published as a conference paper at ICLR 2020
Finally, show that d has non-zero component along the eigenvector of B with eigenvalue Amaxs hence the convergence of SGI++Nsterov is controlled by the eigenvalue of Bbs with the largest magnitude.
Lemma 3. Assume Nesteret is initialized with wo such that both components (Wo w", ei)
and (wo -w'ee> are non-zero. Then, for all t 2, D.2 has a non-zero component in the eigen direction of Blú that corresponds to the eigenvalue with largest magnitude.
Remark 8. When w is randomly initialized. the conditions Wo--w",e ,i) & 0 and (wo-w" e2) of O are satisfied with probability 1, since complementary cases form lower dimensional manifold which has measure O.
By combining Lemma and 3 we have that SGD+Nesterov either diverges or converges at rate of (1 ((1Kk)), and hence, we conclude the non-acceleration of SGD+Nesterov. In addition, Corollary 1 is special case of Theorem I and is proven by combining Lemma and B
In high level, the proof ideas of Lemma and is analogous those (9), which proves the non-acceleration of stochastic Heavy Ball method over SGD. But the proof idea of Lemma is unique.
Proof of Lemma The characteristic polynomial of By, j = 1, are:
(2(2) =x (1 (1+7)2 (2 + 7)
[ (1 -2 - no3]) -2²,,) X2
- 44
(33)
First note that limx- D2 = +00 > 0. In order to show B3, has eigenvalue larger than 1, it suffices to verity that D (A 1) < 0, because (2 is continuous.
Replacing y by
and no? by tı, we have
(1(1) = 4u²t - 2n 2ut 10u2t + Gu 6t - 16ut + 3882tt) 16u² 18t +48uf - 22 + 12
(34)
Solving for the inequality D1(1) < 0, we have
-3 - 2u 2n + v9 + 84u 164u² + 100 - 20
n= 4
2(9 15u + 6u²)
for positive step size 7)-
Proof of Lemma the condition in Eq 32
We will show that at least one of the eigenvalues of B is 1 - 0(1kk), under
First, we note that l2 4/xx 1/KK, which is 0(1ks). We consider the following cases separately: 1) u is O(12.)) 2) u o((255 and w(1);; 3) u is O(12): 4) u is w(1..5) and o(1); and 5) u is O(1), the last of which includes the where momentum parameter is constant.
Note that, for cases 1-4, u is o(1). In such cases, the step size condition Eq 32 can be written as
2 n < 3 o(u).
(35)
It is interesting to note that must be o(1) to not diverge, when u is o(1). This is very different to SGD where a constant step size can result in convergence, see (12).
Case 1: u is O(1.5)). In this case, the terms u u uA12, 22t and 1o are of the same order.
We find that
To 1-
Ti = -3w" + 1212 + 0(13/2
T2 9n 72u21 2521 0(15/2)
14

---

Published as a conference paper at ICLR 2020
Hence,
A = 1 11 - 12 + ul2
2
12f-- 3u²
1
Ag
+
- u2) + +0122)
3 (108 412 u2)
3 3-21/3
A = 1- uu + (1 -1- iv3)
2//3
1262 - 3u²
+ (1 + iv3)
1
(108 - - O(t))
6
(108(412 (412 32)3)116
6 5//1/3
1/3
12t₂ 3u
1
4 1-u iv3
(108 - 42)3)//6 (1 (1-iv3)
(108 -
6 21/3
Write 1/ cu2 asymptotically for some constant If 412 2 u² i.e.
i.e. 4c 2 then
A 1 - + 0(22),
A 1 - V
(tt)).
V3
4c
A --1--u u
Ott2).
v3
If 4tg S u22 i.c, 4c- 1 15 0, then
A + O(12),
A + VI
4c
+ ((2),
V3
vI
4c
4 1 u
u + (t2).
v3
In either case, the first-order term is of order u.
Recall that f22 = n/K, then we have
2cu cu
22 = ct2 = cT//K <
(36)
3k
hence, < <</n== Therefore, A₁, 1,2, 4 are 1 0(1m)).
Case 2: is o(t2-)) and (t2). In this case,
To = 1- 1-u- 7t2/3 3 + o(t2):
--733/
Ti = -121 0122)
T2 -252th 72u + o(t2)
Hence,
A1 = 1 - u - t2 + ut2.
A2 1 - + +(t2),
Ag = 1 - u + 2i + O(t)),
A = 1 1- u 22 +0tz)
= Ottg/K), we have th-a O(1/k), hence i2 o(1 / k²2 This implies that 16.5 o(1 /x) and u o(1/k)). Therefore, all the eigenvalues A; are of order O(1kk).
Assume u t2. When E (0.5, 1). note that t2 n/K <
2u
3x
Case 3: is Ol2)). This case if forbidden by the assumption of this lemma. This is because, 12 22=1// 11// < 3x d(u) (1/1 K is o(1)). This contradictory to (112).
Case 4: u is ((1255) and o(1). this case, we first consider the terms independent t2. i.c. constant term and w-only terms. These terms can be obtained by putting the eigenvalues are simplified as:
0. In such setting,
A X u, d2lez=0 1, Aalez=o 1 2n u² >aleg=o 1
(37)
15

---

Published as a conference paper at ICLR 2020
Note that the u--nly terms cancel in X2, the first order after the constant term must be of t2 (could be tz/u², t2/ etc.). In the following we are going to analyze the t2 terms.
Since is ((tt2.), u² has lower order than t2, and tz/u² is o(1). This allows us to do Taylor expansion:
-3u
- u
12 [() higher order terms,
1/2 + g + higher order terms,
T2 = (1 - ui
where f(u) and g(u) are u-terms only, which, by the above analysis in 3q 37 are shown con- tribute nothing to X2- Hence, we use the first terms of Ti and 72 above to analyze the first order term of X2. Plugging in these term to the expression of X2, and keeping the lowest order of l2, we find a zero coefficient of the lowest order 12-term: l2/u².
Hence, 2 can be written as:
A = c- +0(2),,
(38)
where c is the coefficient.
On the other hand, by Eq 35 and t2 = n/K, we have
12 = 0(1k))
(39)
u
Therefore, we can write Eq = 1 =
Case 5: u is O(1). This is the case where the momentum parameter r-independent. Using the same argument as in case 4, we have zero u-only terms. Then, directly taking Taylor expansion with respect 1/ results in:
A 11-00(()=-000
=
(40)
Proof of Lemma This proof follows the idea of the proof for stochastic Heavy Ball method in ( The idea is examine the subspace spanned by +b11 eigenvector of Bli corresponding to top eigenvalue (i.e., eigenvalue with largest magnitude) is not orthogonal to this spanned subspace. This in turn implies that there exists non-zero component of
2. j 1,2, and to prove that the
( the eigen direction of Blu corresponding top eigenvalue, and this decays/grows at of Xma (BL)).
Recall that $11 Bl Hence, 3155) has non-zero component in the eigen direction of Bbi with top eigenvalue, then ab(ب) should also have non-zero component in the same direction. Thus, it suffices to show that at least one of Tb/ T15 T and T has non-zero component in the eigen
direction with top eigenvalue.
Since и is diagonal for this woo-dimensional decoupled data, w and w evolves independently, and we can analyze each component separately. In addition, it can be seen that each of the initial
values w0s1 (w"),l, which is non-zero by the assumption of this lemma, just acts as scale factor
during the training. Hence, without loss of generality, we can assume w (w*)Gi 1, for each j. Then, according to the recurrence relation of SGD+Nesterov in Eq 26
(1)
1
[i] ) I
[
-
(1 + 7)
s/ 7
s/1
[il
[
(1 7) ا
[
x(1 +11+10 7)) - 783
(1 7) [ -782
) (41)
(1 ) U1 1
[
62
782
where s6 = n(at61)2 1,2,3,
16

---

Published as a conference paper at ICLR 2020
Denote the vectorized form of @b22 vec( which is 4 1 column vector. We stack the vectorized forms of T Tb0 Tbl Thl to make a 4 x matrix, denoted as Mbl;
M = [vec( vec( vec( rec(og))
(42)
Note that @b 0, 2,3, are symmetric tensors, which implies that Mb contains two identical rows. Specifically, the second and third row of Mb1 are identical. Therefore, the vector v (0,-1/v2, 1)" is an eigenvector of M with eigenvalue 0. In fact, v is also an eigenvector of gbl with eigenvalue 7(1 noj)). Note that
det(Bbu) 7 n0 ((L not)² + 5(nof))) 2 A [oj="
Hence, v is not the eigenvector along top eigenvalue, and therefore, is orthogonal to the eigen space with top eigenvalue.
In order to prove at least one of 2 t = 0, 3, has a non-zero component along the eigen direction of top eigenvalue, it suffices to verify that Mil is rank 3, i.e., spans three-dimensionall space. Equivalently, we consider the following matrix
M' == E
60.16-1,1
60,161,1
61,162,1
(43)
E11
2
2
where we omitted the superscript [j] for simplicity of the expression. the determinant of M not zero, then it full rank, and hence Mbb1 spans a three-dimensional space.
Plug in the expressions in 41 then we have
(e (1 =) (361) - 18ut3 + Gul,; + 31, 3u + 1),
(44)
2
if and only if the polynomial 3613 18uf3 + Gut, + 3t, 3u + = 0. Solving for this equation, we have
where n107 and 7. det(
t -1 2u + v(1 2n) 8(3 u)(u 2)
(45)
12(2 - u)
We note that, for all u [0, 1) both i, are not positive. This means that, for all and positive ły. the determinant (eM'l can never be zero.
Therefore, for each j = 1, 2, M cludes the eigenvector with the top eigenvalue of Bbl, Hence, at least one of db["], t {0, 2,3 has non-zero component in the eigen direction with top eigenvalue. By $.51 وااا 51 all succeeding
bil is full rank, and M spans a three-dimensional space, which in-
g also have non-zero component in the eigen direction with top eigenvalue of Bb}
Proof of Theorem 7 Lemma and show that, for any hyper-parameter setting (17, 7) with 17 > 0 and E (0, 1), either top eigenvalue of [3(]] is larger than or top eigenvalue of [ is 1 0(1nk). Hence, [Amarl is either greater than or is 1- ((1k). Lemma 3 shows that +, has non-zero component along the eigenvector of B with eigenvalue (B).
By Eq Eq 28 and Lemma [ and 2 the sequence []] either diverges or converges rate of (1 OTT/xO x) By definition of & in Eq 27 we have that {[eei]]e either diverges or converges at rate (1 (l
Note that, for the two-dimensional component decoupled data, we have
E [f(w))] - f(w") 3E [|], - w = oB [[].
(46)
Therefore, the convergence rate of SGD+Nesterov is lower bounded by (1 ((1k))))) Note that the convergence rate of SGD on this data is (1 - 0(1x))),, hence SGD+Nesterov does not accelerate SGD on the two-dimensional component decoupled dataset.
17

---

Published as a conference paper at ICLR 2020
L and 7 [0.6, 1), the condition in Eq 31 is satisfied. By Lemma I the top eigenvalue Xmaz of B 4) is larger than By Lemma
Proof of Corollary 7
When 7
3 @1l has non-zero compo-
nent along the eigenvector with this top eigenvalue X!ll Hence, ((w: w", (X
w", eiil grows at rate of
D PROOF OF THEOREM 2
We first give lemma that is useful for dealing with the mini-batch scenario: Lemma 4. If square loss f is in the interpolated setting, i.e., there exists w such that f(w") 0,
then H[ Hm] H m
(R 1) H.
Proof.
E|Hm H
Hml
Σ
m
X2
x,x, T
Σ ig.
x
TH
"x,,,"
7
1 R.H
1
+ m
H.
m²
172
m
Proof of Theorem 2
By Eq
we have
||
w 1
[[L a + au, w 1 + +82 H (:mmu: w
1
w (1- a)ve + au; - w")
Using the convexity of the norm || -ll and the fact that is the smallest non-zero eigenvalue of the Hessian, we get
B[Å] S
(1-a))lvv:
w' + allu, w' S (1-a))lvv - w + a |lu w w=
Applying Lemma on the term B, we have
B < 52m uu w'll.
(47)
Note that E HmHm]= H, then
B[Ć] =
-5 w", (1 - a) + au, w*)
225(ur w", w - a (u: -w:))
1 - a j (I] w011 -llu: 1 [/2-|[we - -u,l??)
= -20llu: w' 1 +
1 8 un w/112
< 8 Wt w 11
(48)
a
Therefore,
E - 11
S (1-a)llve-w wx
1 -
o||w: wor-ww1p w' 1
-| (a
1 +
1+0))
8)
Iu w" w*1 Rm |u- -u-ww"i w
-
a
On the other hand, by the fact that E
H (see (12)
m7
m
B[[[w -w' E
| w- n (U: w|
w 1
27llue -ou--w"l li + n2 Tim U w
(49)
18

---

Published as a conference paper at ICLR 2020
Hence,
E | - w'l + - W w-1lp]
1 a 6|[W: w 1/- + (a/u- 8) lu - w"1l
< (1 a)llve w
+ R8 81²² Lm/a 210/a)
|| ||
By the condition in Eq
10, 61 00,0 O. then the last two terms are non-positive. Hence,
E
| - x² x0 H-1
[| w-1p] $ (1 -1-oh a) (Ive - w w + | w=1
I (1-a) (Ivo -0'--wl' |wo w w(1²))
E PROOF OF THEOREM 4
Proof. The update rule for variable is, in Eq
Ve+1 avv. + au, oVmf(u,).
(50)
By 1/ convexity of g. we have
g(vi+1) $ ((1-a)vv - au,) + (Vg + aau),, -ov mf.m)(u + 02 - V fw;)ll
2p
(51)
Taking expectation on both sides, we get
B[g(ve+1)] = g - a)
+ au)) + (Vg ((1-0(1))))) a)v, + -oV()-))((u.)) + 82 Eill | m (u:)))
2/
+ 8(1 () a)v, + au - w") + 82 2Lm
f(u)),
24
where in the last inequality we used the convexity of g and the assumption in the Theorem.
By Eq 48
-5(1 -((1-0)(1 w', (--w")= 5(1 c) (1
|w: w²112_ 1 + Ill w 112
By the strong convexity of g.
ag(u,) 1 a anl - w w11
2p
Hence,
8(1 c)
w|,, w w1
a
8(1 + a)(1-c) )
||u - w 21 km f(ue).
-w--w">
2a
24
2a
(52)
On the other hand,
B Billwe+1- w0113] |
w - 27/(ur
- -w", vf(u:)) + fmu
< Iu - 2 - 2nf(u:) + n7² fu,))
(53)
where in the last inequality we used the convexity of f.
19

---

Published as a conference paper at ICLR 2020
Multiply factor of ((1-)) onto Eq
53 53
and add it to 52 then
E
g(v++1) + 5(1
Wi+1 W w¹1]]
s
(1 a)g(v))++++ + + (11-a) -c) ()
w. w¹11
2a
2a
a
-8(1 -8(1-))
111e w-12
#
8
(1 ()) Tum 11) 82 8mmm s(ve). (54)
+
a
If the hyper-paramen paremeearseeerrs selected as:
6
1
7 2
a
(55)
2km
2Lm
then the last two terms in Eq 54 are non-positive. Hence,
5(1 c)
s (1- a)B g(v.) + 5(1
E g(ve+1)+ +
Wi+1
-
Wt w' w²13
(56)
2a
2a
which implies
g(v:)) + 8(1 - c)
I|,, - w w'113 S 5
1- g(vo) +
8(1-c)
wo - w']l]
(57)
2a
2km
2a
Since S(w.) S L/2 11/2-//w:-- w 11 (by smoothness), then we have the final conclusion
Bis(w(] C. C1 (1- 1--1-- 1- (1-1-9)-
(58)
2
with C. being a constant.
F EVALUATION ON SYNTHETIC DATA
F.1 DISCUSSION ON SYNTHETIC DATASETS
Component Decoupled Data. The data is defined as follows (also defined in section 3
Fix an arbitrary w' E R²² and let z be randomly drawn from the zero-mean Gaussian distribution
with variance E[2?] 2, i.e. 2 NO. 2). The data points (x, y) constructed follow:
x
01 2 e
02 e2 w.p. 0.5,
w.p.
and y (w",,)) x),
(59)
where e1, ey E 2 are canonical basis vectors, 01 > 02 >
Note that the corresponding square loss function on D is in the interpolation regime, since f(w*) The Hessian and stochastic Hessian matrices turn out to be
0
(1) 0
H
H
(60)
(arl2))
Note that H is diagonal, which implies that stochastic gradient based algorithms applied on this data evolve independently in each coordinate. This allows a simplified directional analysis of the algorithms applied.
Here we list some useful results for our analysis. The fourth-moment of Gaussian variable E[=^] 3|E[=1]² 12. Hence, bi) of and [x bi) )*] 60z, where superscript 2, is the index for coordinates in R22 It is easy to check that Go? /oz and ñ 6.
20

---

Published as a conference paper at ICLR 2020
50D SID banntarryy
SCD+ileavy Ball ASCD Mads
-10
Mo55
2200
4003
1933
9903
10000
2000
4033
9933
8303
10500
Figure 6: Fast convergence of MaSS and non-acceleration of SGD+Nesterov on component decou- pled data. (left) of and 2 1/2'2; (right) of and o 1/2
-10
500
1000
1500
2000
2000
2000
2000
4000
500
1000
1000
2000
2000
2000
2000
4000
Figure 7: Fast convergence of MaSS and non-acceleration of SGD+Nesterov on 3-d Gaussian data. (left) of 1 and o3 1/20; (right) of and of 1//222
Gaussian Data. Suppose the data feature vectors {x,} zero-mean Gaussian distributed, and (w" xs), Vi, where w is fixed but unknown. Then, by the fact that E[2] E[z1 22
[[a]=2]B[[232 [[[zz E[2 [z]]Z] [| for zero-mean Gaussian random variables
22, and 24, we have
BIAH (2H + (r(()))H))))))) H, E E
EE[x* H - 1xx*
d)H,
where d is the dimension of the feature vectors. Hence L1 = 22maz (1) + tr(H) and R = 2 + d, and K. = Lipp. This implics a convergence rate of O(e-t/v ////tt//22/0 /(2+)))) of MaSS when batch size is 1. Particularly, if the feature vectors are n-dimensional, e.g., as in kernel learning, then MaSS with mini batches of size has convergence rate of (e Of////nn
F.2 EVALUATION OF FAST CONVERGENCE OF MASS AND NON-ACCELERATION OF SGD+NESTEROV
In this subsection, show additional empirical verification for the fast convergence of MaSS, as well as the non-acceleration SGD+Nesterov, on synthetic data. In addition, we show the divergence of SGD+Nesterov when using the same step size SGD and MaSS, indicated by Corollary [
We consider two families of synthetic datasets:
Component decoupled: (as defined in Section 3 Fix an arbitrary w E R² with all com- ponents non-zero. x; is drawn from (0, diag 0)) (O diag(0, 2a²)) with prob- ability 0.5 each. yi (w",
(w',xx, xx) for all i.
3-d Gaussian: Fix an arbitrary w E IR3 with all components non-zero. x, are indepen- dently drawn from (0, diag(o? of, aā)), and y (w", xx) for all i.
Non-acceleration of SGD+Nesterov and accelerated convergence of MaSS. with SGD and SGD+ Nesterov linear regression with the above datasets.
We compare MaSS Each comparison is
21

---

Published as a conference paper at ICLR 2020
140
Nesterov: 0.9
SGD
200
200
500
3530
1992
2008
2305
Iterations
Figure 8: Divergence of SGD+Nesterov with large step size. Step size: v7" = 1/h1 = 1/6, and
momentum parameter: 0.9 0.99.
performed on either 3-d Gaussian or component decoupled data with fixed σ and 02. For each setting of (01,02), we randomly select w", and generate 2000 samples for the dataset. Batch sizes for all algorithms are set be We report the performances of SGD, SGD+Nesterov and SGD+HB using their best parammprreeetr setting selected from dense grid search. On the other hand, we do tune hyper-parameters of MaSS, but use the suggested setting by our theoretical analysis, Eq 14 Specifically, we use
5
6 02
Component decoupled:
1/2
7
(61a)
+
60z
+ 022
1
20
20 02
3-d Gaussian:
vi 4
12
72t
(61b)
20
+
200 +
For ASGD, we use the setting suggested by (8)
Figure [6 (in addition Fig and Figure show the curves of the compared algorithms under various data settings. We observe that: 1) SGD+Nesterov with its best peper-parrmmttrs is almost identical to the optimal SGD; MaSS, with the suggested
selections, converges faster than all of the other algorithms, especially SGD. These observations are consistent with our theoretical results about non-acceleration of SGD+Nesterov, Theorem I and accelerated conver- gence of MaSS, Theorem 3
Recall that MaSS differs from SGD+Nesterov by only a compensation term, this experiment illus- trates the importance of this term. Note that the vertical axis is log scaled. Then the linear decrease of log losses the plots implies an exponential loss decrease, and the slopes correspond to the coefficients in the exponents.
Divergence of SGD+Nesterov with large step size. As discussed in Corollary T SGD+Nesterov diverges with step size 17" 1/L, (when 7 [0.6, 1)), which is the optimal choice of step size for both SGD and MaSS. We run SGD+Nesterov, with step size 17" = 1/L,, to optimize the square loss function on component decoupled data mentioned above. Figure shows the divergence of SGD+Nesterov with two common choices of momentum parameter 7y: 0.9 and 0.99.
F.3 COMPARISON OF VASWANI'S METHOD 21 GAUSSIAN-DISTRIBUNN DATA
WITH SGD AND MASS ON
The analysis in Vaswani et. al. (21) is based on the strong growth condition (SGC), Assuming SGC with the parameter P on the loss function they prove convergence rate (1 (1- 11//2k) of their method (called SGD with Nesterov acceleration in their paper), where / the iteration number. In the following, show that, on simple (zero-mean) Gaussian distributed data, this rate is slower than that of SGD, which has a rate of (1 1/x)*. On the other hand, MaSS achieves the accelerated
rate (1 (2 d)k
22

---

Published as a conference paper at ICLR 2020
Consider the problem of minimizing the squared loss, f(w) Fi(i Ew(w"x, over zero-mean Gaussian distributed dataset, as defined in F.1 Then,
B [ (w w E,,
X x (w-w") ww"
= (w- + (r( w"),
(62)
whereas,
|V/(w)]] (w (w- -w-). w")
(63)
According to the definition of SGC,
E,
(64)
Hence the SGC parameter p must satisfy
tr(H)
p 2+
> Kr
(65)
Amin (H)
where x is the condition number.
In this case, the convergence rate (1 (1-V1/p2k of Vaswani's method would be slower than
(1 11=1/=²/3) which is slower than SGD.
On the other hand, MaSS accelerates over SGD on this dataset. Recall from Section E. that, for this Gaussian data, & 2 d, where d is the dimension of the the data. According to Theorem the
convergence rate of MaSS is (1 1/v(2+))x) which is faster than that of SGD.
G MINI-BATCH DEPENDENCE OF CONVERGENCE SPEED AND OPTIMAL HYPER-PARAMETERS
G.1 ANALYSIS
The two critical points are defined as follow:
m = min(L1/LL L, R), m. max(L1/L,8)
When < mi. we have L, /L and R, which implies Lm LI/m, Km Ki k1/m and Rm 2 R/m. Plugging into Eq 13 we find that the optimal selection of hyper- parameters is approximated by:
n" (m) se -7 (1), (m) xe a (1),0"(m) se 81),,,
and the convergence rate Eq 16 is approximately O(e 0 the latter of which indicates linear gains in convergence when increases.
Now consider the following two cases: (i) For m 2 L1/ L, we have Km < 2x following the definition of T.m. in E (ii) For > R. Rm k/m + (m 1)/m S 2. When either case holds m 2 mi, the convergence rate (6 becomes
o( maxx
42 1)
indicating that increasing the mini-batch size results in sublinear gain the convergence speed, of at most vm. Moreover, in the saturation regime m >> my (i.c., when both conditions (i) and (ii) hold), the convergence rate is then upper-bounded by ((xxp(=2$2) of MaSS with mini-batch size m is equivalent up to a multiplicative factor of 2 to an iteration with full gradient.
That implies that single iteration
23

---

Published as a conference paper at ICLR 2020
G.2 EMPIRICAL VERIFICATION
We empirically verify the three-regime partition observed in section 5 using zero-mean Gaussian data.
In this evaluation, we set the covariant matrix of the (zero-mean) Gaussian to be:
Σ
diog( 1,
2
2
(66)
40
and generate 2000 samples following the Gaussian distribution NO,, E). Recall from Example
that, for zero-mean Gaussian data, I 2Amaz ( +r)++((FF)) and i = 2+-d. In this case, Tn/L I. R2. 10 and R Rs 50. The two critical values mi, m² of mini-batch size are then:
mi = 10,
m = 50.
In the experiments, we run MaSS with a variaty of mini-batch size m, ranging from 1 to 160,
Convergence speed vs. mini-batch size
on this Gaussian dataset. For each training pro- cess, we compute the convergence speed sm)) which is defined to be the inverse of the number of iterations needed achieve a training error of e. Running 1 iteration of MaSS with mini- batch size y is almost as effective as running s(m)/st iterations of MaSS with mini-batch of size 1.
Bapess sraurt
15
Saturation
Dimirishing Returns
Emriircall results
Theoretical lower bound
Figure 9 demonstrates the convergence speed s(m) as a function the mini-batch size m. We see that the three regimes defined by mi and m. coincide with the analysis in subsec-
Figure 9: Convergence speed per iteration as a function of mini-batch size m. Red solid curve:
experimental results. Larger a(m) indicates faster convergence. Blue dash curve: theoretical lower bound VKm.m. Critical mini-batch size values: mi 10, m4 s2 50.
tion 5 left (m < mī), almost linear, middle (m E [mi, mt)) sublinear; right (m > mz), saturation.
H EXPERIMENTAL SETUP
H.1 NEURAL NETWORK ARCHITECTURES
Fully-connected Network. The fully-connected neural network has hidden layers, with 100 ReLU-activated neurons in each layer. After each hidden layer, there is dropout layer with keep probability 0.5. This network takes 784-dimensional vectors as input, and has 10 softmax-activated output neurons. has <999 trainable parameters in total.
Convolutional Neural Network (CNN). The CNN we considered has three convolutional layers with kernel size of 5 5 and without padding. The first two convolutional layers have 64 channels each, while the last one has 128 channels. Each convolutional layer is followed by 2 x 2 max pooling layer with stride of On top of the last max pooling layer, there is fully- ReL.--actvvteed layer of size 128 followed by the output layer of size 10 with softmax non-lineane oineeiirar dropout layer with keep probability 0.5 applied after the full-connected layer. The CNN has 5766 trainable parameters in total.
Residual Network (ResNet). We train a ResNet ( with 32 convolutional layers. The ResNet-32
has sequence of 15 residual blocks: the first 5 blocks have output of shape 32 x 32 16, the following blocks have an output of shape 16 x 32 and the last blocks have an output of shape 8 x 8 x 64. On top of these blocks, there is 2 x average pooling layer with stride of 2, followed by a output layer of size 10 with softmax nin-linearit.. The ResNet-32 32 has 4x467k trainable parameters in total.
We use the fully-connected network to classify the MNIST dataset, and use CNN and ResNet to classify the CIFAR-10 10 dataset.
24

---

Published as a conference paper at ICLR 2020
H.2 EXPERIMENTAL SETUP FOR TEST PERFORMANCE OF MASS
The 3-layer CNN we use for this experiment is slightly different from the aforementioned one. We insert a batch normalization (BN) layer after each convolution computation, and remove the dropout layer in the fully-connected phase.
Reduction of Learning Rate. On both CNN and ResNet-32, we initialize the learning rate of SGD, SGD+Nesterov and Mass using the same value, while that of Adam is set to 0.001, which is common default setting. CNN, the learning rates all algorithms drop by 0.1 at 60 and 120 epochs, and train for total 150 epochs. On ResNet-32, the learning rates drop by 0.1 at 150 and 225 epochs, and we train for total 300 epochs.
Whenever the learning rate of MaSS reduced, restart the MaSS with the latest learned weights. The reason for restarting is to avoid the mismatch between the large momentum term and small gradient descent update after the reduction of learning rate.
Data Augmentation. We augment the Cifar-10 training data by enabling random horizontal flip, random horizontal shift and random vertical shift of the images. For the random shift of images, we allow a shift range of 10% of the image width or height.
Selection for MaSS. Since the reduction of learning rate may affect the sug- gested value of (c.f. 13 consider (1), a, Rm) independent hyper-parameteer parameters instead, where &m = n7/ (ao). Observing the fact that Rm S Km, we select Rm in the range (1, 1/a).. In our experiments,
set 0.05, corresponding to the "momentum parameter" being 0.90, which is commonly used in Nesterov's ' method. We find that good choices of R. often locate in the interval [2, 25) for mini-batch size 64 in our experiments.
The classification results of MaSS Table 6 are obtained under the following paramer settings:
CNN:
" 0.01 (initial), 0.05, 7m 3;
7) = 0.3 (initial), a = 0.05, Rm = 6.
ResNet-32:
= 0.1 (initial), a 0.05, Rm = 2:
7) 0.3 (initial), a 0.05, Km 24.
25


Reviews:
[{"review_id": "rJly18kqKr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper shows the non-acceleration of Nesterov SGD theoretically with a component decoupled model. Moreover, the authors introduce an additional compensation term and derive a novel optimization method, MaSS. MaSS is both theoretically and empirically proved to outperform Nesterov SGD as well as SGD.\n\nPros\n1. It's amazing to see the great improvement introduced by the compensation term into the theoretical result of MaSS. Moreover, the authors generalize the setting of square loss function to other convex loss functions.\n2. The encouraging result in Table 1 in EMPIRICAL EVALUATION shows the consistent outperformance of MaSS over SGD and Nesterov SGD regardless of the changing learning rates.\n\nCons\n1. The discussion on why the zero eignvalue can be ignored in Section 4 is insufficient. \"(stochastic) gradients are always perpendicular to W^*\" seems not that obvious.\n2. The empirical result merely involves two settings of learning rate: 0.01, 0.3. I suggest a wider range of learning rates to show the outperformance of MaSS.\n\nSome typos\nLast line of the first paragraph in INTRODUCTION: there is a redundant \"can\". 7th line of the 5th paragraph in INTRODUCTION: there is a reduntant \"the\" after \"In this case\".\n    ", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper."}, "extra_text": {}}, {"review_id": "r1gR1zv3KB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors present a new first order optimization method that adds a corrective term to Nesterov SGD. They demonstrate that this adjustment is necessary and sufficient to benefit from the faster convergence of Nesterov gradient descent in the stochastic case. In the full-batch (non deterministic) setting, their algorithm boils down to the classical formulation of Nesterov GD. Their approach is justified by a well conducted theoretical analysis and some empirical work on toy datasets. \n\nPositive points:\n- The approach is elegant and thoroughly justified. The convergence to Nesterov GD when the batch size increase is comforting.\n- The empirical evaluation, even if it is still preliminary and larger scale experiments will have to be conducted before the method could be widely adopted, are suitable and convincing.\n- Some interesting observations regarding the convergence regimes (in respect to the batch size) are made. It would have been interesting to see how the results from fig3 generalize to the non convex problems considered in the paper.\n\nPossible improvements:\n- In H2, it is mentioned that the algorithm is restarted (the momentum is reset) when the learning rate is annealed. Was this also done for SGD+nesterov? Also, I think it is an important implementation detail that should be mentioned outside of the appendix\n- Adam didn’t get the same hyper-parameter tuning as MaSS did. It is a bit disappointing, as I think the superior performance (in generalization) of non-adaptive methods would still hold and the experiment would have been more convincing. Rate of convergence is also not reported for Adam in fig 5.\n\nI think this is definitely a good paper that should be accepted. I’m looking forward to see how it performs on non-toy models and if the community adopt it.\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "SkgtBCT1YH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "1) In the statement of theorem 1, what do you mean by “with probability one” and “convergence in expectation” together? The inequality (7) does not have any random variable anymore after taking the expectation. Need to explain more clearly this part. \n\n2) Basically, all the results of this paper is based on the (or close to) strongly convex property. However, numerical experiments show for some non-convex functions, specifically for deep learning problems. It is unclear what kind of loss function the author(s) are using for training classification problems on MNIST and CIFAR-10. This could be softmax cross-entropy but not quadratic. \n\n3) The theoretical results in this paper are not strong. The interpolation setting could make all solutions of the component function are the solution of the total loss function. In this situation, we know that stochastic algorithms could take advantage because of “automatic variance reduction”. \n\n4) The result in this paper is quite incremental from the one in Vaswani et al 2019, “Fast and Faster Convergence of SGD for Over-Parameterized Models (and an Accelerated Perceptron)”. More discussion is needed if the author(s) think that it has significantly improvement. \n\n5) It is true that Nesterov SGD is very efficient for training neural networks and MaSS may have some effect in practice. However, theoretical part needs to be improve. I would suggest to analyze for nonconvex problems or using the assumptions which are verifiable and reasonable for neural network. \n\nThe work may be potential, but in order to convince people to trust this algorithm, rigorous theory must be provided. Some experiments in the paper are not representing all scenarios that MaSS may not work. \n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors provide an empirical and theoretical exploration of Nesterov momentum, particularly in the over-parametrized settings. Nesterov momentum has attracted great interest at various times in deep learning, but its properties and practical utility are not well understood. This paper makes an important step towards shedding some light on this approach for training models with a large number of parameters. 
Decision: Accept (Poster)