Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper provides a new analysis for implicit regularization for the heavy ball momentum gradient descent. The paper shows that the momentum updates for gradient descent and its stochastic counterpart are closer to the modified regularized gradient flow than previously known. Their analysis is based on studying a piecewise first order ODE, as opposed to a second order ODE analysis that was undertaken by a previous work which makes the crucial difference in the final results. 
strength_and_weaknesses: Strengths:

- The paper explains the setup well, explains the implicit regularization effect due to the closeness to the modified flow, and also why the modified flow is suited for better generalization which helps in a lot in getting a complete picture of the impact of this work.
- The variance reduction effect of momentum in SGD is one of the most interesting aspects of the presented analysis. The authors have made relevant comments how the overall generalization is likely due to a combination of various factors including variance, stability and the contributing implicit regularization. The effect of variance, for example, still requires further imho even though there are a couple of studies cited in this work that talk about how smaller variance can lead to bad local minima. 
- The relevant literature is well-cited and well discussed, mentioning key contributions and how they relate to this paper. 
- The empirical section is largely sufficient and complements the theoretical contributions well. 

Weaknesses: 
- I had a hard time reading the paper the first time mostly because I had to wait till eq 6 on page 4 before finally understanding and appreciating what O(h^2) closeness means and why that is important, even though the authors use it freely starting from right in the abstract. I suggest the authors consider re-wording this. I have not read all the related works cited in this paper, so I am not sure if it is a common jargon used in this community, but nevertheless it makes the paper a lot harder to read for more general audience. 
- Is there a reason why the authors used only the simple linear 2layer model to illustrate the IGR effect in Sec 4.1, especially considering that they have mentioned earlier in the paper about jelassi and Li 2022 not applicable to more general NNs? I understand they reproduced the setting of Barrett and Dherin 2020 but it would have been interesting to see a non-linear activation. Nevertheless, this is not a deal-breaker since the stability and full-batch experiments complement the theoretical contributions well. 



clarity,_quality,_novelty_and_reproducibility: - The paper is largely clearly written, minus the early focus on O(h^2) that I have talked about in weaknesses. 

- The result and the analysis is novel and original as far as I know. However, I have not gone through all the proofs. 

- The authors have provided the code for their experiments, and from the presented experiments, I dont see an obvious problem with reproducibility. 
summary_of_the_review: The paper makes a non-trivial contribution to the field and should be of interest to the community. The result demonstrating the regularizing effect of heavy ball in both the classical gradient descent and the stochastic settings is interesting, and so is the presented analysis.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper studies the implicit regularization effect in GD and SGD methods with momentum. It quantifies the regularization effect when algorithms take heavy-ball momentum step with a parameter beta, which partially explains the generalization ability and why momentum helps GD and AGD to find flatter minima. The authors also corroborate their findings with some empirical results.
strength_and_weaknesses: The paper has a strong motivation, clean exposition and nice writing. I think it answers the very interesting problem of implicit regularization effect of momentum steps from one perspective, which may have positive effects on future work toward a more complete understanding of implicit regularization and acceleration. The following parts could be improved a bit more:

1) The theoretical part seems to suggest the parameter beta of heavy-ball momentum shall be set to as high as possible, since then it leads to both faster convergence and better generalization. This I feel may be counter-intuitive to observations in practice. While the authors did try to touch upon such concerns in last sentences of Section 4, it may be helpful to particularly touch upon that point and how the theory guide practical choice of beta in more detail.

2) The convergence rate difference of 1/(1-beta) factor seems to be somewhat different from the classic square root speedup for Polyak's momentum method in convex optimization. Is there a good intuition explaining why this is true?

3) The sharpness and "edge of stability" explanation on middle of page 7 seems a bit hand-wavy. It might be helpful to elaborate in a bit more detail why this means (GD+M) shall potentially have worse test accuracy.


clarity,_quality,_novelty_and_reproducibility: The paper is well-structured and well-motivated, and a pleasant to read. The high-level approach follows prior works' analysis but there are some novel idea to get around the difficulty in directly extending. Some part of the writing feels a little less rigorous and a better balance between explaining intuition and providing rigor derivations may be helpful.
summary_of_the_review: I like the problem it studies and the perspective it takes. With some efforts the exposition can be made better and I'd be happy to re-evaluate once my concerns have been properly addressed.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This work studies the generalization performance of momentum methods (GD+M, SGD+M) through the lens of implicit gradient regularization (Barrett & Dherin, 2020). The authors show that the effect of momentum can be understood as stronger implicit gradient regularization + stronger variance reduction (compared with GD/SGD using the same effective learning rate), and verify their claim with numerical justifications. These results provide a deeper understanding of the mechanism of momentum and some promising future directions (such as combining implicit gradient regularization with noise injection).
strength_and_weaknesses: This is a very interesting work, which extends the idea of implicit gradient regularization (IGR) (Barrett & Dherin, 2020) to explain the effect of momentum in GD/SGD. The theorems explain the empirical observation that with the same effective learning rate, the convergence of GD/SGD is more unstable (has larger variance) than GD+M/SGD+M. And also the experiments in (Ma, J., & Yarats, D., 2018) which fixed the effective learning rate, although they used Nesterov's momentum (maybe IGR can also be used to study Nesterov's momentum? or even QHM?). The authors give very detailed discussion and insights about the theorems, which I found very nice. I didn't check all the proofs, but they looks correct. 

Section 7 points out another very interesting topic, though without empirical verifications. From my perspective, the current contribution is sufficient for acceptance. I think it would be interesting to also discuss the effect of learning rate schedulers. The authors mentioned that the IGR term will get very weak when converging, and thus the generalization performance of GD/SGD and GD+M/SGD+M might be similar in this case. This can be observed in (Ma, J., & Yarats, D., 2018) for NAG and SGD after learning rate reductions. I think that the IGR is a powerful tool, and that the authors are moving in the correct direction using it to understand NN optimizers.



(Ma, J., & Yarats, D., 2018)  Ma, J., & Yarats, D. (2018). Quasi-hyperbolic momentum and Adam for deep learning. In International Conference on Learning Representations.
clarity,_quality,_novelty_and_reproducibility: This work is generally well-written and has a nice flow of ideas.

Some typos:
- Mismatched parentheses: Theorem 4.1. ((IGR-M) ; Equation (11)
- Remark 5.4, adjusted learning rate -> effective learning rate
- Section 6, (GD+M) performed for various β with a fixed step-size h − 0.1, -> h = 0.1

summary_of_the_review: This work explains the effect of momentum using the idea of implicit gradient regularization (IGR). The theorems nicely explain several empirical differences between GD/SGD and GD+M/SGD+M. I believe that the IGR has the potential to explain more NN optimizers, and thus the authors are heading in the correct direction. I vote for acceptance.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper uses a classical tool in numerical analysis, namely modified equation, to account for the effect of small but finite learning rate used in (stochastic) gradient descent with momentum. As a result of this analysis and as a standard treatment, the continuous time limit of the optimizer, which is an ODE, will have additional O(h) term(s), which can then be employed to characterize the optimizer’s implicit bias. This paper investigates in such correction term(s) and shows that the momentum parameter also affects the strength of the implicit regularization. Empirical discussions and experiments are also provided.
strength_and_weaknesses: Strength:

(1) the problem considered is of critical importance to machine learning.

(2) working out the algebra to quantify the role of momentum variable is nice.

(2) the empirical discussions and experiments are interesting.

Weakness:

(1) Modified equation for SGD with momentum, unlike suggested, has already been studied in details. See for instance [Li et al. Stochastic modified equations and adaptive stochastic gradient algorithms. 2017] for a short version and [Li et al. Stochastic modified equations and dynamics of stochastic gradient algorithms i: Mathematical foundations. 2019] for a long version where the validity of modified equation, which is otherwise just a formal result, is actually rigorously quantified. 

(2) In addition, unlike the aforementioned results, the derivation of modified equation in this paper is only formal. In fact, the formal asymptotic expansion used for deriving modified equation will blow up once h becomes not that small. This problem is already starting to be addressed by the more recent literature, such as [Wang et al. Large Learning Rate Tames Homogeneity. 2021].

(3) The main results, Theorem 4.1  and 5.1, are just short time results, meaning $T$ is fixed in Theorem 4.1 and $n \leq T/h$ for fixed $T$ in Theorem 5.1. The derivation is based on standard (but still nice) numerical analysis, which in fact requires $T$ to be O(1) (i.e. small) in order for the hidden constants in the error bounds to be not exponentially large. This limits the applicability of the results to practical training, unless the setup is more specific so that early stopping becomes reasonable or necessary.

In terms of actions, it would be great if the above are at least fairly discussed in the paper.

clarity,_quality,_novelty_and_reproducibility: This paper is generally speaking written with good clarity. 

Regarding originality, I’d like to hear from the authors about the above before making a final assessment. 

In terms of quality, I also have an additional question, which I did not count as weakness: on page iii, is it really necessary to involve PAC-Bayes? Can one directly say something about the landscape? Note that Hessian (and thus flatness) has already been quantitatively related to hyperparamters in, e.g., [Bock & Weiß. Local Convergence of Adaptive Gradient Descent Optimizers. 2021] and [Wang et al. Large Learning Rate Tames Homogeneity. 2021], and while I understand the setups may be slightly different, I wonder if the same technique of local stability analysis cannot be applied.
summary_of_the_review: This paper is considering an interesting problem from a nice quantitative perspective. However, before I can better understand the innovation, I’m afraid I cannot give a very positive recommendation.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper studies the implicit bias of SGD with a specific type of momentum, showing that as the step size is taken to zero, the updates are close to an ODE on a modified loss function.  This is an interesting perspective on momentum, and combined with the positive reception by the reviewers, I feel this is a clear accept.
justification_for_why_not_higher_score: This is a nice paper, but the bar for oral is very high.
justification_for_why_not_lower_score: Calibrated according to my other meta-reviews, this paper has an interesting perspective on a problem that has not been considered before (afaik), and the reviewer reception overall is positive.
Decision: Accept: notable-top-25%