Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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.

Finally, the authors prove a variety of theorems on a synthetic problem where momentum provably results in greater generalization.
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.

Weaknesses: My complaints are primarily around significance and presentation.

First some comparatively minor nits, to get them out of the way: 
-The loss values in Figure 1 on the left pane are quite difficult to parse--you might consider making this logscale.
-In a couple of places you refer to "his momentum" when you probably mean "its momentum"

More 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).

I'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.

Finally, 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.

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.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: 
This 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.
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.

However, 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.    
In 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.

Other concerns: 
1. "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
regime", in which SGD with momentum typically outperforms vanilla SGD. I suggest the authors reconduct their experiments in the proper full-batch GD setting.
2. "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.
3. The authors did not provide details on their experimental setup.

Minor concerns:
* 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?
* 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?
* "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. 
* "We suspect that this observation is due to batch normalization (BN) which is known to dramatically bias the algorithm’s generalization (Lyu & Li,
2019)". To my knowledge, Lyu & Li (2019) did not write about BN, please, correct the citation.

---

**UPD**  
After reading the authors' response, I am inclined to keep my score unchanged.
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.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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.
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.

1. 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.

2. 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.

3. 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_review: 1. Solid theoretical results under a special case

2. Big gap in the paper

3. The reason of considering GD+M

4. Lack of experiment (for verifying the theoretical results)
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper shows that the momentum conditionally improves the generalization by reconstructing a data case.
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.

1. 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.

2. 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.

3. This paper provides plenty of detailed theoretical results. Many technical lemmas are developed. 

4. The authors present the corresponding numerical experiments to demonstrate the theoretical findings.
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.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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.
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$

The 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.

As 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.

However, 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.


1. (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 

$$\hat{L}(W^{(t)}) = \Theta(1) \left( \hat{L}^{(t)}(\alpha) +  \hat{L}^{(t)}(\beta)    \right)$$

$$\hat{L}(W^{(t)} - \eta \gamma g^{(t)} ) \leq \Theta(1) \left( \hat{L}^{(t)}(\alpha) +  \hat{L}^{(t)}(\beta)    \right)$$

Did 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?
Can the authors write down precisely the constant that $\Theta(1)$ in (180) and (181) represents?
Furthermore, can the authors comment on why the approximation (188) makes sense?
Also, can the authors expand on the last sentence of the proof? How to apply Lemma I.24 to get (181)?

2. (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".
But 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.


3. (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?

A 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?

4. (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?

5. (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?

6. (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.

7. (The sentence right below Lemma 5.4) QUOTE With this fast convergence, Lemma 5.4 implies that the weight of... are barely update. UNQUOTE 
The authors might want to expand on how Lemma 5.4 implies this.

8. (Typo on B.2) Check the definition of $r_{\max}$

9. (Typo on (4)) $y_i$ is dropped.

10. Sentence right after (8) is not complete.

11. ((65) on Page 9) Can the authors provide a detailed derivation of the inequalities on (65)?

12.  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.

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.
review_title: null

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