Towards understanding how momentum improves generalization in deep learning
Authors: Samy Jelassi
Yuanzhi Li
Venue: ICLR 2022 Submitted (2022)
Keywords: Deep learning theory
non-convex optimization

Abstract: Stochastic gradient descent (SGD) with momentum is widely used for training modern deep learning architectures. While it is well understood that using momentum can lead to faster convergence rate in various settings, it has also been observed that momentum yields higher generalization. Prior work argue that momentum stabilizes the SGD noise during training and this leads to higher generalization. In this paper, we take the opposite view to this result and first empirically show that gradient descent with momentum (GD+M) significantly improves generalization comparing to gradient descent (GD) in many deep learning tasks. From this observation, we formally study how momentum improves generalization in deep learning. We devise a binary classification setting where a two-layer (over-parameterized) convolutional neural network trained with GD+M provably generalizes better than the same network trained with vanilla GD, when both algorithms start from the same random initialization. The key insight in our analysis is that momentum is beneficial in datasets where the examples share some features but differ in their margin. Contrary to the GD model that memorizes the small margin data, GD+M can still learn the features in these data thanks to its historical gradients. We also empirically verify this learning process of momentum in real-world settings.

Under review as a conference paper at ICLR 2022
TOWARDS UNDERSTANDING HOW MOMENTUM IM- PROVES GENERALIZATION IN DEEP LEARNING
Anonymous authors
Paper under double-blind review
ABSTRACT
Stochastic gradient descent (SGD) with momentum is widely used for training modern deep learning architectures. While it ís well understood that using momen- tum can lead to faster convergence rate in various settings, has also been observed that momentum yields higher generalization. Prior work argue that momentum stabilizes the SGD noise during training and this leads to higher generalization. In this paper, we take the opposite view to this result and first empirically show that gradient descent with momentum (GD+M) significantly improves generalization comparing to gradient descent (GD) in many deep learning tasks. From this obser- vation, we formally study how momentum improves generalization in deep learning. We devise a binary classification setting where two-layer (over-pane parammertattt) convolutional neural network trained with GD+M provably generalizes better than the same network trained with vanilla GD, when both algorithms start from the same random initialization. The key insight in our analysis is that momentum is beneficial in datasets where the examples share some features but differ in their margin. Contrary to the GD model that memorizes the small margin data, GD+M can still learn the features these data thanks to its historical gradients. We also empirically verify this learning process of momentum in real-world settings.
INTRODUCTION
It is commonly accepted that adding momentum to an optimization algorithm is required to optimally train a large-scale deep network. Most of the modern architectures maintain during the training process a heavy momentum close to 1 (Krizhevsky et al., 2012; Simonyan & Zisserman, 2014; He al., 2016; Zagoruyko & Komodakis, 2016). Indeed, it has been empirically observed that architectures trained with momentum outperform those which are trained without (Sutskever et al., 2013). Several papers have attempted to explain this phenomenon. From the optimization perspective, Defazio (2020) assert that momentum yields faster convergence of the training loss since, at the early stages, it cancels out the noise from the stochastic gradients. On the other hand, Leclere & Madry (2020) empirically observes that momentum yields faster training convergence only when the learning rate small. While these works shed light on how momentum acts on neural network training, they fail capture the generalization improvement induced by momentum (Sutskever et al., 2013). Besides, the noise reduction property of momentum advocated by Defazio (2020) seems to even contradict the observation that, in deep learning, having a large noise in the training improves generalization (Li et al., 2019; HaoChen et al., 2020). To the best of our knowledge, there is no existing work which theoretically explains how momentum improves generalization in deep learning. Therefore, this paper aims to close this gap and addresses the following question:
Is the higher generalization induced by momentum tied the stochastic noise of the gradient? If not, what is the underlying mechanism of momentum improving generalization in deep learning?
In this paper, we empirically verify that the generalization improvement induced by momentum is not tied to the stochasticity of the gradient. Indeed, as reported Figure I, momentum improves generalization more significantly for full batch GD than for SGD in CIFAR object recognition tasks. Motivated by this empirical observation and the fact that the stochastic noise influences generalization, theoretically study how gradient descent with momentum (GD+M) can generalize better than vanilla gradient descent (GD). We therefore only focus on the contribution of momentum of the true gradient generalization.
The question we address concerns algorithmic regularization which characterizes the generalization of an optimization algorithm when multiple global solutions exist in over-parameterizze deep learning

---

Under review as a conference paper at ICLR 2022
CIFAR-I0
CIFAR- 100
CIFAR-II 10
CIFAR- 100
Test
Ratio
Test
Ratio
Test
Ratio
Test
Ratio
R18 WR16
75.83/84.68
1.11
43.32//51.99
1.20
RI8
86. 1685511
0.99
53,81758.01
L.08
75.02/84.48
1.12
42.95/51.33
1.20
WRI6
84.83/87.85
1.04
55.09/60.83
1.10
(a)
(b)
SGD (0.00)
2.0
SCD+M (0.00)
CD (0.00)
Training Loes
1.5
GD (0.01)
Test Accuracy
60
1.0
40
SGD (86.13)
0.5
SCD +M (85.91)
20
GD (75.83)
0.0
GD+M (84.68)
50
100
150
200
250
300
50
100
150
200
250
300
Number of epochs
Number of epochs
(c)
(d)
Figure 1: Test accuracy obtained with Resnet-18 18 (R18) and WideResnet16 (WR16) 16) on CIFAR-10 and CIFAR- 100. The architectures trained using GD/GD+M (a) and SGD/ SGD+M (b) for 300 epochs to ensure zero training error. (c)-(d) respectively display the training loss and test accuracy by R18 with GDIGD+M on CIFAR-10. To isolate the effect of momentum, we turn off data augmentation, dropout and batch normalization. GD and SGD respectively refer to stochastic gradient descent with batch sizes 50% (full batch) and 128. We grid scarched the best (scheduled) learning rate and weight decay for each individual algorithm separately. Results are averaged over runs and we only report the mean (sec Appendix for complete table).
model Soudry et al. (2018); Lyu & Li (2019); Ji & Telgarsky (2019); Chizat & Bach (2020); Gunasekar et al. (2018); Arora et al. (2019). This regularization arises in deep learning mainly due to the non- convexity of the objective function. Indeed, this latter create multiple global minima scattered in the space that vastly differ in terms of generalization. A Algorithmic regularization is induced by and depends on many factors such learning rate and batch size (Goyal et al., 2017; Hoffer et al., 2017; Keskar et al., 2016; Smith et al., 2018). initialization Allen-Zia Zhu & Li (2020), adaptive step-size (Kingma & Ba, 2014; Neyshabur et al., 2015; Wilson al., 2017), batch normalization (Arora et al., 2018; Hoffer et al., 2019; Ioffe & Szegedy, 2015) and dropout (Srivastava et al., 2014; Wei et al., 2020). However, none of these works theoretically analyzes the regularization induced by momentum. We therefore start our investigation by raising the following question:
Does momentum unconditionally improve generalization in deep learning?
This question could be positively answered given the success of momentum for learning distinet architectures such as ResNets (He al., 2016) or BERT (Devlin et al., 2018). However, we here empirically give negative answer through the following synthetic example in deep learning. We consider a binary classification problem where data-points are generated from a standard normal distribution and labels are outputs of teacher networks. Starting from the same initialization, train different over wver-parametrized student networks using GD and GD+M. Based on Table I, whether the target function is simple (linear) or complex (neural network), momentum does not improve generalization even when using a non-linear neural network as learner. The same observation holds for SGD/SGD+M as shown in the Appendix. Therefore, momentum does not always lead to higher generalization in deep learning. Instead, such benefit seems to heavily depend on both the structure the data and the learning problem.
On which data set does momentum help generalization? In this paper, in order to deter- mine the underlying mechanism produced by momentum to improve generalization, we de- sign binary classification problem with simple data structure where training a two-layer (over- parameterized) convolutional network with momentum provably improves generalization in deep learning. It is built upon data distribution that relies on the concepts of feature and margin. Infor- mally, each example in this distribution is ID image having P patches. One of the patches (the signal patch) contains a feature we want to learn and all the others are Gaussian random noise with small variance.
Mathematically, one can think of a feature as a vector w" E Rdd We assume that our training examples divided into large margin data where the signal is aw" with constant and small margin data where the signal is 3w with 3 & 1. Intuitively, the second type of data inherently noisier as the margin is small and therefore, a classifier would struggle more to generalize this type of data. We
2

---

Under review as a conference paper at ICLR 2022
a
Figure 2: Dataset equation (D) 2D. Each data-point is X, [es w", w". .7.44..) _ for some de E R. We project these points the 2D space (span(w" span(n)). The feature is w" and the noisy patch in span(n)) The large margin data (squares) have large component along w" and relatively small noise component and are thus roughly equal to ow, The small margin data (circles) have relatively large noise component and thus, these data are well-spread on the span of n.
Teacher
Linear
1-MLP
2-MI.P
I-CNN
2-CNN
Student
1-MLP
93.48/93.25
92.32/92.18
84.3/83.68
94.18/94.12
76.04/76.12
2-MLP
93.45/92.85
91.02/91.78
33,82/83,25
94.14/94.20
75.50/75.56
1-CNN
92.21/92.34
92.31/92.33
83.39/83.44
94.39/94.39
79.44/78.32
2-CNN
91.04/91.22
91.51/91.56
82.44/82.12
93.91/93.79
80.86/78.56
Table I:
Test accuracy obtained using GDIGD+M Gaussian synthetic dataset trained using neural network with ReLU activations. The training dataset consists in 500 data points dimension 30 and test set 5000 points. The student networks are trained for 1000 epochs to ensure zero training error. The results are averaged over 3 runs and we only report the mean (see Appendix for complete table).
underline that all the examples share the same feature but differ the intensity of the signal. We consider a training dataset of size N with the following split for < 1:
(1 P) datapoints are with large margin, j.N datapoints are with small margin data.
(D)
Figure sketches equation (D) in 2D setting. We emphasize that datasets having similar features and different margins are common in the real-world. Examples include object-recognition datasets such CIFAR (Krizhevsky et al., 2009) Imagenet (Deng et al., 2009) (for example, the "'wheel feature" of car can be strong or weak depending on the orientation of the car). More specifically, we believe that the dataset (D) can be viewed as simplified model of these object-recognition datasets. In this context, the following informal theorems characterize the generalization of the GD and GD+M models. They dramatically simplify Theorem 3.1 and Theorem 3.2 but highlight the intuitions behind our results.
Theorem 1.1 (Informal, GD+M). There exists a dataset of the form (D) with size N such that two-layer poveteaaramttrrized) convolutional network trained with GD+M:
1. initially only learns large margin data from the (1 - Ni)N examples.
2. has large historical gradients that contain the feature w" present in small margin data.
3. keeps learning the feature in the small margin data using its momentum historical gradients. The model thus reaches zero training error and perfectly classify large and small margin data at test. Theorem 1.2 (Informal, GD). There exists a dataset of the form (D) with size N such that a two-layer (over-parameterizee) convolutional network trained with GD:
1. initially only learns large margin data from the from the (1 -i)N examples.
2. has small gradient after learning these data.
3. memorizes the remaining small margin data from the j&N examples using the noises.
The model thus reaches zero training and manages to classify the large margin data at test. However. fails to classify the small margin data because of the memorization step during training.
Why does GD+M generalize better than GD? Since the large margin data are dominant, GD focus in priority on these examples to decrease its training loss. However, after fitting this data, it significantly lowers its gradient. The gradient is thus not large enough for learning the small margin data. Similarly, GD+M fits the large margin data and subsequently gets small gradient. However,
3

---

Under review as a conference paper at ICLR 2022
accuracy (smaal margin
10
100
GD
80
GD+M
Test accurae
50
10"
25
20
GD+M
GD+M
0
20
40
0
20 40
20 40
Number of epochs
Number epochs
Number of epochs (c)
(a)
(b)
Figure 3: (a): Training loss (b) test accuracy on large margin data and (c) test accuracy on the small margin data in the synthetic setting. While GD and GD+M get zero training loss, GD+M generalizes better on small margin
data than GD. Setting: 20000 training data, 2000 test data, d=30, number of neurons=5, number of patches=5.
100
80
Traninng Accuracy
Test Accuracy
60
60
GD (73.69)
GD+M (83.82)
40
GD (100.00)
GD (SM) (65.14)
CD+M (100.00)
CD M (SM) (80.36)
100
200
300
100
150
200
300
Number of epochs
Number of epochs
(a)
(b)
Figure 4: Training (a) and test (b) accuracy obtained with Resnet-18 CIFAR-IO dataset with artificially generated small margin data. architectures are trained using GD/GD+M for 300 epochs to ensure zero training error. Data augmentation, dropout and batch normalization are turned off. (SM) stands for the test accuracy obtained by the algorithm on the small margin data. Results are averaged over runs with best scheduled learning rate and weight decay for each individual algorithm separately.
contrary to GD, GD+M has large historical gradients in his momentum gradient. These gradients helped to learn the feature in the large margin data. They also help to learn small margin data since all the examples share the same feature. GD+M therefore uses his momentum to learn the small margin data. We name this process historical feature amplification and believe that it is key to understand why momentum improves generalization.
Empirical justification. We also provide empirical justification that such phenomenon does happen in a real-world setting as reported in Figure 4. In this experiment, we create small margin data in the CIFAR-10 dataset by respectively lowering the resolution of 10% of the training and test images, adding Gaussian noise of variance 0.005 and randomly shuffling the RGB channels. Figure 4 shows that though both algortihms reach zero training error and 100% training accuracy, GD+M gets higher generalization than GD on this decimated dataset. Above all, at test, GD+M performs well on small and large margin data while GD does relatively worse small margin Indeed, the relative accuracy drop for GD+M is 80.36 33//6.3/ /8.332 = 0.97 while for GD is equal to 85.14/73.66 0.88.
Our paper is organized as follows. In Section 2, we formally define the data distribution equation (D), the model and algorithms we use to learn it. Lastly, Section presents our main theorems and provide proof sketch in Section 4 and Section 5. Additional experiments can be found in the Appendix.
MORE RELATED WORK
Momentum in convex setting. GD+M (a.k.a. heavy ball or Polyak momentum) consists in calcu- lating the exponentially weighted average of the past gradients and using it update the weights. For convex functions near strict wicc--iifferentiable minimum, GD+M is optimal regarding local convergence rate Polyak (1963; 1964); Nemirovskij Yudin (1983); Nesterov (2003). However, may fail to converge globally for general strongly convex wwice-differentiable functions Lessard et al. (2015) and no longer optimal for the class smooth convex functions. the stochastic setting, GD+M is more sensitive to noise in the gradients; that is, to preserve their improved convergence rates, significantly less noise is required d' Aspremont (2008); Schmidt et al. (2011) 1); Devolder et al.
(2014); Kidambi et al. (2018). Finally, other momentum methods are extensively used for convex functions such as Nesterov's accelerated gradient Nesterov (1983). Our paper focuses on the use of GD+M and contrary the aforementioned papers, setting is non-convex and mainly focus
4

---

Under review as a conference paper at ICLR 2022
the generalization of the model learned by GD and GD+M when both methods converge to global optimal. We underline that contrary to the non-convex world, generalization is typically disentangled with optimization for (strictly) convex functions.
Non-convex optimization with momentum. A long line of work consists understanding the convergence speed of momentum methods when optimizing non-convex functions. Mai & Johansson (2020); Liu et al. (2020); Cutkosky & Mchta (2020); Defazio (2020) show that SGD+M reaches stationary point as fast as SGD under diverse assumptions. Besides, Leclere & Madry (2020) empirically shows that momentum accelerates neural network training for small learning rates and slows it down otherwise. Our paper differs from these works as we work in the batch setting and theoretically investigate the generalization benefits brought by momentum (and not the training ones).
Generalization with momentum. Momentum- based methods such as SGD+M, RMSProp (Tiele- man & Hinton, 2012) and Adam (Kingma & Ba, 2014) are standard in deep learning training since the seminal work of Sutskever al. (2013). Although its well accepted that Momentum improve generalization in deep learning, only a few works formally investigate the role of momentum in generalization. Leclerc Madry (2020) empirically reports that momentum yields higher general- ization when using a large learning rate. However, they assert that this benefit can be obtained by applying an even larger learning rate on vanilla SGD. We suspect that this observation is due to batch normalization (BN) which is known to dramatically bias the algorithm's 's generalization (Lyu & Li, 2019). In Appendix, we report that BN reduces the generalization gain of momentum comparing to without BN. To our knowledge, our work is first that theoretically investigate the generalization of momentum in deep learning.
2 SETTING AND ALGORITHMS
In this section, we first introduce formal definition of the data distribution equation (D) and the neural network model we use to learn it. We finally present the GD and GD+M algorithms.
General notations. For a matrix W Rm we denote by w, its r-th row. For function f: mxd + R. we denote by V (W) the gradient of f with respect to w, and V)(W) the gradient with respect to W. For an optimization algorithm updating vector w, w(t) represents its iterate at time We use La for the d identity matrix and 1m the all-ones vector of dimension m. Finally, we use the asymptotic complexity notations when defining the different constants in the paper. We use Ô 0, Ω to hide logarithmic dependency on d.
Data distribution. We define our data distribution D as follows.
Each sample from D consists in an input data X and a label that are generated as:
1. The label y is uniformly sampled from {-1, 1].
Each data-point X = (X. X(P]) consists in P patches where each X[i] E Rd. Signal patch: for one patch P(X) E [P], we have XiP(X)) = cw", where E R,
w"
Rd and |
4. The distribution of e satisfies that
ay with probability By
with probability j
5. Noisy patches: for all the other patches j E
(()) (O000000oorr (I-w"w²
We precise that we sample the noisy patches in the orthogonal complement of w" have simpler analysis. To present the simplest result, we assume that the values in equation (D) satisfy a 6.49 [2. pdlylog(d)).
p2 oz o va and
Using this model, generate training dataset Z {(X,, : Us) hie[M] where X, (x,15))EE We focus on the case where μ = (d) and N = θ (=) We let to be partitioned in two sets E and Zg such that 31 gathers the large margin data while Z, the small margin ones. Lastly, we define |2,1 the fraction of small margin data.
Learner model. We use a two-layer convolutional neural network with cubic activation to learn the training dataset 2. This model is the simplest non-linear network since a quadratic activation
5

---

Under review as a conference paper at ICLR 2022
would only output positive labels and mismatch our labeling function. The first layer weights W E Rmnd and the second layer is fixed to mm Given a input data X, the output the model is
P
(x)
(CNN)
The number of neurons is set as m polylog(d) to ensure that (CNN) mildly over-parametrized. Training objective. We fit the training dataset 2 using (CNN) and solve the logistic regression problem
> 2 [ L(W). 2
min WER
log exp (.ff(w)))) +
(P) sheds light on our choice of cubic activation in (CNN). Indeed, it is the smallest polynomial degree that makes the training objective (P) non-convex and compatible with our dataset. Linear or quadratie activations would respectively make the problem convex all the labels positive. Here, pick À
0, Poly(d)N
Importance of non-convexity. When À > O, if the loss N Σ log (1 + exp (-w (X.))) is convex, then there is unique global optimal solution, so the choice of optimization algorithm does not matter. In our case, due to the non-convexity of the training objective, GD M converges to different (approximate) global optimal comparing to GD, with better generalization properties.
Test error. We assess the quality of predictor W using the classical 0-1 loss used in bi- nary classification. Given a sample (X.y), , the individual test (classification) error is defined as (X, v) = 1[ (X)y < OJ. While L measures the eπror of fw on an individual data-point, we are interested in the test error that measures the average loss over data points generated from (D) and defined
L(fw) Exx,))= (f (X),
(TE)
Algorithms. We solve the training problem equation (P) using GD and GD+M. GD is defined by w(++1) (()) ,w((), for 1 1:2 0,
(GD)
where 7) > the learning rate. On the other hand, GD+M is defined by the update rule
((+)) -g (2) + (1 71 VZ for 1 2 0. W(+1) W - (g
(GD+M)
where y E (0,1) is momentum factor. We now detail how to set parameters in (GD) and (GD+M). Parametrization 2.1. When running GD and GD+M on equation (P), the number of iterations is T (p)) dOolo d) /())] For both algorithms,, the weights w( (0) initialized using independent samples from normal distribution (0, where of polylog(d) The learning rate is set as:
d
1. GD: the learning rate may take any reasonable value v E (0, Ö(1).
2. GD+M: the learning rate is large learning rate: = =().
Lastly, the momentum factor in GD+M set to be 7 =1 polylog
Our Parametrization 2.1 matches with the parameters used in practice the weights generally initialized from Gaussian with small variance and momentum is set close to (Sutskever et al., 2013).
3 MAIN RESULTS
We now formally state our main theorems regarding the generalization of models trained using equation (GD) and equation (GD+M) on the training set Z generated by equation (D), As announced in the introduction, we show that the GD+M model incurs generalization error that dramatically smaller than the GD model. Before introducing the main result, we define some notations:
'This is consistent with the empirical observation that only momentum with large learning rate improves generalization (Sutskever al., 2013)

---

Under review as a conference paper at ICLR 2022
Main objects. Let E [m], i [ P\(P(X.)), y (0. 1) and 2 0. We mainly interested in wif the r-th weight the network, V [(W(t)) the gradient the training loss w.r.. Wr. gr the momentum gradient defined by gf [(++1) ng) + (1-7)V L(W(O). The analysis lies on the projection of these objects on the feature w² and on noisy patches X,[i]. We introduce the following notations for the component of the learned weights along feature and noise directions:
Projection on w G
(wt ww)
Projection on X, i.j,i = (w/)) ,Xbl)>.
- Total noise: =
- [(EPP)(P(X.)) (wr x.bii>
Maximum signal: let Tmax = argmax (1)
elt) cr
Theorem 3.1. Assume that
GD (P) for T iterations with parameters set as in Parametriza- tion 2.1. With probability at least 1 - o(1), the weights learned by GD
1. partially learn the feature: for all E [m], 16 <(1/aa).
2. memorize from small margin data: for all i Z2, _ (1(1).
Consequently, the training error is smaller than (uuppoy((d) and the test error is at least M(p).
Intuitively, the training process of the GD model is described as follows. Since the large margin data are dominant in Z. the gradient points mainly in the direction the feature w". Therefore, GD eventually learns the feature in 21 (Lemma 4.1) and the gradients from 21 quickly become small. Afterwards, the gradient is dominated by the gradients from Zg (Lemma 4.2). Because 2g has small margin, the full gradient is now directed by the noisy patches. It implies that GD memorizes noise in Z2 (Lemma 4.4). Since these gradients also control the amount of remaining feature to be learned (Lemmaa 4.3), conclude that the GD model partially learns the feature and introduces huge noise component in the learned weights. We provide a proof sketch of Theorem 3.1 in Section 4.
Theorem 3.2. Assume that we run GD+M on equation for T iterations with parameters set as in Parametrizution 2.1. With probability at least - o(1), the weights learned by GD+M
1. (at least for one of them) is highly correlated with the feature: c!T) (2(133).
2. are barely correlated with noise: for all r [m], for all i [N] and j E [P]. Ö(oo). Consequenaly, the training loss and the test error are at most ((p)))ly(d)).
Intuitively, the GD+M model follows this training process. Similarly GD, it first fits the Z (Lemma 5.1). Contrary to GD, the momentum gradient is still highly correlated with w² after this step (Lemma 5.2). Indeed, the key difference is that momentum accumulates historical gradients. Since these gradients were accumulated when learning large margin data, the direction of momentum gradient is highly biased towards w". Therefore, the GD+M model amplifies the feature from these historical gradients to learn the feature in small margin data (Lemma 5.3). Subsequently. the gradient becomes small (Lemma 5.4) and the weights are no longer updated. Therefore, the GD+M model manages to ignore the noisy patches (Lemma 5.5) and learns the feature from both E, and Z,. We provide proof sketch Theorem 3.2 in Section 5.
To state the proof, we further decompose the gradients along signal and noise directions.
Projection on w*: (e(0) (V,, [(w)), w²) and _. (gf (t) w*)
Projection on X : _ (V.. (() X.DI)>. ((I) = (or .x(ii)
- Maximum signal: let Fimx = argmax,efmm
(1) Crmax and (()) (!t)
Signal and noise iterates. Our malyysisii is build upon decomposition of the updates equation (GD)
and equation (GD+M) on w and X. These decompositions are respectively defined as follows:
[f+1) clt) - (/g(()) (GD-S)
=!))
-.j.r no(") (GD-N)
7

---

Under review as a conference paper at ICLR 2022
g = -9 + +(1 +1- 3 C (1+1) (1) - - (GDM-S)
(t+1) ( (1) + +1 -
((+1) [(t) G((+1)
Ju =
(GDM-N)
We detail how these dynamics to analyze GD+M and GD in Section 4 and Section 5. Our anal-
ysis heavily depends on the gradients of the training loss which involve sigmoid(z) (1 + e -=
We define the derivative of a data-point as e
(::nodd(yy::woee (X,)), the derivatives Uk $ Eieza 4 for l E (1, and the full derivative ult) v1 1/2
(0)
4 ANALYSIS OF GD
In this section, we provide proof sketch for Theorem 3.1 that reflects the behavior of GD with A 0. A more detailed proof (extending to À > 0) can be found in the Appendix.
Step I: Learning Z,. At the beginning of the learning process, the gradient is mostly dominated by the gradients coming from the 2, samples. Since these data have large margin, the gradient is thus highly correlated with w' and +t increases as shown in the following Lemma.
Lemma 4.1. For all E [m] and t 2 0, equation (GD-S) simplified as:
((+1) o(o) (())a²((())) sigmoid(- -E.= a2(c
Consequently, after To = θ moado.)) iterations, for all E [To; we have cl0 2 (111/a).
Intuitively, the increment in the update in Lemma 4. is non-zero when the sigmoid is not too small which is equivalent cff) < Ó(1/a). Therefore, c( keeps increasing until reaching this threshold. After this step, the 21 data have small gradient and therefore, GD has learned these data.
Lemma 4.2. Let To θ
After t E [To. T'I iterations, the Z, derivative is bounded as (t) 2/
11 < ò
The full derivative is vlt) z (m (1 8a
n(| MT--To+Ija
U/
By our choice of parameter, Lemma 4.2 indicates that the full gradient is dominated by the gradients from 2g data after To = 5 pmaa
Consequently, 112 (t) also rules the amount of feature learnt by GD.
Lemma 4.3. Let To = = ((mm)))))) p For E [To: T). equation (GD-S) becomes (1+1) < 0(11/)++
Ö(133/a) Et 7
(t) Lemma 4.3 implies that quantifying the decrease rate of u provides estimate on the quantity of feature learnt by the model. We remark that 2/2 sigmoid( (83 Ex (cs + { for some i Zz. We thus need determine whether the feature or the noise terms dominates in the sigmoid.
Step 2: Memorizing Zz. We now show that the total correlation between the weights and the noise
in Zg data increases until being large.
Lemma 4.4. Let 0 and E Zz. Assume that =(( < Ō(1). Then, equation (GI-N) can be simplified as:
2 O(no2d)
- (PoPva)
y 3 (11)
[E (.
δ
igj 2 ojj
+
N
a
Let Ti = Ō ( ( Therefore, = > f((), E [Ti,T] and thus GD memorizes.
By Lemma 4.4, in the gradient of Zn data, the noise term dominates the feature term (which scales as O(33)). Consequently, the algorithm memorizes the 2, data which implies a fast decay of v/().
8

---

Under review as a conference paper at ICLR 2022
Lemma 4.5. Let Ti = =Ō - (ooViooa)) For t [T1,T], we have Er 1/2 S =o (1o)))
Combining Lemma 4.5 and Lemma 4.3, we prove that GD partially learns the feature. Lemma 4.6. For t. _ T, the signal component satisfies elt) < (1/a))
Lemma 4.4 and Lemma 4.6 respectively yield the first two items in Theorem 3.1. Bounds on the training and test emrrs are respectively obtained by plugging these results in (P) and (TE).
5 ANALYSIS OF GD+M
In this section, we provide a proof sketch for Theorem 3.2 that reflects the behavior of GD+M with 0. A more detailed proof (also extending to À > 0) can be found in the Appendix.
Step 1: Learning 21. Similarly to GD, by our initialization choice, the early gradients and so, momentum gradients are large. They also spanned by the feature w" and therefore, the GD+M model also increases its correlation with w"
Lemma 5.1. For all E [m] and 2 0, as long dl0 S Ō(1/a), the momentum update equation (GDM-S) simplified as:
= + (1 (1-1))60 (00a))
Consequently, after To 6
1 iterations, for all E Th we have c( > (11/a)).
Step 2: Learning Zz. Contrary to GD, GD+M has large momentum that contains w" after Step 1.
Lemma 5.2. Let To è
doa +
- For t [To, T], we have g 2 S(VI-7/a)
Lemma 5.2 hints an important distinction between GD and GD+M: while the current gradient along w" is small at time To, the momentum gradient stores historical gradients that are spanned by w". It amplifies the feature present previous gradients learn the feature from small margin data.
iterations, for E [T1, T7, we Lemma 5.3. Let To = (oous + r After Ti = To + θ (1=))
have cl 2 5 (a) Our choice of parameter in Section 2, this implies c(t) > ((1/B).
Lemma 5.3 states that least of the weights that is highly correlated with the feature compared GD where c(t) Ō(1). This result implies that vit) converges fast.
Lemma 5.4. Let To = è yoor - After Ti To +
iterations, for E [Ti, (+))
00 Ō 7(C
With this fast convergence, Lemma 5.4 implies that the correlation of the weights with the noisy patches does not have enough time to increase and thus, remains small.
Lemma 5.5. Let i E [N], j E [P]MP((X)) and E [m]. For t 2 O, equation (GDM-N) can be rewritten as (G(t+D| S y (
L (1 (1-1)) (00
As a consequence, after [T. T
iterations, we thus have / S Ö(anaVil).
Lemma 5.3 and Lemma 5.5 respectively yield the two first items in Theorem 3.2.
DISCUSSION
Our work first step towards understanding the algorithmic regularization of momentum and leaves room for improvements. We constructed data distribution where historical feature amplification may explain the generalization improvement of momentum. However, it would interesting to understand whether this phenomenon is the only reason whether there are other mechanisms explaining momentum's benefits.An interesting setting for this question NLP where momentum is used to train large models as BERT (Devlin et al., 2018). Lastly, analysis is in the batch setting to isolate the generalization induced by momentum. would interesting to understand how the stochastic noise and the momentum together contribute the generalization of neural network.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Zeyuan Allen-Zht and Yuanzhi Li. Towards understanding ensemble, knowledge distillation and self-distillation in deep learning. arXiv preprint arXiv:2012.09816, 2020.
Sanjeev Arora, Zhiyuan Li, and Kaifeng Lyu. Theoretical analysis auto rate-tuning by batch normalization, arXiv preprint arXiv: drXiv:1812.03981, 2018.
Sanjeev Arora, Nadav Cohen, Wei Hu, and Yuping Luo. Implicit regularization in deep matrix factorization, arXiv preprint arXiv:I905. 2019.
Anthony Carbery and James Wright. Distributional and 19 norm inequalities for polynomials over convex bodies in R". Mathematical research letters, 8(3):233-28) 248, 2001.
Lenaic Chizat and Francis Bach. Implicit bias of gradient descent for wide two-layer neural networks trained with the logistic loss. In Conference on Learning Theory, pp. 1305-1338. PMLR, 2020.
Ashok Cutkosky and Harsh Mehta. Momentum improves normalized sgd. In International Conference Machine Learning, pp. 2260-2268. PMLR, 2020.
Alexandre d' Aspremont. Smooth optimization with approximate gradient. SIAM Journal on Opti- mization, 19(3):111-11183 2008.
Aaron Defazio. Understanding the role of momentum in non-convex optimization: Practical insights from syapunov analysis. arXiv preprint
100::2000.0040000 2020.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pp. 248-255. leee, 2009.
Jacob Devlin, Ming-Wos Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint / 040005 2018.
Olivier Devolder, François Glineur, and Yurii Nesterov. First-order methods of smooth convex optimization with inexact oracle. Mathematical Programming, 146(1):37-75, 2014.
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 170.007706.06777, 2017.
Suriya Gunasekar, Blake Woodworth, Srinadh Bhojanapalli, Behnam Neyshabur, and Nathan Srebro. Implicit regularization in matrix factorization. 2018 Information Theory and Applications Workshop (ITA), pp. 1-10. IEEE, 2018
Jeff Z HaoChen, Colin Wei, Jason D Lee, and Tengyu Ma. Shape matters: Understanding the implicit bias of the noise covariance. arXiv preprint arXiv: 08680, 2020.
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 recognition, pp. 770-778, 2016.
Elad Hoffer, Itay Hubara, and Daniel Soudry. Train longer, generalize better: closing the gen- cralization gap in large batch training of neural networks. arXiv preprint arXiv:1705.0874/ 2017.
Elad Hoffer, Ron Banner, Itay Golan, and Daniel Soudry. Norm matters: efficient and accurate normalization schemes in deep networks, 2019.
Sergey Ioffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International conference on machine learning, pp. 448-456. PMLR, 2015.
Ziwei Ji and Matus Telgarsky. The implicit bias of gradient descent on nonseparable data. In Conference Learning Theory, pp. 1772-1798. PMLR, 2019.
10

---

Under review as a conference paper at ICLR 2022
Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Peter Tang. On large-bater batch training for deep learning: Generalization gap and sharp minima. arXiv preprint arXiv:1609.04830 2016.
Rahul Kidambi, Praneeth Netrapalli, Prateek Jain, and Sham Kakade. On the insufficiency of existing momentum schemes for stochastic optimization. In 2018 Information Theory and Applications Workshop (ITA), pp. 1-9. IEEE, 2018.
Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint arXiv:14/2.6980, 2014.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep con- volutional neural networks. Advances in neural information processing systems, 25:1097-1105, 2012.
Guillaume Leclere and Aleksander Madry. The two regimes of deep network training. arXiv preprint arXiv:2002. 10376, 2020.
Laurent Lessard, Benjamin Recht, and Andrew Packard. Analysis and design of optimization algorithms via integral quadratic constraints, 2015.
Yuanzhi Li, Colin Wei, and Tengyu Ma. Towards explaining the regularization effect of initial large learning rate in training neural networks. arXiv preprint arXiv: 2019..
Yanli Liu, Yuan Gao, and Wotao Yin. An improved analysis of stochastic gradient descent with momentum. arXiv preprint arXiv:2007.0798) 2020.
Shachar Lovett. An elementary proof of anti-concentration of polynomials in gaussian variables. Electron. Colloquium Comput. Complex., 17:182, 2010.
Kaifeng Lyu and Jian Li. Gradient descent maximizes the margin of homogeneous neural networks. arXiv preprint arviv: 190.::99000099090 2019.
Vien Mai and Mikael Johansson. Convergence of stochastic gradient method with momentum for non-smooth non-convex optimization. In International Conference on Machine Learning, pp. 6630-6639, PMLR, 2020.
Arkadij Semenovië
Nemirovskij and David Borisovich Yudin. Problem complexity and method efficiency in optimization. 1983.
Yurii Nesterov. method for unconstrained convex minimization problem with the rate of conver- gence (1/K* 2). In Doklady an ussr, volume 269, pp. 543-547, 1983.
Yurii Nesterov. Introductory lectures convex optimization: A basic course, volume 87. Springer Science & Business Media, 2003.
Behnam Neyshabur, Ruslan Salakhutdinov, and Nathan Srebro. Path-sgd: Path-normalized optimiza- tion in deep neural networks. arXiv preprint 1rXiv:1506.026111 2015.
Boris T Polyak. Gradient methods for the minimisation of functionals. USSR Computational
Mathematics and Mathematical Physics, 3(4):864-878, 1963.
Boris T Polyak. Some methods of speeding up the convergence of iteration methods. Ussr computa-
tional mathematics and mathematical physics, 4(5):1-17, 1964.
Mark Schmidt, Nicolas Le Roux, and Francis Bach. Convergence rates of inexact methods for convex optimization. arXiv preprint arXiv: 100.2419. 2011.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint 1rXiv:1409.153: 2014.
Samuel L. Smith, Pieter-Jan Kindermans, Chris Ying, and Quoc V. Le. Don't 't decay the learning rate, increase the batch size, 2018
11

---

Under review as a conference paper at ICLR 2022
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The implicit bias of gradient descent on separable data. The Journal of Machine Learning Research, 19(1): 2822-2872 2018.
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: a simple way to prevent neural networks from overfitting. The journal of machine learning research, 15():1199--1958 2014.
llya Sutskever, James Martens, George Dahl, and Geoffrey Hinton. On the importance of initialization and momentum in deep learning. In International conference machine learning, pp. 1139-1147. PMLR, 2013,
Tijmen Tieleman and Geoffrey Hinton. Lecture 6.5-rmsprop: Divide the gradient by a running average of its recent magnitude. COURSERA: Neural networks for machine learning. 4(2):26-31, 2012.
Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47, Cambridge university press, 2018.
Martin Wainwright. High-dimensional statistics: non-asymptotic viewpoint, volume 48. Cam- bridge University Press, 2019.
Colin Wei, Sham Kakade, and Tengyu Ma. The implicit and explicit regularization effects of dropout, 2020.
Ashia C Wilson, Rebecca Roelofs, Mitchell Stern, Nathan Srebro, and Benjamin Recht. The marginal value of adaptive gradient methods in machine learning. arXiv preprint arXiv: 2017.
Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. arXiv preprint arXiv: arXiv:1605.07144 2016.
12


Reviews:
[{"review_id": "nxMDBmuoMfA", "reviewer": "Reviewer_osph", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The main strength of this paper is a rigorous mathematical analysis that exhaustively justifies the generalization gains from adding momentum to the gradient descent algorithm. The analysis is solid and sound (although I did not manage to check all the details carefully) and could be interesting from a mathematical perspective.\n\nHowever, these results reflect only a specific case of problem statement, which is the major weakness of this submission. Namely, the authors consider a binary classification problem with a two-layer convolutional neural network with cubic activation and a fixed second layer. The data is generated according to a specific scheme where each data point has a single patch containing useful information (the signal patch), and all the others are Gaussian random noise with a small variance; the data is split into large-margin and small-margin parts according to the intensity of the signal patch. The authors claim that real-world datasets possess similar properties, however, they do not provide sufficient grounding for that argument. Figure 3 exhibits that momentum indeed gives more gains if real data are artificially augmented with small margin data (which accords with the provided theory), but it does not prove that real data initially *had* such structure.    \nIn other words, even if the derived theory is correct in the particular case, it still does not suffice to explain the benefits of momentum in deep learning unless the authors prove that the considered case is relevant for practical deep learning. That becomes especially acute in light of the provided counterexample with teacher-student learning on Gaussian data. It is unclear why the authors consider their setup more relevant to deep learning than the latter.\n\nOther concerns: \n1. \"Indeed, a batch size of 1024 is known to be large enough in CIFAR training to consider the stochastic gradient relatively close to the full gradient (Cohen et al., 2021)\". I could not find any reference in Cohen et al. (2021) about this. In fact, Cohen et al. (2021) train their models on subsets of original datasets to perform actual full-batch gradient descent. I am not convinced that taking a batch size of 1024 in SGD reduces it to GD. Moreover, such large-batch settings are well studied in prior work (see, e.g., https://arxiv.org/abs/2006.15081) and are known as \"curvature dominated\nregime\", in which SGD with momentum typically outperforms vanilla SGD. I suggest the authors reconduct their experiments in the proper full-batch GD setting.\n2. \"In this paper, we ... empirically show that gradient descent with momentum (GD+M) significantly improves generalization comparing to gradient descent (GD) in many deep learning tasks\". In the main body of the paper, I could only find experiments with ResNet and Wide-ResNet on CIFAR datasets, which does not seem like \"many deep learning tasks\". I suggest either providing more experiments or softening the wording.\n3. The authors did not provide details on their experimental setup.\n\nMinor concerns:\n* The results are stated for the momentum with updates of type $g^{(t+1)} = \\gamma g^{(t)} + (1 - \\gamma) \\nabla \\hat{L}(W^{(t)})$ while the conventional momentum update takes the form of $g^{(t+1)} = \\gamma g^{(t)} + \\nabla \\hat{L}(W^{(t)})$. How do the results carry over to this case?\n* Table 3(b) in supplementary demonstrates that for large batch sizes GD+M performs worse than conventional GD. Is that a typo or an outlier?\n* \"An interesting setting for this question is NLP where momentum is used to train large models as BERT (Devlin et al., 2018)\". As far as I know, large NLP models are usually trained with Adam or more sophisticated optimizers rather than SGD+M. \n* \"We suspect that this observation is due to batch normalization (BN) which is known to dramatically bias the algorithm’s generalization (Lyu & Li,\n2019)\". To my knowledge, Lyu & Li (2019) did not write about BN, please, correct the citation.\n\n---\n\n**UPD**  \nAfter reading the authors' response, I am inclined to keep my score unchanged.", "summary_of_the_paper": "\nThis paper investigates the generalization benefits of using momentum when training neural networks with gradient descent. In contrast with existing literature, which studies momentum mostly empirically and in the stochastic setting, the authors develop a theoretical explanation for why generalization improves when optimization is performed using full-batch gradient descent with momentum (GD+M) than without it (GD). Their analysis focuses on a specific structure of the data and the learning problem, and the authors argue that similar assumptions apply to the real-world datasets used in practice. The authors prove two main results: one about GD learning large-margin data and overfitting to small-margin data and the other about GD+M successfully learning all the data thanks to historical gradients. Interestingly, the authors provide a counterexample where momentum does not aid generalization (or even worsen it), which offers good food for thought.", "summary_of_the_review": "This paper provides a solid theoretical analysis, which, however, applies only to a specific problem statement and thus cannot be considered a satisfactory argument for why momentum is beneficial in deep learning (unless the authors provide more evidence that their setting is relevant to real-world datasets). The empirical justification does not correctly reflect the considered full-batch gradient descent training. I believe the paper could benefit from another round of revision and is not ready for publication yet.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "g4clcNeNcOR", "reviewer": "Reviewer_Vuuz", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths: The paper was clear and well written, particularly the toy example on when momentum hurts, as well as all of the proof sketches.\n\nWeaknesses: My complaints are primarily around significance and presentation.\n\nFirst some comparatively minor nits, to get them out of the way: \n-The loss values in Figure 1 on the left pane are quite difficult to parse--you might consider making this logscale.\n-In a couple of places you refer to \"his momentum\" when you probably mean \"its momentum\"\n\nMore substantively, I'm a little perplexed why the authors went to such great lengths to construct a dataset and prove statements about its training performance, but then did not actually perform any training using that dataset or that (peculiar) architecture used in the analysis of the theorems.  I think the manuscript would be greatly improved by explicitly demonstrating the generalization gap proved by the authors, preferably in a plot as a function of $d$ and  $\\mu$ (which seem to be the key control knobs on the generalization results).\n\nI'm likewise a bit unsure of the significance of this work.  It's not clear whether the mechanism proposed by the authors is also at play in other architectures, or if this is entirely a manifestation of the author's construction.  That is to say, the result is clearly progress, but it would significantly improve the impact if a thread could be drawn between this mechanism, and a non-synthetic dataset.\n\nFinally, I'm a bit wary of ICLR submissions that have 60 pages of proofs.  These sorts of articles probably get more thorough review (and more _useful_ review) via a journal submission.\n", "summary_of_the_paper": "The authors provide a new perspective on the why momentum is useful for generalization in neural networks.  They provide motivating intuition around why momentum is not always useful (including a great toy example), as well as empirical experiments on CIFAR-10.\n\nFinally, the authors prove a variety of theorems on a synthetic problem where momentum provably results in greater generalization.", "summary_of_the_review": "The work is technically sound (to my knowledge), but of limited significance.  This thread of work _could_ be of great significance if the mechanism proposed by the authors can be shown to be behind the performance of more realistic models, so I don't want to discourage the author's current line of investigation---it's more that I'm unsure if this is a good match for ICLR.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "eDihE5QsVfv", "reviewer": "Reviewer_6raf", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper shows that gradient descent + momentum (a.k.a. Heavy Ball) provably generalizes better than standard gradient descent for training a two-layer convolution network when the data distribution has a particular structure. Specifically, it considers a binary classification dataset of size N of which $(1-\\hat{u}) N$ are with a large margin and $\\hat{\\mu} N$ are with a small margin. Most of the data points are with a large margin, i.e. $\\hat{u} << 1$\n\nThe paper starts by giving some empirical evidence --- GD+M generalizes better for training Resnet-18 and WideResnet on CIFAR-10 and CIFAR 100 than GD. The paper also reports an experiment on a synthetic dataset in which features are from a Guassian distribution and shows that momentum does not improve over GD, which suggests that whether momentum has an advantage over GD depends on the underlying data distribution.\n\nAs the authors argue, the key to showing that momentum generalizes better is by showing that after a certain number of iterations, even though the current gradient could be small for those data points with a small margin, the momentum (which is an weighted average of previous gradients) has a sufficient size of projection onto the signal direction $w_*$. Hence, GD+M can still learn $w_*$ from the small margin data.\n\nHowever, the proof in the appendix in my opinion is not written well. There are a few typos and a lot of approximations, e.g. a lot of $O(\\cdot)$ and $\\Theta(\\cdot)$. For some of the approximations, it is hard to tell if the approximations make sense.  Here are some questions regarding the analysis.\n\n\n1. (Lemma H.5): Can the authors provide a detailed derivation of the inequality (174) from (173)? The authors claim that by using Lemma H.6 one can get (174) but it is not clear at all from my perspective. Specifically, Lemma H.6 writes \n\n$$\\hat{L}(W^{(t)}) = \\Theta(1) \\left( \\hat{L}^{(t)}(\\alpha) +  \\hat{L}^{(t)}(\\beta)    \\right)$$\n\n$$\\hat{L}(W^{(t)} - \\eta \\gamma g^{(t)} ) \\leq \\Theta(1) \\left( \\hat{L}^{(t)}(\\alpha) +  \\hat{L}^{(t)}(\\beta)    \\right)$$\n\nDid the authors try to show $\\hat{L}(W^{(t)} - \\eta \\gamma g^{(t)} ) \\leq \\hat{L}(W^{(t)})$? If so, why don't just prove $\\hat{L}(W^{(t)} - \\eta \\gamma g^{(t)} ) \\leq \\hat{L}(W^{(t)})$ directly? Is this used anywhere in the proof of Lemma H.5?\nCan the authors write down precisely the constant that $\\Theta(1)$ in (180) and (181) represents?\nFurthermore, can the authors comment on why the approximation (188) makes sense?\nAlso, can the authors expand on the last sentence of the proof? How to apply Lemma I.24 to get (181)?\n\n2. (Lemma H.5): The first line on Page 48 says \"by Induction hypothesis C.2, we know that $ c_r^{(t)} \\geq 0$ for all t\".\nBut from Induction hypothesis C.2 (Page 16), it is only shown that $c_r^{(t)}$ is larger than a negative number. The validity of Lemma H.5 is concerning given this and the above concern.\n\n\n3. (Lemma I.15): The authors show that $z_t \\geq v$ for all $t \\geq t_0$. Can the authors explain where exactly in the proof did they show the \"for all $t \\geq t_0$\" part?\n\nA related question about Lemma I.16-I.17: Should one also show $z_t \\geq v$ for all $t \\geq t_0$ like Lemma I.15?\n\n4. (Lemma 4.4): Can the authors elaborate on \"Therefore, the sequence $y_i \\Xi_{i,j,r}^{(t)}$ is non-decreasing\" based on the inequality in the lemma?\n\n5. (Lemma 5.1~5.4) We see that the iterate complexities in these lemmas all have a $\\frac{1}{1-\\gamma}$ factor. Does it suggest that the progress of GD+momentum is slower when a larger value of the momentum parameter $\\gamma$ is used?\n\n6. (Lemma 5.2) The lemma shows the size of momentum is lower bounded as $g^{(t)} \\geq O( \\sqrt{1-\\gamma} )$. The lower bound becomes smaller and smaller as the momentum parameter $\\gamma$ increases. I found this counter-intuitive. The authors might want to explain this.\n\n7. (The sentence right below Lemma 5.4) QUOTE With this fast convergence, Lemma 5.4 implies that the weight of... are barely update. UNQUOTE \nThe authors might want to expand on how Lemma 5.4 implies this.\n\n8. (Typo on B.2) Check the definition of $r_{\\max}$\n\n9. (Typo on (4)) $y_i$ is dropped.\n\n10. Sentence right after (8) is not complete.\n\n11. ((65) on Page 9) Can the authors provide a detailed derivation of the inequalities on (65)?\n\n12.  Regarding the intuition of why GD+M generalizes better than GD --- the authors claim that it is because momentum stores historical gradients that are spanned by w_* and hence amplifies the features present in the previous gradients and helps learn the feature from the small margin data. Can the authors quantize how large is the signal in the momentum term compared to the signal in the gradient term? Is it $\\frac{1}{1-\\gamma}$ larger? This is not transparent from the proof.\n", "summary_of_the_paper": "This paper shows that gradient descent + momentum (a.k.a. Heavy Ball) provably generalizes better than standard gradient descent for training a two-layer convolution network when the data distribution has a particular structure.", "summary_of_the_review": "The analysis is not very clear, a lot of approximations are made throughout the proof, and some places in the proof are concerning. I don't recommend an acceptance at the current point.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "CkBvRayo6h", "reviewer": "Reviewer_Jrkp", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper considers a very important optimization problem in real application especially deep learning. The paper is well-organized and very easy to understand. The authors provided a very solid theoretical results under a very special case and some assumptions. However, I still have some questions to be addressed.\n\n1. Due to the theoretical results of GD and GD+M are built on a very special case, there is a big gap between the results in this paper and deep learning. It seems that the authors over-claimed the contribution of this paper.\n\n2. The authors claimed that they only focused on GD+M since the empirical results of GD+M can generalize better than GD (e.g., Figure 1). However, this is not realistic since the authors did not conduct GD+M and GD but large mini-batching SGD+M and SGD. In fact, the results only show that large mini-batching SGD+M can generalize better than large mini-batching SGD. Therefore, it is reasonable to focus on the contribution of momentum of the large mini-batching stochastic gradient (rather than \"true gradient\") on generalization.\n\n3. It is strongly recommended and needed to provide experiments to verify the theoretical result. At least, the authors should provide numerical results on a simulation data according to the data distribution $\\mathcal D$ (page 5) and the learning problem (page 6). The numerical results will make the contribution of this paper complete and solid. ", "summary_of_the_paper": "Through some experiments, this paper claims that momentum does not always lead to a higher generalization in deep learning and such benefit seems to heavily depend on both the structure of the data and the learning problem. Then, the authors considered a certain data structure (large and small margin data) and learning problem (binary classification problem with 2-layer CNN model and logistic loss). Under this special case, the authors shown that both GD and GDM reach zero training error and perfectly classify large margin data, but GD fails to classify the small margin data while GDM can still perfect classify small margin data due to the historical gradients caused by the momentum.", "summary_of_the_review": "1. Solid theoretical results under a special case\n\n2. Big gap in the paper\n\n3. The reason of considering GD+M\n\n4. Lack of experiment (for verifying the theoretical results)", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "3NUmEGWNDZ", "reviewer": "Reviewer_PBhC", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I am not an expert in this area and am not very familiar with the results presented by this paper.  But after I search and read related papers, I think this paper is very novel.\n\n1. Does momentum unconditionally improve generalization in deep learning is quite important in ML and AI. This paper answers this problem negatively by a construction method.\n\n2. This paper presents an insight that momentum helps to learn small margin data since all the examples share the same feature. I think this idea is wonderful and novel.\n\n3. This paper provides plenty of detailed theoretical results. Many technical lemmas are developed. \n\n4. The authors present the corresponding numerical experiments to demonstrate the theoretical findings.", "summary_of_the_paper": "This paper shows that the momentum conditionally improves the generalization by reconstructing a data case.", "summary_of_the_review": "I do not think this paper is below the accept bar due to its interesting topic, novel analysisis, interesting result, complicated techniques, and good presentation.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Meta-review: All but one of the reviewers recommended rejecting this submission. The reviewer recommending acceptance (PBhC) was not confident in their assessment and was unwilling to champion the paper during the discussion phase, making it very difficult for me to unilaterally overrule the de facto reviewer consensus and recommend accepting the submission. Although some of the reviewers recommending rejecting the submission made relatively weak arguments, others raised more compelling points in favor of rejecting the paper. The discussion and reviews convinced me that the preponderance of the evidence indicated that I should recommend rejecting on the merits of the case anyway. Ultimately, I am recommending rejecting this submission, primarily because I do not believe the empirical contributions are strong enough, nor are they polished enough. Holistically, it is hard to see what impact this work can have without improved empirical evidence, given how little guidance the theoretical results give to practitioners. That said, I hope the authors iterate some more on the experiments and refocus the narrative a bit in that direction.

The paper exhibits a problem where gradient descent with momentum provably generalizes better than gradient descent without momentum. Given that momentum does not universally improve the out of sample error of neural networks trained with gradient descent, we should strongly suspect that there also exist problems where adding momentum to gradient descent degrades out of sample performance. Therefore, what actionable insights do we have? The paper suggests that perhaps the details of the problem (constructed in the submission) where momentum helps gives us an ability to predict when momentum will be helpful in practice, but we would need to see several more successful predictions of this form on typical datasets from the literature or other real (non-synthetic) datasets. Furthermore, has the literature and this submission even demonstrated convincingly enough that momentum improving out of sample error for the same training loss is a common occurrence? And has this submission even made a convincing empirical case on CIFAR10, let alone a larger selection of problems? The latter question would be sufficient to reject the submission, but resolving it favorably would not, in my view, be sufficient to accept the submission without also more evidence for the prevalence of this momentum generalization phenomenon or without demonstrating successful predictions about relative generalization performance on more problems.

Has the literature established that gradient descent or minibatch stochastic gradient descent often generalizes better when using momentum? The paper says "While these works shed light on how momentum acts on neural network training, they fail to capture the generalization improvement induced by momentum (Sutskever et al., 2013)." but Sutskever et al. to my recollection only measures training set loss and never properly considers questions of generalization. Certainly, in many places in the literature we see momentum get better validation error, but rarely do we get information on whether it does so for the same training loss and a priori we should suspect optimization speed is the primary effect at play. The paper also claims "Although it is well accepted that Momentum improve generalization in deep learning...", but the submission does not provide enough evidence that this is well accepted. The results of Leclerc & Madry (2020) are equivocal and may well be confounded by batch norm, but would need to be investigated further. So no, at least with the citations in this submission, it is far from well-established that momentum often improves generalization performance, i.e. that momentum results in better validation loss for the same training loss. Of course it won't always do this, but we should observe it regularly in the wild (the more dramatically the better) for this to be interesting.

Ok, but what about the experiments on CIFAR10? These experiments are hard to interpret because they seem to compare misclassification error (zero one loss) with the actual optimization objective of cross entropy error. These issues may be resolvable, but in their current form leave open too many loose ends. Just because two training runs both get zero classification errors on the training set does not mean that they do not differ in the log loss and even a small difference in log loss might explain a large difference in out of sample classification error. Although we often use these quantities as proxies for each other, that isn't quite safe and a better way to conduct this measurement would be to select an iterate of GD without momentum that has an almost identical (but slightly better) training cross entropy loss than a specific iterate of GD with momentum and then compare the cross entropy loss on the validation set, repeating for many different runs and iterates.

In the final analysis, stochastic gradient descent without momentum rarely gets used in practice and full gradient descent even more rarely, so this submission needs to do a better job of making a case for the impact it will have on researchers in this field. Perhaps a stronger case can be made, but I do not quite find the current version sufficiently compelling.
Decision: Reject