The Implicit Bias of Adam on Separable Data
Authors: Chenyang Zhang
Difan Zou
Yuan Cao
Venue: NeurIPS 2024 poster (2024)
Keywords: Adam
implicit bias
Primary area: optimization_for_deep_networks

Abstract: Adam has become one of the most favored optimizers in deep learning problems. Despite its success in practice, numerous mysteries persist regarding its theoretical understanding. In this paper, we study the implicit bias of Adam in linear logistic regression. Specifically, we show that when the training data are linearly separable, the iterates of Adam converge towards a linear classifier that achieves the maximum $\ell_\infty$-margin in direction. Notably, for a general class of diminishing learning rates, this convergence occurs within polynomial time. Our result shed light on the difference between Adam and (stochastic) gradient descent from a theoretical perspective.

The Implicit Bias of Adam on Separable Data
Chenyang Zhang
Difan Zou
Department of Statistics and Actuarial Science
Department of Computer Science
School of Computing and Data Science
School of Computing and Data Science Institute of Data Science
The University of Hong Kong chyzhangéconnect. .kku. .kk
The University of Hong Kong dzouêcs hku. hk
Yuan Cao
Department of Statistics and Actuarial Science School of Computing and Data Science & Department of Mathematics The University of Hong Kong yuancao@hku.
Abstract
Adam has become one of the most favored optimizers in deep learning problems. Despite its success in practice, numerous mysteries persist regarding its theoretical understanding. this paper, we study the implicit bias of Adam in linear logistic regression. Specifically, we show that when the training data linearly separable, the iterates of Adam converge towards linear classifier that achieves the maximum -argin in direction. Notably, for general class of diminishing learning rates, this convergence occurs within polynomial time. Our result shed light on the difference between Adam and (stochastic) gradient descent from a theoretical perspective.
Introduction
is of the most widely used optimization algorithms in deep learning. By entry-wisely adjusting the learning rate based on the magnitude of historical gradients, Adam has proven to be highly efficient in solving optimization tasks in machine learning. However, despite the remarkable empirical success of Adam, current theoretical understandings of Adam cannot fully explain its fundamental difference compared with other optimization algorithms.
Adam 25
has been recently pointed out that the implicit bias 32 40 21 of an optimization algorithm is es- sential in understanding the performance of the algorithm in machine learning. In over- pee--paramttriieed learning tasks where the training objective function may have infinitely many solutions, the implicit bias of optimization algorithm characterizes how the algorithm prioritizes converging towards specific optimum with particular structures and properties. Several recent works studied the implicit bias of Adam and other adaptive gradient methods. Specifically, of AdaGrad, and showed that AdaGrad converges to a direction that can be characterized as the solution of a quadratic optimization problem related to the limit of preconditioners. However, their results cannot be extended to Adam. [45) showed that gradient descent with momentum (GDM) and its adaptive variants have the same implicit bias with gradient descent. This result is extended to the setting of training homogeneous models in [44). However, the results in [45] 44 reply on
33 studied the implicit bias
nonnegligible stability constant when the gradient entries are minimized below the stability constant
(which is by default 10 in Adam), adaptive gradient methods will essentially behave like gradient
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

descent. Therefore, it remains an open question how Adam will behave under the more practical regime where stability constant negligible.
We note that there exist several recent works studying variants of Adam without the stability constant. First of all, sign gradient descent, which can be regarded as Adam without momentum stability constant, is usually considered proxy of Adam in theoretical studies due to its case of analysis. [44] studied the implicit bias of steepest descent with respect different potentials and norms covering a variant of sign gradient descent, and demonstrated that sign gradient descent converges to the maximum Los -margin solution. However, this result for sign gradient descent cannot cover Adam, as the momentum terms in the update of Adam are crucial. Besides, more recent work [50) studied the implicit bias of AdamW without considering the stability constant. They showed that, the iterates of AdamW converge, then the limiting point must be a KKT point of an optimization problem with Sox constraints. However, the analysis of Adam W in [50] relies on a non-zero regularization parameter, and therefore cannot be extended to the study of Adam.
In this paper, we investigate the implicit bias of Adam. Specifically, let {(x,, y:) C RR x {+1} be a training data set of a binary classification problem. We consider using Adam to train a linear model to minimize the empirical logistic loss (or exponential loss). Then our main results can be summarized as the following informal theorem:
Theorem 1.1 (Simplified version of Theorem 4.5).. Let {' t (we 1 be the sequence of learning rates and iterates of Adam respectively. Suppose that the data set ((x,,)))) U/)];= is linearly separable, and that lime- = O. >I=0 1/ = xc. Then under certain conditions, it holds that
(We: V/ x;)
7 + Σ 1-1 The 7E 9e' -
)
min (E(m)
50
(for logistic loss)
|Wellas
0r=o7 7r
(We. yi x;)
T= Tf
min [E(m]
0
(for exponential loss)
|W
0r=
Gr
where y [[x|| minke[x]] (w, y/ x:) is the maximum -ar-nnn on the training data set.
Theorem
shows that, for general class of learning rate schedules, Adam will eventually achieve the maximum -margin on the training data set.
We demonstrate the implicit bias of Adam for solving linear logistic regression with linearly separable data. Specifically, we prove that Adam has an implicit bias towards a maximum 600- margin solution when solving linear classification problems. Our result distinguishes Adam from (stochastic) gradient descent with/without momentum, whose implicit bias towards the maximum fz-margin solution.
Our analysis of Adam covers a broad range of diminishing learning rate schedules. For me = O(t with (0, 1]. our result demonstrates the following convergence rate:
O a/2),
if a < 2/3;
(Wer Mi xx) Welloo
-
O logg)
if 2/3;
min (E(n)
0(tl-9).
2f < a < 1; if =ta=1.
O(1/log(),
Notably, when a < I, the above rates indicate that the convergence towards the maximum fxo- margin occurs in polynomial time. This further differentiates Adam from (stochastic) gradient descent with/without momentum terms of the convergence speed.
Our result focuses on a particularly challenging setting where we ignore the "stability constant e" in the Adam algorithm. In practice, the stability constant is by default set as e = 10-8 which is almost negligible throughout the optimization process. Therefore, by covering the setting without the stability constant, our theory matches the practical setting better. We demonstrate by simulation that our theory can also correctly characterize the implicit bias of Adam with the stability constant.
Notation. Given two sequences (a.) and (yn). J. we denote Vn O(y,) if there exist some absolute constant C₁ 0 and N > Osuch that [z,] S C. for all N. Similarly, we denote x, 22

---

variant of if there exist C2 > 0 and N > 0 such that |xx 2 C2lynl for all n > N. We say = (v.) if In (vn) and F,, = S2 ky,) both holds. We use O(+), ((-), and ( to hide logarithmic factors in these notations respectively. Moreover, we denote En = poly(yn) I, = O(yn) for some positive constant D, and n denote a V = max b) and a A b min(a, b). For any E N+. we use [r] to denote the set (1,2. ,n). For any scalar denotes the largest integer smaller equal to For vector E Rd a(k] denote its k-th entry. Finally, e E R" denotes the i-th basis vector in IR".
(y)) if 2,, poly(log(v,)) For two scalars and b,
IR, [c] denotes the smallest integer larger or equal to e and [c]
2 Additional Related Work
Theoretical analyses of Adam and its variants. There has been line of works studying the properties of Adam and its variants from different aspects. [37] pointed out that there exists simple convex objective functions which Adam may fail to minimize, and proposed
Adam, the AMSGrad algorithm, which enjoys convergence guarantees
convex optimization.
(54 10 17 33 optimization.
18 established optimization guarantees of Adam and its variants in non-convex
19 implemented variance reduction techniques in Adam and proposed new variants of Adam accordingly. [47 52 55 56) studied the generalization performance of Adam and 3 [ tried to explain the performance of Adam by studying the connections between Adam and sign gradient descent. [5] explored the optimization trajectories of Adam from the & geometry.
29
compared it with GD under different learning tasks. [27 4
6
Implicit bias. Classic results 40 21 demonstrated the iterates of GD will converge to the maximum f2-margin solution in direction on linear logistic regression with linear separable datasets. [31 extended this result under stochastic settings. [14] explored the implicit bias of general class of
optimization methods, containing mirror descent and steepest descent. (23 proposed a primal-dual
analysis and derived a faster convergence rate with larger learning rate compared to [40] 21). [48]
explored the implicit bias of gradient descent at the 'edge of stability' regime, where the learning rate can be arbitrarily large constant. [30 22 showed that q-homogeneous neural network trained
by GD will converge to KKT point of maximum b my-margin optimization problem. [8] established an implicit bias type result for the Lion [ algorithm its continuous form. There also exist numerous works studying the implicit bias for different problem setting, including matrix factorization models [16]] 28 36), squared loss models (38 24], weight normalization and batch
normalization [49 deep linear neural networks 15 20 two-layer neural networks [1] 34 13
26
3 Problem Settings
We consider binary linear classification problems. Specifically, given training data points {(x, w:) where x; Rd and y/s E {+1,-1}, we aim to find coefficient vector w which minimizes the following empirical loss
R(w)= 1
E((w xx)),
(3.1)
where E((w.ys y/ x;)) ) is the loss function value on the data point (x;, 9:). In this paper, we consider
E (bing Lexp). where (1) = log(1 + + is the logistic loss function and (exp(=) e is the exponential loss function. We consider using Adam to minimize (3.T). Denoting m_1 = - = E
d and starting with initialization wo. Adam applies the following iterative formulas:
m: = -,m + - (1- VR(w:),
(3.2)
V, = V2 + (1 - 32) VR(w:)?
(3.3)
m
W = W. - 1/ Vv
(3.4)
where ,1,82 E [0, 1) are the hyperparameters of Adam, and the square ()2, square root (v.) and
division (-) above all denote entry-wise calculations.
3

---

<v++++ where an additional term с = 10-6 8 added in (3.4) to improve stability. However, in our analysis, we do not consider such term c. This is because in practice, one seldom run Adam until V, is around the same level as e, However, by the nature of implicit bias, the result needs to cover infinitely many iterations, and the additional term will eventually significantly affect the result. In fact, a recent work (45] showed that when one considers such an additional é term, Adam will be asymptotically equivalent to gradient descent. In comparison, in this paper, will show that when ignoring e, Adam has unique implicit bias that is different from gradient descent.
Note that in practice, it is common to consider the variant Wa+1 = W, - "vi++"
Main Results
In this section, present main result the implicit bias of Adam in linear classification problems. We first introduce several assumptions.
Assumption 4.1. There exists E Rd such that (w. x,) >> 0 for all E [n].
Assumption
is a standard assumption in the study of implicit bias of linear models 40
14
23 45 48 It can be easily satisfied in the over-paranee wverppaaaeeteriee setting where d 2 n. With the linear
separability assumption, we can further define the maximum -s
max min (w, Yt xz).
(4.1)
w S1
We also make the following assumption on the initialization Wo. Assumption 4.2. The initialization Wo of Adam satisfies that for all & E [d], VR((w))M)) 2
42 ensures that at every finite iteration, the entries of v, strictly positive. We remark that this is a mild assumption: if x,, E [n]] are generated from a continuous, non-degenerate distribution, then regardless of the choice of Wu. (R( will only appear in our results in the form of log(1/p). and therefore, even if p is small, will not significantly hurt the convergence rates. A similar assumption has also been considered in [50].
Assumption
with probability 1. Moreover, p
Assumption 4.3. {ne are decreasing in i, and satisfy Σ T 0o, lim, 7t 0.
Assumption 4.3 is mild and standard assumption of the learning rates (17 ) that is commonly
considered in the general optimization literature. has also been considered recent studies of Adam and its variants 02 [9] 50).
Assumption 4.4. For / E (0.1) and e > there exist i E N4 and 02 that only depend on 3, C1. such that Σi= 3r (c Er dh- - 1) I 027) for all 2 f1.
Although Assumption 4.4 seems non-trivial, we claim it is a fairly mild assumption. In fact, for both small fixed learning rate 1/- 77, and decay learning rate π) (t + 2)- -a with (0, 1], Assumption 4.4 always hold. We formally prove this result in Lemma C.I in the appendix.
Now, we state main theorem about the implicit bias about Adam follows.
Theorem 4.5. Let (w, 1000 o be the iterates of Adam in (2.4) with 31 < B2. In addition, let ?
be defined in (4.1) and B = max4e(n) [|x; 11- Then under Assumptions 4.1 4.2
4.3 and 4.4 there
exists to tn d. B1, 32, 7, B, wo) such that
If lexps then for all tu.
log2 - - -1 vr and min
(we, Vo xx) |welloo
Eto
1/r + d d tF r-1
R(w:) <
? S
n
sE(n]
1/7
If f flog. then for all t to.
R(w ((w))
log 2
- E1-l
71
and
(We, S fi xi) [w 1loo
21=0 The + d x
177 -
The -1E, T.
min [E
s 50
Σ1=1 7

---

where we use O()) to omit factors that only depend on 82, B.
Theorem 4.5 implies that Adam can minimize the loss function to zero, and that the normalized bo margii achieved by Adam will eventually converge to the maximum -margnn of the training data set. To address general learning rate schedules, we do not specify a particular convergence rate for either the loss or the margin, nor do we provide exact formula for to. However, it can be easily verified that R(wa) I O(e "/4(1-a)) when т) (t + 2)- with a 1. This loss convergence rate of Adam is much faster than that (stochastic) gradient descent (with momentum) given fixed small learning rate, which is of order O(1/l) [40 31 45]. In addition, we have la = poly [n, d, (1-3)) --- (1-28 32) 31
B, log(1/p), R( (w)] when = (1+2) with a < 1, and we defer the derivation details to Appendix [8.2, Regarding margin convergence, will give set of detailed convergence rate results for different learning rate schedules in Corollary 4.7
According to Theorem 4.5 the nature of Adam is vastly different from (stochastic) gradient descent from the perspective of implicit bias: Adam maximizes the -margin, while existing works have
demonstrated that (stochastic) gradient descent maximizes the f2-margin 40
31
21 Compared with
our result demonstrates novel type of implicit bias with accurate convergence rates, which can not been covered in the previous results. Notably, [45] showed that, if a stability constant is added, i.e.. (3.4) is replaced by We+1 W; ?/t /Vett* then Adam will eventually be equivalent to gradient descent and will converge to the maximum l2-margin solution. However, the analysis in [45] relies on a positive e: their proof is based the fact that after large number of iterations, the entries of will eventually be much smaller than e, and the update of Adam will be similar to gradient descent with momentum. In analysis, are able to cover the setting where 0. and result demonstrates that studying the setting without is essential, as the implicit bias is completely different. Section [] we will demonstrate by experiments that our setting matches the practical observations better.
existing works on the implicit bias of adaptive gradient methods [35] 45 50
As we have discussed, Theorem 4.5 implies the convergence the normalized fox -margin of Adam iterates towards the maximum 8x -mrgin. Since the results cover very general learning rates, the convergence rates are presented in rather complicated formats. However, based on the assumption immediately conclude the following simplified result by
S8 that - T/t do, lim,- Th: O, the Mesàrr theorem (see Theorem C.8 in the appendix).
Corollary 4.6. Under the same conditions Theorem 4.5 holds that
(W,, 9:
x.)
lim min iE[n]
max min (w, 9i x.) [|w W ll iE[m]
|weloo
there exists a unique maximum loo -margin solution w- = argmmx/[w/l=ss minkein] (w, x:), then we have lim Twll w".
We can also investigate the convergence rates of the mar-mnn with specific learning rates. The results summarized in the following Corollary.
Corollary 4.7. Consider T) = (t + 2) with a E (0, 1]. Denote by w exp and w. the iterates of Adam for & Loxp and e boog respectively. Suppose that B1 32 and Adam starts with initialization Wo. Let B == max;e|m] ||x,||1- Then under Assumptions 4.1 and 4.2 there exists
to lo(n, d, B1, 82,7: 7: B, p. wo) such that for all 2 lo, the following results hold:
If a < 2
3
(w mxp xi)
(w/ log [
xi)
min
min iE(n)
ie
w
1loc
log
11000
ta/2
a 3
2
(w. oxp Di xx)
d log + +log + log ((w)) + [log( (1g(1/p)2//
min xE(n]
[w exP 1100
7
50
t1/3
(w. log
F/ X;)
d logtt t + nd + nR(ww) + [log(1/p))133
min sE(n]
<
[w 1og
1/3
5

---

If 1a<1,
exp B/ x!)
d log + log R(wo)
+ [log(L//
min
[w exp
(Wg log
Us- x,)
d nd 201-
n (wo) [og(1/p))=-
min =E[n]
- S
[w][0]] 11x0
tl-a
If
2 De X2)
exP
d + log n + log R R(wu) + log log(1/p)
min
50
:E(n]
w e 0c
log t
(we
Jng
Ms X+)
d n log d mR((w)) + log log(1/p)
iE|n]
min
|| log
7
0
logt
Corollary 4.7 comprchensively presents the convergence rate of the -marinn for different learning rates. It also indicates that the margin convergence rates for fexp and &log are of the same order of t. Notably, for < 1, the normalized fo- -aarinn converges in polynomial time. This clearly distinguishes Adam from (stochastic) gradient descent with/without momentum, for which the normalized & fa-margin converges speed (1/ log t) 44
We note that recent work [46] proposed a novel algorithm named progressive rescaling gradient descent that can maximize the margin an exponential rate. Here our focus is different from [46]: our purpose is not to propose new algorithms to achieve better convergence rates, but is to theoretically study the properties of the classic Adam algorithm. We would also like remark that, although Corollary 4.7 seemingly indicates that 7/2 = (t + 2) 22-23 is the learning rate schedule with the fastest convergence rate, it does not mean that 7/2 = (t 2) -2/3 always converge faster than the other learning rate schedules in all learning tasks. The bounds Corollary [.7 are derived under the worst cases, and in practice, we can frequently observe that the margins all converge faster than the bounds in the corollary.
20
45
Experiments
In this section, we conduct numerical experiments verify our theoretical conclusions. We set the sample size n 50, and dimension d = 50. Then the data set {(x,, 81)} } are generated as follows:
1. x,, E: [ra] are independently generated from (0,
2. yıs E [n] are independently generated from as +1 or - with equal probability.
Note that for data sets generated following the procedure above, Assumption 4.1 almost surely holds. We can also apply standard convex optimization to calculate the maximum E margin In order to make a clearer comparison between Adam and GD, we generate 10 independent sets of data, and we select the dataset with the most significant difference in the directions of the maximum ég-margin solution and maximum -margin solution. We then run the experiments on this selected data set. Throughout our experiments, for gradient descent with momentum, we set the momentum parameter as 31 = 0.9, and for Adam, we set 31 0.9, B2 = 0.99. All these hyper-parameter setups are common in practice. All optimization algorithms are initialized with standard Gaussian distribution, and are run for 10th iterations.
We first run GD, GDM, Adam without the stability constant, and Adam with stability constant 10- train linear model minimizing the logistic loss, and compare their normalized 6x0- margin and normalized my-margin. The results are given in Figure I] We can see that the normalized -mrrgnss of Adam, both with and without c, converge to the maximum lo -margin, whereas the normalized L -aarins of GD and GDM do not. In contrast, the normalized &g fz-margins of GD and GDM converge to the maximum ma-mangin, while the ma-maggs of Adam, both with and without do not. By comparing the curves of Adam with and without we find that they behave similarly and their convergence remains highly stable. This justifies our theoretical setting where we ignore the stability constant in Adam, and demonstrate that our maximum & -margin implicit bias result

---

derived without e characterizes the practical behaviour of Adam more accurately compared with the maximum l2 fa-mari result for Adam with in 45
We also run a set of experiments to demonstrate the polynomial time convergence rate of the foo margin. We run experiments Adam with learning rates 7 @(t=") for {0.3, 0.5, 0.7, 1), and report the log-log plots in Figure 2 where we perform the experiments for Adam with/without the stability constant separately. In the log-log plot, we observe that after certain number of iterations, curves for a < 1 almost appear as straight lines, suggesting that the normalized &oc -mr-inn converges in polynomial time for a < 1, while the curve for indicating the normalized lo margin converges logarithmically in t for = 1. Similarly to the previous observations, there still no significant distinction between Adam with and without c, further demonstrating that our theoretical setting, which disregards is reasonable. We also note that in Figure 2 the margin achieved by Adam with Y = ( converges the fastest. However, as we have commented in Section 4 different learning rate schedules may perform differently on different data sets, and is not necessarily true that ?) ( -0.3) is always the best learning rate schedule.
exhibits logarithmic behavior,
175
0.4
125
mi
Adam with 1-
Adam with c. R) 1.0
0.2
Adam w/o --0
0.50
with 0.1
GDM p
0.1
margin
miximmu
0.00
0.0
10a
10
10a
10a
10a
10a
10
10a
10a
10r
10P
10e
iteraiions
(a) normalized &o -margin
(b) normalized f2-margin
Figure I: Normalized &oo -maginns and ma-mangs achieved by GD, GDM, and Adam with/without the stability constant during training, (a) gives the results of normalized -margins,, while (b) shows the results normalized f2-margins.
10a
109
109
10a1
Adam with f - 193
10
Adam with (g=
Adam with 13
Adam with 2.03
Adam with p47
Adam with 1o07
1
10"*
Adam
10'
10a
10'
10'
nerations
(a) normalized lo margin gap with
(b) normalized for margin gap without
Figure 2: Log-log plots of the normalized for -maginn gaps mmnnggn]] training iterations. (a) presents the results for Adam with the stability constant e, and (b) presents the results for Adam without the stability constant
( (W,, D/ x;) / w/ 7 versus
6 Proof Sketch for Theorem 4.5
In this section, we explain how we establish the convergence of the -margnn of linear models trained by Adam, and provide the sketch proof Theorem 4.5) For simplicity, here we focus on the case & = lexp- The proof for = bog is almost the same.

---

We first introduce several notations. Define
12 Σ 72
g(w)
El ((w,y: x;))
Then for E E {lexp: foog), is clear that g(w) for all w R In the following, we will show that ((w) plays key role in the convergence and implicit bias analysis.
Step 1. Accurate characterizations of the first and second moments. Adam algorithm is defined based on the first and second moments m, and V;, which are calculated as exponential moving averages of the historical gradients and squared gradients respectively. key challenge in studying Adam is to accurately characterize each entry of m, and V; throughout training. We present the following lemma.
Lemma 6.1. Under the same condition in Theorem 4.5 there exists 4 = 11 (B1, 82, B) such that
m [k:] (1 81+1) VR VR(w.) [A] S (me):
vr [k] v 1 35+1 VR(w.) S co C.
for all t >> t and ls E [d], where C. and c2 constants that only depend on 31, 32 and B.
Since T)s, 10 and 35+11 all decrease to zero as / increases, Lemma 6.1 implies that after a sufficient number iterations, the entries m, and v, will be close to the corresponding entries of (R(w,, and (w.) respectively. Notably, the term G (w.) also appears in the bounds. In fact, deriving such bounds with the factor Gl (we) is essential to enable our implicit bias analysis: when the algorithm converges, by definition, (ww)) will also decrease to zero, which implies that the bounds with the factor (w,)) are strictly tighter than the bounds without ((w,). Lemma 6.1 is one of our key technical contributions.
Step R(w,) starts to decrease after fixed number iterations. Based on Lemma 6. we can analyze the convergence of R R(w,). Specifically, we can show that, after fixed number of iterations, the training loss function will start to decrease. This result is summarized in the following lemma.
Lemma 6.2. Under the same condition in Theorem 4.5, there exist t tt B2, B) such that for all t > t1, it holds that
R(w++1) S R(w:) - 767 (1 (1- C18 - C2d - (nd + nn) G(we),
where C1, C2 only depend on B1, B2, B.
Note that by definition, G(w) > 0 for all w E Rd. Therefore, Lemma 6.2 implies that R(w:)) starts to decrease after a fixed number of iterations, and gives bound on the decreasing speed. We remark that the proof of Lemma 6.2 is highly non-trivial. Although we have related m, and v. to the loss gradient VR( (.) in Lemma 6.1, the fact that Wt+1 is updated according to the entry-wise ratio m still introduces challenges: under our problem setting, it is entirely possible that at certain iteration, a certain entry of VR( will exactly equal zero. In this case, the results Lemma 6. not directly lead to any conclusions about the ratio m. /Vi In our proof, we implement careful inequality that also takes the historical values of VR(w,) into consideration.
Step 3. Lower bound for un-normalized margin. The proof of the implicit bias towards maximum -arrin also relies on a tight analysis on the un-normalized margin min (oneix/[w, (We, Vi x;) during training. We have the following lemma providing lower bound on the un-normalized margin.
Lemma 6.3. Under the same condition in Theorem 4.5 all t 2 to, then holds that
if there exists to such that R(w,) I log for
G(wr)
min muin(we. yi s
Tr
Cgd R(w+)
Σ T=
1/7
2
C4
T=to
r=to
for all 1 2 lo where Cg, C4 only depend on B1, 12, B.
Note that this lower bound contains negative term -C3d -C3d( 1-1 Di=
1/
3/2
+
ET=to 112). Under
our (mild) assumptions the learning rates, it is entirely possible that Er= 1T
3/2
- nr
8

---

to0 and thus the negative term in the lower bound may go to -c0. However, we can show that lim,-xc ((w,)/((w,)
(in fact, for exponential loss, it is obvious that ((w,)/R(w,) 1). Therefore, after fixed number of iterations, the positive term in the lower bound will dominate, and Lemma 6.3 gives a non-trivial bound. The strength of this lemma lies its applicability very general learning rates (7h 1==
Step An upper bound of ||Welloo.
In Lemma 6.33 we have obtained a lower bound of the un-normalized margin. However, to show the convergence of the -ormaalll margin, also need to establish tight upper bound of |/wa llae- We present this result in the following lemma, which is inspired by Lemma 4.2 in [50].
Lemma 6.4. Suppose that the same conditions in Theorem 4.5 hold. There exist Cs. Cs that only depend on $1, B, such that the following result hold: if there exists to > log(11p) such that for all t 2 to. then |[wellso S -i=to 7) + Co Ei=-l 17 for all t > to.
R(w))= S
V Cono
Lemma 6.4 gives upper bound of ||wellso which mainly depends - ?/- Note that
Lemma 6.3 also gives lower bound of the un-normalized margin which mainly depends on
Er 9 (/ (w))) These two lemmas will be combined to derive the convergence of the normalized margin.
Step 5. Finalizing the proof. Finally, based on the lemmas established in the previous steps, we can prove Theorem 4..5 We also need the following utility lemma provided by (56).
Lemma 6.5 (Lemma A.2
[56]). For Adam iterations defined in (3. 3.4 with B1 S 32 and let
Ba (111-8)) then m. k] a. Vr]kk for all k E [d].
We are now ready prove Theorem 4.5 for the case lexp-
Proof of Theorem 4.5 By Lemma 6.2 there exists to = +2(d, B1, B2, y, B)) such that
?i7 g(w:))
R( R(w S R(w,) 2
(6.1)
for all 2 12- Note that for l fexp= by definition we have g(w:) Ei=
= x,))
R(w:). Therefore, for all t > f2. 6.. can be re-written
R(W++1) < (1 7Tk 2 R(w,)= S R(w,) e 2 < R(Ww,))
Although loxp is not Lipschitz continuous over I, we have R(Wez) S R(wo) EaB
2/20' W
by Lemma 6.5 and triangle inequality. Letting Ro = minf log
and
VBR-Co 13
to (n, d BI. 32, r, B. wo) be the first time such that E dr
2aB 1/ 12-1
17-
7
log R(wo) 2 log Ra and to 2 log p. By such definition of lo, we can derive that for all 1 2 lo- 7
Pr
R(w))= I R(Ww,)
Ro
which proves the bound on R(w,). Since to satisfies all the conditions in Lemmas 6.3 and 6.4 by Lemmas 6.3 6.4annd and the fact that G(w,) = R(w,) ) for exponential loss, we have
(Wi, De xx)
E 77 - C3d( Et=1. + + ni) C4
||
Ei=1 17r C6 E.e 17-
for all [n]. where Ca, C4 and Oo are constants solely depending on B1, 82 and B. Now by definition, we have y 2 minze(m) (W x/)/|[wellas Therefore, we have
1Co En- 7r + Cgd Ei-1 1 + E 1 + Ca
(We, Di xi)
min k
|
7
Σ Mr + Cb 11-1 7
Ei Th + d -r=to 17
fo-1
00
Σ1=1 7/
where the second inequality follows by the assumption that M) 0. This finishes the proof.

---

7 Conclusion and Future Work
In this paper, study the implicit bias of Adam under challenging but insightful setting where the "stability constant c" is negligible and set to zero. We demonstrate that Adam has an implicit bias converging towards the maximum -marinn solution, and such convergence occurs polynomials of time for a general class of learning rates. This result further helps to understand the distinctions between Adam and (stochastic) gradient descent with/without momentum, whose iterates will eventually converge to the maximum lz- fa-margin solution with an ( 2(1/log t) convergence rate. This finding aligns with the implicit bias of Adam observed in experiments, for both cases the stability constant e is zero and 10 We predict that similar result can be extended to homogeneous neural networks, and we believe that this is good future work direction. Moreover, since this paper focuses on full-batch Adam, another feasible future work is to investigate the implicit bias of stochastic Adam based on our results. In addition, establishing matching lower bounds for the loss and margin convergence rates for Adam is also an interesting future work direction.
Acknowledgments and Disclosure of Funding
We would like to thank the anonymous reviewers and area chairs for their helpful comments. DZ is supported in part by NSFC 62306252, Guangdong NSF 2024A1515012444 Hong Kong ECS award 27309624, and the central fund from HKU IDS. YC is supported in part by NSFC 12301657 and Hong Kong ECS award 27308624.
References
[1] ALI, A., DOBRIBAN, and TIBSHIRANI, R. (2020). The implicit regularization of stochastic gradient flow for least squares. In 8th International Conference on Learning Representations, ICLR 2020. PMLR.
[2] ARORA, S., COHEN, N., HU, W. and LUO, Y. (2019). Implicit regularization in deep matrix factorization. Advances in Neural Information Processing Systems 32.
[3] BALLES, L. and HENNIG, (2018). Dissecting adam: The sign, magnitude and variance of stochastic gradients. In Proceedings of the 35th International Conference Machine Learning, ICML 2018 (J. G. Dy and A. Krause, eds.), vol. 80 of Proceedings of Machine Learning Research. PMLR.
[4] BALLES, I.., PEDREGOSA, F. and ROUX, N. L.. (2020). The geometry of sign gradient descent. CoRR abs/2002.08056.
[5] BERNSTEIN, J., WANG, Y., AZIZZADENESHIELI K. and ANANDKUMAR. A. (2018). SIGNSGD: compressed optimisation for non-convex problems. Proceedings of the 35th International Conference Machine Learning, ICML 2018, vol. 80 of Proceedings of Machine Learning Research. PMLR.
[6] BERNSTEIN, J., ZHAO, J., AZIZZADENESHELL K. and ANANDKUMAR. A. (2019), signsgd with majority vote is communication efficient and fault tolerant. In 7th International Conference on Learning Representations, ICLR 2019. OpenReview.net.
[7] CAO, Y., ZOU, D... LI, Y. and Gu, Q. (2023). The implicit bias of batch normalization in linear models and two-layer linear convolutional neural networks. In The Thirty Sixth Annual Conference Learning Thheory. PMLR.
[8] CHEN, L., LIU, B., LIANG, K. ET AL. (2023). Lion secretly solves a constrained optimization: As lyapunov predicts. In The Twelfth International Conference on Learning Representations.
[9] CHEN, X., LIANG, C., HUANG, D., REAL, E.,, WANG, K., PHAM, H., DONG, X., LUONG, T., HSIEH, C.-J., LU, Y. ET AL. (2024). Symbolic discovery of optimization algorithms. Advances in Neural Information Processing Systems 36.
[10] CHEN, X., LIU, S., SUN, R. and HONG, M. (2019). On the convergence of class of adam- type algorithms for non-convex optimization. 7th International Conference on Learning Representations, ICLR 2019.
10

---

[11] CHIZAT, L. and BACH, F. (2020). Implicit bias of gradient descent for wide two-layer neural networks trained with the logistic loss. Conference on learning theory. PMLR.
[12] DE, S., MUKHERRBEE, A. and ULLAII, E. (2018). Convergence guarantees for rmsprop and adam in non-convex optimization and an empirical comparison to nesterov acceleration. arXiv preprint arXiv:1807.06766
[13] FREI, S., VARDI, G., BARTLETT, P., SREBRO, N. and HU, W. (2022). Implicit bias in leaky relu networks trained on high-dimensional data. In The Eleventh International Conference on Learning Representations.
[14] GUNASEKAR, S., LEE, J., SOUDRY, D. and SREBRO, N. (2018). Characterizing implicit bias in terms of optimization geometry. In Proceedings of the 35th International Conference on Machine Learning, vol. 80 of Proceedings of Machine Learning Research. PMLR.
[15] GUNASEKAR, S., LEE, J. D., SOUDRY, D. and SREBRO, N. (2018). Implicit bias of gradient descent on linear convolutional networks, Advances in neural information processing systems 31.
[16) GUNASEKAR, S., WOODWORTH, B. E., BHOJANAPALLI, S., NEYSHABUR, B. and SREBRO, N. (2017). Implicit regularization matrix factorization. In Advances in Neural Information Processing Systems.
[17] GUO, Z., Xu, Y.. YIN, W. JIN, and YANG. T. (2021). A novel convergence analysis for algorithms of the adam family, arXiv preprint arx:v:2112.03459.
[18] HONG, Y. and LIN, J. (2024). On convergence of adam for stochastic optimization under relaxed assumptions. arXiv preprint arXiv:2402.03985
[19] HUANG, F., LI, J. and HUANG, H. (2021). Super-adam: faster and universal framework of adaptive gradients. Advances in Neural Information Processing Systems 34
[20] J1, Z. and TELGARSKY, M. (2019). Gradient descent aligns the layers of deep linear networks. In 7th International Conference on Learning Representations, ICLR 2019.
[21] J1, Z. and TELGARSKY, M. (2019). The implicit bias of gradient descent on nonseparable data. In Proceedings of the Thirty-Second Conference on Learning Theory, vol. of Proceedings of Machine Learning Research. PMLR.
[22] J1, Z. and TELGARSKY, M. (2020). Directional convergence and alignment in deep learning. Advances in Neural Information Processing Systems 33 17176-17186.
[23] J1, Z. and TELGARSKY, M. (2021). Characterizing the implicit bias via a primal-dual analysis. In Algorithmic Learning Theory, 16-19 March 2021, Virtual Conference, Worldwide, vol. 132 of Proceedings of Machine Learning Research. PMLR.
[24] JIN, H. and MONTUFAR, G. (2023). Implicit bias of gradient descent for mean squared error regression with two-layer wide neural networks. Journal of Machine Learning Research 24 1-97.
[25] KINGMA, D. P. and BA, J. (2015). Adam: A method for stochastic optimization. In 3rd International Conference on Learning Representations, ICLR 2015.
[26] KoU, Y., CHEN, Z. and GU, Q. (2024). Implicit bias of gradient descent for two-layer relu and leaky relu networks nearly-orthogonal data. Advances in Neural Information Processing Systems 36.
[27] KUNSTNER, F., CHEN, J., LAVINGTON, J. W. and SCHMIDT, M. (2023). Noise is not the main factor behind the gap between sgd and adam on transformers, but sign descent might be. The Eleventh International Conference on Learning Representations, ICLR 2023. OpenReview.net.
[28] LI, Y., MA, T. and ZHANG, H. (2018). Algorithmic regularization in werrpaarameterized matrix sensing and neural networks with quadratic activations. In Conference On Learning Theory.
11

---

[29] LIU, M., ZHANG, W., ORABONA, F. and YANG, T. (2020). Adam+: A stochastic method with adaptive variance reduction. arXiv preprint arXiv:2011.11885.
[30] LYU, K. and LI, J. (2019), Gradient descent maximizes the margin of homogeneous neural networks. In 7th International Conference Learning Representations, ICLR 2019.
[31] NACSON, M. S., SREBRO, N. and SOUDRY, D. (2019). Stochastic gradient descent on separable data: Exact convergence with fixed learning rate, In The 22nd International Conference on Artificial Intelligence and Statistics, AISTATS 2019, vol. 89 of Proceedings of Machine Learning Research. PMLR.
[32] NEYSHABUR, B., TOMIOKA, R. and SREBRO, N. (2014). In search of the real inductive bias: On the role of implicit regularization in deep learning. arXiv preprint arXiv: 1xXix:1412.6614
[33] PAN, Y. and LI, Y. (2022). Toward understanding why adam converges faster than sgd for transformers. In OPT 2022: Optimization for Machine Learning (NeurIPS 2022 Workshop).
[34] PHUONG, M. and LAMPERT, C. H. (2020). The inductive bias of relu networks on orthogonally separable data. In 8th International Conference on Learning Representations, ICLR 2020.
[35] QIAN, Q. and QIAN, X. (2019). The implicit bias of adagrad separable data. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019.
[36] RAZIN, N. and COIEN, N. (2020). Implicit regularization in deep learning may not be explainable by norms. Advances in neural information processing systems 33 21 1174-21187
[37] REDDI, S. J., KALE, S. and KUMAR, S. (2018). On the convergence of adam and beyond. In 6th International Conference on Learning Representations, ICLR 2018.
[38] ROSASCO, L. and VILLA, S. (2015). Learning with incremental iterative regularization. Advances in neural information processing systems 28.
[39] SHALEV-SHWARTZ, S. and SINGER, Y. (2010). On the equivalence of weak Iearnability and linear separability: new relaxations and efficient boosting algorithms. Mach. Learn. 80 141-163.
[40] SOUDRY. D., HOFFER, E., NACSON, M. S., GUNASEKAR, S. and SREBRO, N. (2018). The implicit bias of gradient descent on separable data. J. Mach. Learn. Res. 19 70:1-70:57.
[41] TELGARSKY, M. (2013). Margins, shrinkage, and boosting. In Proceedings of the 30th International Conference on Machine Learning, ICML 2013, vol. 28 of JMLR Workshop and Conference Proceedings. JMLR.org.
[42] VARDI, G., SHAMIR, O. and SREBRO, N. (2022). On margin maximization in linear and relu networks. Advances in Neural Information Processing Systems 35 37024-37036.
[43] VARDI, G., YEHUDAL, G. and SHAMIR, O. (2022). Gradient methods provably converge to non-robust networks. Advances in Neural Information Processing Systems 35
[44] WANG, B., MENG, Q., CHEN, W. and LIU, T.-Y. (2021). The implicit bias for adaptive optimization algorithms on homogeneous neural networks. International Conference on Machine Learning. PMLR.
[45] WANG, B., MENG, Q., ZHANG, H., SUN, R., CHEN, W. MA. Z.-M. and LIU, T.-Y. (2022). Does momentum change the implicit regularization on separable data? In Advances in Neural Information Processing Systems, vol. 35. Curran Associates, Inc.
[46] WANG, M.. MIN, Z. and Wu, L. (2024). Achieving margin maximization exponentially fast via progressive norm rescaling. In Forty-first International Conference on Machine Learning.
[47] WILSON, A. C., ROELOFS, R., STERN, M., SREBRO, N. and RECHT, B. (2017). The marginal value of adaptive gradient methods in machine learning. Advances in neural information processing systems 30.
12

---

[48] WU, J., BRAVERMAN, V. and LEE, J. D. (2023). Implicit bias of gradient descent for logistic regression the edge of stability. Advances in Neural Information Processing Systems 36: Annual Conference Neural Information Processing Systems 2023, NeurIPS 2023.
[49] WU, X., DOBRIBAN, E., REN, T., WU, S., LI, Z., GUNASEKAR, S., WARD, R. and LIU, Q. (2020). Implicit regularization and convergence for weight normalization. Advances Neural Information Processing Systems 33
[50] XIE, S. and LI, Z. (2024). Implicit bias of adamw: -orm constrained optimization. In Forty-first International Conference on Machine Learning.
[51] XIE, S., MOHAMADI, M. A. and LI, Z. (2024). Adam exploits loo geomeery of loss landscape via coordinate-wise adaptivity. arXiv preprint arXiv:2410.08198.
[52] ZHANG, J., KARIMIREDDY, S. P., VEIT, A., KIM, S., REDDI, S., KUMAR, and SRA, (2020). Why are adaptive methods good for attention models? Advances in Neural Information Processing Systems 33 15383-15393.
[53] ZHANG, Y., CHEN, C.. SHI, N.. SUN, R. and LUO, Z.-Q. (2022). Adam can converge without any modification on update rules. Advances in neural information processing systems 35 18386-28399
[54] ZHOU, D., CHEN, J., CAO, Y., TANG, Y., YANG, Z. and GU, Q. (2024). On the convergence of adaptive gradient methods for nonconvex optimization. Transactions on Machine Learning Research.
[55] ZHOU, P., FENG, J., MA, C., XIONG, C., Hoi, S. C. H. ET AL. (2020). Towards theoretically understanding why sgd generalizes better than adam in deep learning. Advances in Neural Information Processing Systems 33 21285-21296.
[56] Zou, D., CAO, Y., LI, Y. and GU, Q. (2023). Understanding the generalization of adam in learning neural networks with proper regularization. The Eleventh International Conference on Learning Representations, ICLR 2023. OpenReview.net.
13

---

A Proof in Section 6
A.1 Preliminary Lemma
It can be figured out that only the product ys is concerned in 33. Therefore, we define = X4, then 3.1 could be re-written as
R(w)= Σ e((w, 2)).
We also define Z = [21, 22, Zn E R to denote our sample with i-th row is 2, and we will use Z Ruxd to denote the data sample instead of [(x,8)))3 following paragraphs. Then g(w)
the
and we introduce L'(w) [ z,))] which means g(w) = I[]((w)ll- The fol-
n [-]e(((,,)) 21),, a ((w z2)),.... (2W(((2))),... lowing lemma reveals the relationship between the maximum margin y and VR(w,) by duality.
Lemma A.I. For data sample Z under Assumption 4.1
and maximum foo -margin 7 defined in
then
? S min I rrrl,,, rEAn
where 4, (r/r RR, ME= 1, 2 0} the n dimensional simplex.
Remark A.2. Since L'(we) G(w)) E An, and vR(w.) = zT L'we), we always have >g(w,) <
(V:((;;) I1, which is the essence for proving the convergence direction of gradient-based algorithms.
This result was also proposed [39 14 23).
Proof of Lemma A.] Firstly, we introduce a definition of indicator function z(-) as
0, E E; <x(2) ( + 00, if E,
(r) where E is any set. Let =s. and g(z) | l1. then we could derive that fr(r")
[aXie(m] (e;, r*) is the dual function of f(r) and (z)) = 11 is the dual function of g(z).
Then by Fenchel-Youne inequality, have
min rEAn
IZ r(]1 = min
rER" ((r) + g(Z r(
2
max WEEd
- (Zw) - 9" (-w)
max WEB
max e, Zw - [|/w .E(n]
max
min e, Zw 7
[| S1
A.2 Proof of Lemma 6.5
We first introduce the proof of Lemma 6.5 since it will be used for further proof of other lemmas.
Proof of Lemma
6.5 By Cauchy-Schwart Schwartz inequality, we could derive an upper bound for m, [k] as
m [K]]
B1 8,m,- [k] (1 B1) VR(w.)
Σ BT 31) [R(w..>)[k)
V 13 82) BT 31)
VR(W
135(1 122)
88 (1- 1
35 B2) VR( vR(w<>>)1113)
Σ
35(1-
T=0
< 2 v, [.].
14

---

The last inequality is from
Velk = Σ
35 32) \R(w;-n)[k},
7=0
and
31)
(1- ) 8
B2 -3,)
a²
35 - 32)
1 - B2
82
(1 - A22 (8))
==0
This finishes the proof.
A.3
Proof of Lemma
Proof of Lemma 6.1
Let a
0a(1-8:) (1-82)(822 PPf
be defined in Lemma 6.5 For m. [k], it could be
rewritten as
my [k] =
Σ
(T - B1) VR(W,-r)(A)
-=0
= -1- (R(w:)[k) + Σ (1 B1)3T (VR(W.-)\M) (R(w.)(kk)
7=0
Therefore the difference between m. [k] and (1 - -(+1) VR(w:) can be bounded as
m, [k] (1 - - vR(w:)
Σ [1 3:)3T
(VR(W:->)BB [|]
vR(W:)(k)) -VR[)))))
Σ 3188
E (((wer)) 2,)) - C'((We 2z))] 2, 2/
Σ (1 B1)8T (1 Σ ((((ww, 2i))| ((((wor: 2n)) - [R:]]
e((we,z)))
7=0
$ (1 BB) Σ B8 ('((e. ())2
(1 31)Be21 G(w.) = Cmll g(w,).
The second inequality holds since
[k]] < || |2,111 B, and for both E E flexps bugg), we have
E' (((Wor7;2)) (((W,, 2,))
S ellwe wwwwwwwwwaee
w.-..
x llw, we- 1oo lmill ca Ei Ve-o! 1,
by Lemma 6.5 and Lemma C.5
The last inequality holds since Σt B4 Pe-r! - -1) S
c2ll by our Assumption 4.4 Similarly for v.[k], we also have
ve [k]] (1 -1-1 VR(w;) [k|
1
(1- (VR(W>-)<K)P- -RW
Ea (1-333333
1 Σ (() 21)) ((we, 2:)) ((we. 2,))] z, [k]] 22((k)2,((1)) [k.))
Σ (1- B2)
kz [2 2 [s1)
('((w, 2z)) (e)):):))(((. (w))
7=0
1,j=1
15

---

n
53 B²) Σ Σ
32
((w
(2 (c
n 1,=1
< 33(1 - B2) e2t ((w.)² = e.p ((we)²
Similarly, the second inequality holds since 22 [ [,]]|, s |2||i||z,|1 S B², and for both (eeps boggh, we have
8' ((WI- 2,) ( 2gi) -1
(' ((W,,, 2i) ) Wes k;))
(ww, ((w.- -. -1 1) + (eliwi-w-rza)) -1) + (cliWt-wnnnttt))l
[lw |1:ll1 1)
(elli-w-rlllllle 1asyll -1) + we 11 -1)
2.B
by Lemma 6.5 and Lemma C.6 The last inequality holds since Σt= 0J (c Ei' Me- 1)
C2f) by our Assumption 4.4 Now, it remains to show the upper bound for \v V
3221
[A)]].)[A)]. Notice that both v.[k] and (1 -3+1) VR(w;; are positive and for two positive numbers a and b, la² bb blla + b) 2 la - b/2, therefore we finally conclude that,
V1
V M
1-- [R(w:)(<)] S COVTi -(w.).
This finishes the proof.
A.4 Proof of Lemma 6.2
Before we prove Lemma 6.2 we first introduce and prove Lemma A.3
which will used for proving
Lemma 6..2
Lemma A.3. Under the same condition in Theorem 4.5
there exists
(111,, (2, 7), such that
when > f1, we have
g
VR(()),
/v/ )
m,
VR
(RR(w)ll
$41
VR(W))
354T
6c,,
V + 30mmh)) g(w.), (A.1) 1-
VI
B2
where Cn and cu are both constants which only depend on 33, B2 and B.
Proof of Lemma A.3 By Lemma 6.1 we could re-write my [k] and /vllk] as
m; [k] (1 8 t). VR(w.) Cmalle G(w.) Er,m,,
and
ve[k) k
/
35+1 VR(w.)]K] cv cu G(w:) EI,0Kk 0,
where 6.m. and v, are just some error terms with (e,,b (e, S inner-product (VR(w;), m.) for each iteration
Then we can calculate the
VR(w:), Vv
m,
[R((w)) + Σ vR(W)(())
my [k]
FR(w:)
[
VR(w:)
16

---

Moreover, we let
mr[k]
VR(W:) [K]
Eτ, = VR((w:)
ve[ki
V R w:) [A]]
(1 13-
VR( (w:) + Cm ((ws)) 6t,,,, g/1 [R((w) Ce 9 ((w)) Cr,u,k
VR((::)()) VR(ws)
[RR(wa)[k)
and consider to separate Éi, into two complementary parts. The first part is Ee,k Ar, where AeA {v1 - 18211 [VR(w:) 2 200//Tt g(we)) lee,oul). While another part is Er, 1l A5 where Af, {V1 -1- VR(w:)(B 20 ((w)) leccull By such separation, have
d Eou Ank +
[(0| = Σ fe + Eex Lax
AEN
S
Σ Eee AAA
We calculate part by part. For the first part
Σ
Ex=1 1= Se, Anel we have
d
ge+1
35+1
VR(W.)]<]] (cm + C. CV
g(w.)) /VR(w.)[<]]
E
A
11 A
- 832 [R(ww][k] + +o - g(w.) ((,0k)) [R(())]()]
Am 1
kml
d
1
g1+1
v 16t1
VR(W (Crm + CoV g(w.)) |R[[
//11 Bzt1. /R([w)]k]]
k=1
8+
(R(We))l
+
2d
Cmmlle + coyTH) 9(w)).
(A.2)
3441
The first inequality is derived by triangle inequality and let,m, ke,v,k 1. The second inequality holds since / - - 1,+1 [RR(w:)()] + G. /Th G(w.) 6r,n, > 1// gt+1 [w:)]] when A = 1. And the last inequality is simply due to an arithmetic result that
8
34+1
< 1
V
g++1
g
324 + g(+1 < 2,3 4
Then for another part derive an upper bound as
Exm E. I. we use the property [v 2 vI B2 VR( [k]] to
(w:(:) + Cmllt (((e))
+ + 1) 1g,,
Σ
f. A
[R(w:)(k]].
VI 32. VR(w;)
k=1
d
4c,
The + cmm) R(w.).
(A.3)
V1
B2
The first inequality is derived by triangle inequality and |c,mm / 1. The second inequality holds since [V((w:)(K [k]]
V- Tie (ww)) when Lag, = 1. Combining the results of (A.2..A.3
20n
and Lemma
C
we finally prove finish the proof.
Now, we are ready to prove Lemma 6.2
Proof of Lemma 6.2 We upper bound R(w++1) for f.rt > l by second-order Taylor expansion as
1 ( Tv'RRR + <(We+1 w.)) -w.)
R(W++1) R(w.) + (VR(w;), We+1 w.) + +
17

---

=[(w)) - (VR(we).
mi
V2R(wi + (00-+1-w/)) (n m
n
v
/vi
vv.
S R((ws) - 111 (1-11) 41
gtt1
/v((w))]
1
Byt
d
6c,
V + 3cm/lt) g((.)) + naa²B² max (((W)))((WE+))) ((
+ 1/1 VI B2
32+1
g
6o
I R((w)) 1178
1 1 (1-1//
g(w.) + m V (1- B2) -32-1)
-((:))
- 18411
a BB
30md d
+ n
g(wi).
2
32
The first inequality is from Lemma
A.3 and for the vector m.
Vv.
m
V
R
w))
m
|2: 1| S a²B² G(w)
Vv
by Lemma C.2 and Lemma 6.5 and g ((w, <(wi+1 wi)) S max (g(w)). ((we+1))
} from convexity of (w)). The last inequality is from g(we+1) I eaBne S eaBro by Lemma C.S and G(w.)
(g(w,) & (VR(w:)ll by Lemma A.1
A.5 Proof of Lemma 6.3
Proof of Lemma
6.3 By Lemma 6.2 and Lemma C.2 we have
((W++1) 2 R(w)) (1 (1-7m- Mp
g(w:)
+ (Crmm + nº C2d + of (2d)
g(w.)
R(we)
R(w.).
((w))
I R(ww)) exp (-ym-
+ CCrmost/2 C2d (n mn))
R(w:)
ta+1
2og2 exp (-7
R(w=)
((w,)
+ C2d
Σ T=to
m7
+
?? + Ciymo
VBI
T=
t=
(A.4)
for all t 2 tg- By Lemma C.4
we can derive that (We, nz) 2 0 for all E [n] and 2 to. Then n
we have e- minee(s] 2.)
Tog2 max,e|n] E((we, 23)) S log (w.)) by Lemma C.3 Plugging this
result into (A.pp and taking log on both sides, we finish the proof for Lemma 6.3
A.6 Proof of Lemma 6.4
Before we prove Lemma 6.4 we first present and prove Lemma A.4 which will be used for proving Lemma 6.4
Lemma A.4. For Adam iterations defined 33. 3.4 with B1 s 32, for any to E N4, t to. and
all k E [d].
w.lk] Woo [k]]
<
7r
t=
(1 +
32 81
Σ 1--
87 10 17
+
(B2 31)(1
(1)
t-1
77
1-87-
1-81
Σ 21
(-T-1
7 88
7r
log( v- [1])
32
Σ Σ n7
1-
32
T=ta
1 77
1
(A.5)
18

---

Proof of Lemma A.4 If we consider implementing the Cauchy-Schwarrs inequality on the sum of the iterations, we can get,
[
[k[k] Wio [6]
T
V
[
t-t
81
3
fo+t
m
[k]] +
Σ
B (1 - (1- vR(W>->>([))
V-
[k]
r'=0
T-To
m2g 116/2 + Σ
B7 (1 - B1) VR( VR(W>--)1K/2)
[k]
r'm0
[T
10--0-11
Σ
3 (1 B1))
7/-
1-1
T7r
91 - 11
[k] +
T-to
Σ
1 1- 31 V
Vr-r
[k]
32v, -
Σ
1-1
1/-
[k]
1 B2
Vr [
r'=0
r=to
(A.6)
The inequality is by Cauchy-Schwartz inequality and the second equality is from
(1 B2)
VR((w-
[K]] - V2 -2
v,-
and
To
1-1 Σ nr (g5 +1 - 84 35-10-1)
t-1
Σ
Tr 8
10-10++1
Σ
B1)
Σ
nr--
T=to
For the first part (+) defined in A.6 we could re-arrange as,
1
(x)
T7r
8T +1 m 2A
[k]
(1 B1)) Vo[k] - B2 Vin 1 [k] + (B1 (22)
-r'=l
to 3 -1
V [k]
(1 (1-13) ++2)
$
[-1
T/r
89H
8y-1u t0 (3102_B2l
B2(11 16(1-80 31)
Veo )
+
1-31 1-1
Σ 1/
V=(k
1- B2
1 - .3 t=to
(1
B1) -32)
T-10
Vr-rr(ki [k]
Σ
Σ
-1
1 82
k-[k]
T=
T'=1
1 31
1-1
(1-
(31
-82)
1-1 r-to
V 7- [k]
<
Σ 17
Σ
9r
1 32 7=0
1-Be 32
Vr [k]
T= 1==1
1-1
B2 - 31
1-1 Σ
- (3)
B1)
77:11 gr' 1 V r-r² [k]
Σ 1F +
1/-
1- 82
1- B2
v [b
T= r'=1
[-1
82 31 1-1
Toto
Vr- [k] V= [k]
Σ
7 +
Σ 77
1- (1 - (1)))
B
1- 82
Σ
7F +
82 - 31
Σ
17
BT B8-10 +(1 11)
T-1o
B -1 (1- - B1)
T-4o
Σ
-1 V [k]
1- B2 7=00
v [k]
T=
7/=1
r'=l
32 31
T-
B -1 111 (1- Yr-ro [k]]
Σ 7/ +
Σ
1/r
8 to +
(1 -B))
Σ
1 82
v [k]
19

---

B2 31
1-1
T-L0
V--r v [k]] )t))
v, [k]
77 +
Σ 1/7
89- + (1 (1)
Σ
1 log
1 - 82
1=
T=t
r'=1
Σ
(-1
1/ +
82 - 31
Σ
1-1
10 +
- (
(1)
1-1
1/-
T- 10
Σ
99 -1
log(v=(1)) log(vo log(v~-~111))
1- B2 1=4
1 32
T=
7=1
r'=1
B2 31
t-1
Σ 7 +
17. to
1 82
(32 3:)(1 - 31)
t-1
1
ST
-
1-1 Σ
to
1/7
log(vr [kk))
1/7
B
log (og( 1k))
1- 82
B1
7 T=
r'=1
T'=T-T'
17 +
32 31
Σ
17:11
to
1 32
T=T0
T=to
+ (B2 B1)(1 (1)
(-1
1 - 18
(-1
7-1
Σ 7
log(v, [k])
Σ Σ
-5- -1
"--===-o((V-- [K])
7/-
1- 32
1 - 31
r=to
T=fo
r'=lo
1-1
82 - 31
Σ T=
1/ +
1
1 82
T=ta
(32 31)(1 -31)
1-1
1- 88 -
1-1
+
log (og(v=(1:)=
Σ log(v,-115 (k:)
Σ
n-
1-3p
1 - 31
r=to
r=
[-1
82 - 31
1-1
Σ r=
7/ +
Σ
17,99
17-37-1
to
1 - B2 7=4
+ (32 31)(1
31)
Σ
t-1
1-
87-
t-r-1
Σ
-11) log(v,16)) [k]) (A.7)
7/r
1- 32
31
Plugging
A.7 7
into A.6
then we derive the result of A.5
Now we are ready to prove Lemma 6.4
Proof of Lemma 6.4 Considering the last two terms on the RHS of (A.7). for the second term, can upper-bound it as,
B2 B1
t-1
to < M/. (B2 B1)
Σ
32
(1 - B1) - -82)
-=to
since 17, is decreasing. Let C3
cg in statement of Lemma A.4 Then for the third term, by
Lemma 6.1 and our condition R(w,)= < /B*+Com0 we have
velk & (R(w)) + e. - ((w))² < (B² + Cs7)) R(w,)² <
for all & E [d], which implies that log(v.(k)) < 0 for all L > 40- On the other hand,
lb)( 2 l0g(35(1 - 32) VR [1}3) 2 t log 32 - log(1 - (82) + log P,
and
1 - 3T
6---1
1 - 3 to
b-r-1
1/7 3 to
1/7 1 31
Σ
2 1//
Σ
-1
3
3
Combining these results, we can upper-bound the third term as,
(32 - 31)(1 B1) 1- 32
Σ
1- 1-
t-v-1
8/-11 log(v, (k))
1r
31
r=
20

---

B2 81 1-1
Σ
1 10 (- log B2 log(11 - F2) log p)
1 B2 T=to
n/ (32 - 31)
1o
31 ) lolog
log B2) - log(1 - B2) - log
(1 Bi) (2)
Plugging these results into AA.5) with Bernoulli inequality, we have,
nho (B2 B1)
[wr[k]] < Wro [k]]+
Σ
(10 T- B1 (- log 32) log(1 -B2) -log p
7
2(1 -31)(1 - -32)
+
to
1/ + 11o (32 - B1)
(100
1 B1 )
1
(-log log 32) - log(1 - B2) - -log p+1
2(1 - B1)(1 - 82)
7=to
r=0
to
t--1
Mr
7/ + Conoto
Σ T=to
71 + Co
7
where Cs and C. are constants only depending on 31. 32 and B. The second inequality is from triangle inequality [we,[k]] and 6.55 The third inequality is from our condition to -log p and the last inequality is because is decreasing. Since the preceding result holds for all k E [d]. it also holds for |w/|ooo, which finishes the proof.
B
Complete Proof for Theorem 4.5 and Calculation Details for Corollary 4.7
B.1 Complete Proof for Theorem 4.5
Proof of Theorem 4.3 For Ci,Cs defined in Lemma 6.2 it's trivial that when is large
have the following inequalities hold:(i). < :ट, (ii..): I min { 3 } We use
t2 t2 31, B2. 7, B) to denote the first time that all the preceding inequalities hold after I = t (B, 82, B) in Assumption 4.4. Plugging all aforementioned inequality conditions into Lemma 6.2 we can derive that for all 12,
Te? g(w.).
R(w(41) R(w))
(B.1)
Therefore we prove that R(w++1) < R(w.) for all t 2 t2. For further proof, we separately consider È = Lopp and Llog.
When l = fexps by definition we have ((w:) R(w.). Therefore, for all / 2 l2, B.1 can be re-written
R(W++1) < ) R(w,) < R(w,) e - S RR(w,))... ) >bi dr
2
Although lexp not Lipschitz continuous over R. we have
R(w:,) S R(wo) exp
|xssh//wa woll < R(wo))-o exp (BB Σ
1/7
by Lemma 6.5 and triangle inequality.
Letting Ro min log2
and to
/B2+22
B
(n, d, B1, 32, B, t1, wo) be the first time be the first time such that E Er= Tr log R(we) log Rs and to 2 log p. By such definition of to. derive that for all t 2 to. 7
2aB E(2-1 7/r
7
E -0
R(w))= < R( R(Wr,)
Ro -
Since to satisfies all the requirements in Lemma 6.3 and Lemma 6.4 we can finally derive that
(Wt, De xx) || w, 1loo
7o Σ to o
1/ + Czdl Σ 7
Et-1 ni
+ Ca
min EE
7
Σt=1 71 + Co 50 ?
21

---

Elo 1/7 + - 1//
S 0
2r 7/
since the decay learning rate 7) 0 by Assumption 4.3 and C3, C4 and Cs are constants solely depending on 31, $2 and B.
When e flog. by taking a telescoping sum on the result of B.I.. we obtain y Er=t, 77, (7. - 2R( (R()) for any t 2 12- Since blog is 1-Lipschitz.comnieee continuous, we can derive that R(w,,) S R(wo) + aB Di= Vr. Letting Ro min 1og
and lo (n, d, 81, B2, 7, B, (1, wo) be the c200000
B
first time such that Et Thr
+
21 - and to - -log p. then we can conclude that
7:8
2R (x2))
Ro 2R(wo) + 20x 2r= 1/r < 2
min g(w+) < rE(t2uto)
Σm 1/7
E 1/7
Let 7' argmin ((tadtal (wr)), then we obtain that (z,, Wy') 2 for all i [r|] by Lemma C.4 Moreover, by Lemma and the monotonicity of (ww,) derived in (B.T). we can conclude that Ro for all t > to. Similarly, the inequality R(w,) < Ro also
R(w:) < R(w,))
implics (.. w.) 2 0 for all > to by Lemma C.4 and correspondingly R(w,) S 2g(ww) by
Lemma
Then for all t 2 tor we can re-write (B.I as
R(w.) S R (Ww--1)) - 7 g(ws)) S
Mh-1 (1- (R(w-1)
2
R((ww)
S R((wo)) . - ot S Ro. - -2 1T,
By this result and Lemma C.7
we have
((w)) R( w
nR((ss) 2
21
RRo Et=t
21
E dr
(B.2)
2
Since to satisfies all the requirements in Lemma 6.3 and Lemma Lemma 6.4 and (B.2) and finally derive that
6.4 we can combine Lemma
6.3
7C E.zo + Czd
Σ T + Er=th 1/² + C4 + Σi The
72
(We, Me x.) |
min :E|m]
- <
Ei + Co Ete-1 1/7
Erio 1/ + d Di 11 + Et T/E Direno 7/
Σ+=
since the decay learning rate π) + by Assumption 4.3 and C3, C4 and Cg are constants solely depending on 31. B2 and B.
B.2 Calculation Details for Corollary 4.7
In this section, we use the notation C1 C2, Cs.... to denote constants solely depending on 31, 32 and B. While may seem an abuse of notation as these symbols could be different from Section or denote distinct constants across different formulas, we assert that their exact values are immaterial for our analysis. Therefore, we opt for this shorthand notation for the sake of brevity and clarity, without concern for the precise numerical values of these constants in each instance.
For given 7) = (++2) 2)= with a E (0, 1), recall the definition of tz in Appendix B.1 be the first time such that (1) < 6CT (ii).m+ I min { (36Č34) 60ga } We can derive that
2 log G + log Ci (36Gd22 1 6CO2d = Cyd=. 72
1/ = max
log 3
We consider the following four cases,
22

---

If l = feep and a E (0, recall in Appendix B.1 the definition for to when & = lexp is the first time such that Σ 7 2 Σ 7 Zog R(wa)- log Ro and to 2 loog p. by simple approximation from integral of to, we can derive that,
S Cjda + C2 log - + C3llog R(wo)] C4 Cog(((/p))
Similarly, we can also derive
Σ "r S 7=0
City
S C2d 20 m)
+ C3 log n + C4 log R(wo) + Cc/log(1//p]]
When a > 3:
2 E= B is bounded by some constant, Σ 77 = -(t and 2(1-a) < 1,
therefore conclude that,
o0d d log n + log R(wo) + [log(1/p)]
zi) 3 1
min iE(m)
exp
tl-a
When a = 2 3.
similarly we have
1-1 of Ollog t) and 4-1 1/, = O(t!/3), then we conclude
that
Zi)
logt + logn + log R(wo) + [log(1/)))/3
min iE
00
[
EXP
11000
t//
When a < 3. similarly we have 2i1 1) = 0 and E = O(t2-9). Under this sub-case, we could always find new to 2 to such that besides the preceding condition for to, we اسااا
also have d to /ll3a/22 = log n, log R(wo), [log(1 - p)] p)) Letting this new ty to be the la in our statement of Corollary 4.7 then we conclude that,
Zi)
d
30
201 o)
+ log n + log R(w) + [log(1/p)]
min 1E
50
S
Exp
fl-o
1a/2
20
l fexp and a 1, then by the definition of to and integral of 6-1, we obtain that,
log to s C₁ log d + C2 log + log R(wo) + C4 log log(L/p).
Similarly, we can also derive
S C1 log d + C2 logn + C3s log R(wo) + log (1/p).
nr
Since E1=1 = Ollog t) and Er= 1/ 3 is bounded, we obtain that,
exp
zi)
d log + log R(wo) + log log(1/p) log
min iE(n)
f
0
w
If f = blog and (0,1), firstly we upper bound the last term Dt ThE
I'rr 7/4 as
Σ B -3 Ei
<
7ilo 11--a
Σ (T 2)
12)--
- -
Therefore, Et to THE Er is always bounded by a constant. The only difference between Elog, and Lexp how to determine the value of to. For liogs the formula for to is the first time such and log(1/p). Similar the preceding process,
that 1'o-1 7/ could derive that
4R(wo) + 4aB E
Roo
to H Cnn'd di + [(wo)) + C3 log(1/p).
23

---

and
Th S Cind 201-a + C2nR(wo) + Cc[log(1/p]]
0
When 3.
Ex 1 is bounded by some constant, Σ= fr O((t-a) and 2(1-a) S
therefore we conclude that
z,)
7 50 d nd 21-a)
nnR(wo) + [log(1/p)1=0
min [E(n]
log
11-0
00
When a similarly have Σr=to ? that
O t) and E 7/- O then conclude
Log
Z5)
d logt + nd + nR(ww)
min (E
50
lox
0o
11/3
When < 5. similarly we have Σ
10 17 - and Er 4 O(t Under this
setting, we could always find new to 2 ty such that besides the preceding condition for to. we also have d to f1-30/2, max(nd the to in our statement of Corollary 4.7 then we conclude that,
log R(wo), [log(1 -)]²-a}. Letting this new to to be
log wy [
nd 211-al
+ nR(w))) + [log(1 (gg(1/))]=~0
d
min sE(n
50
Jog
100
t
la/2
Er=to De EE 7o as
l flog and a 1, firstly we upper bound the last term
1-1
Σ
The ii n & (fo + 1)7741
7= (T (++1)1+7/4 S 227/11
4
which implies Σ e Ei n/' is also a constant. Then by the definition of to and integral of 111 we obtain that
log S Cin log + CanR(wo)) + C3 log log(1 (p)).
and similarly
Σ
Sin + C2nR((w)) C3 log (1p)
Since Σt=1 7/r
3 Olog t) and Ei=t n/ is bounded, obtain that
r-1
(
log z,)
( d n log d + nR(wo) + log log(1/p)
min kE(p]
0
log 100
log
C Technical Lemmas
C.1 Lemma for Assumption 4.4
Lemma C.1. Assumption 4.4 holds for both small fixed learning rate 7) = 17 S
1-8
and decay
2c1
learning rate пe (t 2) with (0, 1].
Proof of Lemma C.1 Firstly, we prove it for learning rate ?) 1) S constant, then we have,
1-2 2c,
which is a small fixed
Σ (cITT)*
1
Σ 8 ( Ete We-r -1)
Σg Br (6
-c
T=0
0=0
k=1
24

---

(1117) k
(c17)* &
3
Σ
3r 8t th
k!
k!
T=0
k=1
k=1
T=0
1
C17 B
k
201
- (1 3)2
k=1
The penultimate inequality holds because 0 S So B d = [- (=g I (1-8)8+1-
kd
k!
Therefore, we prove that Assumption 4.4 holds for t E N4, when 7/t = = S L-B Next, we consider the case where decay learning rate ?) (++2)a with E (0, 1), and similarly, we have,
2er
J Tt- + +20
T
dr
(t- T-T' + 222
7'=1
(1+1)) (1-
1
T+ (t+ + 1) at - +1)= -(t 1)a T + 1)
1 a
(++ + (t (T-T+ 1)a
2 T
(1 a) 11+
By this result, we can similarly obtain that for 1 2
dei
(1-3)<1--0)
8 ( Exen me-r -1)
S
B
e
2
1) =
20 T
k $1
a) + 1)o0
k!
0=
-=0
T=0
k=1
00
8
20
1
20
k
<
8r
Σ
(1 - a)(t + 1)aa
k!
(1 - a) + 1)0
k! r=0
7=0
k=
km
1
8
201
k
1-
3
(1 - B) - a) + 11/a
k=1
4ei
1
Sc1 1/--
<
(1 3) a)
(t+ 1)a
(1 3) - a)
Therefore, we prove that Assumption 4.4 holds for t > (1- when 1)+ (++2)= Finally
40
consider the case where the decay learning rate ne
1 and similarly, we have Σx. Me-T'
4+2
Er J hT 2 dr' loo(1 Ft1) ). By this result, obtain that
[al -1)
Σ B (e 11) -
Σ 8r
(1
==0
[c]
[c]]
T
3
(C.I)
k
7=0
Because [ci] and (fx)) are both absolute constant, it suffices to show that Σt= ca for all > t and & 2 where f1, C2 are both constants, Actually, we could split the summation 142 of into two parts as
3r
<
B
T
3r
T
b
3r
t
1-
+
t- +1
T=0
T=0
1
111
25

---

For the first part, we have
L
2
k
2² 1
Σ B
8T <
(1 - 3)++1 1
For the second part, could find constant 8 t1 (c1, 3) such that tlc11+2 1
(1)
for all f 2 t
since 1 > 1. Then for all 2 11, derive that
Σ B (T +=111+1
b S S
Σ
1 7 B - 7
r=1
The last inequality is by our condition plugging it into CC.Ip we finally get
2 and h - [ca Combining these two results and
([ai]) 2
k: ) 2 [all
Σ T=0
B (c - 1) S lall
(1- +1) 1
max
kE([ei]]
2 [E[[c]]]
max
[[c]]
k )) ( s/
(1-
(1 3) 1)(a+++111111111 +I +1) T
for all / 2 4, which completes the proof.
C.2 Propertics for Logistic and Exponential Loss Function
Lemma C.2. For e E (Lexps (log) and any z I. (z) S 1e(()) S ((z). For any 0, (z) S Mlog (z)l-
Proof of Lemma C.2
For E = Lexp. ((xp(=)] = (xxp(2) = Lexp (2) = e For l = Blog. we e²
calculate the derivatives fog (z) Ite=
I and flog (2) (I+e=)2
Notice that
lim (og(z)= = lim |l/g(2)] =0 ++000
ottoo
and
1
(z) 1 S 2+
(2) (1(o)(())))
- te=
Therefore we derive that li (z) S (()og())) s (1ng(2).
Lemma C.3. For any 2 O, (x)( (x)e())]
2 1 and (ina(t)
2 loo 2.
(x) (x)
2 (epp(z)
Proof of Lemma C For 2 0, it holds that
2
2
B (2) S leep (2) 2
<
22 (2)l.
1 e
The second result holds because (x)(x) (0, 1] for 2 2 O.
log(1+e")) is decreasing function for e= and e= (2)
Lemma C.4. For E E (Foxps bog J. either g(w) S i E [n).
I R(w) <
1og2 implies (w, 2,) > 0 for all
2n
Proof of Lemma C.4 If S 2 have (e((w, zi)) S nG(w) S. Then by monotonicity of
[e(()) we have (w, 2,) 2 O. Similarly if R(w) < log2 we also have 8((w, 2:)) S nR(w) S log 2.
Then by monotonicity of E(-) we have (w, z.) 0.
Lemma C.5. For E E (Loxps blo and any 21, E R. we have
((1)
< -2-
(C.2)
((())
26

---

Proof of Lemma C.5 For l = expp
" (21)
1
= e -
S g -
8 exp (22)
the inequality is from lea
1 S ela)
For llog.
(0 (21)
E e²
S c E²1
e
Rug (22)
+ 6
+ c
Lemma C.6. For l (lexps flogt and any 21, 22, 23, 24 E 1R, we have ((()) (2z)
- (elii-esl - 1) + (elts-eal - + ( (clttos-0--u)1111
(C.3)
(22))(((z))
Proof of Lemma
C.6
For l Lexp.
Foxpl
L (2x)
22 - e (c
Peepl (22)
exp (24)
the inequality is from
lea
11 S clu)
- 1. For
BioR
Lion (21) (23)
(1 + -2 (1
+ E24
e² + e + 2 - - -
Mlo (22) (24)
e
E
1 + e t
e²l
c 220
2 - 6
+
c
e
e k
p - 1) + ((clks (cks-val +
(cl (clestes- -1)
$
Lemma C.7. For l flng, and any w E IRd, we have
g(we) nR(ww R(w)
2
Proof of Lemma C.7 Let ri Boo ((w, z.) log(1 + (w(wz))) and f(z) log ((w,z, 2;))
e-= then
s-i-ع f(1). Therefore for any given R(w), finding min G(w.)
1te- (w)j
e"i
equals the following optimization problem,
min E s.t. n
nR((). r. 2 0 for all E [m]
Since f(2) is an increasing function and the increasing rate would be slow increase since f=) < O, we can easily derive that the aforementioned optimization problem will take the minimum
(ww))) for some i [n] and rj 0 for all j # i. Therefore, can derive that,
g(w)) 1 1- 1 RRR(()
21 nR(()
R(w) nR(w)
2
by Taylor's expansion.
C.3 Auxiliary Results
The following result is the classic Stolz-Cesäre theorem.
Theorem C.8 (Stolz-Cesâro theorem). Let Jan]n21, (bm)a2 be two sequences of real numbers. Assume that (b, is a strictly monotone and divergent sequence (i.e. strictly increasing and approaching +oo, or strictly decreasing and approaching -c) and the following limit exists:
lim ax+1 an
b bn
Then it holds that
lim an
l. 20000 bn
27

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction clearly outline the primary results and contribu- tions of the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We have discussed the limitation of this work in the conclusion and future work section.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-speciiiitiinn asymptotic approximations only holding locally). ). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
28

---

Answer: [Yes]
Justification: In Section 4 we have clearly stated all the assumptions that are necessary for our theorem results.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proof' in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: We have provided the complete configuration the experiments. Since the experiments all on synthetic data, the configuration is simple to explain.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
29

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [No]
Justification: This paper focuses on theoretical analysis of the standard optimization al- gorithm Adam. While we include some simulation results, they are very simple and are irrelevant to the key theoretical contributions of this paper.
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co cc/
ssmiiiiiiiicc for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to to reproduce the results. See the NeurlPS code and data submission guidelines (https craips.cc/uublicee gww.//uwgeeeeeegggeee www.eddeeeeodebmmmiccce ssiicyolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended to paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We have provided all the experiment details. The experiments are on synthetic data and the setup is simple.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
Justification: This paper studies optimization problems and there is statistical significance results to report.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
30

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [No]
Justification: We only present very simple simulation results and computational resources are not the focus.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: h/tp::///eeups/eeeeeeeeee httc///ubccctthccccueeeeeellleee
Answer: [Yes]
Justification: The research results align with the ethical principles outlined NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative socictal impacts of the work performed?
Answer: [No]
This paper is theoretical work that has no direct social impact. We would like to emphasize that, although the topic is related to "implicit bias", it a pure thcoretical terminology and has nothing to do with social bias.
Justification:
Guidelines:
The answer NA means that there is no societal impact of the work performed.
31

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: This paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
32

---

If assets are released, the license, copyright information, and terms of use in the thcode has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
latasets.paperssit
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the asshts?
Answer: [NA]
Justification: This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moode as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: This paper does not involve human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
33

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
34


Reviews:
[{"review_id": "GvQmgodRaD", "reviewer": "Reviewer_qQ6s", "summary": "This paper studies the implicit bias of the Adam optimizer for logistic regression on linearly separable data. The authors prove that Adam converges to the linear classifier with the maximum $\\ell_\\infty$-margin. This result contrasts with the classical results on (stochastic) gradient descent (with or without momentum), which converge to the maximum $\\ell_2$-margin solution.", "questions": "- Does Theorem 4.5 imply that Adam (with a learning rate $\\eta_t = (t+2)^{-a}$, $a<1$) reduces loss faster than GD (Adam: $O(e^{-\\gamma t^{1-a} / 4(1-a)})$ vs. GD: $O(1/t)$)? It would be great if the authors could provide a detailed comparison of the convergence rates of loss between Adam and (S)GD with/without momentum.\n- Is $\\beta_1 \\le \\beta_2$ a necessary condition? What happens if we use Adam with $\\beta_1 > \\beta_2$?\n- Assumption 4.4 seems to be a non-standard assumption. Is this assumption a necessary condition? Can you explain why such an assumption is needed?", "limitations": "The paper discusses its limitations and future directions, including the extension of the results to homogeneous neural networks and the analysis of stochastic Adam instead of full-batch Adam. I think both directions are promising avenues for future research.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "- The authors theoretically study a popular yet not well-understood optimization method, Adam, in the context of a well-studied classical problem: logistic regression on linearly separable data. This offers a solid and insightful contribution to understanding Adam. In particular, distinguishing Adam from (S)GD with/without momentum on this classical problem is a very interesting result.\n- The technical contributions are also of independent interest, as they prove the results for Adam without relying on the stability constant (which is closer to practice) and use mild assumptions.\n- The paper is well-written and easy to follow. The proof sketch provides a clear and comprehensive overview of the proof of the main theorem.", "weaknesses": "There are no major concerns about this paper. Below are minor comments and some areas for improvement:\n- The paper does not provide an intuition behind why Adam achieves the maximum $\\ell_\\infty$-margin solution, in contrast to GD which achieves the maximum $\\ell_2$-margin solution. It would be great if the authors could offer insights on how the $\\ell_\\infty$-margin arises instead of the $\\ell_2$-margin, for example, through a warm-up analysis with SignGD ($\\beta_1=\\beta_2=0$) or RMSProp ($\\beta_1=0$). One way to provide an intuition is as follows: Gunasekar et al. (2018) proved that steepest descent converges to the max-margin solution, implying that SignGD (steepest descent w.r.t. $\\ell_\\infty$-norm) converges to the maximum $\\ell_\\infty$-margin solution. Since SignGD is known to be a good proxy for Adam, this may offer an insight into why Adam converges to the maximum $\\ell_\\infty$-margin solution.\n- The authors claim that the bounds in Corollary 4.7 are derived under worst-case scenarios and argue that this is why, in practice, we often observe margins converging faster than the bounds in the corollary. However, this statement lacks supporting evidence. The paper should prove that the rate of convergence is tight. Otherwise, the observed faster convergence of margins in experiments might simply indicate that the bound is not tight enough.\n- Some sentences, including those in the abstract, use the term \"convergence\" unclearly. For example, in the abstract, \"this convergence occurs within polynomial time\" does not indicate the objective (the normalized $\\ell_\\infty$-margin in this case) of convergence. This could be confused with other notions of convergence, such as convergence in direction (i.e., $\\frac{w_t}{\\lVert w_t \\rVert} \\to \\frac{w^*}{\\lVert w^* \\rVert}$).\n- (page 6, line 183) According to the paper, the normalized $\\ell_2$-margin converges at a speed of $O(\\log \\log t / \\log t)$ when using GD. However, this should be corrected to $O(1 / \\log t)$. According to Soudry et al. (2018), the normalized weight vector converges to the maximum $\\ell_2$-margin vector \"in direction\" with a convergence rate of $O(\\log \\log t / \\log t)$, i.e., $\\lVert \\frac{w_t}{\\lVert w_t \\rVert} - \\frac{w^*}{\\lVert w^* \\rVert}\\rVert = O(\\log \\log t / \\log t)$. However, the normalized $\\ell_2$-margin converges at the speed of $O(1/\\log t)$, i.e., $|\\min \\frac{\\langle w_t, y_t \\cdot x_t \\rangle}{\\lVert w_t \\rVert} - \\frac{\\langle w^*, y_t \\cdot x_t \\rangle}{\\lVert w^* \\rVert} | = O(1/\\log t)$.\n- (page 1, line 25) Typo: reply on -> rely on\n\n---\n[Gunasekar et al. 2018] Characterizing Implicit Bias in Terms of Optimization Geometry, ICML 2018.\n\n[Soudry et al. 2018] The Implicit Bias of Gradient Descent on Separable Data, JMLR 2018.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your constructive feedback! We address your comments as follows:\n\n>**Q1**:\nThe paper does not provide an intuition why Adam and GD have different implicit biases. Relation to SignGD?\n\n**A1**:\nThanks for your suggestion. Several recent works have discussed that Adam and SignGD are closely related [2], and the implicit bias of SignGD shown by [1] can indeed provide valuable insights into the implicit bias of Adam. Some of our lemmas are also motivated by this intuition (Lemma 6.1 and Lemma A.3). We will add more discussions on this intuition in the revision.  However, we would also like to clarify that, despite the clear intuition, our proof for Adam is not a simple combination of existing techniques. For example, the proofs of Lemma 6.1 and Lemma A.3 are non-trivial, and in Lemma A.3, we have implemented a particularly careful analysis which enables us to cover general learning rates and general values of $\\beta_1,\\beta_2$. \n\n\n>**Q2**:\nThe authors claim that Corollary 4.7 is derived under the worst case and this is why in experiments we often observe margins converging faster than the bounds. This statement lacks supporting evidence. The paper should prove that the rate of convergence is tight.\n\n**A2**:\nCurrently, we do not have any lower bounds on the margin convergence rates. Due to the complicated optimization dynamics, establishing such lower bounds may be very challenging, and therefore it is difficult to prove that our rate of convergence is optimal. We will make it clear in the revision. We will also mention in the revision that establishing lower bounds on the margin convergence rates is an interesting future work direction. \n\nDespite not having matching lower bounds, our result demonstrates that the margin of the linear predictor converges in polynomial time for a general class of learning rates, which already significantly distinguishes Adam from gradient descent. Such polynomial convergence rates are also supported by our experiment results.\n\n>**Q3**:\nThe term \"convergence\" is used unclearly: objective convergence vs normalized margin convergence.\n\n**A3**:\nThanks for pointing out the unclear expressions. We will revise them. \n\n>**Q4**: on page 6, line 183, $\\ell_2$-margin convergence speed for GD should be $O(1/\\log t)$.\n\n**A4**:\nThanks for pointing it out. We will clarify it in the revision.\n\n>**Q5**:\n(page 1, line 25) Typo: reply on -> rely on\n\n**A5**:\nThanks for pointing out this typo. We will fix it.\n\n>**Q6**:\nDoes Theorem 4.5 imply that Adam reduces loss faster than GD? The authors should provide a detailed comparison.\n\n**A6**:\nThanks for your suggestion. You are right that our result shows an $O(e^{-\\frac{\\gamma t^{1-a}}{4(1-a)}})$ convergence rate of the training loss for Adam in logistic regression when the data are linearly separable, and this is faster than the $O(1/t)$ convergence rate of gradient descent. In the revision, we will comment on it, and give a detailed comparison of the convergence rates of loss between Adam and (S)GD with/without momentum.\n\n>**Q7**:\nIs $\\beta_1\\leq\\beta_2$ necessary? What happens if we use Adam with $\\beta_1>\\beta_2$?\n\n**A7**:\nYes, this condition $\\beta_1\\leq\\beta_2$ is necessary in our analysis. Such a condition ensures the stability of Adam. Under this condition, we can show that in each iteration of Adam, the update in each coordinate is bounded by a constant (Lemma 6.5). \n\nOn the other hand, without this condition, there exist extreme cases where Adam is unstable. For example, consider $\\beta_2=0$, $\\beta_1 > 0$, and suppose that there exists a coordinate index $k$ such that at iteration $t = 1$, the corresponding coordinate of the gradient is very close to zero, satisfying $0 \\leq \\nabla \\mathcal{R}(w_1)[k] \\leq \\beta_1(1-\\beta_1)\\rho / 10000 $. Then, by Assumption 4.2, we can see that $\\mathbf{m}_1[k] \\geq \\beta_1(1-\\beta_1)\\rho$, and hence \n$ \\mathbf{m}_1[k] / \\sqrt{\\mathbf{v}_1[k]} \\geq \\frac{ \\beta_1(1-\\beta_1)\\rho }{ \\beta_1(1-\\beta_1)\\rho / 10000 } = 10000 $. Clearly, $\\mathbf{m}_1[k] / \\sqrt{\\mathbf{v}_1[k]}$ can be arbitrarily large when $\\nabla \\mathcal{R}(w_1)[k]$ tends to zero. This implies that when $\\beta_2=0$, $\\beta_1 > 0$, there are cases where Adam is unstable. For general $\\beta_1,\\beta_2$ with $\\beta_1 > \\beta_2$, there are also certain extreme scenarios where Adam is unstable. \n\nWe would also like to point out that the condition $\\beta_1\\leq\\beta_2$ is a common condition considered in recent works studying Adam [3, 4, 5]. Besides, this condition aligns well with practice, where popular choices are ($\\beta_1=0.9, \\beta_2=0.99$), or ($\\beta_1=0.9, \\beta_2=0.999$). We will add more explanations in the revision.\n\n\n>**Q8**:\nAssumption 4.4 seems non-standard. Is it a necessary condition? Why is such an assumption needed?\n\n**A8**:\nAssumption 4.4 is necessary for our proof. Our proof of Lemma 6.1 relies on this assumption (line 482-line 484, line 485-line 488). As we commented below Assumption 4.4 and proved in Lemma C.1, this assumption is quite mild: it holds for fixed (small enough) learning rate, or decaying learning rates $\\eta_t = (t+2)^{-a}$ with $a \\in (0, 1]$. \n\n[1] Gunasekar, S., Lee, J., Soudry, D. and Srebro, N. (2018). Characterizing implicit bias in terms of optimization geometry. International Conference on Machine Learning.\n\n[2] Balles, L., Pedregosa, F., and Roux, N. L. (2020). The geometry of sign gradient descent. arXiv preprint arXiv:2002.08056.\n\n[3] Xie, S. and Li, Z. (2024). Implicit Bias of AdamW: $\\ell_\\infty $-Norm Constrained Optimization. International Conference on Machine Learning.\n\n[4] Hong, Y. and Lin, J. (2024). On Convergence of Adam for Stochastic Optimization under Relaxed Assumptions. arXiv preprint arXiv:2402.03982.\n\n[5] Zou, D., Cao, Y., Li, Y. and Gu, Q. (2023). Understanding the generalization of adam in learning neural networks with proper regularization. International Conference on Learning Representations.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "QMFLkYjMUQ", "reviewer": "Reviewer_dtxf", "summary": "In this work, the author studies the implicit bias of Adam optimizer for a single layer neural network on separable data. The author's work suggests that, compared to the implicit bias of gradient descent which is the max $ \\ell_2 $ margin solution, Adam solution converges to the maximum $ \\ell_\\infty $ margin solution. For this work, authors take both exponential and logistic loss and find that the convergence speed is on a polynomial order. \n\nIn order to confirm the results, the authors perform experiments on synthetic datasets for binary classification tasks and confirm Adam’s convergence to the $ \\ell_\\infty $ margin comparatively.", "questions": "1) Can the authors expand on how they arrive at the right side of inequality after line 292 using 6.1 ? Perhaps take me through the inequality step by step ? \n2) Can the author provide some comments regarding the independence of convergence in the case of $ a = \\frac{2}{3} $ from $ \\rho $ ? Is there some intuition with regards to the boundaries and case on $ a $ ?", "limitations": "None", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "The work is novel (to the best of my knowledge) and interesting as the study of implicit bias of Adam could have further implications in characterizing the difference in optimization behavior of Adam vs SGD in practical scenarios. The assumptions of the work have been clearly presented and seem reasonable. With regard to the $ \\epsilon $, while theoretical results are not provided, the authors include convincing experimental illustrations to convince me of the assumption. I also appreciate the well written proof sketch which helps convey the ideas", "weaknesses": "At the moment, I have some concerns with the paper which are more fit to be discussed as questions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your supportive comments! We address them in detail as follows:\n\n>**Q1**:\nCan the authors expand on how they arrive at the right side of inequality after line 292 using 6.1 ? Perhaps take me through the inequality step by step ?\n\n**A1**:\nThanks for your question. We would like to explain that there is a typo on line 292: \"for all $t > t_2$\" should be \"for all $t \\geq t_2$\".\n\nWe now present the detailed derivation as follows. Our target is to derive equation after line 292, which is \n\n$\\mathcal{R}(w_{t+1}) \\leq \\Big(1-\\frac{\\gamma\\eta_t}{2}\\Big)\\cdot \\mathcal{R}(w_{t})\\leq \\mathcal{R}(w_{t})\\cdot e^{-\\frac{\\gamma\\eta_t}{2}}\\leq \\mathcal{R}(w_{t_2})\\cdot e^{-\\frac{\\gamma\\sum_{\\tau=t_2}^{t}\\eta_\\tau}{2}}$.      $\\qquad$ (target)\n\n\nTo derive these results, we first recall that in equation (6.1), we have\n\n$\\mathcal{R}(w_{t+1})\\leq \\mathcal{R}(w_{t}) - \\frac{\\gamma\\eta_t}{2}\\mathcal{G}(w_t)$.\n\nNote that in the proof sketch, for simplicity we focus on the case of exponential loss, and for the exponential loss, it holds that $\\ell(x) = -\\ell'(x) =e^{-x}$. Therefore, by the definition of $\\mathcal{R}(w_{t})$ and $\\mathcal{G}(w_{t})$, we have $\\mathcal{R}(w_{t}) = \\mathcal{G}(w_{t})$. Replacing $\\mathcal{G}(w_{t})$ by $\\mathcal{R}(w_{t})$ in equation (6.1) then gives \n\n$\\mathcal{R}(w_{t+1})\\leq \\Big(1-\\frac{\\gamma\\eta_t}{2}\\Big)\\cdot \\mathcal{R}(w_{t})$. \n\nThis proves the first inequality in (target). To prove the second inequality in (target), we utilize the fact that $1-x\\leq e^{-x}$ holds for all $x$. Based on this, we have \n\n$1-\\frac{\\gamma\\eta_t}{2} \\leq e^{-\\frac{\\gamma\\eta_t}{2}}$,\n\nwhich further implies \n\n$\\Big(1-\\frac{\\gamma\\eta_t}{2}\\Big)\\cdot \\mathcal{R}(w_{t})\\leq \\mathcal{R}(w_{t})\\cdot e^{-\\frac{\\gamma\\eta_t}{2}}$.\n\nThis proves the second inequality in (target). So far, we have proved that \n\n$\\mathcal{R}(w_{t+1})\\leq \\mathcal{R}(w_{t})\\cdot e^{-\\frac{\\gamma\\eta_t}{2}}$\n\nfor all $t \\geq t_2$. Applying this result recursively gives \n\n$\\mathcal{R}(w_{t+1})\\leq \\mathcal{R}(w_{t})\\cdot e^{-\\frac{\\gamma\\eta_t}{2}}  \\leq \\mathcal{R}(w_{t-1})\\cdot e^{-\\frac{\\gamma\\eta_{t-1}+\\gamma\\eta_t}{2}}\\leq \\cdots \\leq \\mathcal{R}(w_{t_2})\\cdot e^{-\\frac{\\gamma\\sum_{\\tau=t_2}^{t}\\eta_\\tau}{2}}$.\n\nThis proves the last inequality in (target), and our derivation is finished. We will clarify the derivation of this result in the revision.\n\n\n>**Q2**:\nCan the author provide some comments regarding the independence of convergence in the case of $a=2/3$ from $\\rho$? \n\n**A2**:\nWe believe that the margin convergence rate in the case of $a=2/3$ does depend on $\\rho$, as the corresponding bound in Corollary 4.7 is \n$O(\\frac{d\\cdot\\log t + \\log n + \\log \\mathcal{R}(w_0) + [\\log(1/\\rho)]^{1/3}}{t^{1/3}})$ for exponential loss, and $O(\\frac{d\\cdot\\log t +nd+ n \\mathcal{R}(w_0) + [\\log(1/\\rho)]^{1/3}}{t^{1/3}})$ for logistic loss. Since we are considering the margin convergence rate as $t$ goes to infinity, these convergence rates can be simplified into $O(\\frac{d\\cdot\\log t}{t^{1/3}})$ for both exponential and logistic losses, because the term  $ d\\cdot \\log t$ can eventually dominate the other terms in the numerators. However, since $d\\cdot \\log t$ increases very slowly in $t$ and will require exponentially many iterations to dominate the other terms, in our result we still keep the other terms to make the bounds more concrete. \n\nWe guess that you are asking about why $\\rho$ does not appear in the margin convergence rates for the case $a<2/3$. In fact, this is because we have applied the simplifications discussed above. Let us take exponential loss as an example. When $a<2/3$, for exponential loss, we can prove (see the bound below line 603 in Appendix B.2.) a margin convergence rate of the order \n\n$O(\\frac{d t^{1-3a/2} + d^{\\frac{2(1-a)}{a}} + \\log n + \\log \\mathcal{R}(w_0) +  [\\log(1/\\rho)]^{1-a}}{t^{1-a}})$.\n\nIt is clear that the first term in the numerator $d t^{1-3a/2}$ is the only term that increases in $t$. Moreover, as $t$ increases, the term $d t^{1-3a/2}$  will dominate the other terms in the numerator in polynomial time, which leads to the following simplification:\n\n$O(\\frac{d t^{1-3a/2} + d^{\\frac{2(1-a)}{a}} + \\log n + \\log \\mathcal{R}(w_0) +  [\\log(1/\\rho)]^{1-a}}{t^{1-a}}) = O(\\frac{d t^{1-3a/2}}{t^{1-a}}) = O(\\frac{d}{t^{a/2}})$,\n\nThis gives the final bound in Corollary 4.7 for $a<2/3$, which does not depend on $\\rho$.\n\n>**Q3**: Is there some intuition with regards to the boundaries and case on $a$?\n\n**A3**:\nAgain, we explain it for the case of exponential loss. We note that Corollary 4.7 is derived based on Theorem 4.5, in which the upper bound for margin convergence is \n\n$O(\\frac{\\sum_{\\tau=0}^{t_0-1}\\eta_\\tau + d\\sum_{\\tau=t_0}^{t-1}\\eta_\\tau^{\\frac{3}{2}}}{\\sum_{\\tau=0}^{t-1}\\eta_\\tau})$. \n\nTherefore, to give more concrete convergence rates when $\\eta_t$ is specifically set as $(t+2)^{-a}$, we need to calculate $\\sum_{\\tau=0}^t \\eta_\\tau^{3/2}$ and $\\sum_{\\tau=0}^t \\eta_\\tau$ for different values of $a$. By properties of the series $\\{ (t+2)^{-a}  \\}$, this calculation can be separated into 4 cases as follows:\n\n1. When $0<a<\\frac{2}{3}$, $\\sum_{\\tau=0}^t \\eta_\\tau^{3/2}=\\sum_{\\tau=0}^t (\\tau+2)^{-3a/2} = \\Theta(t^{1-3a/2})$ and $\\sum_{\\tau=0}^t \\eta_\\tau=\\sum_{\\tau=0}^t \\tau^{-a} = \\Theta(t^{1-a})$. \n\n2. When $a=\\frac{2}{3}$, $\\sum_{\\tau=0}^t \\eta_\\tau^{3/2}=\\sum_{\\tau=0}^t \\tau^{-3a/2} = \\Theta(\\log t)$ and $\\sum_{\\tau=0}^t \\eta_\\tau=\\sum_{\\tau=0}^t \\tau^{-a} = \\Theta(t^{1-a})$. \n\n3. When $\\frac{2}{3}<a<1$, $\\sum_{\\tau=0}^t \\eta_\\tau^{3/2}=\\sum_{\\tau=0}^t \\tau^{-3a/2} = \\Theta(1)$ and $\\sum_{\\tau=0}^t \\eta_\\tau=\\sum_{\\tau=0}^t \\tau^{-a} = \\Theta(t^{1-a})$. \n\n4. When $a=1$, $\\sum_{\\tau=0}^t \\eta_\\tau^{3/2}=\\sum_{\\tau=0}^t \\tau^{-3a/2} = \\Theta(1)$ and $\\sum_{\\tau=0}^t \\eta_\\tau=\\sum_{\\tau=0}^t \\tau^{-a} = \\Theta(\\log t)$. \n\nThe calculations above lead to the boundary cases in Corollary 4.7.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "mtXPBn5MYb", "reviewer": "Reviewer_CKHd", "summary": "This paper examines the implicit bias of the Adam optimizer in the context of linear logistic regression, demonstrating that it converges to the maximum $\\ell_\\infty$-margin solution under certain mild conditions. The authors note that omitting the stability constant in Adam updates results in a different implicit bias than gradient descent, with or without momentum, which converges to the maximum $\\ell_2$-margin solution. They also explore various decreasing learning rates, showing that Adam's margin converges at a polynomial rate, which is faster than that of gradient descent. Additionally, they provide numerical experiments that support their findings.", "questions": "Can the authors comment more on why considering the stability constant $\\epsilon=0$ makes the setting more challenging? I understand the motivation in lines 105-107, but it is unclear what the challenge is since the accumulated second-order moments would be non-zero.", "limitations": "There is no potential negative impact of this work.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Understanding why Adam performs better than GD in several settings is an important problem and this work takes an important step towards this by showing that Adam has a different implicit bias than GD in the linear logistic regression setting.\n\n- Overall, the paper is well-written and easy to follow. The proof sketch in Section 6 is explained well.", "weaknesses": "- The paper does not present results for a fixed learning rate and only considers a set of decreasing learning rates.\n\n    - The discussion in lines 50-52 and after Corollary 4.7, comparing the rates of Adam and GD, should also comment on the convergence rates for GD with adaptive learning rates (e.g., normalized GD) which have been shown to converge faster (see [1] and related work) than GD.\n\n    - (Minor) In Assumption 4.3, ‘non-increasing’ should be ‘decreasing’ or ‘diminishing’.\n\n- The results in prior work on implicit bias of GD are global (hold for any initialization), whereas the results in this paper require an assumption on the initialization (Ass. 4.2). Based on the discussion following this assumption, it might be better to state an assumption on the data and then show that the condition on the initialization holds as a Lemma.\n\n- The paper does not comment on how optimal the obtained rates in Corollary 4.7 are.\n\n**References:**\n\n[1] Wang et al., Achieving Margin Maximization Exponentially Fast via Progressive Norm Rescaling, 2023.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your positive comments. Your comments and questions are addressed as follows.\n\n>**Q1**:\nThe paper does not present results for a fixed learning rate.\n\n**A1**:\nWhen considering fixed learning rate $\\eta_t=\\eta$ for some small $\\eta$, our analysis can imply that $\\lim_{t\\to \\infty}\\big|\\min\\frac{\\langle w_{t}, y_i\\cdot x_i\\rangle}{\\lVert w_t \\lVert_{\\infty}}-\\frac{\\langle w^*, y_i\\cdot x_i\\rangle}{\\lVert w^*\\lVert_{\\infty}} \\big|\\leq O(\\sqrt{\\eta})$. We will add a comment in the revision. \n\n\n>**Q2**:\nThe discussion after Corollary 4.7, comparing Adam and GD, should also compare Adam and GD with adaptive learning rates (see [1] and related work).\n\n**A2**:\nThanks for your suggestion and for pointing out the related work [1]. We will cite it and add more comprehensive comparisons and discussions in the revision. \n\n>**Q3**:\n (Minor) In Assumption 4.3, ‘non-increasing’ should be ‘decreasing’ or ‘diminishing’.\n\n**A3**:\nThanks for your suggestion. We will change \"non-increasing\" to \"decreasing\" in the revision. We will also add comments to clarify that we do not require the learning rates to be \"strictly decreasing”. \n\n>**Q4**:\nBased on the discussion following Assumption 4.2, it might be better to state an assumption on the data and then show that the condition on the initialization holds as a Lemma.\n\n**A4**:\nWe propose such an assumption because it is the most general version of assumption and it can cover various different settings. For example, we expect that the current version of Assumption 4.2 covers the following two cases:\n\n- Case 1 (fixed $w_0$, random data): consider an arbitrary fixed vector $w_0\\in \\mathbb{R}^d$. Then as long as the training data inputs $\\mathbf{x}_1,\\ldots, \\mathbf{x}_n$ is sampled from any continuous and non-degenerate distribution, $\\nabla \\mathcal{R}(w_0)[k] \\neq 0$ holds with probability $1$. \n\n- Case 2 (fixed data, random $w_0$): consider any fixed training data inputs $\\mathbf{x}_1,\\ldots, \\mathbf{x}_n$ satisfying that the matrix $ [ \\mathbf{x}_1,\\ldots, \\mathbf{x}_n ] $ has no all-zero row. Then as long as $w_0$ is initialized following a continuous and non-degenerate distribution,  $\\nabla \\mathcal{R}(w_0)[k] \\neq 0$ with probability $1$.\n\nTherefore, we feel that the current version of Assumption 4.2 may be more general.\n\nBesides, we would also like to clarify that assumptions on properties of initialization have been considered in various previous works studying implicit bias [2, 3, 4, 5]. In particular, [2] makes an assumption that is essentially the same as Assumption 4.2.\n\n\n>**Q5**:\nThe paper does not comment on how optimal the obtained rates in Corollary 4.7 are.\n\n**A5**:\nCurrently, we do not have any lower bounds on the margin convergence rates. Due to the complicated optimization dynamics, establishing such lower bounds may be very challenging, and therefore it is difficult to prove that our rate of convergence is optimal. We will add discussions in the revision, and will also mention in the revision that establishing lower bounds on the margin convergence rates is an interesting future work direction. \n\nDespite not having matching lower bounds, our result demonstrates that the margin of the linear predictor converges in polynomial time for a general class of learning rates, which already significantly distinguishes Adam from gradient descent. Such polynomial convergence rates are also supported by our experiment results.\n\n\n>**Q6**:\nWhy does considering the stability constant $\\epsilon=0$ make the setting more challenging? The accumulated second-order moments would be non-zero.\n\n**A6**:\nWhen studying Adam without $\\epsilon$, it is true that under Assumption 4.2, the gradient coordinates at initialization are non-zero and therefore the accumulated second-order moments would be non-zero throughout training. However, please note that the impact of the initial gradient values decays exponentially fast during training: in a worst case where for a certain coordinate $k$, $\\nabla \\mathcal{R}(w_t)[k] = 0$ for all $t > 0$, we have $\\mathbf{v}_t[k] = \\beta_2 (1-\\beta_2)^t \\cdot \\mathcal{R}(w_0)[k]^2$. Therefore, without a very careful analysis, the worst-case exponentially decaying $\\mathbf{v}_t[k]$ may significantly affect the stability of the algorithm, and may even impose a $\\exp( t )$ factor in the bounds of convergence rate, making the bounds vacuous. \n\nIn fact, many existing analyses of Adam and its variants rely on a non-zero stability constant $\\epsilon$, having a factor of $1/\\epsilon$ in their convergence bounds, e.g., [6] (see Theorem 4.3) and  [7] (see Corollary 1 and Remark 2). In comparison, in our work, we implement a very careful analysis (also utilizing the relatively simple problem setting of linear logistic regression) to avoid having such factors in the bounds.\n\n[1] Wang, M., Min, Z. and Wu, L. (2024). Achieving Margin Maximization Exponentially Fast via Progressive Norm Rescaling. International Conference on Machine Learning.\n\n[2] Xie, S. and Li, Z. (2024). Implicit Bias of AdamW: $\\ell_\\infty $-Norm Constrained Optimization. International Conference on Machine Learning.\n\n[3] Lyu, K. and Li, J. (2020). Gradient Descent Maximizes the Margin of Homogeneous Neural Networks. International Conference on Learning Representations.\n\n[4] Ji, Z. and Telgarsky, M. (2020). Directional convergence and alignment in deep learning. Advances in Neural Information Processing Systems.\n\n[5] Wang, B., Meng, Q., Chen, W. and Liu, T.Y. (2021). The Implicit Bias for Adaptive Optimization Algorithms on Homogeneous Neural Networks. International Conference on Machine Learning.\n\n[6] Zhou, D., Chen, J., Cao, Y., Yang, Z. and Gu, Q. (2024). On the Convergence of Adaptive Gradient Methods for Nonconvex Optimization. Transactions on Machine Learning Research.\n\n[7] Huang, F., Li, J. and Huang, H. (2021). SUPER-ADAM: Faster and Universal Framework of Adaptive Gradients. Advances in Neural Information Processing Systems.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "aHfkRN83Kq", "reviewer": "Reviewer_Gj1V", "summary": "The main focus of this paper is on the implicit bias of Adam for a single layer linear model which performs binary classification on separable data. In particular, assuming a zero stability constant $\\epsilon$, this paper reveals that Adam finds the solution that achieves maximum-$\\ell_\\infty$-margin and characterizes the convergence rate for different classes of learning rate. This implicit bias is different from the $\\ell_2$-norm minimization solution obtained by previous work which does not assume $\\epsilon = 0$.", "questions": "1. Could the authors explain the contradiction and connection with previous works? Is it possible to start with a non-zero $\\epsilon$ and let $\\epsilon=0$ be a special case? \n\n2. How will adding stochastic sampling noise affect the implicit bias?", "limitations": "I do not find a separate limitation section in the main part. In my view, removing the stability constant is a bit rough. This makes the approach presented in this paper fail to capture how the implicit bias of Adam changes for different values of stability constant.  \n\nThe societal impact is not applicable to this work as it focuses on theoretical parts of Adam.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This paper is clearly written and well-organized. It is easy and clear to follow the argument and motivation of this paper, e.g., the proof sketch makes it easy to follow the way how the theoretical conclusion is developed. In addition, to me, the introduction of the related works are comprehensive and clear. It also clearly summarizes the difference between this paper and related works.\n- The settings and results of this paper are new compared to previous works, i.e., previous works showed an $\\ell_2$-norm solution implicit bias of Adam on separable data while this paper reveals an $\\ell_{\\infty}$-norm implicit bias when the stability constant $\\epsilon$ is zero.", "weaknesses": "Despite the novelty of the theoretical claims, I still have several concerns, which I will discuss in the following.\n\n1. Removing the stability constant $\\epsilon$ makes the approach of this paper fails to characterize the influence of it, which, though being small, still has non-negligible effect, e.g., [1] observed that Adam with an $\\epsilon$ that is too small does not even converge in certain circumstances. Treating $\\epsilon$ as 0 seems a bit rough to me. \n\n    In addition, [2] showed that Adam minimizes the interpolation norm of gradients that depends on magnitudes of various hyper parameters including the stability constant $\\epsilon$ (although [2] did not specify the types of loss functions and model architectures). [1] claimed that Adam with nonzero $\\epsilon$ converges to $\\ell_2$-norm solution, which is also verified by extensive experiments. As a comparison, this paper showed that both Adam with $\\epsilon=0$ and with a non-negligible $\\epsilon$ do not converge to the aforementioned solutions (line 210). In this sense, it seems that the conclusion reached by this paper contradicts with those derived by [1, 2]. Therefore, in my view, it would be better to start with a non-zero $\\epsilon$ and let the case with $\\epsilon=0$ be a special case to better capture the effect of the $\\epsilon$ on the implicit bias.\n\n2. This paper only considers a simple setting: the model is only a one-layer linear model and there is no stochastic sampling noise which is typically necessary in practice. As a comparison, authors of [1] have already studied Adam on separable data for homogeneous models, which can cover the single layer model of the current work as a special case. Thus excluding the stochastic sampling noise in the current work is kind of unsatisfying to me since the model is already a simple one. In addition, I think that the authors of the current work should at least repeat the experiments conducted in [1] (such as those for homogeneous neural networks) to further support their theoretical claims, especially considering that the authors claimed in line 210 that their results are more accurate than those of [1].\n\n**Reference**\n\n[1] Wang et al. The implicit bias for adaptive optimization algorithms on homogeneous neural networks.\n\n[2] Cattaneo et al. On the Implicit Bias of Adam.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your support, and address your questions as follows.\n\n>**Q1**:\nAdam without $\\epsilon$ sometimes does not converge. Contradiction with [1, 2]? Study a non-zero $\\epsilon$ and let $\\epsilon=0$ be a special case?\n\n**A1**:\nOur goal is to study the implicit bias of Adam when the stability constant $\\epsilon$ is negligible. The differences between our result and [1,2,3] that consider a non-negligible $\\epsilon$ do not lead to any contradiction. Instead, these differences demonstrate that our work indeed provides novel and complementary insights into Adam. We address your detailed comments as follows:\n\n- We emphasize that Adam without $\\epsilon$ provably converges under our setting. Proving convergence even without $\\epsilon$ is a contribution of our work.\n\n- Our result does not contradict with [2]. By treating the correction term in the continuous-time approximation of Adam as a penalty, [2] gives an informal summary of the implicit bias of Adam without specifying the loss or model. In comparison, our work focuses on a specific setting, and provides a formal and rigorous analysis on the implicit bias of Adam with concrete convergence rates.\n\n- Our theory does not contradict with the theories in [1,3]. [1,3] prove that Adam with a non-negligible $\\epsilon$ has the implicit bias towards the maximum $\\ell_2$-margin. The intuition is that, after sufficiently many iterations, $\\nabla \\mathcal{R}(w_t)$ and $v_t$ will be very close to zero (much smaller than $\\epsilon$), and $\\frac{m_t}{\\sqrt{v_t} + \\epsilon} \\approx \\frac{1}{\\epsilon}m_t$, indicating that Adam with a non-negligible $\\epsilon$ will eventually be similar to GD with momentum. In comparison, we focus on the setting where $\\epsilon$ is negligible, and demonstrate that in this case, Adam will have a unique implicit bias towards the maximum $\\ell_\\infty$-margin. Therefore, our theoretical results do not contradict those in [1,3]. Instead, our paper and [1,3] can together provide a more comprehensive understanding of the implicit bias of Adam. \n\n- Our experiments do not contradict with the experiments in [1,3]. In our simulations, we run different algorithms for $10^6$ iterations, and Adam can typically reach training losses below $10^{-8}$, demonstrating that it is reasonable to stop the training there. Our experiments show that within $10^6$ iterations, Adam with $\\epsilon = 10^{-8}$ is indeed approaching the maximum $\\ell_\\infty$-margin. In comparison, in Figure 1 in [3], Adam and other algorithms are run for over $10^{14}$ iterations, where Adam with $\\epsilon$ can eventually approach the maximum $\\ell_2$-margin solution. Therefore, our paper focuses more on the practical stopping time, while [3] focuses more on the behavior of Adam after an extensively long training. Hence, our experiment results are complementary to [3], and there is no contradiction.\n\n- “Start with a non-zero $\\epsilon$ and let $\\epsilon=0$ be a special case” could be an interesting future direction, and we will discuss it in the revision. However, given that existing works [1,2,3] have studied the case with a non-zero $\\epsilon$, we believe that our current setting with $\\epsilon = 0$ helps us demonstrate our claim in the cleanest setting. \n\n>**Q2**:\nLinear model + full-batch Adam is simple compared with [1]. Consider stochastic sampling noise or homogeneous models?\n\n**A2**:\nThanks for your comment. Again, our work aims to study a relatively understudied scenario where $\\epsilon$ in Adam is negligible. This setting is complementary to the studies in [1,3], and therefore it is reasonable for us to start from the most classic setting to study implicit bias, which is solving linear logistic regression with full-batch algorithms [3,6].\n\nTo the best of our knowledge, existing works on the implicit bias of Adam or AdamW such as [1,3,6] mainly focus on the full batch setting. Extensions to stochastic Adam can possibly be done following the analysis in [5], where the implicit bias of full batch GD is extended to SGD. However, such an extension may be more challenging for Adam due to its complex form. This can be a future direction.\n\nExtensions to homogeneous networks are also an important future direction. However, since our goal is to study the implicit bias of Adam with a negligible $\\epsilon$, establishing concrete results in linear logistic regression is a reasonable starting point, and this clean and classic setting serves our purpose well in demonstrating the difference in the implicit bias of Adam when $\\epsilon$ is negligible.\n\n>**Q3**:\nLine 210 claims the results are more accurate than [1], so add experiments on homogeneous networks?\n\n**A3**:\nWe would like to clarify that around line 210, we do not compare our result with [1]. Instead, we are comparing with [3], which studies linear classification. We will revise our comments and highlight more on our purpose, which is to study a setting that is complementary to [1,3].\n\nWe have concerns that experiments of homogeneous models are out of the scope of our paper as we do not claim anything about homogeneous models. However, we have added some preliminary experiment results in the pdf rebuttal page.\n\n[1] Wang, B., Meng, Q., Chen, W. and Liu, T.-Y. (2021). The implicit bias for adaptive optimization algorithms on homogeneous neural networks. ICML.\n\n[2] Cattaneo, M.D., Klusowski, J.M. and Shigida, B. (2024). On the Implicit Bias of Adam. ICML.\n\n[3] Wang, B., Meng, Q., Zhang, H., Sun, R., Chen, W., Ma, Z.-M. and Liu, T.-Y. (2022).\nDoes momentum change the implicit regularization on separable data? NeurIPS.\n\n[4] Xie, S. and Li, Z. (2024). Implicit Bias of AdamW: $\\ell_\\infty $-Norm Constrained Optimization. ICML.\n\n[5] Nacson, M. S., Srebro, N. and Soudry, D. (2019). Stochastic gradient descent on separable data: Exact convergence with a fixed learning rate. AISTATS.\n\n[6] Soudry, D., Hoffer, E., Nacson, M. S., Gunasekar, S. and Srebro, N. (2018). The implicit\nbias of gradient descent on separable data. JMLR.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
Dear Reviewers,

We appreciate your supportive and constructive comments on our paper. We have addressed all your questions in detail in our individual responses to you. Here, as suggested by Reviewer Gj1V, we include a pdf page presenting some preliminary experiment results on training homogeneous neural networks. But we would also like to clarify that we do not aim to claim any conclusions about trianing neural networks -- our work is still focused on the simple and clean setting of linear classification.

We lookfoward to your further comments and suggestions, and we are happy to discuss any remaining questions in detail.

Best regards,

Authors

Meta-review: The paper presents a significant contribution to the understanding of Adam’s implicit bias, particularly in a setting where the stability constant is negligible. While there are some limitations due to the simplified setting and the exclusion of the stability constant, the paper’s novel theoretical insights and thorough analysis make it a valuable addition to the literature. The reviewers unanimously recommended to accept this paper. The authors should incorporate the feedbacks of reviewers into the camera-ready version.
Decision: Accept (poster)