Year: 2021

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 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-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.

heading: 1 INTRODUCTION
text: It 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 et al., 2017). It is shown in the analysis of Adaboost that the coordinate descent would converge to the L1 max-margin solution for the linear classification task with exponetial-tailed loss ((Schapire & Freund, 2013; Telgarsky, 2013)). Latter, Soudry et al. (2018) shows that gradient descent would converge to the L2 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 et 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 et al., 2021).
However, though the momentum acceleration technique is 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-based optimizers?
In this paper, we 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-tailed loss using Stochastic Gradient Descent with Momentum (SGDM) and Adam optimizers. We consider the optimizers with constant learning rate and constant momentum hyperparameters, 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 as a special case of SGDM, and naturally share the properties for SGDM. Our main results are summarized in Theorem 1. Theorem 1 (informal). With linear separable dataset S, for SGDM and Adam (without stochasticity, abbreviated as w/s latter), the loss converges to 0 with rate O( 1t ) where t is the number of iterations, the parameter norm diverges to infinity, and direction of parameters converges to the direction of the L2 max-margin solution.
Theorem 1 states SGDM converges to the L2 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 as the margin of a 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 practice and our theoretical characterization deepens the understanding on their generalization property, which is important by its own.
• Technically, we propose a 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 a middle variable of an alternative 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 momentum-based optimizers. We then construct a new Lyapunov function to bound the difference of learned parameters and the scaled 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.
Organization of This Paper. Section 2 collects further related works on the implicit bias of first order optimizers and convergence of momentum-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 a 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.

heading: 2 FURTHER RELATED WORKS
text: Implicit Bias of First-order Optimization Methods. Soudry et al. (2018) prove that gradient descent on linear classification problem with exponential-tailed loss converges to the direction of the max L2 margin solution of the corresponding 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 a 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 on (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 on the primal space is no longer a Nesterov’s Acceleration Method nor GDM, which is significantly different from our settings.
On the other hand, 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 a framework to analyze the asymptotic direction of GD on homogeneous neural networks, proving that given there exists a time the network achieves 100% training accuracy, GD will converge to some KKT point of the L2 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 a 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-Based Optimization Methods. For convex optimization problems, the convergence rate of Nesterov’s Acceleration Method has been proved in Nesterov (1983). In
contrast, although GDM (Polyak’s Heavy-Ball Method) was proposed in (Polyak, 1964) prior to the Nesterov’s Acceleration Method, the convergence of GDM on convex loss with Lipschitz gradient was not solved until Ghadimi et al. (2015) provides an ergodic convergent result for GDM, i.e., 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 et al. (2019) prove that if the training loss is coercive (the training loss goes to infinity whenever parameter norm goes to infinity), convex, and globally smooth, then, with constant momentum hyper-parameter, the training loss converges to minima with rateO(t−1). Tao et al. (2021) analyze a case when momentum coefficient increases to 1 and the gradient is bounded all over the parameter space, showing SGDM can improve the convergence rate of SGD by a 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 on the investigation of momentum-based method from the view point of dynamics (Sarao Mannelli & Urbani, 2021). However, there is no existing work on the implicit bias of momentum-based optimizers for the classification problem, which is first analyzed by this paper.

heading: 3 PRELIMINARIES
text: In this paper, we focus on the linear model with exponential-tailed loss. We first derive the results for binary classification, then we show that the methodology can be easily extended to the multi-class classification problem.
Problem setting. The dataset used for training is defined as S = (xi,yi)Ni=1, where xi ∈ Rd is the i-th feature, and yi ∈ R is the i-th label (i = 1, 2, · · · , N ). We will use the linear model to fit the label: for any feature x ∈ Rd and parameter w ∈ Rd, the prediction is given by 〈w,x〉. For binary classification, given any data zi = (xi,yi) ∈ S, the individual loss for parameter w is given as `(yi〈w,xi〉). A common setting is to ensemble the feature and label together as x̃i = yixi (there is a mapping T : (x,y)→ yx, and x̃i is T ((xi,yi))). The individual loss can be rewritten as
˜̀(w, (xi,yi)) = `(yi〈w,xi〉) = `(〈w, x̃i〉).
The optimization target is defined as the averaged loss:
L(w) = ∑N i=1 ˜̀(w, (xi,yi))
N .
Without loss of generality, we consider the case with normalized data1, that is, ‖x̃i‖ ≤ 1, ∀i ∈ [N ]. Optimizer. Here we will introduce the update rules of SGDM and Adam (w/s). SGDM can be viewed as a stochastic version of GDM by randomly choosing a subset of the dataset to update. Specifically, the update rule of SGDM is given as
(SGDM) : w(t+ 1)−w(t) = −η∇LB(t)(w(t)) + β(w(t)−w(t− 1)), ∀t ≥ 1, (1)
where B(t) is a subset of S with size b which is sampled independently and uniformly with replacement, and LB(t) is defined as LB(t)(w) = ∑ z∈B(t) ˜̀(w,z)
b . We also define Ft as the sub-sigma field such that {w(t)}∞t=1 is adapted with respect to Filtration {Ft}∞t=1.
1The proof can be naturally applied to unnormalized data by letting `(x) = `(maxx̃∈T (S) ‖x̃‖ · x) and x̃i =
x̃i maxx̃∈T (S) ‖x̃‖ .
The Adam (w/s) can be viewed as a variant of GDM in which the preconditioner is adopted, whose form is characterized as follows:
m(0) = 0,m(t) = β1m(t− 1) + (1− β1)∇L(w(t)), m̂(t) = 1
1− βt1 m(t), ∀t ≥ 1,
ν(0) = 0, ν(t) = β2ν(t− 1) + (1− β2) (∇L(w(t)))2 , ν̂(t) = 1
1− βt2 ν(t), ∀t ≥ 1,
(Adam (w/s)) : w(t) = w(t− 1)− η m̂(t− 1)√ ν̂(t− 1) + ε1d , ∀t ≥ 1, (2)
where 1√ ν̂(t−1)+ε1d ) is called the preconditioner at step t.
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 as follows:
Assumption 1 (Linearly Separable Dataset). There exists one parameter w ∈ Rd, such that
〈w, x̃i〉 > 0, ∀i ∈ [N ].
Assumption 2 (Exponential-tailed Loss). The individual loss ` is exponential-tailed, i.e.,
• Differentiable and monotonically decreasing to zero, with its derivative also converging to zero, i.e., limx→∞ `(x) = limx→∞ `′(x) = 0, and `′(x)<0 ∀x;
• Close to exponential loss when x is large enough, i.e., there exist positive constants c, a,K, µ+, µ−, x+, x− and x0, such that,
∀x > x+ : −`′(x) ≤ c(1 + e−µ+x)e−ax, (3) ∀x > x− : −`′(x) ≥ c(1− e−µ−x)e−ax. (4)
Assumption 3 (Smooth Loss). Either of the following assumptions holds regarding the case:
(D): (Deterministic Case) The individual loss ` is locally smooth, i.e., for any s0 ∈ R, there exists a positive real Hs0 , such that ∀x, y ≥ s0, |`′(x)− `′(y)| ≤ Hs0 |x− y|. (S): (Stochastic Case) The individual loss ` is globally smooth, i.e., there exists a positive real H , such that ∀x, y ∈ R, |`′(x)− `′(y)| ≤ H|x− y|.
We provide explanations 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 γ(w) of parameter w defined as the lowest score of the prediction of w over the dataset S, i.e., γ(w) = minx̃i∈T (S)〈w, x̃i〉. By Assumption 1 and the positive homogeneous of γ, γ( ŵγ(ŵ) ) = 1, and thus we define the maximum margin solution ŵ and the L
2 max margin γ of the dataset S as follows:
ŵ 4 = arg min γ(w)≥1 ‖w‖2, γ 4= 1 ‖ŵ‖
Since ‖ · ‖2 is strongly convex and set {w : γ(w) ≥ 1} is convex, ŵ is uniquely defined. Assumption 2 constraints the loss to be exponential-tailed, which is satisfied by many popular choices of `, including the (`exp(x) = e−x) and the logistic loss (`log(x) = log(1 + e−x)). Also, as c and a can be respectively absorbed by resetting the learning rate and data as η = cη and xi = axi, without loss of generality, in this paper we only analyze the case that c = a = 1.
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).

heading: 4 WARM UP: IMPLICIT BIAS OF GDM
text: In this section, we study the implicit bias of GDM as a warm up. The update rule of GDM is
w(t+ 1)−w(t) = −η∇L(w(t)) + β(w(t)−w(t− 1)), ∀t ≥ 1 (5)
which is a determined case of SGDM, with batch size b = N and thus without randomness. Although the analysis of GDM is essentially easier than that of SGDM, it helps us gain a 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:
Theorem 2. Let Assumptions 1, 2, and 3. (D) hold. Let β ∈ [0, 1) and η < 2 1−βH`−1(NL(w1)) . Then, for almost every data set S2, with arbitrary initialization point w(1), GDM (Eq. (5)) satisfies that w(t)− log(t)ŵ is bounded as t→∞, and limt→∞ w(t)‖w(t)‖ = ŵ ‖ŵ‖ .
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 an constant momentum hyper-parameter, which agrees with the practice use (e.g., β is set to be 0.9 (Xie et al., 2017)). Also, Theorem 2 puts no restriction on the range of β, which allows wider choices of hyper-parameter tuning. Furthermore, Theorem 2 shows the implicit bias of GDM agrees with GD in linear classification with exponential-tailed loss (c.f. Soudry et al. (2018) for results on GD), and this consistency can be verified by existing results (c.f. Section 7 for detailed discussions).
We then present a proof sketch of Theorem 2, which is divided into two parts: we first prove that the sum of squared gradients is bounded, which indicates both the loss and the norm of gradient converge to 0; we then show the difference between w(t) and log(t)ŵ is bounded, and therefore, the direction of ŵ dominates as t→∞. Stage I: Bound the sum of squared gradients. The core of Stage I is to select a 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 L itself is non-increasing with properly chosen learning rate, we can just pick ξ(t) = L(t). However, as the update of GDM doesn’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 ξ(t) is proposed as the follows:
Lemma 1. Let all conditions in Theorem 2 hold. Define ξ(t) 4= L(w(t)) + β2η‖w(t)−w(t− 1)‖ 2. Let C1 be a positive real, s.t., η = 2 1−βH`−1(NL(w1)) C1. We then have
ξ(t) ≥ ξ(t+ 1) + (1− β)(1− C1) η ‖w(t+ 1)−w(t)‖2. (6)
Remark 1. Although this Lyapunov function is obtained by (Sun et al., 2019) by directly examining the Taylor’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 et al., 2019), and the Taylor’s expansion can only be applied to w(t+1) if it’s ensured that all parameters on the line αw(t)+(1−α)w(t+1) (α ∈ (0, 1)) have training loss no larger than L(w(0)).
To prove Lemma 1, we define w(t+α) = αw(t) + (1−α)w(t+ 1) for any t ∈ Z+ and α ∈ (0, 1), and prove a generalized version of Eq. (6):
ξ(t) ≥ ξ(t+ α) + (1− β)(1− c)α 2
η ‖w(t+ 1)−w(t)‖2. (7)
The proof idea is that as long as Eq. (7) holds for all time in [1, t + α), the training loss across [1, t+α] will be smaller than L(w(1)), and the strict inequality in Eq. (7) holds. Consequently, there exists some small enough positive real ε, such that Eq. (7) holds for all time in [1, t+ α+ ε), 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 B.1.1.
2Here "almost everywhere" means the conclusion holds except a zero-measure set in Rd×N .
By Lemma 1, we have that ξ(t) is monotonously decreasing by gap (1−β)(1−c)α 2
η ‖w(t+1)−w(t)‖ 2. As ξ(1) = L(w(1)) is a finite number, we have ∑∞ t=1 ‖w(t + 1) − w(t)‖2 < ∞, 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, ∑∞ t=1 ‖∇L(w(t))‖2 <∞. The proof of Corollary 1 can be found in Appendix B.1.1. Resulted from Corollary 1, we have ‖∇L(w(t))‖2 → 0 as t → ∞, which by the exponential-tailed loss assumption further leads to limt→∞ L(w(t)) = 0. Stage II. Bound the difference between w(t) and log(t)ŵ. It seems natural to directly bound ‖w(t)− log(t)ŵ‖ across all iterations. Soudry et al. (2018) and Nacson et al. (2019) indeed follow this routine by showing the norm of r(t) 4 = w(t) − log(t)ŵ − w̃ is bounded, where w̃ is some constant vector satisfying e〈w̃,x̃〉 recovers the coefficient of support vector x̃ in ŵ. However, their analyses rely on the fact that w(t+ 1)−w(t) equals −η∇L(w(t)), which has a simple form, i.e.,
For GD : ‖r(t+ 1)‖2 − ‖r(t)‖2 = ‖r(t+ 1)− r(t)‖2 − 2〈log t+ 1 t ŵ + η∇L(w(t)), r(t)〉.
However, it no longer holds for GDM, as w(t+1)−w(t) is a exponentially-decayed sum of gradients at w(s), 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, ‖r(t)‖ is bounded if and only if the function g(t) is upper bounded, where g : Z+ → R is defined as
g(t) 4 = 1 2 ‖r(t)‖2 + β 1− β 〈r(t),w(t)−w(t− 1)〉 − β 1− β t∑ τ=2 〈r(τ)− r(τ − 1),w(τ)−w(τ − 1)〉. (8)
Furthermore, we have ∑∞ t=1(g(t+ 1)− g(t)) 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 is to construct a easy-to-verify criterion (i.e., g(t) is upper bounded) of ‖r(t)‖ is upper bounded. To demonstrate how g(t) is constructed intuitively, we consider the continuous dynamics approximation of GDM, i.e.,
β 1− β d2w(t) dt2 + dw(t) dt + η 1− β ∇L(w(t)) = 0.
We then calculate the 12‖r(t)‖ 2 − 12‖r(1)‖ 2 by applying the integral of the dynamics as ∫ t 1 1 2 d‖r(s)‖2 ds ds = ∫ t 1 〈 r(s),− η 1− β ∇L(w(s))− 1 s ŵ 〉 ds + ∫ t 1 β 1− β 〈 r(s),− d2w(s) ds2 〉 ds
= ∫ t 1 〈 r(s),− η 1− β ∇L(w(s))− 1 s ŵ 〉 ds + β 1− β (〈 r(t),− dw(t) dt 〉 − 〈 r(1),− dw(t) dt ∣∣∣∣ t=1 〉 + ∫ t 1 〈 dr(s) ds , dw(s) ds 〉 ds ) ,
where the last equation is due to Integration by part. We denote g̃(t) = β1−β (〈r(t), dw(t) dt 〉 −∫ t
1 〈dr(s)ds , dw(s) ds 〉ds)+ 1 2‖r(t)‖ 2, and it can be verified the derivative of g̃(t) is 〈r(t),− η1−β∇L(w(t)) − 1t ŵ〉. By replacing dw(t) dt as w(t) − w(t − 1), and dr(t) dt as r(t) − r(t − 1) in g̃(t), we obtain g(t), and g(t+ 1)− g(t) has the form 〈r(t),− η1−β∇L(w(t))− log t+1 t ŵ〉, which can be analyzed following the similar routine as (Soudry et al., 2018). The proof of the second claim is completed.
On the other hand, the core of the proof of Lemma 2 is that 12‖r(t)‖ 2 + β1−β 〈r(t),w(t)−w(t− 1)〉 is bounded if and only if 12‖r(t)‖ 2 is bounded, while 〈r(τ) − r(τ − 1),w(τ) −w(τ − 1)〉 is an
absolute convergent based on ∑∞ t=1 ‖w(t+ 1)−w(t)‖2 <∞.

heading: 5 TACKLE THE DIFFICULTY BROUGHT BY RANDOM SAMPLING
text: 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 an example, if we want to
follow the same routine of the GDM case to show L(w(t)) + β2ηE‖w(t)−w(t− 1)‖ 2 is a Lyapunov function of SGDM, we can only have
EL(w(t)) + β 2η E‖w(t)−w(t− 1)‖2 ≥EL(w(t+ 1)) + β 2η E‖E [w(t+ 1)−w(t)|Ft] ‖2
+ (1− β)(1− c)
η E‖E [w(t+ 1)−w(t)|Ft] ‖2.
As the squared first momentum is smaller than the second momentum, EL(w(t)) + β2ηE‖w(t) − w(t − 1)‖2 may no longer be monotonously decreasing for every β ∈ [0, 1). Furthermore, if the margin γ is small, β will be required to be upper bounded by a small number, which contradicts to 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 β ∈ [0, 1) and η < min{ 1−β 1+HN bγ2 , (1−β) 3γ4b 2H2N3β2 }. Then, for almost every data set S, with arbitrary initialization point w(1), SGDM (Eq. (1)) satisfies w(t)− log(t)ŵ is bounded as t→∞ and limt→∞ w(t)‖w(t)‖ = ŵ ‖ŵ‖ , almost surely (a.s.).
To the best of our knowledge, this is the first convergence analysis of SGDM with no restriction on the gradient norm and with constant learning rates. Also, as both 1−β
1+HN bγ2
and (1−β) 3γ4b
2H2N3 are monotonously
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 3 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 B(t). Specifically, within the T -th epoch E(T ) = {KT + 1, · · · ,KT +T} (K is the length of one epoch), {B(t)}t∈E(T ) is a 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.1.
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, we first present a lemma to provide an alternative form of update rule of SGDM:
Lemma 3. Define η̃ 4= η1−β , and u(1) 4 = w(1). The update rule of SGDM (Eq. (1)) is equivalent to
u(t+ 1) = −η̃∇LB(t)(w(t)) + u(t), w(t+ 1) = βw(t) + (1− β)u(t+ 1). (9)
By a simple rearrangement of the second equation, we have u(t+1) = w(t)+ 11−β (w(t+1)−w(t)), which differs from w(t+ 1) only by a larger step size updated from w(t). The following lemma then indicates that EL(u(t)) is a proper selection of Lyapunov function. Lemma 4. Let all conditions in Theorem 3 hold. Then, we have
E[L(u(t+ 1))] ≤ EL(u(t))− η̃ 2 E‖∇L(w(t))‖2 + 1− β 4 η̃ ( t−1∑ s=1 βt−1−sE ‖∇L(w(s))‖2 ) ,
and
E[L(u(t+ 1))] ≤ L(u(1))− t∑
s=1
η̃ 4 E‖∇L(w(s))‖2.
EL(u(t)) may be not monotonously decreasing. However, the upper bound of EL(u(t)), i.e., L(u(1)) − ∑t s=1 η̃ 4 ‘E‖∇L(w(s))‖ 2, is monotonously decreasing by η̃4E‖∇L(w(t))‖ 2 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 is finite, a.s.).
The proof idea of Lemma 4 is the expectation of the first order Taylor’s expansion of L at w(t) has the form
E[L(u(t+ 1))|Ft] ≤ L(u(t))− η̃〈∇L(u(t)),∇L(w(t))〉+ Lη̃2
2 E[‖∇LB(t)(w(t))‖2|Ft].
As L is H smooth, we have ∇L(u(t)) = ∇L(w(t)) +O(‖u(t) −w(t)‖), where u(t) −w(t) = β 1−β (w(t) − w(t − 1)) = −η β 1−β ∑t−1 s=1 β
t−1−s∇LB(s)(w(s)) is proportional to η. Therefore, when η is small, −〈∇L(u(t)),∇L(w(t))〉 is close to −‖∇L(w(t))‖2, and the coefficient of −‖∇L(w(t))‖2 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 as the g(t) in the GDM case. As we have proved the sum of squared gradient along the trajectory is bounded, one can easily obtain that ∑∞ t=1 ‖w(t + 1) −w(t)‖2 is bounded, and ‖r(t)‖ being bounded is still equivalent to that g(t) is upper bounded. However, when it comes to the detailed calculation of analyzing g(t + 1) − g(t), it differs from the GDM case due to the random subset. We defer the proof to Appendix B.2.2.

heading: 6 ANALYZE THE EFFECT OF PRECONDITIONERS
text: 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 1, 2, and 3. (D) hold. Let 1 > β2 > β41 ≥ 0, and the learning rate η is a small enough constant (The upper bound of learning rate is complex, and we defer it to Appendix C.1). Then, for almost every data set S, with arbitrary initialization point w(1), Adam (w/s) (Eq. (2)) satisfies that w(t)− log(t)ŵ is bounded as t→∞, and limt→∞ w(t)‖w(t)‖ = ŵ ‖ŵ‖ .
Remark 3. Existing literature usually assume a time-decaying hyperparameter choice of β1 or β2 (c.f., (Kingma & Ba, 2014; Chen et al., 2018)). To the best of our knowledge, the only work analyzing Adam with constant β1 and β2 is (Reddi et al., 2019), which assumes β2 > β21 (stronger than our assumption). Our result indicates that the ranges of β1 and β2 can be broader in hyper-parameter 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 in Stage I, we will also prove the loss converges to 0 with rate Θ(t−1). This property will be used in Stage II to analyze the effect of preconditioner on implicit bias.
Stage I: Bound the sum of squared gradients. The next lemma can be viewed as an extension of Lemma 1 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 t ≥ 1,
L(t+ 1) + 1 2 1− βt1 η(1− β1) ∥∥∥ 4√ε1d + ν̂(t) (w(t+ 1)−w(t))∥∥∥2 ≤L(w(t)) + 1− β t−1 1
2cη(1− β1) 1− (cβ1)t 1− (cβ1)t−1 ∥∥∥ 4√ε1d + ν̂(t− 1) (w(t)−w(t− 1))∥∥∥2 . (10)
The difference between the proof of Lemma 5 and Lemma 1 is that we need to handle the gap between the preconditioners at step t and step t + 1, this leads to a amplifying factor 4 √ 1−βt2
β2(1−βt−12 ) of term ∥∥∥ 4√ε1d + ν̂(t− 1) (w(t)−w(t− 1))∥∥∥2, which, however, is smaller than the shrinking factor 1−β t 1
β2(1−βt−12 ) introduced by the gap between the coefficients of momentum
m̂(t) and m̂(t − 1). As t → ∞, both βt1 → 0 and (cβ1)t → 0, and we can obtain that ξ(t) 4 = L(w(t)) + 1
2 2 √ cη(1−β1) ∥∥∥ 4√ε1d + ν̂(t− 1) (w(t)−w(t− 1))∥∥∥2 is a Lyapunov function. Based on Lemma 5, we can prove the following asymptotic rate of L. Lemma 6. Let all conditions in Theorem 4 hold. Then,
L(w(t)) = Θ ( t−1 ) , ‖w(t)‖ = Θ(log(t)), and ‖w(t)−w(t− 1)‖ = Θ(t−1).
The proof idea of Lemma 6 is that by the exponential-tailed property, when time is large enough, the training loss can be bounded by the gradient, and further bounded by ‖ 4 √ ε1d + ν̂(t− 1) (w(t)− w(t− 1))‖. Consequently, ξ(t+ 1)− ξ(t) ≤ −O(ξ(t)), and ξ(t) = O(t−1). Stage II. Bound the difference between w(t) and log(t)ŵ. The Lyapunov function for the direction difference is also modified according to the preconditioner, as introduced in Lemma 7:
Lemma 7. Let all conditions in Theorem 4 hold. Then, ‖r(t)‖ is bounded if and only if g(t) is upper bounded, where g(t) is defined as follows.
g(t) 4 =
√ ε
2 ‖r(t)‖2 + β1 1− β1
〈 r(t), (1− βt−11 ) √ ε1d + ν̂(t− 1) (w(t)−w(t− 1)) 〉 − β1
1− β1 t∑ τ=2 〈r(τ)− r(τ − 1), (1− βτ−11 ) √ ε1d + ν̂(τ − 1) (w(τ)−w(τ − 1))〉.
Furthermore, we have ∑∞ s=1(g(t+ 1)− g(t)) 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(t+ 1)− g(t) leads to
〈r(t), ( √ ε− (1−βt1) √ ε1d + ν̂(t)) (w(t+1)−w(t))〉+ 〈r(t),− √ ε log( t+ 1
t )ŵ− η 1− β∇L(w(t))〉.
This is where we need Lemma 6, which bounds the gap between √ ε1d + ν̂(t) and √ ε by O(t−2)
and makes ∑∞ t=1〈r(t), ( √ ε− (1− βt1) √ ε1d + ν̂(t)) (w(t+ 1)−w(t))〉 an absolute continuous
sequence. The second term 〈r(t),− √ ε log( t+1t )ŵ − η 1−β∇L(w(t))〉 can be tackled by following the same routine as the GDM/SGDM 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 to the L2 max margin solution, which is proposed by (Tao et al., 2021) and has the following form3:
w(t+ 1) = w(t)− η ∇LB(t)(w(t))√ ε1d + ν̂(t) + β(w(t)−w(t− 1)), t ≥ 1,
where ν̂(t) is defined as Eq. (2).The proof is a 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(1))
u(t+ 1) = − η 1− β ∇LB(t)(w(t))√ ε1d + ν̂(t) + u(t),
w(t+ 1) = βw(t) + (1− β)u(t+ 1).
However, Adam is different from the stochastic adaptive heavy-ball algorithm as 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.
3Compared to (Tao et al., 2021), we put the ε1d inside the square-root and use ν̂(t) instead of ν(t) to demonstrate the difference between Adaptive Heavy Ball and Adam, while these changes will not influence the convergent direction.

heading: 7 DISCUSSIONS
text: Extension to the Multi-Class Classification Problem. As mentioned in the introduction, despite all the previous analyses are aimed at the binary classification problem, they can be naturally extended to the analyses multi-class classification problem. Specifically, in the linear multi-class classification problem, for any (x,y) ∈ RdX × {1, · · · , C} in the sample set S, the (individual) logistic loss with parameter W ∈ RC×dX is denoted as
`(y,Wx) = log eWy,x∑C i=1 e Wi,x .
Correspondingly, dataset S is separable if there exists a parameter W , such that ∀(x,y) ∈ S, we have Wy,x >Wi,x, ∀i 6= y. The multi-class L2 max-margin problem is then defined as
min ‖W ‖F , subject to : Wy,x ≥Wi,x + 1,∀(x,y) ∈ S, i 6= y,
where ‖ · ‖F denotes the Frobenius norm. Denote Ŵ as the L2 max-margin solution, we have (mini-batch) SGDM and Adam (w/s) still converges to 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 a small enough learning rate, and 1 > β2 > β41 ≥ 0 (for Adam (w/s)), (mini-batch) SGDM and Adam (w/s) converge to the multi-class L2 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 1 in (Soudry et al., 2018)), and it 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 et 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 et al. (2021) conduct the experiments of SGD, SGDM, Adam (without momentum) and Adam on MNIST using homogeneous neural networks (c.f. Appendix F.1.2 in (Wang et al., 2021)), and observe such similarity for deep neural networks. Our theorems apply to linear models, which is a special case of homogeneous 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 a Lyapunov function bounding the rate between loss and parameter norm of GD on the homogeneous deep neural networks, and prove the parameter direction converges to some KKT point of the L2 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 a Lyapunov function can be constructed for GDM and Adam in homogeneous neural networks.

heading: 8 CONCLUSION
text: In this paper, we study the implicit bias of momentum-based optimizers in linear classification with exponential-tailed 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 L2 max-margin solution. Our theoretical results stands with existing experimental observations.

heading: A PREPARATIONS
text: This section collect definitions and lemmas which will be used throughout the proofs.

heading: A.1 CHARACTERIZATION OF THE MAX-MARGIN SOLUTION
text: 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 ∈ [N ], x̃i is called a support vector of the dataset S, if 〈x̃i, ŵ〉 = 1. Correspondingly, x̃i is called a non-support vector if 〈x̃i, ŵ〉 > 1. The support set of S is then defined as
Ss = {(xi,yi) : 〈yixi, ŵ〉 = 1}.
The following lemma delivers ŵ as an linear combination of support vectors.
Lemma 8 (Lemma 12, Soudry et al. (2018)). For almost every datasets S, there exists a unique vector v = (v1, · · · ,vN ), such that ŵ can be represented as
ŵ = N∑ i=1 vix̃i, (11)
where v satisfies vi = 0 if x̃i /∈ T (Ss), and vi > 0 if x̃i ∈ T (Ss). Furthermore, the size of S̃s is at most d.
By Lemma 8, we further have the following corollary:
Corollary 2. For almost every datasets S, the unique v given by Lemma 8 further satisfies that for any positive constant C2, there exists a non-zero vector w̃, such that, x̃i ∈ T (Ss), we have
C2e −〈x̃i,w̃〉 = vi. (12)
Proof. For almost every datasets S, any subsets with size d of S is linearly independent. Since S̃s has size no larger than d (by Lemma 8), and Eq. (12) is equivalent to linear equations, the proof is completed.
For the stochastic case, we will also need the following lemma when we calculate the form of parameter at time t.
Lemma 9 (Lemma 5, Nacson et al. (2019)). Let B(s) be the random subset used in SGD (i.e., the one used in SGDM). Almost surely, there exists a vector w̌
N
b t−1∑ s=1 1 s ∑ i:x̃i∈T (B(s)∩Ss) vix̃i = log ( bt N ) ŵ + n(t),
where n(t) satisfies ‖n(t)‖ = o(t−0.5+ε) for any ε > 0, and ‖n(t+ 1)− n(t)‖ = O(t−1). If the B(s) is the random subset used in SGDM (i.e., the one used in mini-batch SGDM), then the a.s. condition can be removed.

heading: A.2 PREPARATIONS OF THE OPTIMIZATION ANALYSIS
text: This section collects technical lemmas which will be used in latter proofs. We begin with a lemma bounding the smooth constants if the loss is bounded.
Lemma 10. If loss ` satisfies (D) in Assumption 3, then for any w0, if L(w) ≤ L(w0), then we have L is Hs0 smooth at point w, where s0 = `−1(NL(w0)). Furthermore, L is globally Hs0 smooth over the set {w : L(w) ≤ L(w0)}.
Proof. Since ` is positive, we have ∀i ∈ [N ],
˜̀(w, zi)
N <
∑N j=1 ˜̀(w, zj)
N = L(w) ≤ L(w0),
which leads to ˜̀(w, zi) < NL(w0), and ` is Hs0 smooth at 〈w, x̃i〉.
Furthermore, since∇w ˜̀(w, zi) = ∇w`(〈w, x̃i〉) = `′(〈w, x̃i〉)x̃i, for any two parameters w1 and w2 close enough to w,
‖∇w ˜̀(w1, zi)−∇w ˜̀(w2, zi)‖ = ‖(`′(〈w1, x̃i〉)− `′(〈w2, x̃i〉))x̃i‖ ≤|`′(〈w1, x̃i〉)− `′(〈w2, x̃i〉)| ≤ Hs0 |〈w1 −w2, x̃i〉| ≤ Hs0‖w1 −w2‖,
and thus,
‖∇wL(w1)−∇wL(w2)‖ ≤ 1
N N∑ i=1 ‖∇w ˜̀(w1, zi)−∇w ˜̀(w2, zi)‖ ≤ Hs0‖w1 −w2‖,
which completes the proof that L is locally Hs0 smooth at w. Now if w1 and w2 both belong to {w : L(w) ≤ L(w0)}, we have for any x̃i ∈ T (S), 〈w1, x̃i〉 > `−1(NL(w0)), and 〈w2, x̃i〉 > `−1(NL(w0)). Following the same routine as the locally smooth proof, we complete the second argument.
The proof is completed.
Based on Assumption 2, we also have the following lemma characterizing the relationship between loss ` and its derivative `′ when x is large enough.
Lemma 11. Let loss ` satisfy Assumption 2. Then, there exists an large enough x0 and a positive real K, such that, ∀x > x0, we have
− 1 K `′(x) ≤ `(x) ≤ −K`′(x).
Proof. By Assumption 2, there exists a large enough x0, such that ∀x > x0, we have 1
2 e−x ≤ −`′(x) ≤ 2e−x. (13)
On the other hand, as limt→∞ `(x) = 0, we have
`(x) = ∫ ∞ s=x −`′(s)ds,
which by Eq. (13) leads to
1 2 e−x = 1 2 ∫ ∞ x e−sds ≤ `(x) ≤ 2 ∫ ∞ x e−sds = 2e−x.
Therefore, setting K = 4 completes the proof.
The following lemma bridges the second moment of∇LB(t) with its squared first moment.
Lemma 12. Let the dataset S satisfies the separable assumption 1. Let B be a random subset of S with size b sampled independently and uniformly without replacement. Then, at any point w, we have
‖∇L(w)‖2 ≤ EB [ ‖∇LB(w)‖2 ] ≤ N γ2b ‖∇L(w)‖2.
Proof. To start with, notice that
‖∇L(w)‖ = ‖EBLB(w)‖ ≤ EB‖LB(w)‖.
Therefore, the first inequality can be directly obtained by Cauchy-Schwartz’s inequality. To prove the second inequality, we first calculate the explicit form of∇LB(w).
‖∇LB(w)‖2 = 1
b2 ∥∥∥∥∥∇∑ z∈B ˜̀(w, z) ∥∥∥∥∥ 2
= 1
b2 ∥∥∥∥∥∥ ∑
x̃∈T (B)
`′(〈w, x̃〉)x̃ ∥∥∥∥∥∥ 2 = 1 b2 ∑ x̃,x̃′∈T (B) `′(〈w, x̃〉)`′(〈w, x̃′〉)〈x̃, x̃′〉
≤ 1 b2 ∑ x̃,x̃′∈T (B) `′(〈w, x̃〉)`′(〈w, x̃′〉).
Therefore,
EB‖∇LB(w)‖2
≤EB 1
b2 ∑ x̃,x̃′∈T (B) `′(〈w, x̃〉)`′(〈w, x̃′〉) (14)
=EB 1
b2 ∑ x̃,x̃′∈T (S) `′(〈w, x̃〉)`′(〈w, x̃′〉)1x̃,x̃′∈T (B)
= 1
b2 ∑ x̃,x̃′∈T (S) `′(〈w, x̃〉)`′(〈w, x̃′〉)EB1x̃,x̃′∈T (B)
= 1
Nb ∑ x̃∈T (S) `′(〈w, x̃〉)2 + b− 1 bN(N − 1) ∑ x̃,x̃′∈T (S),x̃ 6=x̃′ `′(〈w, x̃〉)`′(〈w, x̃′〉)
≤ 1 Nb  ∑ x̃∈T (S) `′(〈w, x̃〉) 2 . (15) On the other hand,
‖∇L(w)‖ = 1 N ∥∥∥∥∥∥ ∑
x̃∈T (S)
`′(〈w, x̃〉)x̃ ∥∥∥∥∥∥ ≥ 1 N 〈 ∑ x̃∈T (S) `′(〈w, x̃〉)x̃,− ŵ ‖ŵ‖ 〉 (?) ≥ γ N ∑ x̃∈T (S) `′(〈w, x̃〉)
where Eq. (?) is due to ∀z ∈ 〈x̃,−ŵ〉 ≥ 1 and `′ < 0. Therefore,
‖∇L(w)‖2 ≥ γ 2
N2  ∑ x̃∈T (S) `′(〈w, x̃〉) 2 . (16) The proof is completed by putting Eqs. (15) and (16) together.
In the following lemma, we 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.,
‖w(t+ 1)−w(t)‖ > 0,∀t > 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
w(t+ 1)−w(t) = −η
( t∑
s=1
βt−s∇L(w(s)) ) . (17)
Similarly, the update rule of SGDM can be written as
w(t+ 1)−w(t) = −η
( t∑
s=1
βt−s∇LB(s)(w(s)) ) , (18)
while the update rule of Adam can be given as w(t+ 1)−w(t) = −η ∑t s=1 1−β1 1−βs1
βt−s1 ∇L(w(s))√ ε1d + ∑t s=1 1−β2 1−βs2 βt−s2 (∇L(w(s)))2 . (19)
On the other hand, by the definition of empirical risk L, the gradient of L at point w can be given as ∇L(w) = ∑N i=1 `
′(〈w, x̃i〉)x̃i N . (20)
By Eq. (20) and Eq. (17), we further have for GDM,
w(t+ 1)−w(t) = −η
( t∑
s=1
βt−s ∑N i=1 `
′(〈w(s), x̃i〉)x̃i N
) . (21)
By Assumption 1, there exists a non-zero parameter ŵ, such that, 〈ŵ, x̃i〉 > 0, ∀i. Therefore, by executing inner product between Eq. (21) and ŵ, we have
‖w(t+1)−w(t)‖‖ŵ‖ ≥ 〈w(t+1)−w(t), ŵ〉 = −η
( t∑
s=1
βt−s ∑N i=1 `
′(〈w(s), x̃i〉)〈x̃i, ŵ〉 N
) (∗) > 0,
where Eq. (∗) is due to `′ < 0. This complete the proof for GDM. Similarly, for SGDM, we have
‖w(t+ 1)−w(t)‖‖ŵ‖ ≥ −η
( t∑
s=1
βt−s ∑ (x,y)∈B ` ′(〈w(s),yx〉)〈yx, ŵ〉
b
) > 0,
which completes the proof of SGDM.
For Adam, we have
‖w(t+ 1)−w(t)‖ ∥∥∥∥∥∥ŵ √√√√ε1d + t∑
s=1
1− β2 1− βs2 βt−s2 (∇L(w(s)))2 ∥∥∥∥∥∥ ≥− 〈 ŵ
√√√√ε1d + t∑ s=1 1− β2 1− βs2 βt−s2 (∇L(w(s)))2, η ∑t s=1 1−β1 1−βs1 βt−s1 ∇L(w(s))√ ε1d + ∑t s=1 1−β2 1−βs2 βt−s2 (∇L(w(s)))2 〉
= 〈 ŵ, η
t∑ s=1 1− β1 1− βs1 βt−s1 ∇L(w(s)
〉
=− η
( t∑
s=1
1− β1 1− βs1 βt−s1
∑N i=1 `
′(〈w(s), x̃i〉)〈x̃i, ŵ〉 N
) > 0,
which completes the proof of Adam.
The proof is completed.
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.

heading: B.1.1 PROOF OF THE SUM OF SQUARED GRADIENTS CONVERGES
text: To begin with, we will prove the sum of squared norm of gradients along the trajectory is finite for gradient descent with momentum. To see this, we first define the continuous-time update rule as
w(t+ α)−w(t) = α(w(t+ 1)−w(t)),∀t ∈ Z+,∀α ∈ [0, 1].
We then prove a generalized case of Lemma 1 for any w(t+ α). Lemma 14 (Lemma 1, extended). Let all conditions in Theorem 2 hold. We then have
L(w(t)) + β 2η ‖w(t)−w(t− 1)‖2 ≥L(w(t+ α)) + β 2η α2‖w(t+ 1)−w(t)‖2
+ (1− β)(1− C1)α2
η ‖w(t+ 1)−w(t)‖2,
where C1 is a positive real such that η = 2 1−βHs0 C1.
Proof of Lemma 14. For brevity, we denote s0 4 = `−1(NL(w1)). We prove this lemma by reduction to absurdity.
Concretely, let t∗ be the smallest positive integer time such that there exists an α ∈ [0, 1], such that Eq. (7) doesn’t hold. Let α∗ = inf{α ∈ [0, 1] : Eq. (7) doesn′t hold for (t∗, α)}. By continuity, Eq. (7) holds for (t∗, α∗).
We further divide the proof into two cases depending on the value of α∗.
Case 1: α∗ = 0: For any t∗ > t ≥ 1, we have Eq. (7) holds for (t, 1). Specifically, we have
L(w(t)) + β 2η ‖w(t)−w(t− 1)‖2 ≥ L(w(t+ 1)) + β 2η ‖w(t+ 1)−w(t)‖2,
which further leads to
L(w(1)) = L(w(1)) + β 2η ‖w(1)−w(0)‖2 ≥ L(w(t∗)) + β 2η ‖w(t∗)−w(t∗ − 1)‖2.
Since β2η‖w(t ∗)−w(t∗ − 1)‖2 is non-negative, we have
L(w(1)) ≥ L(w(t∗)).
By Lemma 10, we have L is Hs0 smooth at w(t∗). Therefore, by Taylor’s expansion for L at point w(t∗), we have for small enough α > 0
L(w(t∗ + α))
≤L(w(t∗)) + 〈∇L(w(t∗)),w(t∗ + α)−w(t∗)〉+ Hs0 2 ‖w(t∗ + α)−w(t∗)‖2 =L(w(t∗)) + α〈∇L(w(t∗)),w(t∗ + 1)−w(t∗)〉+ Hs0α 2
2 ‖w(t∗ + 1)−w(t∗)‖2
(∗) =L(w(t∗)) + α
〈 1
η (β(w(t∗)−w(t∗ − 1))− (w(t∗ + 1)−w(t∗))),w(t∗ + 1)−w(t∗) 〉 + Hs0α 2
2 ‖w(t∗ + 1)−w(t∗)‖2
=L(w(t∗)) + αβ η 〈(w(t∗)−w(t∗ − 1),w(t∗ + 1)−w(t∗)〉+
( Hs0α 2
2 − α η
) ‖w(t∗ + 1)−w(t∗)‖2
(∗∗) ≤ L(w(t∗)) + αβ 2η ‖(w(t∗)−w(t∗ − 1)‖2 + αβ 2η ‖(w(t∗ + 1)−w(t∗)‖2
+
( Hs0α 2
2 − α η
) ‖w(t∗ + 1)−w(t∗)‖2
=L(w(t∗)) + αβ 2η ‖(w(t∗)−w(t∗ − 1)‖2 +
( αβ
2η − α η + Hs0α
2
2
) ‖(w(t∗ + 1)−w(t∗)‖2
=L(w(t∗)) + β 2η ‖(w(t∗)−w(t∗ − 1)‖2 − (1− α)β 2η ‖(w(t∗)−w(t∗ − 1)‖2
+
( αβ
2η − α η + Hs0α
2
2
) ‖(w(t∗ + 1)−w(t∗)‖2
( ) ≤L(w(t∗)) + β 2η ‖w(t∗)−w(t∗ − 1)‖2 − β 2η α2‖w(t∗ + 1)−w(t∗)‖2
− (1− β)(1− C1)α 2
η ‖w(t∗ + 1)−w(t∗)‖2, (22)
where Eq. (∗) is due to a simple rearrangement of the update rule of gradient descent with momentum (Eq. (5)), i.e.,
∇L(w(t)) = 1 η (β(w(t)−w(t− 1))− (w(t+ 1)−w(t))),∀t ≥ 1, (23)
Inequality (∗∗) is due to Cauchy Schwarz’s inequality and arithmetic-geometric average inequality, and Inequality ( ) is due to
− (1− α)β 2η
‖(w(t∗)−w(t∗ − 1)‖2 + ( αβ
2η − α η + Hs0α
2
2
) ‖(w(t∗ + 1)−w(t∗)‖2
=− (1− α)β 2η ‖(w(t∗)−w(t∗ − 1)‖2 +O(α)
≤O(α2)
=− β 2η α2‖w(t∗ + 1)−w(t∗)‖2 − (1− β)(1− C1)α 2 η ‖w(t∗ + 1)−w(t∗)‖2.
Here the inequality is due to that− (1−α)β2η ‖(w(t ∗)−w(t∗−1)‖2 tend to− β2η‖(w(t ∗)−w(t∗−1)‖2 as α tend to zero, which is a negative constant by Lemma 13.
Eq. (22) indicates Eq. (7) holds at (t∗, α) for α > 0 is small enough, which contradicts to α∗ = 0.
Case 2: α∗ 6= 0: Same as Case 1, we have for any 1 ≤ t < t∗,
L(w(t)) + β 2η ‖w(t)−w(t− 1)‖2 ≥ L(w(t+ 1)) + β 2η ‖w(t+ 1)−w(t)‖2,
which further leads to
L(w(1)) ≥ L(w(t∗)) + β 2η ‖w(t∗)−w(t∗ − 1)‖2. (24)
On the other hand, by the definition of α∗, we have for any 0 ≤ α < α∗, we have Eq. (7) holds for (t∗, α), which by continuity further leads to Eq. (7) holds for (t∗, α∗). Therefore, α∗ < 1, otherwise, Eq. (7) holds for (t∗, α), ∀α ∈ [0, 1] which contradicts the definition of t∗. Combining Eq. (7) with (t∗, α) and Eq. (24), we further have
L(w(1)) ≥ L(w(t∗ + α)) + β 2η α2‖w(t+ 1)−w(t)‖2 + 1− C1 2C1 Hs0α 2‖w(t+ 1)−w(t)‖2,
Consequently, for any α ∈ [0, α∗]
L(w(1)) ≥ L(w(t∗ + α)),
and by Lemma 10, we then have L is Hs0 smooth at w(t∗ + α), which further by Taylor’s expansion leads to
L(w(t∗ + α∗))
≤L(w(t∗)) + 〈∇L(w(t∗)),w(t∗ + α∗)−w(t∗)〉+ Hs0 2 ‖w(t∗ + α∗)−w(t∗)‖2
(◦) ≤L(w(t∗)) + α ∗β
2η ‖w(t∗)−w(t∗ − 1)‖2 + α
∗β
2η ‖w(t∗ + 1)−w(t∗)‖2
+
( Hs0(α ∗)2
2 − α
∗
η
) ‖w(t∗ + 1)−w(t∗)‖2
=L(w(t∗)) + α ∗β
2η ‖w(t∗)−w(t∗ − 1)‖2 +
( Hs0(α ∗)2
2 − α ∗(2− β) 2η
) ‖w(t∗ + 1)−w(t∗)‖2
(•) =L(w(t∗)) + α
∗β
2η ‖w(t∗)−w(t∗ − 1)‖2 +
( (1− β)C1(α∗)2
η − α ∗(2− β) 2η
) ‖w(t∗ + 1)−w(t∗)‖2
(∗) <L(w(t∗)) + β 2η ‖w(t∗)−w(t∗ − 1)‖2 − (α
∗)2β 2η ‖w(t∗ + 1)−w(t∗)‖2
− (1− β)(1− C1)(α ∗)2
η ‖w(t∗ + 1)−w(t∗)‖2
where Eq. (◦) follows the same routine as Case 1, Eq. (•) is due to the definition of η and C1, and Eq. (∗) is due to α∗ < 1, and ‖w(t∗ + 1)−w(t∗)‖2 > 0 (given by Lemma 13). By the continuity of L, for any small enough δ > 0, Eq. (7) holds for (t∗, α∗ + δ), which contradicts to the definition of α∗.
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
∞∑ t=1 ‖w(t+ 1)−w(t)‖2 <∞. (25)
Consequentially, we have ‖w(t)‖ = O( √ t).
Proof. By Lemma 1, we have
L(w(t)) + β 2η ‖w(t)−w(t− 1)‖2−
( L(w(t+ 1)) + β
2η ‖w(t+ 1)−w(t)‖2 ) ≥ (1− C1)(1− β)
η ‖w(t+ 1)−w(t)‖2,
which by summing over t further leads to L(w(1)) ≥ L(w(1))− ( L(w(t+ 1)) + β
2η ‖w(t+ 1)−w(t)‖2
) ≥ (1− C1)(1− β)
η
t∑ s=1 ‖w(s+1)−w(s)‖2.
Taking t→∞ leads to ∞∑ s=1 ‖w(s+ 1)−w(s)‖2 <∞.
By triangle inequality, we further have
‖w(t)‖ ≤ t∑
s=1
‖w(s+ 1)−w(s)‖+ ‖w(1)‖
(?) ≤ √√√√t( t∑ s=1 ‖w(s+ 1)−w(s)‖2 ) + ‖w(1)‖ = O( √ t),
where Eq. (?) 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
‖w(t+ 1)−w(t)‖2 =η2 ∥∥∥∥∥ t∑ s=1 βt−s ∑N i=1 ` ′(〈w(s), x̃i〉)x̃i N ∥∥∥∥∥ 2
=η2 ∥∥∥∥∥ t∑
s=1
βt−s ∑N i=1 `
′(〈w(s), x̃i〉)x̃i N ∥∥∥∥∥ 2 ‖ŵ‖2 ‖ŵ‖2
(∗) ≥η2γ2 〈 ŵ,
t∑ s=1 βt−s ∑N i=1 ` ′(〈w(s), x̃i〉)x̃i N 〉2 (∗∗) ≥ η2γ2 ( t∑
s=1
βt−s ∑N i=1 `
′(〈w(s), x̃i〉) N
)2
≥η2γ2 (∑N
i=1 ` ′(〈w(t), x̃i〉) N )2 (•) ≥η2γ2 (∑N i=1 `
′(〈w(t), x̃i〉)‖x̃i‖ N
)2
≥η2γ2 ∥∥∥∥∥ ∑N i=1 ` ′(〈w(t), x̃i〉)x̃i N ∥∥∥∥∥ 2
=η2γ2 ‖∇L(w(t))‖2 , (26)
where Inequality (∗) is due to Cauchy-Schwartz’s inequality, Inequality (∗∗) is due to `′(s) < 0, ∀s ∈ R and 〈ŵ, x̃i〉 ≥ γ, ∀i ∈ [N ], and Inequality (•) is due to ‖x̃i‖ ≤ 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, limt→∞ ‖∇L(w(t))‖ = 0, and
lim t→∞ 〈w(t), x̃i〉 =∞,∀i.
Consequently, there exists an large enough time t0, such that, ∀t > t0, ∀i, we have 〈w(t), x̃i〉 > 0, and
−`′(〈w(t), x̃i〉) ≤ (1 + e−µ+〈w(t),x̃i〉)e−〈w(t),x̃i〉, −`′(〈w(t), x̃i〉) ≥ (1− e−µ−〈w(t),x̃i〉)e−〈w(t),x̃i〉.

heading: B.1.2 BOUNDING THE ORTHOGONAL PART
text: To prove Theorem 2, we only need to show w(t) − log(t)ŵ (t ≥ 1) has bounded norm for any iteration t > 0. Letting C2 = η(1−β)N in Corollary 2, we obtain an constant vector w̃ satisfying Eq. (12). Define
r(t) 4 = w(t)− log(t)ŵ − w̃. (27)
As w̃ is a constant vector, that w(t)− log(t)ŵ (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 ‖r(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, ‖r(t)‖ is bounded if and only if function g(t) is upper bounded. Proof. We start the proof by showing that A1(t) 4 = ∑t τ=2〈r(τ)− r(τ − 1),w(τ)−w(τ − 1)〉 has bounded absolute value.
By the definition of r(t) , we have r(t)− r(t− 1) =w(t)−w(t− 1)− log ( t
t− 1
) ŵ,
which further indicates
A1(t) = t∑ τ=2 〈 w(τ)−w(τ − 1)− log ( τ τ − 1 ) ŵ,w(τ)−w(τ − 1) 〉 .
Therefore, the absolute value of A1(t) can be bounded as
|A1(t)| = ∣∣∣∣∣ t∑
τ=2
〈 w(τ)−w(τ − 1)− log ( τ
τ − 1
) ŵ,w(τ)−w(τ − 1) 〉∣∣∣∣∣ ≤
t∑ τ=2 ∣∣∣∣〈w(τ)−w(τ − 1)− log( ττ − 1 ) ŵ,w(τ)−w(τ − 1) 〉∣∣∣∣ ≤
t∑ τ=2 ‖w(τ)−w(τ − 1)‖2 + t∑ τ=2 ∣∣∣∣〈log( ττ − 1 ) ŵ,w(τ)−w(τ − 1) 〉∣∣∣∣ ≤
t∑ τ=2 ‖w(τ)−w(τ − 1)‖2 + t∑ τ=2 ∥∥∥∥log( ττ − 1 ) ŵ ∥∥∥∥ ‖w(τ)−w(τ − 1)‖ (?) ≤ 3 2 t∑ τ=2 ‖w(τ)−w(τ − 1)‖2 + 1 2 t∑ τ=2 ∥∥∥∥log( ττ − 1 ) ŵ
∥∥∥∥2 (◦) <∞,
where Inequality (?) is due to the Inequality of arithmetic and geometric means, and Inequality (◦) is due to Corollary 3 and log ττ−1 = O( 1 τ ).
Therefore, g(t) is upper bounded is then equivalent to 12‖r(t)‖ 2 + β1−β 〈r(t),w(t)−w(t− 1)〉 is upper bounded. Now if 12‖r(t)‖ 2 + β1−β 〈r(t),w(t)−w(t− 1)〉 is upper bounded, we will prove ‖r(t)‖ is bounded by reduction to absurdity. Suppose that ‖r(t)‖ has unbounded norm. By Corollary 3, we have limt→∞ ‖w(t)−w(t−1)‖ = 0, and there exists a large enough time T , such that ‖w(t) −w(t − 1)‖ < 1 for any t ≥ T . On the other hand, since r(t) is unbounded from above, there exists an increasing time sequence ki > T , i ∈ Z+, such that
lim i→∞
‖r(ki)‖ =∞.
Therefore, we have
lim i→∞
1 2 ‖r(ki)‖2 + β 1− β 〈r(ki),w(ki)−w(ki − 1)〉
≥ lim i→∞
1 2 ‖r(ki)‖2 − β 1− β ‖r(ki)‖ ‖w(ki)−w(ki − 1)‖
≥ lim i→∞
1 2 ‖r(ki)‖2 − β 1− β ‖r(ki)‖ =∞,
which leads to contradictory, and completes the proof of necessity.
On the other hand, if ‖r(t)‖ is upper bounded, since ‖w(t) − w(t − 1)‖ is also upper bounded, we have 12‖r(t)‖
2 + β1−β 〈r(t),w(t)−w(t− 1)〉 is upper bounded, which completes the proof of sufficiency.
The proof is completed.
Therefore, the last piece of this puzzle is to prove g(t) is upper bounded ∀t > 0. Lemma 16 (Second argument in Lemma 2). Let all conditions in Theorem 2 hold. Then, we have g(t) is upper bounded.
Proof. We start the proof by calculating g(t+ 1)− g(t). For any t ≥ 2, we have
g(t+ 1)− g(t) =1 2 ‖r(t+ 1)− r(t)‖2 + 〈r(t), r(t+ 1)− r(t)〉+ β 1− β 〈r(t+ 1),w(t+ 1)−w(t)〉
− β 1− β 〈r(t),w(t)−w(t− 1)〉 − β 1− β 〈r(t+ 1)− r(t),w(t+ 1)−w(t)〉
= 1 2 ‖r(t+ 1)− r(t)‖2 + 〈r(t), r(t+ 1)− r(t)〉+ β 1− β 〈r(t),w(t+ 1) + w(t− 1)− 2w(t)〉.
On the other hand, by simply rearranging the update rule Eq. (5), we have
β 1− β (w(t+ 1) + w(t− 1)− 2w(t)) = − η 1− β ∇L(w(t))− (w(t+ 1)−w(t)), (28)
which further indicates
g(t+ 1)− g(t)
= 1
2 ‖r(t+ 1)− r(t)‖2 + 〈r(t), r(t+ 1)− r(t)〉+
〈 r(t),− η
1− β ∇L(w(t))− (w(t+ 1)−w(t)) 〉 = 1
2 ‖r(t+ 1)− r(t)‖2 +
〈 r(t),− log ( t+ 1
t
) ŵ − η
1− β ∇L(w(t))
〉 .
Denote A2(t) = ‖r(t + 1) − r(t)‖2, and A3(t) = 〈 r(t),− log ( t+1 t ) ŵ − η1−β∇L(w(t)) 〉 . We
then prove respectively ∑∞ t=1A2(t) and ∑∞ t=1A3(t) are upper bounded.
First of all, by definition of r(t) Eq.(27), we have ∞∑ t=1 A2(t) = ∞∑ t=1 ( ‖w(t+ 1)−w(t)‖2 + log ( t+ 1 t )2 ‖ŵ‖2 − 2 log ( t+ 1 t ) 〈w(t+ 1)−w(t), ŵ〉 )
≤2 ∞∑ t=1
( ‖w(t+ 1)−w(t)‖2 + log ( t+ 1
t
)2 ‖ŵ‖2 ) (•) < ∞, (29)
where Eq. (•) is due to Lemma 3 and log ( t+1 t ) = O( 1t ).
Then we only need to prove ∑∞ t=1A3(t) <∞.
To begin with, by adding one additional term 1t ŵ into A3, we have
A3(t) =
〈 r(t), 1
t ŵ − log
( t+ 1
t
) ŵ 〉 + 〈 r(t),−1
t ŵ − η 1− β ∇L(w(t))
〉 .
On the one hand, by Corollary 3, ‖w(t)‖ = O( √ t), which further leads to
‖r(t)‖ = ‖w(t)‖+ log(t)‖ŵ‖+ ‖ŵ‖ = O( √ t)
By 1t − log t+1 t = O ( 1 t2 ) , we have〈
r(t), 1
t ŵ − log
( t+ 1
t
) ŵ 〉 = O ( 1
t 3 2
) . (30)
On the other hand, by direct calculation of the gradient, we have〈 r(t),−1
t ŵ − η 1− β ∇L(w(t)) 〉 = 〈 r(t),−1
t ŵ − η (1− β)N N∑ i=1 `′(〈w(t), x̃i〉)x̃i 〉 (?) = 1
N
〈 r(t),−1
t
η 1− β ∑
x̃i∈T (Ss)
e−〈w̃,x̃i〉x̃i − η
1− β N∑ i=1 `′(〈w, x̃i〉)x̃i
〉
= 1
N
〈 r(t),− η 1− β ∑
x̃i∈T (Ss)
( 1
t e−〈w̃,x̃i〉 + `′(〈w(t), x̃i〉)
) x̃i 〉 − 1 N 〈 r(t), η 1− β ∑
x̃i /∈T (Ss)
`′(〈w(t), x̃i〉)x̃i 〉 ,
where Eq. (?) is due to the definition of w̃ (Eq. (12) with C2 = η1−β ).
Denote
A4(t) = − 〈 r(t), η 1− β ∑
x̃i /∈T (Ss)
`′(〈w(t), x̃i〉)x̃i 〉 ,
and
A5(t) =
〈 r(t),− η 1− β ∑
x̃i∈T (Ss)
( 1
t e−〈w̃,x̃i〉 + `′(〈w(t), x̃i〉)
) x̃i 〉 .
We then analysis these two terms respectively. As for A4(t), due to `′ < 0, we have
A4(t) ≤ − η
1− β
〈 r(t),
∑ x̃i /∈T (Ss),〈r(t),x̃i〉>0 `′(〈w(t), x̃i〉)x̃i
〉 .
By Corollary 4, we further have ∀t > t0 −`′(〈w(t), x̃i〉) ≤ (1 + e−µ+〈w(t),x̃i〉)e−〈w(t),x̃i〉 ≤ 2e−〈w(t),x̃i〉, which further indicates A4(t) ≤− η 1− β ∑
x̃i /∈T (Ss),〈r(t),x̃i〉>0
`′(〈w(t), x̃i〉) 〈r(t), x̃i〉
≤ η 1− β ∑ x̃i /∈T (Ss),〈r(t),x̃i〉>0 2e−〈w(t),x̃i〉 〈r(t), x̃i〉 = η 1− β ∑
x̃i /∈T (Ss),〈r(t),x̃i〉>0
2e−〈r(t)+log tŵ+w̃,x̃i〉 〈r(t), x̃i〉
≤ η 1− β ( max i e〈−w̃,x̃i〉 ) ∑ x̃i /∈T (Ss),〈r(t),x̃i〉>0 2e−〈r(t)+log tŵ,x̃i〉 〈r(t), x̃i〉
(◦) ≤ η
1− β
( maxi e 〈−w̃,x̃i〉 )
tθ
∑ x̃i /∈T (Ss),〈r(t),x̃i〉>0 2e−〈r(t),x̃i〉 〈r(t), x̃i〉
( ) ≤ η
1− β
( maxi e 〈−w̃,x̃i〉 )
tθ 2N,
where θ in Eq. (◦) is defined as
θ = min x̃i /∈T (Ss)
〈x̃i, ŵ〉 > 1. (31)
As ∑∞ t=1 1 tθ <∞, we have
∞∑ t=1 A4(t) <∞4. (32)
For each term 〈 r(t),− η1−β ( 1 t e −〈w̃,x̃i〉 + `′(〈w, x̃i〉) ) x̃i 〉 (x̃i /∈ T (Ss)) in A5(t), we divide the analysis into two parts depending on the sign of 〈r(t),xi〉. Case 1: 〈r(t), x̃i〉 ≥ 0. By Corollary 4, we have〈
r(t),− η 1− β
( 1
t e−〈w̃,x̃i〉 + `′(〈w, x̃i〉)
) x̃i 〉 =− η
1− β
( 1
t e−〈w̃,x̃i〉 + `′(〈w, x̃i〉)
) 〈r(t), x̃i〉
≤ η 1− β ( −1 t e−〈w̃,x̃i〉 + (1 + e−µ+〈w(t),x̃i〉)e−〈w(t),x̃i〉 ) 〈r(t), x̃i〉
( ) =
η
1− β ( −1 t e−〈w̃,x̃i〉 + (1 + e−µ+〈r(t)+log tŵ+w̃,x̃i〉)e−〈r(t)+log tŵ+w̃,x̃i〉 ) 〈r(t), x̃i〉 ,
where Eq. ( ) is due to the definition of r(t) (Eq. (27). Since 〈r(t), x̃i〉 ≥ 0, we further have〈
r(t),− η 1− β
( 1
t e−〈w̃,x̃i〉 + `′(〈w, x̃i〉)
) x̃i 〉 ≤ η
1− β ( −1 t e−〈w̃,x̃i〉 + (1 + e−µ+〈log tŵ+w̃,x̃i〉)e−〈r(t)+log tŵ+w̃,x̃i〉 ) 〈r(t), x̃i〉
( ) =
η
1− β ( −1 t e−〈w̃,x̃i〉 + 1 t (1 + t−µ+e−µ+〈w̃,x̃i〉)e−〈r(t)+w̃,x̃i〉 ) 〈r(t), x̃i〉
= η 1− β 1 t e−〈w̃,x̃i〉
( −1 + (1 + t−µ+e−µ+〈w̃,x̃i〉)e−〈r(t),x̃i〉 ) 〈r(t), x̃i〉 ,
where Eq. ( ) is due to 〈ŵ, x̃i〉 = 1, ∀x̃i ∈ T (Ss). Specifically,
− 1 + (1 + t−µ+e−µ+〈w̃,x̃i〉)e−〈r(t),x̃i〉
=− 1 + e−〈r(t),x̃i〉 + t−µ+e−µ+〈w̃,x̃i〉e−〈r(t),x̃i〉
≤t−µ+e−µ+〈w̃,x̃i〉e−〈r(t),x̃i〉.
Therefore,
η 1− β 1 t e−〈w̃,x̃i〉
( −1 + (1 + t−µ+e−µ+〈w̃,x̃i〉)e−〈r(t),x̃i〉 ) 〈r(t), x̃i〉
≤ η 1− β 1 t e−〈w̃,x̃i〉
( t−µ+e−µ+〈w̃,x̃i〉e−〈r(t),x̃i〉 ) 〈r(t), x̃i〉
≤ η (1− β)e 1 t1+µ+ e−(1+µ+)〈w̃,x̃i〉 = O
( 1
t1+µ+
) .
4In this paper, for a real series {ri}∞i=1, we use ∑∞ i=1 ri < ∞ representing ∑T i=1 ri is uniformly upper
bounded for any T .
Case 2: 〈r(t), x̃i〉 < 0. Similar to Case 1., in this case we have〈 r(t),− η
1− β
( 1
t e−〈w̃,x̃i〉 + `′(〈w, x̃i〉)
) x̃i 〉 ≤ η
1− β ( −1 t e−〈w̃,x̃i〉 + ( 1− e−µ−〈w(t),x̃i〉 ) e−〈w(t),x̃i〉 ) 〈r(t), x̃i〉
= η
1− β ( −1 t e−〈w̃,x̃i〉 + ( 1− e−µ−〈r(t)+log tŵ+w̃,x̃i〉 ) e−〈r(t)+log tŵ+w̃,x̃i〉 ) 〈r(t), x̃i〉
= η 1− β 1 t e−〈w̃,x̃i〉
( −1 + ( 1− e−µ−〈r(t)+log tŵ+w̃,x̃i〉 ) e−〈r(t),x̃i〉 ) 〈r(t), x̃i〉 .
Specifically, if 〈r(t), x̃i〉 ≥ −t−0.5µ− ,∣∣∣∣ η1− β 1t e−〈w̃,x̃i〉 (−1 + (1− e−µ−〈r(t)+log tŵ+w̃,x̃i〉)e−〈r(t),x̃i〉) 〈r(t), x̃i〉 ∣∣∣∣
= ∣∣∣∣ η1− β 1t e−〈w̃,x̃i〉 (−1 + (1− t−µ−e−µ−〈r(t)+w̃,x̃i〉)e−〈r(t),x̃i〉) 〈r(t), x̃i〉 ∣∣∣∣
≤ η 1− β
1
t1+0.5µ− e−〈w̃,x̃i〉 ∣∣∣−1 + (1− t−µ−e−µ−〈r(t)+w̃,x̃i〉) e−〈r(t),x̃i〉∣∣∣ (†) =O ( 1
t1+0.5µ−
) ,
where Eq. (†) is due to if 〈r(t), x̃i〉 ≥ −t−0.5µ− ,
lim t→∞ ∣∣∣−1 + (1− t−µ−e−µ−〈r(t)+w̃,x̃i〉) e−〈r(t),x̃i〉∣∣∣ = 0. If −2 ≤ 〈r(t), x̃i〉 < −t−0.5µ− , we have
η 1− β 1 t e−〈w̃,x̃i〉
( −1 + ( 1− e−µ−〈r(t)+log tŵ+w̃,x̃i〉 ) e−〈r(t),x̃i〉 ) 〈r(t), x̃i〉
= η 1− β 1 t e−〈w̃,x̃i〉
( −1 + ( 1− 1
tµ− e−µ−〈r(t)+w̃,x̃i〉
) e−〈r(t),x̃i〉 ) 〈r(t), x̃i〉
≤ η 1− β 1 t e−〈w̃,x̃i〉
( −1 + ( 1− e 2µ−
tµ− e−µ−〈w̃,x̃i〉
) e−〈r(t),x̃i〉 ) 〈r(t), x̃i〉 .
Therefore, when t is large enough, 1− e 2µ− tµ− e −µ−〈w̃,x̃i〉 > 0, which by e−〈r(t),x̃i〉 ≥ 1− 〈r(t), x̃i〉 leads to
η 1− β 1 t e−〈w̃,x̃i〉
( −1 + ( 1− e 2µ−
tµ− e−µ−〈w̃,x̃i〉
) e−〈r(t),x̃i〉 ) 〈r(t), x̃i〉
≤ η 1− β 1 t e−〈w̃,x̃i〉
( −1 + ( 1− e 2µ−
tµ− e−µ−〈w̃,x̃i〉
) (1− 〈r(t), x̃i〉) ) 〈r(t), x̃i〉
≤ η 1− β 1 t e−〈w̃,x̃i〉
( −1 + ( 1− e 2µ−
tµ− e−µ−〈w̃,x̃i〉
)( 1 + 1
t0.5µ−
)) 〈r(t), x̃i〉
= η 1− β 1 t e−〈w̃,x̃i〉
( 1
t0.5µ− + o
( 1
t0.5µ−
)) 〈r(t), x̃i〉 < 0.
If −2 > 〈r(t), x̃i〉,
η 1− β 1 t e−〈w̃,x̃i〉
( −1 + ( 1− e−µ−〈r(t)+log tŵ+w̃,x̃i〉 ) e−〈r(t),x̃i〉 ) 〈r(t), x̃i〉
= η 1− β 1 t e−〈w̃,x̃i〉
( −1 + ( 1− e−µ−〈w(t),x̃i〉 ) e−〈r(t),x̃i〉 ) 〈r(t), x̃i〉 .
For large enough t, 1− e−µ−〈w(t),x̃i〉 > 12 , and
η 1− β 1 t e−〈w̃,x̃i〉
( −1 + ( 1− e−µ−〈w(t),x̃i〉 ) e−〈r(t),x̃i〉 ) 〈r(t), x̃i〉
≤ η 1− β 1 t e−〈w̃,x̃i〉
( −1 + ( 1− e−µ−〈w(t),x̃i〉 ) e2 ) 〈r(t), x̃i〉
≤ η 1− β 1 t e−〈w̃,x̃i〉
( −1 + e 2
2
) 〈r(t), x̃i〉 < 0.
Therefore, in Case 2., for large enough t, we have〈 r(t),− η
1− β
( 1
t e−〈w̃,x̃i〉 + `′(〈w, x̃i〉)
) x̃i 〉 ≤ O ( 1
t1+0.5µ−
) .
Combining Case 1. and Case 2., we conclude that A5(t) ≤ O (
1
t1+0.5µ+
) ,
which further yields ∞∑ t=1 A5(t) <∞. (33) Combining Eq. (32) and Eq. (33), we conclude that ∑∞ t=1A3(t) <∞, which together with Eq. (29)
yields ∑∞ t=2 g(t+ 1)− g(t) <∞, and completes the proof.
We are now ready to prove Theorem 2.
Proof of Theorem 2. By Lemma 16, we have g(t) is upper bounded. Therefore, by Lemma 2, we have ‖r(t)‖ is bounded, which further indicates ‖w(t)− log(t)ŵ‖ is bounded. Therefore, the direction of w(t) can be calculated as
w(t)
‖w(t)‖ =
log(t)ŵ ‖w(t)‖ + w(t)− log(t)ŵ ‖w(t)‖ = log(t)ŵ ‖ log(t)ŵ + w(t)− log(t)ŵ‖ + w(t)− log(t)ŵ ‖w(t)‖
= ŵ∥∥∥ŵ + w(t)−log(t)ŵlog t ∥∥∥ + w(t)− log(t)ŵ ‖w(t)‖ → ŵ ‖ŵ‖ (as t→∞).
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.1, we will first prove that the sum of the squared gradient norms along the trajectory is finite. One may expect L(w(t)) + β2η‖w(t)−w(t− 1)‖ 2 is a Lyapunov function of SGDM. However, due to the randomness of the update rule of SGDM, L(w(t)) + β2η‖w(t)−w(t− 1)‖ 2 may no longer decrease (we will show this in the end of Appendix B.2, please see Appendix B.2.3 for explanation).

heading: B.2.1 PROOF OF THE SUM OF GRADIENTS ALONG THE TRAJECTORY IS FINITE
text: We first provide a proof of Lemma 3.
Proof of Lemma 3. We denote the parameter of the t-th step in Eq. (9) as w̃, while that in Eq. (1) as w(t). With w(1) = w̃(1), we will prove w̃(t) = w(t), ∀t > 1 iteratively. Specifically, suppose for any 1 ≤ k ≤ t w(k) = w̃(k). Then, we have
u(t+ 1) = −η̃∇LB(t)(w̃(t)) + u(t) = −η̃∇LB(t)(w(t)) + u(t) = −η̃∇LB(t)(w(t))− η̃∇LB(t−1)(w(t− 1)) + u(t− 1)
= · · · = − t∑
k=1
η̃∇LB(k)(w(k)) + u(1) = − t∑
k=1
η̃∇LB(k)(w(k)) + w(1).
Therefore,
w̃(t+ 1) = βw̃(t) + (1− β)u(t+ 1) = βw̃(t) + (1− β) ( −
t∑ k=1 η̃∇LB(k)(w̃(k)) + w̃(1)
) ,
which by iteration further indicates
w̃(t+1) = w̃(1)−η̃
( t∑
k=1
(1− βt+1−k)∇LB(k)(w̃(k)) ) = w(1)−η̃ ( t∑
k=1
(1− βt+1−k)∇LB(k)(w(k)) ) ,
w(t) = w(1)− η̃ ( t−1∑ k=1 (1− βt−k)∇LB(k)(w(k)) ) ,
and
w(t− 1) = w(1)− η̃ ( t−2∑ k=1 (1− βt−1−k)∇LB(k)(w(k)) ) .
On the other hand, by Eq. (1), we have
w(t+ 1)
=w(t)− η∇LB(t)(w(t)) + β(w(t)−w(t− 1))
=w(1)− η̃ ( t−1∑ k=1 (1− βt−k)∇LB(k)(w(k)) ) − η∇LB(t)(w(t)) + βη̃ ( t−1∑ k=1 (βt−1−k − βt−k)∇LB(k)(w(k)) )
=w(1)− η̃
( t∑
k=1
(1− βt+1−k)∇LB(k)(w(k)) ) = w̃(t+ 1).
The proof is completed.
Using the alternative form given by Lemma 3, we then prove Lemma 4, which indicates L(u(t)) is a 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
L(u(t+ 1)) ≤ L(u(t)) + 〈u(t+ 1)− u(t),∇L(u(t))〉+ H 2 ‖u(t+ 1)− u(t)‖2,
which by Eq. (9) leads to
L(u(t+ 1)) ≤ L(u(t))− η̃〈∇LB(t)(w(t)),∇L(u(t))〉+ Hη̃2
2 ‖∇LB(t)(w(t))‖2. (34)
Taking the expectation of Eq. (34) with respect to w(t+ 1) conditioning on {w(s)}ts=1, we have
Ew(t+1)[L(u(t+ 1))|{w(s)}ts=1] (?) =EB(t)[L(u(t+ 1))|{w(s)}ts=1]
≤EB(t) [ L(u(t))− η̃〈∇LB(t)(w(t)),∇L(u(t))〉+ Hη̃2
2 ‖∇LB(t)(w(t))‖2 ∣∣∣∣ {w(s)}ts=1] (◦) =L(u(t))− η̃〈∇L(w(t)),∇L(u(t))〉+ Hη̃ 2
2 EB(t)
[ ‖∇LB(t)(w(t))‖2 ] (•) ≤L(u(t))− η̃〈∇L(w(t)),∇L(u(t))〉+ Hη̃ 2N
2bγ2 ‖∇L(w(t))‖2, (35)
where Eq. (?) is due to that w(t+ 1) is uniquely determined by B(t) given {w(s)}ts=1, Eq. (◦) is due to u(t) is uniquely determined by {w(s)}ts=1, and Inequality. (•) is due to Lemma 12. Therefore, we have
Ew(t+1)[L(u(t+ 1))|{w(s)}ts=1]
≤L(u(t))− η̃〈∇L(w(t)),∇L(u(t))〉+ Hη̃ 2N
2bγ2 ‖∇L(w(t))‖2
=L(u(t))− η̃〈∇L(w(t)),∇L(w(t))〉+ η̃〈∇L(w(t)),∇L(w(t))−∇L(u(t))〉+ Hη̃ 2N
2bγ2 ‖∇L(w(t))‖2 =L(u(t))− η̃ (
1− Hη̃N 2bγ2
) ‖∇L(w(t))‖2 + 〈η̃∇L(w(t)),∇L(w(t))−∇L(u(t))〉
≤L(u(t))− η̃ (
1− Hη̃N 2bγ2
) ‖∇L(w(t))‖2 + 1
2 ‖η̃∇L(w(t))‖2 + 1 2 ‖∇L(w(t))−∇L(u(t))‖2
=L(u(t))− η̃ ( 1− ( 1
2 + HN 2bγ2
) η̃ ) ‖∇L(w(t))‖2 + 1
2 ‖∇L(w(t))−∇L(u(t))‖2 .
By Assumption 3. (S), ` is H-smooth, which further leads to
‖∇L(w(t))−∇L(u(t))‖2 = ∥∥∥∥∥∥ ∑ x̃∈S̃ (`′(〈x̃,w(t)〉)− `′(〈x̃,u(t)〉)) x̃ ∥∥∥∥∥∥ 2
≤ ∑ x̃∈S̃ |`′(〈x̃,w(t)〉)− `′(〈x̃,u(t)〉)| 2 ≤ H∑ x̃∈S̃ |〈x̃,w(t)〉 − 〈x̃,u(t)〉| 2
≤H2N2‖w(t)− u(t)‖2 ( ) ≤ H 2N2β2
(1− β)2 ‖w(t)−w(t− 1)‖2
= H2N2β2
(1− β)2 ∥∥∥∥∥ t−1∑ s=1 ηβt−1−s∇LB(s)(w(s)) ∥∥∥∥∥ 2 = H2N2η̃2β2 ∥∥∥∥∥ t−1∑ s=1 βt−1−s∇LB(s)(w(s)) ∥∥∥∥∥ 2
( ) ≤H 2N2η̃2β2
γ2
( t−1∑ s=1 βt−1−s ∥∥∇LB(s)(w(s))∥∥ )2 (♣) ≤ H 2N2η̃2β2
γ2
( t−1∑ s=1 βt−1−s ∥∥∇LB(s)(w(s))∥∥2 )( t−1∑ s=1 βt−1−s )
≤H 2N2η̃2β2
γ2(1− β) ( t−1∑ s=1 βt−1−s ∥∥∇LB(s)(w(s))∥∥2 ) , (36)
where Inequality ( ) is due to β(w(t)−w(t− 1)) = (1− β)(u(t)−w(t)) by Eq. (9), Inequality ( ) is due to triangular inequality, and Inequality (♣) is due to Cauchy-Schwartz Inequality.
Combining Eqs. (35) and (36), we have
Ew(t+1)[L(u(t+ 1))|{w(s)}ts=1] ≤L(u(t))− η̃ ( 1− ( 1
2 + HN 2bγ2
) η̃ ) ‖∇L(w(t))‖2 + 1
2
H2N2η̃2β2
γ2(1− β) ( t−1∑ s=1 βt−1−s ∥∥∇LB(s)(w(s))∥∥2 ) ,
which by taking expectation to {w(s)}ts=1 leads to
EFt+1 [L(u(t+ 1))] = E{w(s)}t+1s=1 [L(u(t+ 1))] ≤EFtL(u(t))− EFt η̃ ( 1− ( 1
2 + HN 2bγ2
) η̃ ) ‖∇L(w(t))‖2 + EFt 1
2
H2N2η̃2β2
γ2(1− β) ( t−1∑ s=1 βt−1−s ∥∥∇LB(s)(w(s))∥∥2 )
=EFtL(u(t))− η̃ ( 1− ( 1
2 + HN 2bγ2
) η̃ ) EFt‖∇L(w(t))‖2 + 1
2
H2N2η̃2β2
γ2(1− β) ( t−1∑ s=1 βt−1−sEFs+1 ∥∥∇LB(s)(w(s))∥∥2 ) .
By Lemma 12 and η < min{ 1−β 1+HN bγ2 , (1−β) 3γ4b 2H2N3β2 }, we further have
EFt+1 [L(u(t+ 1))] = E{w(s)}t+1s=1 [L(u(t+ 1))] ≤EFtL(u(t))− η̃ ( 1− ( 1
2 + HN 2bγ2
) η̃ ) EFt‖∇L(w(t))‖2
+ 1
2
H2N3η̃2β2
γ4b(1− β) ( t−1∑ s=1 βt−1−sEFs ‖∇L(w(s))‖ 2 )
≤EFtL(u(t))− η̃
2 EFt‖∇L(w(t))‖2 + 1− β 4 η̃ ( t−1∑ s=1 βt−1−sEFs ‖∇L(w(s))‖ 2 ) . (37)
Summing Eq. (37) with t from 1 to T leads to
E[L(u(T + 1))] = EFT+1 [L(u(T + 1))]
≤L(u(1))− T∑ t=1 η̃ 2 EFt‖∇L(w(t))‖2 + T∑ t=1 1− β 4 η̃ ( t−1∑ s=1 βt−1−sEFs ‖∇L(w(s))‖ 2 )
=L(u(1))− T∑ t=1 η̃ 2 EFt‖∇L(w(t))‖2 + T−1∑ s=1 1− β 4 η̃
( T∑
t=s+1
βt−1−sEFs ‖∇L(w(s))‖ 2
)
≤L(u(1))− T∑ t=1 η̃ 2 EFt‖∇L(w(t))‖2 + T−1∑ s=1 1 4 η̃ ( EFs ‖∇L(w(s))‖ 2 )
≤L(u(1))− T∑ t=1 η̃ 4 EFt‖∇L(w(t))‖2
=L(u(1))− T∑ t=1 η̃ 4 E‖∇L(w(t))‖2.
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
∞∑ t=1 E‖∇L(w(t))‖2 <∞. (38)
Consequently, ∞∑ t=1 ‖∇L(w(t))‖2 <∞ and 〈w(t), x̃〉 → ∞,∀x̃ ∈ S̃
hold almost surely.
Proof. By Lemma 4, we have for any T > 1, T∑ t=1 η̃ 4 E‖∇L(w(t))‖2 ≤ L(u(1))− E[L(u(T + 1))] ≤ L(u(1)) <∞,
which completes the proof of Eq. (38). The rest of claims follows immediately by Fubini’s Theorem and Assumption 2.
The proof is completed.

heading: B.2.2 BOUNDING THE ORTHOGONAL PART
text: Similar to the case of GDM, we define w̃ as the solution of Eq. (12) with C2 = η(1−β)N . We also let n(t) be given by Lemma 9, and define r(t) in this case as
r(t) 4 = w(t)− log(t)ŵ − w̃ − n(t). (39)
As w̃ is a constant vector, and ‖n(t)‖ → 0 as t→∞, we have w(t)− log(t)ŵ has bounded norm if and only if ‖r(t)‖ 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 g : Z+ → R is defined as
g(t) 4 = 1 2 ‖r(t)‖2+ β 1− β 〈r(t),w(t)−w(t−1)〉− β 1− β t∑ τ=2 〈r(τ)−r(τ −1),w(τ)−w(τ −1)〉. (40) Proof. To begin with, we prove that almost surely | ∑t τ=2〈r(τ)− r(τ − 1),w(τ)−w(τ − 1)〉| is upper bounded for any t. By Corollary 5, we have almost surly ∞∑ t=1 ‖∇L(w(t))‖2 <∞.
On the other hand, for any w, we have
‖∇LB(t)(w)‖ = 1
b ∥∥∥∥∥∥ ∑
x̃∈T (B(t))
`′(〈w, x̃〉)x̃ ∥∥∥∥∥∥ ≤− 1
b ∑ x̃∈T (B(t)) `′(〈w, x̃〉) < −1 b ∑ x̃∈T (S) `′(〈w, x̃〉)
≤− 1 b ∑ x̃∈T (S) `′(〈w, x̃〉)〈ŵ, x̃〉 ≤ N b ∥∥∥∥∥∥ 1N ∑ x̃∈T (S) `′(〈w, x̃〉)x̃ ∥∥∥∥∥∥ ‖ŵ‖ = N
bγ ‖∇L(w)‖ .
Therefore, we have almost surely, ∞∑ t=1 ∥∥∇LB(t)(w(t))∥∥2 <∞,
which further leads to almost surely
∞∑ t=1 ‖w(t+ 1)−w(t)‖2 ≤ η2 ∞∑ t=1 ∥∥∥∥∥ t∑ s=1 βt−s∇LB(s)(w(s)) ∥∥∥∥∥ 2
≤η2 ∞∑ t=1
( t∑
s=1
βt−s ∥∥∇LB(s)(w(s))∥∥
)2
≤η2 ∞∑ t=1
( t∑
s=1
βt−s ∥∥∇LB(s)(w(s))∥∥2
)( t∑
s=1
βt−s
)
≤ η 2
1− β ∞∑ s=1 ∥∥∇LB(s)(w(s))∥∥2 ∞∑ t=s βt−s
= η2
1− β ∞∑ s=1 ∥∥∇LB(s)(w(s))∥∥2 <∞. By the definition of r(t) (Eq. (39)), we further have∣∣∣∣∣ t∑ τ=2 〈r(τ)− r(τ − 1),w(τ)−w(τ − 1)〉
∣∣∣∣∣ ≤
t∑ τ=2 |〈r(τ)− r(τ − 1),w(τ)−w(τ − 1)〉|
= t∑ τ=2 ∣∣∣∣〈w(τ)−w(τ − 1)− log(τ + 1τ ) − (n(τ)− n(τ − 1)),w(τ)−w(τ − 1) 〉∣∣∣∣ ≤
t∑ τ=2 ‖w(τ)−w(τ − 1)‖2 + t∑ τ=2 ∣∣∣∣〈− log(τ + 1τ ) − (n(τ)− n(τ − 1)),w(τ)−w(τ − 1) 〉∣∣∣∣ ≤3
2 t∑ τ=2 ‖w(τ)−w(τ − 1)‖2 + 1 2 t∑ τ=2 ∥∥∥∥− log(τ + 1τ ) − (n(τ)− n(τ − 1)) ∥∥∥∥2 (?) ≤ 3 2 t∑ τ=2 ‖w(τ)−w(τ − 1)‖2 + 1 2 t∑ τ=2 O ( 1 τ )2 <∞,
where Inequality (?) is due to ‖n(τ)− n(τ − 1)‖ = O( 1τ ) and log τ+1 τ = O( 1 τ ).
Therefore, g(t) is upper bounded almost surely is equivalent to 12‖r(t)‖ 2+ β1−β 〈r(t),w(t)−w(t−1)〉 is upper bounded, which can be shown to be equivalent with ‖r(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(t+ 1)− g(t)
= 1
2 ‖r(t+ 1)− r(t)‖2 + 〈r(t), r(t+ 1)− r(t)〉+
〈 r(t),− η
1− β ∇LB(t)(w(t))− (w(t+ 1)−w(t))
〉 ,
where ∑∞ t=1 ‖r(t+ 1)− r(t)‖2 is upper bounded.
On the other hand, by the definition of r(t) (Eq. (39)), we have
r(t+ 1)− r(t) =w(t+ 1)−w(t)− log ( t+ 1
t
) ŵ − n(t+ 1) + n(t),
while by Lemma 9,
N
b
1
t ∑ i:x̃i∈T (B(t)∩Ss) vix̃i = log ( t+ 1 t ) ŵ + n(t+ 1)− n(t).
Combining the above two equations, we further have
r(t+ 1)− r(t) = w(t+ 1)−w(t)− N bt ∑ i:x̃i∈T (B(t)∩Ss) vix̃i,
which further indicates
g(t+1)−g(t) = 1 2 ‖r(t+1)−r(t)‖2+
〈 r(t),− η
1− β ∇LB(t)(w(t))−
N
bt ∑ i:x̃i∈T (B(t)∩Ss) vix̃i
〉 .
Therefore, we only need to prove ∑∞ t=1〈r(t),− η 1−β∇L(w(t))− N bt ∑ i:x̃i∈T (B(t)∩Ss) vix̃i〉 <∞. By directly applying the form of∇L(w(t)), we have〈 r(t),− η
1− β ∇LB(t)(w(t))−
N
bt ∑ i:x̃i∈T (B(s)∩Ss) vix̃i
〉
= 〈 r(t),− η (1− β)b ∑
i:x̃i∈T (B(s))
`′(〈w(t), x̃i〉)x̃i − N
bt ∑ i:x̃i∈T (B(s)∩Ss) vix̃i
〉
= η
(1− β)b
〈 r(t),−
∑ i:x̃i∈T (B(s)) `′(〈w(t), x̃i〉)x̃i − N(1− β) η 1 t ∑ i:x̃i∈T (B(s)∩Ss) vix̃i
〉
= η
(1− β)b
〈 r(t),−
∑ i:x̃i∈T (B(s)) `′(〈w(t), x̃i〉)x̃i − 1 t ∑ i:x̃i∈T (B(s)∩Ss) e−〈w̃,x̃i〉x̃i
〉
= η (1− β)b ∑
i:x̃i∈T (B(s)∩Ss)
( −`′(〈w(t), x̃i〉)− 1
t e−〈w̃,x̃i〉
) 〈r(t), x̃i〉
+ η (1− β)b ∑
i:x̃i∈T (B(s)∩Scs)
〈r(t),−`′(〈w(t), x̃i〉)x̃i〉 .
Let A6(t) = ∑ i:x̃i∈T (B(s)∩Ss) ( −`′(〈w(t), x̃i〉)− 1t e −〈w̃(t),x̃i〉 ) 〈r(t), x̃i〉, and A7(t) =∑
i:x̃i∈T (B(s)∩Scs) 〈r(t),−`′(〈w(t), x̃i〉)x̃i〉. We will investigate these two terms respectively.
As 〈w(t), x̃〉 → ∞, ∀x̃ ∈ T (S), a.s., we have a.s., there exists a large enough time t0, s.t., ∀t ≥ t0, ∀x̃ ∈ T (S),
−`′(〈w(t), x̃〉) ≤ (1 + e−µ+〈w(t),x̃〉)e−〈w(t),x̃〉, −`′(〈w(t), x̃i〉) ≥ (1− e−µ−〈w(t),x̃〉)e−〈w(t),x̃〉,
〈x̃,w(t)〉 > 0.
Therefore, A7(t) ≤ ∑
i:x̃i∈T (B(s)∩Scs)
−`′(〈w(t), x̃i〉)〈r(t), x̃i〉1〈r(t),x̃i〉≥0
≤ ∑
i:x̃i∈T (B(s)∩Scs)
(1 + e−µ+〈w(t),x̃i〉)e−〈w(t),x̃i〉〈r(t), x̃i〉1〈r(t),x̃i〉≥0
≤2 ∑
i:x̃i∈T (B(s)∩Scs)
e−〈r(t)+log(t)ŵ+w̃+n(t),x̃i〉〈r(t), x̃i〉1〈r(t),x̃i〉≥0
(?) ≤2 ∑
i:x̃i∈T (B(s)∩Scs)
1 tθ e−〈w̃+n(t),x̃i〉e−〈r(t),x̃i〉〈r(t), x̃i〉1〈r(t),x̃i〉≥0
(†) ≤ 2 e 1 tθ ∑ i:x̃i∈T (B(s)∩Scs) e−〈w̃+n(t),x̃i〉1〈r(t),x̃i〉≥0
(◦) =O
( 1
tθ
) ,
where Inequality. (?) is due the definition of θ (Eq. (31)), Inequality. (†) is due to e−〈r(t),x̃i〉〈r(t), x̃i〉 ≤ e−1 , and Eq. (◦) is due to limt→∞ e−〈w̃+n(t),x̃i〉 = e−〈w̃,x̃i〉. Thus,
∞∑ t=1 A7(t) <∞.
On the other hand, A6(t) can be rewritten as
A6(t) = ∑
i:x̃i∈T (B(s)∩Ss)
( −`′(〈w(t), x̃i〉)− 1
t e−〈w̃(t),x̃i〉
) 〈r(t), x̃i〉1〈r(t),x̃i〉≥0
+ ∑
i:x̃i∈T (B(s)∩Ss)
( −`′(〈w(t), x̃i〉)− 1
t e−〈w̃(t),x̃i〉
) 〈r(t), x̃i〉1〈r(t),x̃i〉<0.
If 〈r(t), x̃i〉 ≥ 0, we have for ε < 0.5,( −`′(〈w(t), x̃i〉)− 1
t e−〈w̃(t),x̃i〉
) 〈r(t), x̃i〉
≤ (( 1 + e−µ+〈w(t),x̃i〉 ) e−〈w(t),x̃i〉 − 1
t e−〈w̃(t),x̃i〉
) 〈r(t), x̃i〉
= (( 1 + e−µ+〈r(t)+log(t)ŵ+w̃+n(t),x̃i〉 ) e−〈r(t)+log(t)ŵ+w̃+n(t),x̃i〉 − 1
t e−〈w̃(t),x̃i〉
) 〈r(t), x̃i〉
= (( 1 + e−µ+〈r(t)+log(t)ŵ+w̃+n(t),x̃i〉 ) e−〈r(t)+n(t),x̃i〉 − 1 ) 1 t 〈r(t), x̃i〉e−〈w̃(t),x̃i〉
≤ (( 1 + 1
tµ+ e−µ+〈w̃+n(t),x̃i〉
) e−〈r(t)+n(t),x̃i〉 − 1 ) 1
t 〈r(t), x̃i〉e−〈w̃(t),x̃i〉
(•) = (( 1 +O ( 1
tµ+
))( 1 +O ( 1
t0.5−ε
)) e−〈r(t),x̃i〉 − 1 ) 1
t 〈r(t), x̃i〉e−〈w̃(t),x̃i〉
= ( e−〈r(t),x̃i〉 − 1 ) 1 t 〈r(t), x̃i〉e−〈w̃(t),x̃i〉 + 1 t O (
1
tmin{µ+,0.5−ε}
) e−〈r(t),x̃i〉〈r(t), x̃i〉e−〈w̃(t),x̃i〉
≤1 t O (
1
tmin{µ+,0.5−ε}
) e−〈r(t),x̃i〉〈r(t), x̃i〉e−〈w̃(t),x̃i〉
( ) =O
( 1
tmin{1+µ+,1.5−ε}
) ,
where Eq. (•) is due to n(t) = O( 1t0.5−ε ), and Eq. ( ) is due to e −〈r(t),x̃i〉〈r(t), x̃i〉 ≤ 1e .
On the other hand, if 〈r(t), x̃i〉 < 0, we have( −`′(〈w(t), x̃i〉)− 1
t e−〈w̃(t),x̃i〉
) 〈r(t), x̃i〉
≤ (( 1− e−µ−〈w(t),x̃i〉 ) e−〈w(t),x̃i〉 − 1
t e−〈w̃(t),x̃i〉
) 〈r(t), x̃i〉
= 1
t e−〈w̃,x̃i〉
( −1 + ( 1− e−µ−〈w(t),x̃i〉 ) e−〈r(t)+n(t),x̃i〉 ) 〈r(t), x̃i〉
Specifically, if 〈r(t), x̃i〉 ≥ −t−0.5min{µ−,0.5},∣∣∣∣1t e−〈w̃,x̃i〉 (−1 + (1− e−µ−〈w(t),x̃i〉) e−〈r(t)+n(t),x̃i〉) 〈r(t), x̃i〉 ∣∣∣∣
≤ 1 t1+0.5min{µ−,0.5}
e−〈w̃,x̃i〉 ∣∣∣−1 + (1− e−µ−〈w(t),x̃i〉) e−〈r(t)+n(t),x̃i〉∣∣∣
( ) =O
( 1
t1+0.5min{µ−,0.5}
) ,
where Eq. ( ) is due to that as 〈w(t), x̃i〉 → ∞ and t−0.5min{µ−,0.5} → 0 as t→∞, there exists a large enough time T , s.t., ∀t > T , under the circumstance 0 > 〈r(t), x̃i〉 ≥ −t−0.5min{µ−,0.5}, e−〈r(t)+n(t),x̃i〉 < 1 and e−µ−〈w(t),x̃i〉 < 1.
If −2 ≤ 〈r(t), x̃i〉 < −t−0.5min{µ−,0.5}, then, for large enough t, |〈x̃i,n(t)〉| < 2, 1 − eµ−(−〈w̃,x̃i〉+4)
tµ− > 0, and
1 t e−〈w̃,x̃i〉
( −1 + ( 1− e−µ−〈w(t),x̃i〉 ) e−〈r(t)+n(t),x̃i〉 ) 〈r(t), x̃i〉
= 1
t e−〈w̃,x̃i〉
( −1 + ( 1− e−µ−〈r(t)+log(t)ŵ+w̃+n(t),x̃i〉 ) e−〈r(t)+n(t),x̃i〉 ) 〈r(t), x̃i〉
= 1
t e−〈w̃,x̃i〉
( −1 + ( 1− e −µ−〈w̃,x̃i〉
tµ− e−µ−〈r(t)+n(t),x̃i〉
) e−〈r(t)+n(t),x̃i〉 ) 〈r(t), x̃i〉
≤1 t e−〈w̃,x̃i〉
( −1 + ( 1− e µ−(−〈w̃,x̃i〉+4)
tµ−
) e−µ−〈r(t)+n(t),x̃i〉 ) 〈r(t), x̃i〉
≤1 t e−〈w̃,x̃i〉
( −1 + ( 1− e µ−(−〈w̃,x̃i〉+4)
tµ−
) (1− µ−〈r(t) + n(t), x̃i〉) ) 〈r(t), x̃i〉
≤1 t e−〈w̃,x̃i〉
( −1 + ( 1− e µ−(−〈w̃,x̃i〉+4)
tµ−
)( 1 + µ−t −0.5min{µ−,0.5} − µ−〈n(t), x̃i〉 )) 〈r(t), x̃i〉
= 1
t e−〈w̃,x̃i〉
( −1 + ( 1− e µ−(−〈w̃,x̃i〉+4)
tµ−
)( 1 + µ−t −0.5min{µ−,0.5} + o ( t−0.5min{µ−,0.5} ))) 〈r(t), x̃i〉
= 1
t e−〈w̃,x̃i〉
( −1 + 1 + µ−t−0.5min{µ−,0.5} + o ( t−0.5min{µ−,0.5} )) 〈r(t), x̃i〉 < 0.
If −2 > 〈r(t), x̃i〉, then for large enough time t, e−〈r(t)+n(t),x̃i〉 ≥ e 3 2 , 1− e−µ−〈w(t),x̃i〉 ≥ e− 12 , and
1 t e−〈w̃,x̃i〉
( −1 + ( 1− e−µ−〈w(t),x̃i〉 ) e−〈r(t)+n(t),x̃i〉 ) 〈r(t), x̃i〉
≤1 t e−〈w̃,x̃i〉 (−1 + e) 〈r(t), x̃i〉 < 0.
Conclusively, if 〈r(t), x̃i〉 < 0, for large enough t, we have( −`′(〈w(t), x̃i〉)− 1
t e−〈w̃(t),x̃i〉
) 〈r(t), x̃i〉 ≤ O ( 1
t1+0.5min{µ−,0.5}
) ,
which further indicates, for large enough t, we have A6(t) ≤ max { O ( 1
t1+0.5min{µ−,0.5}
) ,O (
1
tmin{1+µ+,1.5−ε}
)} ,
which indicates ∞∑ t=1 A6(t) <∞.
Therefore, ∞∑ t=1 (g(t+ 1)− g(t))
= ∞∑ t=1 1 2 ‖r(t+ 1)− r(t)‖2 + 〈 r(t),− η 1− β ∇LB(t)(w(t))− N bt ∑ i:x̃i∈T (B(t)∩Ss) vix̃i 〉 =
∞∑ t=1 ( 1 2 ‖r(t+ 1)− r(t)‖2 + η 1− β A6(t) + η 1− β A7(t) ) <∞.
The proof is completed.

heading: B.2.3 EXPLANATION FOR PROPER LYAPUNOV FUNCTION
text: Based on the success of applying Lyapunov function L(w(t)) + β2η‖w(t)−w(t− 1)‖ 2 to analyze gradient descent with momentum, it is natural to try to extend this routine to analyze stochastic gradient descent with momentum. However, in this section, we will show such Lyapunov function is not proper to analyze SGDM as this will put constraints on the range of the momentum rate β. Specifically, at any step t, since the loss L is H smooth at w(t), we can expand the loss L in the same way as the GDM case:
L(w(t+ 1)) ≤L(w(t)) + 〈w(t+ 1)−w(t),∇L(w(t))〉+ H 2 ‖w(t+ 1)−w(t)‖2.
By taking expectation with respect to w(t+ 1) conditioning on {w(s)}ts=1 for both sides, we further obtain
Ew(t+1) [ L(w(t+ 1)) ∣∣{w(s)}ts=1 ] ≤L(w(t)) + 〈Ew(t+1) [ w(t+ 1)−w(t)
∣∣{w(s)}ts=1 ] ,∇L(w(t))〉+ H2 Ew(t+1) [‖w(t+ 1)−w(t)‖2 ∣∣{w(s)}ts=1 ] (?) =L(w(t)) + 1
η
〈 Ew(t+1) [ w(t+ 1)−w(t) ∣∣{w(s)}ts=1 ] , β (w(t)−w(t− 1))− Ew(t+1) [w(t+ 1)−w(t) ∣∣{w(s)}ts=1 ]〉 + H
2 Ew(t+1)
[ ‖w(t+ 1)−w(t)‖2 ∣∣{w(s)}ts=1 ] =L(w(t)) + β
η
〈 (w(t)−w(t− 1)) ,Ew(t+1) [ w(t+ 1)−w(t) ∣∣{w(s)}ts=1 ]〉 + H
2 Ew(t+1)
[ ‖w(t+ 1)−w(t)‖2 ∣∣{w(s)}ts=1 ]− 1η ∥∥Ew(t+1) [w(t+ 1)−w(t) ∣∣{w(s)}ts=1 ]∥∥2 ≤L(w(t)) + β
2η ‖w(t)−w(t− 1)‖2 + β 2η ∥∥Ew(t+1) [w(t+ 1)−w(t) ∣∣{w(s)}ts=1 ]∥∥2 + H
2 Ew(t+1)
[ ‖w(t+ 1)−w(t)‖2 ∣∣{w(s)}ts=1 ]− 1η ∥∥Ew(t+1) [w(t+ 1)−w(t) ∣∣{w(s)}ts=1 ]∥∥2 , where Eq. (?) is becasue Ew(t+1) [w(t+ 1)−w(t) |{w(s)}ts=1 ] = −η∇L(w(t)) + β (w(t)−w(t− 1)) due to the definition of SGDM (Eq. (1)). Rearranging the above inequal-
ity and taking expectations of both sides with respect to {w(s)}ts=1 leads to
Ew(t+1) [L(w(t+ 1))] + 2− β
2η E{w(s)}ts=1 ∥∥Ew(t+1) [w(t+ 1)−w(t) ∣∣{w(s)}ts=1 ]∥∥2 −H
2 E{w(s)}t+1s=1
[ ‖w(t+ 1)−w(t)‖2 ] ≤Ew(t)L(w(t)) + β
2η E{w(s)}ts=1 ‖w(t)−w(t− 1)‖ 2 . (41)
On the other hand, we wish to obtain some positive constant α from Eq. (41), such that (at least),
Ew(t+1) [L(w(t+ 1))] + αE{w(s)}ts=1 ‖w(t+ 1)−w(t)‖ 2 .
≤Ew(t)L(w(t)) + αE{w(s)}ts=1 ‖w(t)−w(t− 1)‖ 2 , (42)
which requires to lower bound E{w(s)}ts=1 ∥∥Ew(t+1) [w(t+ 1)−w(t) |{w(s)}ts=1 ]∥∥2 by E{w(s)}t+1s=1 ‖ w(t+ 1)−w(t)‖ 2. However, in general cases,
E{w(s)}ts=1 ∥∥Ew(t+1) [w(t+ 1)−w(t) |{w(s)}ts=1 ]∥∥2 is only upper bounded by E{w(s)}t+1s=1 ‖ w(t+ 1)−w(t)‖ 2 (Holder’s Inequality), although in our case,∥∥Ew(t+1) [w(t+ 1)−w(t) |{w(s)}ts=1 ]∥∥2 can be bounded as∥∥Ew(t+1) [w(t+ 1)−w(t) ∣∣{w(s)}ts=1 ]∥∥2
= ‖−η∇L(w(t)) + β (w(t)−w(t− 1))‖2
= ‖−η∇L(w(t))‖2 + ‖β (w(t)−w(t− 1))‖2 + 2βη〈w(t)−w(t− 1),−∇L(w(t))〉,
while Ew(t+1) [ ‖ w(t+ 1)−w(t)‖2 |{w(s)}ts=1 ] can be calculated as
Ew(t+1) [ ‖ w(t+ 1)−w(t)‖2 ∣∣{w(s)}ts=1 ] =EB(t)
∥∥−η∇LB(t)(w(t)) + β(w(t)−w(t− 1))∥∥2 =EB(t)
∥∥−η∇LB(t)(w(t))∥∥2 + ‖β(w(t)−w(t− 1))‖2 + 2ηβEB(t)〈−∇LB(t)(w(t)),w(t)−w(t− 1)〉 =EB(t)
∥∥−η∇LB(t)(w(t))∥∥2 + ‖β(w(t)−w(t− 1))‖2 + 2ηβ〈−∇L(w(t)),w(t)−w(t− 1)〉 ≤ N bγ2 ‖−η∇L(w(t))‖2 + ‖β(w(t)−w(t− 1))‖2 + 2ηβ〈−∇L(w(t)),w(t)−w(t− 1)〉
≤ N bγ2
( ‖−η∇L(w(t))‖2 + ‖β(w(t)−w(t− 1))‖2 + 2ηβ〈−∇L(w(t)),w(t)−w(t− 1)〉 ) = N
bγ2 ∥∥Ew(t+1) [w(t+ 1)−w(t) ∣∣{w(s)}ts=1 ]∥∥2 . (43)
By Eqs. (41) and (43), we have that to ensure Eq. (42), it is required that
2− β 2η bγ2 N − H 2 ≤ β 2η ,
which puts constraint on β that
β ≤ 2 bN γ 2 −Hη 1 + bN γ 2 .
Specifically, β < 2 b N γ 2
1+ bN γ 2 , which approaches 0 when γ approaches 0, and constrains β in a small
range.
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: (1). we first prove the sum of squared gradients along the trajectory is finite. Additionally, we prove the convergent rate of loss is O( 1t ); (2). we prove w(t)− log(t)ŵ has bounded norm. Before we present these two stages of proof, we will first give the required range of η for which Theorem 3 holds.

heading: C.1 CHOICE OF LEARNING RATE
text: Let Hs0 be the smooth parameter over [s0,∞) given by Assumption 3. (D). Let β2 = (cβ1)4 (c > 1). The "sufficiently small learning rate" in Theorem 3 means
η ≤
√ ε inft≥2 ( 1−βt1 1−β1 − 1−βt−11 c(1−β1) 1−(cβ1)t 1−(cβ1)t−1 ) H`−1((1−cβ1)−1NL(w(1))) .
To ensure η is well-defined, we need to prove
inf t≥2 ( 1− βt1 1− β1 − 1− β t−1 1 c(1− β1) 1− (cβ1)t 1− (cβ1)t−1 ) > 0,
and we introduce the following technical lemma: Lemma 19. Define ft(x) = 1−x t
x(1−xt−1) , ∀t ∈ Z, t ≥ 2. We have ft(x) is decreasing with respect to x. Furthermore, for any x ∈ [0, 1), we have
f(x) ≥ 4 √ f(x4). (44)
Proof. First of all, by definition,
f(x) = 1− xt
x− xt = 1 + 1− x x− xt = 1 + 1− x x(1− xt−1) = 1 +
1
x(1 + x+ · · ·+ xt−2) is monotonously decreasing as 0 ≤ x < 1. Secondly, Eq. (44) is equivalent to
(1− xt)4 β41(1− xt−1)4 ≥ (1− x 4t) x4(1− x4(t−1))
⇐⇒ (1− x t)3 (1− xt−1)3 ≥ (1 + x t)(1 + x2t) (1 + xt−1)(1 + x2(t−1)) .
The left side of the above inequality is no smaller than 1, while the right side is no larger than 1, which completes the proof.
We are now ready to prove η is well-defined. First of all, for every t, we have
1− βt1 1− β1 − 1− β t−1 1 c(1− β1) 1− (cβ1)t 1− (cβ1)t−1
= β1(1− βt−11 )
1− β1
( 1− βt1
β1(1− βt−11 ) − 1− (cβ1) t (cβ1)(1− (cβ1)t−1) ) (?) = β1(1− βt−11 )
1− β1 (ft(β1)− ft(cβ1)) > 0, (45)
where Eq. (?) is by Lemma 19 and cβ1 = 4 √ β2 < 1.
On the other hand, we have
lim t→∞ ( 1− βt1 1− β1 − 1− β t−1 1 c(1− β1) 1− (cβ1)t 1− (cβ1)t−1 ) = ( 1− 1 c ) 1 1− β1 . (46)
By Eq. (45) and Eq. (46), we obtain 1−β t 1 1−β1 − 1−βt−11 c(1−β1) 1−(cβ1)t 1−(cβ1)t−1 is lower bounded by some positive constant across t, and η is well defined.

heading: C.2 SUM OF GRADIENTS ALONG THE TRAJECTORY IS BOUNDED
text: We start with the following lemma, which indicates L(w(t))+‖ 4 √ ε1d + ν̂(t) (w(t)−w(t−1))‖2 is a proper Lyapunov function for Adam.
Proof of Lemma 5. We start with the case t = 1. To begin with, we have L is H`−1(NL(w(1))) smooth around w(1). By definition Hx is non-increasing with respect to x, and since `−1 is also non-increasing, we have
H`−1(NL(w(1))) ≤ H`−1( 11−cβ1NL(w(1))),
which further indicates when α is small enough,
L(w(1 + α)) (?) ≤L(w(1)) + α〈∇L(w(1)),w(2)−w(1)〉+ L 2 α2‖w(2)−w(1)‖
=L(w(1))− α 〈 ∇L(w(1)), η 1√
ε1d + ν̂(1) ∇L(w(1))
〉 + o(α2)
≤L(w(1))− 1 2η α2 ∥∥∥ 4√ε1d + ν̂(1) (w(2)−w(t))∥∥∥2 ,
where in Eq. (?) we denote L 4 = H`−1( 11−cβ1NL(w(1))) , and the last inequality is due to 12ηα 2∥∥∥ 4√ε1d + ν̂(1) (w(2)−w(t))∥∥∥2 = o(α2), and 〈∇L(w(1)), η 1√
ε1d+ν̂(1) ∇L(w(1))
〉 is
positive.
Now if there exists an α ∈ (0, 1), such that Eq. (10) fails, we denote α∗ = inf{α : Eq.(10) fails for 1 + α}. We have α∗ > 0, and the equality in Eq. (10) holds for 1 + α∗. Therefore, we have for any α ∈ (0, α∗),
L(w(1 + α)) ≤ L(w(1 + α)) + 1 2η α2 ∥∥∥ 4√ε1d + ν̂(1) (w(2)−w(t))∥∥∥2 ≤ L(w(1)),
which by Lemma 10 leads to L is H`−1(NL(w(1))) smooth (thus L smooth) over the set {w(1 + α) : α ∈ [0, α∗]}, and L(w(1 + α∗))
≤L(w(1)) + α∗〈∇L(w(1)),w(2)−w(1)〉+ L 2 (α∗)2‖w(2)−w(1)‖2
=L(w(1))− α∗ 〈 1
η
√ ε1d + ν̂(1) (w(2)−w(1)) ,w(2)−w(1) 〉 + L
2 (α∗)2‖w(2)−w(1)‖2
=L(w(1))− α∗ 1 η ∥∥∥ 4√ε1d + ν̂(1) (w(2)−w(1))∥∥∥2 + L 2 (α∗)2 ∥∥∥∥∥ 14√ε1d + ν̂(1) 4 √ ε1d + ν̂(1) (w(2)−w(1)) ∥∥∥∥∥ 2
≤L(w(1))− α∗ 1 η ∥∥∥ 4√ε1d + ν̂(1) (w(2)−w(1))∥∥∥2 + L 2 √ ε (α∗)2 ∥∥∥ 4√ε1d + ν̂(1) (w(2)−w(1))∥∥∥2
<L(w(1))− (α∗)2 1 η ∥∥∥ 4√ε1d + ν̂(1) (w(2)−w(1))∥∥∥2 + L 2 √ ε (α∗)2 ∥∥∥ 4√ε1d + ν̂(1) (w(2)−w(1))∥∥∥2
≤L(w(1))− (α∗)2 1 2η ∥∥∥ 4√ε1d + ν̂(1) (w(2)−w(1))∥∥∥2 , (47) where the second-to-last inequality is due to ‖w(2)−w(1)‖ > 0 (by Lemma 13) and α∗ > (α∗)2, while the last inequality is due to
η ≤
√ ε inft≥2 ( 1−βt1 1−β1 − 1−βt−11 c(1−β1) 1−(cβ1)t 1−(cβ1)t−1 ) L ≤ √ ε ( 1−β21 1−β1 − 1−β1 c(1−β1) 1−(cβ1)2 1−(cβ1) ) L
=
√ ε ( 1 + β1 − 1+(cβ1)c )
L =
√ ε ( 1− 1c ) L < √ ε L .
Eq. (47) contradicts the fact that the equality in Eq. (10) holds for 1 + α∗, which completes the proof of t = 1.
If t ≥ 2, following the similar routine as t = 1, we also prove Eq. (10) by reduction to absurdity. If there exist t and α such that Eq. (10) fails. Denote t∗ as the smallest time such that there exists an α ∈ [0, 1) such that Eq. (10) fails for t∗ and α. By Lemma 13,∥∥∥ 4√ε1d + ν̂(t∗ − 1) (w(t∗)−w(t∗ − 1))∥∥∥2 is positive, and strict inequality in Eq. (10) holds for t and α = 0, which by continuity leads to
1 > α∗ 4 = inf{α ∈ [0, 1] : Eq.(10) fails for 1 + α} > 0.
Then, for any α ∈ [0, α∗], we have
L(w(t∗ + α))
≤L(w(t∗ + α)) + 1 2 α2 1− βt∗1 η(1− β1) ∥∥∥ 4√ε1d + ν̂(t∗) (w(t∗ + 1)−w(t∗))∥∥∥2 ≤L(w(t∗)) + 1− β t∗−1 1
2cη(1− β1) 1− (cβ1)t
∗ 1− (cβ1)t∗−1 ∥∥∥ 4√ε1d + ν̂(t∗ − 1) (w(t∗)−w(t∗ − 1))∥∥∥2 .
On the other hand, for any time 2 ≤ s ≤ t∗ − 1, we have
L(w(s+ 1)) + 1 2 1− βs1 η(1− β1) ∥∥∥ 4√ε1d + ν̂(s) (w(s+ 1)−w(s))∥∥∥2 ≤L(w(s)) + β1(1− β s−1 1 )
2cη(1− β1) 1− (cβ1)s 1− (cβ1)s−1 ∥∥∥ 4√ε1d + ν̂(s− 1) (w(s)−w(s− 1))∥∥∥2 . (48)
By Eq. (46), we have
1− βs1 η(1− β1) > 1− βs1 cη(1− β1) = 1− βs1 cη(1− β1) 1− (cβ1)s+1 1− (cβ1)s 1− (cβ1)s 1− (cβ1)s+1 ,
which by (1−β s−1 1 )
(1−βs1) further leads to
L(w(s)) + 1− β s−1 1 2cη(1− β1) 1− (cβ1)s 1− (cβ1)s−1 ∥∥∥ 4√ε1d + ν̂(s− 1) (w(s)−w(s− 1))∥∥∥2
≥L(w(s+ 1)) + 1 2 1− βs1 η(1− β1) ∥∥∥ 4√ε1d + ν̂(s) (w(s+ 1)−w(s))∥∥∥2 >L(w(s+ 1)) + 1− β s 1
2cη(1− β1) 1− (cβ1)s+1 1− (cβ1)s 1− (cβ1)s 1− (cβ1)s+1 ∥∥∥ 4√ε1d + ν̂(s) (w(s+ 1)−w(s))∥∥∥2
> 1− (cβ1)s
1− (cβ1)s+1
( L(w(s+ 1)) + 1− β s 1
2cη(1− β1) 1− (cβ1)s+1 1− (cβ1)s ∥∥∥ 4√ε1d + ν̂(s) (w(s+ 1)−w(s))∥∥∥2) .
(49)
On the other hand, for s = 1, we have
L(w(1)) ≥L(w(2)) + 1 2 1− β1 η(1− β1) ∥∥∥ 4√ε1d + ν̂(1) (w(2)−w(1))∥∥∥2 ≥ 1− (cβ1)
1− (cβ1)2
( L(w(2)) + 1− β1
2cη(1− β1) 1− (cβ1)2 1− (cβ1) ∥∥∥ 4√ε1d + ν̂(1) (w(2)−w(1))∥∥∥2) . (50)
Combining Eqs. (48), (49), and (50), we have
L(w(t∗ + α))
≤L(w(t∗)) + 1− β t∗−1 1
2cη(1− β1) 1− (cβ1)t
∗ 1− (cβ1)t∗−1 ∥∥∥ 4√ε1d + ν̂(t∗ − 1) (w(t∗)−w(t∗ − 1))∥∥∥2
< 1− (cβ1)t
∗
1− (cβ2)t∗−1
( L(w(t∗ − 1)) + 1− β t∗−2 1
2cη(1− β1) 1− (cβ1)t
∗−1 1− (cβ1)t∗−2 ∥∥∥ 4√ε1d + ν̂(t∗ − 2) (w(t∗ − 1)−w(t∗ − 2))∥∥∥2)
< · · ·
< 1− (cβ1)t
∗
1− (cβ1)2
( L(w(2)) + 1− β1
2cη(1− β1) 1− (cβ1)2 1− (cβ1) ∥∥∥ 4√ε1d + ν̂(1) (w(2)−w(1))∥∥∥2) ≤1− (cβ1) t∗
1− cβ1 L(w(1)) < 1 1− cβ1 L(w(1)).
Therefore, by Lemma 10, L isH`−1( 11−cβ1NL(w(1))) smooth (thus L smooth) over the set {w(t ∗+α) : α ∈ [0, α∗]}, which further leads to
L(w(t∗ + α∗))
≤L(w(t∗)) + α∗〈∇L(w(t∗)),w(t∗ + 1)−w(t∗)〉+ L 2 (α∗)2‖w(t∗ + 1)−w(t∗)‖2
(•) = − α
∗
η(1− β1)
〈 w(t∗ + 1)−w(t∗), (1− βt ∗ 1 ) √ ε1d + ν̂(t∗) (w(t∗ + 1)−w(t∗))
− β1(1− βt ∗−1 1 ) √ ε1d + ν̂(t∗) (w(t∗)−w(t∗ − 1)) 〉 +L(w(t∗)) + L
2 (α∗)2‖w(t∗ + 1)−w(t∗)‖2
=L(w(t∗)) + L 2 (α∗)2‖w(t∗ + 1)−w(t∗)‖2 − α ∗(1− βt∗1 ) η(1− β1) ∥∥∥ 4√ε1d + ν̂(t∗) (w(t∗ + 1)−w(t∗))∥∥∥2 +β1 α∗(1− βt ∗−1 1 )
η(1− β1)
〈 w(t∗ + 1)−w(t∗), √ ε1d + ν̂(t∗) (w(t∗)−w(t∗ − 1)) 〉 =L(w(t∗)) + L
2 (α∗)2‖w(t∗ + 1)−w(t∗)‖2 − α ∗(1− βt∗1 ) η(1− β1) ∥∥∥ 4√ε1d + ν̂(t∗) (w(t∗ + 1)−w(t∗))∥∥∥2 +β1 α∗(1− βt ∗−1 1 )
η(1− β1) 〈 8 √ ε1d + ν̂(t∗ − 1) 8 √ ε1d + ν̂(t∗) 4 √ ε1d + ν̂(t∗) (w(t∗ + 1)−w(t∗)),
8 √ ε1d + ν̂(t∗ − 1) 8 √ ε1d + ν̂(t∗) 4 √ ε1d + ν̂(t∗ − 1) (w(t∗)−w(t∗ − 1)) 〉
≤L(w(t∗)) + L 2 (α∗)2‖w(t∗ + 1)−w(t∗)‖2 − α ∗(1− βt∗1 ) η(1− β1) ∥∥∥ 4√ε1d + ν̂(t∗) (w(t∗ + 1)−w(t∗))∥∥∥2 +β1 (α∗)2(1− βt ∗−1 1 )
2η(1− β1)
∥∥∥∥∥ 8 √ ε1d + ν̂(t∗ − 1) 8 √ ε1d + ν̂(t∗) 4 √ ε1d + ν̂(t∗) (w(t∗ + 1)−w(t∗)) ∥∥∥∥∥ 2
+β1 (1− βt
∗−1 1 )
2η(1− β1) ∥∥∥∥∥ 8 √ ε1d + ν̂(t∗ − 1) 8 √ ε1d + ν̂(t∗) 4 √ ε1d + ν̂(t∗ − 1) (w(t∗)−w(t∗ − 1)) ∥∥∥∥∥ 2
( ) ≤L(w(t∗)) + L 2 (α∗)2‖w(t∗ + 1)−w(t∗)‖2 − α ∗(1− βt∗1 ) η(1− β1) ∥∥∥ 4√ε1d + ν̂(t∗) (w(t∗ + 1)−w(t∗))∥∥∥2 +β1 (α∗)2(1− βt ∗−1 1 )
2η(1− β1) 1− (cβ1)t
∗
cβ1(1− (cβ1)t∗−1) ∥∥∥ 4√ε1d + ν̂(t∗) (w(t∗ + 1)−w(t∗))∥∥∥2 +β1 (1− βt ∗−1 1 )
2η(1− β1) 1− (cβ1)t
∗
cβ1(1− (cβ1)t∗−1) ∥∥∥ 4√ε1d + ν̂(t∗ − 1) (w(t∗)−w(t∗ − 1))∥∥∥2 ≤L(w(t∗)) + L
2 √ ε
(α∗)2‖ 4 √ ε1d + ν̂(t∗) (w(t∗ + 1)−w(t∗))‖2
−α ∗(1− βt∗1 ) η(1− β1) ∥∥∥ 4√ε1d + ν̂(t∗) (w(t∗ + 1)−w(t∗))∥∥∥2 +β1
(α∗)2(1− βt∗1 ) 2η(1− β1)
1− (cβ1)t ∗
cβ1(1− (cβ1)t∗−1) ∥∥∥ 4√ε1d + ν̂(t∗) (w(t∗ + 1)−w(t∗))∥∥∥2 +β1
(1− βt∗1 ) 2η(1− β1)
1− (cβ1)t ∗
cβ1(1− (cβ1)t∗−1) ∥∥∥ 4√ε1d + ν̂(t∗ − 1) (w(t∗)−w(t∗ − 1))∥∥∥2 ( ) < L(w(t∗))− (α
∗)2(1− βt∗1 ) 2η(1− β1) ∥∥∥ 4√ε1d + ν̂(t∗) (w(t∗ + 1)−w(t∗))∥∥∥2 + (1− βt ∗−1 1 )
2η(1− β1) 1− (cβ1)t
∗
c(1− (cβ1)t∗−1) ∥∥∥ 4√ε1d + ν̂(t∗ − 1) (w(t∗)−w(t∗ − 1))∥∥∥2 , where Eq. (•) is due to an alternative form of the Adam’s update rule:
(1− βt ∗ 1 ) √ ε1d + ν̂(t∗) (w(t∗ + 1)−w(t∗))− β1(1− βt ∗−1 1 ) √ ε1d + ν̂(t∗ − 1) (w(t∗)−w(t∗ − 1))
=− η(1− β1)∇L(w(t∗)), (51) Inequality ( ) is due to
4 √ ε1d + ν̂(t∗ − 1) 4 √ ε1d + ν̂(t∗) = 4 √ ε1d + ν̂(t∗ − 1) ε1d + ν̂(t∗) = 4 √√√√ ε1d + ν̂(t∗ − 1) ε1d +
β2ν(t∗−1)+(1−β2)∇L(w(t∗))2 1−βt∗2
≤ 4 √√√√ε1d + ν̂(t∗ − 1) ε1d +
β2ν(t∗−1) 1−βt∗2
= 4 √√√√ ε1d + ν̂(t∗ − 1) ε1d + β2(1−βt ∗−1 2 )ν̂(t ∗−1)
1−βt∗2
≤ 4 √√√√ ε1d + ν̂(t∗ − 1) β2(1−βt ∗−1 2 )ν̂(t
∗−1) 1−βt∗2 ε1d + β2(1−βt
∗−1 2 )ν̂(t
∗−1) 1−βt∗2
= 4
√ 1− βt∗2
β2(1− βt ∗−1 2 ) 1d (all the computings are component-wisely),
and f(cβ1) ≥ 4 √ f((cβ1)4), and Inequality ( ) is due to
L
2 √ ε ≤
inft≥2 ( 1−βt1 1−β1 − 1−βt−11 c(1−β1) 1−(cβ1)t 1−(cβ1)t−1 ) 2η ≤
( 1−βt ∗ 1
1−β1 − 1−βt
∗−1 1
c(1−β1) 1−(cβ1)t
∗
1−(cβ1)t∗−1 ) 2η ,
α∗ > (α∗)2, and ∥∥∥ 4√ε1d + ν̂(t∗) (w(t∗ + 1)−w(t∗))∥∥∥2 > 0.
This contradicts to that the equality in Eq. (10) holds for t∗ + α∗.
The proof is completed.
As limt→∞ βt1 = 0 and limt→∞(cβ1) t = 0, we have the following corollary based on Lemma 1. Corollary 6. Let all assumptions in Theorem 4 hold. Then, for large enough t, we have
L(w(t+ 1)) + 1 2 4 √ cη(1− β1) ∥∥∥ 4√ε1d + ν̂(t) (w(t+ 1)−w(t))∥∥∥2 ≤L(w(t)) + 1
2 2 √ cη(1− β1)
∥∥∥ 4√ε1d + ν̂(t− 1) (w(t)−w(t− 1))∥∥∥2 . (52)
Consequently, we have ∞∑ t=1 ‖∇L(w(t))‖2 <∞. (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 {ai}∞i=1 be a series of non-negative reals, and ε be a positive real. Then, ∑∞ i=1 ai <∞ is equivalent to ∑∞ i=1
ai√ ε+ ∑t s=1 as <∞.
Proof of Corollary 6. We have
lim t→∞ 1− βt−11 2cη(1− β1) 1− (cβ1)t 1− (cβ1)t−1 =
1
2cη(1− β1) <
1
2 2 √ cη(1− β1) ,
lim t→∞ 1− βt1 2η(1− β1) = 1 2η(1− β1) >
1
2 4 √ cη(1− β1) ,
which completes the proof of Eq. (52). Rearranging Eq. (52) leads to
4 √ c− 1
2 2 √ cη(1− β1) ∥∥∥ 4√ε1d + ν̂(t) (w(t+ 1)−w(t))∥∥∥2 ≤ 1 2 4 √ cη(1− β1) ∥∥∥ 4√ε1d + ν̂(t− 1) (w(t)−w(t− 1))∥∥∥2 +L(w(t))− ( L(w(t+ 1)) + 1
2 4 √ cη(1− β1) ∥∥∥ 4√ε1d + ν̂(t) (w(t+ 1)−w(t))∥∥∥2) , which by iteration further leads to that for a large enough time T1
T2∑ t=T1
4 √ c− 1
2 2 √ cη(1− β1) ∥∥∥ 4√ε1d + ν̂(t) (w(t+ 1)−w(t))∥∥∥2 ≤L(w(T1)) + 1
2 4 √ cη(1− β1) ∥∥∥ 4√ε1d + ν̂(T1 − 1) (w(T1)−w(T1 − 1))∥∥∥2 −L(w(T2 + 1)) + 1
2 4 √ cη(1− β1) ∥∥∥ 4√ε1d + ν̂(T2) (w(T2 + 1)−w(T2 + 1))∥∥∥2 <L(w(T1)) + 1
2 4 √ cη(1− β1) ∥∥∥ 4√ε1d + ν̂(T1 − 1) (w(T1)−w(T1 − 1))∥∥∥2 . Consequently, we obtain
∞∑ t=1
4 √ c− 1
2 2 √ cη(1− β1) ∥∥∥ 4√ε1d + ν̂(t) (w(t+ 1)−w(t))∥∥∥2 <∞. (54) On the other hand, for any t, we have∥∥∥ 4√ε1d + ν̂(t) (w(t+ 1)−w(t))∥∥∥ ∥∥∥ 4√ε1d + ν̂(t) ŵ∥∥∥ ≥ 〈 4 √ ε1d + ν̂(t) (w(t+ 1)−w(t)), 4 √ ε1d + ν̂(t) ŵ 〉 = 〈 2 √ ε1d + ν̂(t) (w(t+ 1)−w(t)), ŵ
〉 = 〈−ηm̂(t), ŵ〉 = −η(1− β1)
1− βt1
〈 t∑
s=1
βt−s1 ∇L(w(s)), ŵ
〉
=− η(1− β1) 1− βt1 1 N
〈 t∑
s=1
βt−s1 ∑
x̃i∈T (S)
`′(〈x̃i,w(s)〉)x̃i, ŵ 〉 ≥ −η(1− β1)
1− βt1 1 N t∑ s=1 βt−s1 ∑
x̃i∈T (S)
`′(〈x̃i,w(s)〉)
≥− η(1− β1) 1− βt1 1 N ∑ x̃i∈T (S) `′(〈x̃i,w(t)〉) ≥ η(1− β1) 1− βt1 ‖∇L(w(t))‖,
which by Eq. (54) indicates ∞∑ t=1 ( η(1− β1) 1− βt1 )2 ‖∇L(w(t))‖2∥∥∥ 4√ε1d + ν̂(t) ŵ∥∥∥2 <∞. As limt→∞ ( η(1−β1) 1−βt1 )2 = η2(1− β1)2, we then obtain
∞∑ t=1
‖∇L(w(t))‖2
2 √ ε+ ∑t s=1 ‖∇L(w(t))‖2 ≤ ∞∑ t=1
‖∇L(w(t))‖2
2 √ ε+ ∑t s=1(1− β)βt−s‖∇L(w(t))‖2
≤ √ 1
1− β ∞∑ t=1
‖∇L(w(t))‖2
2 √ ε+ ∑t s=1(1−β)βt−s‖∇L(w(t))‖2
1−βt
≤ d √ 1
1− β ∞∑ t=1
‖∇L(w(t))‖2∥∥∥∥ 4√ε1d + ∑ts=1(1−β)βt−s∇L(w(t))21−βt ∥∥∥∥2 =d √ 1
1− β ∞∑ t=1 ‖∇L(w(t))‖2∥∥∥ 4√ε1d + ν̂(t)∥∥∥2 ≤ d‖ŵ‖2∞ √ 1 1− β ∞∑ t=1
‖∇L(w(t))‖2∥∥∥ 4√ε1d + ν̂(t) ŵ∥∥∥2 <∞, 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
‖η(1− β1)∇L(w(t))‖2 = ∥∥∥(1− βt1)√ε1d + ν̂(t) (w(t+ 1)−w(t))− β1(1− βt−11 )√ε1d + ν̂(t− 1) (w(t)−w(t− 1))∥∥∥2 ≤ ∥∥∥(1− βt1)√ε1d + ν̂(t) (w(t+ 1)−w(t))∥∥∥+ ∥∥∥β1(1− βt−11 )√ε1d + ν̂(t− 1) (w(t)−w(t− 1))∥∥∥2 ≤ (∥∥∥√ε1d + ν̂(t) (w(t+ 1)−w(t))∥∥∥+ ∥∥∥√ε1d + ν̂(t− 1) (w(t)−w(t− 1))∥∥∥)2 ≤2 (∥∥∥√ε1d + ν̂(t) (w(t+ 1)−w(t))∥∥∥2 + ∥∥∥√ε1d + ν̂(t− 1) (w(t)−w(t− 1))∥∥∥2) (55)
On the other hand, by Corollary 6, ∞∑ s=1 ‖∇L(w(s))‖2 <∞,
which following the same routine as Corollary 5 leads to
〈w(t), x̃〉 → ∞,∀x̃ ∈ S̃. Therefore, by Lemma 11, there exists a large enough time T1, such that ∀t ≥ T1,
1
K `(〈w(t), x̃〉) ≤ −`′(〈w(t), x̃〉) ≤ K`(〈w(t), x̃〉),∀x̃ ∈ T (S),
which by the separable assumption further leads to
γ K L(w(t)) ≤ − γ N ∑ x̃∈T (S) `′(〈w(t), x̃〉) ≤ 1 N
〈 −
∑ x̃∈T (S) `′(〈w(t), x̃〉)x̃, γŵ
〉
≤ 1 N ∥∥∥∥∥∥ ∑
x̃∈T (S)
`′(〈w(t), x̃〉)x̃ ∥∥∥∥∥∥ ‖γŵ‖ = ‖∇L(w(t))‖ ≤ − 1
N ∑ x̃∈T (S) `′(〈w(t), x̃〉) ≤ KL(w(t)). (56)
Combining Eq. (26) and the above inequality, we have
( η(1− β1)γ
K
)2 L(w(t))2 ≤ 2 (∥∥∥√ε1d + ν̂(t) (w(t+ 1)−w(t))∥∥∥2 ‘ +
∥∥∥√ε1d + ν̂(t− 1) (w(t)−w(t− 1))∥∥∥2) . (57) On the other hand, by Eq. (54), we have
∞∑ t=1 ∥∥∥ 4√ε1d + ν̂(t) (w(t+ 1)−w(t))∥∥∥2 <∞. Therefore, there exists large enough time T2, such that ∀t > T2, ∥∥∥ 4√ε1d + ν̂(t) (w(t+ 1)−w(t))∥∥∥2 < 1, and thus, ∥∥∥ 4√ε1d + ν̂(t) (w(t+ 1)−w(t))∥∥∥4 < ∥∥∥ 4√ε1d + ν̂(t) (w(t+ 1)−w(t))∥∥∥2 . (58) Combining Eq. (57) and Eq. (58), there exists a positive real constant C, such that
L(w(t))2 ≤C (∥∥∥√ε1d + ν̂(t) (w(t+ 1)−w(t))∥∥∥2
+ ∥∥∥√ε1d + ν̂(t− 1) (w(t)−w(t− 1))∥∥∥2) ,∥∥∥ 4√ε1d + ν̂(t) (w(t+ 1)−w(t))∥∥∥4 ≤C (∥∥∥√ε1d + ν̂(t) (w(t+ 1)−w(t))∥∥∥2
+ ∥∥∥√ε1d + ν̂(t− 1) (w(t)−w(t− 1))∥∥∥2) .
Rearranging Eq. (52) leads to
4 √ c− 1
4 2 √ cη(1− β1) (∥∥∥ 4√ε1d + ν̂(t− 1) (w(t)−w(t− 1))∥∥∥2 + ∥∥∥ 4√ε1d + ν̂(t− 1) (w(t)−w(t− 1))∥∥∥2)
≤L(w(t)) + 4 √ c+ 1
4 2 √ cη(1− β1) ∥∥∥ 4√ε1d + ν̂(t− 1) (w(t)−w(t− 1))∥∥∥2 − ( L(w(t+ 1)) + 4 √ c+ 1
4 2 √ cη(1− β1)
∥∥∥ 4√ε1d + ν̂(t) (w(t+ 1)−w(t))∥∥∥2) ,
which further indicates( L(w(t)) +
4 √ c+ 1
4 2 √ cη(1− β1) ∥∥∥ 4√ε1d + ν̂(t− 1) (w(t)−w(t− 1))∥∥∥2)2 ≤2 ( L(w(t))2 + 4 √ c+ 1
4 2 √ cη(1− β1) ∥∥∥ 4√ε1d + ν̂(t− 1) (w(t)−w(t− 1))∥∥∥4) ≤2C ( 1 + 4 √ c+ 1
4 2 √ cη(1− β1) )(∥∥∥√ε1d + ν̂(t) (w(t+ 1)−w(t))∥∥∥2 + ∥∥∥√ε1d + ν̂(t− 1) (w(t)−w(t− 1))∥∥∥2)
≤2C ( 1 + 4 √ c+ 1
4 2 √ cη(1− β1) ) 4 2 √ cη(1− β1) 4 √ c− 1 ( L(w(t)) +
4 √ c+ 1
4 2 √ cη(1− β1)
· ∥∥∥ 4√ε1d + ν̂(t− 1) (w(t)−w(t− 1))∥∥∥2 − (L(w(t+ 1)) + 4 √ c+ 1
4 2 √ cη(1− β1) ∥∥∥ 4√ε1d + ν̂(t) (w(t+ 1)−w(t))∥∥∥2)) . Denote ξ(t) as
ξ(t) 4 = L(w(t)) +
4 √ c+ 1
4 2 √ cη(1− β1) ∥∥∥ 4√ε1d + ν̂(t− 1) (w(t)−w(t− 1))∥∥∥2 . We then have
ξ(t)2 ≤ 2C ( 1 + 4 √ c+ 1
4 2 √ cη(1− β1) ) 4 2 √ cη(1− β1) 4 √ c− 1 (ξ(t)− ξ(t+ 1)),
which leads to
ξ(t) = O ( 1
t
) , i.e., L(w(t)) = O ( 1
t
) ,
and ∥∥∥ 4√ε1d + ν̂(t− 1) (w(t)−w(t− 1))∥∥∥2 = O(1
t
) .
Due to Eq. (56), we further have ‖∇L(w(t))‖ = O(t−1), which indicates
‖w(t)‖ ≤‖w(1)‖+ t∑
s=1
‖w(s+ 1)−w(s)‖ = ‖w(1)‖+ η t∑
s=1
∥∥∥∥∥ m̂(s)√ν̂(s) + ε1d ∥∥∥∥∥
≤‖w(1)‖+ η√ ε t∑ s=1 ‖m̂(s)‖ = ‖w(1)‖+ η√ ε t∑ s=1
1
(1− βs) ∥∥∥∥∥ s∑ i=1 βs−i∇L(w(i)) ∥∥∥∥∥ ≤‖w(1)‖+ η√
ε(1− β) t∑ s=1 s∑ i=1 βs−i ‖∇L(w(i))‖
≤‖w(1)‖+ η√ ε(1− β)2 t∑ s=1 ‖∇L(w(s))‖ = O(log(t)).
Therefore, for any x̃ ∈ T (S), we have 〈w(t), x̃〉 = O(log(t)), which by ` is exponential-tailed leads to `(〈w(t), x̃〉) = Ω(t−1), and thus L(w(t)) = Θ(t−1). Also, since L(w(t)) = O(t−1), we have 〈w(t), x̃〉 = Ω(log(t)), which further leads to ‖w(t)‖ = Ω(log(t)), and thus ‖w(t)‖ = Θ(log(t)).
Finally, we have
γ t∑ s=1 βt−s‖∇L(w(s))‖ = γ N t∑ s=1 βt−s ∥∥∥∥∥∥ ∑ x̃∈T (S) `′(〈w(s), x̃〉)x̃ ∥∥∥∥∥∥ ≤− γ
N t∑ s=1 βt−s ∑ x̃∈T (S) `′(〈w(s), x̃〉) ≤ − 1 N t∑ s=1 βt−s 〈 ∑ x̃∈T (S) `′(〈w(s), x̃〉)x̃, γŵ 〉
≤ ∥∥∥∥∥ t∑
s=1
βt−s∇L(w(s)) ∥∥∥∥∥ ‖γŵ‖ = ‖m(t)‖ ≤ t∑
s=1
βt−s‖∇L(w(s))‖,
which leads to ‖m(t)‖ = Θ(t−1). Similarly, we have ν(t) = O(t−2), component-wisely. As limt→∞ β t 1 = 0 and limt→∞ β t 2 = 0, we have
‖w(t)−w(t− 1)‖ = ∥∥∥∥∥ m̂(t)√ε1d + ν̂(t) ∥∥∥∥∥ = Θ(t−1).
The proof is completed.

heading: C.3 BOUNDING THE ORTHOGONAL PART
text: By Lemma 8, there exists a solution w̃ as the solution of Eq. (12) with C2 = η(1−β)√ε . Define r(t) as
r(t) 4 = w(t)− log(t)ŵ − w̃, (59)
and we only need to prove ‖r(t)‖ is 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. Lemma 21. Let all conditions in Theorem 4 hold. Then, ‖r(t)‖ is bounded if and only if g(t) is upper bounded.
Proof. Following the same routine as Lemma 2 and Lemma 17, we only need to prove
lim t→∞ ∥∥∥(1− βt−11 )√ε1d + ν̂(t− 1) (w(t)−w(t− 1))∥∥∥ = 0, (60) and
∞∑ τ=2 ∣∣∣〈r(τ)− r(τ − 1), (1− βτ−11 )√ε1d + ν̂(τ − 1) (w(τ)−w(τ − 1))〉∣∣∣ <∞. (61) As for Eq. (60), by Lemma 6, we have∥∥∥(1− βt−11 )√ε1d + ν̂(t− 1) (w(t)−w(t− 1))∥∥∥
=O(t−1) = o(1).
As for Eq. (60), we have∣∣∣〈r(τ)− r(τ − 1), (1− βτ−11 )√ε1d + ν̂(τ − 1) (w(τ)−w(τ − 1))〉∣∣∣ = ∣∣∣∣〈w(τ)−w(τ − 1)− log ττ − 1ŵ, (1− βτ−11 )√ε1d + ν̂(τ − 1) (w(τ)−w(τ − 1)) 〉∣∣∣∣
≤ ∣∣∣∣〈log ττ − 1ŵ, (1− βτ−11 )√ε1d + ν̂(τ − 1) (w(τ)−w(τ − 1)) 〉∣∣∣∣ + (1− βτ−11 )
∥∥∥ 4√ε1d + ν̂(τ − 1) (w(τ)−w(τ − 1))∥∥∥2 (?) =O(τ−2),
where Eq. (?) is due to Lemma 6 and log( ττ−1 ) = Θ(τ −1).
The proof is completed.
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) is upper bounded. Proof. g(t) is upper bounded is equivalent to ∑∞ t=1 g(t+ 1)− g(t) <∞. We then prove this lemma by calculating g(t+ 1)− g(t) directly. g(t+ 1)− g(t)
=
√ ε
2 ‖r(t+ 1)‖2 + β1 1− β1
〈 r(t+ 1), (1− βt1) √ ε1d + ν̂(t) (w(t+ 1)−w(t)) 〉 − (√ ε
2 ‖r(t)‖2 + β1 1− β1
〈 r(t), (1− βt−11 ) √ ε1d + ν̂(t− 1) (w(t)−w(t− 1)) 〉) − β1
1− β1 〈r(t+ 1)− r(t), (1− βt1)
√ ε1d + ν̂(t) (w(t+ 1)−w(t))〉
=
√ ε
2 ‖r(t+ 1)− r(t)‖2 + β1 1− β1
〈 r(t), (1− βt1) √ ε1d + ν̂(t) (w(t+ 1)−w(t))
−(1− βt−11 ) √ ε1d + ν̂(t− 1) (w(t)−w(t− 1)) 〉 + √ ε〈r(t+ 1)− r(t), r(t)〉
(?) = 〈 r(t),−(1− βt1) √ ε1d + ν̂(t) (w(t+ 1)−w(t))− η
1− β ∇L(w(t)) 〉 + √ ε
2 ‖r(t+ 1)− r(t)‖2 +
√ ε〈r(t+ 1)− r(t), r(t)〉,
where Eq. (?) is due to a simple rearranging of the update rule of Adam, i.e., β1 1− β1 ( (1− βt1) √ ε1d + ν̂(t) (w(t+ 1)−w(t))− (1− βt−11 ) √ ε1d + ν̂(t− 1) (w(t)−w(t− 1)) ) = − η
1− β1 ∇L(w(t))− (1− βt1)
√ ε1d + ν̂(t) (w(t+ 1)−w(t)) .
On the one hand, as ‖r(t+ 1)− r(t)‖ = ‖w(t+ 1)−w(t)− log t+1t ŵ‖ = O(t −1),
∞∑ t=1 √ ε 2 ‖r(t+ 1)− r(t)‖2 <∞.
On the other hand,〈 r(t),−(1− βt1) √ ε1d + ν̂(t) (w(t+ 1)−w(t))− η
1− β ∇L(w(t)) 〉 + √ ε〈r(t+ 1)− r(t), r(t)〉
= 〈 r(t),−(1− βt1) √ ε1d + ν̂(t) (w(t+ 1)−w(t))− η
1− β ∇L(w(t)) 〉 + √ ε 〈 w(t+ 1)−w(t)− log ( t+ 1
t
) ŵ, r(t) 〉 = 〈 r(t),−(1− βt1) √ ε1d + ν̂(t) (w(t+ 1)−w(t)) + √ ε(w(t+ 1)−w(t))
〉 + 〈 r(t),− √ ε log ( t+ 1
t
) ŵ − η
1− β ∇L(w(t)) 〉 (•) =O(βt1 + t−2) + 〈 r(t),− √ ε log ( t+ 1
t
) ŵ − η
1− β ∇L(w(t))
〉 ,
where Eq. (•) is due to ν̂(t) = O(t−2). Furthermore, following exactly the same routine as Lemma 16, we have
∞∑ t=1 〈 r(t),− √ ε log ( t+ 1 t ) ŵ − η 1− β ∇L(w(t)) 〉 <∞.
The proof is completed.

heading: D APPLICATIONS&EXTENSIONS

heading: D.1 APPLICATION TO THE MINI-BATCH SGDM
text: This section provides formal description of the implicit bias of mini-batch SGDM and its corresponding proof. To begin with, we would like to provide a formal definition of mini-batch SGDM. Mini-batch SGDM differs from SGDM by applying sampling without replacement to obtain B(t) in Eq. (1). Specifically, let K = Nb . For any T ≥ 0, we call time series {KT + 1, · · · ,KT +K} the (T + 1)-th epoch, and during the T + 1-th epoch, the dataset S is randomly uniformly divided into K parts {B(KT + 1), · · · ,B(KT +K)}, with ⋃KT+K t=KT+1 B(t) = S. The implicit bias of mini-batch SGDM is then stated as the following theorem:
Theorem 6. Let Assumptions 1, 2, and 3. (S) hold. Let learning rate η be small enough, and β ∈ [0, 1).Then, for almost every dataset S, mini-batch SGDM satisfies w(t)− log(t)ŵ is bounded as t→∞, and limt→∞ w(t)‖w(t)‖ = ŵ ‖ŵ‖ .
The without-replacement sampling method leads to the direction of every trajectory of mini-SGDM converge to the max-margin solution, compared to 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
L(u(t+ 1)) ≤ L(u(1))− Ω(η) t∑
s=1
‖∇L(w(s))‖2.
Proof. By the Taylor Expansion of L(u(t+ 1)) at u(t), we have
L(u(KT + T + 1))
≤L(u(KT + 1))− η̃ 〈 ∇L(u(KT + 1)),
K∑ t=1 ∇LB(t+KT )(w(t+KT ))
〉
+ Hη̃2
2 ∥∥∥∥∥ K∑ t=1 LB(t+KT )(w(t+KT )) ∥∥∥∥∥ 2 . (62)
On the other hand, for any t ∈ {2, · · · ,K}, we have
w(KT + t)−w(KT + 1) = η t∑
s=1 ( KT+s∑ `=1 βKT+s−`∇LB(`)(w(`)) )
=η t∑ s=1 ( KT+s∑ `=KT+1 βKT+s−`∇LB(`)(w(`)) ) + η t∑ s=1 ( KT∑ `=1 βKT+s−`∇LB(`)(w(`)) )
=η t∑ `=1 1− βt−`+1 1− β ∇LB(KT+`)(w(KT + `)) + η β(1− βt) 1− β KT∑ `=1 βKT−`∇LB(`)(w(`))
=η t∑ `=1 1− βt−`+1 1− β ∇LB(KT+`)(w(KT + `))− η t∑ `=1 1− βt−`+1 1− β ∇LB(KT+`)(w(KT + 1))
+η β(1− βt)
1− β KT∑ `=1 βKT−`∇LB(`)(w(`)) + η t∑ `=1 1− βt−`+1 1− β ∇LB(KT+`)(w(KT + 1)),
which by η is small enough further indicates
‖w(KT + t)−w(KT + 1)‖
≤η ∥∥∥∥∥ t∑ `=1 1− βt−`+1 1− β ∇LB(KT+`)(w(KT + `))− t∑ `=1 1− βt−`+1 1− β ∇LB(KT+`)(w(KT + 1)) ∥∥∥∥∥ +η
∥∥∥∥∥β(1− βt)1− β KT∑ `=1 βKT−`∇LB(`)(w(`)) ∥∥∥∥∥+ η ∥∥∥∥∥ t∑ `=1 1− βt−`+1 1− β ∇LB(KT+`)(w(KT + 1)) ∥∥∥∥∥ =O(η)
t∑ `=2 ‖w(KT + `)−w(KT + 1)‖+O(η) ( KT∑ `=1 βKT−` ∥∥∇LB(`)(w(`))∥∥ ) +O(η) ‖∇L(w(KT + 1))‖ .
Applying the same analysis to ‖w(KT + t− 1)−w(KT + 1)‖ recursively, we finally obtain
‖w(KT + t)−w(KT + 1)‖
≤O(η) ( KT∑ `=1 βKT−` ∥∥∇LB(`)(w(`))∥∥ ) +O(η) ‖∇L(w(KT + 1))‖ . (63)
Applying Eq. (63) to the ∥∥∇LB(`)(w(`))∥∥ in Eq. (63) (∀` ∈ [1,KT ]) iterative and choosing η to be small enough, we further have
‖w(KT + t)−w(KT + 1)‖
≤O(η) ( T−1∑ `=0 √ βK(T−`) ∥∥∇LB(K`+1)(w(K`+ 1))∥∥ ) +O(η) ‖∇L(w(KT + 1))‖
=O(η) ( T∑ `=0 √ βK(T−`) ∥∥∇LB(K`+1)(w(K`+ 1))∥∥ ) .
Therefore,
K∑ t=1 ∇LB(t+KT )(w(t+KT ))
= K∑ t=1 ∇LB(t+KT )(w(t)) +O
( η ( T∑ `=0 √ βK(T−`) ∥∥∇LB(K`+1)(w(K`+ 1))∥∥ ))
=K∇L(w(t)) +O ( η ( T∑ `=0 √ βK(T−`) ∥∥∇LB(K`+1)(w(K`+ 1))∥∥ )) . (64)
Similarly, one can obtain
∇L(u(KT + 1)) =∇L(w(KT + 1)) +O (‖w(KT + 1)−w(KT )‖)
=∇L(w(KT + 1)) +O ( η ( T∑ `=0 √ βK(T−`) ∥∥∇LB(K`+1)(w(K`+ 1))∥∥ )) . (65)
Applying Eq. (64) and Eq. (65) back to the Taylor Expansion (Eq. (62)), we have
L(u(KT + T + 1)) ≤L(u(KT + 1))− Ω(η) 〈∇L(w(KT + 1)),∇L(w(KT + 1))〉
+O η2( T∑ `=0 √ βK(T−`) ∥∥∇LB(K`+1)(w(K`+ 1))∥∥ )2
≤L(u(KT + 1))− Ω(η) 〈∇L(w(KT + 1)),∇L(w(KT + 1))〉
+O ( η2 ( T∑ `=0 √ βK(T−`) ∥∥∇LB(K`+1)(w(K`+ 1))∥∥2 )) .
Summing the above inequality over T and setting η small enough leads to the conclusion.
The proof is completed.

heading: D.2 EXTENSION TO THE MULTI-CLASS CLASSIFICATION PROBLEM
text: Here we use several notations and lemmas from (Soudry et al., 2018). We define w = vec(W ), ŵ = vec(Ŵ ), ei ∈ RC (i ∈ {1, · · · , C}) satisfying (ei)j = δij , and Ai = ei ⊗ IdX , where IdX is the identity matrix with dimension dX . We still consider the normalized data, i.e., ‖x‖ ≤ 1, ∀(x,y) ∈ S. Then, the individual loss of sample (x,y) can be then represented as
`(y,Wx) = log e〈w,Ayx〉∑C i=1 e 〈w,Aix〉 .
Furthermore, the gradient of training error at W has the form
∇L(w) = 1 N ∑ (x,y)∈S C∑ i=1 1∑C j=1 e 〈w,(Aj−Ai)x〉 (Ai −Ay)x.
and the Hessian matrix of L can be represented as
HL(w) = 1 N ∑ (x,y)∈S C∑ i=1
∑C j=1 e
〈w,(Aj−Ai)x〉(∑C j=1 e 〈w,(Aj−Ai)x〉 )2 (Ai −Ay)x((Aj −Ai)x)>,
one can then easily verify all absolute value of the eigenvalues ofHL(w) is no larger than 2, which indicates L is 2-globally smooth. On the other hand, the separable assumption leads to 〈ŵ, (Ay −Ai)x〉 > 0, ∀y 6= i, which further indicates
〈∇L(w), ŵ〉 > 0.
Let γ = 1‖ŵ‖ , following the similar routine as the binary case, we have for a random subset of S sampled uniformly without replacement with size b, we have
‖∇L(w)‖2 ≤ EB(t)‖∇LB(t)(w)‖2 ≤ 2N
γb2 ‖∇L(w)‖2. (66)
Similarly, we have for any positive real series {at}t2t=t1 ,
γ t2∑ t=t1 a(t)‖∇L(w(t))‖ ≤ ∥∥∥∥∥ t2∑ t=t1 a(t)∇L(w(t)) ∥∥∥∥∥ ≤ t2∑ t=t1 a(t)‖∇L(w(t))‖. (67)
The proofs of Stage I can then be obtained with Lyapunov 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(t),− η1−β∇L(w(t)) − log t+1 t ŵ〉 (for GDM, 〈r(t),− η 1−β∇LB(t)(w(t)) −
N bt ∑ i:x̃i∈T (B(t)∩Ss) vix̃i〉 for SGDM, 〈r(t),− √ ε log ( t+1 t ) ŵ − η1−β∇L(w(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: Lemma 24 (Part of the proof of Lemma 20, (Soudry et al., 2018)). If 〈w(t), (Ay −Ai)x〉 → ∞ as t→∞, ∀(x,y) ∈ S and ∀i 6= y, we have the sum of 〈r(t),− η1−β∇L(w(t))− log t+1 t ŵ〉 is upper bounded.
The proof of Theorem 5 is then completed.

heading: E EXPERIMENTS
text: This section collects several experiments supporting our theoretical results.

heading: E.1 EXPERIMENTS OF LINEAR MODEL

heading: E.1.1 COMPARING THE TRAINING BEHAVIOR OF GD, GDM, AND ADAM (W/S)
text: 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 as (Figure 1, (Soudry et al., 2018)) and run GD, GDM and Adam (w/s) over it with different learning rates η = 0.1, 0.01 and different random seeds (for random initialization and random samples despite the support sets {((1.5, 0.5), 1), ((0.5, 1.5), 1), ((−1.5,−0.5),−1), ((−1.5,−0.5),−1)}). Both the angle between the output parameter and max margin solution and the training accuracy are plotted in Figure 1. Specifically, we plot the results with learning rate (1). ηGD = ηGDM = ηAdam = 0.001, (2). ηGD = ηGDM = ηAdam = 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 1. The observations can be summarized as follows:
• When learning rate is small enough (η = 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.

heading: E.1.2 COMPARING THE TRAINING BEHAVIOR OF SGD AND SGDM
text: We also run the stochastic optimizers (SGD and SGDM) on the same synthetic dataset as Figure 1. The learning rate is 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 to the max margin solution.

heading: E.1.3 ADAM ON ILL-POSED DATASET IN (SOUDRY ET AL., 2018)
text: In Figure 3 of (Soudry et al., 2018), an ill-posed synthetic dataset is proposed to 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-posed synthetic dataset with different learning rates and different random seeds as Figure 3. Figure 3. (f) is similar to Figure 3 in (Soudry et al., 2018), where with learning rate η = 0.1 and random seed 1, 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 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 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, x2), y) in the dataset,
|x1| is always smaller than 2, while |x2| 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 angle keep decreasing.

heading: E.2 EVIDENCE IN THE DEEP NEURAL NETWORKS
text: 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 in (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 (1). SGDM achieves similar test accuracy compared to SGD while (2). SGDM converges faster than SGD.

Review summaries:
The authors study the convergence of stochastic gradient descent momentum (SGDM) in a problem with of binary classification with separable data.  Interestingly, the authors observed that SGDM and GD converge to the same solution (i.e. the max margin solution) with the same convergence rate O(1/t).  The paper proposed a variation of [Soudry et al. 2018] solution, that allows for the analysis of the more complex SGDM.