The Implicit Bias of Adam on Separable Data

Authors: chenyang  zhang
difan  zou
yuan  cao
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 19:07:57

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.

Main paper: 
 introduction: 
 Adam [25] is one 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.It has been recently pointed out that the implicit bias [32, 40, 21] of an optimization algorithm is essential in understanding the performance of the algorithm in machine learning. In over-parameterized learning tasks where the training objective function may have infinitely many solutions, the implicit bias of an optimization algorithm characterizes how the algorithm prioritizes converging towards a specific optimum with particular structures and properties. Several recent works studied the implicit bias of Adam and other adaptive gradient methods. Specifically, [35] studied the implicit bias 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 a nonnegligible stability constant -when the gradient entries are minimized below the stability constant (which is by default 10 -8 in Adam), adaptive gradient methods will essentially behave like gradient descent. Therefore, it remains an open question how Adam will behave under the more practical regime where stability constant is 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 or stability constant, is usually considered a proxy of Adam in theoretical studies due to its ease of analysis. [14] studied the implicit bias of steepest descent with respect to different potentials and norms covering a variant of sign gradient descent, and demonstrated that sign gradient descent converges to the maximum ℓ ∞ -margin solution. However, this result for sign gradient descent cannot cover Adam, as the momentum terms in the update of Adam are crucial. Besides, a more recent work [50] studied the implicit bias of AdamW without considering the stability constant. They showed that, if the iterates of AdamW converge, then the limiting point must be a KKT point of an optimization problem with ℓ ∞ constraints. However, the analysis of AdamW 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 i , y i )} n i=1 ⊂ R d × {±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 } ∞ t=0 , {w t } ∞ t=0 be the sequence of learning rates and iterates of Adam respectively. Suppose that the data set {(x i , y i )} n i=1 is linearly separable, and that lim t→ η t = 0, ∞ t=0 η t = ∞. Then under certain conditions, it holds thatmin i∈[n] ⟨w t , y i • x i ⟩ ∥w t ∥ ∞ -γ ≤ O t-1 τ =0 η 3 2 τ + t-1 τ =0 η τ e -γ 4 τ -1 τ ′ =0 η τ ′ t-1 τ =0 η τ, (for logistic loss)min i∈[n] ⟨w t , y i • x i ⟩ ∥w t ∥ ∞ -γ ≤ O t-1 τ =0 η 3 2 τ t-1 τ =0 η τ ,(for exponential loss)where γ := max ∥w∥∞≤1 min i∈[n] ⟨w, y i • x i ⟩ is the maximum ℓ ∞ -margin on the training data set.Theorem 1.1 shows that, for a 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 ℓ ∞margin solution when solving linear classification problems. Our result distinguishes Adam from (stochastic) gradient descent with/without momentum, whose implicit bias is towards the maximum ℓ 2 -margin solution.• Our analysis of Adam covers a broad range of diminishing learning rate schedules. For η t = Θ(t -a ) with a ∈ (0, 1], our result demonstrates the following convergence rate:min i∈[n] ⟨w t , y i • x i ⟩ ∥w t ∥ ∞ -γ ≤            O t -a/2 , if a < 2/3; O t -1/3 log t , if a = 2/3; O t 1-a , if 2/3 < a < 1; O 1/ log t , if a = 1.Notably, when a < 1, the above rates indicate that the convergence towards the maximum ℓ ∞margin occurs in polynomial time. This further differentiates Adam from (stochastic) gradient descent with/without momentum in terms of the convergence speed.• Our result focuses on a particularly challenging setting where we ignore the "stability constant ϵ" in the Adam algorithm. In practice, the stability constant is by default set as ϵ = 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 {x n } and {y n }, we denote x n = O(y n ) if there exist some absolute constant C 1 > 0 and N > 0 such that |x n | ≤ C 1 |y n | for all n ≥ N . Similarly, we denote x n = Ω(y n )if there exist C 2 > 0 and N > 0 such that |x n | ≥ C 2 |y n | for all n > N . We say x n = Θ(y n ) ifx n = O(y n ) and x n = Ω(y n ) both holds. We use O(•), Ω(•), and Θ(•) to hide logarithmic factors in these notations respectively. Moreover, we denote x n = poly(y n ) if x n = O(y D n ) for some positive constant D, and x n = polylog(y n ) if x n = poly(log(y n )). For two scalars a and b, we denote a ∨ b = max{a, b} and a ∧ b = min{a, b}. For any n ∈ N + , we use [n] to denote the set {1, 2, • • • , n}. For any scalar c ∈ R, ⌈c⌉ denotes the smallest integer larger or equal to c and ⌊c⌋ denotes the largest integer smaller or equal to c. For a vector a ∈ R d , a[k] denote its k-th entry. Finally, e i ∈ R n denotes the i-th basis vector in R n . 
additional related work: 
 Theoretical analyses of Adam and its variants. There has been a 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 a new variant of Adam, the AMSGrad algorithm, which enjoys convergence guarantees in convex optimization. [54, 10, 17, 33, 53, 18] established optimization guarantees of Adam and its variants in non-convex optimization. [29, 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 compared it with GD under different learning tasks. [27, 4, 6, 3, 5] tried to explain the performance of Adam by studying the connections between Adam and sign gradient descent. [51] explored the optimization trajectories of Adam from the ℓ ∞ geometry.Implicit bias. Classic results [40, 21] demonstrated the iterates of GD will converge to the maximum ℓ 2 -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 a general class of optimization methods, containing mirror descent and steepest descent. [23] proposed a primal-dual analysis and derived a faster convergence rate with a 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 an arbitrarily large constant. [30, 22] showed that q-homogeneous neural network trained by GD will converge to a KKT point of maximum ℓ 2 -margin optimization problem. [8] established an implicit bias type result for the Lion [9] algorithm in its continuous-time form. There also exist numerous works studying the implicit bias for different problem setting, including matrix factorization models [16, 28, 2, 36] , squared loss models [38, 1, 24] , weight normalization and batch normalization [49, 7] , deep linear neural networks [15, 20] , two-layer neural networks [11, 34, 13, 42, 43, 26] .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 no 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 (e.g., independence assumptions, noiseless settings, model well-specification, 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 a few datasets or with a 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, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to 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 fairness. • 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 acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
problem settings: 
 We consider binary linear classification problems. Specifically, given n training data points {(x i , y i )} n i=1 where x i ∈ R d and y i ∈ {+1, -1}, we aim to find a coefficient vector w which minimizes the following empirical lossEQUATIONwhere ℓ(⟨w, y i • x i ⟩) is the loss function value on the data point (x i , y i ). In this paper, we consider ℓ ∈ {ℓ log , ℓ exp }, where ℓ log (z) = log(1 + e -z ) is the logistic loss function and ℓ exp (z) = e -z is the exponential loss function. We consider using Adam to minimize (3.1) . Denoting m -1 = v -1 = 0 ∈ R d and starting with initialization w 0 , Adam applies the following iterative formulas:EQUATIONEQUATIONEQUATIONwhere β 1 , β 2 ∈ [0, 1) are the hyperparameters of Adam, and the square (•) 2 , square root ( √ •) and division ( • • ) above all denote entry-wise calculations.Note that in practice, it is common to consider the variant w t+1 = w t -η t mt √ vt+ϵ , where an additional term ϵ ≈ 10 -8 is added in (3.4) to improve stability. However, in our analysis, we do not consider such a term ϵ. This is because in practice, one seldom run Adam until v t is around the same level as ϵ. 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, we will show that when ignoring ϵ, Adam has a unique implicit bias that is different from gradient descent.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
main results: 
 In this section, we present our main result on the implicit bias of Adam in linear classification problems. We first introduce several assumptions. Assumption 4.1. There exists w ∈ R d such that ⟨w,y i • x i ⟩ > 0 for all i ∈ [n].Assumption 4.1 is a standard assumption in the study of implicit bias of linear models [40, 14, 31, 21, 23, 45, 48] . It can be easily satisfied in the over-parameterized setting where d ≥ n. With the linear separability assumption, we can further define the maximum ℓ ∞ -margin:γ = max ∥w∥∞≤1 min i∈[n] ⟨w, y i • x i ⟩. (4.1)We also make the following assumption on the initialization w 0 . Assumption 4.2. The initialization w 0 of Adam satisfies that for all k ∈[d], ∇R(w 0 )[k] 2 ≥ ρ.Assumption 4.2 ensures that at every finite iteration, the entries of v t are strictly positive. We remark that this is a mild assumption: if x i , i ∈ [n] are generated from a continuous, non-degenerate distribution, then regardless of the choice of w 0 , ∇R(w 0 )[k] ̸ = 0 with probability 1. Moreover, ρ will only appear in our results in the form of log(1/ρ), and therefore, even if ρ is small, it will not significantly hurt the convergence rates. A similar assumption has also been considered in [50] . Assumption 4.3. {η t } ∞ t=1 are decreasing in t, and satisfy ∞ t=0 η t = ∞, lim t→∞ η t = 0. Assumption 4.3 is a mild and standard assumption of the learning rates {η t } ∞ t=0 that is commonly considered in the general optimization literature. It has also been considered in recent studies of Adam and its variants [12, 19, 50] . Assumption 4.4. For all β ∈ (0, 1) and c 1 > 0, there exist t 1 ∈ N + and c 2 > 0 that only depend on β, c 1 , such thatt τ =0 β τ e c1 τ τ ′ =1 η t-τ ′ -1 ≤ c 2 η t for all t ≥ t 1 .Although Assumption 4.4 seems non-trivial, we claim it is a fairly mild assumption. In fact, for both small fixed learning rate η t = η, and decay learning rate η t = (t + 2) -a with a ∈ (0, 1], Assumption 4.4 always hold. We formally prove this result in Lemma C. = t 0 (n, d, β 1 , β 2 , γ, B, ρ, w 0 ) such that • If ℓ = ℓ exp , then for all t ≥ t 0 , R(w t ) ≤ log 2 n • e -γ 2 t-1 τ =t 0ητ , and minEQUATIONmin i∈[n] ⟨w t , y i • x i ⟩ ∥w t ∥ ∞ -γ ≤ O t0-1 τ =0 η τ + d t-1 τ =t0 η 3 2 τ + t-1 τ =t0 η τ e -γ 4 τ -1 τ ′ =t 0 η τ ′ t-1 τ =0 η τ ,where we use O(•) to omit factors that only depend on β 1 , β 2 , γ, B.Theorem 4.5 implies that Adam can minimize the loss function to zero, and that the normalized ℓ ∞ -margin achieved by Adam will eventually converge to the maximum ℓ ∞ -margin 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 an exact formula for t 0 . However, it can be easily verified that R(w t ) ≤ O e -γt 1-a /4(1-a) when η t = (t + 2) -a with a < 1. This loss convergence rate of Adam is much faster than that of (stochastic) gradient descent (with momentum) given a fixed small learning rate, which is of order O(1/t) [40, 31, 45] . In addition, we havet 0 = poly[n, d, (1 -β 1 ) -1 , (1 -β 2 ) -1 , γ -1 , B, log(1/ρ), R(w 0 )] when η t = (t + 2) -a with a < 1, and we defer the derivation details to Appendix B.2. Regarding margin convergence, we will give a 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 ℓ 2 -margin [40, 31, 21] . Compared with existing works on the implicit bias of adaptive gradient methods [35, 45, 50] , our result demonstrates a 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 w t+1 = w t -η t mt √ vt+ϵ , then Adam will eventually be equivalent to gradient descent and will converge to the maximum ℓ 2 -margin solution. However, the analysis in [45] relies on a positive ϵ: their proof is based the fact that after a large number of iterations, the entries of v t will eventually be much smaller than ϵ, and the update of Adam will be similar to gradient descent with momentum. In our analysis, we are able to cover the setting where ϵ = 0, and our result demonstrates that studying the setting without ϵ is essential, as the implicit bias is completely different. In Section 5, we will demonstrate by experiments that our setting matches the practical observations better.As we have discussed, Theorem 4.5 implies the convergence of the normalized ℓ ∞ -margin of Adam iterates towards the maximum ℓ ∞ -margin. Since the results cover very general learning rates, the convergence rates are presented in rather complicated formats. However, based on the assumption that ∞ t=0 η t = ∞, lim t→∞ η t = 0, we can immediately conclude the following simplified result by the Stolz-Cesàro theorem (see Theorem C.8 in the appendix). Corollary 4.6. Under the same conditions in Theorem 4.5, it holds thatlim t→∞ min i∈[n] ⟨w t , y i • x i ⟩ ∥w t ∥ ∞ = max ∥w∥∞≤1 min i∈[n] ⟨w, y i • x i ⟩.If there exists a unique maximum ℓ ∞ -margin solution w * = argmax ∥w∥∞≤1 min i∈[n] ⟨w, x i ⟩, then we have lim t→∞ wt ∥wt∥∞ = w * .We can also investigate the convergence rates of the ℓ ∞ -margin with specific learning rates. The results are summarized in the following Corollary.Corollary 4.7. Consider η t = (t + 2) -a with a ∈ (0, 1]. Denote by w exp t and w log t the iterates of Adam for ℓ = ℓ exp and ℓ = ℓ log respectively. Suppose that β 1 ≤ β 2 and Adam starts with initialization w 0 . Let B := max i∈[n] ∥x i ∥ 1 . Then under Assumptions 4.1 and 4.2, there exists t 0 = t 0 (n, d, β 1 , β 2 , γ, B, ρ, w 0 ) such that for all t ≥ t 0 , the following results hold:• If a < 2 3 , min i∈[n] ⟨w exp t , y i • x i ⟩ ∥w exp t ∥ ∞ -γ , min i∈[n] ⟨w log t , y i • x i ⟩ ∥w log t ∥ ∞ -γ ≤ O d t a/2 . • If a = 2 3 , min i∈[n] ⟨w exp t , y i • x i ⟩ ∥w exp t ∥ ∞ -γ ≤ O d • log t + log n + log R(w 0 ) + [log(1/ρ)] 1/3 t 1/3 , min i∈[n] ⟨w log t , y i • x i ⟩ ∥w log t ∥ ∞ -γ ≤ O d • log t + nd + nR(w 0 ) + [log(1/ρ)] 1/3 t 1/3 . • If 2 3 < a < 1, min i∈[n] ⟨w exp t , y i • x i ⟩ ∥w exp t ∥ ∞ -γ ≤ O d + log n + log R(w 0 ) + [log(1/ρ)] 1-a t 1-a , min i∈[n] ⟨w log t , y i • x i ⟩ ∥w log t ∥ ∞ -γ ≤ O d + nd 2(1-a) a + nR(w 0 ) + [log(1/ρ)] 1-a t 1-a . • If a = 1, min i∈[n] ⟨w exp t , y i • x i ⟩ ∥w exp t ∥ ∞ -γ ≤ O d + log n + log R(w 0 ) + log log(1/ρ) log t , min i∈[n] ⟨w log t , y i • x i ⟩ ∥w log t ∥ ∞ -γ ≤ O d + n log d + nR(w 0 ) + log log(1/ρ) log t .Corollary 4.7 comprehensively presents the convergence rate of the ℓ ∞ -margin for different learning rates. It also indicates that the margin convergence rates for ℓ exp and ℓ log are of the same order of t. Notably, for a < 1, the normalized ℓ ∞ -margin converges in polynomial time. This clearly distinguishes Adam from (stochastic) gradient descent with/without momentum, for which the normalized ℓ 2 -margin converges at a speed O(1/ log t) [40, 20, 45] . We note that a recent work [46] proposed a novel algorithm named progressive rescaling gradient descent that can maximize the margin at 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 to remark that, although Corollary 4.7 seemingly indicates that η t = (t + 2) -2/3 is the learning rate schedule with the fastest convergence rate, it does not mean that η t = (t + 2) -2/3 always converge faster than the other learning rate schedules in all learning tasks. The bounds in Corollary 4.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. 
experiments: 
 In this section, we conduct numerical experiments to verify our theoretical conclusions. We set the sample size n = 50, and dimension d = 50. Then the data set {(x i , y i )} are generated as follows:1. x i , i ∈ [n] are independently generated from N (0, I).2. y i , i ∈ [n] are independently generated from as +1 or -1 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 ℓ ∞ -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 ℓ 2 -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 β 1 = 0.9, and for Adam, we set β 1 = 0.9, β 2 = 0.99. All these hyper-parameter setups are common in practice. All optimization algorithms are initialized with standard Gaussian distribution, and are run for 10 6 iterations.We first run GD, GDM, Adam without the stability constant, and Adam with stability constant ϵ = 10 -8 to train a linear model minimizing the logistic loss, and compare their normalized ℓ ∞margin and normalized ℓ 2 -margin. The results are given in Figure 1 . We can see that the normalized ℓ ∞ -margins of Adam, both with and without ϵ, converge to the maximum ℓ ∞ -margin, whereas the normalized ℓ ∞ -margins of GD and GDM do not. In contrast, the normalized ℓ 2 -margins of GD and GDM converge to the maximum ℓ 2 -margin, while the ℓ 2 -margins 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 ϵ characterizes the practical behaviour of Adam more accurately compared with the maximum ℓ 2 -margin result for Adam with ϵ in [45] .We also run a set of experiments to demonstrate the polynomial time convergence rate of the ℓ ∞margin. We run experiments on Adam with learning rates η t = Θ(t -a ) for a ∈ {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 a certain number of iterations, curves for a < 1 almost appear as straight lines, suggesting that the normalized ℓ ∞ -margin converges in polynomial time for a < 1, while the curve for a = 1 exhibits logarithmic behavior, indicating the normalized ℓ ∞ -margin converges logarithmically in t for a = 1. Similarly to the previous observations, there is still no significant distinction between Adam with and without ϵ, further demonstrating that our theoretical setting, which disregards ϵ, is reasonable. We also note that in Figure 2 , the margin achieved by Adam with η t = Θ(t -0.3 ) converges the fastest. However, as we have commented in Section 4, different learning rate schedules may perform differently on different data sets, and it is not necessarily true that η t = Θ(t -0.3 ) is always the best learning rate schedule. 6 Proof Sketch for Theorem 4.5In this section, we explain how we establish the convergence of the ℓ ∞ -margin of linear models trained by Adam, and provide the sketch proof of Theorem 4.5. For simplicity, here we focus on the case ℓ = ℓ exp . The proof for ℓ = ℓ log is almost the same.We first introduce several notations. DefineG(w) = - 1 n n i=1 ℓ ′ (⟨w, y i • x i ⟩).Then for ℓ ∈ {ℓ exp , ℓ log }, it is clear that G(w) > 0 for all w ∈ R d . In the following, we will show that G(w) plays a 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 t and v t , which are calculated as exponential moving averages of the historical gradients and squared gradients respectively. A key challenge in studying Adam is to accurately characterize each entry of m t and v t throughout training. We present the following lemma. Lemma 6.1. Under the same condition in Theorem 4.5, there existst 1 = t 1 (β 1 , β 2 , B) such that m t [k] -(1 -β t+1 1 ) • ∇R(w t )[k] ≤ c m η t G(w t ), v t [k] -1 -β t+1 2 • ∇R(w t )[k] ≤ c v √ η t G(w t ) for all t > t 1 and k ∈ [d],where c m and c v are constants that only depend on β 1 , β 2 and B.Since η t , β t+1 1 and β t+1 2 all decrease to zero as t increases, Lemma 6.1 implies that after a sufficient number of iterations, the entries of m t and v t will be close to the corresponding entries of ∇R(w t ) and |∇R(w t )| respectively. Notably, the term G(w t ) also appears in the bounds. In fact, deriving such bounds with the factor G(w t ) is essential to enable our implicit bias analysis: when the algorithm converges, by definition, G(w t ) will also decrease to zero, which implies that the bounds with the factor G(w t ) are strictly tighter than the bounds without G(w t ). Lemma 6.1 is one of our key technical contributions.Step 2. R(w t ) starts to decrease after a fixed number of iterations. Based on Lemma 6.1, we can analyze the convergence of R(w t ). Specifically, we can show that, after a 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 existt 1 = t 1 (β 1 , β 2 , B) such that for all t > t 1 , it holds that R(w t+1 ) ≤ R(w t ) -η t γ • 1 -C 1 β t/2 1 -C 2 d • η 1 2 t + η t • G(w t ), where C 1 , C 2 only depend on β 1 , β 2 , B.Note that by definition, G(w) > 0 for all w ∈ R d . Therefore, Lemma 6.2 implies that R(w t ) starts to decrease after a fixed number of iterations, and gives a bound on the decreasing speed. We remark that the proof of Lemma 6.2 is highly non-trivial. Although we have related m t and v t to the loss gradient ∇R(w t ) in Lemma 6.1, the fact that w t+1 is updated according to the entry-wise ratio m t / √ v t still introduces challenges: under our problem setting, it is entirely possible that at a certain iteration, a certain entry of ∇R(w t ) will exactly equal zero. In this case, the results in Lemma 6.1 can not directly lead to any conclusions about the ratio m t / √ v t . In our proof, we implement a careful inequality that also takes the historical values of ∇R(w t ) into consideration.Step 3. Lower bound for un-normalized margin. The proof of the implicit bias towards maximum ℓ ∞ -margin also relies on a tight analysis on the un-normalized margin min i∈[n] ⟨w t , y i • x i ⟩ during training. We have the following lemma providing a lower bound on the un-normalized margin.Lemma 6.3. Under the same condition in Theorem 4.5, if there exists t 0 such that R(w t ) ≤ log 2 n for all t ≥ t 0 , then it holds thatmin i∈[n] ⟨w t , y i • x i ⟩ ≥ γ t-1 τ =t0 η τ • G(w τ ) R(w τ ) -C 3 d t-1 τ =t0 η 3 2 τ + t-1 τ =t0 η 2 τ -C 4for all t ≥ t 0 , where C 3 , C 4 only depend on β 1 , β 2 , B.Note that this lower bound contains a negative term -C3 d t-1 τ =t0 η 3/2 τ + t-1 τ =t0 η 2 τ .Under our (mild) assumptions on the learning rates, it is entirely possible that∞ τ =t0 η 3/2 τ , ∞ τ =t0 η 2 τ =+∞ and thus the negative term in the lower bound may go to -∞. However, we can show that lim t→∞ G(w t )/R(w t ) = 1 (in fact, for exponential loss, it is obvious that G(w t )/R(w t ) = 1). Therefore, after a 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 in its applicability to very general learning rates {η t } ∞ t=1 .Step 4. An upper bound of ∥w t ∥ ∞ .In Lemma 6.3, we have obtained a lower bound of the un-normalized margin. However, to show the convergence of the ℓ ∞ -normalized margin, we also need to establish a tight upper bound of ∥w t ∥ ∞ . 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 C 5 , C 6 that only depend on β 1 , β 2 , B, such that the following result hold: if there existst 0 > log(1/ρ) such that R(w t ) ≤ 1 √ B 2 +C5η0 for all t ≥ t 0 , then ∥w t ∥ ∞ ≤ t-1 τ =t0 η τ + C 6 t0-1 τ =0 η τ for all t > t 0 .Lemma 6.4 gives an upper bound of ∥w t ∥ ∞ which mainly depends on t-1 τ =t0 η τ . Note that Lemma 6.3 also gives a lower bound of the un-normalized margin which mainly depends on t-1 τ =t0 η τ G(w τ )/R(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 in [56] ). For Adam iterations defined in (3.2)-(3.4) withβ 1 ≤ β 2 and let α = β2(1-β1) 2 (1-β2)(β2-β 2 1 ) , then m t [k] ≤ α • v t [k] for all k ∈ [d].We are now ready to prove Theorem 4.5 for the case ℓ = ℓ exp .Proof of Theorem 4.5. By Lemma 6.2, there existsEQUATIONfor all t ≥ t 2 . Note that for ℓ = ℓ exp , by definition we have G(w t ) = 1 n n i=1 exp(-⟨w t , y i • x i ⟩) = R(w t ). Therefore, for all t > t 2 , (6.1) can be re-written asR(w t+1 ) ≤ 1 - γη t 2 • R(w t ) ≤ R(w t ) • e -γη t 2 ≤ R(w t2 ) • e - γ t τ =t 2 ητ 2 .Although ℓ exp is not Lipschitz continuous over R, we have R(w t2 ) ≤ R(w 0 ) • e αB t 2 -1 τ =0 ητ by Lemma 6.5 and triangle inequality.Letting R 0 = min{ log 2 n , 1 √ B 2 +C5η0} andt 0 = t 0 (n, d, β 1 , β 2 , γ, B, ρ, w 0 ) be the first time such that t0-1 τ =t2 η τ ≥ 2αB γ t2-1 τ =0 η τ + 2 log R(w0)-2 log R0 γand t 0 ≥ -log ρ. By such definition of t 0 , we can derive that for all t ≥ t 0 ,R(w t ) ≤ R(w t2 ) • e - γ t τ =t 0 ητ 2 • e - γ t 0 -1 τ =t 2 ητ 2 ≤ R 0 • e - γ t τ =t 0 ητ 2, which proves the bound on R(w t ). Since t 0 satisfies all the conditions in Lemmas 6.3 and 6.4, by Lemmas 6.3, 6.4 and the fact that G(w τ ) = R(w τ ) for exponential loss, we have ⟨w t , y i • x i ⟩ ∥w t ∥ ∞ ≥ γ t-1 τ =t0 η τ -C 3 d t-1 τ =t0 η 3 2 τ + t-1 τ =t0 η 2 τ -C 4 t-1 τ =t0 η τ + C 6 t0-1 τ =0 η τ for all i ∈ [n],⟨w t , y i • x i ⟩ ∥w t ∥ ∞ -γ ≤ γC 6 t0-1 τ =0 η τ + C 3 d t-1 τ =t0 η 3 2 τ + t-1 τ =t0 η 2 τ + C 4 t-1 τ =t0 η τ + C 6 t0-1 τ =0 η τ ≤ O t0-1 τ =0 η τ + d t-1 τ =t0 η 3 2 τ t-1 τ =0 η τ ,where the second inequality follows by the assumption that η t → 0. This finishes the proof. 
conclusion and future work: 
 In this paper, we study the implicit bias of Adam under a challenging but insightful setting where the "stability constant ϵ" is negligible and set to zero. We demonstrate that Adam has an implicit bias converging towards the maximum ℓ ∞ -margin solution, and such convergence occurs in 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 ℓ 2 -margin solution with an O(1/ log t) convergence rate. This finding aligns with the implicit bias of Adam observed in experiments, for both cases the stability constant ϵ is zero and 10 -8 . We predict that similar result can be extended to homogeneous neural networks, and we believe that this is a 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. 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [No] Justification: This paper is a theoretical work that has no direct social impact. We would like to emphasize that, although the topic is related to "implicit bias", it is a pure theoretical terminology and has nothing to do with social bias.Guidelines:• The answer NA means that there is no societal impact of the work performed.• 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 a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an 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 a 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 to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?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 a 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 is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?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 or dataset.• The authors should state which version of the asset is used and, if possible, include a 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.• If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • 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 is not available online, the authors are encouraged to reach out to the asset's creators. 
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/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
crowdsourcing 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 as 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 in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as 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. 
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 an equivalent approval/review based on the requirements of your country or 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 nor research with human subjects. • Depending on 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.• We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to 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. 
 
 Appendix: A.1 Preliminary Lemma It can be figured out that only the product y i •x i is concerned in (3.1) . Therefore, we define z i = y i •x i , then (3.1) could be re-written asR(w) = 1 n n i=1 ℓ(⟨w, z i ⟩).We also defineZ = [z 1 , z 2 , • • • , z n ] ⊤ ∈ R n×dto denote our sample with i-th row is z ⊤ i , and we will useZ ∈ R n×d to denote the data sample instead of {(x i , y i )} n i=1 in the following paragraphs. Then G(w) = 1 n n i=1 -ℓ ′ (⟨w, z i ⟩), and we introduce L ′ (w) = [-1 n ℓ ′ (⟨w, z 1 ⟩), -1 n ℓ ′ (⟨w, z 2 ⟩), • • • , -1 n ℓ ′ (⟨w, z n ⟩)] ⊤ , which means G(w) = ∥L ′ (w)∥ 1 .The following lemma reveals the relationship between the maximum margin γ and ∇R(w t ) by duality. Lemma A.1. For data sample Z under Assumption 4.1 and maximum ℓ ∞ -margin γ as defined in (4.1), thenγ ≤ min r∈∆n ∥Z ⊤ r∥ 1 , where ∆ n = {r|r ∈ R n , n i=1 r i = 1, r i ≥ 0} is the n dimensional simplex. Remark A.2. Since L ′ (wt)G(wt) ∈ ∆ n , and ∇R(w t ) = Z ⊤ L ′ (w t ), we always have γG(w t ) ≤ ∥∇R(w t )∥ 1 , which is the essence for proving the convergence direction of gradient-based algorithms. This result was also proposed in [39, 41, 14, 21, 23] .Proof of Lemma A.1. Firstly, we introduce a definition of indicator function ι(•) asι E (z) = 0, if z ∈ E; + ∞, if z / ∈ E,where E is any set. Let f (r) = ι ∆n (r) and g(z) = ∥z∥ 1 , then we could derive that f * (r * ) = max i∈[n] ⟨e i , r * ⟩ is the dual function of f (r) and g * (z * ) = ι ∥z * ∥∞≤1 is the dual function of g(z).Then by Fenchel-Young inequality, we havemin r∈∆n ∥Z ⊤ r∥ 1 = min r∈R n f (r) + g(Z ⊤ r) ≥ max w∈R d -f * (Zw) -g * (-w) = max w∈R d -max i∈[n] e ⊤ i Zw -ι ∥w∥∞≤1 = max ∥w∥∞≤1 min i∈[n] e ⊤ i Zw = γ.A.2 Proof of Lemma 6.5We 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-Schwartz inequality, we could derive an upper bound for m t [k] asm t [k] = β 1 m t-1 [k] + (1 -β 1 ) • ∇R(w t )[k] ≤ t τ =0 β τ 1 (1 -β 1 ) • ∇R(w t-τ )[k] = t τ =0 β τ 2 (1 -β 2 ) β τ 1 (1 -β 1 ) β τ 2 (1 -β 2 ) • ∇R(w t-τ )[k] ≤ t τ =0 β τ 2 (1 -β 2 ) • ∇R(w t-τ )[k] 2 1 2 t τ =0 β 2τ 1 (1 -β 1 ) 2 β τ 2 (1 -β 2 ) 1 2 ≤ α v t [k].The last inequality is fromv t [k] = t τ =0 β τ 2 (1 -β 2 ) • ∇R(w t-τ )[k] 2 ,andt τ =0 β 2τ 1 (1 -β 1 ) 2 β τ 2 (1 -β 2 ) ≤ (1 -β 1 ) 2 1 -β 2 ∞ τ =0 β 2 1 β 2 τ = β 2 (1 -β 1 ) 2 (1 -β 2 )(β 2 -β 2 1 ) = α 2 .This finishes the proof.A.3 Proof of Lemma 6.1Proof of Lemma 6.1.EQUATION1 ) be defined in Lemma 6.5. For m t [k], it could be rewritten asm t [k] = t τ =0 β τ 1 (1 -β 1 ) • ∇R(w t-τ )[k] = (1 -β t+1 1 ) • ∇R(w t )[k] + t τ =0 (1 -β 1 )β τ 1 • ∇R(w t-τ )[k] -∇R(w t )[k] .Therefore the difference between m t [k] and (1 -β t+1 1 ) • ∇R(w t )[k] can be bounded as m t [k] -(1 -β t+1 1 ) • ∇R(w t )[k] = t τ =0 (1 -β 1 )β τ 1 • ∇R(w t-τ )[k] -∇R(w t )[k] = t τ =0 (1 -β 1 )β τ 1 1 n n i=1 ℓ ′ (⟨w t-τ , z i ⟩) -ℓ ′ (⟨w t , z i ⟩) • z i [k] ≤ t τ =0 (1 -β 1 )β τ 1 1 n n i=1 ℓ ′ (⟨w t , z i ⟩) ℓ ′ (⟨w t-τ , z i ⟩) ℓ ′ (⟨w t , z i ⟩) -1 z i [k] ≤ (1 -β 1 )B t τ =0 β τ 1 1 n n i=1 ℓ ′ (⟨w t , z i ⟩) e αB τ τ ′ =1 η t-τ ′ -1 ≤ (1 -β 1 )Bc 2 η t • G(w t ) = c m η t • G(w t ).The second inequality holds since |z i [k]| ≤ ∥z i ∥ 1 ≤ B, and for both ℓ ∈ {ℓ exp , ℓ log }, we haveℓ ′ (⟨w t-τ , z i ⟩) ℓ ′ (⟨w t , z i ⟩) -1 ≤ e |⟨wt-wt-τ ,zi⟩| -1 ≤ e ∥wt-wt-τ ∥∞∥zi∥1 -1 ≤ e αB τ τ ′ =1 η t-τ ′ -1,by Lemma 6.5 and Lemma C.5. The last inequality holds sincet τ =0 β τ 1 e αB τ τ ′ =1 η t-τ ′ -1 ≤ c 2 η t by our Assumption 4.4. Similarly for v t [k], we also have v t [k] -(1 -β t+1 2 ) • ∇R(w t )[k] 2 = t τ =0 (1 -β 2 )β τ 2 • ∇R(w t-τ )[k] 2 -∇R(w t )[k] 2 = t τ =0 (1 -β 2 )β τ 2 1 n 2 n i,j=1 ℓ ′ (⟨w t-τ , z i ⟩)ℓ ′ (⟨w t-τ , z j ⟩) -ℓ ′ (⟨w t , z i ⟩)ℓ ′ (⟨w t , z j ⟩) • z i [k]z j [k] ≤ t τ =0 (1 -β 2 )β τ 2 1 n 2 n i,j=1 ℓ ′ (⟨w t , z i ⟩) ℓ ′ (⟨w t , z j ⟩) ℓ ′ (⟨w t-τ , z i ⟩)ℓ ′ (⟨w t-τ , z j ⟩) ℓ ′ (⟨w t , z i ⟩)ℓ ′ (⟨w t , z j ⟩) -1 z i [k] z j [k] ≤ 3(1 -β 2 )B 2 t τ =0 β τ 2 1 n 2 n i,j=1 ℓ ′ (⟨w t , z i ⟩) ℓ ′ (⟨w t , z j ⟩) e 2αB τ τ ′ =1 η t-τ ′ -1 ≤ 3(1 -β 2 )B 2 c 2 η t • G(w t ) 2 = c 2 v η t • G(w t ) 2 .Similarly, the second inequality holds since|z i [k]||z j [k]| ≤ ∥z i ∥ 1 ∥z j ∥ 1 ≤ B 2, and for both ℓ ∈ {ℓ exp , ℓ log }, we haveEQUATION≤ e |⟨wt-wt-τ ,zi⟩| -1 + e |⟨wt-wt-τ ,zj ⟩| -1 + e |⟨wt-wt-τ ,zi+zj ⟩| -1 ≤ e ∥wt-wt-τ ∥∞∥zi∥1 -1 + e ∥wt-wt-τ ∥∞∥zj ∥1 -1 + e ∥wt-wt-τ ∥∞∥zi+zj ∥1 -1≤ 3 e 2αB τ τ ′ =1 η t-τ ′ -1by Lemma 6.5 and Lemma C.6. The last inequality holds since t τ =0 β τ 2 e 2αB τ τ ′ =1 η t-τ ′ -1 ≤| v t [k] -1 -β t+1 2 • ∇R(w t )[k] . Notice that both v t [k] and (1 -β t+1 2 ) • ∇R(w t )[k]2 are positive and for two positive numbers a and b, |a 2 -b 2 | = |a -b||a + b| ≥ |a -b| 2 , therefore we finally conclude that,v t [k] -1 -β t+1 2 • ∇R(w t )[k] ≤ c v √ η t • G(w t ).This finishes the proof.A.4 Proof of Lemma 6.2Before we prove Lemma 6.2, we first introduce and prove Lemma A.3, which will be used for proving Lemma 6.2. Lemma A.3. Under the same condition in Theorem 4.5, there exists t 1 = t 1 (β 1 , β 2 , γ), such that when t > t 1 , we have∇R(w t ), m t √ v t -∇R(w t ) 1 ≤ 4 β t+1 1 1 -β t+1 2 • ∇R(w t ) 1 + d √ 1 -β 2 6c v 1 -β t+1 2 √ η t + 3c m η t • G(w t ), (A.1)where c m and c v are both constants which only depend on β 1 , β 2 and B.Proof of Lemma A.3. By Lemma 6.1, we could re-writeEQUATIONv t [k] = 1 -β t+1 2 • ∇R(w t )[k] + c v √ η t • G(w t ) • ϵ t,v,k > 0,where ϵ t,m,k and ϵ t,v,k are just some error terms with |ϵ t,m,k |, |ϵ t,v,k | ≤ 1. Then we can calculate the inner-product ⟨∇R(w t ), mt √ vt ⟩ for each iteration as∇R(w t ), m t √ v t = ∇R(w t ) 1 + d k=1 ∇R(w t )[k] • m t [k] v t [k] - ∇R(w t )[k] |∇R(w t )[k]| ( * ).Moreover, we letξ t,k = ∇R(w t )[k] • m t [k] v t [k] - ∇R(w t )[k] |∇R(w t )[k]| = ∇R(w t )[k] • (1 -β t+1 1 ) • ∇R(w t )[k] + c m η t • G(w t ) • ϵ t,m,k 1 -β t+1 2 • ∇R(w t )[k] + c v √ η t • G(w t ) • ϵ t,v,k - ∇R(w t )[k] |∇R(w t )[k]| ,and consider to separate ξ t,k into two complementary parts. The first part is ξ t,k 1 A t,k , whereA t,k = 1 -β t+1 2 • ∇R(w t )[k] ≥ 2c v √ η t • G(w t ) • |ϵ t,v,k | . While another part is ξ t,k 1 A c t,k , where A c t,k = 1 -β t+1 2 • ∇R(w t )[k] < 2c v √ η t • G(w t ) • |ϵ t,v,k | . By such separation, we have ( * ) = d k=1 ξ t,k 1 A t,k + ξ t,k 1 A c t,k ≤ d k=1 ξ t,k 1 A t,k + d k=1 ξ t,k 1 A c t,kWe calculate it part by part. For the first partd k=1 ξ t,k 1 A t,k , we have d k=1 ξ t,k 1 A t,k ≤ d k=1 1 -β t+1 -1 -β t+1 2 • ∇R(w t )[k] 3 + c m η t + c v √ η t • G(w t ) • ∇R(w t )[k] 2 1 -β t+1 2 • ∇R(w t )[k] + c v √ η t • G(w t ) • ϵ t,v,k • ∇R(w t )[k] 1 A t,k ≤ d k=1 1 -β t+1 -1 -β t+1 2 • ∇R(w t )[k] 3 + c m η t + c v √ η t • G(w t ) • ∇R(w t )[k] 2 1 2 1 -β t+1 2 • ∇R(w t )[k] 2 ≤ 4 β t+1 1 1 -β t+1 2 • ∇R(w t ) 1 + 2d 1 -β t+1 2 c m η t + c v √ η t • G(w t ). (A.2)The first inequality is derived by triangle inequality and|ϵ t,m,k |, |ϵ t,v,k | ≤ 1. The second inequality holds since 1 -β t+1 2 • ∇R(w t )[k] + c v √ η t • G(w t ) • ϵ t,v,k > 1 2 1 -β t+1 2 • ∇R(w t )[k] when 1 A t,k = 1.And the last inequality is simply due to an arithmetic result that1 -β t+1 1 -1 -β t+1 2 ≤ 1 -1 -β t+1 2 + β t+1 1 ≤ 1 -1 + β t+1 2 + β t+1 1 ≤ 2β t+1 2 1 .Then for another partd k=1 ξ t,k 1 A c t,k , we use the property v t [k] ≥ √ 1 -β 2 • ∇R(w t )[k] to derive an upper bound as d k=1 ξ t,k 1 A c t,k ≤ d k=1 ∇R(w t )[k] • ∇R(w t )[k] + c m η t • G(w t ) √ 1 -β 2 • ∇R(w t )[k] + 1 1 A c t,k ≤ d √ 1 -β 2 4c v 1 -β t+1 2 √ η t + c m η t • R(w t ). (A.3)The first inequality is derived by triangle inequality and |ϵ t,m,k | ≤ 1. The second inequality holds since ∇R(wt )[k] ≤ 2cv √ 1-β t+1 2 √ η t • G(w t ) when 1 A c t,k = 1.Combining the results of (A.2),(A.3) and Lemma C.2, 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 t+1 ) for t > t 1 by second-order Taylor expansion asR(w t+1 ) = R(w t ) + ∇R(w t ), w t+1 -w t + 1 2 w t+1 -w t ⊤ ∇ 2 R w t + ζ(w t+1 -w t ) w t+1 -w t = R(w t ) -∇R(w t ), η t m t √ v t + 1 2 η t m t √ v t ⊤ ∇ 2 R w t + ζ(w t+1 -w t ) η t m t √ v t ≤ R(w t ) -η t 1 -4 β t+1 1 1 -β t+1 2 • ∇R(w t ) 1 + η t d √ 1 -β 2 6c v 1 -β t+1 2 √ η t + 3c m η t • G(w t ) + η 2 t α 2 B 2 2 • max G(w t ), G(w t+1 ) ≤ R(w t ) -η t γ 1 -4 β t+1 1 1 -β t+1 2 • G(w t ) + η 3 2 t 6c v d (1 -β 2 )(1 -β t+1 2 ) • G(w t ) + η 2 t α 2 B 2 e αBη0 2 + 3c m d √ 1 -β 2 • G(w t ).The first inequality is from Lemma A.3, and for the vector mt √ vt ,m t √ v t ⊤ ∇ 2 R(w) m t √ v t ≤ 1 n n i=1 ℓ ′′ ⟨w, z i ⟩ m t √ v t 2 ∞ z i 2 1 ≤ α 2 B 2 • G(w)by Lemma C.2 and Lemma 6.5, and G w t + ζ(w t+1 -w t ) ≤ max G(w t ), G(w t+1 ) from convexity of G(w). The last inequality is from G(wt+1) G(wt) ≤ e αBηt ≤ e αBη0 by Lemma C.5 and γG(w t ) ≤ ∥∇R(w t )∥ 1 by Lemma A.1.Proof of Lemma 6.3. By Lemma 6.2 and Lemma C.2 , we haveR(w t+1 ) ≤ R(w t ) • 1 -γη t • G(w t ) R(w t ) + C 1 γη t β t/2 1 + η 3 2 t C 2 d + η 2 t C 2 d • G(w t ) R(w t ) ≤ R(w t ) • exp -γη t • G(w t ) R(w t ) + C 1 γη t β t/2 1 + C 2 d • (η 3 2 t + η 2 t ) ≤ log 2 n • exp -γ t τ =t0 η τ • G(w τ ) R(w τ ) + C 2 d t τ =t0 η 3 2 τ + t τ =t0 η 2 τ + C 1 γη t0 β t 0 +1 2 1 1 - √ β 1 . (A.4)for all t ≥ t 0 . By Lemma C.4, we can derive that ⟨w t , z i ⟩ ≥ 0 for all i ∈ [n] and t ≥ t 0 . Then we have e -min i∈[n] ⟨wt,zi⟩ ≤ 1 log 2 max i∈[n] ℓ(⟨w t , z i ⟩) ≤ n log 2 R(w t ) by Lemma C.3. Plugging this result into (A.4) and taking log on both sides, we finish the proof for Lemma 6.3.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 in (3.2)-(3.4) with β 1 ≤ β 2 , for any t 0 ∈ N + , t > t 0 , and all k ∈ [d],w t [k] -w t0 [k] ≤ t-1 τ =t0 η τ • 1 + β 2 -β 1 1 -β 2 t-1 τ =t0 β τ -t0 1 η τ t-1 τ =t0 η τ + (β 2 -β 1 )(1 -β 1 ) 1 -β 2 t-1 τ =t0 η τ 1-β τ -t 0 1 1-β1 - t-τ -1 τ ′ =1 η τ +τ ′ β τ ′ -1 1 t-1 τ =t0 η τ log(v τ [k]) 1 2 . (A.5)Proof of Lemma A.4. If we consider implementing the Cauchy-Schwartz inequality on the sum of the iterations, we can get,w t [k] -w t0 [k] = t-1 τ =t0 η τ m τ [k] v τ [k] = t-1 τ =t0 η τ v τ [k] β τ -t0+1 1 m t0-1 [k] + τ -t0 τ ′ =0 β τ ′ 1 (1 -β 1 ) • ∇R(w τ -τ ′ )[k] ≤ t-1 τ =t0 η τ v τ [k] β τ -t0+1 1 m t0-1 [k] 2 + τ -t0 τ ′ =0 β τ ′ 1 (1 -β 1 ) • ∇R(w τ -τ ′ )[k] 2 1 2 • t-1 τ =t0 η τ β τ -t0+1 1 + τ -t0 τ ′ =0 β τ ′ 1 (1 -β 1 ) 1 2 = t-1 τ =t0 η τ v τ [k] β τ -t0+1 1 m t0-1 [k] 2 + τ -t0 τ ′ =0 η τ β τ ′ 1 1 -β 1 1 -β 2 v τ -τ ′ [k] -β 2 v τ -τ ′ -1 [k] v τ [k] ( * ) 1 2 t-1 τ =t0 η τ 1 2 . (A.6)The inequality is by Cauchy-Schwartz inequality and the second equality is from(1 -β 2 ) • ∇R(w τ -τ ′ )[k] 2 = v τ -τ ′ [k] -β 2 v τ -τ ′ -1 [k],andt-1 τ =t0 η τ β τ -t0+1 1 + τ -t0 τ ′ =0 β τ ′ 1 (1 -β 1 ) = t-1 τ =t0 η τ β τ -t0+1 1 + 1 -β τ -t0+1 1 = t-1 τ =t0 η τ .For the first part ( * ) defined in (A.6), we could re-arrange it as,( * ) = t-1 τ =t0 η τ v τ [k] β τ -t0+1 1 m t0-1 [k] 2 + t-1 τ =t0 η τ (1 -β 1 ) v τ [k] -β 2 β τ -t0 1 v t0-1 [k] + (β 1 -β 2 ) τ -t0 τ ′ =1 β τ ′ -1 1 v τ -τ ′ [k] (1 -β 2 )v τ [k] ≤ t-1 τ =t0 η τ v τ [k] β τ -t0 1 β 1 α 2 - β 2 (1 -β 1 ) 1 -β 2 v t0-1 [k] + 1 -β 1 1 -β 2 t-1 τ =t0 η τ + (1 -β 1 )(β 1 -β 2 ) 1 -β 2 t-1 τ =t0 τ -t0 τ ′ =1 η τ β τ ′ -1 1 v τ -τ ′ [k] v τ [k] ≤ 1 -β 1 1 -β 2 t-1 τ =t0 η τ + (1 -β 1 )(β 1 -β 2 ) 1 -β 2 t-1 τ =t0 τ -t0 τ ′ =1 η τ β τ ′ -1 1 v τ -τ ′ [k] v τ [k] = t-1 τ =t0 η τ + β 2 -β 1 1 -β 2 t-1 τ =t0 η τ - (1 -β 1 )(β 2 -β 1 ) 1 -β 2 t-1 τ =t0 τ -t0 τ ′ =1 η τ β τ ′ -1 1 v τ -τ ′ [k] v τ [k] = t-1 τ =t0 η τ + β 2 -β 1 1 -β 2 t-1 τ =t0 η τ 1 -(1 -β 1 ) τ -t0 τ ′ =1 β τ ′ -1 1 v τ -τ ′ [k] v τ [k] = t-1 τ =t0 η τ + β 2 -β 1 1 -β 2 t-1 τ =t0 η τ β τ -t0 1 + (1 -β 1 ) τ -t0 τ ′ =1 β τ ′ -1 1 -(1 -β 1 ) τ -t0 τ ′ =1 β τ ′ -1 1 v τ -τ ′ [k] v τ [k] = t-1 τ =t0 η τ + β 2 -β 1 1 -β 2 t-1 τ =t0 η τ β τ -t0 1 + (1 -β 1 ) τ -t0 τ ′ =1 β τ ′ -1 1 1 - v τ -τ ′ [k] v τ [k] ≤ t-1 τ =t0 η τ + β 2 -β 1 1 -β 2 t-1 τ =t0 η τ β τ -t0 1 + (1 -β 1 ) τ -t0 τ ′ =1 β τ ′ -1 1 log v τ [k] v τ -τ ′ [k] = t-1 τ =t0 η τ + β 2 -β 1 1 -β 2 t-1 τ =t0 η τ β τ -t0 1 + (β 2 -β 1 )(1 -β 1 ) 1 -β 2 t-1 τ =t0 η τ τ -t0 τ ′ =1 β τ ′ -1 1 log(v τ [k]) -log(v τ -τ ′ [k]) = t-1 τ =t0 η τ + β 2 -β 1 1 -β 2 t-1 τ =t0 η τ β τ -t0 1 + (β 2 -β 1 )(1 -β 1 ) 1 -β 2 t-1 τ =t0 η τ 1 -β τ -t0 1 1 -β 1 log(v τ [k]) - t-1 τ =t0 η τ τ -t0 τ ′ =1 β τ ′ -1 1 log(v τ -τ ′ [k]) τ * =τ -τ ′ ======= t-1 τ =t0 η τ + β 2 -β 1 1 -β 2 t-1 τ =t0 η τ β τ -t0 1 + (β 2 -β 1 )(1 -β 1 ) 1 -β 2 t-1 τ =t0 η τ 1 -β τ -t0 1 1 -β 1 log(v τ [k]) - t-1 τ =t0 η τ τ -1 τ * =t0 β τ -τ * -1 1 log(v τ * [k]) = t-1 τ =t0 η τ + β 2 -β 1 1 -β 2 t-1 τ =t0 η τ β τ -t0 1 + (β 2 -β 1 )(1 -β 1 ) 1 -β 2 t-1 τ =t0 η τ 1 -β τ -t0 1 1 -β 1 log(v τ [k]) - t-1 τ * =t0 log(v τ * [k]) t-1 τ =τ * +1 η τ β τ -τ * -1 1 = t-1 τ =t0 η τ + β 2 -β 1 1 -β 2 t-1 τ =t0 η τ β τ -t0 1 + (β 2 -β 1 )(1 -β 1 ) 1 -β 2 t-1 τ =t0 η τ 1 -β τ -t0 1 1 -β 1 - t-τ -1 τ ′ =1 η τ +τ ′ β τ ′ -1 1 log(v τ [k]). (A.7)Plugging (A.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, we can upper-bound it as,β 2 -β 1 1 -β 2 t-1 τ =t0 η τ β τ -t0 1 ≤ η t0 (β 2 -β 1 ) (1 -β 1 )(1 -β 2 ),since η t is decreasing. Let C 5 = c 2 v in statement of Lemma A.4.Then for the third term, by Lemma 6.1 and our condition R(w t )≤ 1 √ B 2 +C5η0, we haveEQUATIONη τ 1 -β τ -t0 1 1 -β 1 - t-τ -1 τ ′ =1 η τ +τ ′ β τ ′ -1 1 ≥ η τ 1 -β τ -t0 1 1 -β 1 - t-τ -1 τ ′ =1 β τ ′ -1 1 ≥ -η τ β τ -t0 1 1 -β 1 .Combining these results, we can upper-bound the third term as,(β 2 -β 1 )(1 -β 1 ) 1 -β 2 t-1 τ =t0 η τ 1 -β τ -t0 1 1 -β 1 - t-τ -1 τ ′ =1 η τ +τ ′ β τ ′ -1 1 log(v τ [k]) ≤ β 2 -β 1 1 -β 2 t-1 τ =t0 η τ β τ -t0 1 -τ log β 2 -log(1 -β 2 ) -log ρ ≤ η t0 (β 2 -β 1 ) (1 -β 1 )(1 -β 2 ) t 0 + 1 1 -β 1 (-log β 2 ) -log(1 -β 2 ) -log ρ .Plugging these results into (A.5) with Bernoulli inequality, we have,|w t [k]| ≤ |w t0 [k]| + t-1 τ =t0 η τ + η t0 (β 2 -β 1 ) 2(1 -β 1 )(1 -β 2 ) t 0 + 1 1 -β 1 (-log β 2 ) -log(1 -β 2 ) -log ρ + 1 ≤ t-1 τ =t0 η τ + α t0-1 τ =0 η τ + η t0 (β 2 -β 1 ) 2(1 -β 1 )(1 -β 2 ) t 0 + 1 1 -β 1 (-log β 2 ) -log(1 -β 2 ) -log ρ + 1 ≤ t-1 τ =t0 η τ + α t0-1 τ =0 η τ + C ′ 6 η 0 t 0 ≤ t-1 τ =t0 η τ + C 6 t0-1 τ =0 η τ ,where C 6 and C ′ 6 are constants only depending on β 1 , β 2 and B. The second inequality is from triangle inequality of |w t0 [k]| and Lemma 6.5. The third inequality is from our condition t 0 > -log ρ and the last inequality is because η t is decreasing. Since the preceding result holds for all k ∈ [d], it also holds for ∥w t ∥∞, which finishes the proof. Proof of Theorem 4.5. For C 1 , C 2 defined in Lemma 6.2, it's trivial that when t is large we have the following inequalities hold:(i).βt/2 1 ≤ 1 6C1 ; (ii).η t ≤ min γ 2 36C 2 2 d 2 , γ 6C2d . We use t 2 = t 2 (d, β 1 , β 2 , γ, B)to denote the first time that all the preceding inequalities hold after t 1 = t 1 (β 1 , β 2 , B) in Assumption 4.4. Plugging all aforementioned inequality conditions into Lemma 6.2, we can derive that for all t ≥ t 2 ,R(w t+1 ) ≤ R(w t ) - η t γ 2 G(w t ). (B.1)Therefore we prove that R(w t+1 ) < R(w t ) for all t ≥ t 2 . For further proof, we separately consider ℓ = ℓ exp and ℓ = ℓ log .When ℓ = ℓ exp , by definition we have G(w t ) = R(w t ). Therefore, for all t ≥ t 2 , (B.1) can be re-written asR(w t+1 ) ≤ 1 - γη t 2 • R(w t ) ≤ R(w t ) • e -γη t 2 ≤ R(w t2 ) • e - γ t τ =t 2 ητ 2 .Although ℓ exp is not Lipschitz continuous over R, we haveR(w t2 ) ≤ R(w 0 ) • exp 1 n n i=1 ∥x i ∥ 1 ∥w t2 -w 0 ∥ ∞ ≤ R(w 0 ) • exp αB t2-1 τ =0η τ by Lemma 6.5 and triangle inequality.Letting R 0 = min{ log 2 n , 1 √ B 2 +c 2 v η0} and t 0 = t 0 (n, d, β 1 , β 2 , γ, B, t 1 , w 0 ) be the first time be the first time such thatt0-1 τ =t2 η τ ≥ 2αB γ t2-1 τ =0 η τ + 2 log R(w0)-2 log R0 γand t 0 ≥ -log ρ. By such definition of t 0 , we can derive that for all t ≥ t 0 ,R(w t ) ≤ R(w t2 ) • e - γ t τ =t 0 ητ 2 • e - γ t 0 -1 τ =t 2 ητ 2 ≤ R 0 • e - γ t τ =t 0 ητ 2 .Since t 0 satisfies all the requirements in Lemma 6.3 and Lemma 6.4, we can finally derive that When ℓ = ℓ log , by taking a telescoping sum on the result of (B.1), we obtain γmin i∈[n] ⟨w t , y i • x i ⟩ ∥w t ∥ ∞ -γ ≤ γC 6 t0-1 τ =0 η τ + C 3 d t-1 τ =t0 η 3 2 τ + t-1 τ =t0 η 2 τ + C 4 t-1 τ =t0 η τ + C 6 t0-1 τ =0 η τ ≤ O t0-1 τ =0 η τ + d t-1 τ =t0 η 3 2 τ t-1 τ =0 η τt τ =t2 η τ G(w t ) ≤ 2R(w t2 ) for any t ≥ t 2 . Since ℓ log is 1-Lipschitz continuous, we can derive that R(w t1 ) ≤ R(w 0 ) + αB t2-1 τ =0 η τ . Letting R 0 = min{ log 2 n , 1 √ B 2 +c 2 v η0} and t 0 = t 0 (n, d, β 1 , β 2 , γ, B, t 1 , w 0 ) be the first time such thatt0-1 τ =t2 η τ ≥ 4R(w0)+4αB t 2 -1 τ =0 ητ γR0and t 0 ≥ -log ρ, then we can conclude that min τ ∈[t2,t0] G(w τ ) ≤ 2R(w t2 ) γ t0-1 τ =t2 η τ ≤ 2R(w 0 ) + 2αB t2-1 τ =0 η τ γ t0-1 τ =t2 η τ ≤ R 0 2 . Let τ ′ = argmin τ ∈[t2,t0] G(w τ ),R(w t ) ≤ R(w t-1 ) - γη t-1 2 • G(w t ) ≤ 1 - γη t-1 4 • R(w t-1 ) ≤ R(w t-1 ) • e -γη t-1 4 ≤ R(w t0 ) • e -γ 4 t-1 τ =t 0 ητ ≤ R 0 • e -γ 4 t-1 τ =t 0 ητ .By this result and Lemma C.7, we haveG(w t ) R(w t ) ≥ 1 - nR(w t ) 2 ≥ 1 - nR 0 • e -γ 4 t-1 τ =t 0 ητ 2 ≥ 1 -e -γ 4 t-1 τ =t 0 ητ . (B.2)Since t 0 satisfies all the requirements in Lemma 6.3 and Lemma 6.4, we can combine Lemma 6.3, Lemma 6.4 and (B.2) and finally derive that In this section, we use the notation C 1 , C 2 , C 3 , . . . to denote constants solely depending on β 1 , β 2 , γ and B. While it may seem an abuse of notation as these symbols could be different from Section 6 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.min i∈[n] ⟨w t , y i • x i ⟩ ∥w t ∥ ∞ -γ ≤ γC 6 t0-1 τ =0 η τ + C 3 d t-1 τ =t0 η 3 2 τ + t-1 τ =t0 η 2 τ + C 4 + t-1 τ =t0 η τ e -γ 4 τ -1 τ ′ =t 0 η ′ τ t-1 τ =t0 η τ + C 6 t0-1 τ =0 η τ ≤ O t0-1 τ =0 η τ + d t-1 τ =t0 η 3 2 τ + t-1 τ =t0 η τ e -γ 4 τ -1 τ ′ =t 0 η ′ τ t-1 τ =0 η τ ,For given η t = (t + 2) -a with a ∈ (0, 1], recall the definition of t 2 in Appendix B.1 to be the first time such that (i).βt/2 1 ≤ 1 6C1 ; (ii).η t ≤ min γ 2 36C 2 2 d 2 , γ6C2d . We can derive thatt 2 = max - 2 log 6 + 2 log C 1 log β 1 , 36C 2 2 d 2 γ 2 1 a , 6C 2 d γ 1 a = C 3 d 2 a .We consider the following four cases,• If ℓ = ℓ exp and a ∈ (0, 1), recall in Appendix B.1, the definition for t 0 when ℓ = ℓ exp is the first time such thatt0-1 τ =t2 η τ ≥ 2αB γ t2-1 τ =0 η τ + 2 log R(w0)-2 log R0γ and t 0 ≥ -log ρ, by simple approximation from integral of t -a , we can derive that,t 0 ≤ C 1 d 2 a + C 2 [log n] 1 1-a + C 3 [log R(w 0 )] 1 1-a + C 4 log(1/ρ).Similarly, we can also derivet0-1 τ =0 η τ ≤ C 1 t 1-a 0 ≤ C 2 d 2(1-a) a + C 3 log n + C 4 log R(w 0 ) + C 5 [log(1/ρ)] 1-a . When a > 2 3 , ∞ τ =t0 η 3 2τ is bounded by some constant,t-1 τ =0 η τ = O(t 1-a ) and 2(1-a)a < 1, therefore we conclude that,min i∈[n] ⟨w exp t , z i ⟩ ∥w exp t ∥ ∞ -γ ≤ O d + log n + log R(w 0 ) + [log(1/ρ)] 1-a t 1-a .When a = 2 3 , similarly we havet-1 τ =t0 η 3 2 τ = O(log t) and t-1 τ =0 η τ = O(t 1/3), then we conclude thatmin i∈[n] ⟨w exp t , z i ⟩ ∥w exp t ∥ ∞ -γ ≤ O d • log t + log n + log R(w 0 ) + [log(1/ρ)] 1/3 t 1/3 .When a < 2 3 , similarly we havet-1 τ =t0 η 3 2 τ = O(t 1-3a 2 ) and t-1 τ =0 η τ = O(t 1-a ).Under this sub-case, we could always find a new t ′ 0 ≥ t 0 such that besides the preceding condition for t 0 , we also haved • t ′1-3a/2 0 > max{d 2(1-a) a , log n, log R(w 0 ), [log(1 -ρ)] 1-a }.Letting this new t ′ 0 to be the t 0 in our statement of Corollary 4.7, then we conclude that,min i∈[n] ⟨w exp t , z i ⟩ ∥w exp t ∥ ∞ -γ ≤O d • t 1-3a 2 + d 2(1-a) a + log n + log R(w 0 ) + [log(1/ρ)] 1-a t 1-a ≤ O d t a/2 .• If ℓ = ℓ exp and a = 1, then by the definition of t 0 and integral of t -1 , we obtain that,log t 0 ≤ C 1 log d + C 2 log n + C 3 log R(w 0 ) + C 4 log log(1/ρ).Similarly, we can also derivet0-1 τ =0 η τ ≤ C 1 log d + C 2 log n + C 3 log R(w 0 ) + C 4 log log(1/ρ). Since t-1 τ =0 η τ = O(log t) and t-1 τ =t0 η 3 2τ is bounded, we obtain that,min i∈[n] ⟨w exp t , z i ⟩ ∥w exp t ∥ ∞ -γ ≤ O d + log n + log R(w 0 ) + log log(1/ρ) log t .• If ℓ = ℓ log and a ∈ (0, 1), firstly we upper bound the last termt τ =t0 η τ e -γ 4 τ -1 τ ′ =t 0 η τ ′ as t-1 τ =t0 η τ e -γ 4 τ -1 τ ′ =t 0 η τ ′ ≤ e γ(t 0 +1) 1-a 4(1-a) ∞ τ =t0 1 (τ + 2) a e -γ(τ +1) 1-a 4(1-a) ≤ 4 γ e γ 4(1-a) .Therefore,t τ =t0 η τ e -γ 4 τ -1 τ ′ =t 0η τ ′ is always bounded by a constant. The only difference between ℓ log and ℓ exp is how to determine the value of t 0 . For ℓ log , the formula for t 0 is the first time such that t0-1τ =t2 η τ ≥ 4R(w0)+4αB t 2 -1 τ =0 ητ γR0and t ≥ log(1/ρ). Similar to the preceding process, we could derive thatt 0 ≤ C 1 n 1 1-a d 2 a + C 2 n 1 1-a [R(w 0 )] 1 1-a + C 3 log(1/ρ). and t0-1 τ =0 η τ ≤ C 1 nd 2(1-a) a + C 2 nR(w 0 ) + C 3 [log(1/ρ)] 1-a . When a > 2 3 , ∞ τ =t0 η 3 2τ is bounded by some constant,t-1 τ =0 η τ = O(t 1-a ) and 2(1-a) a ≤ 1, therefore we conclude that min i∈[n] ⟨w log t , z i ⟩ ∥w log t ∥ ∞ -γ ≤ O d + nd 2(1-a) a + nR(w 0 ) + [log(1/ρ)] 1-a t 1-a .When a = 2 3 , similarly we havet-1 τ =t0 η 3 2 τ = O(log t) and t-1 τ =0 η τ = O(t 1/3), then we conclude thatmin i∈[n] ⟨w log t , z i ⟩ ∥w log t ∥ ∞ -γ ≤ O d • log t + nd + nR(w 0 ) + [log(1/ρ)] 1/3 t 1/3 .When a < 2 3 , similarly we havet-1 τ =t0 η 3 2 τ = O(t 1-3a 2 ) and t-1 τ =0 η τ = O(t 1-a ).Under this setting, we could always find a new t ′ 0 ≥ t 0 such that besides the preceding condition for t 0 , we also haved • t ′1-3a/2 0 > max{nd 2(1-a) a , n log R(w 0 ), [log(1 -ρ)] 1-a }.Letting this new t ′ 0 to be the t 0 in our statement of Corollary 4.7, then we conclude that,min i∈[n] ⟨w log t , z i ⟩ ∥w log t ∥ ∞ -γ ≤O d • t 1-3a 2 + nd 2(1-a) a + nR(w 0 ) + [log(1/ρ)] 1-a t 1-a ≤ O d t a/2 .• If ℓ = ℓ log and a = 1, firstly we upper bound the last termt τ =t0 η τ e -γ 4 τ -1 τ ′ =t 0 η τ ′ as t-1 τ =t0 η τ e -γ 4 τ -1 τ ′ =t 0 η τ ′ ≤ (t 0 + 1) γ/4 ∞ τ =t0 1 (τ + 1) 1+γ/4 ≤ γ 4 2 γ/4 , which implies t τ =t0 η τ e -γ 4 τ -1 τ ′ =t 0 η τ ′ is also a constant.Then by the definition of t 0 and integral of t -1 , we obtain thatlog t 0 ≤ C 1 n log d + C 2 nR(w 0 ) + C 3 log log(1/ρ).and similarlyt0-1 τ =0 ≤ C 1 n log d + C 2 nR(w 0 ) + C 3 log log(1/ρ). Since t-1 τ =0 η τ = O(log t) and t-1 τ =t0 η 3 2τ is bounded, we obtain thatmin i∈[n] ⟨w log t , z i ⟩ ∥w log t ∥ ∞ -γ ≤ O d + n log d + nR(w 0 ) + log log(1/ρ) log t .C.1 Lemma for Assumption 4.4Lemma C.1. Assumption 4.4 holds for both small fixed learning rate η t = η ≤ 1-β 2c1 , and decay learning rate η t = (t + 2) -a with a ∈ (0, 1].Proof of Lemma C.1. Firstly, we prove it for learning rate η t = η ≤ 1-β 2c1 , which is a small fixed constant, then we have,t τ =0 β τ e c1 τ τ ′ =1 η t-τ ′ -1 = t τ =0 β τ e c1ητ -1 = t τ =0 β τ ∞ k=1 (c 1 ητ ) k k! ≤ ∞ τ =0 β τ ∞ k=1 (c 1 ητ ) k k! = ∞ k=1 (c 1 η) k k! ∞ τ =0 β τ τ k ≤ 1 1 -β ∞ k=1 c 1 η 1 -β k ≤ 2c 1 (1 -β) 2 ηThe penultimate inequality holds because∞ τ =0 β τ τ k ≤ ∞ 0 β τ τ k dτ = k! [-log(β)] k+1 ≤ k! (1-β) k+1 .Therefore, we prove that Assumption 4.4 holds for t ∈ N + when η t = η ≤ 1-β 2c1 . Next, we consider the case where decay learning rate η t = 1 (t+2) a with a ∈ (0, 1), and similarly, we have,τ τ ′ =1 η t-τ ′ = τ τ ′ =1 1 (t -τ ′ + 2) a ≤ τ +1 1 1 (t -τ ′ + 2) a dτ ′ = 1 1 -a (t + 1) 1-a -(t -τ + 1) 1-a = 1 1 -a τ + (t + 1) 1-a (t -τ + 1) a -(t + 1) a (t -τ + 1) 1-a (t + 1) a + (t -τ + 1) a ≤ 2 (1 -a) τ (t + 1) aBy this result, we can similarly obtain that for t ≥4c1 (1-β) 2 (1-a) 1 a . t τ =0 β τ e c1 τ τ ′ =1 η t-τ ′ -1 ≤ t τ =0 β τ e 2c 1 τ (1-a)(t+1) a -1 = t τ =0 β τ ∞ k=1 2c 1 τ (1 -a)(t + 1) a k 1 k! ≤ ∞ τ =0 β τ ∞ k=1 2c 1 τ (1 -a)(t + 1) a k 1 k! = ∞ k=1 2c 1 (1 -a)(t + 1) a k 1 k! ∞ τ =0 β τ τ k ≤ 1 1 -β ∞ k=1 2c 1 (1 -β)(1 -a)(t + 1) a k ≤ 4c 1 (1 -β) 2 (1 -a) • 1 (t + 1) a < 8c 1 (1 -β) 2 (1 -a) • η t .Therefore, we prove that Assumption 4.4 holds for t ≥4c1 (1-β) 2 (1-a) 1 a when η t = 1(t+2) a . Finally we consider the case where the decay learning rate η t = 1 t+2 , and similarly, we haveτ τ ′ =1 η t-τ ′ = τ τ ′ =1 1 t-τ ′ +2 ≤ τ +1 1 1 t-τ ′ +2 dτ ′ = log(1 + τ t-τ +1 ). By this result, we obtain thatt τ =0 β τ e c1 τ τ ′ =1 η t-τ ′ -1 ≤ t τ =0 β τ 1 + τ t -τ + 1 ⌈c1⌉ -1 = t τ =0 β τ ⌈c1⌉ k=1 ⌈c 1 ⌉ k τ t -τ + 1 k . (C.1)Because ⌈c 1 ⌉ and ⌈c1⌉ k are both absolute constant, it suffices to show thatt τ =0 β τ τ t-τ +1 k ≤ c2t+2 for all t > t 1 and k ≥ 1 where t 1 , c 2 are both constants. Actually, we could split the summation of τ into two parts ast τ =0 β τ τ t -τ + 1 k = ⌊ t 2 ⌋ τ =0 β τ τ t -τ + 1 k + t τ =⌊ t 2 ⌋+1 β τ τ t -τ + 1 k .For the first part, we have⌊ t 2 ⌋ τ =0 β τ τ t -τ + 1 k ≤ 2 t k ⌊ t 2 ⌋ τ =0 β τ τ k ≤ 2 k k! (1 -β) k+1 • 1 t .For the second part, we could find a constantt 1 = t 1 (c 1 , β) such that t ⌈c1⌉+2 ≤ 1 β t 2 for all t ≥ t 1 since 1 β > 1.Then for all t ≥ t 1 , we can derive thatt τ =⌊ t 2 ⌋+1 β τ τ t -τ + 1 k ≤ β t 2 t τ =⌊ t 2 ⌋+1 τ k ≤ β t 2 t k+1 ≤ 1 t .The last inequality is by our condition t ≥ t 1 and k ≤ ⌈c 1 ⌉. Combining these two results and plugging it into (C.1), we finally get Therefore we derive that ℓ ′′ log (z) ≤ |ℓ ′ log (z)| ≤ ℓ log (z).t τ =0 β τ e c1 τ τ ′ =1 η t-τ ′ -1 ≤ ⌈c 1 ⌉ • max k∈[⌈c1⌉] ⌈c 1 ⌉ k • 2 ⌈c1⌉ ⌈c 1 ⌉! (1 -β) ⌈c1⌉+1 + 1 • 1 t ≤ 2⌈c 1 ⌉ • max k∈[⌈c1⌉] ⌈c 1 ⌉ k • 2 ⌈c1⌉ ⌈c 1 ⌉! (1 -β) ⌈c1⌉+1 + 1 • η t for all t ≥ t 1 ,Lemma C.3. For any z ≥ 0,|ℓ ′ log (z)| ℓ log (z) , |ℓ ′ log (z)| ℓexp(z) ≥ 1 2 and ℓ log (z) ℓexp(z) ≥ log 2.Proof of Lemma C.3. For z ≥ 0, it holds thatℓ log (z) ≤ ℓ exp (z) = 2 2e z ≤ 2 1 + e z = 2|ℓ ′ log (z)|.The second result holds becauseℓ log (z) ℓexp(z) = log(1+e -z ) e -zis an decreasing function for e -z and e -z ∈ (0, 1] for z ≥ 0.Lemma C.4. For ℓ ∈ {ℓ exp , ℓ log }, either G(w) ≤ 1 2n or R(w) ≤ log 2 n implies ⟨w, z i ⟩ ≥ 0 for all i ∈ [n]. Proof of Lemma C.4. If G(w) ≤ 1 2n , we have ℓ ′ (⟨w, z i ⟩) ≤ nG(w) ≤ 1 2 . Then by monotonicity of |ℓ ′ (•)| we have ⟨w, z i ⟩ ≥ 0. Similarly if R(w) ≤ log 2n , we also have ℓ(⟨w, z i ⟩) ≤ nR(w) ≤ log 2. Then by monotonicity of ℓ(•) we have ⟨w, z i ⟩ ≥ 0.Lemma C.5. For ℓ ∈ {ℓ exp , ℓ log } and any z 1 , z 2 ∈ R, we haveℓ ′ (z 1 ) ℓ ′ (z 2 ) -1 ≤ e |z1-z2| -1 (C.2) Proof of Lemma C.5. For ℓ = ℓ exp , ℓ ′ exp (z 1 ) ℓ ′ exp (z 2 ) -1 = e z2-z1 -1 ≤ e |z2-z1| -1 the inequality is from |e x -1| ≤ e |x| -1. For ℓ = ℓ log , ℓ ′ log (z 1 ) ℓ ′ log (z 2 ) -1 = 1 + e z21 + e z1 -1 = e z2 -e z1 1 + e z1 ≤ e z2 -e z1 e z1 ≤ e |z2-z1| -1Lemma C.6. For ℓ ∈ {ℓ exp , ℓ log } and any z 1 , z 2 , z 3 , z 4 ∈ R, we have ≤ e |z1-z2| -1 + e |z3-z4| -1 + e |z1+z3-z2-z4| -1ℓ ′ (z 1 )ℓ ′ (z 3 ) ℓ ′ (z 2 )ℓ ′ (z 4 ) -1 ≤ e |z1-z2| -1 + e |z3-z4| -1 + e |z1+z3-z2-z4| -1 (C.3) Proof of Lemma C.6. For ℓ = ℓ exp , ℓ ′ exp (z 1 )ℓ ′ exp (z 3 ) ℓ ′ exp (z 2 )ℓ ′ exp (z 4 ) -1 = e z2+z4-z1-z3 -1 ≤ e |z1+z3-z2-z4| -1 the inequality is from |e x -1| ≤ e |x| -1. For ℓ = ℓ log , ℓ ′ log (z 1 )ℓ ′ log (z 3 ) ℓ ′ log (z 2 )ℓ ′ log (z 4 ) -1 = (1 + e z2 )(Lemma C.7. For ℓ = ℓ log , and any w ∈ R d , we haveEQUATIONProof of Lemma C.7. Let r i = ℓ log (⟨w, z i ⟩) = log(1 + e -⟨w,zi⟩ ) and f (z) = 1 -e -z , then |ℓ ′ log (⟨w, z i ⟩)| = e -⟨w,z i ⟩ 1+e -⟨w,z i ⟩ = e r i -1 e r i = f (z i ). Therefore for any given R(w), finding min G(w t ) equals to the following optimization problem,min 1 n n i=1 f (r i ) s.t. n i=1 r i = nR(w), r i ≥ 0 for all i ∈ [n]Since f (z) is an increasing function and the increasing rate would be slow as z increase since f ′′ (z) < 0, we can easily derive that the aforementioned optimization problem will take the minimum at r i = nR(w) for some i ∈ [n] and r j = 0 for all j ̸ = i. Therefore, we can derive that,G(w t ) R(w) ≥ 1 -e -nR(w) nR(w) ≥ 1 - nR(w)2 by Taylor's expansion.The following result is the classic Stolz-Cesàro theorem. Theorem C.8 (Stolz-Cesàro theorem). Let {a n } n≥1 , {b n } n≥1 be two sequences of real numbers. Assume that {b n } n≥1 is a strictly monotone and divergent sequence (i.e. strictly increasing and approaching +∞, or strictly decreasing and approaching -∞) and the following limit exists:lim n→∞ a n+1 -a n b n+1 -b n = l.Then it holds that lim Justification: The abstract and introduction clearly outline the primary results and contributions 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 in 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 as long as it is clear that these goals are not attained by the paper. 


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

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: There are no major concerns about this paper. Below are minor comments and some areas for improvement:
- 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.
- 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.
- 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}$).
- (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)$.
- (page 1, line 25) Typo: reply on -> rely on

---
[Gunasekar et al. 2018] Characterizing Implicit Bias in Terms of Optimization Geometry, ICML 2018.

[Soudry et al. 2018] The Implicit Bias of Gradient Descent on Separable Data, JMLR 2018.
questions: 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.
- Is $\beta_1 \le \beta_2$ a necessary condition? What happens if we use Adam with $\beta_1 > \beta_2$?
- 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: 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.
paper_summary: paper_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. 

In 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.
strength_weakness: strength_weakness: At the moment, I have some concerns with the paper which are more fit to be discussed as questions.
questions: 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 ? 
2) 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: limitations: None
paper_summary: paper_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.
strength_weakness: strength_weakness: - The paper does not present results for a fixed learning rate and only considers a set of decreasing learning rates.

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

    - (Minor) In Assumption 4.3, ‘non-increasing’ should be ‘decreasing’ or ‘diminishing’.

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

- The paper does not comment on how optimal the obtained rates in Corollary 4.7 are.

**References:**

[1] Wang et al., Achieving Margin Maximization Exponentially Fast via Progressive Norm Rescaling, 2023.
questions: 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: limitations: There is no potential negative impact of this work.
paper_summary: paper_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$.
strength_weakness: strength_weakness: Despite the novelty of the theoretical claims, I still have several concerns, which I will discuss in the following.

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

    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.

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

**Reference**

[1] Wang et al. The implicit bias for adaptive optimization algorithms on homogeneous neural networks.

[2] Cattaneo et al. On the Implicit Bias of Adam.
questions: 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? 

2. How will adding stochastic sampling noise affect the implicit bias?
limitations: 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.  

The societal impact is not applicable to this work as it focuses on theoretical parts of Adam.

Comments: title: Thanks for the response
Reply to rebuttals
comment: Thank you very much with the detailed response. It helped clarify some of my confusions. I am happy to keep my currrent evaluation.
I thank the authors for the detailed rebuttal. The lack of a discussion on the optimality of the rates presents a weakness, so I am not raising my score, but I still believe the paper makes a good contribution, so I will maintain my score.
I thank the authors for the response.

If the transition is abrupt as explained by the authors, then there is no contradiction, which addressed my concern on this aspect..

On the other hand, from my perspective, it’s still important to clearly characterize the role of the stability constant and the abrupt transition, as well as the role stochasticity, for the reason that the setting would be more practical then.

Overall, I think this paper is a good addition to the implicit bias of Adam with zero stability constant in logistic regression.
Thank you for your support and detailed suggestions. We will make sure to include our discussions in the revised version of the paper.
Thanks for your prompt reply and for clarifying your question. We confirm that when $\epsilon\to 0^+$, the transition of the implicit bias is indeed abrupt. Consider Adam with stability constant $\epsilon$, and denote by $w_{t, \epsilon}$ its iterate at the $t$-th iteration. Then, the implicit bias of Adam with a fixed value of $\epsilon$ can be characterized by the limits: 

$\lim\_{t\to +\infty} \max\_{i\in[n]} \frac{\langle y_i\cdot x_i, w\_{t, \epsilon}\rangle}{\\|w\_{t, \epsilon}\\|\_2}$ and $\lim_{t\to +\infty} \max\_{i\in[n]} \frac{\langle y_i\cdot x_i, w\_{t, \epsilon}\rangle}{\\|w\_{t, \epsilon}\\|\_\infty}$. 

Mathematically, the abrupt transition of implicit bias when $\epsilon \to 0^+$ is then due to the fact that the limit $t\to+\infty$ and the limit $\epsilon\to0^+$ are not interchangeable:

$\lim\_{\epsilon\to 0^+}\lim\_{t\to +\infty} \max\_{i\in[n]} \frac{\langle y_i\cdot x_i, w\_{t, \epsilon}\rangle}{\\|w\_{t, \epsilon}\\|_2} \neq \lim\_{t\to +\infty}\lim\_{\epsilon\to 0^+} \max\_{i\in[n]} \frac{\langle y_i\cdot x_i, w\_{t, \epsilon}\rangle}{\\|w\_{t, \epsilon}\\|_2}$, and
 
$\lim_{\epsilon\to 0^+}\lim_{t\to +\infty} \max_{i\in[n]} \frac{\langle y_i\cdot x_i, w_{t, \epsilon}\rangle}{\\|w_{t, \epsilon}\\|\_\infty} \neq \lim_{t\to +\infty}\lim_{\epsilon\to 0^+} \max_{i\in[n]} \frac{\langle y_i\cdot x_i, w_{t, \epsilon}\rangle}{\\|w_{t, \epsilon}\\|_\infty}$.

Therefore, there is no contradiction. We hope the discussion above can address your question.
I thank the authors for the detailed response.

I would like to clarify that, as I pointed out in my review, I understand that the current work considers Adam without the stability constant. My point of the contradiction between the current paper and previous works lies in that how letting $\epsilon \to 0$ changes the implicit bias from the $\ell_2$ solution to the drastically different $\ell_\infty$-margin solution, e.g., is the transition smooth or abrupt? There exists a gap.

The rest of the rebuttals addressed my other concerns.
Thank you for the clarifications. I have thoroughly reviewed the rebuttal and have no further questions. I appreciate the authors' efforts and am happy to maintain my score, voting for acceptance. I look forward to seeing the discussions mentioned in the rebuttal incorporated into the revised manuscript.