Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper studies the implicit regularization of momentum based optimization algorithms on separable data. In particular, this paper proves that gradient descent with momentum, SGD with momentum, and full-batch Adam can both lead to the max-margin solution, which completes the prior results on the implicit regularization of GD and SGD (without momentum).
strengths_and_weaknesses: Overall, the strengths of this paper are clearly stated in the paper:

1. This paper first proves the implicit regularization of momentum-based optimizers. 
2. A new proof technique is developed for studying the algorithmic behavior when momentum is involved, which is of independent interest.

The weaknesses are as follows:

1. This paper does not clearly discuss the difference between GD and GDM (or SGDM). In particular, the authors only prove the implicit regularization/final converging point of GDM, which is the same as that of GD. However, the role that momentum plays in the training process is still not clear. For instance, can you show that the momentum can accelerate the training process (at least in stage 1)?

2. In practice, the training algorithms are typically performed with early stopping, thus the output of the optimizer will not be exactly (or even not close to) the max-margin solution. Can you elaborate on this point and provide some brief discussion regarding the difference between GD, GDM, and ADAM. Perhaps early stopping is one aspect of the empirical generalization differences between these optimizers.
questions: 1. Although the momentum will not affect the final converging point, how does it affect the optimization trajectory in the early stages? Will it bring some accelerations in terms of convergence, at least for linear classification problems?

2. What happens if we consider early stopping?

3. It would be better to discuss more regarding the nonconvex model. In practice, it is more likely that different optimization algorithms will admit different implicit regularization (or optimization trajectory) in early stages so that they will finally find different local minima, and the quality of the local minima (e.g., sharpness) will determine the generalization ability. Extending to deep homogenous models is definitely a good working direction, but it could be more interesting and important to focus on more general DNN models that the "local property" of the found solutions is more important.
limitations: Please refer to the weakness part.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper studies the implicit bias of gradient descent with momentum. The authors show that gradient descent with momentum, stochastic gradient descent with momentum, and deterministic Adam all converge to the L2 max-margin solution. 
strengths_and_weaknesses: Strengths: 

The results of the paper are solid and interesting. 

The presentation of the paper is clear and easy to follow.

The authors give a fairly comprehensive analysis of implicit bias in different settings.

Weaknesses: 

Although the results in this paper seem valid, they, to some extent, contradict the empirical observation that Adam and SGD usually have different generalization errors, as is discussed in [39]. This is worth some more discussion and investigation.

The experiments are mostly deferred to the appendix, and Figure 1 in the main part of the paper does not seem very convincing. 

questions: There are a number of works studying the generalization error of gradient descent with momentum / Adam:

Jelassi, Samy, and Yuanzhi Li. "Towards understanding how momentum improves generalization in deep learning." (2021).

Zou, Difan, Yuan Cao, Yuanzhi Li, and Quanquan Gu. "Understanding the generalization of adam in learning neural networks with proper regularization." arXiv preprint arXiv:2108.11371 (2021).

It would be very helpful if the authors can discuss the relation between the implicit bias results with these previous works.

limitations: This paper does not have any potential negative societal impact.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The author(s) studied the implicit regularization property of gradient descent method with momentum and its adaptive version. This work is theoretical in essence. It was shown that GDM, SGDM and deterministic Adam all converge to the max-margin solution. 
strengths_and_weaknesses: Overall, I think this paper makes a descent contribution on understanding the implicit regularization property of GDM and its variants, which is a important research topic in machine learning. I tried to check the proof for Theorem 2 and I think it is correct (though I think the proof sketch stated in the main context should be improved). I recommend acceptance if all other reviewers confirm that the proof is correct.

Some concern:
- Line 208-213 is a little bit confusing. In particular, the first bullet-point states that the analysis of [29] can be directly borrowed. However, the definition of $w$ is different from [29] since momentum is being used. Therefore a more careful explanation should be given. The third bullet-point is also confusing, I understand that $\int \| \frac{d w(s)}{ds} \|^2 ds$ is bounded, but $\int \| \frac{d w(s)}{ds} \| ds$ may not be bounded, so why is $\int \langle \hat{w},\frac{d w(s)}{ds} \rangle ds$ bounded?
- Line 214, it seems that it was shown that $\| r(T) \|^2$ is bounded by $O(1) +o( \| r(T) \| )$ instead of $\| r(T) \|^2 + o(\|r(T)\|)$ bounded by some constant.

Minor:
- $L_2$ and $L^2$ are used interchangeably, the term $L_2$ is used in abstract and the term $L^2$ is used in the main context.
- Line 14, Numerical experiments are conducted and support -> Numerical experiments are conducted to support …
- Line 57, parameter -> parameters
- Line 63, first order -> first-order
- Line 95, Interesting -> interested
- Line 195, better to mention that $\inf \xi(t) > -\infty$


questions: - The third paragraph of Section 3.4 of [1] states that they observe ADAM does not converges to the max-margin solution. Does the results established in this work contradict with their observation?
- Please see my questions for line 208-213 in the "strengths and weakness" section.
limitations: This paper has no potential negative societal impact.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper analyzes classification problems with linearly separable data and exponential-tailed loss.  The setting and analysis is inspired from the one in [1]. They start by reminding this setting in Section 3. In section 4, when running GDM on this problem, they show that the solution that is obtained is the L2 max-margin solution. They further detail the steps to get this result. In Section 5,  they show analogous results for SGDM and point out the differences with GDM in the analysis. In Section 6, they show that deterministic Adam and stochastic RMSProp converge to the L2 max margin solution as well. Finally, the authors run experiments on a "well-posed" dataset where they show that all the aforementioned algorithms converge to the l2 max margin solution.





[1] Soudry, Daniel, et al. "The implicit bias of gradient descent on separable data. (2018)
strengths_and_weaknesses: I summarize as follows the strengths and weaknesses of this paper.

Strengths: I find the paper well written and easy to follow. I appreciated the fact that the proof sketch in Section 4 was easy to understand. I also believe that it is interesting to know that with momentum, the solution obtained is the max margin one. 

Weaknesses: I have two major concerns regarding this paper. First, it is not focused on one single algorithm or phenomenon to understand. After reading the paper, the main message that pops in mind is  "several classical algorithms converge to the L2 max margin solution for linearly separable data". I think it would have been more beneficial to isolate a factor such as momentum and characterizing when it is useful.

Another main flaw I find in this paper is that it is incremental. On one hand, the authors do a good job at pointing out the differences between their analysis and the one in [1]. However, I think that the authors should do a better work at i) explaining intuitively with momentum it is not obvious to get the max margin solution ii) point out more clearly the convergence rate to the max margin solution (so that we see the difference with GD). I guess that a theorem like theorem 5 in [1] would be a good idea. Do you have a faster convergence rate when using momentum? The same remark I make above holds for deterministic Adam. I think there would be a lot of benefits to point out the difference between the algorithms. 

I would like to raise the authors' attention on [2] that shows a separation between GD and GDM. In their setting, they consider logistic regression with linearly separable data and their learner model is a polynomial activation CNN. They show that GD still converges to the max margin solution but GDM does not converge to the max margin solution. In their setting, the max margin solution does not generalize while the one found by GDM generalizes. Their setting is different from the setting studied in this paper but I think it is good for the authors to be aware of this work.  


[1] Soudry, Daniel, et al. "The implicit bias of gradient descent on separable data. (2018)

[2] Jelassi, Samy, and Yuanzhi Li. "Towards understanding how momentum improves generalization in deep learning." (2021).


questions: I would like to raise more technical questions/concerns in this section. 

1) I am concerned by the mix between discrete time and continuous time dynamics in the analysis in Section 4. As mentioned in the paper,  the loss for GDM does not decrease contrary to GD. This is why the authors propose Lemma 1. According to me, this Lemma only holds in the discrete dynamics because when eta ->0, the term (1-C1)*||w(t+1)-w(t)||^2/eta blows up. Do the authors agree with this? If this is the case, then I would like a clarification on how the authors can use the result "||\sum_{t=1}|w(t+1)-w(t)||^2 < \infty" in their proof in continuous time in line 212-213.  [1] does not have this issue with going back and forth between discrete time and continuous time dynamics since the loss is decreasing.

2) The experimental section seems a bit light. I think that it would be a good idea to reproduce the exact same plots as Figure 1 in [1] for GD, GDM and deterministic Adam in the case of ill-posed and well-posed datasets. 

3) Overall, I think that the main concern I have is that we do not really see the difference between all these algorithms that are very different from each other. They indeed all converge to the L2 max margin solution but maybe we may see the benefit of using a 1st or 2nd order momentum in the convergence rate? 



[1] Soudry, Daniel, et al. "The implicit bias of gradient descent on separable data. (2018)

limitations: The authors mentioned the limitations of their approach in conclusion. In particular, they underlined that the gap between their approach and the deep learning setting.
review_title: null

Meta-review: metareview: The reviewers agree that the paper provides a nice technical contribution to understanding the effects of momentum on the generalization error of optimization methods. The results of the paper are solid and interesting, while the presentation is clear and easy to follow.
confidence: Certain
Decision: Accept