Momentum Doesn't Change The Implicit Bias
Authors: Bohan Wang
Qi Meng
Huishuai Zhang
Ruoyu Sun
Wei Chen
Zhi-Ming Ma
Venue: ICLR 2022 Submitted (2022)
Keywords: Momentum-based Optimizers
Convergence Analysis
Implicit Bias

Abstract: The momentum acceleration technique is widely adopted in many optimization algorithms. However, the theoretical understanding on how the momentum affects the generalization performance of the optimization algorithms is still unknown. In this paper, we answer this question through analyzing the implicit bias of momentum-based optimization. We prove that both SGD with momentum and Adam converge to the $L_2$ max-margin solution for exponential-tailed loss, which is the same as vanilla gradient descent. 
That means, these optimizers with momentum acceleration still converge to a model with low complexity, which provides guarantees on their generalization.  Technically, to overcome the difficulty brought by the error accumulation in analyzing the momentum, we construct new Lyapunov functions as a tool to analyze the gap between the model parameter and the max-margin solution.

Under review as a conference paper at ICLR 2022
DOES MOMENTUM CHANGE THE IMPLICIT BIAS ON SEPARABLE DATA?
Anonymous authors Paper under double-blind review
ABSTRACT
The momentum acceleration technique widely adopted in many optimization algorithms. However, the theoretical understanding on how the momentum affects the generalization performance of the optimization algorithms is still unknown. In this paper. answer this question through analyzing the implicit bias of momentum-bant -base optimization. We prove that on the linear classification problem with separable data, both SGD with momentum and Adam (without stochasticity) converge to the L2 max-margin solution for exponential-taiie same vanilla gradient descent. That means, these optimizers with momentum ac- celeration still converge to model with low complexity, which provides guarantees on their generalization. Technically, overcome the difficulty brought by the error accumulation in analyzing the momentum, we construct new Lyapunov functions as tool to analyze the gap between the model parameter and the max-margin solution.
loss, which is the
INTRODUCTION
is widely believed that the optimizers have implicit bias in terms of selecting output parameters among all the local minima on the landscape (Neyshabur et al., 2015; Keskar et al., 2017; Wilson al., 2017). It shown in the analysis of Adaboost that the coordinate descent would converge to the L mmax-marii solution for the linear classification task with exponetial-taiie & Freund, 2013; Telgarsky, 2013)). Latter, Soudry et (2018) shows that gradient descent would converge to the L max-margin solution under the same setting, which mirrors its good generalization property in practice. Since then, many efforts have been taken on analyzing the implicit bias of various local-search optimizers, including stochastic gradient descent (Nacson al., 2019), steepest descent (Gunasekar et al., 2018a), AdaGrad (Qian & Qian, 2019) and optimizers for homogeneous neural networks (Lyu & Li, 2019; Ji & Telgarsky, 2020; Wang al., 2021).
loss ((Schapire
However, though the momentum acceleration technique widely adopted in the optimization algorithms in both convex and non-convex learning tasks (Sutskever et al., 2013; Vaswani et al., 2017; Tan & Le, 2019), the understanding on how the momentum would affect generalization performance of the optimization algorithms is still unclear. A natural question is:
Can we theoretically analyze the implicit bias of momentum- optimizers?
In this paper, take the first step to analyze the convergence of momentum based optimizers and unveil their implicit bias. Specifically, we study the classification problem with linear model and exponential-taled loss using Stochastic Gradient Descent with Momentum (SGDM) and Adam optimizers. We consider the optimizers with constant learning rate and constant momentum hyper- parameters, which are widely adopted in practice, e.g., the default setting in popular machine learning frameworks (Paszke et al., 2019) and in experiments (Xie et al., 2017). We note that Gradient Descent with Momentum (GDM) can be viewed for SGDM. Our main results are summarized in Theorem 1.
special case of SGDM, and naturally share the properties
Theorem (informal). With linear separable dataset S, for SGDM and Adam (without stochasticity, abbreviated as w/s latter), the loss converges with rate O(}) where is the nunber of iterations, the parameter norm diverges to infinity, and direction of parameters converges to the direction of the 1,2 max-margin solution.

---

Under review as a conference paper at ICLR 2022
Theorem 1 states SGDM converges to the L max-margin solution, which is the same as SGD, indicating that momentum does not affect the convergent direction. The good generalization behavior of the output parameters of SGDM is well validated the margin of classifier is positively correlated with its generalization error (Jiang et al., 2019). This is supported by existing experimental observations (c.f. Figure 1, (Soudry et al., 2018) and Figure 2, (Nacson et al., 2019)). Similar claims hold for Adam (w/s), which is also well supported by empirical results in Wang et al. (2021).
Our contributions are significant in terms of the following aspects:
We establish the implicit bias of the momentum based optimizers, an open problem since the initial work Soudry et al. (2018). The momentum based optimizers are widely used in prac- tice and our theoretical characterization deepens the understanding on their generalization property, which is important by its own.
Technically, we propose new Lyapunov function to analyze the convergence of SGDM, which helps to bound the sum of squared gradients along the training trajectory. Compared to the usual one, the new Lyapunov function depends on middle variable of an alternatve update rule of SGDM, which helps to capture the historical dependence in the momentum update. To our knowledge, such a technique has not been exploited ever before and can be of independent interest for convergence analysis of momentuumbasee optimizers. We then construct new Lyapunov function to bound the difference of learned parameters and the scaled max- max-margin solution, which finally leads to the direction convergence. This Lyapunov function provides a direct way to establish the convergence to the desired direction.
Section 2 collects further related works on the implicit bias of first order optimizers and convergence of momentum-batt based optimizers. Section 3 shows basic settings and assumptions which will be used throughout this paper. Section 4 studies the implicit bias of GDM as warm up. while Section 5 and Section 6 explore respectively the implicit bias of SGDM and Adam (w/s). Discussions of these results are put in Section 7.
Organization of This Paper.
2 FURTHER RELATED WORKS
Implicit Bias of First-order Optimization Methods. Soudry et al. (2018) prove that gradient descent on linear classification problem with exponential-tiledd loss converges to the direction of the max 2 margin solution of the corresponding hard-marg hard-margin Support Vector Machine. Nacson et al. (2019) extend the results in (Soudry et al., 2018) to the stochastic case, proving that the convergent direction of SGD is the same as GD almost surely. Qian Qian (2019) go beyond the vanilla gradient descent methods and consider the AdaGrad optimizer instead. They prove that the convergent direction of AdaGrad has a dependency on the optimizing trajectory, which varies according to the initialization. Ji & Telgarsky (2021) propose primal-dual analysis framework for the linear classification models, and prove a faster convergent rate of the margin by increasing the learning rate according to the loss. Based (Ji & Telgarsky, 2021), (Ji et al., 2021) design another algorithm with an even faster convergent rate of margin by applying the Nesterov's Acceleration Method on the dual space. However, the corresponding form of the algorithm the primal space is no longer Nesterov's 's Acceleration Method nor GDM, which is significantly different from our settings.
On the other hand, there is another line of work trying to extend the result in the linear case to deep neural networks. Ji & Telgarsky (2018); Gunasekar et al. (2018b) study the deep linear network and Soudry et al. (2018) study the two-layer neural network with ReLU activation. Lyu & Li (2019) propose 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 1,2 max-margin problem. Wang et al. (2021) extend the framework of Lyu & Li (2019) to adaptive optimizers, and prove RMSProp and Adam without momentum have the same convergent direction as GD, while AdaGrad doesn't. '. The results (Lyu & Li. 2019; Wang et al., 2021) indicate that results in the linear model can be extended to deep homogeneous neural networks, and suggest that the linear model is proper start point to study the implicit bias. There are also works on the implicit bias of regression problems with bounded optimal points and interesting readers can refer to (Rosasco & Villa, 2015; Lin & Rosasco, 2017; Ali et al., 2020) etc. for details.
Convergence of Momentum-Basee Optimization Methods. For convex optimization problems, the convergence rate of Nesterov's Acceleration Method has been proved in Nesterov (1983). In
2

---

Under review as a conference paper at ICLR 2022
contrast, although GDM (Polyak's Heavy-Ball Method) was proposed in (Polyak, 1964) prior the Nesterov's Acceleration Method, the convergence of GDM on convex loss with Lipschitz gradient not solved until Ghadimi et al. (2015) provides ergodic convergent result for GDM. i.., the convergent result for the running average of the iterates. However, the ergodic result is undesired under many learning scenarios, e.g., in classification tasks, the optimization algorithms usually output the parameters of the last step. To the best of our knowledge, there is only two works on the non-ergodic analysis of (S)GDM: Sun et al. (2019) and Tao et al. (2021). Sun al. (2019) prove that if the training loss is coercive (the training loss goes to infinity whenever parameter norm goes infinity), convex, and globally smooth, then, with constant momentum hyper-parametts the training loss converges to minima with rate ). Tao et al. (2021) analyze a case when momentum coefficient increases to and the gradient is bounded all over the parameter space, showing SGDM can improve the convergence rate of SGD by factor log(t).
There are also works on the gradient norm convergence of SGDM under various settings (Yan et al., 2018; Yu et al., 2019; Liu et al., 2020) and the investigation of momentum-based method from the view point of dynamics (Sarao Mannelli & Urbani, 2021). However, there no existing work on the implicit bias of momentum-baan based optimizers for the classification problem, which is first analyzed by this paper.
PRELIMINARIES
In this paper, we focus on the linear model with exponential-tailed loss. We first derive the results for binary classification, then show that the methodology can be easily extended to the multi-class classification problem.
Problem setting. The dataset used for training is defined as (æ:,, y: ) where æ; E Rd is the i-th feature, and y/: E IR is the i-th label (i = 1, .... N). We will use the linear model to fit the label: for any feature
Hd and parameter E Rd, the prediction is given by (w. æ).
For binary classification, given any data z; (æ,, y.) E S, the individual loss for parameter w is given (y: x;)). A common setting ensemble the feature and label together क; y, (there is a mapping T (x, 3) + yæ, and 2; is T [( y:))). The individual loss can be rewritten as
kw, (æ,, y))) = { (w, mz)) = ((w k.)).
The optimization target defined as the averaged loss:
((w) Ex f(ww (z 9:))
N
Without loss of generality, we consider the case with normalized data', that is, || 1, Vi [N].
Optimizer. Here we will introduce the update rules of SGDM and Adam (w/s). SGDM can be viewed as stochastic version of GDM by randomly choosing subset of the dataset to update. Specifically, the update rule of SGDM is given as
(SGDM) : w(t + 1) - wtt = v, DO + (ww(t) - wit - 1)), Vt 2 1,
(1)
where (()) is a subset of S with size b which is sampled independently and uniformly with replace- ment, and L is defined as ( Exemcy ((w.x) We also define F, as the sub-sigma field such that {e is adapted with respect to Filtration (F.)
'The proof be naturally applied to unnormalized data by letting ((x) ((maxee7(s) ||]||| z) and &
T; maxge T(S) |
3

---

Under review as a conference paper at ICLR 2022
The Adam (w/s) can be viewed as variant of GDM in which the preconditioner is adopted, whose form characterized as follows:
m(0) 0, mt) 31 - (1- -:) (.)V m((t) 1- B9 m m(t, Vt 2 1,
1
(0) = 0, (t) Bru(t - 1) +1 (1
32) (VL(w(tt)) f(t)
- B (t), A2 2
mi(1 -
(Adam (w/s)): w(t) = w(t 1) - 1Л V - 1) =ll
44 2 1,
(2)
where 1o(t-1)+c12
is called the preconditioner at step 4.
Assumptions: The analysis of this paper are based on three common assumptions in existing literature (first proposed by (Soudry et al., 2018)), respectively on the separability of the dataset, the individual loss behaviour at the tail, and the smoothness of the individual loss. We list them follows:
Assumption (Linearly Separable Dataset). There exists one parameter E Rdd such that
(w,, ..)
0, Vi E [N].
Assumption (Exponential-taile Loss). The individual loss is exponential-tailed, i.e.,
Differentiable and monotonically decreasing to zero, with its derivative also converging to zero, i.e., lim {(x) lim (xx O, and El (0 Vz;
Close to exponential loss when x is large enough, i.e., there exist positive constants c, C,O, K, K,,,, I4, x- and nn, such that,
Ve x+ :f'(z)) c(1 1e Vx x_ :-f(xx) c(1 e -e
(3)
(4)
Assumption 3 (Smooth Loss). Either of the following assumptions holds regarding the case:
(D): (Deterministic Case) The individual loss is locally smooth, for any so R, there exists positive real Hag- such that Vx, 2 8o. (f'()) ('(y) - H&g yl-
(S): (Stochastic Case) The individual loss 8 globally smooth, i.e., there exists a positive real H, such that Vx, E R. (x) - (3)l S H yl.
We provide cxplanations of these three assumptions respectively. Based on Assumption 1, we can formally define the margin and the maximum margin solution of an optimization problem, which is introduced in Definition 1
Definition 1. Let the margin (ww) of parameter w defined as the lowest score of the prediction of ur over the dataset S, i.e., ((w) mina;e7(s)) (w, 2.). By Assumption I and the positive homogeneous of 7( w
and thus we define the maximum margin solution in and the T22 max margin Y of the dataset S as follows:
i arg min ||0l 7(w)
Since ||- 1| is strongly convex and set {w : (ww) 2 1} is convex, ı is uniquely defined.
Assumption 2 constraints the loss be exponential-tailed which is satisfied by many popular choices
of f, including the (x) = e e=") and the logistic loss (foog (z) = log(1 + e e=))). Also, as c and can be respectively absorbed by resetting the learning rate and data n en and æ; az, without loss of generality, in this paper we only analyze the case that c a
The globally smooth assumption (Assumption 3. (S)) is 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

---

Under review as a conference paper at ICLR 2022
4
WARM UP: IMPLICIT BIAS OF GDM
In this section, we study the implicit bias of GDM as a warm up. The update rule of GDM is wit + 1) - w(t) = V[(((t)) + ((w(t))
wit - 1)), At 2 1
(5)
which is determined case of SGDM, with batch size N and thus without randommess. Although the analysis of GDM is essentially easier than that of SGDM, it helps us gain better understanding of this problem, and helps us to demonstrate several techniques which will be applied latter. The formal theorem of the implicit bias of GDM is as follows:
2H ( Then, for almost every data set 5 with arbitrary initialization point w(1), GDM (Eq. (5)) satisfies that w(t - log(t)(ù is bounded as t oo, and lim4-+co [[(([]]
1-3 Theorem 2. Let Assumptions 2, and 3. (D) hold. Let 3 E [0, 1) and 17 2
w((t) w
ab
Before we move on to the proof, we would like to provide some explanations of the results in Theorem 2. To begin with, Theorem 2 adopts constant momentum hyper-parameter, which agrees with the practice use (e.g. 33 is set to be 0.9 (Xie et al., 2017)). Also, Theorem 2 puts no restriction on the range of B. which allows wider choices of hyper-paramen the implicit bias of GDM agrees with GD in linear classification with exponential tailed loss (c.f. Soudry et al. (2018) for results GD), and this consistency can be verified by existing results (c.f. Section 7 for detailed discussions).
tuning. Furthermore, Theorem 2 shows
We then present proof sketch of Theorem 2, which is divided into parts: first prove that the sum of squared gradients is bounded, which indicates both the loss and the norm of gradient converge to O; we then show the difference between wt) and log(t) é is bounded, and therefore, the direction of w dominates as t + 0o.
Stage I: Bound the sum of squared gradients. The core of Stage I is select proper Lyapunov function {(t), which is required to correlated with the training loss L and be non-increasing along the optimization trajectory. For GD, since C itself is -on-incraas with properly chosen learning rate, we can just pick E(t) = C(t). However, as the update of GDM doesn't 't align with the direction of negative gradient, training loss L(t) in GDM is no longer monotonously decreasing, and the Lyapunov function requires special construction. A choice of E(t) is proposed as the follows:
Lemma 1. Let all conditions in Theorem hold. Define ((t) - [(w(t)) + 2n ([w(t) w(t 1)
Let C1 be positive real, s.t., 1 2 H- ((NEE)))) C1. We then have
1-8
E(1) 2 E(1+1)+ (1 3)(1 - (1-) 1
B1o(1 + 1!)
(6)
Remark 1. Although this Lyapunov function is obtained by (Sun et al., 2019) by directly examining the Taylor's 's expansion at w(t), the proof here is non-trivial as we only requires the loss to be locally smooth instead of globally smooth in (Sun el al., 2019), and the Taylor's 's expansion can only be applied to w((+1) it's's ensured that all parameters on the line cow(1)+ - -a)w((+1)) (a E (0, 1)) have training loss no larger than ((w(
To prove Lemma 1, we define wit + a)) = (t) + (1 atloaaawttttttt for any t z and a e (0, 1).
and prove a generalized version of Eq. (6):
(1 - 3)(1 - c)a²
E(I) 2 E((+ a) +
|| || +1) -nn)))
n
The proof idea is that as long as Eq. (7) holds for all time in [1, + ax), the training loss across [1, + a] will be smaller than [(w(1)). and the strict inequality in Eq. (7) holds. Consequently. there exists some small enough positive real e, such that Eq. (7) holds for all time in [1, t + a + E), and we are able to extend the feasible set where Eq. (7) holds. The formal description of the generalized lemma and its corresponding proof is deferred to Appendix 1.
Here "almost everywhere" means the conclusion holds except zero-measure set in d
5

---

Under review as a conference paper at ICLR 2022
By Lemma 1, we have that that E(1) is monotonously decreasing by gap (1-8)(1-c)a* (n(())) - - (())
"
As 5(1) = [1w(1)) is a finite number, we have Σi=1 1|w + 1) (t))l < co, which further leads to the following corollary by the negative derivative of the individual loss and separable data:
Corollary 1. Let all conditions in Theorem 2 hold. We have, Σi= || ((w(())) co.
The proof of Corollary 1 can be found in Appendix B.I.1. Resulted from Corollary I, we have [[L[(((t)]] + as + oc, which by the exponential-taie loss assumption further leads to lim (t)( = 0.
Stage II. Bound the difference between wtt and log(t) to. It seems natural to directly bound ((=(() log(!)tö(| across all iterations. Soudry et al. (2018) and Nacson et al. (2019) indeed follow
this routine by showing the norm of r()) - w((() log(!) ii is bounded, where t is some constant vector satisfying e ((w,a) recovers the coefficient of support vector ă in w.. However, their analyses rely on the fact that w(t + 1) wtt) equals (7)(((w(()) which has a simple form, i.e.
For GD ||r(t + 1)11² |r])] = ||r(t + - (t)ll 2log L ++1
~ (V)((w(t))r(()))
However, it no longer holds for GDM, as w(t++ u (f) a apponentially-decayee sum of gradients at wss), S t. To handle this problem, we propose a novel Lyapunov's function for the direction convergence, concluded as the following Lemma.
Lemma 2. Let all conditions in Theorem 2 hold. Then, [|((t]] is bounded if and only if the function g(t) is upper bounded, where g Z + R is defined as
1 g(t) e 1 ||(0))*+ I- (r(),, w(t) w(t 1))
3
1- Σ (((())-((r-- 1), w(() w(r - 1)}. (8)
8
Furthermore, we have
+ g()) is upper bounded.
The first claim in Lemma 2 provides an alternative approach to verify that [[r(t]] is bounded, while the second claim shows this approach can be fulfilled. The motivation of this lemma to construct a casy-to-verify criterion (i.e., g(t) is upper bounded) of [|r(t)]| is upper bounded. To demonstrate how g(f) is constructed intuitively, we consider the continuous dynamics approximation of GDM, i.e.,
3 dw
dw)(t
" V[(w(t)) = 0.
1- B di2 +
dt
I 1-3
We then calculate the [1]( - [1)(1
by applying the integral of the dynamics as 2 de de 1/' (m(o) --p v[(w(())) ) da
/' d(r(())12
8
d" d'w(s) do2
1-3
1-3 ((0).
-/," (M00). 7 vC(w(()) 11) do 1-8 (( ((00)- dw(()) (r())
B
dw(() de
/ dr(s) dw(s) do de
do)
1-3
de
where the last equation is due to Integration by part. We denote ğ(t) 8 ((r(t), dw((t)
1-3
J (dr(s) dwvl)) )ds)+ [[))) and it can be verified the derivative of ğ(t) is (r(t), - - Vl(w(()) ds ds -) By replacing dw((t) as wt)) wit 1), and dr(t) di as r(t) - r(t 1) in g(), we obtain g(t), and g(t + 1) (t) has the form (r(t). - - ([w((t) - log _ w)) which can be analyzed following the similar routine as (Soudry et al., 2018). The proof of the second claim is completed.
dt
On the other hand, the core of the proof of Lemma 2 is that [|( - (r(t), w() - wo( - 1)) is bounded if and only if ] [|]] is bounded, while (r(r) - r(r 1), w(T w(T 1)) is an absolute convergent based D || + (+) co.
TACKLE THE DIFFICULTY BROUGHT BY RANDOM SAMPLING
In this section, we analyze the implicit bias of SGDM. The randomness introduced by random sampling makes the analysis of GDM no longer work for SGDM. As example, if we want to

---

Under review as a conference paper at ICLR 2022
follow the same routine of the GDM case to show [(w((t) function of SGDM, we can only have
8
2n
El]((()) ww( 1)ll is Lyapunov
BC(w(())
P Bl(w(()) w(t 1)11* 2BBC(wo(t + 1)) 2n
_
E| we(t -)
2m
81 [ -o()
w(()]
As the squared first momentum smaller than the second momentum, EL(w(t)) 2, Bl
w(t - 1) may no longer be monotonously decreasing for every / E [0, 1). Furthermore, if the margin y small, 8 will be required be upper bounded by small number, which contradicts the relatively large choice of / in practice, e.g. 0.9 (We defer a detailed discussion to Appendix B.2.3). To tackle this problem, we propose a new Lyapunov function, with which we derive the following theorem for the implicit bias of SGDM:
Theorem 3. Let Assumption 1, 2, and 3. (S) hold. Let B E [0, 1) and < mmnnf 1-9 (1-0)9a²b }- HN 2H=Na32
Then, for almost every data set S, with arbitrary initialization point w()), SGDM (Eq. (1)) satisfies w(t) - log(t)ı i is bounded as + oo and lim
w(t))
almost surely (a.s.).
To the best of our knowledge, this is the first convergence analysis of SGDM with no restriction the gradient norm and with constant learning rates. Also, as both 1-8 and (1-8)"yyb NH are monotonously I+
increasing with respect to batch size b. Theorem 3 also sheds light on the learning rate tuning, i.e., the larger the batch size is, the larger the learning rate is. Furthermore, similar to the GDM case, Theorem shows the implicit bias of SGDM under this setting is consistent with SGD (c.f. (Nacson et al., 2019) for the implicit bias of SGD). This matches the observations in practice (c.f. Section 7 for details).
Remark 2. In practice, mini-batch SGDM are more widely adopted, whose update rule differs from SGDM only by the way obtaining Bt).. Specifically, within the T-th epoch E(T) = {KT 1,... KT+TT (K is the length of one epoch), (B()) is randomly and uniformly partition of S. One may wonder whether the same result hold for mini-batch SGDM. The answer is "Yes", with the a.s. condition removed in this case. We defer the detailed description of the corresponding theorem together with the proof to Appendix D.
The proof sketch follows the same framework as that for GDM by dividing the proof into two stages. However, the implementations in both stages differ, among which the proof of Stage I is significantly distinctive, as a new Lyapunov function is proposed.
Stage I: Bound the sum of squared gradients. To obtain the new Lyapunov function, first present a lemma to provide an alternative form of update rule SGDM:
Lemma 3. Define îj - "
I-B and u(1) (1) _ w(). The update rule of SGDM (Eq. (1)) is equivalent to ull + 1) -ni LB (w]()) +u((), w(t + 1) = (1)((() (1 B)u(L + 1).
By simple rearrangement of the second equation, we have u((++) wl) (w)(+1))) which differs from wt + 1) only by a larger step size updated from w (t). The following lemma then indicates that (E)(((()) is proper selection of Lyapunov function.
Lemma 4. Let all conditions in Theorem 3 hold. Then, have
E[C(u(t + 1))1 < El(u(t)) i [[] + 4
1-8 n
Σ [VV[sss)
and
Blc(u(t+ + 1))] < C(u(1))
Σ Bl L(
7

---

Under review as a conference paper at ICLR 2022
El(u(t)) may be not monotonously decreasing. However, the upper bound of EC(u(t)), ie.. [(u(1)) Σ
([(VL(((())ll is monotonously decreasing by [ at step t, and leads to the sum of expected squared gradients being finite along the trajectory (which further indicates the sum of squared gradients finite, a.s.).
The proof idea of Lemma 4 is the expectation of the first order Taylor's expansion of L at w(() has the form
Lij TB[ FIIV (
B[C(u(L+ + F)) ((a(()) " VL(w(())
As L is H smooth, we have VL(u(()) = Vl(((()) + -w(())) @
where ua()) =(()=
1-9 (wo()) wtt 1)) - & ((s is proportional to n7 Therefore, when yj is small, - (( is close to - V[(w(()) and the coefficient of -[V]((((t)] becomes dominant.
Stage II. Bound the difference between w(t) and log(t)(; w. The Lyapunov function used by Stage II of SGDM is the same the g() in the GDM case. As we have proved the sum of squared gradient along the trajectory is bounded, one can easily obtain that Et= ||/0(1 + 1) ((()) is bounded, and [[]]]]] being bounded is still equivalent to that g() is upper bounded. However, when comes to the detailed calculation of analyzing g + 1) (t), it differs from the GDM case due to the
random subset. We defer the proof to Appendix B.2.2.
ANALYZE THE EFFECT OF PRECONDITIONERS
When it comes to the analysis of Adam (w/s), the effect of the preconditioner should be taken into consideration when designing the corresponding Lyapunov functions. To tackle this problem, we incorporate the preconditioner into the Lyapunov function, and obtain the implicit bias of Adam (w/s) as follows:
Theorem 4.
Let Assumption 2, and (D) hold. Let 32 > B1 2 O. and the learning rate n is small enough constant (The upper bound of learning rate is complex, and defer it to Appendix C.I). Then, for almost every data set S, with arbitrary initialization point w w(1), Adam (w/s) (Eq. (2)) satisfies that w(t)= - log(t) (t) is bounded as tt -> co, and lim;
w(t)
10
Remark 3. Existing literature usually assume time-decaying hyperparameter choice of 31 or Bo (c.f.. (Kingma & Ba, 2014; Chen et al., 2018)). To the best of our knowledge, the only work analyzing Adam with constant 31 and 32 (Reddi al., 2019), which assumes 32 8 (stronger than our assumption). Our result indicates that the ranges of $1 and B2 can be broader in selection.
We still start the proof sketch by proving the sum of squared gradients is finite in Stage I. Compared to GDM, the difference is that Stage I, we will also prove the loss converges to 0 with rate O This property will be used in Stage II to analyze the effect of preconditioner
implicit bias.
Stage I: Bound the sum of squared gradients. The next lemma can be viewed as an extension of Lemma I by taking the preconditioner into consideration, and characterizes the one-step loss update in Adam (w/s).
Lemma 5. Let all conditions in Theorem 4 hold. Then, for any > 1,
- B
C(1 + (1 2 27 31)
Vella+ + ((T) @ (wo(1 1)) ww))
<L(w(t)) + 2en(1 31) (c Vella D(t (w(t) w(t (o(t-1))]]_ (10)
1 1- 8/
1 (c
The difference between the proof of Lemma 5 and Lemma 1 is that we need handle the gap between the preconditioners at step t and step t + 1, this leads to a amplifying factor VELl + D(t - 1) o (wot) - w(t - 1)>| which, however, is smaller than introduced by the gap between the coefficients of momentum
1-88 of term || V 02(1-10-1
1-9 92(1-8
the shrinking factor
8

---

Under review as a conference paper at ICLR 2022
mt(t) and mi(t - 1). As oo, both B1 0 and (c31)² + 0, and can obtain that E(t) ((w((t) + 2 [
V VElu+ (t -t o (w((t w(t - -))
is a Lyapunov function.
Based on Lemma 5, we can prove the following asymptotic rate of L.
Lemma 6. Let all conditions Theorem hold. Then.
[(w(t)) = = (t @(log(t)), and ||0(()) - w(( - 1)1l = O)
The proof idea of Lemma 6 is that by the exponential-tailed property, when time large enough, the training loss can be bounded by the gradient, and further bounded by Vel it - (w(tt=
(t 1) Consequently, E(t + - E(t) = O(g(t)), and { O(t
Stage II. Bound the difference between w (t) and ltg(t) w. The Lyapunov function for the direction
difference is also modified according to the preconditioner, introduced in Lemma 7:
Lemma 7. Let all conditions in Theorem 4 hold. Then, [|(((]] is bounded if and only if g(l) is upper bounded, where g(l) is defined as follows.
(t)
VE 2
|r(t)]|
B1
(r(0),1 -10)
Vela itt (w0(t) w(t - -11)
1-
31
Σ (T(T) r(T - -1,, - 3T -1- 51 + D(T (wn(T) w(( - 1)))-
B1
Furthermore, we have E (g(l + -g(()) is upper bounded.
The first claim of Lemma 7 is similar to that in GDM and SGDM case. However, when we come to the second claim, simple calculation of g(( 1) (() leads to
(VE- (1- + (wo -(())) + (r(t), - -Velog( & + no 1- V[(w(t))).
This is where we need Lemma 6, which bounds the gap between V / + (t) and VE by Ot el
and makes E (r(t), (vē - (1 / (()) @ (un(t w())) an absolute continuous sequence. The second term (r(t), - /E (+1 1 1-3 VLww(t))) can be tackled by following the same routine as the GDM/SGIDM case. Consequently, the proof of Lemma 7 is completed.
Till now, we have obtained the implicit bias for GDM, SGDM and Adam (w/s), one may wonder whether the implicit bias of stochastic Adam can be obtained. Here, we make some discussions here and put its further investigation for future works. First, our analysis can be extended to prove that the stochastic adaptive heavy-ball algorithm converges the 1.2 max margin solution, which is proposed by (Tao et al., 2021) and has the following form?:
(CB()((())) + 3(w(() wi( 1)), 1, Vella + E(t)
an(t + 1) (t)
where (tt) is defined Eq. (h) proof is simple combination of the proof techniques in SGDM and Adam by observing that the stochastic adaptive heavy-ball algorithm has the following equivalent update rule (u(1) = w())
VLB()) + u((),
u(t + 1) = - 1- Velle (tf)
w + 1) (w + (1 B)u(t+
However, Adam is different from the stochastic adaptive heavy-ball algorithm it combine the conditioner and momentum as a whole, which makes our constructed Lyapunov function can not be applied. We will put further investigation on stochastic Adam in future work.
*Compared to (Tao et al.. 2021). we put the ella inside the square-roo root and use p(t) instead of vt() to demonstrate the difference hetween Adaptive Heavy Ball and Adam, while these changes will not influence the convergent direction.

---

Under review as a conference paper at ICLR 2022
7 DISCUSSIONS
Extension to the Multi-Class Classification Problem. As mentioned in the introduction, despite all the previous analyses are aimed the binary classification problem, they can be naturally extended to the analyses multi-class classification problem. Specifically, in the linear multi-class classífication problem, for any (xr y) E R&xx {1,... C in the sample set S, the (individual) logistic loss with parameter W E R Cxxx is denoted as
W. m
(y: Wx) = log
W
Correspondingly, dataset S is separable there exists a parameter W, such that V(æ, y) S, we have W y. at Wi,z, Vi + y. The multi-class L max-margin problem is then defined as
min W || rr subject to: Wy. a Var, y) E S y.
where || denotes the Frobenius norm. Denote W the L max- max-margin solution, we have (mini-batch) SGDM and Adam (w/s) still converges the direction of W. the proof of which is deferred to the Appendix D.2.
Theorem 5. For linear multi-class classification problem using logistic loss and almost every separable data, with small enough learning rate, and 1 B2 Bi 2 (for Adam (w/s)), (mini-batch) SGDM and Adam (w/s) converge to the multi-class L max-margin solution (a.s. for SGDM).
Consistency with the Existing Experimental Results. Our results stand with existing experimental observations. Specifically, Soudry et al. (2018) conduct experiments using GD and GDM on the same linear separable data (c.f., Figure in (Soudry al., 2018)), and is observed that the training behaviors of GD and GDM are quite similar in terms of the direction w(t). the training loss, and the margin, which supports our Theorem 2. Nacson al. (2019) extend the experiment to the stochastic setting (c.f. Figure 2 in (Nacson et al., 2019)). and observe the same similarity between SGD and SGDM, which agrees with our Theorem 3. Wang al. (2021) conduct the experiments of SGD, SGDM, Adam (without momentum) and Adam MNIST using homogeneous neural networks (c.f. Appendix F.1.2 (Wang et al., 2021)), and observe such similarity for deep neural networks. Our theorems apply to linear models, which is special case of homogencous neural network, and meet their observation.
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, Lyu & Li (2019) construct Lyapunov function bounding the rate between loss and parameter norm of GI) on the homogeneous deep neural networks, and prove the parameter direction converges to some KKT point of the L max-margin problem, which extends the result of GD on linear model. Wang et al. (2021) further show the proof techniques in (Lyu & Li, 2019) can be generalized, and successfully extend the Lyapunov function to AdaGrad, RMSProp and Adam (without momentum) on deep homogeneous neural networks. It will be interesting to see whether such Lyapunov function can be constructed for GDM and Adam in homogeneous neural networks.
8 CONCLUSION
In this paper, we study the implicit bias of momentum-based optimizers in linear classification with exponential-taiie loss. Our results indicates that for SGD and Adam, adding momentum will not influence the implicit bias, and the direction of parameter converges to the 2 max-margin solution. Our theoretical results stands with existing experimental observations.
REFERENCES
Alnur Ali, Edgar Dobriban, and Ryan Tibshirani. The implicit regularization of stochastic gradient flow for least squares. In International Conference on Machine Learning, pp. 233-244. PMLR, 2020.
10

---

Under review as a conference paper at ICLR 2022
Xiangyi Chen, Sijia Liu, Ruoyu Sun, and Mingyi Hong. On the convergence of a class of adam-type algorithms for non-convex optimization. In International Conference on Learning Representations, 2018.
Euhanna Ghadimi, Hamid Reza Feyzmahdavian, and Mikael Johansson. Global convergence of the heavy-ball method for convex optimization. In 2015 European control conference (ECC), pp. 310-30 315. IEEE, 2015.
Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nathan Srebro. Characterizing implicit bias in terms of optimization geometry. In International Conference on Machine Learning, pp. 1832-1841. PMLR, 2018a.
Suriya Gunasekar, Jason D Lee, Daniel Soudry, and Nati Srebro. Implicit bias of gradient descent on linear convolutional networks. In Advances in Neural Information Processing Systems, pp. 9461-9471, 2018b.
Ziwei Ji and Matus Telgarsky. Gradient descent aligns the layers of deep linear networks. arXiv 2018.
preprint arXiv:
Ziwei Ji and Matus Telgarsky, Directional convergence and alignment in deep learning. arXiv preprint arXiv:2006.066 06657, 2020.
Ziwei Ji and Matus Telgarsky. Characterizing the implicit bias via primal-dual analysis. In Algorithmic Learning l'heory, pp. 772-804. PMLR, 2021.
Ziwei Ji, Nathan Srebro, and Matus Telgarsky. Fast margin maximization via dual acceleration. In International Conference Machine Learning, pp. 4860-4869. PMLR, 2021.
Yiding Jiang, Behnam Neyshabur, Hossein Mobahi, Dilip Krishnan, and Samy Bengio. Fantastic generalization measures and where to find them. arXiv preprint arXiv:1912.022778 2019.
Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Peter Tang. On large-batch training for deep learning: Generalization gap and sharp minima. In International Conference on Learning Representations, 2017.
Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint 1411v:1412.69980 2014.
Junhong Lin and Lorenzo Rosasco. Optimal rates for multi-pant pass stochastic gradient methods. The Journal of Machine Learning Research, 18(1):3375- 3421, 2017.
Yanli Liu, Yuan Gao, and Wotao Yin. An improved analysis of stochastic gradient descent with momentum. Advances in Neural Information Processing Systems, 33, 2020.
Kaifeng Lyu and Jian Li. Gradient descent maximizes the margin of homogeneous neural networks. arXiv preprint 1906v:1906.05000 2019.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In International Conference Learning Representations, 2018.
Mor Shpigel Nacson, Nathan Srebro, and Daniel Soudry. Stochastic gradient descent on separable data: Exact convergence with fixed learning rate. In The 22nd International Conference Artificial Intelligence and Statistics. pp. 3051-3059. PMLR, 2019.
Nesterov. A method for solving a convex programming problem with convergence rate o (1/k2). In Soviet Mathematics. Doklady, volume 27, pp. 367-372, 1983.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. In search of the real inductive bias: On the role of implicit regularization deep learning. ICLR, 2015.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, hegf-peeformance deep learning library. Advances in neural information processing systems, 32: 8026-8037, 2019.
11

---

Under review as a conference paper at ICLR 2022
Boris T Polyak. Some methods of speeding up the convergence of iteration methods. Ussr computa- tional mathematics and mathematical physics, 4(5):1-17, 1964.
Qian Qian and Xiaoyuan Qian. The implicit bias of adagrad on separable data. In Advances in Neural Information Processing Systems, pp. 7761-7769, 2019.
Sashank Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. arXiv preprint arXiv:/904 092377, 2019.
Lorenzo Rosasco and Silvia Villa. Learning with incremental iterative regularization. In Proceedings of the 28th International Conference on Neural Information Processing Systems-Volume 1, pp. 1638, 2015.
Stefano Sarao Mannelli and Pierfrancesco Urbani. Analytical study of momentuum-assed acceleration methods in paradigmatic high-dimensional non-convex problems, Advances in Neural Information Processing Systems, 34, 2021.
Robert E Schapire and Yoav Freund. Boosting: Foundations and algorithms. Kybernetes, 2013.
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The implicit bias of gradient descent separable data. The Journal of Machine Learning Research, 19(1): 2018
Tao Sun, Penghang Yin, Dongsheng Li, Chun Huang, Lei Guan, and Hao Jiang. Non-ergodic convergence analysis of heavy-ball algorithms. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 5033-5040, 2019.
Ilya Sutskever, James Martens, George Dahl, and Geoffrey Hinton. On the importance of initialization and momentum in deep learning. In International conference on machine learning, pp. 1139-1147. PMLR, 2013.
Mingxing Tan and Quoe Le. Efficientne:: Rethinking model scaling for convolutional neural networks. In International Conference on Machine Learning, pp. 6105-61 14. PMLR, 2019.
Wei Tao, Sheng Long, Gaowei Wu, and Qing Tao. The role of momentum parameters in the optimal convergence of adaptive polyak's heavy-ball methods. arXiv preprint 1021::2002.07314, 2021.
Matus Telgarsky. Margins, shrinkage, and boosting. In International Conference on Machine Learning, pp. 307-315. PMLR, 2013.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, pp. 009855999099 2017.
Bohan Wang, Qi Meng, Wei Chen, and Tie-Yan Liu. The implicit bias for adaptive optimization algorithms on homogeneous neural networks. In International Conference on Machine Learning. pp. 10849-10858. PMLR, 2021.
Ashia C Wilson, Rebecca Roelofs, Mitchell Stern, Nati Srebro, and Benjamin Recht. The marginal value of adaptive gradient methods in machine learning. In Advances in neural information processing systems, pp. 4 4148-4158, 2017.
Saining Xie, Ross Girshick, Piotr Dollár, Zhuowen Tu, and Kaiming He. Aggregated residual transformations for deep neural networks. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 1492-1500, 2017.
Y Yan. T Yang, Z Li. Q Lin, and Y Yang. A unified analysis of stochastic momentum methods for deep learning. IJCAI International Joint Conference on Artificial Intelligence, 2018.
Hao Yu, Rong Jin, and Sen Yang. On the linear speedup analysis of communication efficient momentum sgd for distributed non-convex optimization. In International Conference on Machine Learning, pp. 7184-7193. PMLR, 2019.
12

---

Under review as a conference paper at ICLR 2022
Supplementary materials for "Does momentum Change the Implicit Bias on separable data?"
A
PREPARATIONS
This section collect definitions and lemmas which will be used throughout the proofs.
A.1 CHARACTERIZATION OF THE MAX-MARGIN SOLUTION
This section collects several commonly-used characterization of the max-margin solution from Nacson et al. (2019) and Soudry et al. (2018).
To start with, we define support vectors and support set, which are two common terms in margin analysis.
Definition 2 (Support vectors and support set), For any i E [N], T; is called support vector of the dataset S, if
(Ri, i =
Correspondingly, i; is called non-support vector if (ē;, w) 1. The support set of S is then
defined as
S. = { y:) (y, w) = 1}.
The following lemma delivers i as an linear combination of support vectors. Lemma 8 (Lemma 12, Soudry et al. (2018)). For almost every datasets S, there exists unique vector v (V), ,N), such that w can be represented as
i
(11)
where satisfies v; 0 if & T(S.), and v, 0ff E T(S)). Furthermore, the size of S, is at most
By Lemma 8, we further have the following corollary:
Corollary 2. For almost every datasets S, the unique v given by Lemma 8 ffurthrr satisfies that for any positive constant Cz there exists non-zero vector w, such that, R, E <T(s)), we have
Cze (ā: U;
(12)
Proof. For almost every datasets S, any subsets with size d of S is linearly independent. Since $, has size no larger than d (by Lemma 8), and Eq. (12) equivalent to linear equations, the proof is completed.
For the stochastic case, will also need the following lemma when we calculate the form of parameter at time I.
Lemma (Lemma 5, Nacson et al. (2019)). Let Bss) be the random subset used in SGD (i.e., the one used in SGDM). Almost surely, there exists vector tp
N
Σ
v,C. log
1 - n(().
b
N
==1
(B(()))
where re(t) satisfies [[)( B(s) the random subset used in SGDM (i.e., the one used in mini-batch SGDM), then the a.s. condition be removed.
oft 0.5+c) for any O. and |n + 1) re(t) O(t If the
13

---

Under review as a conference paper at ICLR 2022
A.2 PREPARATIONS THE OPTIMIZATION ANALYSIS
This section collects technical lemmas which will be used in latter proofs. We begin with a lemma bounding the smooth constants if the loss bounded.
Lemma 10. loss satisfies (D) in Assumption then for any wo, L(w) L(wo), then we have C is Hag smooth at point w, where 80 = (F((NL(W))) Furthermore, L is globally Hap smooth over the {w L(w))= & ((
Proof. Since is positive, we have E [N],
tww,a xi)
E/=1 ((,,
N
<
= L(w) < ((wo);
N
N
which leads to Ê(w, 2;) < NL and is Ho smooth at (wn mt)-
Furthermore, since V. V. zi) = V Cl(((( x.)) ) = E' ((w,, az)) for any two parameters wh and w2 close enough u,
/w 2,) ( x;)1 = [1('((w11, x;)) ((w2, x $ (10 x:)) f' f((22, xi)) S Hoo k:01 - w2. xi)l S Hap || wy ll:
and thus,
N
[V - -VW((u)))VV((())) S
V Ve ( z,) - Velluug, zi)1l S Heal|wr - w2ll.
which completes the proof that C is locally Ha, smooth at w.
Now if wi and w2 both belong to {w L(w)= < C(wa)}, we have for any ã; E T(S), (w), ã.) (NL(w))) Following the same routine as the locally smooth proof, we complete the second argument.
(NVC(())) and (w2, > 8- -
The proof is completed.
Based on Assumption 2, we also have the following lemma characterizing the relationship between loss & and its derivative l' when large enough.
Lemma 11. Let loss satisfy Assumption 2. Then, there exists an large enough xn and positive real K, such that, Vx > Fo, we have
{()) -K(
Proof. By Assumption 2, there exists a large enough To. such that Vo > zo, we have
1 - < -f'(x) I =
(13)
2
On the other hand, lim ((x) = 0, we have
((x) (()dds
5=
which by Eq. (13) leads
" ds < <((x) < 10 -' 26
Therefore, setting K 4 completes the proof.
The following lemma bridges the second moment of VL with its squared first moment.
14

---

Under review as a conference paper at ICLR 2022
Lemma 12.
Let the dataset S satisfies the separable assumption 1. Let B be random subset of S with size b sampled independently and uniformly without replacement. Then, at any point w, we have
N [V[(w)]
|V((w)]] & EB [IV[B(w))]]] b
Proof. To start with, notice that
[V[(w)] [B - EBI|C((W)].
Therefore, the first inequality can be directly obtained by Cauchy-Schwartz inequality. To prove the second inequality, first calculate the explicit form of V (L))
1 12
VLB(w)]
V
(w, z)
ZEB
Σ
((ww, 2))
Σ
((w ((),,,))e (3)
b
(E)(B)
1
Σ
(((w, ()),)(
82
(B)
Therefore.
EB [LB(w)]1
< 12
Σ
((w,
(14)
(T()E((B)
-EB b
Σ
(() (.TT(())
ă. (T()
1
Σ
((ww
(gla
62
(T(S)
b -
Σ
(((w, x)) 2
Σ
((w,, () E²1)
Nb
bN(N -1
@ET(S)
a. (5)
$ Nb
Σ C(ww, x)) RET(S)
(15)
On the other hand,
1 = N
Σ *ET(S)
(((w, Z))²
Σ
((un, )))
v
(x) 7
Σ
C(ww, a))
N
SET(S)
TET(S)
where Eq. (+) is due to Vz (x. -w) > and El <. Therefore,
72
[VL(w)]1 2
Σ
((ww, 2t))
(16)
N2
@ET(S)
The proof is completed by putting Eqs. (15) and (16) together.
15

---

Under review as a conference paper at ICLR 2022
In the following lemma, show the updates of GDM, Adam, and SGDM are all non-zero. Lemma 13. Regardless of GDM, Adam, or SGDM,, the updates of all steps are non-zero, i.e.,
wwwt + 1) w(t) || > 0, vt > 1.
Proof. We start with the alternative forms of the update rule of GDM, Adam, and SGDM using the gradients along the trajectory respectively. For GDM, by Eq. (5), the update rule can be written as
wt + 1) (t) = Σ 8 VV
(17)
Similarly, the update rule of SGDM be written
w(t + 1) ((() - Σ gt- VV VV-V ((s))
(18)
while the update rule of Adam can be given as
E 1-8 $1 'V VL(w(s)) 1-31
w + 1) - w(t) = Vela Σ
(19)
1- 8g 1-
(
(VL(((()))
On the other hand, by the definition of empirical risk L, the gradient of at point w can be given as VL(w) Σ (((ww, x.))
(20)
N
By Eq. (20) and Eq. (17), we further have for GDM,
w(t 1) w(t) = - Σ gi-e E
(((w((s), #.))
(21)
N
By Assumption 1, there exists non-zero parameter wù, such that, (1ù, ..) > 0. Vi. Therefore, by executing inner product between Eq. (21) and wù we have
(
Σ gi- Disl ((((((s) (ā,,, 20) (2) 0,
(to(++1)-w(()) | (wt++))-w(() wd)
where Eq. (+) is due to l' 0. This complete the proof for GDM.
Similarly, for SGDM, we have
- ( yEn (((w(ss) yæ)) 20)
|| 1) (()) إb 2 -7
Σ gt-s
0,
b
which completes the proof of SGDM.
For Adam, we have
1 32
||al(t + 1) (0--((()) w()ll
El.
Σ
22
(V L(w(s)))
33
t
1
82
Σ 1- 1-
i
El
82
(VL(un())))
35
Vela+ + E 1 - (V((o(s)))
1=1
1 - 81
w.
3 VL(w(())
s=1
31 DN E' ((((((s), a.)) ( .))
Σ
39
N
which completes the proof of Adam.
The proof is completed.
16

---

Under review as a conference paper at ICLR 2022
B IMPLICIT BIAS OF GD/SGD WITH MOMENTUM
This section collects the proof of the implicit bias of gradient descent with momentum and stochastic gradient descent with momentum.
B.1 IMPLICIT BIAS OF GD WITH MOMENTUM
This section collects the proof of Theorem 2.
B.I.I PROOF THE OF SQUARED GRADIENTS CONVERGES
To begin with, we will prove the sum of squared norm of gradients along the trajectory is finite for gradient descent with momentum. To this, first define the continuous-time update rule
w + a) (t) atw(t 1) w()), VI z+, Va [0,
We then prove generalized case of Lemma for any w(t + ox). Lemma 14 (Lemma 1, extended). Let all conditions in Theorem 2 hold. We then have
[(w(t)) $ ((w(t) w(t - 1)1l L(w(( + a))
8 a22l 2lllw( (t 1) w(t)ll
2n
2n
(1 B) -1)aa
| + 1) ww(())
n
where C1 is positive real such that 17 = -1 Cz.
Proof of Lemma 14. For brevity, we denote so - (NC(ww)) We prove this lemma by reduction to absurdity.
Concretely, let to be the smallest positive integer time such that there exists [0, 1], such that Eq. (7) doesn't hold. Let a* = inf(a E [0. Eq. (7) doesn't hold for at", By continuity,
Eq. (7) holds for (t", o.)).
We further divide the proof into two cases depending on the value of az
Case 1: a 0: For any to t t 1, we have Eq. (7) holds for (t, 1). Specifically, we have
B (1((t) w(t 1)1l 2 L(w(t + 1)) +
8 27
((w((t) +
1 + 1) wt)))
27
which further leads
8 || ([w(1) w(0)] L(w((t)) +
8 l(=(tt)) -w(tt" 11)
[(w(1)) = [(w (1)) +
2m
2n
Since A 2n ((((tt)) w(tt - 1| is non-negative, we have
[(w((1) 2 L(w((")).
By Lemma 10, we have C is Ha, smooth at w(t"). Therefore, by Taylor's expansion for C at point w(t" ), we have for small enough a > 0
[(w(t" + a))
Ha
<f(w(tt)) + (VL(w((t)), w(t" + +a) - wo(tt)) + 110(t" + +a) -t())
2
H a2
-l(w(t")) + 0: (VV((((( wit + ww(()) +
|/ + - w(t+))l
2
((w(t)) + a 1 (B(w(t)) - wot 1)) (wi( + w(t")), w(t" + 1) w((t)
a
|/o(1" + 1) a((("))²
2
17

---

Under review as a conference paper at ICLR 2022
-[(w(t")) + aB
H Hop a²
-a)
((w(t") w(t - 1), w(( + 1) - -w((t)) +
we(tt + +1) -0(
2
1
a
aB
S ((w((t))
+
((()(tt)) w(tt" - 1)11 +
11(2r(t" + =0(?))1
2n
2nj
+
a²
a
1w(t" +1 -w(t))l²
2
11
= [(w(tt))
+
aB
((w(tt)) w(t 1)ll +
aB
a
Hoya²) |1(w((" +1) w((
2m
2n
1
B
-w(tt - 1)112 (1 - a)s
= [t)(
+ ((2ott))
((w(tt) w0tt" - 1)11
27
2n
+
( aB
a
+
Hap
1(20(t" +1 - w(
2n
7
2
(0)
B
w(tt - 1]]11- B a² 120(t +1) m(1
((w(tt)))
|l=(t))
2n
27
11-83(
11- )
1/w(t" 1) w(t*) ||3
(22)
7
where Eq. (+) is due to simple rearrangement of the update rule of gradient descent with momentum (Eq. (5)), i.e.
vL(w(()) = - (B(((()) - w(t - 1)) - (w + 1) w(t))) Vt 1,
(23)
Inequality (**) is due to Cauchy Schwarz's ' inequality and arithmetic-gcome -coometree average inequality, and Inequality (o) is due
(1 )3
((w(tt) w0t - 1)]{² +
[aB
a +
H H
[1(w(t + 1) - 2t))11
2n
2n
2
(1-a)3
a)3
(((w(tt)) wol1 - 1)11² + ((a)
21
<0(a2)
8
a "|w((t" +1 - w0(")|1 (1 B) C2)a2
||w(tt + - w0(
=
2m
Here the inequality is due to that as a tend to zero, which a negative constant by Lemma 13.
(1-aحي (w) wtt - 1)]l tend to 2y [1(((((tt) wr(t - 1]
2n
Eq. (22) indicates Eq. (7) holds at (t", a) for a > is small enough, which contradicts to a" 0.
Case 2: a" # Same as Case 1, we have for any 1 S <t.
3 (2o(t) w(t 1)112 2 L(w(t + 1)) + 3 wol + 1) wt))
((w(tt) + 27
27
which further leads
3 2m
f(w((1) 2 ((w((t)) +
uu((t))
wtt 1)1
(24)
On the other hand, by the definition of a*, we have for any 5 a < a", we have Eq. (7) holds for (t", aa), which by continuity further leads to Eq. (7) holds for (t" (t",a"). Therefore, a" < 1, otherwise,
Eq. (7) holds for (t", a). Va E [0, 1] which contradicts the definition of t".
Combining Eq. (7) with (t", a:) and Eq. (24), we further have
3 a² (ll| + 1) - w0)) 1-C,
L(w(1)) 2 L(wr(t" + a)) + 2m
H Ha a3)a(t + - =(tt)l
20,
18

---

Under review as a conference paper at ICLR 2022
Consequently, for any [0, a*]
[(w((1) 2 L(w(lt" + a));
and by Lemma 10, we then have is H., smooth w((t + a), which further by Taylor's expansion leads to
[(w(11 + +a)))
Sc(w((()) + (VL((((")) (((())))))((((()))) u/l1 + +a") - -o(())) + Hoo
(tt(t" + +x)) - -w(()]]
2
(0)
B S [((w(t))) + (t())) - w((t" - -1)1?++ a²
10(t" + - w
2n
27
Hs.(aa))
a²
||w(tt + +1) =t(t))1
"
a²B
Hao (a*)²
a2 (2)
=[(w((()) +
l(0((()) - -w(l" - 1))11++ +
||w0(( + +1) - =1
2n
2
21
B 11((t)
(1 - 0)))(a)
1= (2 (2-13) B)
(((w(t)))
- w(tt - 1)11² +
1|wo(t" +1) wtt)
2n
71
21
( [((o(('))
3
|10((") w0ll" 1)]1 (a*)²²
10011 + 1) -w0((")12
2n
2n
(1 - (1 - (a*)² |/w((t +1) ur(*")²
7
where Eq. (o) follows the same routine as Case 1, Eq. (+) is due to the definition of r and C₁ and
Eq. (+) is due to a² < 1, and ||t((1" + 1) wv(()) |2 0 (given by Lemma 13).
By the continuity of L. for any small enough 5 > 0, Eq. (7) holds for (t",a" a + +), which contradicts to the definition of a".
The proof is completed.
By Lemma 1, one can easily obtain the sum of the squared norms of the updates across the trajectory converges.
Corollary 3. Let all conditions in Theorem 2 hold. We have
Σ |utt + 1) w(()l12 co.
(25)
Consequentially, we have
[u(t)]l=
Proof. By Lemma we have
B (lo(t) w(t - 1)|12- (Cluo( + +1))+ 2n
B
[(w((t) 2n
[w(t 1) s(t))1
(1 C1)(1 (3)
wwit + 1) (t
7
which by summing over t further leads to
[(w(1)) 2 ((w((1)- ((wu((t + 1)) + 2m
(((o))))((((t
||o + 1) - wt))12)) 2
(1 C1)(1 - 3) Σ
[s(s+1)-----) -s)+++)-((s){
Taking + oo leads to
ww( + 1) - =ss)) < ao.
19

---

Under review as a conference paper at ICLR 2022
By triangle inequality, we further have
1 (t)l - (20 + +1) - w(s))l + (1)(l
(+) 1s + 1) 1)
m(())1 -
+ [1][
where Eq. (x) is due to Cauchy-Schwartz's inequality.
The proof is completed.
By the negative derivative of the loss and the separable data, we can finally prove Corollary 1.
Proof of Corollary 1. By Eq. (21), we have
N
(((w(ss) )x))
(1 + 1) 2 =1²
Σ 3r 88
N
N
((w((s)), (z
|100
-12
Σ
8r
Li=1
N
|
1
(+)
w. gi-s N
(((w((s) (;)));;;
217
N
(04)
g E
iiml ((((w(s), 2ii)
2 722
Σ
N
ΣN ('((wn(t, +.))
20222
N
Li C'((w(t), [2:))][[ 2
(
217
N
Σn (;)( N
20²2?
" [VV(((()))
(26)
where Inequality (*) is due to
'ss inequality, Inequality (**) is due to (((s) < 0,
Vs IR and (w. σ.,) y, Vi E [N] and Inequality (o) is due to | 1. By combining Eq. (25)
and Eq. (26), we complete the proof.
By the exponential-tailed assumption of the loss (Assumption 2), we further have the following corollary.
Corollary 4. Let all conditions in Theorem 2 hold. Then, lom VL(w(t))] = 0, and
Tim (w((), a:;) 0o, Vi.
Consequently, there exists an large enough time lo, such thut, VI > la. Vi, we have (wo(1) m.) > 0. and
_e(((((t), $ (1 + e (20())) ) (w)(t)...) ) (L((w(()), m:)) 2 (1 (w0()))) ((w))))))((()))))))))))) (w.())..))
20

---

Under review as a conference paper at ICLR 2022
B.1.2 BOUNDING THE ORTHOGONAL PART
To prove Theorem 2, we only need show w(t) log(t) (t 2 1) has bounded norm for any iteration t > 0. Letting C2 (1-3)N in Corollary 2, we obtain an constant vector tù satisfying Eq. (12). Define
r1) - (() log(t) it.
(27)
As v is a constant vector, that w(t) - (t) (t 1) has bounded norm is equivalent to r(t) has bounded norm. Lemma 2 then propose an equivalent proposition of ||r(t)]] is bounded, and further prove this proposition is fulfilled. As the proof is rather complex, we separate it into two sub-lemmas. We first prove ||((t)] is bounded if and only if function g(t) is upper bounded.
Lemma 15 (First argument in Lemma 2). Let all conditions in Theorem 2 hold. Then, [|((t]] is bounded if and only if function g(t) is upper bounded.
Proof. We start the proof by showing that (i( - 2 -r(r 1), ()() w(( 1)) has bounded absolute value.
By the definition of r(t). we have
rtt) r(t - 1) -w(() - w(t - 1) - log
w..
t {--1)
which further indicates
(t "'((())) ((T)) - -w(r 1) -log (--1)
T
w. w(T) w(T 1)
Therefore, the absolute value of (1) can be bounded as
[A(()]= = Σ w(T) - ww( - 1) - -log
v. w0(T) - -wo(T 1)
(T(T) - w(T - 1) - log
w. w(() - w(r 1))
[ w(r - 1)11² + Σ
log
w (l()) - un(r 11)
-
Σ [ w(r 1)112 +
Σ
log
T
i
w 1)ll
r=2
3+)
||w(T) -w( 1)11
+
1
T T log
i
2
(0)
<00,
where Inequality (x) is due to the Inequality of arithmetic and geometric means, and Inequality (o) is
T due to Corollary 3 and log - = (
Therefore, g(t) is upper bounded is then equivalent [1rr + (r(t), w(t) w(t 1)) is upper bounded. Now if (1)) - w() - wo(t 1)) is upper bounded, will prove [[][ is bounded by reduction to absurdity.
Suppose that [[]]( has unbounded norm. By Corollary 3, we have lim [|w](() w(( - 1)[ 0. and there exists large enough time T, such that [|wr(() - w((1 - 1) < for any / 2 On the other hand, since r(t) is unbounded from above, there exists an increasing time sequence k > T.
i zt, such that
lim [[(kk))] oo. 1000
21

---

Under review as a conference paper at ICLR 2022
Therefore, have
B *I-3 (r(ks), w(k:) w(kk - 1))
lim
[k:)))
lim 1000 2
||r(k))]1
1 - B [|>(k:)] (ka) w(kk - 1)ll
3 [|[(k:]]]? 1- [|r(k))]] = c0,
which leads to contradictory, and completes the proof of necessity.
On the other hand, if ||r(t)]] is upper bounded, since ((x(t) w(t 1)ll is also upper bounded, we have 1 [t]] + (rt), w()) w(t 1)) is upper bounded, which completes the proof of sufficiency.
The proof is completed.
Therefore, the last piece of this puzzle prove g(t) is upper bounded Vt 0. Lemma 16 (Second argument in Lemma 2). Let all conditions in Theorem 2 hold. Then, have g(t) is upper bounded.
Proof. We start the proof by calculating g(t + 1) - g(t). For any t 2 2, we have
8 B
g(l 1) g(() 1r(((((()))
(r()) (())
r())) + (r(1: + 1), woll 1) w(())
33
B
1 - 3 (r(t), w0() - w(t - 1)) - 1- (r(t + 1) rt),, wit + +1) w(t))
2 lr(++ rt)] + (r(t), r())) + 3 B
(r(t). w(t +o(++10 1) w(t 1) (w)
On the other hand, by simply rearranging the update rule Eq. (5), we have
1- (w + 1) + w(t - 1) 2w(()) = 1 - vL(w(t)) - (wo(t + 1) - w(())),
3
"
(28)
which further indicates
g(t + 1) - g(t)
2 |r([ -1(()+ + (10),,((+1-r)(()) + (r((), T V[(w((()-(w((t
"
(wol (w)((()))(((( mo())) )
1 |r(( + 1r((11 - - + (T()). - -log (1+1) in "
1- vL((v(()))
2
Denote Az(t) = ||r(t + 1) r(t)ll2 and As(t) (T(t), log (4:11 w 1----"sVC' V[(w(t))) We
then prove respectively Σ Az(t) and E As(t) are upper bounded.
First of all, by definition of rtt) (27), we have
t t+1
t++
At(t)
|10(t + 1) wt) + log
|000 - 2 log
(wot + 1) - w(t), w
t
+
2
(0)
[|w(t+ 1) 11-++1 w(t)] + log
||
(29)
t
where Eq. (+) is due Lemma 3 and log [+1)
(
Then only need to prove Eee As(l) < xo.
22

---

Under review as a conference paper at ICLR 2022
To begin with, by adding one additional term } i into A3. we have
As(t) r(t), On the one hand, by Corollary 3. (t)ll O (VE), which further leads to
1 - log +
1
i + r(()) 2 17
V[(w((t))
t
1-
||(((]]| = (+) + log(() |قم|| + ||:م||| = O(vi)
By 1 log s+1 O (2). we have
((++] 2
t ++1
1 13
rtt) w log
(30)
On the other hand, by direct calculation of the gradient, we have
r(t),
t 1
"
VL(w(t)))
1-8 B
N
r(t).
1
((w(()) +;))a
(1 B)N
N
(4) 1
r(), 1
Σ
17
Σ
El
((w,, x.) )::
N
81-
1 1-B-
(SE)
1
r(),
17
Σ
(7o- (()) + C' ((w(()), ((+)
1
r(t):
Σ
((((((t)
N
1-8
N
1 (S.)
*.ET(S.)
where Eq. (x) is due the definition of t (Eq, (12) with C2=
-
Denote
Aa(1)
r(1),
Σ (((w(()) oz))):)))))
&TET(S.)
and
As(() r()), 1-
Σ
1 (e
(1) + E' ((v((()), iss
(,ET(S.)
We then analysis these two terms respectively. As for Aa(t), due to E < 0, we have
1) Aa(1) S 1- B r(),
Σ
(((w((),
m.)) (x))
a
(S
By Corollary 4, we further have Vt > to
(e'((x(t), 2.1) s (1 + (m(()) (w(()),a)) s
<20 2c (m)(t).
which further indicates Aa(!)
Σ
e((w((t)) ax)) (r))
T (E.T(SS)(((M (1())
Σ
2e (w()) (r(1), a::)
1 ET (S, (0)
Σ
2e tr())+tog w.
(r(t), i.)
1-3 3
ET (ETT(S.),. ())))))))
"
(mxx (-
Σ
2e (ot)) (r(1), a.)
a (T) ((()))))
mmax; el ( (.++))
Σ
2c (r())_a)) (r()),
5
(6)
(max; - ++))
1
2N,
1 8
t
23

---

Under review as a conference paper at ICLR 2022
where 9 in Eq. (o) is defined
0
min (,,)(S,)
(ii, w) 1.
(31)
As Eist 1/2 <00, we have
20
Σ
A4(t) < oot.
(32)
For each term (r(t). 1- (e-(w.))) + l(ww, 2;))) 2. (#, $ T(S.)) in As(t), we divide the
analysis into two parts depending on the sign of (r(t), 2.).
Case 1: (r()), k 2 O. By Corollary 4, we have
(t),
7 (10.e)) + ((w, T.
I- B
(.) ll ((w, m.)) (x))
77
(w. + (1 + e (w0()) (e00))))) (r(t),
1-8
(0)
(w,@.) + + (rr
(r(0)) 2.) (r(1). ax)
where Eq. (0) is due to the definition of r() (Eq. (27).
Since (r()) m.) 2 O. further have
r(t). 1- 3 (2) + ((w, 2.))) az
7
"
c (wق + (1 + -4 (log (r(1)) tū (r (r(t), (x))
$
1- 8
(0) 1
e (1) + { + -+ t ( (r (r(t), xii)
1- 8
17
(1).a:))
(-1+ (1 t ( (((())))
(+()) (1))),))))
1 B
where Eq. (0) is due to (u) k.) =1 vZ, E T(S.). Specifically,
- -1+ h+ e e ( (z0, (r((),aa))
=- 1--- + (10 ( (2)))
a+o ++ 1 (1) (r(1),
Therefore,
17 1
(w:)):)
(1 (x))
3 t
< 1)
(w.
(a (+(()))))) (z)))
e
B t
< 17 1
E (1+
= [1+i]
[1 B)e |1+11
'In this paper, for a real series (r:) we use Eie Ta < representing Er. Ts is uniformly upper bounded for any T.
24

---

Under review as a conference paper at ICLR 2022
Case 2: (r(t), Ø.) < O. Similar to Case 1., in this case we have
r(t),
7
1 c (1,,))) + ((w, {;11 Φi
11
(10 (x) (1 ( e ((((())))) (r(1), mi))
1 1- 3
17
(0, 1 e-- ( (10)) 110 (r(1),
1 8
11
(10 (.) (-1+ + 1 e 1---0o00000-oo000o000000))) --(r))))))) --000)))))))))))))))) (r((), ti).
1 B
Specifically, if (r(t), x.) 2- -t -0.5p_
17 1
e (1),
-1+ (1 (e //
(r(t), at)) (1+ (1 - -- -- -0000)0)))) (r(1), 2b:)
1- B t
1
(10
1 B
t
17
1
-1+ (1 (1- - ((()))))))))) e (11))
<
e
1 /
+1+0.5p
20
[1+0.5m
where Eq. (t) is due to if (r(1), m.) 2 -1-
lim t+00
-1+ (1
)- = 0.
If -2-2 (r(1),
-t- -0.5p- we have
17
(w0 .b))
(-1+ 1 - -= e- -1(0))
(r((),
1- B
17
(1n .i)
-1+ 1
e -m00)a))) (r(1), ax:)
1 - B
e²p-
< 1 - B
17 (10 ..))
-1+
1
ti e (w,
e --(r(0ha))) (r((), (x))),
Therefore, when / is large enough, 1 leads to
3 eH
- (1) > O, which by e- (M(1),))))) > 1 1- (r(1),
1 1
e²u_
(1(0),0))) ) (r(t), a.,)
1
tu c a- (1)
1 B
t
1
1
(
-1+
1
e?u
t² - x (1,,5,)
(1 (r(t), (.))) (T(t),
1 3 f
1
1
-1+
ezu-
- - (10.6.))
( (1+ po.t )) (r(().
1
1
B
tM
1)
1
(10.6.)
1
1
(r(1), wx) << O.
10.5am
T0.6u=
1f-2 (r(1), 2.))
17
(10 )b:)
-1+ (1-E 1--00-(r()+oo (00 e -m(0))a))) (r(t),
1- 8
71
(10 ..)
(-1+ + (1 - (----(((())))) e- -(M0)))) ((())) (x)))
1 - 3
25

---

Under review as a conference paper at ICLR 2022
For large enough t, e -- (10(t)))))))))
2 and
7
3 c (w.#.)
-1+ +
- (1-0))((())))))) e e-(1(0..)) (r(t), 2.)
(1)
-1 +
e 1 ((u(1),aa)) 27) (m(1). a.)
3
< 1 ((
-1 + 2
(r(1), < 0.
B
Therefore, in Case 2., for large enough i, we have
( - (w + C(ww, k.)) 2i S (T....pp))
rr(), 1 1-
(.)
Combining Case 1. and Case 2., we conclude that
As(() 0 f1+0.544
which further yields
Σ t=1
As(t) <
<0. 00.
(33)
Combining Eq. (32) and Eq. (33), we conclude that Σ As(t) < co, which together with Eq. (29)
===1
yields Er + 1) - g(t) < co, and completes the proof.
We are now ready to prove Theorem 2.
Proof of Theorem 2. By Lemma 16, have gt)) upper bounded. Therefore, by Lemma 2, we have [t]]] is bounded, which further indicates ||ær(t) - log(t) is bounded.
Therefore, the direction of (t) can be calculated
w(t)
log(t)( i
w (t) log(t)
log(t)w
w(t - log(t))
+
[w]l
ww (t)l
log(() (1)
w(() log(()
[l]]l
(l)
log(1)) w
(as + oc).
(n(F) log i
1 (t)l i
log
The proof is completed.
B.2 IMPLICIT BIAS OF SGD WITH MOMENTUM
This section collects the proof of Theorem 3. Following the same framework as Appendix B. we will first prove that the sum of the squared gradient norms along the trajectory finite. One may expect ((w(t)) + B ((())) w(t 1) a Lyapunov function of SGDM. However, due the randomness of the update rule of SGDM, [(w(()) + 2n [[((() w(( - 1)ll² may longer decrease (we will show this in the end of Appendix B.2, please see Appendix B.2.3 for explanation).
2n
B.2.1 PROOF OF THE SUM OF GRADIENTS ALONG THE TRAJECTORY IS FINITE
We first provide proof of Lemma 3.
26

---

Under review as a conference paper at ICLR 2022
Proof of Lemma 3. We denote the parameter of the t-th step in Eq. (9) w. while that in Eq. (1) as w(t). With w(1) = (1), we will prove w(() w (t), Vt itterativll. Specifically, suppose for any 1 k < w(k) = (k)). Then, we have
( 1) - (o) (m) - (VLL(((()( (VV - 1)) + u(1 1)
+ u(()
= - 1jV B (w(()) + =a(1)
(LL(()((((k)) t(11) = Σ
(VLL(() ww()
k=1
Therefore,
T6(1 + = =Br((1) + (1 -B)u(L+ Bri(() -1-38 -3)
iv (B( +
k=1
which by iteration further indicates
1 Σ( gt+1 b) (LBc ww(1)
Σa (
w(++1) 2i(1
[-1
w(t) w(1 n
Σ (1 3* (CB))((())(((())))
and
1-2
w(t - 1) = w1 -
Σ
8d 1 [BB()
On the other hand, by Eq. (1), we have
w(t + 1)
(w( 17 ()VL + ((w(t) - w(t - 1))
1-1
-w( - -
(w((t) (1 3" ( ([ n (x)()((w(tt + Bn
Σ
- / v ( (w)))))()))))))))))))))))))))(
km
-w(1) - Σa (1 get - V z 1).
The proof is completed.
Using the alternative form given by Lemma 3, then prove Lemma 4, which indicates [(u(t)) is proper choice of Lyapunov function.
Proof of Lemma 4. We start the proof by applying the Taylor's expansion of L at the point u(t) to the point u(t + 1). Concretely, by Assumption 3. (S), we have
H Clu(t + 1)) & ((u(t)) (u(t+ u(t), vc(u(t))) ||u(t + u(tt)12
which by Eq. (9) leads
Hn 2 (VLn)(ww())I))
L(u(t + 1)) & L(u(t)) VVV vl(u(t))) +
(34)
27

---

Under review as a conference paper at ICLR 2022
Taking the expectation of Eq. (34) with respect to w(t + 1) conditioning {w(s)) we have ( + (w))
EB [CuolllCtttttttt + 1))(((+++))))
<EB( - (l (V) + H
| B() (w(s))
2
- [(u(t)) - (V
Hij
BB()
(ww()(
2
(
3 (((()))))(((((t))) V(((()))))
Hij2N [VL(w(t))]
(35)
26y
where Eq. (+) due to that w(t + 1) is uniquely determined by B(t) given {w(s)) Eq. (o) is
due to (() is uniquely determined by (w(s))a=1- and Inequality. is due to Lemma 12.
Therefore, we have
H
- (((()))))((((()())) v((u(t)) + 2by² [VL(w())]]
=l(u(t)) 7 (V (t)), - - (((())))))))(VV((()))))))))))))) -V((()))V(())))))) + 2by²
(VL(((())
HĀN
-L(u(()
vl(a(()))
217,
Hij
<L(u(())
[|VC(u)(()]] + [ (1)) + [V[((()) v
2bn?
1
HN
-L(u(t)) 7
1
2
71 [VV(((()) + - -
2,n,3
By Assumption 3. (S), E is H-smooth, which further leads
[VL(w(()) - v = Σ
(C w()) C(( u(()))) a
MES
2
2
Σ
(e((E, (((
S
H Σ
(ã, w(t) - (2, (.,)())))
&ES
#cS
< <H2 - u(t)ll? (0) H2 N2 32
(1- - 3)2 (|w(t) wit 1)1
32
Σ n VL
=22222233 32
Σ g 1- 2 v VL (CB((
(1- 3)²
N2
8
BB(()) (w) (m)())]
72
H2 N2 B2 72
8
VC n m (s))))
Σ st-
12 (1
8 VL (2) (w)s))))))
(36)
where Inequality (C) is due to (() - wit - 1)) = (1 - (u(() w())) by Eq. (9). Inequality
(o) is due to triangular inequality, and Inequality (+) is due to Cauchy-Schward Inequality.
28

---

Under review as a conference paper at ICLR 2022
Combining Eqs. (35) and (36), we have
sc(u(t)) - 1 (1 (1-(2 2
2by/ 8) [[V((((()))++ 1 122
HN
1-1
Σ
gt-1- [LB(
72 -3)
which by taking expectation to {w0(s) leads to E + 1))] = E ((n(s))]s [L(u(t + 1))1
<BxF((u(() - -E,, (1
2 +
HN
i [VC( 12
3 3--1-1 [[BB)
1-4
2b7y
(2 -B)
=Ey,c(u(t)- - (1 (1- +
HN
n E,, [VC((()))+ 2 72 B)
11
g B Bftt [
20///
8 (1-9)" 1-
By Lemma 12 and 17 < min
). we further have
2H-N232 by
E 1))] = E ) [[((((+1))
<By,flu(t)) 1 1 (1
HN
+ 20n 8i E,, (VC(w(())
2
1 18
gr-1-sEa Ex, [[L((()))]
+ 2 2
1 1- 3 7 E, [VL(((())) {Bz,C(u(())
[-1
4 1j
Σ 8 #=1
Er,
[I
(37)
Summing Eq. (37) with from to T leads to
E[C(u(T + 1))1 = I
[C + 1))1
<l(u(1))
T
7
Ey, [[w((()))
T
3
7
[-]
g Ey- [[
2
4
t=1
==1
=[(u(1)
7 R,
V
C(
(1))
1-3 3
g1-1-aE, Ey, (L((())))
2
1=x+1
T
<c(u(1))
7
F
V
((0(1))
Ex, V[[(u(>))]
2
7 E,
sc(u(1))
[L((it))
4
=L(u(1))
E [[
The proof is completed.
As L(u(1)) is upper bounded, we have the following corollary given by Lemma 4. Corollary 5. Let all conditions in Theorem 3 hold. Then, we have
[(w(())) < oo.
(38)
29

---

Under review as a conference paper at ICLR 2022
Consequently,
8
[V((((t))] <0
and
(w(t), + 00, Vu E $
hold almost surely.
Proof. By Lemma 4, we have for any T > 1,
Σ [E]V((((())1=- & ((u(1)) - EE[((u(T + 1))] = f(u(1)) < 00,
which completes the proof of Eq. (38). The rest of claims follows immediately by Fubini's Theorem and Assumption 2.
The proof is completed.
B.2.2 BOUNDING THE ORTHOGONAL PART
Similar to the case of GDM, we define vo as the solution of Eq. (12) with C2 (1-8)N- We also let ntt) be given by Lemma and define r(t) in this case
r()) - w (t) log(t) i n2t).
(39)
As V is a constant vector, and [[]] + 0 as f - co, we have w()) - log(t) has bounded norm if and only if [|r()]] is upper bounded. Similar to the GDM case, we have the following equivalent condition of that [[r(t]]] is bounded.
Lemma 17. Let all conditions in Theorem 3 hold. Then, ||r(t)]] is bounded almost surely if and only if function g(t) is upper bounded almost surely, where Z - R is defined as
1 ((1) 2 2 |r(011 + I- (r()) w(1) wit (o(t-1) 1))
3
8
(r(7) r (---r((-1)))) 1), w(() w(( - 1)). (40)
Proof. To begin with, we prove that almost surely 2
(r(T) r(T 1), ()() - -w(T 1))1 is
upper bounded for any By Corollary 5, we have almost surly
[((w(t)))
On the other hand, for any w. have
|/ [VL =
Σ (((w,ā))
(t)(B(()
- 1
b Σ
C( a)) <
Σ
((w,))))
(ET(B())
#ET(S)
< b
1 Σ
((w,,
1
Σ
((1,, 2))²
||
b
N
TET(S)
@ET(S)
N VVC(w))
by
Therefore, we have almost surely,
v (w())) <
30

---

Under review as a conference paper at ICLR 2022
which further leads to almost surely
wt(t + 1) - w(())]
S n7
8
V n (
Σ 8 VL (LL(s))
1=1
8 VVL,))
1/2
gt= VLB(s) (w) (s)]]
3
11²
( <0.
By the definition of r(t) (Eq. (39)), we further have
E(((n) r(r- 1), w(T) w(r - 1))
(r(()) - -r(r 11,, (T) - ww( 1)}1
r=2
Σ
( (T) - w(r - 1) - log
T [ - (n((T) - n(T - (T() w(T -11
r=2
T ++1 - -(n(T) - -n(TT= - 1)) (0(7 w0 -1))
[u((T) - un(r= - 1)112 +
log
r=2
T=2
3
Σ (|w(T) w(T 1)11 +
1
Σ
log
T 1
(n((T) n2(T -1)3
2 7=2
2
T
r=2
(+)
1
1
$
(|w(T) w(T 1)11² +
0
00,
2
7
2
where Inequality (+) is due to ||m(T) n²t - 1)ll O and log -يت = (
Therefore,g(e is upper bounded almost surely is equivalent to } [|((())]++++ (r(t), vo(t)-w(t 1))
upper bounded, which can be shown to be equivalent with ||[(t]] is bounded following the same routine as Lemma 2.
The proof is completed.
As the case of GDM, we only need to prove g(t) is upper bounded to complete the proof of Theorem 3.
Lemma 18. Let all conditions in Theorem 3 hold. We have g(t) is upper bounded.
Proof. Following the same routine as Lemma 2, we have
g(l+ + 1) - (()) 1
- (r(( + -((r) (+(), - -()) + (r()) +00++((00- - (LB()(w(()) - (wo(++1) -w((1)
"
where Eee ||r(t 1) - -r())1 is upper bounded.
31

---

Under review as a conference paper at ICLR 2022
On the other hand, by the definition of rt)) (Eq. (39)), we have
r(t + 1) r(1)
[++1
=w(t + (tt) log
n(t 1) m(t),
while by Lemma 9,
N 1
Σ (((())
v,ē; log
(
++1
v + n(t -)(())
b I
Combining the above two equations, we further have
N
r(1 + 1) -((() = w(( + 1) -w(()= bt
Σ (BB))S)))
which further indicates
g(t+1)-g(() = 111((++1)--((111)) ((()) "
1-6 (CB()(w(t))
N bt (B(()))
E u
Therefore, we only need to prove 2 - - VL(w(t)) be (B)n))) v,ãi)) < co. By directly applying the form of VL(((t)), we have
r(), 1 VLB()(((())
7
N
Σ
D
S ())))((()))
rt),
Σ
((ww(t)
N
Σ
U,
(1 B)b
bt
(T(())
t (B(()))s.))
1
r(t). Σ
((w((t), +;)))
N(1 3)
U,Y0
(1 Byb
1
t
()())(B()))
(B())))(())SS))
77
r(1),
Σ
((ww((,,))))))
(w. Ki
(1 BBb
(B(ET(B(S)
E (((.)))())
17
Σ
(Ee((x(t), (()) - 1 - ((( (r())
(1 - BBb
iā ERLET(IBE (B()ns))
17
Σ
((m))((()
(1 Byb
t: ((())n))
Let A6(t) Ei (-e(((((),,:))) a:)) - -e (w0)),.))) (r(t), a.), and Az(t) (1), )..) We will investigate these two terms respectively.
As (w(t), a) + t0, Vo E T(S), a.s., we have a.s., there exists a large enough time to, s.t., Vt 2 to. Vo T(S).
[(((w(()) .)) < (1 + e n+ (wo(t)))) ( (tw((t))))) _e((w(t), 2.)) 2 (1 -p (wo(1).0) ) ((w(())
(5. w()) 0.
32

---

Under review as a conference paper at ICLR 2022
Therefore,
Ar(t) -
E
iT (B()))))))))
Σ
(1+e ( (w(t) (r(t), +
<2
Σ
(00--D 2;) (T(1),
(B)))))()))))))
(w+n()),ū))) (00000))000000000000000011111111 (r(t). 2.
(o(0),..)222
to
())))8))))
(
Σ
--(++n(1))0)) (r(()),0.)0
t
(o)
10
where Inequality. (+) is due the definition of 0 (Eq. (31)), Inequality. (t) is due to (r(0) (r(1), 2.) S e__ and Eq. (o) is due to lim (w++)(t)) e (w,8.) Thus,
Ar(t) < <0.
On the other hand, Ac(() can be rewritten as
Ao(1)
Σ
(- (-e((0(())
-e (w000))))))) (r(1), a:) (+0))))20
i: (B()))))))))
Σ
(((((((),
1 --- )e((0(())2))) (r(t), (r(1), (1()),)))
(()
If (r((),, 2 0. we have for e < 0.5,
((w((), xx)) 4 (w(()))))))) (r(1),
(1 + (0(()))(((())))) (m)()), 1 (w(t))aa)) (r(1), #.))
[1 ++e (T(()) b1g (1))+) _.e -(000))))))) (r(1), m.)
+ e 1h (700))00(((0100000000000000 (m()))+ 1) 1
& (r(t), -.)e (1b((),a))
1 - (0(()))((())) -1) (r()), aile (10()),0))
|
124
1
(0.3--) )) e (0(0)))))) -1 (r(1), - (1)())))))
1
1 O
814+
(r(1),a.)) - -1)
1
(tt),,
t::ee (1)))) + to [min//440.3-e)
1
(r())) (r(t), (1.
7
0
1
e (+(1)))))))) (r(1): w.)e (1)()))))) (w))))
[miu 0f5
(0)
1
|
where Eq. is due to (1) O (( and Eq. (o) is due to (+(000) (r(1), w.) 5
33

---

Under review as a conference paper at ICLR 2022
On the other hand, if (r(t), .bi) < O, we have
((w(t)) x()) { e -0001)))))))) ) (o((t), ab))
1
(1-e-- p- (w(0((()))))))) e (w((0)))))
- 1 -1000001))) (r((), m.))
1 aw) (-1+ 1--em-(o0()) e (((0)t(())))))) (r(t), at))
Specifically, if (r(t), 2- -t -0.5minnfuup0 00.5.
(. (-1+ + (1 e ((((()(()))))) ) (r((1), mt:)
-1+ (1- (100))(())))22)) e (1()))+(())) S +00.5 ( 0.53 e _(t
1
where Eq. (L) is due to that as (ww(t), (x:) + co and (00, + 0 as t + co, there exists a large enough time T, s.t., VI > T, under the circumstance 0 > (r,)), 2- -1- m0. 0055] (()))) < 1 and e (wo(t))) < <.
If -2 < (r(1), at)) < -t 0.3mii 0.5), then, for large enough t, |(0;, n(t) 2, 1 c" (- (-0,2;))+4)
0, and
1
(-1+ [ -- (w(1),e)) (-000+)(())))))) (r(t), ai)
8
(1).
(-1+ 1 e e. (r(t)+ ( ((())(()))))))) (r(t),
-1+ - (.)
(+...))
H² --0-00(0))))))))))) )--m()--0))))))) (r(t), a.)
elt (1)+))))++4)
e x- (0(0))))t))))) (r(1), 2.)
<
-1+
W4-
e (11
(t. (.))
-1+
(1 1- (r()) + (()) (r(1), mx)
e (-(10
(1+p- 0.5 (u 005) - - (m(1)) (n(1),zz)) 2.1)) (r(1), a:)
-1+
yu
e (-(10
(1)...))
-1+ 1
11+
+ (-005m)ln( (r((). m.)
tu
e (#))
(-1+1 1 u_t
0.S (M- 0.5)
+ +o
0.5 (10.5minf/a.0555) (r(1), 2x) <0.
If 12-23 > (r(1), az)). then for large enough time t, e- (+(0))+)(())))) > e 1 e (ww((())) 2 b
and
1 (.,
(-1+ + (1 e- (mot))at))) e -(())(())))))) (r()),
t
1 - a.)
(-1+ e) ()()) < 0.
Conclusively, if (r(1), a):) < 0, for large enough i, we have
(- - ((1((()))))))) =e ((0(1).a.)) (r(1), 2.) 5
1
f1+0.5 pー 0.5}
34

---

Under review as a conference paper at ICLR 2022
which further indicates, for large enough we have
At(t) max {o
(1.0.5min(u-- 0.5) ( )0
1
1
fmin 1.5-
which indicates
Σ tm1
As(t) <0.
Therefore,
(t 1) g(t))
)
|l((tt + 1) r(t)]l+++ + r(f), 1-3 (LD(()
N
Σ
bt
(BB.ET(B())SS.)
2 (llr( + 1) - -(())1
+
1- Ac(1) + 7
"
A7(1))
1- 3
<X.
The proof is completed.
B.2.3
EXPLANATION FOR PROPER LYAPUNOV FUNCTION
Based on the success of applying Lyapunov function [(u((t) + 2 [1=(t) w(t 1)1|2 analyze gradient descent with momentum, it is natural try extend this routine to analyze stochastic gradient descent with momentum. However, in this section, we will show such Lyapunov function not proper analyze SGDM as this will put constraints on the range of the momentum rate Specifically, at any step i, since the loss L is H smooth at w(t), we can expand the loss L in the same way as the GDM case:
2n
H C(w(t 1)) <L(w(t)) + (wot 1) wt),, VL(w(t))) + w|w + 1) 2(t)
2
By taking expectation with respect to wt + 1) conditioning on fwr(s) for both sides, we further obtain
Ew(t+1) [[(w(( 1)) (s)
H
<C(w(t)) + (Ew(e+1) (t + 1) w (s))) v((w(t))) +
2 Ew((+1) [1/o(t + 1) - ((())){(((())){=
1 " [(w(t)) + (Bm(eti) [w(t+ 1) w(t) [w(s)][_]]]] (wi(t w(t 1)) Emo(++1 [wot+ + 1) w(() (((s){((s))
E Bw((tt) [1|2(( + w ( 2
[w(
-[(w(()) + ((w(l) w(1 1)) Ew((+)) (wl + 1) - w(l) (woss)
7)
H Ew((t1) [1|e0(1+ + 1) - w (1)1 | (w(s))
-1 1 [ [wol 1) w((1) (w((s)
8 <C(w(tt)+ + ||w(t) ww( 2 + 2n || [Eu((e+)) (2o 1) - w(t) (w((s) |
2n
H Ew((tt) [l| + 1) (t)ll (w)s)
1
Emi(t)) [wot + 1) w(t) (w(s)) 1|
17
where Eq. (+) becasue E [w + 1) w(t) (w(ss)
-n)((w(())
(w(1)) wll 1)) due to the definition of SGDM (Eq. (1)). Rearranging the above inequal-
35

---

Under review as a conference paper at ICLR 2022
ity and taking expectations of both sides with respect to {wo(s) leads to
1m((+1) [C(w(t + 1))] + 2 - 3 E (w(())) (u((++) [w(t+ + 1) - w(t) [[w(s)]
]]
2n
H B (w(w))11 [1120(1 + =(
2
3
((w())((((()) + E ((m())) (2o(t) w(t - 1)11²
(41)
2n
On the other hand, we wish to obtain some positive constant a from Eq. (41), such that (at least),
E [L(w(t + 1))l + (B((())) (to(t + 1) w(t)ll
(lw())((((()) + (w())) (1w(1) w(t 1)ll²
(42)
which
by E (w(o)) wt( + +1 w(t) (w)())) B (w(t + 1) w(t) [(w(s)) ]| ((o()))) (wu(et)) [wo(t + 1) (())
requires
to lower bound
However, in general cases, only upper bounded by (Holder's Inequality), although in our case, can be bounded as [Ee(+t) (20 + - (x))))))) |||
((w(s))!Ll
[ww(++1) + - (w)
V[) + w(t 1))1|
ww( - 1))11 + (8m((w(t) - w(( - 1), -V VV((w(t))
=
while (w((++))
|| w0l + - w()] [(((s) can be calculated as
Ew((+1)
w( + 1) -((((
=EB(()
V L (1)) (((())))(()))))))))))))))))))))) wil
1))[|
=EB()
V (10))))) - -w - 1))1 ( w()),(())))))))))))))))))))))()) w(l 1))
|| -1
(1))) (0)))))+ w(t 1))11 0 (n) w(t 1))
N
[1=) w(t 1)) + + 1))
N
|1 (t)) (1 w(t - + 2n ( - wo( 1)))
b
N
(w(t 1) w(t) [w(()))
111
(43)
By Eqs. (41) and (43), we have that ensure Eq. (42), it is required that
2 - 3 by²
H
0
2n N
2n
which puts constraint on 3 that
2/ 2 Hn 1 2
3
x 1+ 3
Specifically,
which approaches 0 when y approaches 0, and constrains in small
range.
36

---

Under review as a conference paper at ICLR 2022
C IMPLICIT BIAS OF ADAM
This section collects the proof of the convergent direction of Adam, i.e., Theorem 4. The methodology of this section bears great similarity with GDM, although the preconditioner of Adam requires specific treatment for analysis. The proof is still divided into two stages: (I), we first prove the sum of squared gradients along the trajectory is finite. Additionally, we prove the convergent rate of loss O()); (2). we prove w(t) (tg i has bounded norm. Before we present these two stages of proof, we will first give the required range of 1) for which Theorem 3 holds.
C.I CHOICE OF LEARNING RATE
Let H., be the smooth parameter over [so, 00) given by Assumption 3. (D). Let B2 = (c3))* (c 1). The "sufficiently small learning rate" in Theorem means
VEinf122
1- 1-8 1-(0,))
T- a-- [(
1) S
H He-1((1-031) (NC(0-))))
To ensure 7 is well-defined, we need prove
8
1- 5 1 1- (c
inf
d1-B) - (cB,)(-1) 0,
(22
31
and we introduce the following technical lemma:
Lemma 19. Define fx(x) z(1-at-1)- Vt Z, 2. We have fo(x)) is decreasing with respect
1-r'
x. Furthermore, for any x E [0, 1). we have
f(x) 2 vf(tt).
(44)
Proof. First of all, by definition,
f(x) 1-
1- x
1 1-
x xl
I
x1
x(-1)
201 + x + x2-
is monotonously decreasing as 0 S < 1. Secondly, Eq. (44) is equivalent to
(1 - x²)²
(1 - x 2
(1 - r'-1)4 2
x 21]-
(1 - r²)3
(1 + x1) + 21)
(1 - 1=3 2
(1+ 22(+
The left side the above inequality no smaller than 1, while the right side is no larger than 1, which completes the proof.
We are now ready to prove 17 is well-defined. First of all, for every t, we have
- 31 1- 81-1 1- (c
- 31 c(1 - (1) 1 - (c31)--1
B1 (1 11
1 - (c 81 - 11-1) (cB:)(1 (cB2) 1-
1- B
1 1 B1
( (1 81-1)
(f((31) - fo f((r)) >
(45)
1- B1
where Eq. (x) is by Lemma 19 and es1 = -T/ 1.
On the other hand, we have
3
1- 81-1 1 - (cB1)²
-
lim 8000
(46)
3
c(1
31) - (c
By Eq. (45) and Eq. (46), obtain
1-8 3
1- (-(
lower bounded by some positive
-1-Bt)
constant across I, and 1) is well defined.
37

---

Under review as a conference paper at ICLR 2022
C.2 SUM OF GRADIENTS ALONG THE TRAJECTORY IS BOUNDED
We start with the following lemma, which indicates ((w())+ +())+++++++++++())))) w(l 1))1 a proper Lyapunov function for Adam.
Proof of Lemma 5. We start with the case t = 1. To begin with, we have & is (N(()))(( smooth around w(1). By definition H, is non-increasing with respect to and since (-1 is also non-increasing, we have
Hg (NC((C)((L & H3 ( NC(w(())
which further indicates when a is small enough,
(+) [(ur(1 + a)) S [((((1)) + a (VVV(VV(())) (r(2)-a(1)) mn(1) + 2/20 a 2//2((2)) - wr(1)ll
L.
1
v((wo(1)) ) + o(a²)
-[(w(1)) - a VL(w((1)
Vella + (1)
La² Vella ((1 о (w(2) w (1)
SL(w(1)) - 21
where in Eq. (+) we denote L - H Hg-1( NL(w(L)))) and the last inequality is due to 2n a
Vela+ (11 @ (w(2) w(tt)|
1 o(a²), and (VL(w(1)), Velstor @ vl(w(11)) is
positive.
Now if there exists an a E (0, 1), such that Eq. (10) fails, we denote a" = inffa (10) fails for 1 + a). We have a > O, and the equality in Eq. (10) holds for + a². Therefore, we have for any a E (0,a*),
[(w(1 + a)) ((w(1++)) + 2n
1 a²
VEll+ + #(1) @ (w(2) w(t)) ((w(1)),
which by Lemma 10 leads to L is H (N smooth (thus L. smooth) over the set {un(1 + a):
E [0, (1), and
[(w((+aa))
<L(w(11) + a² (V w(2) w()) + [ (a")
w(1)
(
1
+ T. (aa))[[w(()) =1]l
=[(w((1) a²
cll (0)a+0(1000 (w(2) w()) w(2) -w(1) )
2
=[(w(1)) a²
1
V 11 + (11) 2 - w(1) (w)))) + マタ (1))2
L
3 Vel.+ o (((2)-w(11)
7
+ +01)
sC(w((1)) a² 1)
e1 + (11) 2 (w w(1)
+ 2
(a*)²
V/el+ 011) @ (w(2) - w w1))
- (C(w((1))((') = !
Vela+ + (1) 3 (w(2) w (1))|
2 (a')²
L
VElla+ (11) 2 (w w (1)) 2
1
SC(u)(1)) (2*) 2n
1
/ell++ + ((1) 3 (2) w0 m0))
(47)
where the second-tor to-st inequality is due (2 - w(1)l (by Lemma 13) and a (a*)
while the last inequality is due to
Vinff22
(1-8) 1-91
1 1-8 1-(e3,)' o(1)))) (1(
V8
11-8 1-6; 1-(c8,)² )²
1-91
e(1-8)) (-(09))
1
5
L
Vē 1 31 [+(e)1)
VE(1
V8
2
1
L
T
38

---

Under review as a conference paper at ICLR 2022
Eq. (47) contradicts the fact that the equality in Eq. (10) holds for 1 + a", which completes the proof of 1.
If 2 2, following the similar routine as t 1. also prove Eq. (10) by reduction to absurdity. If there cxist t and a such that Eq. (10) fails. Denote t* as the smallest time such that there exists
[0, such that Eq. (10) fails for t and a. By Lemma 13, 2 is positive, and strict inequality in Eq. (10) holds for
Vell + itt - 1) @ (wo(t) - w(t" - 1))
t and a which by continuity leads
1> a - inffa e [0, 1]: (q.(10) fails for 1 + a) > 0.
Then, for any [0, a, we have
[(w(tt +a))
<h(w(l' + +a)) + -0² 1- 3
Vsll + 0(1)) 2 (wolt" +1) -1)--((("))) w((')))
111 - -1
sc(w((()) + 1- 3//-11 -1 1- (cBi)²
vela+ (wo(t) w0( - 1))
201(11 - B1) (cB: )C
On the other hand, for any time S 8 S 1x - 1, we have
C(w(s + 1)) 1 84
2 27 - 31) Vell + {ss o (w(s + 1) - w(ss) w()-)(s)) 2
SL(w(s)) + B1 - 89 1 - (cBB)
2on - 81) 1 - (cB1)=-1 Vell + i(s 1) 3 (ww(s) - w(s 1))/ (48)
By Eq. (46), we have
1- ,9
> 1 1- 3
1 1- 34 1-((6) (c5) o+1 1 - (c
711 - 31)
en(( - B1)
en(1 31) 1 1- (c 1 - (c3)) )
which by (1-67-1 1 further leads to (1- --)
2cn - 31) (c32)s )a-1 V + iss 1) 0 (w(s) w(s 1)){²
1 18-1
1 - (cBi)²
((w(s))
2[ww(s + 1)) + 1 1 81
2 n 31) Ve1. d + (ss) @ (w(s + 1) - w(s)) 2
>(uuss + +1) + 20 {1) 1- (c8))* 1- ++1
81
1- 1-(c8) (cB]) - (cBi)²
Vel + +(s)) (w 11 (w((s+1)-w(s)) -))=-(s))]
m(s))|{
1 1- (c(1))
1- B 1 1- (c3])=+1
Vella (0la+0(s)00 (0)) 1) co(s)) ((²
[(wo(s + 1)) + 2en((1 - B1) (c
(43
(49)
On the other hand, for 1, we have
1 1 - 81
Wella+00 + 0(1) @ (un(2) m((1)) |
[(w(1)) 22))
2 17 - 31)
1 - (cB1) (((u(2)) +
1- B1 1 (c8))2
|| |VeL++ + x(1) @ (w(2) m()i)l²)
(c3))²
2cn(1 - 81) 1- (c81)
(50)
39

---

Under review as a conference paper at ICLR 2022
Combining Eqs. (48), (49), and (50), we have
L(uo(1" + a))
2011(1 - 31) 1 (c31))--1 Vela + f((" - 1) o (wo(t) - -w(t" - 1)) |
1 88
1 - (c3i)
<((w((+))
1 (c81)*
201(11 B1) (c3)) )2- Vela+t(t* D(t 2) (w(t 1) w0(t - -2)1((
1- 0/- -2 1 (cB:)**-
((w((t-11))
(cB2)(-1
1 (cB1)*
[((w(2)) + 1- 91 1- (cB1)²
V + +11 o (w(() - - 1')
(c31)²
207/(1 - B1) 1 - (c3))
1 (c
1
((w((1)
< 1- c3 (Iw(1)).
cB1
Therefore, by Lemma 10, is N a0, which further leads to
(L)())))) smooth (thus L smooth) over the set (w((t +a)
+a")
{((w(tt)) + (V wit +1) w(t')) + L (a (11(" + +1) - ((t))l2
2
a'
(wit" + - (1 3f )v Vela + i(t*) o (w(t" + +1) - w((²))
11[1- 31)
- 3:(1 - "1"'"W ((t*)())))) o (w(tt) - wo( 11))
+L(w((()) L (a")²
|| -1)- (12
2
=[(w(t')) + (a") )²
L
1100tt + - w(t
|| w1)- 1/11 31)
a²(1 (1-)
Vella + +tt) @ (witt + - m(( -))))
2
+3, a²(1 21-1-B)
8 -1
ww(t" +1) - w(t'), v E1l, 0(t))
(w(t") w(t - 1))
17(1 - 81)
=[(w(t')) + L
(an))1|e(( + +1) +1) w 1/(1 31)
a-(1-
Vella + ((t)) o (wit + - w((")) -1)))(tt))]
2
+31 a² a- (1-
Vella +
Vel + i(t*) 3 (wit + +1) - wv()))
1111 - B1)
VEla+ + +t**)
el + 0(t
C V + 0t - 1) 2 (wv(t) ww( - 1))
Vel + +((1)
L
a² )
<((w(t))) + - (11(tt + +1) - w((")))
Vella ((t*) @ (w(tt + 1) - z0())w(())
2
7(1-81)
+31 (a (a - -1
VELx + i0t-
c Vells + x(t*) o (wo(t" + +1) - -w((t))
21 - 31)
VEL + ((t*))
+3 (1- -1
$ Vela+ D(10 -1) V/La + +((t))
Vel, + 1(t 1) o (wo(t)) w(t - 1))
2y(1 31)
40

---

Under review as a conference paper at ICLR 2022
(0)
L
a² a² ((1-81) 8
o (w(tt + w((*)) /
S [(w(t))) + 2 (a Flw((t + w(())
v
111 - 31)
+31 (a (a)) 1
1- (c31)*
Vela+ + (((1) 3 (w((t +1) - -w(("))
21 - -1) c3i (c3) (c31)
+31 (1- (1- 0/- -) 1 1 (cBr)*
21 31) cBI (1 (c31) 11- VeLa+ 1(t - 1) @ (w(t") w(t 1))
s((w((()) + 2 (a') V ((t)) ① (wit + - ((*)))
a²(1 - a'(1- )
VVEl + VEIl+ @ (w(t" + w ()]
m(1- 31)
+3 (a0)²(1 )
1- (c31)*
V Vela+ + + 3 (w0(1" +1) - mo(rt)\|
21((1 - B1) c3: - (cB) )r-
+31 (1-
)5 (1-85)
1 (c3))
Vella + 0(t O - 1] 1 (wo(t)) - -w(t" - 1)>|
2n(1 B1) cB1 (1 (cB1)
(0) [(w((()) (a+)² (P11-95 )
(w(l( 1) - wwwww()))] w(())) /|
21 - (1)
(1- 84 - 1 1- (c
Vela+ D11" - 1) o (wi(t) - wil! - -1)] w((
211(1 31) c(1 - (c
where Eq. (+) is due to alternative form of the Adam's 's update rule:
(1- 8 V + @ (wo(t +1 - wx())) - (1 - 3 -"" O(t - 1 17(1 ())V(((((()))
o (wi(t) - wit - 1))
(51)
Inequality (o) is due to
VEla + ftt 1)
Ella + Ett" 1)
Eld + ftt - 1)
Vel. + +(11)
ell + i(tt))
ela + Brv(l (1+11)))V
1-1h
eld + D0t" - 1)
E Ella + V1t* 1)
Eld + it -1) 1)
ala + Bou(t--1)
Ell + 82(1 12(1- 10
Bal1 m -1p00- E1 +
Bal 22(1-85" 10(00
1-33"
BB
1-13
1-
1 1 1-38"
La (all the computings are component-wiselyy)
32(1 - 3/- -1
and (((3)) Vf(()))) and Inequality (O) is due to
L inf
1-8 1-31
<11-A]I-1e31)
c(I-At
1-8 1 1-(08))
1-(e3]
1-0f"
1-81
1- 1-(c8,)
o(l 1-(c
2
27
2m
Vella + ((t)) o (wi(t + +1) - ww+t)) ||/
a² >>>(0) (a*),, and
> O.
This contradicts to that the equality in Eq. (10) holds for t" a-
The proof is completed.
As lim B 0 and lim = 0, we have the following corollary based Lemma 1.
Corollary 6. Let all assumptions in Theorem 4 hold. Then, for large enough I, we have
1
L(w(( + 1)) + 2 - 8,)
Vella + i(1) +(()) @ (ur(1- 1) - =oo
<L(w(()) + 2 - 31)
Vell+ O(t 1) ② (wi(t) w(( - 13)
(52)
41

---

Under review as a conference paper at ICLR 2022
Consequently, we have
[[((((t)) <o.
(53)
The proof of Corollary 6 requires the following classical lemma on the equivalence between the convergence of two non-negative sequence. The proof is omitted here and can be found in Wang et al. (2021).
Lemma 20 (c.f. Lemma 27, Wang et al. (2021)). Let {a | be a series of non-aagaiive reals, and be positive real. Then, Ei= 0g < co is equivalent -i=1 Ve+2%-1 a. XC.
Proof of Corollary 6. We have
lim 1- 19-1 1 (cB1)²
1000 2c1(11 - B1) - ((B1)t-1 2cT( - B1) <
2/on( 1 - 31)
1 1- 13
lim (+0 21y(1 - 31) 21/(1 - B1) 2 V - 31)
which completes the proof of Eq. (52). Rearranging Eq. (52) leads to
v6-1
| Vella + 0(1) @ (wo(1 +1 - mn())| 1 2 Von(1 - -1)
Vela+ + D(1- -
(wo() - w(( - 1))|
2von(1 - B1)
+L((w(t)) - ([(vo(t + 1)) + 2 - B,) Vell+ + D(t) o (w(t + +1) 11)++(1wol -0o(t))](²)
1
which by iteration further leads to that for a large enough time Ti
2 - 31) VVela ((t) @ (w(t + 1) 1000-wj-1 w(t)) |
VC- 1
Σ
Vella+ (ellaD((T)) - 3 (w( w(Ti 1)>|²
<l(w(Ti)) 2 - B1)
-L(w(Ts + 1)) + 2 - 31)
1
VEll -
@ (w + 1) w(l2 + 1)) |?
1 1) (w(Ti) w (Ti - 1))1
<L(w(Ti)) + 2/an(1 B1)
+
Consequently, we obtain
8
Ve-1 2 - 31)
VVel++ f(t) ( 1) w()])())) <o.
(54)
On the other hand, for any 4, we have
V E1la + x(t) 3 (w 1) w(t) VVEl++ 2 ró
/ella + 2(1) @ (ur(t + 1) wt)) eeela+0((0) +
3) = =(Vella + 0(t @ (wr( 1) - w(()), it
1711 - 81
31)
= (1) w
3 VVVL(((s))
1111 - -B1)
8
2 1((1 - -B1)
8
Σ
((ă,, w(s)) v
Σ 8 Σ
Cl w(s)))
1- 81 N
1- 31 N
E3ET(8)
s=1
a.ET(S)
7/1 B1)
(( w (t))) > 1 31)
Σ
VL(w(t))]l
1- (SE
1 31
42

---

Under review as a conference paper at ICLR 2022
which by Eq. (54) indicates
n(1 n(1-)1)
[L(w(t))]
<0.
1 89
Vela+ 0(1) o i
As lim
n(1-31)
- ())) we then obtain
1-88
8
[VL(w(tt)1
[L(w(t))]1
E
(t)(((
E==1(1
[[w((t))
1 oc
[V(((()))12
S dd
3
Σ (1 B)8 [[[((((]]]
1-ge
1
B
t=1
VeLa+ + E. (1- -10- VV)
[VL(2(1))12 2
V [V(((())]
d 10
2 <000
Vela D(t)
1
Vela + (Dta++(tto) Oz ②
which by Lemma 20 completes the proof.
Based on Corollary 6, we can further prove Lemma 6, characterizing the convergent rate of loss L directly.
Proof of Lemma 6. To begin with, Eq. (51) indicates
|lm(1 (()))(
(11 /1) ((t) @ (wn(t + 1) w()) - ( w(t - w()(=1)|1
< (1 (1 ellve1.+ +()) @ (wn(t + +1)
+ 1|11((11-11 - -
(wo(t) - wi( - 1)}
VeL. + D(1) @ (w(t + 1) -w()) + ||
w(1 1))
E1 + (tt) @ (wit +1) w(t)) + 0(t [
w(t 1 l'r
(55)
On the other hand, by Corollary 6.
VL(w(s)))] < oc,
which following the same routine as Corollary 5 leads to
(w((): x) - xi, Vo E S.
Therefore, by Lemma 11, there exists a large enough time Ti. such that Vt > Ti.
1
K ((w((()) x)) - - ((ur((())) .)) S K ((((w(()))))
va E T(S),
which by the separable assumption further Icads to
2
((w(t))
< 7 N *ET(S)
Σ ((w(()), x)) < N
Σ
(() y2
K
*ET(S)
1
Σ
E' ((w((1) ())
N
(E)
<
1
Σ
(((w(t) (KC(((())))
(56)
$ET(S)
43

---

Under review as a conference paper at ICLR 2022
Combining Eq. (26) and the above inequality, we have
n(1 n(1--1)7) 2 [(w(tt)² 2 (1 [1 /Ll o (w(t+1) -w()] (w(()) - wll1 wo(l 1)) -1)1"))
K
+ Vella+ + -(1 -
(57)
On the other hand, by Eq. (54), we have
Vela+000 @ (w((++1 - mn())){ < co.
Therefore, there exists large enough time T2, such that VI >> T2.
V Vela+ + E(1) @ (wo(t (0(t+1))u((1)) <1,
and thus,
Veel ((t)
((t) @ (w(t+ + - w(tt)|' < Vella e(t) @ (w(t + 1) w(t))|??
(58)
Combining Eq. (57) and Eq. (58), there exists a positive real constant C, such that
(1 (Ile +(l)a+(((0)+0)) ((1) 2 (ur(1 -
f(ur(1))2 sc
+ V O O(t - 1) (w(t) w(t -1)]|())
| Venl D(1) @ (wil +) - m(\)\| sc (IVeila+ 0(1) 2 (wol + 1) -
V + Ott - (w(t) wilt 11)1
+
Rearranging Eq. (52) leads to
-
(IVelatol D(1 ((L)) (w(() m(t 1))|
4/oo(1 B1)
+ Vela + D - (t) ww(t - 1> 1)|1?
f 1
Veld 0(t 1) 2 (w(t) - wilt - 1])1
sC(w(t)) + 4 - 81)
- ((s(un(t + 1))
Veela ((1) (wo( + 1) =0(t))(").
4 -81
44

---

Under review as a conference paper at ICLR 2022
which further indicates
gc+1 1
w(t - -1)1 /// 2
[(wu(t))+ + 4//o(1 31)
<2 (((u(t)))
y6+1
VeLa+ + 1(t
o (wo(t -w(t - 12/1
4//o(11 - B1)
S2C (1+ 40/e(11 - ) (IVell+ + f(t) 0 (w0(t + 1) - =((t))
V/ ve+1 1
+ || V + Eit 1) @ (wo(t) w(t - 1)) 1²)
Vc+1
4 4 - 31) (((u(t)) + 4Voa(1 B1)
Vo+1
52C 1+ 48an(1 - B1)
Vc ---1
Vela + O(t -0-11 1) @ (wo(t) w(t - 1>a| -(C(w(t + 1))
+
(') )
VEL.+ (11) 3 (1)
4 - 31)
Denote [(t) as
E(t) A [(w(()) + 4g/en11 - 3,)
+
|Vel++ + i(t - 1) @ (w((t) - w(t -)>|
+(tt
We then have
+2+1
4 4von - -11) fc-1
s20 (1+ 4ffan(1 - /3))
(E(t) - g(t + 1)),
which leads to
<(t) (1)=00( (!) i.c. [(w(t))= 0 ( (+)
and Vell a(t 1) 3 (wr(t) w(( |>}l 0 (
Due to Eq. (56), we further have VL(u(tt)) ((- which indicates
((()) mi (8)
[100 (100))1/1000( (1]] + lwss + 1) - (x)) = ||0 |)|| +1
eld
<]]w((1)]|+ +
|| (+)l = [1] + n
Σ
3 v ((w(i)
Ba)
i=1
<||w((1)|| +
go VV(w
VE(1 3)
i=1
<1|w(11)l+ +
7
VL( (log(t)).
VE(1 3)2
Therefore, for any & E T(S), to {((((t)))) = 2 ()( and thus ((w())) = O (). Also, since [(w(t)) = O(t ") we have (wo(), .)) = =((log())) which further leads to [|]]| (llog((),, and thus |u=()]] = +llog(())
we have (w) (log(t)), which by i expoeetiial--tlleed leads
45

---

Under review as a conference paper at ICLR 2022
Finally, we have
[L(w(())]]
7
Σ g' Σ
x))
=
N
sml
BET(S)
(((u(()), x3) -
Σ @ET(S)
(()=(s), T0
N
BET(S)
((w(s)))
|| (m)(()))] &
3 - VL(w(s))]]
which leads to [[((t)) = @ O(t Similarly, we have v(t) = O(t 3). component-wisely. As
lim /f 0 and Tim 83 0, we have
mi(t)
[(w(()) - w0( 1)ll
= 0((
V + ((t)
The proof is completed.
C.3 BOUNDING THE ORTHOGONAL PART
By Lemma 8, there exists solution v as the solution of Eq. (12) with C2 (1-BIVE' Define r())
as
r(t) w(t) - log(t) - w. and we only need to prove ||r(t]]] bounded over time. We then prove Lemma 7, providing an equivalent condition of []r(t)]] being bounded. As the GDM and SGDM case, we separate the proof into two sub-lemmas.
(59)
Lemma 21. Let all conditions in Theorem 4 hold. Then, ||([[]] is bounded if and only if g(() is upper bounded.
Proof. Following the same routine Lemma 2 and Lemma 17, only need prove
lim
(1 (1--8 1 0(t - 1) @ (w(t) w(t 1)) 0,
(60)
and
80
(r(r)- - r(r (1- -) ala
0(T 1) (w(() w(T - 1))) < 00.
(61)
As for Eq. (60), by Lemma 6, we have
(1 (1- - 1(1) (w((1 - wil - 1))
= =0(-))= = o(1)
As for Eq. (60), we have
((T)) r(T 1), (1 - BT- ) /lll B(T 2 (w(T) w(r - 17)
((()) w(T 1) - log
T --1 ú (1 - 0 21 (T 2 (20(T) - w(r 11)
т
log 1-1 w. (1 -1 -1--11 )) all Ü(T (w((T w(T 1))
(w(r) - w(r 1)) 2
+ (1 (1-81-1) 31-1) VElla ( )
w -
where Eq. (+) due to Lemma and log(.-)) O(T
The proof is completed.
46

---

Under review as a conference paper at ICLR 2022
We conclude the proof of Theorem 4 by showing g(t) is upper bounded.
Lemma 22. Let all conditions in Theorem 4 hold. Then, g(t) upper bounded.
Proof. g(1) is upper bounded is equivalent to Ei=1g((+)) - s(l) < co. We then prove this lemma by calculating g(t + 1) - g(t) directly.
g(1 + 1) (1)
VE
B1
rr( 1)112 + 1- B1
r((t + (i (w(t 1) - -w((t))
2
V
||((t]] +
31
(r(1), (1 -----)) a(t - 1) の (wo(t) - w(t 1)))
2
1 81
B1
(r(t+ 1) rt), (1 - VllVEL.+ (tt 3 (wit +) - w(t)))
1 31
VE
(r( + 1) - -r(t)]] + 1 31
31
(r(t), (1- V ((t) @ (wot - 1) - w(t))
2
-(1 87 12-1) cL. + iit @ (w(() w(t 11)) + Ve(r(t + +1) - -r(t),
(
r1), -(1 - /1 VeeVelatt
cla cla (() @ (wit + - wt)) -
1- 3 vL(w((t))
2 |r( + 1) -0((++)=r00]+++ VE(((1 +1) -r())((())
where Eq. (+) is due to a simple rearranging of the update rule of Adam, i.c.,
81
(1 - V)) p(T) e (w(t 1) - w()) (1 - 31' Vell D(L - 1) の (w(() w(( 1)))
1- 81
1-3 v[(w(() (1 - M1) / LL. ((() 3 (wo(1 + 1) w()).
1
On the one hand, as ||r(1 + 1) r (1)
1| + 1) - wtt) log ++1 w0 O(1-1),
|r(t + 1) r(t)l| < oo.
2
On the other hand,
r(t), -(1 - (1 +la+ @
" V[(w(t))
1 3
+ +e((r(1 1) - r()),(())
(MO), -(1 - / (L) @
17
vL(w(I))
- -i-11-1 3
+ Ve w(t + 1) - w(t) - log 1 w. r(t))
(r(0), -(1 - 51) ElL + f(t)
@ (w(t + 1) - -t)))) + VE(w(t + +1) - (1)-((t)) w())
+ (n(0). VE log
[+1
w
1 - B vl(w(t)))
"
t
0 + - + r(t), V log
[
v((u(()))
t
1-
where Eq. (+) is due to (() = (1 Furthermore, following exactly the same routine as Lemma 16, have
r(t), - VElog (+1 1
"
vl(w((()) <0..
w 1- 3
The proof is completed.
47

---

Under review as a conference paper at ICLR 2022
D APPLICATIONS&XXTESSIISS
D.1 APPLICATION TO THE MINI-BATCH SGDM
This section provides formal description of the implicit bias of mini-batch SGDM and its corre- sponding proof. To begin with, we would like to provide formal definition of mini-batch SGDM. Mini-batch SGDM differs from SGDM by applying sampling without replacement to obtain (t) in Eq. (I). Specifically, let K N. For any T 2 O, we call time series {KT + 1,... KT + K} the b
(T 1)-th epoch, and during the T 1-th epoch, the dataset S randomly uniformly divided into K parts { (KT + 1)...... B KT + K)}, with -I=KT-1 (t) = S. The implicit bias of mini-batch SGDM is then stated the following theorem:
Theorem 6. Let Assumptions 1, 2, and 3. (S) hold. Let learning rate n be small enough, and E [0, Then,,, for almost every dataset S, mini-batch SGDM satisfies w(() log(t)) is bounded as + oc, and lim
20(3) [x)]
The replaeetrel sampling method leads to the direction of every trajectory of mini-SGDM converge the max-margin solution, compared the same conclusion holds for SGDM a.s.. We prove the theorem following the same framework of GDM, by proceeding with two stages.
Stage I. The following lemma proves L(u(t)) is an Lyapunov function for mini-batch SGDM and without the a.s. condition.
Lemma 23. Let all conditions in Theorem 6 hold. Then, we have
[(u(t + 1)) s ((u(1)) P(()) Σ vL(wa()))11
Proof. By the Taylor Expansion of L(u(t + 1)) ut), we have
+T+T+++1]] c(u(KT+T+1))
K
SL(u(KT + 1)) - VL(u(KT+1)) + +1),
v (wyl KKT)
Hij + 2
K (wu+ (oo(t++K)]]
(62)
On the other hand, for any t E .2..... K). we have
KT+s
(KTT+ - w(KT 1
Σ
gKT+ '
VLB(((
1=1
KT+
KT Σ
Σ
gKT+s (((()((((())
+1 Σ
KT KT / (LB(e)
KT+1
#=1
1=1
g1-4+1
B(1
3r) KT
VLB(KT4((W(KT +f) +
gKT-L (((e)(
1-8 B
1 - 3 t=1
1
1-ge-ti
t
f1-141
Σ
(LnKTH (W -()) - Σ
(L + 1))
1-8 B
1-B
1=1
F=1
3(1 - 8t)
KT
- Bt-2+1 t+1
+1
9 gKT- VC C VL (w) +
V (WBKT++(W((KT + 1)),
1 8
1
t=1
1=1
48

---

Under review as a conference paper at ICLR 2022
which by 77 is small enough further indicates
1 KT + - - + 1)1l
1
g
gt-e11
51
VLB(KCH((O(KTTOO) +
Σ
(V 1))
1 1-3 3
1-3
t=1
1=1
[(1 - 8*)
1 -
+1
3KT VLB +1
Σ
(W 1))
1 1-3
1 1-3
1=1
KT
-0(
Σ [K(TT + - w w(KT 1)1+++00
Σ 3 -k
1=2
0 [V KT + 1))11
Applying the same analysis to || (KT + -) w w(T 1)ll recursively, we finally obtain
1w(KT + 1) - - (TT + 1)
KT
<O(n)
Σ I VLBc + O(n) [V[(w((T+1)] 1=1
(63)
Applying Eq. (63) to the VBn (w({)) in Eq. (63) (A) [1, KT)) iterative and choosing to be small enough, we further have
WKT +t) w(KT 1)ll
<0(n)
(3K(T- V 1))l] + +O(n) [V[[((XT +
=O(n)
Σ
(BK(T- [L -1)]]
12=0
Therefore,
(C(H+k((w(t+*K7)
(Cnu)x((u(tt)+
Σ
3K(T-1)
(unK + 17][]
k=0
T +0(1
= <KLL(w(() +0
V (k(T-() [
(64)
1=0
Similarly, one can obtain
v[(u(KT 1)) VLww((T + 1)) + ([]= - w(KT)))
T
=VL(w(KT + 1)) +0
Σ
(65)
49

---

Under review as a conference paper at ICLR 2022
Applying Eq. (64) and Eq. (65) back to the Taylor Expansion (Eq. (62)), we have
L(u(KT + 1))
<p(u(KT + 1)) 2(1)
+)) 1))
T
1
1=
Sp(u(KT + 1)) - (()) 11). + 1)))
1
BK(T [V
Summing the above inequality over T and setting 7 small enough leads to the conclusion.
The proof is completed.
D.2 EXTENSION TO THE MULTI-CLASS CLASSIFICATION PROBLEM
Here we use several notations and lemmas from (Soudry et al., 2018). We define w = vec(W). v vec W), e, Rº (i E {I...., .......C' C}) satisfying (ex), d.j, and A, @ Idx where 1dx the identity matrix with dimension dx. We still consider the normalized data, i.c., ||0||| v(x y) E S. Then, the individual loss of sample (æ, y) can be then represented as
e A.w.A
(v. Wx) = log Σ e(w.A..)
Furthermore, the gradient of training error W has the form
VL(w)=
Σ
(A, Ay)a.
N
2j=1 (A, A.)00)
(2.9)ES 1=1
and the Hessian matrix of can be represented
E (lw,,,;--Aii 1.0,-AA31 At)ar)
H.C(w)
Σ
(A: Ay)x((A) A,)x=
N
(2.))S8
ES= (A)-Aaa
one can then easily verify all absolute value of the eigenvalues of HL((w) ) is no larger than 2, which indicates is 2-globally smooth.
On the other hand, the separable assumption leads to (ıo, (A, A))x) >> 0, Vy * i, which further indicates
(VL(w), m) 0.
Let y To following the similar routine as the binary case, we have for random subset of S sampled uniformly without replacement with size b, we have
2N 7 V
|VL(w)]| < B (
(66)
Similarly, we have for any positive real series faz l
(()))\ < Σ ((()V[(((())
a (()))L((())
(67)
The proofs of Stage I can then be obtained with Lyapumov functions unchanged and by replacing the corresponding lemmas using Eq. (66) and Eq. (67).
As for the proofs of Stage II. the Lyapunov functions are still the same, while we only need to prove the sum of (r()), -" VL(w((() log -= - (for GDM, (r(t), - - (L((((w(()))
50

---

Under review as a conference paper at ICLR 2022
be (T((E)) vy for SGDM, (r(t).-vElos ( (1:) ف 1- [[(((t))) for Adam). For the multi-class case using GDM, We present the following lemma from (Soudry et al., 2018), while the other two cases can be proved similarly:
N
Lemma 24 (Part of the proof of Lemma 20, (Soudry et al., 2018)). If (tt):: (Ay - -A,)a)) - oc as t oo, V( y) E and Vi + y. we have the sum of (r(t), -13 VL(w((t) -log 7-w) is upper bounded.
The proof of Theorem 5 is then completed.
E EXPERIMENTS
This section collects several experiments supporting our theoretical results.
E.1 EXPERIMENTS OF LINEAR MODEL
E.1.1 COMPARING THE TRAINING BEHAVIOR OF GD, GDM, AND ADAM (W/S)
The experiments in this section is designed to verify Theorem 2, i.e, with proper learning rates, gradient descent with momentum converges to the max margin solution, which is the same as gradient descent. We use the synthetic dataset (Figure 1, (Soudry et al., 2018)) and run GD, GDM and Adam (w/s) over it with different learning rates = 0.01 and different random seeds (for random initialization and random samples despite the support sets {(115, 0.5), 1), ((0.5, 1.5), 1), ((-1.5, -0.5) -1), ((-1.5, -..5). -)))). Both the angle between the output parameter and max margin solution and the training accuracy are plotted Figure 1. Specifically, we plot the results with learning rate (1). MGD = MCDM = A]Adam = 0.001, (2).
IID = TCDM = AAdam = 0.1. We plot the training accuracy and the angle between the output parameter and the max margin solution for each setting respectively. The results are shown in Figure The observations can be summarized as follows:
When learning rate small enough (17 0.1, 0.001), both GD, GDM, and Adam converge to the max margin solution, which supports our theoretical results;
(Similarity between GD and GDM) The training behaviors of GD and GDM are highly similar.
(The acceleration effect of Adam) Adam achieves smaller angle with the max margin solution under the same number of iterations.
E.1. COMPARING THE TRAINING BEHAVIOR OF SGD AND SGDM
We also run the stochastic optimizers (SGD and SGDM) on the same synthetic dataset as Figure 1. The learning rate same as Figure 1, namely 0.001 and 0.1. The results of the experiment are plotted in Figure 2. It can be observed that when learning rate is small enough, SGD and SGDM have the similar training behavior, both converging the max margin solution.
E.1.3 ADAM ON ILL-POSED DATASET IN (SOUDRY ET AL., 2018)
In Figure 3 of (Soudry al., 2018), ill-posed synthetic dataset is proposed support the argument "Adam does not converge to max margin solution", which contradicts to the theoretical results of this paper. We re-conduct the experiment of Figure 3 in (Soudry et al.. 2018) with the same ill- ill-posed synthetic dataset with different learning rates and different random seeds as Figure 3. Figure 3. (f) similar Figure in (Soudry et al., 2018), where with learning rate 17 the angle of GD to the max margin solution is smaller than Adam all the time. However, it can be observed from the amplified figure that the angle of GD keeps still and above 0 all the time, meaning that GD doesn't 't converge to the max margin solution under this setting, However, the angle of Adam to the max margin solution still keeps decreasing and it's unreasonable to claim "Adam doesn't 't converge to the max margin solution" in this case (the same issue exists in Figure 3 in (Soudry et al., 2018)). Also, as we mentioned at the beginning of this section, this dataset is ill posed, which is due to the imbalance between the two components of the data (for all data ((x1, y) in the dataset,
and random seed 1,
51

---

Under review as a conference paper at ICLR 2022
100
4 Adam
Adem 0gM
2.0
Xcursy
0.6
0.4
02
lagid
lugil
(a) Comparison of Accuracy: 7 0.001, random
(b) Comparison of Angle: 17 0.001, random seed
seed
CDM
2.0-
2.-
23
23
0.0
Right
lng21
(c) Comparison of Accuracy: 0.001, random
(d) Comparison of Angle: = 0.001, random seed
seed 2
20-
Rcureey
0.
04-
02-
Adart
ODM
lxgtt
(e) Comparison of Accuracy: 0.1, random seed
(I) Comparison of Angle: = 0.1, random seed
100
Adam
91-
2.
Xcuncy
02
22-
3.00
lagid
lugil
(g) Comparison of Accuracy: 1) 0.1, random seed
(h) Comparison of Angle: v/ 0.1, random seed
Figure 1: Comparison of GD, GDM, and Adam on the synthetic dataset in (Soudry et al., 2018). In (a-g). the GD curve coincides with the GDM curve.
52

---

Under review as a conference paper at ICLR 2022
563 S0DM
6G0
2.0
0.0
20
0.-
bodoege wht
0.4
02
02
10
10
leail
laail
(a) Comparison of Accuracy: 0.001, random
(b) Comparison of Angle: 0.001, random seed
sced
100
5012 SGOM
2013 56aV
2.0-
Scuncy
2.-
03
0.0
(c) Comparison Accuracy: 7 0.001, random 2
(d) Comparison of Angle: 1 0.001, random seed
seed
20.
0.-
Accueey
0.6
04-
522
50D
00
0.-
10
10
(e) Comparison of Accuracy: v 0.1, random seed
(I) Comparison of Angle: = 0.1, random seed
5GD
93-
20-
Acurey
02
60
3.00
22-
0.3-
10
10
lagid
leail
(g) Comparison of Accuracy: 77 0.1, random seed
(h) Comparison of Angle: 17 0.1, random seed
2
Figure 2: Comparison of SGD and SGDM on the synthetic dataset in (Soudry et al., 2018).
53

---

Under review as a conference paper at ICLR 2022
[21| is always smaller than 2, while [zy] is larger than 10 (and even larger than 30 despite two data in the dataset)), which requires smaller learning rate. To tackle this problem, we need to tune down the learning rate. By Figure 3. (b),(d) and Figure 4. (b), after scaling down the learning rate, both GD's angle and Adam's 's angle keep decreasing.
E.2 EVIDENCE IN THE DEEP NEURAL NETWORKS
We conduct an experiment on the MNIST dataset using the four layer convolutional networks used in (Lyu & Li, 2019; Wang et al., 2021) (first proposed by (Madry et al., 2018)) to verify whether SGD and SGDM still behave similarly (homogeneous) deep neural networks. The learning rates of the optimizers are all set to be the default in Pytorch. The results can be seen in Figure 5, It can be observed that (I), SGDM achieves similar test accuracy compared to SGD while (2). SGDM converges faster than SGD.
54

---

Under review as a conference paper at ICLR 2022
80
14-
1.7
03
2.0
62
3.4
234
12
10
10
(a) Comparison of Accuracy: 7 0.1, random seed
(b) Comparison of Angle: 0.001, random seed
100
Adam
3.25
Ncuncy
62-
1.00
0.75
(c) Comparison Accuracy: 0.001, random
(d) Comparison of Angle: 1 0.001, random seed
seed
16
2.4
0.2
1.0
22-
0.-
10
30
(e) Comparison of Accuracy: 0.1, random seed
(I) Comparison of Angle: = 0.1, random seed
364
3.2
Acurey
00
3.00
0.8
0.0
044
02-
Adam
10
10
lazid
leaill
(g) Comparison of Accuracy: 7) 0.1, random seed
(h) Comparison of Angle: 17 0.1, random seed
Figure 3: Comparison of GD and Adam on the ill-posed synthetic dataset in (Soudry et al., 2018).
55

---

Under review as a conference paper at ICLR 2022
201
100
00
0.0
10
10
kigh1
(a) Comparison of Accuracy: 0.1, random seed
(b) Comparison of Angle: 0.001, random seed
Figure 4: Comparison of GD and Adam the ill-posed synthetic dataset in (Soudry et al., 2018) (continue).
100.05
03
00
Tustr (OLLENS
20
00.00
25
20 25
99
100
230
200
430
500
Spoch SCMe)
(a) Comparison of Training Accuracy
(b) Comparison of Test Accuracy
Figure 5: Comparison of SGD and SGDM on MNIST with four layer CNN.
56


Reviews:
[{"review_id": "oh-oDtICE64", "reviewer": "Reviewer_5GXX", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "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. \nThe authors provide an analysis of SGD and ADAM with momentum using new Lyapunov functions, but I didn't check the proofs thoroughly. \n\nHowever, 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).\nAlso, 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.\n\nQuestions:\n-\tWhat 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).\n-\tIt 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 ? \n-\tWhat is the effect of $\\varepsilon$ in ADAM ?\n\nMinor:\nit will be good to define “almost every dataset”.\n", "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.", "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. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "lZbGRMHTiAM", "reviewer": "Reviewer_4RNH", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "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.  \n\nAlthough 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?\n\nComparing 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? \n\nAlthough 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.\n\nReference\n\n[1] The Implicit Bias of Gradient Descent on Separable Data, JMLR 2018\n\n[2] Implicit bias of SGD: Stochastic gradient descent on separable data: Exact convergence with a fixed learning rate, AISTATS 2019", "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. ", "summary_of_the_review": "1. The authors provided new theoretical results for implicit bias of momentum methods.\n\n2. The learning rate of GDM/SGDM is smaller than that of GD/SGD, which allows narrower choices.\n\n3. No numerical results.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "YR7vJ3_ZYAp", "reviewer": "Reviewer_g2J5", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "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.\n\nMy major comments are as follows:\n1. 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.\n\n2. 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.\nThe 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.\n\n3. 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.\nA. 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.\nB. Lemma 12: The lines between (15) and (16) are erroneous. The correctness of first inequality (the one before (*)) is unclear to me.\nC. 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.\n\nMinor comments:\n1. 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.\n2. Assumption 2: \\ell' > 0 should be \\ell' < 0.\n3. Lemma 8: \\tilde S_s is undefined.\n4. Corollary 2: \\hat w should be \\tilde w.\n5. Lemma 10: x_0 should be s_0.\n6. 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.\nIn case 2: (\\dot) should be \\leq instead of =. In its previous line, alpha should be alpha^*.\n7. Corollary 1: the 2nd equality is wrong. Note that \\| \\hat w\\| = \\gamma. All later terms should have \\gamma^2 cancelled out.\n8. Corollary 4: there are 2 consecutive \\infty in the first equation.\n9. 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.\n10. 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.\n11. 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).\n12. 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.\n13. 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.\n\n", "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.", "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.\n\nI'd like to thank the authors for a detailed explanation and revising the manuscript.\nAfter 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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "ODiEBVDW8V", "reviewer": "Reviewer_D63g", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "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. \n\nThe 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. \nBoth, 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.)\n\nIn 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}. \nAt the end of the section, the summatory has a nabla term should not be there. \n\nI 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.\n\nThe 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_paper": "The authors study the convergence of stochastic gradient descent momentum (SGDM) in a problem with of binary classification with separable data. \nInterestingly, 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). \nThe paper proposed a variation of [Soudry et al. 2018] solution, that allows for the analysis of the more complex SGDM.", "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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

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