Does Momentum Change the Implicit Regularization on Separable Data?
Authors: Bohan Wang
Qi Meng
Huishuai Zhang
Ruoyu Sun
Wei Chen
Zhi-Ming Ma
Tie-Yan Liu
Venue: NeurIPS 2022 Accept (2022)
Keywords: Implicit Regularization
Momentum-based Optimizers
Optimization

Abstract: The momentum acceleration technique is widely adopted in many optimization algorithms. However, there is no theoretical answer on how the momentum affects the generalization performance of the optimization algorithms. This paper studies this problem by analyzing the implicit regularization of momentum-based optimization. We prove that on the linear classification problem with separable data and exponential-tailed loss, gradient descent with momentum (GDM) converges to the $L^2$ max-margin solution, which is the same as vanilla gradient descent. That means gradient descent with momentum acceleration still converges to a low-complexity model, which guarantees their generalization. We then analyze the stochastic and adaptive variants of GDM (i.e., SGDM and deterministic Adam) and show they also converge to the $L^2$ max-margin solution.  Technically, the implicit regularization of SGDM is established based on a novel convergence analysis of SGDM under a general noise condition called affine noise variance condition. To the best of our knowledge, we are the first to derive SGDM’s convergence under such an assumption. Numerical experiments are conducted to support our theoretical results.

Does Momentum Change the Implicit Regularization on Separable Data?
Bohan Wang*
Qi Meng' Microsoft Research Asia meq@microsofr com
University of Science & Technology of China bhwangfy@gmail.com
Huishuai Zhang
Ruoyu Sun
Microsoft Research Asia huzhang@miccosofft com
The Chinese University of Hong Kong, Shenzhen, China
sunruoyu@cukk.cm edu.cn
Wei Chen
Zhi-Ming Ma
Tie-Yan Liu
Chinese Academy of Sciences chenvei2022@icc.. ac cn
Chinese Academy of Sciences mazm@amt... ac cn
Microsoft Research Asia tyl
com
Abstract
The momentum acceleration technique widely adopted in many optimization algorithms. However, there is no theoretical answer on how the momentum affects the generalization performance of the optimization algorithms. This paper studies this problem by analyzing the implicit regularization of momentum -based optimiza- tion. We prove that on the linear classification problem with separable data and exponential-tan -aaile loss, gradient descent with momentum (GDM) converges to the T,² max-margin solution, which the same as vanilla gradient descent. That means gradient descent with momentum acceleration still converges to low-complexity model, which guarantees their generalization. We then analyze the stochastic and adaptive variants of GDM (i.e., SGDM and deterministic Adam) and show they also converge to the L max-margin solution. Technically, the implicit regular- ization of SGDM is established based on novel convergence analysis of SGDM under a general noise condition called affine noise variance condition. To the best of our knowledge, an assumption. Numerical experiments are conducted to support our theoretical results.
the first to derive SGDM's convergence under such
Introduction
It is widely believed that the optimizers have the implicit regularization in terms of selecting output parameters among all the minima on the landscape 126, 17, 45]. Parallel the analysis of coordinate descent ([31, 40]), [34] shows that gradient descent would converge to the L max-margin solution loss, which mirrors its good generalization
for the linear classification task with exponential-taill property in practice. Since then, many efforts have been taken analyzing the implicit regularization of various local-search optimizers, including stochastic gradient descent [24], steepest descent [8]. AdaGrad [29] and optimizers for homogeneous neural networks [21, 14, 43].
However, though the momentum acceleration technique widely adopted in the optimization algorithms in both convex and non-convex learning tasks [37, 41, 38), the understanding of how
"The work done when Bohan Wang intern at Microsoft Research Asia. Conresponding Authors
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Table 1: The algorithms investigated in this paper (GDM and Adam) along with algorithms (GD) already investigated in the existing literature. We also compare the learning rates required to obtain the characterization of implicit regularization. As for stochastic Adam with B1 * we leave its
implicit regularization as future work.
Method
With Random Sampling
Learning Rate
Corresponding Literature
Constant
[34]
GD
Constant
[24]
Constant
This Work
GDM
Constant
This Work
x
Constant
This Work
Adam
Decaying
v
B1 = 0 in this Work
the momentum would affect the generalization performance of the optimization algorithms is still unclear, as the historical gradients in the momentum may significantly change the searching direction of the optimization dynamics. A natural question is:
Can we theoretically analyze the implicit regularization of momentum-based optimizers?
In this paper, we take the first step to analyze the convergence momentum based optimizers and unveil their implicit regularization. Our study starts from the classification problem with the linear model and exponential-tailed loss using Gradient Descent with Momentum (GDM) optimizer. Then the variants of GDM such as Stochastic Gradient Descent with Momentum (SGDM) and deterministic Adam are also analyzed. We consider the optimizers with constant learning rate and constant momentum byper-parameters, which are widely adopted in practice, e.g., the default setting in popular machine learning frameworks [27] and in experiments [46]. Our main results are summarized in Theorem 1.
Theorem 1 (informal). With linearly separable dataset S, linear model and exponential-tailet loss:
For GDM with a constant learning rate, the parameter norm diverges to infinity, with its direction converging to the I.² max-margin solution. The same conclusion holds for SGDM with a constant learning rate.
For deterministic Adam with constant learning rate and stochastic RMSProp (i.e., Adam without momentum) with decaying learning rate, the same conclusion holds.
Theorem 1 states that GDM and its variants converge the L max-margin solution, which is the same as their without-momentum versions, indicating that momentum does not affect the convergent direction. Therefore, the good generalization behavior of the output parameters of these optimizers is well validated as the margin of a classifier is positively correlated with its generalization error [16] and is supported by existing experimental obscrvations (e.g., [34. 23, 43]).
Our contributions are significant in terms of the following aspects:
We establish the implicit regularization of the momentum bbased optimizers, open problem since the initial work [34]. The momentum-be optimizers are widely used in practice, and our theoretical characterization deepens the understanding of their generalization property, which is important on its own.
Technically, we design two-stage framework analyze the momentum-basee optimiz- ers, which generalizes the proof techniques in [34] and [24]. The first stage shows the convergence of the loss. Specifically, we derive the first convergence analysis of SGDM under affine noise variance condition [2], generalizing the results under bounded noise variance condition literature [47, 20]. The second stage shows the convergence of parameters. We propose an easy-to- to-check condition of whether the difference between learned parameters and the scaled max-margin solution bounded. This condition can be generalized to implicit regularization analyses of other momentum-brrt based optimizers.

---

We further verify our theory through numerical experiments.
The technical difficulty to analyzing the implicit regularization of the momentum-based optimizers mainly come from the historical information of training trajectory contained by the momentum term. Specifically, the foundation of the analysis is to derive the convergence of the loss. It is not trivial because, for momentum-baan based optimizers, the loss may not monotonously decrease due the mismatch between the direction of the gradient and the momentum. Furthermore, even if the loss proved converge, the converging direction of the parameters is still hard to characterize as it's difficult to track the training trajectory due to the momentum term.
Organization of This Paper. Section 2 collects further related works on the implicit regularization of the first-order optimizers and the convergence of momentum-bale basic settings and assumptions which will be used throughout this paper. Section 4 studies the implicit regularization of GDM, while Section 5 and Section 6 explore respectively the implicit regularization of SGDM and Adam. Discussions of these results are put in Section Detailed proof' and experiments can be found in the appendix.
optimizers. Section 3 shows
Further related works
Implicit Regularization of First-order Optimization Methods. [34] prove that gradient descent on linear classification problem with exponential-tailee loss converges to the direction of the max L margin solution of the corresponding hard-margin Support Vector Machine. [24] extend the results in [34] to the stochastic case, proving that the convergent direction of SGD is the same as GD almost surely. [29] go beyond the vanilla gradient descent methods and consider the AdaGrad optimizer instead. They prove that the convergent direction of AdaGrad has dependency on the optimizing trajectory, which varies according to the initialization.
[15] propose a primal-dum analysis framework for the linear classification models and prove faster convergent rate of the margin by increasing the learning rate according to the loss. Based on [15]. [12] design another algorithm with an even faster convergent rate of margin by applying the Nesterov's Acceleration Method the dual space. However, the corresponding form of the algorithm on the primal space is no longer a Nesterov's Acceleration Method nor GDM, which is significantly different from our settings.
On the other hand, another line of work is trying to extend the linear case result to deep neural networks. [13, 9] study the deep linear network and [34] study the two-layer neural network with ReLU activation. [21] propose a framework to analyze the asymptotic direction of GD on homogeneous neural networks, proving that given there exists a time the network achieves 100% training accuracy, GD will converge to some KKT point of the L max- max-margin problem. [43] extend the framework of [21] adaptive optimizers and prove RMSProp and Adam without momentum have the same convergent direction as GD, while AdaGrad does not. The results [21, 43] indicate that results in the linear model can be extended deep homogeneous neural networks and suggest that the linear model is an appropriate starting point to study the implicit bias.
Except for the exponential-taile loss, there are also works the implicit bias with squared loss. Interested readers can refer to [30, 19, 1] etc. for details.
Convergence of Momentum-Bann Bassd Optimization Methods. For convex optimization problems, the convergence rate of Nesterov's 's Acceleration Method [25] has been proved in various approaches (e.g., [25, 35, 44)). In contrast, although GDM (Polyak's Heavy-Ball Method) was proposed in [28] before the Nesterov's 's Acceleration Method, the convergence of GDM on convex loss with Lipschitz gradient was not solved until [7] provides an ergodic convergent result for GDM, i.e., the convergent result for the running average of the iterates. [36] provide non-ergodic analysis when the training loss is cocrcive (the training loss goes to infinity whenever parameter norm goes to infinity), convex, and globally smooth. However, all existing results cannot be directly applied to exponential-taiie loss, which is non-coercive.
There are also works on the convergence of SGDM under various settings. [47] prove SGDM converges to a bounded region assuming both bounded gradient norm and bounded gradient variance. The bounded gradient norm assumption is further removed by [48, 20J. Nevertheless, a converging- to-stationary-pon analysis is required in the implicit regularization analysis. Thus their results can not be directly applied. [39] analyze a particular case when the momentum parameter increases over iterations, which, however, does not agree with the practice where the momentum parameter is fixed.
3

---

As for (stochastic) Adam, its convergence analysis is still an open problem, and the current analyses are restricted specific settings (e.g., bounded gradient, dynamical momentum hyperparameters) We recommend interested readers to refer to [5, 4, 33, 10] for details.
3 Preliminaries
This paper focuses on the linear model with the exponential-tailed loss. We mainly investigate binary classification. However, the methodology can be easily extended to the multi-class classification problem (please refer to Appendix F.3 for details).
Problem setting. The dataset used for training is denoted as S = (æ;; Ui) where æ; E Rd is the i-th input feature, and y/ R is the i-th label (i 1, 1,2,-. 2.2.... .N.. We will use the linear model to fit the label: for any feature x E Rd and parameter w E IRd the prediction is given by (w, x).
For binary classification, given any data 2; (æ; y:) E S, the individual loss for parameter w given as (y: a.:). As only y is used in the loss, we then ensemble the feature and label together and assume y: = 1 (Vi {1, ,N}) without the loss of generality. We then drop y: for brevity and redefine S [x))] The spectral norm of the data matrix (#1, .NN ) defined as
Oman- We use E(w, x) A ((www for brevity.
The optimization target is defined as the averaged loss: L(w) E ((w.w.))
N
Optimizer. Here we will introduce the update rules of GDM, SGDM and deterministic Adam. GDM's update rule is
m(0) = 0, mft = 8mm(t - 1) (1 (1- ())(())))))))))))))))))))))))))) w + 1) = w(t) - (mm
(1)
SGDM can be viewed as stochastic version of GDM by randomly choosing a subset of the dataset to update. Specifically, SGDM changes the update of mt) into
m²t)= Bt 1) + (1 (w))))))
where {(t) is the gradient noise of the t-th step. independent of the randomness of the previous steps and satisfying Eg(e) (L)
((ww). Ye. this paper, {(t) comes from the random sampling of subset B (t) of S with size b (either with replacement (abbreviated as "w/. r"") or without replacement (i.e., with random shuffling, abbreviated as "w/o. r")), and Lς(e) is defined
as Lg(e)(tu (w) = L (w) = Ee k(w.x))
We also define F, as the sub-sigma algebra over the gradient noise collecting randomness before the t-th step. Therefore, w(t) is adapted with respect to the sigma algebra flow F.
The Adam optimizer can be viewed as a variant of SGDM in which the preconditioner is adopted, whose form is characterized as follows:
(0) 0, (t) = fi - +) (1 V
v(0) 0, v(t) = 32 - 1) + (1) 32 @ vL(w(())
ri((() 1- Bi ml()) = 1- 1-93 v(),
(Update Rule): : w(l)= = wi( 1) - Volt + tell
3 mm( - 1),
(3)
is called the preconditioner. where Vott-1)+eh,
Assumptions: The analysis of this paper are based on three common assumptions in existing literature (first proposed by [34]). They are respectively on the separability of the dataset, the individual loss behavior the tail, and the smoothness of the individual loss. We list them follows:
Assumption (Linearly Separable Dataset). There exists one parameter w E Rd, such that
(w, O, Vi (N).
Assumption 2 (Exponential- saileed Loss). The individual loss E is exponential-tailed i.e..
Differentiable and monotonically decreasing to zero, with its derivative converging to zero at positive infinity and to non-zero at negative infinity i.e., limty-soe {(x) = lit ('(x) 0. lim E' (x)x) < O, and El ((xx) <0, Vx R;

---

Close to exponential loss when x is large enough, i.e., there exist positive constants c, C.0,H H-, 2.,, and r-,, such that,
Yr x+ : (x) & c(1 t -e- Vr > z= (x) 2 c(1 - ")
(4)
(5)
Assumption (Smooth Loss). Either of the following assumptions holds regarding the case:
(D): (Without Stochasticity) The individual loss is locally smooth, fer any &u E R, there exists a positive real Hag. such that Vx, y 80, (6' (w)) S Hag y)-
(S): (With Stochasticity) The individual loss is globally smooth, i.e., there exists a positive real H, such that Vx, E R. ( (x:) - (1(()] S H| vl-
We provide explanations of these three assumptions, respectively. Based on Assumption 1, we can formally define the margin and the maximum margin solution of optimization problem:
Definition 1.
Let the margin ((w) of parameter w defined as the lowest score of the prediction of w over the dataset S, i.e., (ww) milles (w, z). We then define the maximum margin solution ii and the L max margin of the dataset S as follows:
i arg min ||
(ww)
[
Since ||- 2|2 is strongly convex and set fw (w)) 1} is convex, ń is uniquely defined.
Assumption 2 constraints the loss to be exponential-tailed, which is satisfied by many popular choices of f, including the exponential loss (x) e)" and the logistic loss (ftog (x) = llog( [ + e e-")). Also, as and a can be respectively absorbed by resetting the learning rate and data as 1 = crj and
a; az; without loss of generality, in this paper we only analyze the case that
1.
The globally smooth assumption (Assumption 3. (S)) strictly stronger than the locally smooth assumption (Assumption 3. (D)). One can easily verify that both the exponential loss and the logistic loss meet Assumption 3. (D), and the logistic loss also meets Assumption 3. (S).
4 The implicit regularization of GDM
In this section, we analyze the implicit regularization of GDM with two-stage framework 3, Later, we will use this framework to investigate SGDM further and deterministic Adam. The formal theorem of the implicit regularization of GDM as follows:
Theorem 2. Let Assumptions 1, 2, and (D) hold. Let 3 E [0, 1) and 1) 2 2 (N (E-1 is the inverse function of E). Then, for almost every data set S, with arbitrary initialization point (1), GDM (Eq. equation 1) satisfies that [[m((t)]
N
||b|]| = [lo//())))) and L(w(()) (
Theorem 2 shows that the implicit regularization of GDM agrees with GD in linear classification with exponential-tailed loss (c.f. [34] for results GD). This consistency be verified by existing and our experiments (c.f. Section for detailed discussions).
Remark (On the hyperparameter setting). Firstly, the learning rate upper bound 2 Fmnn 1NN agrees with that of GD) exactly [34], indicating analysis is tight. Sec- ondly, Theorem adopts a constant momentum
N
which agrees with the practical use (e.g.. [3 is fixed be 0.9 [46]). Also, Theorem 2 puts restriction on the range of B, which allows tuning.
wider choices of
We then present proof sketch of Theorem 2, which is divided into two parts: we first prove that the sum of squared gradients is bounded, which indicates both the loss and the norm of gradient converge to and the parameter diverges to infinity; these properties will then be applied to show the difference between (t) and In (f) is bounded, and therefore, the direction of in dominates as t + co.
'It should be noticed that the proof sketches in Sections 4, 5, and only hold for almost every dataset (means except zero -rr-ure set in gaxN) ), we want the presentation more simple and straightforward. However, the proof can be extended every dataset with careful analysis (please refer Appendix F.I for details).
5

---

Stage I: Loss Dynamics. The goal of this stage is to characterize the dynamics of the loss and prove the convergence of GDM. The core this stage is select a proper potential function E(t), which is required to correlate with the training loss L and be non-increasing along the optimization trajectory. For GD, since L is non-increasing with a properly chosen learning rate, we can pick <(t) = L(t). However, as the update of GDM does not align with the direction of the negative gradient, training loss [(t in GDM no longer monotonously decreasing, and the potential function requires special construction. Inspired by [36], we choose the following E(t):
Lemma 1. Let all conditions in Theorem 2 hold. Define E(t) ((wr(t)+ 1 254
|ln(()) (o]tt-)]]??
Define C1 as positive real with C1 _ mas H (N ((ww))
17. We then have
1- Ci ||w 1) w
E(t) 2 g(t+
(6)
17
Remark 2. Although this potential function is obtained by [36] by directly examining Taylor's 's expansion at wo()) the proof here non-trivial as we only require the loss be locally smooth instead of globally smooth in [36]. We need to prove that the smoothness parameter along the trajectory is upper bounded. We defer the detailed proof to Appendix C.I.I.
By Lemma 1, we have that {(t) is monotonously decreasing by gap 1-G1 |/r + 1) w wt))l
1 As {(1) = ((w((1) is a finite number, we have Σt=1 1| + 1) w()]l < co. By that (1 ())((((((t) (w(t + w(t)) - B(w(() w( 1)), immediately follows that E [VL(w(()) co.
Stage II Parameter Dynamics. The goal of this stage to characterize the dynamics of the parameter and show that GDM asymptotically converges (in direction) to the max- max-margin solution
w. To see this, we define residual term r() _ w(()= In(()r u with some constant vector w (specified in Appendix C. 12). If we can show the norm of r()) is bounded over the iterations, we complete the proof as In(l)w will then dominates the dynamics of w (()..
For simplicity, we use the continuous dynamics approximation of GDM [36] to demonstrate why rl) is bounded:
8 dw((() dw((t) + (()((t)) = 0.
1- 3 dea df
We start by directly examining the evolution of [r,(t),,ic.. i.c.
[ - -11(21)1-== J," ds]r(s))
ds dss
- -f," (ss), vL(w((s) v ds +
9
d (s) ds, d
1- B r(1),
which by integration by part leads to
RHS 1," (MCs)- 1 8 1- (moT),
dw(T) (rO),
dwl(1)
1"²
dr(s)
dw(s)
de
de
ds
ds
We then check the terms one by one:
1f (r(s), V[(w(s)) - ( ds: This term also occurs in the analysis of GD [34], the analysis of which can be generalized as it does not depend on the form of w(s);
(r(T), - dun(T)): as shown in Stage I, dww(T) discrete case) T + cc. Thus, this term is (II)(())lI)
dt - (i.e., uT( w(T - 1) - 0 in the
ST
lي l dw((s) 2ss is finite S(i..,, Ei=1 ||w(t + 1) w(t)ll2 oo in the discrete case) by Stage I, and the mean-value incquality.
dr(s) dw((s) ds: finite due to dr(s) ds
dw((s)
ds
ds
4 'Please note that {() 2 0 regardless of L. 'The derivation of this property in the same manner as in the discrete case: we choose the potential function as E(t) = ((w(t)) + 2(12) || dve(t) l|a. The derivative of ((t) is dg(t)
de (V)((wt))) dwi()) ) + 1 de=
2 w(())
duw(()) de -I| [ww( 1|2. Therefore, E(0) E(1") So duz(1) || 2dt Then, taking T + yields the conclusion.

---

Putting them together, we show that ||r ((]r(T)) is upper bounded over the iterations,
which immediately leads to that [[r( is bounded. Applying similar methodology the discrete update rule, we have the following lemma (the proof can be found in Appendix C.1.2).
Lemma 2. Define potential function z + R as
g(t) - 2 [|](0)
+ 1- (r((), mn(t) w(t 1))- 1))-
g(t) is upper bounded, which further indicates [|((t)] is upper bounded.
Remark 3. Our technique for analyzing GDM here is essentially more complex and elaborate than that for GD in [34] due to the historical information of gradients GDM. The approach in [34] cannot be directly applied. It is worth mentioning that we provide a more easy-to-chede condition for This condition can be generalized for other
whether r(t) is bounded, i.e. "is g(t) momentum-based implicit regularization analyses. E.g., SGDM and Adam later in this paper.
5 Tackle the difficulty brought by random sampling
In this section, we analyze the implicit regularization of SGDM. Parallel to GDM, we establish the following implicit regularization result for SGDM:
Theorem 3. Let Assumption and 3. (S) hold. Let 3 10, and 1
HDo He Then, (1b-(1-) +
25,
with arbitrary initialization point w(1), SGDM (w/. r) satisfies and [(w(t)) O+)), almost surely (a.s.).
wr(t)
T ((1/oo(())
1
Similar to the GDM case, Theorem 3 shows that the implicit regularization of SGDM under this
setting is consistent with SGD (c.f. [24] for the implicit regularization of SGD). This matches the observations in practice (c.f. Section 7 for details), and is later supported by our experiments (e.g.. Figure 1). We add two remarks on the learning rate upper bound and extension to SGDM (w/. r).
Remark (On the learning rate). Firstly, our learning rate upper bound 1/( by²
H3o + Hot
(Nby(1-8)
26
exactly matches that of SGD 2 Hrb maz [24] when 3 0, and matches that of SGD terms of the order of Tmazs H, and b when 33 + 0. This indicates our analysis is tight. Secondly, as the bound is monotonously increasing with respect to batch size b, Theorem 3 also sheds light on the learning rate tuning, ie., the larger the batch size is, the larger the learning rate is.
Remark 5. (On SGDM (w/o. r)) Theorem 3 can be similarly extended to SGDM (w/o. r). We defer the detailed description of the corresponding theorem together with the proof to Appendix F:2.
Next, we show the proof sketch for Theorem 3. The proof also contains two stages, where Stage II is similar that for GDM. However, we highlight that Stage for SGDM is not trivial extension of that for GDM. The methodology used to construct GDM's potential function fails for SGDM: roughly speaking, the change of {()) (defined in Lemma 1) can be spitted into the "decrease term" and the "error term". The "decrease term" comes from the alignment between directions of the update of GDM and the negative gradient, and contributes to the decrease of (t). However, a gap remains between the directions of the update of GDM and the negative gradient. The "error term" measures this gap and potentially contributes to the increase of (t)). For GDM, both the terms are in the order ((w((t) (t))ll while the "decrease term" has larger coefficient, leading to the decrease of ((t). For SGDM, the "decrease term" the order of [E [ un (1) while the "error term" is in the order of (((())((((()))) bigger than the "decrease term" in unbounded magnitude. Therefore, E(t) may no longer decrease. We defer a detailed discussion to Appendix C.2.3.
of V L
On the other hand, we find the stochastic gradient VL (w) is special, in the sense that it satisfies the strong growth condition [32] as follows.
Lemma 3. Let all the assumptions in Theorem 3 hold. Then, for every I (() satisfies the strong growth condition, i.e., Yw, E | (V) s CallV[(w)]I3 where C22 & No?
Nuz. y26
The proof deferred to Appendix B.2. SGD has been known to converge faster when the strong growth condition holds compared to the case when the variance of the stochastic gradient norm is
7

---

bounded [32. 42]. However, to the best of our knowledge, convergence of SGDM under the strong growth condition has not been established. We then bridge this gap by proposing the following theorem.
Theorem 4. Consider SGDM defined in Eq. (2) with general L and E(1). Let V ( satisfy the following properties:
(Affine noise variance condition). Vun Egce)) V (we)) S /VV[[[(()) + 00.
(Bounded smoothness condition). Vwn, u2, [[((w) vL(w>)]l S L||wi w2ll
Then, with learning rate 1j S
we have
2 +Lo.
VL(ww(t)) S
+ O(noo).
T
Tn
To the best of our knowledge, Theorem 4 is the first establish the convergence of SGDM under the affine noise variance condition [6]. which generalizes the strong growth condition and the bounded gradient variance condition. Note that the affine noise variance condition with du 0 is exact the strong growth condition, in which case Theorem shows that Σ ((w((())))) decays with rate Tr. Combining Lemma 3 and Theorem 4 completes the proof of Stage I for SGDM.
We then briefly state the proof idea of Theorem 4. Inspired by SGD's s simple update rule, we rearrange the update rule of SGDM such that only the gradient information of the current step contained, i.c.,
( + 1) - Bw(l) w(l) fw(( 1) n/ (e(o)(((t))
1 1- 8
By defining utt) A w(t) (w(t)-8((t-1) wtt + 1 (w(() w(t 1)), we have that u(t) is close to (t)) (differs by order of one-step update wt() - wi( - 1)), and the update rule of ut)) only contains the current-step-geee ste-ggrdett information V (ww(())) We then select potential function as (f)()). and
1-3
simple Taylor's expansion directly leads to:
B[C(u(t+ 1)) = [(u(t)) n(VL(w(t)) Vl(u(t))) L(u(t)) (()((
ie.. L(u(t)) is a proper potential function. Summing the above equation across iterations completes the proof.
Analyze the effect of preconditioners
6.1 Implicit regularization of deterministic Adam
This section presents the implicit regularization of deterministic Adam, i.c., Adam without random sampling.
Theorem 5. Let Assumption 1, 2, and 3. (D) hold. Let > 82 3 O, and the learning rate n) is small enough constant (The upper bound of learning rate is complex, and we defer it to Appendix D. Then, with arbitrary initialization point w(1), deterministic Adam (Eq. 3) satisfies
that
wi(t) Tw[ti]|
[
O(1/ log(()) and [(w((t)= = O
Remark (On the 31 and 82 range). Almost all existing literature assume a time-decaying hyper- parameter choice of B1 32 (c.f., [18, 3J). On the other hand, our result proves that deterministic Adam converges with constant settings of 31 and 32, which agrees with the practical use.
Remark 7 (DDisuussion on the results in [34])). [34] observe that, on synthetic dataset, the direction of the output parameter by Adam still does not converge to the max-margin direction after 2 x 106 iterations (but is getting closer). At the same time, GD seems to converge to the max-margin direction. However, this example does not contradict Theorem 5, as we study the asymptotic behavior. In the example, it can be observed that the angle gap keeps decreasing after 10S iteration, which stands with our result. Furthermore, in Figure 3 and 4 of our paper, reproduce the experiment and find that the angle gap still keeps decreasing after extending the training time. Secondly, this synthetic dataset is ill ill-posed, which has large singular value and makes the training rather slow, and it can be
8

---

observed that the training loss of Adam does not vary much until 10* iteration. On the well- well-posed dataset adopted by (Figure 1, [34]). we observe that Adam will converge to the max-margin solution rapidly (please refer to Figure I for details).
We simply introduce the proof idea here and put the full proof in Appendix D. The proof of determin- istic Adam is very similar to that of GDM with minor changes in potential functions. Specifically. <(t)
in Lemma is changed to E(L) - [(w(()) + mL Vella
1-8
D(1 1) @ (wr(1) - wo(1 - 1))11.
and g(t) in Lemma 2 is changed to
ptt (w(()- w(t 11)) 1- B1 + Ve |r())).
s(t) - (1-
2
The rest of the proof then flows similarly to the GDM case.
6.2 What if random sampling is added?
We have obtained the implicit regularization for GDM. SGDM, and deterministic Adam. One may wonder whether the implicit regularization of stochastic Adam can be obtained. Unfortunately, the gap can not be closed yet. This is because an implicit regularization analysis requires the knowledge of the loss dynamics, little of which, however, has been ever known even for stochastic RMSProp (i.e., Adam with 31 in Eq. (3)) with constant learning rates. Specifically, the main difficulty lies in bounding the change of conditioner
across iterations, which is required to make the Vsl++0(1)
drift term (V (t).. E(w(t 1) w(t))) (derived by Taylor's expansion of the epoch start from K't) negative to ensure non-increasing loss.
On the other hand, if we adopt decaying learning rates T) " [33] shows
32 close enough to 1, the
following equation holds for stochastic RMSProp (w/o. r) (recall that K N is the epoch size)
T Σ A=0
(V (w (Kt))l (lnT).
(8)
Based on this result, we have the following theorem for stochastic RMSProp (wlo. r):
Theorem 6. Let Assumptions 1, 2, and 3. (S) hold. Let B2 be close enough to 1. Then, with arbitrary initialization point w(1) and decaying learning rate mt V/ stochastic RMSProp satisfies
(1) (
ab
|| = /lo((t)))))))))))))))))))))))/ and L(w((t) = -0 (2)))
|لقق||
Remark 8 (On the decaying learning rate). The decaying learning rale is a "stronger" setting compared to the constant learning rate, both in the sense that GDM, SGDM, and deterministic Adam can be shown to converge to the max-margin solution following the same routine as Theorems 2, 3, and 5, and in the sense that we usually adopt constant learning rate in practice.
The proof is on the grounds of novel characterization of the loss convergence rate derived from Eq. (8), and readers can find the details in Appendix E.
(a) Margin Gap
(b) Angle gap
(c) Norm
(d) Loss
Figure 1: Comparison of the implicit regularization of the optimizers. We use the synthetic dataset in [34] with learning rate _/-- Figure (b) shows (1). all the optimizers converge to the margin solution, and (2). the asymptotic behaviors with & without momentum are similar. The experimental observation support our theoretical results.

---

7 Discussions
Consistency with the Experimental Results. We conduct experiments to verify our theoretical findings. Specifically, we (1). run GD, GDM, SGD, SGDM, and Adam on synthetic dataset to observe their implicit regularization; (2). run GD and Adam on ill-posed dataset proposed in [34] to verify Theorem 5; (3). run SGD and SGDM on neural networks to classify the MNIST dataset and compare their implicit regularization. The experimental observations stand with our theoretical results. Furthermore, it is worth mentioning that experimental phenomenons that adding momentum will not change the implicit regularization have also been observed by existing literature [34, 23, 43).
Influence of hyperparameters on convergence rates. Our results can be further extended to provide precise characterization of the influence of the hyperparameters 7) and 3 the convergence rate of (S)GDM. Specifically, in Appendix F.4, we show that the asymptotic convergence rate of (S)GDM C where C is some constant independent of 3 and 1). Therefore, increase 1) can lead to a faster convergence rate (with learning rate requirements in Theorems 2 and 3 satisfied). However, changing 33 does not affect the convergence rate, which is also observed in our experiments (e.g.. Figure 1). Furthermore, to the best of our knowledge, there still lacks the theoretical justification of the acceleration effect of the momentum except the strongly convex case. On the other hand, we still can not provide a precise characterization of the exact convergence behavior of Adam in this case due to the ever-changing preconditioner. As this work mainly focuses on the linear model, whether momentum and preconditioner can accelerate the training of non-linear model with the non-convex landscape is exciting future direction and deserves further investigation.
Generalization Behavior of Adam. Our results characterize the implicit regularization behavior of optimizers when the time is large enough, which can be changed by early stopping, especially for Adam. This because the proof of Theorem relies on that when the training time large enough, the gradient is small and the adaptive learning rate Vu(t)+=1a is dominated by _ 1 and then Adam
behaves like GDM and thus converges the max margin solution. This also be verified by Figure 1, as the angle gap of deterministic Adam and RMSProp only start to decrease late in the training.
Gap Between The Linear Model and Deep Neural Networks. While our results only hold for the linear classification problem, extending the results to the deep neural networks is possible. Specifically, existing literature [21, 43] provide framework for deriving implicit regularization for deep homogeneous neural networks. However, the approach in [21, 43] can not be trivially applied to the momentum-basee based optimizers, lower bound a smoothed margin (c.f., Theorem 4.1, [21]). remains an exciting work to see how our results can be expanded to GDM and Adam for deep neural networks.
their proofs require the specific gradient- gradient-based updates to
8 Conclusion
This paper studies the implicit regularization of momentum-basee optimizers in linear classification with exponential-tail loss. Our results indicate that for SGD and the deterministic version of Adam, adding momentum will not influence the implicit regularization, and the direction of the parameter converges the 2 max margin solution. Our theoretical results stand with existing experimental observations, and developed techniques such as the potential functions may inspire the analyses on other momentum based optimizers. Motivated by the results and techniques for linear cases in this paper, it has the potential to extend them to the homogeneous neural network in the future. Another topic left for future work to derive the implicit regularization of constant learning rate stochastic Adam. As discussed in Section 6.2, this topic is non-trivial, and it requires new techniques and assumptions to be developed.
Acknowledgement
This research is supported in part by CAS Project for Young Scientists in Basic Research under Grant No. YSBR-034 and Innovation Project of ICT CAS under Grants No. E261090.
10

---

References
[1] A. Ali, Dobriban, and Tibshirani. The implicit regularization of stochastic gradient flow for least squares. In International Conference Machine Learning, pages 233-244, PMLR, 2020.
[2] L. Bottou, F. E. Curtis, and J. Nocedal. Optimization methods for large-scale machine learning. Siam Review, 60(2):223-311, 2018.
[3] X. Chen, S. Liu, R. Sun, and M. Hong. On the convergence of class of adam-type algorithms for non-convex optimization. In International Conference on Learning Representations, 2018.
[4] S. De, A. Mukherjee, and E. Ullah. Convergence guarantees for rmsprop and adam in non- convex optimization and an empirical comparison nesterov acceleration. arXiv preprint arXivv1807.06666 2018.
[5] A. Défossez, L. Bottou, F. Bach, and N. Usunier. A simple convergence proof of adam and adagrad. arXiv preprint arXiv:2003.00 02395, 2020.
[6] M. Faw, I. Tziotis, C. Caramanis, A. Mokhtari, S. Shakkottai, and R. Ward. The power of adaptivity in sgd: Self-tuning step sizes with unbounded gradients and affine variance. arXiv preprint rrXiv:2202.05791, 2022.
[7] E. Ghadimi, R. Feyzmahdavian, and M. Johansson. Global convergence of the heavy-ball method for convex optimization. In 2015 European control conference (ECC), pages 310-315. IEEE, 2015.
[8] S. Gunasckar, J. Lee, D. Soudry, and N. Srebro. Characterizing implicit bias in terms of optimization geometry. In International Conference Machine Learning, pages 1842-1841. PMLR, 2018
[9] S. Gunasekar, J. D. Lee, D. Soudry, and N. Srebro. Implicit bias of gradient descent on linear convolutional networks. In Advances in Neural Information Processing Systems, pages 9461-9471, 2018.
[10] Z. Guo, Y. Xu, W. Yin, R. Jin, and T. Yang. A novel convergence analysis for algorithms of the adam family. arXiv preprint arXiv:2112.034599 2021.
[1]] S. Jelassi and Y. Li. Towards understanding how momentum improves generalization in deep learning. In International Conference on Machine Learning, pages 1005-00040. PMLR, 2022.
[12] Z. Ji, N. Srebro. and M. Telgarsky. Fast margin maximization via dual acceleration. In International Conference on Machine Learning, pages 4860 PMLR, 2021.
[13] Z. and M. Telgarsky. Gradient descent aligns the layers of deep linear networks. arXiv preprint arXiv: 18000003,, 2018.
[14] 7. Ji and M. Telgarsky. Directional convergence and alignment in deep learning. arXiv preprint arXiv:2006.. 06650,667777 2020.
[15] Z. Ji and M. Telgarsky. Characterizing the implicit bias via primal-dual analysis. In Algorithmic Learning Theory, pages 772-801 804. PMLR, 2021.
[16] Y. Jiang, B. Neyshabur, H. Mobahi, D. Krishnan, and S. Bengio. Fantastic generalization measures and where to find them. arXiv preprint arXiv:1912.00 178, 2019.
[17] N. S. Keskar, D. Mudigere, J. Nocedal, M. Smelyanskiy, and P. T. P. Tang. On large-batch training for deep learning: Generalization gap and sharp minima. In International Conference on Learning Representations, 2017.
[18] D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6982 2014.
[19] Lin and L. Rosasco. Optimal rates for multi- pass stochastic gradient methods. The Journal of Machine Learning Research. 18(1):3375-344 3421, 2017.
[20] Y. Liu, Y. Gao, and W. Yin. An improved analysis of stochastic gradient descent with momentum. Advances in Neural Information Processing Systems, 33, 2020.
[21] K. Lyu and J. Li. Gradient descent maximizes the margin of homogeneous neural networks. arXiv preprint arXiv: 058900 2019.

---

[22] A. Madry, A. Makelov, L. Schmidt, D. Tsipras, and A. Vladu. Towards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations. 2018.
[23] M. S. Nacson, J. Lee, S. Gunasckar, P. H. P. Savarese, N. Srebro, and D. Soudry. Convergence of gradient descent separable data. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 3420-3428. PMLR, 2019.
[24] M. S. Nacson, N. Srebro, and D. Soudry. Stochastic gradient descent on separable data: Exact convergence with fixed learning rate. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 3051-3059 PMLR, 2019.
[25] Y. Nesterov. A method for solving a convex programming problem with convergence rate (1/k2). In Soviet Mathematics. Doklady, volume 27, pages 367-372, 1983.
[26] B. Neyshabur, R. Tomioka, and N. Srebro. In search of the real inductive bias: On the role of implicit regularization in deep learning. In ICLR, 2015.
[27] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury. G. Chanan, T. Killeen, Z. Lin,
N. Gimelshein, L. Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems, 1188026-8077 2019.
[28] B. T. Polyak. Some methods of speeding up the convergence of iteration methods. Ussr computational mathematics and mathematical physics, 4(5):1-17, 1964.
[29] Q Qian and X. Qian. The implicit bias of adagrad on separable data. In Advances in Neural Information Processing Systems, pages 7761-7769, 2019.
[30] L.. Rosasco and S. Villa. Learning with incremental iterative regularization. In Proceedings of the 28th International Conference on Neural Information Processing Systems- Volume I, pages 1630-1638, 2015.
[31] R. Schapire and Freund. Boosting: Foundations and algorithms. Kybernetes, 2013.
[32] M. Schmidt and N. L. Roux. Fast convergence of stochastic gradient descent under a strong growth condition. arXiv preprint arXiv: 2013.
[33] N. Shi, D. Li, M. Hong, and R. Sun. Rmsprop converges with proper hyper-parameter In International Conference on Learning Representations, 2021.
[34] D. Soudry, E. Hoffer, M. S. Nacson, S. Gunasekar, and N. Srebro. The implicit bias of gradient descent on separable data. The Journal of Machine Learning Research, (9(1):28222887) 2018.
[35] W. Su, S. Boyd, and E. Candes. A differential equation for modeling nesterov's 's accelerated gradient method: theory and insights. Advances in neural information processing systems, 27, 2014.
[36] T. Sun, P. Yin, D. Li, C. Huang, L. Guan, and H. Jiang. Non-ergodic convergence analysis of heavy-ball algorithms. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 5033-503444 2019.
[37] I. Sutskever, J. Martens, G. Dahl, and G. Hinton. On the importance of initialization and momentum in deep learning. In International conference on machine learning, pages 1139- 1147. PMLR, 2013.
[38] M. Tan and Q Le. Efficientnet: Rethinking model scaling for convolutional neural networks. In International Conference Machine Learning, pages 6105-6114, PMLR, 2019.
[39] W. Tao, S. Long, G. Wu, and Q. Tao. The role of momentum parameters in the optimal convergence of adaptive polyak's 's heavy-ball methods. arXiv preprint arXiv:2102.07311 2021.
[40] M. Telgarsky. Margins, shrinkage, and boosting. In International Conference Machine Learning, pages 307-315. PMLR, 2013.
[41] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, Ł. Kaiser, and
I. Polosukhin. Attention is all you need. In Advances in neural information processing systems, pages 5998-6008, 2017.
[42] S. Vaswani, F. Bach, and M. Schmidt. Fast and faster convergence of sgd for peerpaaraeterrized models and an accelerated perceptron. The 22nd international conference on artificial intelligence and statistics, pages 1195-1204. PMLR, 2019.
12

---

[43] B. Wang, Q. Meng, W. Chen, and T.-Y. Liu. The implicit bias for adaptive optimization algorithms on homogeneous neural networks. International Conference Machine Learning. pages 10849- 10858. PMLR, 2021.
[44] A. C. Wilson, B. Recht, and M. I. Jordan. A Iyapunov analysis of accelerated methods in optimization. Journal of Machine Learning Research, 22(113):1-34, 2021.
[45] A. C. Wilson, R. Roelofs, M. Stem,, N. Srebro, and B. Recht. The marginal value of adaptive gradient methods in machine learning. Advances in neural information processing systems, pages 4148 4158, 2017.
[46] S. Xie, R. Girshick, P. Dollár, 7. Tu, and K. He. Aggregated residual transformations for deep neural networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 1492-1500, 2017.
[47] Y. Yan, T. Yang, Z. Li, Q. Lin, and Y. Yang. A unified analysis of stochastic momentum methods for deep learning. In IJCAI International Joint Conference on Artificial Intelligence, 2018.
[48] H. Yu, R. Jin, and S. Yang. On the linear speedup analysis of communication efficient momentum sgd for distributed non-convex optimization. In International Conference on Machine Learning, pages 7184-7193. PMLR, 2019.
[49] D. Zou, Y. Cao, Y. Li, and Q Gu. Understanding the generalization of adam in learning neural networks with proper regularization, arXiv preprint arXiv:2108. 11371, 2021.
13


Reviews:
[{"review_id": "xQriWgjTtY-", "reviewer": "Reviewer_wavj", "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. ", "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?\n- Please see my questions for line 208-213 in the \"strengths and weakness\" section.", "limitations": "This paper has no potential negative societal impact.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.\n\nSome concern:\n- 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?\n- 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.\n\nMinor:\n- $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.\n- Line 14, Numerical experiments are conducted and support -> Numerical experiments are conducted to support …\n- Line 57, parameter -> parameters\n- Line 63, first order -> first-order\n- Line 95, Interesting -> interested\n- Line 195, better to mention that $\\inf \\xi(t) > -\\infty$\n\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "gmJ8vhBfk2", "reviewer": "Reviewer_HjYT", "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).", "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?\n\n2. What happens if we consider early stopping?\n\n3. 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.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Overall, the strengths of this paper are clearly stated in the paper:\n\n1. This paper first proves the implicit regularization of momentum-based optimizers. \n2. A new proof technique is developed for studying the algorithmic behavior when momentum is involved, which is of independent interest.\n\nThe weaknesses are as follows:\n\n1. 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)?\n\n2. 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.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "8opZc9Lb7QY", "reviewer": "Reviewer_zpTJ", "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.\n\n\n\n\n\n[1] Soudry, Daniel, et al. \"The implicit bias of gradient descent on separable data. (2018)", "questions": "I would like to raise more technical questions/concerns in this section. \n\n1) 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.\n\n2) 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. \n\n3) 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? \n\n\n\n[1] Soudry, Daniel, et al. \"The implicit bias of gradient descent on separable data. (2018)\n", "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. ", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I summarize as follows the strengths and weaknesses of this paper.\n\nStrengths: 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. \n\nWeaknesses: 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.\n\nAnother 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. \n\nI 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.  \n\n\n[1] Soudry, Daniel, et al. \"The implicit bias of gradient descent on separable data. (2018)\n\n[2] Jelassi, Samy, and Yuanzhi Li. \"Towards understanding how momentum improves generalization in deep learning.\" (2021).\n\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "4tt5cfyPaj", "reviewer": "Reviewer_wZ1t", "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. ", "questions": "There are a number of works studying the generalization error of gradient descent with momentum / Adam:\n\nJelassi, Samy, and Yuanzhi Li. \"Towards understanding how momentum improves generalization in deep learning.\" (2021).\n\nZou, 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).\n\nIt would be very helpful if the authors can discuss the relation between the implicit bias results with these previous works.\n", "limitations": "This paper does not have any potential negative societal impact.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n\nThe results of the paper are solid and interesting. \n\nThe presentation of the paper is clear and easy to follow.\n\nThe authors give a fairly comprehensive analysis of implicit bias in different settings.\n\nWeaknesses: \n\nAlthough 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.\n\nThe experiments are mostly deferred to the appendix, and Figure 1 in the main part of the paper does not seem very convincing. \n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept