Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This manuscript attempts to analyze the asymptotic behavior of heavy-ball method, stochastic gradient with momentum, and an algorithm that combines the heavy-ball method with a coordinate-wise preconditioning similar to that used in Adagrad and Adam for a class of problems that are essentially logistic regression without any regularization, under the assumption that the provided data set is linearly separable.
main_review: The eventual goal of this manuscript (analyzing Adam) is interesting and of importance to some degree. However, the current manuscript seems still a bit far from the final goal as only a deterministic version is analyzed, but such an algorithm is quite meaningless as a deterministic version of Adam is never being used, and using the same name Adam has the suspicion of misleading readers that the stochastic algorithm (as Adam has always been a stochastic algorithm from the beginning, which is also indicated in the title of the original paper of it) is analyzed. Moreover, there are many errors, typos, and undefined symbols in the proof, although most are notational issues that should be easily fixable, I also found that there are crucial errors that invalidate the proofs. In general, viewing from the messiness of the proofs, I would not consider the current manuscript finished, and would like to urge the authors to at least have a thorough check of all their contents before any submission, which should be a minimum common practice.

My major comments are as follows:
1. The whole picture of the manuscript seems to be quite unfocused. If the authors are able to include the analysis of Adam, then surely this is a self-contained story. However, without this piece in the puzzle, the description flow becomes quite divergent and more like just putting all known partial results together to form a paper. Instead, if the manuscript went with either GDM plus SGDM, or GDM plus Eq. (2), the story will look more like a cohesive one.

2. Throughout the manuscript, the authors referred Eq. (2) as Adam. This is very misleading, as Adam is a stochastic algorithm, while (2) is a deterministic algorithm. The analysis of this algorithm is quite meaningless to me, as it is not being used anywhere (although it is analyzed in Wang et al (2021), being analyzed in a theoretical paper only doesn't justify the usefulness of this algorithm). To me, this part of analysis is quite pointless unless it really can lead to any insight for analyzing the original Adam, but this is surely doubtful.
The naming also gives readers the illusion that the real Adam is analyzed and thus falsely boosted the contributions of the manuscript. This obvious limitation is not mentioned at all in the manuscript as well, which is not quite meritorious. If the authors would like to go with the current form, such an incompleteness of their partial results should at least be mentioned in the conclusions.

3. I also found that the proofs contain more than acceptable typos, undefined symbols, and small or huge errors everywhere. I'll list the major ones here and leave the fixable ones to the minor comments.
A. Definition 2:the vector \tilde w is undefined, and so is gamma. The authors also seem to assume gamma = 1 sometimes, but to drop such an assumption sometimes throughout the analysis.
B. Lemma 12: The lines between (15) and (16) are erroneous. The correctness of first inequality (the one before (*)) is unclear to me.
C. Lemma 14: In case 1, the last line of (22) doesn't hold. In particular, on the right-hand side you have O(alpha^2)\|w(t^*+1) - w(t^*)\|^2 (not o(alpha^2) as claimed), while on the right-hand side, the coefficient should actually be O(alpha^2) (instead of small-o) viewing from the previous line. This one is fatal as the same argument is also used in the analysis of SGDM.

Minor comments:
1. The authors are overloading the same symbol for multiple meanings in multiple places, and this is really confusing. For example, c is used in Assumption 2, Lemma 1, and Corollary 2, but they are for different things. There are also inconsistent notations, like sometimes w(1) and sometimes w_0 indicates the initial point.
2. Assumption 2: \ell' > 0 should be \ell' < 0.
3. Lemma 8: \tilde S_s is undefined.
4. Corollary 2: \hat w should be \tilde w.
5. Lemma 10: x_0 should be s_0.
6. Lemma 14: The equality after (**) should be \leq. The next line it should be O(\alpha^2) instead of small-o. The line after (23) has a reference to (by Lemma) without a number.
In case 2: (\dot) should be \leq instead of =. In its previous line, alpha should be alpha^*.
7. Corollary 1: the 2nd equality is wrong. Note that \| \hat w\| = \gamma. All later terms should have \gamma^2 cancelled out.
8. Corollary 4: there are 2 consecutive \infty in the first equation.
9. Lemma 15: we will prove \|r(t)\| is bounded by reduction to absurdity should be by contradiction. In the sequel, a sentence assuming r(t) is unbounded is needed.
10. Lemma 16: The line before (30) is wrong. t^{-1} - log((t+1)/t) = O(t^{-2}) by Taylor's expansion. The equality after (30) wrongly added 1/N to the term of \hat w and led to wrong expressions in all consequential equalities. The last line of this set of equalities missed 1/N for the second inner product.
11. Lemma 3: The equality of (35) should be \leq. The line before (37) misses a \beta^2 in the last term (although (37) is still correct).
12. Lemma 17: In the inequalities after "On the other hand..." , the 3rd line should be using \hat w. The penultimate inequality in the following set of inequalities doesn't seem to be directly interchangeable because the inner one involves the product of 2 sums, but fortunately the final conclusion is still right.
13. Lemma 18: In the equality set before defining A_6 and A_7, 1/b is missing starting from the 3rd line, and \tilde w(t) should be \tilde w. The penultimate line on p. 31 should be 1 - \exp(...). (*) should be \leq instead of =. On the next page, the fact of e^{-x) x \leq e^{-1} is used much earlier at the page top in another set of inequalities, but this is only explained in a later place for another set of inequalities. For the case of r(t)^T \tilde x_i \geq 0, the 2nd inequality should be equality. Here throughout \tilde w(t) should be \tilde w. The line explaining Eq. (\dotp) should be 0.5 - \epsilon instead of 0.5+\epsilon. In the set of inequalities after the line "Specifically, if...", the exponent of t on the right-hand side of the ineq should include min(\mu_-,0.5) instead of just \mu_-. The explanation for the \square doesn't quite make sense to me: -(r(t)+n(t))^T \tilde x_i doesn't seem to approach 0. In the following inequalities, starting from the 4th line, the term of \exp(-(r(t)+n(t))^T \tilde x_i) becomes missing. In the 6th line of the same set of inequalities, +n(t)^T \tilde x_i should be - \mu_- n(t)^T \tilde x_i. I don't see why adding 4  in the exponent of this set of inequalities is needed, seems like the result still holds without this 4.


summary_of_the_review: The manuscript claimed to provide an analysis for Adam but actually didn't and only analyzed a much simplified (non-stochastic) algorithm that is not being used anywhere. The proofs contain many errors and some are vital.

I'd like to thank the authors for a detailed explanation and revising the manuscript.
After the authors' response and revision, I think the proof of lemma 14 is now correct. However, I still think that the analysis of the algorithm described in eq (2) is not very meaningful, as it looks to me more like inventing an algorithm that is not used anywhere and deriving some (however novel or difficult) analysis for it.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper theoretically studies the implicit bias of momentum methods such as GDM/SGDM and Adam under some commonly-used assumptions and shows that momentum doesn't change the implicit bias. One of the main contributions lies on the new theoretical analysis that constructs new Lyapunov functions. 
main_review: This paper provides theoretical results for the implicit bias of momentum methods. This topic is interesting and important. The writing overall is good to me, but there are two comments: the authors should (i) cite paper [1] in the Preliminary section since most contents of this section are borrowed from [1]; (ii) formally define "implicit bias", since it would help general readers to easily understand this paper.  

Although the authors make a contribution in the theoretical side, the theoretical results are still far from many applications in practice since this paper makes many assumptions such linear model, separable data, and smooth loss. I am wondering if some of assumptions such as separable data can be removed? That is to say, if the analysis can be extended to non-separable data?

Comparing with the learning rates for GD [1] and SGD [2], the learning rates in Theorem 2 (for GDM) and Theorem 3 (for SGDM) are smaller respectively, which allows narrower choices of hyper-parameter tuning for learning rate. Does this mean GD/SGD is better than GDM/SGDM? If so, why do we need momentum? 

Although the authors provided the theoretical analysis for the implicit bias of momentum methods, it is strongly recommended and needed that the authors demonstrate their theoretical findings (for example, similar experiments like in [1] and [2]) and compare the momentum methods to other methods such as GD/SGD (for example, different choices of learning rate). The lack of experimental results makes the main contribution of this paper unclear and incomplete.

Reference

[1] The Implicit Bias of Gradient Descent on Separable Data, JMLR 2018

[2] Implicit bias of SGD: Stochastic gradient descent on separable data: Exact convergence with a fixed learning rate, AISTATS 2019
summary_of_the_review: 1. The authors provided new theoretical results for implicit bias of momentum methods.

2. The learning rate of GDM/SGDM is smaller than that of GD/SGD, which allows narrower choices.

3. No numerical results.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The authors study the convergence of stochastic gradient descent momentum (SGDM) in a problem with of binary classification with separable data. 
Interestingly, the authors observed that SGDM and GD converge to the same solution (i.e. the max margin solution) with the same convergence rate O(1/t). 
The paper proposed a variation of [Soudry et al. 2018] solution, that allows for the analysis of the more complex SGDM.
main_review: The main result of the paper that shows the same behavior in (S)GD and SGDM is particularly interesting. However there is incongruence with the result of [Soudry et al. 2018] where the authors showed that Adam does not converge to the L2 max margin. 

The authors need to add "on linearly separable datasets", or some variation, in the title. The title of the paper is extremely misleading and (for what we know) can be false. We do not know whether momentum changes or not the implicit bias in general. 
Both, the title and abstract, do not mention that the analysis is limited to linearly separable binary classification problems. This is deceitful and has to be change. (My current recommendation score is low for this reason.)

In page 6 there are a large number of typos in the equations. The authors should revise. In the equations after "of the dynamic as" there are many "t" that should be replaced by "s" (unless I am mistaken, 3 of them are wrong). The final term dw(1)/dt is imprecise and should be replaced by, dw(t)/dt|_{t=1}. 
At the end of the section, the summatory has a nabla term should not be there. 

I do not have an expertise in this field, therefore it is hard to assess the analysis of the related works nor I can give a comparison with the state of the art. I can observe that citing only 23 papers is strange. For instance, some results that are not reported are: [Neyshabur et al., 2015] that (as far as I know) introduced the concept of implicit bias, [Gunasekar et al 2018] that studied implicit biases for a variety of algorithms, [Mannelli, Urbani 2021] that found a similar conclusion a non-convex task. In general papers in ICLR cite among 40-60 papers, that may be community-dependent, but I would guess that some of the relevant literature have not been cited.

The author should comment on the empirical difference between the speed SGDM with respect to standard SGD. I would be happy to see the result of same simulations. In particular something like figure 3 in [Soudy et al. 2018].
summary_of_the_review: The paper found interesting result that in my opinion are significant. However the paper has two major issues that should be considered before acceptance.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: In this paper the authors analyze the implicit bias of SGD with momentum and ADAM with momentum. For linear classification with exponential-tailed loss and separable data, the authors show that both algorithms converge to the $L_2$ max-margin solution, similarly to vanilla GD.
main_review: I think this is a good paper. Although the model is very simple, the effect of momentum on implicit bias was not analyzed theoretically previously even in such a simple model. 
The authors provide an analysis of SGD and ADAM with momentum using new Lyapunov functions, but I didn't check the proofs thoroughly. 

However, I think the title is quite exaggerated. Claiming that “momentum doesn’t change the implicit bias” based on the simple linear model is not enough, and I think more evidence is needed to state that, at least empirically (e.g. for deep linear networks).
Also, I think it would be good to complement the paper with empirical results, even if some empirical results already appear in previous works. Specifically, since the theoretical results are only for simple linear model, it would be interesting to see empirically the effect of momentum for more complex models, e.g. deep linear/ReLU networks.

Questions:
-	What are the practical implication of the results ?  I think in practice momentum (with good hyperparameters) usually improves generalization, so I would expect that momentum has some effect on the implicit bias (at least in more complex networks).
-	It is shown in Figure 3 of Soudry et al. 2018 that ADAM does not converge to $L_2$ max-margin. This seems to contradict the results for ADAM in this paper. Can you comment on that ? 
-	What is the effect of $\varepsilon$ in ADAM ?

Minor:
it will be good to define “almost every dataset”.

summary_of_the_review: Overall, I think the paper is interesting. The authors push forward the understanding of implicit bias by analyzing the effect of momentum. The tools in this paper might be used to analyze more complex models. Therefore, I recommend for acceptance.
review_title: null

Meta-review: Following a recent line of work on the implicit bias of learning algorithms, the authors consider optimization methods that incorporate momentum. The reviewers found the topic timely and interesting, and generally appreciated the novelty of the technical contributions in the work. However, several critical issues concerning the presentation quality and the positioning of the paper have been raised. In addition, some of the reviewers felt that parts of the paper were somewhat rushed and potentially misleading (mainly, those concerning deterministic\stochastic ADAM and the complexity of the models considered in the paper), and others believed that the experimental section should be made more solid to properly corroborate the theoretical analysis provided in the paper. The authors are encouraged to incorporate the instructive feedback provided by the reviewers in future revisions of the paper.
Decision: Reject