Implicit Bias of Spectral Descent and Muon on Multiclass Separable Data
Authors: Chen Fan
Mark Schmidt
Christos Thrampoulidis
Venue: NeurIPS 2025 spotlight ()
Keywords: Implicit Bias
Implicit Regularization
Muon
Spectral Descent
Adam
Multiclass
Primary area: theory
TL;DR: Implicit bias for p-norm normalized steepest descent (NSD) and momentum steepest descent (NMD) algorithms  in multi-class linear classification with cross-entropy loss.

Abstract: Different gradient-based methods for optimizing overparameterized models can all achieve zero training error yet converge to distinctly different solutions inducing different generalization properties. We provide the first complete characterization of implicit optimization bias for p-norm normalized steepest descent (NSD) and momentum steepest descent (NMD) algorithms in multi-class linear classification with cross-entropy loss. Our key theoretical contribution is proving that these algorithms converge to solutions maximizing the margin with respect to the classifier matrix's p-norm, with established convergence rates. These results encompass important special cases including Spectral Descent and Muon, which we show converge to max-margin solutions with respect to the spectral norm. A key insight of our contribution is that the analysis of general entry-wise and Schatten p-norms can be reduced to the analysis of NSD/NMD with max-norm by exploiting a natural ordering property between all p-norms relative to the max-norm and its dual sum-norm. For the specific case of descent with respect to the max-norm, we further extend our analysis to include preconditioning, showing that Adam converges to the matrix's max-norm solution. Our results demonstrate that the multi-class linear setting, which is inherently richer than the binary counterpart, provides the most transparent framework for studying implicit biases of matrix-parameter optimization algorithms.

Implicit Bias of Spectral Descent and Muon on Multiclass Separable Data
Chen Fan
Department of Computer Science University of British Columbia
Mark Schmidt
Christos Thrampoulidis
Department of Computer Science University of British Columbia Canada CIFAR AI Chair (Amii)
Department of Electrical and Computer Engincering University of British Columbia
Abstract
Different gradient-basse methods for optimizing overparameterizee models can all achieve zero training error yet converge to distinctly different solutions inducing different generalization properties. We provide the first complete characterization implicit optimization bias for p-norm normalized steepest descent (NSD) and momentum steepest descent (NMD) algorithms in multi-class linear classification with cross-entropy loss. Our key theoretical contribution proving that these algo- rithms converge to solutions maximizing the margin with respect to the classifier matrix's 's p-norm, with established convergence rates. These results encompass important special cases including Spectral Descent and Muon, which we show converge to max-margin solutions with respect to the spectral norm. A key insight of our contribution is that the analysis of general entry-wise and Schatten p-norms can be reduced to the analysis of NSD/NMD with max max-norm by exploiting a natural ordering property between all p-norms relative to the max-none and its dual sum- norm. For the specific case of descent with respect to the max-norm, we further extend our analysis include preconditioning, showing that Adam converges to the matrix's max-norm solution. Our results demonstrate that the multi-class linear setting, which is inherently richer than the binary counterpart, provides the most transparent framework for studying implicit biases of matrix-parameter optimization algorithms.
Introduction
The ever-increasing training cost of large language models (LLMs) has demanded better optimizer designs with improved performance and efficiency [11, 1, 23]. The de facto standard optimizers for deep learning training Adam and AdamW [33, 39]. However, these algorithms that employ diagonal preconditioners to independently adjust the learning rate of each coordinate, may fail to capture their inter-dependencces and fully leverage the geometry of the loss landscape [79]. This has spurred a series of research efforts on improving Adam or Adam computational efficiency [20, 24, 51, 80], with LLM--triniig the target application domain [31, 67, 46, 37].
noticeable work by Jordan et al. [31] proposed the Muon optimizer, which was shown to have remarkable performances on NanoGPT benchmarks. More recently, it has been shown that Muon be used for large-scale LLM training with the potential to replace Adam W as the standard choice [37]. The key step in Muon is orthogonalize the updates via the Dewton-Schulz iteration [31, 7J. More precisely, the update (denoted as A) (approximately) replaced by the product of its singular-vector
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Table 1: Summary of margin convergence rates for NSD and NMD algorithms of different norm constraints for linear multiclass separable data with the CE loss. The (truncated) SVDs of the gradient and momentum are denoted
V = UEVT and M = ÜÜVV respectively.
Method
Norm Constraint
Update A
Reference
Rate
NGD
Hazan et al. [25]
Unit I--12-bbll
V
NMD-GD
M
Cutkosky and Mehta [14]
SignGD
sign(
Bernstein al. [8]
Unit Il-llax--bal -ball ball
Signum
sign( M
Bernstein et al. [8]
Spectral-GD
UVT
Bernstein and Newhouse [7]
O log 1+=2
Unit I11-Illo- -ball
Muon
ÜVT
Jordan et al. [31]
O
dloog 1+
pi72
We consider EMA-stylc momentum of the form (5).
NGD and SignGD rates are the same as Spectral-GD; Signum and NMD-GD rates are the same as Muon.
matrices UV (where the (truncated) singular value decomposition (SVD) of A is A UEV?). Even though the benefits of orthogonalization that it could promote updates in directions of small magnitudes given the weight matrices are typically low-rank. Moreover, if the above SVD approximation is exact and gradient accumulations off, then Muon becomes spectral descent [13, 7J. which is the (normalized) steepest descent w.r.t the spectral norm [7]. As noted by Bernstein and Newhouse [7], spectral descent is also Shampoo (which won the AlgoPerf competition [52, 15J) without accumulations in preconditioners. Thus, Muon can be viewed as (approximate) Shampoo when both optimizers are without accumulations. In essence, we observe that one important ingredient of Muon and Shampoo (without accumulations) is the ppectral-descent step.
fully understood, Jordan et al. [31] pointed out
turned
W W- UVT where F
Theoretical investigations of spectral descent or Muon mainly focus on characterizing the convergence rates of the algorithm (e.g., the rate of decrease of the gradient norm in the non-convex setting 36, 46]). However, modern machine learning models are overparameterized, leading to multiple weight configurations that achieve identical training loss but exhibit markedly different generalization properties [78, 6]. The key insight is that gradient-based based methods inherently prefer "simple" solutions according to optimizer-spedt
notions simplicity. Understanding this implicit bias/regularization requires analyzing not just loss convergence, but the geometric trajectory of parameter updates throughout training. To this end, our work aims to address the fundamental question:
What is the implicit bias of spectral descent (and its momentum variants) in linear multiclass classification with separable data and prss-entropy loss?
The multiclass setting where the parameter is matrix, is a natural place to study the class of spectral- descent algorithms, and provides an inherently richer setting. Our work captures this richness by establishing convergence with respect to not only entry-wise matrix norms, but also matrix Schatten norms. Hence, while the focus is on spectral descent and Muon, the analysis establishes implicit bias rates for wide family of algorithms (Table 1), and we state the results in the most general form from the perspective of steepest descent with (unit) norm-ball constraints. Our contributions are as follows:
1. For multiclass separable data trained with the cross-entropy (CE) loss, we show that the iterates of normalized steepest descent (NSD) defined with respect to (W..t.) any matrix entry-wise or Schatten norms converge to solution that maximizes the margin defined w.r.t. the same norm, with a rate O (ztz/ ). This includes sign descent (entry-wise max-norm) [8], normalized gradient descent (entry-wiss wise 2-norm) [25], and spectral descent (Schatten no-morm) [7] as special cases. To achieve this, we introduce a unified analysis framework that relates entry-wise and Schatten p-norms to the entry- wise max-norm, and construct proxy function for the loss that closely traces both its value and gradient. We also show the same machinery applies to other multiclass losses such the exponential loss [41] and the PairL-ggLoss [72].
2. Under the same setting, we utilize the same framework and proxy function to show that a O (1zz margin convergence rate also holds for normalized momentum steepest descent (NMD). This includes the following algorithms in analogy to the ones above: sign momentum descent [8].

---

normalized momentum gradient descent [14], and Muon [31]. The key step of the analysis is to use the proxy function bound the sum-norm difference between the gradient and the momentum (i.e., the exponential moving averages (EMA) of the gradient), which translates to bound on the dual norm through the fundamental corm-relationships used in the study of NSD. The margin convergence rates of various algorithms are summarized in Table 1. Furthermore, we extend the analysis to Adam (without the stability constant) and show its iterates maximize the margin w.r.t the matrix max-norm (proof details and numerical validations in App. G).
We experimentally verify our theoretical predictions across all considered algorithms. First, for sign descent (SignGD) and Signum, we demonstrate that solutions favor the max-norm margin over the 2-norm margin-thhe the opposite behavior to normalized gradient descent (NGD) and normalized momentum gradient descent (NMD-GD). Moreover, we show that both spectral descent (Spectral-GD) and Muon favor the spectral-norm margin over the other norms. We further extend the experiments to the non-linear setting with two-layer neural network. We observe the (unnormalized) spectral-norm margin of Spectral-GD and Muon grow faster than other algorithms. Hence, the norm-preference trend in the linear setting can also exhibit in the non-linear setting.
2 Preliminaries
Notations Matrices, vectors, and scalars are denoted by A, a, and a respectively. For matrix A, we denote its (i, entry A j]. and for vector a, its i-th entry afi] a,. We consider entry- matrix p-norms defined || (Ei, (lP))/, Central to our results are: the infinity norm, denoted as ||
A[i j|l and called the max-norm, and the entry-wise == ||A||| Enj i. [A]. The entry-wise 1-norm is dual to the max- norm. For vectors, the max-norm is equivalent to the infinity norm, denoted as ||a|| while we denote the l norm as ||a]|ı- We further denote the Schatten p-norm of A as |||A|||, := (E a!) 1/p where 01, o,,..., J, are the non-zero singular values of A. Let r = rank rank(A), then special cases of Schatten p-norm include: nuclear norm |||||||| = E
|| || maxij
1-norm, denoted as
Frobenius norm |||A|||| = Ei= of and spectral norm |||Alll = 01. To simplify the discussions, we sometimes write || (dropping subscripts) to refer to any entry-wise or Schatten p-norm with p 2 1. We denote by |||||- the dual-norm with respect to the standard matrix inner product (A, B) = (r)ATB). We denote the gradient and its value at iteration / as V VL(W) and V VL(W,) respectively.
Let : I + A k-1 the softmax map of k-dimensional vectors to the probability simplex A exp(ale)) *
such that for any a E R² holds that S(a) E.ejy exprale]]] E k-1 Let (T) denote the e-th entry of S(b). Let (a) = diag(S(a)) - S(a)S(a)T denote the softmax gradient, with diag(-) a diagonal matrix. Finally, let {e. be the standard basis vectors of IR and indicator diy be such that 6,3- = 1 if and only if = j. For any integer k, [k]] denotes ki).
k...
Setup Consider multiclass classification problem with training data h....., hn and labels y1..... Vn. Each datapoint h E IR is a vector in a d-dimensional embedding space (denote data matrix H = [hi,.... hh,]' E [==xd), and each label y: E [K] represents one of k classes. We assume each class contains at least one datapoint. The classifier fw Rd + R is a linear model with weight matrix W Rxxd The model outputs logits L, = fw(h,) = Wh, for E [m)) which are passed through the softmax map to produce class probabilities ((c = (P.).
We train using empirical risk minimization (ERM): LERM(W) == Eie(m) e (Wh,y)) where the loss function é takes as input the logits of a datapoint and its label. The predominant choice in classification is the CE loss
L(W) -w)==--> EEin] 72
log (Sy, (Wh:)).
(1)
We focus our discussions on the CE loss due to its ubiquity in practice. However, our results hold for other multiclass losses such as the exponential [41] and the PairL [72] (see App. F). Define the maximum margin of the dataset w.r.t. any entry-wise or Schatten p-norm as
y max|wils minge(n], cbn (e ee)) Wh.
(2)
3

---

Optimization Methods
We study iterative algorithms that update the weight matrix by W4+1 W - T/ A.
For the NSD family [10], the update direction ! w.r.t. the norm ||-1|
A = arg m v., A).
(3)
Note that this reduces to SignGD, Coordinate Descent (e.g., Nutini et al. [44]), NGD when the max-norm (i.e. I/))) the entry-wise 1-norm (i.e. Ilm , or the Frobenius Euclidean-nowd (i.e. (1-112) is used, respectively. Concretely, the update directions for SignGD and NGD are:
SignGD: A, sign( (v.). and NGD: A. = Ve/lVelle
where the sign(-) and division operations are applied entry-wise. In the special case of spectral norm (i.e. I1l-Illoc). this becomes the Spectral-GD, for which A. = U,V." where U, and V, are the left/right singular matrices of V respectively (i.e., V. = U,E,V V." with singular values in Σ, > 0 arranged in non-increasing order). Finally, note that the Schatten 2-norm case reduces NGD (as III-IIl2 = l1-112).
We also consider the NMD family with the following update direction w.r.t. the norm ||-11
A == arg max A (M, A)
(4)
where the momentum M, is computed as the EMA of the gradient given by
M, M + (1-31) V.)
(5)
This form of momentum is also known as the heavy-ball or the SGDM-style momentum [47, 19, 38]. Thus, an NMD algorithm chooses the update direction (among all feasible directions in the unit [|-l--ball) that best aligns with the momentum instead of the gradient direction (as chosen by an NSD algorithm). Similar to above, when the max-norm and the Frobenius norm are used, the resulting Signum and NMD-GD update directions are:
Signum: A. = sign(M,), and NMD-MD: A, M
When spectral norm is used in (4), this becomes Muon? for which the SVD is on M, (i.c. M, = U,E, V and the update direction is A, = U.V. Note that Muon reduces to Spectral-GD when the momentum parameter 31 is set to 0. Similar reductions also hold for Signum (to SignGD) and NMD-GD (to NGD) as well.
Establishing the implicit bias of the above mentioned gradient- based optimization algorithms requires the following assumptions. First, we assume data are linearly separable, ensuring the margin 7 is strictly positive, an assumption routinely used in previous works [53, 48, 22, 43, 75]. Assumption 1. There exists W Rexd such that miney (ey. e.) Wh: 0 all E [m).
Assumptions
In this work, we consider learning rate schedule ne = O (())), where (0, 1). Such schedules have been studied in the convergence and implicit bias of various optimization algorithms (e.g., Bottou et al. [9], Nacson et al. [43], and Sun et al. [55]) including Adam [77].
Assumption 2. The learning rate schedule {n+ is decreasing with respect and satisfies the following conditions: lim = O and Et= Th Co.
Assumption 3 can be satisfied by the above learning rate for sufficiently large t as shown in Zhang al. [77, Lemma C.I]. It is used in our analysis of NMD and Adam.
Assumption 3. The learning rate schedule satisfies the following: let B E (0, and > 0 be two constants, there exist time to N and constant 02 c2(c1, > such that 3d Ei- ni-- - 1) S 021 for all 1 Z to-
Finally, we assume that the 1-norm of the data is bounded. Similar assumptions were used in Ji and Telgarsky [26), Nacson et al. [43], Wu et al. [75], and Zhang et al. [77].
Assumption 4. There exists constant B > 0 such that ||h/ll S B for all i E [n].
For p E (1, oo). the norms || ||p and |||-I| are strictly convex, thus there is unique maximizer defining the update in Eqn. (3). For p 1, co the maximizer not necessarily unique and our results hold for any choice of A. the set of maximizers: see e.g. Ziętak [81].
'The implementation in Jordan et al. [31] uses Nesterov-type momentum: Newton-Schan iteration applied to
M, + V, instead of 8:M V, [37].

---

3 A Unified Framework with a Proxy Function
Analyzing margin convergence begins with studying loss convergence through second-order Taylor expansion of the CE loss (recall that S' (v) diag(v) 22 vo
L(W + A) = ((W) + (VL(W), A) 2n Σ A + +oll)) 12),
(6)
ic(n)
To bound the loss at (+1+ W, W 77 Ar we must bound both the first-order and second-order
terms in (6). For NSD updates in Eq. (3), the first term evaluates to -Tj. [V((W)l (recall that
I| is the dual norm). This leads to two key tasks: (I) Lower-bounding the dual gradient norm; (2)
Upper-boundie
the second-order term.
For the proof to proceed, these bounds should satisfy two desiderata: (1) They are expressible the same function of W, call it ((W). up to constants. (2) The function ((W) is a good proxy for the loss for small values of the latter. The former helps with combining the terms, while the latter helps with demonstrating descent. Next, we obtain these key bounds for the CE loss by determining the appropriate proxy G(W).
Besides the need for a proxy (W),, we use the following facts about the sum-norm dominating any entry-wiie/Schatten p-norm. Concretely, for any matrix A and any p 2 1:
|||| ll mAx S |||, S |l and ||xx S ||l| S || sum
(7)
These relationships (proved in Lemma 11 in App. C) are crucial for unifying the analysis of NSD and NMD) algorithms w.r.t. either the entry-wise or the Schatten norms (details below).
Construction of ((W) Before showing our construction for the CE loss, it is insightful to discuss how previous works do this in the binary case with labels yb.s E {+1]. classifier vector w E Rd and binary margin % = max <1 minke[m] 3b, h.- For exponential loss, Gunasckar et al. [22] showed that [[V[(w)]] 2 (ow). For logistic loss E(t) = log(1 + exp(-t)) Zhang al. proved || V 2 (w)) where ((w) 1 E (6' w h2)l and l is the first-order derivative. In both cases, one can take the common form Go(w) = A Σ.= 16" (y/,, h.)]. The proof relies on showing y I min HTrl| via Fenchel Duality [59, 22] and appropriately choosing r.
n
In the multiclass setting, where the loss function is vector-valued, it is unclear how to extend the binary proof or definition of ((W). To this end, we realize that the key is in the proper manipulation of the
gradient inner product (A, V VLW)) (for arbitrary matrix A E [gxxdd The CE gradient evaluates to VL(W) -i (ey,- S W h: /2, and using the fact that S S(W1) h.) E A h-1 it turns out that we
can express (details in Lemma 9): (A. VL(W)) = = Eiem Eesgy Se W W.,.)ee.. ec) Ah.
This motivates defining G(W)
((W)= = n Σ vE[m) (1 Sy (Wh:)).
(8)
The lemma below, following from the inner inner-product calculation above and our definition of (W). confirms this is the right choice. For convenience, denote $ie == S. (Wh;), for i E [n], E [k).
Lemma 1 (Lower bounding the gradient dual--orm). For any W R and any entry-wise or
Schatten p-norm |.:1| with p 2 1, it holds that [[VC(W)] 2 g (W), where ||-I|= is the norm-
The lemma completes the first task: lower bounding the gradient's dual norm. Importantly, the factor in front of ((W) is the margin 7 w.r.t. the norm ||. which is crucial in the forthcoming analysis.
G(W) and second-order term We now show how to bound the second-order term in (6). For this, we establish the following essential lemma whose proof relies on the relationships in (7).
Lemma For any entry-wise or Schatten p-norm I|=Il with p 2 1, any s k- in the k-dimensional
simplex, any index e [k], and v E IR. holds that
t (diag(s) 33 u S 4(1 sc)llve
5

---

Proof. Let S == diag(s) - ss and 2 1 such that 1/p + 1/q = 1. By norm duality, it holds that
v Sv = tr (See) s | vo <
||||
sum vv ||.
where ll.llg is the dual of ||-I| and the second inequality is by (7). Direct calculation yields ||S||sum 2 2 sc(1 8c). The advertised bound then follows by noting the following EcE|M Se 8c) 2(1 82) for any E [k]] (verified in Lemma 13 in App. C).
Next, we apply the above lemma with v + Ah; and c y/. and further the inequalities: |alo 1|p ||01| S || A !i for entry-wise norms and |1/00" ||I |
= |ll 1 || <
||| | | for Schatten norms. Together with Ass. 4, this upper bounds the second-order term in
the CE loss expansion in terms of the proxy function:
1 - Eie πi
2
iE(m) (Wh.))
Properties of G(W) We now show that ((W) meets the second desiderata: being a good proxy for the loss L(W). This is rooted in the elementary relationships between G (W) and L(W), which are used in the various parts the proof. Below, we summarize these key relationships.
Lemma 3 (Properties of G(W) and L(W)). Let W E Rxd, The followings hold: (i) Under Ass. 4. 2B- G(W) 2 [[) (ii) 1 2 9(W)
Z(W) 2 1 nl(W), (iii) W satisfies C(W) s log2 or
g(W) S 1. then L(W) - WV). 2n
Lemma (i) extends Lemma by establishing a sandwich relationship between G(W) and the gradient's dual norm. The lemma's statements (ii) and (iii) show that G(W) can substitute for the loss it lower bounds L(W) and serves as an upper bound when either L(W) or G(W) is sufficiently small. Specifically, the ratio G(W) L(W) converges to as the loss decreases, with the convergence rate depending on the rate of loss decrease. The key property (ii) may seem algebraically complex, but it turns out (details in Lemma 18 in App. C) that both sides of the sandwich relationship follow from the elementary fact that Vo. 0:
-= <
x /2.
4 Implicit Bias of Normalized Steepest Descent
We now leverage our construction of G(W) to show that the margin of NSD's iterates converges to the data margin defined w.r.t. the same entry-wise or Schatten p-norm that is used to define the algorithm (refer to eqns. (2) and (3) for the definitions of margin and NSD). We only highlight the key steps in the proof and defer details to App. D)
NSD Descent We start by showing descent property. By applying Lemmas I and 2 lower and upper bound the first and second order terms in Eq. (6) yields
G(W, -WW
((W S L(W)) - (W,) + 2n/ Bd (W,) sup (E(o.1)
g(W,)
Algebraic manipulations of the definition of G(W) and the relationships in (7) allow us to bound the ratio in the right hand side.
Lemma 4 (Ratio of ((W)). For any E 10, have the following:
G(W-um4) 9(W)
2B All S eB (note that the second inequality is by (7)).
From this and || A < for NSD, we obtain
((W+1) S L(W)) mm - - (W.,)
where as, BBm /7. Given decay learning rate of the form 7)c ( we can conclude that the loss starts monotonically decrease after some time.

---

NSD Unnormalized Margin We now use the descent property in (9) to lower bound the un- normalized margin. An intermediate result towards this recognizing that sufficiently small loss ((W) log guarantees W separates the data (Lemma 19 in App. C). The descent property ensures that NSD iterates will eventually achieve this loss threshold, thereby guaranteeing separability. The main result of this section, shows that eventually the iterates achieve separability with a substantial (unnormalized) margin.
Lemma 5 (NSD Unnormalized Margin). Assume there exists such that ((W) S Then, it holds that for all t 2 (( = eBp
log2 n
v4 >
g(W)) L(W.)
[-1
(ev: e W,, 21 Σ kE|o)eeA
min
O1ea
Σ
(10)
s=1
NSD Margin Convergence Proceeding from Eq. (10) requires showing the convergence of the ratio G(W). The two key ingredients given in Lemma 3 (ii) and (iii.. Lemma (ii) suggests that Z(W)-
is sufficient to study the convergence of L(W), which captured in (9). However, to obtain an explicit rate via (9), we need to rewrite g(W,) in terms of L(W)). This is where Lemma 3 (iii) helps. Putting them together, we arrive at the following theorem (see Thm. and Cor. 1 for details).
Theorem Suppose that Ass. 1, 2, and 4 hold, Set learning rate T) O ((tt)) The following holds for the margin gup of NSD's s iterates
y minie(n) (Cy, - -c) Wih,
<0( logt + n f2/2
[Well
Remark 1. For margin convergence rates of NSD, Nacson et al. [43] showed rate of O (19g)) the binary setting, limited to the entry-wise p-norms and the exponential loss. Compared to this, our results hold for the more practical setting of multiclass data and CE loss. To the best of our knowledge, this is the first non-asymptotic result on the implicit bias of spectral-GD for linear multiclass separable data, and it holds for other p-norms well. Upon completion of this work, we became aware of an update on the arXiv version of Tsilivis et al. [63], which includes an extension of their previous results to steepest descent w.E.. the spectral norm. In comparison ours, their gradient-flon flow analysis applies to homogeneous neural networks with the restriction of infinitesimal step-sizes. Moreover. it does not include normalization nor momentun (like Muon, which we analyze), and the convergence is (asymptotic) to a KKT point of a spectral- margin maximization problem.
5 Implicit Bias of Normalized Momentum Steepest Descent
In this section, we study the implicit bias of NMD algorithms (proof details App E). Similar to Sec. its updates are defined w.r.t. either the entry-wise or the Schatten norm ||-I|- The analysis relies on the relationships in (7) and we show the same proxy function G(W) naturally appears. Given that the NMD updates satisfy |ll < 1, the second-order term in (6) is bounded in the same way as NSD. The main difference is in bounding the first-order term as shown by the following lemma.
Lemma 6. Let Ω = M, v It holds for all 2 0 that
We11 - W.) < 2nl (W,)
Given the relationships in (7) hold for any p 2 1, we can bound the dual norm of || via its sum norm (i.e. [1t]|-- < [| ). Given the goal is to bound all the terms in the Taylor expansion (6) via the proxy function G( W.). natural next step to bound [S2 using the same proxy function. To do this, we decompose the proxy function per-class-wing wise, and apply the per-class proxy functions to bound the entries of 22 associated with their corresponding classes. Concretely, we write the function G(W) in two equivalent ways: ((W)= = Σeejh àt Eiejn,
Siyi)
Enelki EiElnl. Sic, which motivate the following definitions of the per-class proxy functions:
G. = 1/10 E (n (1 - Li
-. and (.(W) = =//1 Σ (E(n))an Sic-
7

---

Next, we bound the entries in each row of S2 (thus belonging to the same class) via the corresponding proxy functions (W,)) and 2. (W.) to arrive at the following lemma. Its proof utilizes the nice properties of softmax map given in Lemma 15 in App. B.
Lemma 7. Suppose that Ass. 1, 2, and 4 hold. Let [k] and j E [d]. There exists time to such that for all 2 to and for aM == B(1 - 31)02:
[M[c,]] (1 si (.C(W)) jll amn (Gc + (w)))
Given the result Lemma 7, we can show that [ - VV. + a. Te (W.). where Te(W, (W.) is defined to be Te (W.) G(W,) + Q(W,) Then, we sum over indices e E [k] and j E [d] and apply | S 2B ((W) (from Lemma (i)) to obtain:
Lemma 8. It holds for all 1 2 0 that ||Sz]] S / G(W.) - 20
This completes the bound the first-order term for NMD algorithms via the proxy G (W). The rest proof follows similar steps as NSD. We note that without the above per-class decomposition, an extra k-factor would appear in the second term of the bound on ||S2 (and thus also show up in the final rate). We state the main theorem for NMD algorithms.
Theorem 2. Under the setting of Lem. 7, the margin gap of NMD with T/. = ((ttZ) ) is O 2-logg--dd
(172
Remark 2. Wang et al. [69] studied implicit bias of un-normalized GD with momentum, and showed its iterates converge asymptotically to the max 2-norm margin solution. In contrast, our rates are non-asymptotic and cover much wider family of algorithms converging non- non-Euulidean geometric margins (W.Et. entry-wise/Schatter norms). Note the convergence rate of NMD matches that of NSD (Thm. 1) up a factor of d. It could be interesting remove this dependence in a fulure work.
Implicit Bias of Adam Finally, observing that Adam [33] (without the stability constant, i.e., eqns (33a), (33b), and (33c) in App. G) shares the same form of momentum as NMD and the (entry-wise) updates are bounded by some constant as shown Zhang et al. [80] and Xie and Li [76]. Thus, our analysis extends to Adam. Concretely, a similar proof strategy can be adapted once a bound on the second gradient moment via the proxy function is established (Lemma 35). In App. G, we prove a O( +nd
max-norm margin convergence rate for Adam (details in Thm. 5 and Cor. 2).
g1/3
Experiments
Synthetic Experiments We generate snythetic multiclass separable data follows: k = 10 class centers are sampled from a standard normal distribution; within each class, data is sampled from normal distribution (000, o² 0.1. We set d 25, sample 50 data points for each class, and ensure that margin is positive (thus data is separable). We run different algorithms to minimize CE loss using 7)- Re (no 0.1 for SignGD and NGD; no 0.05 for Spectral-GD and Muon), where (based on our theorems) a is set to 1/2. We apply truncated SVD on the gradient and momentum for Spectral-GD and Muon respectively. Data margins w.r.t. different norms are found via CVXPY [17]. We denote max- max-margin classifiers defined w.r.t. the 2-norm, the max-norm and the spectral-norn as V2, Vz.. and Vepee: respectively. Based on the margin-gap results in Figure 1, we observe that SignGD, NGD, and Spectral-GDD favor max-norm, 2-norm, and spectral-norm margin respectively. Besides this, the behavior of Muon is very similar to that of Spectral-GD (in agreement with our theories). Figure 2 further confirms that the iterates of these algorithms correlate well with the corresponding max margin separators. Experiments on Signum, NMD-GD, and Adam are provided in App. A and App. G.
Two-layer Neural Network We extend the experiments to the non-linear classification setting using the cross-entropy loss. We sample 100 data points from each of the 10 classes of the MNIST dataset [35]. The model is two-layer neural network with the hidden dimension being 100 (the first and second layer weights are denoted as V and W respectively). The training is done in two ways: (a) Train the first-layer weight with the second-layer weight fixed and (b) Train both the first and second-layed weights. For options (a) and (b), the respective spectral-norn margins of the overall network are defined as
(eg, - -ee) "'''WooVi
V.W = min (ey, ex) Wo (Vh.) (b)%
(a) Ta min iE(n),ctvi
|||b
se max || bc W [l
8

---

where a--) is the sigmoid function. In Figure 3, we track the quantities Vv (Figure 3a and 3b) and VV,WW, (Figure 3c and 3d) as function of the iteration counter t. For both definitions, observe that the spectral-norm margin the iterates of Spectral-GD and Muon grow faster than other Pi Herl
(a) SignGD
(b) NGD
(c) Spectral- GDD
(d) Muon
Figure I: (a) We normalize the iterates of SignGD w.r.t. the max-norm (denoted as W2). compute the margin (denoted Tw,). then plot its difference data margins 7I|- Iss ?]|-I|a and M|1-I11 (note that the margin difference is further divided by the corresponding data margin for comparisons). SignGD favors the margin defined w.r.t. the max-norm. (b, and Same as (a) with SignGD
replaced by NGD (2-norm), Spectral-GD (spectral-norm) and Muon (spectral-norm respectively. NGD favors the 2-norm margin, while Spectral-GD and Muon favor the spectral-norm margin.
Comdestion uttn 10
190
60a0
080
0.0
0.7
19
10
15
(3) SignGD
(b) NGD
(c) Spectral GD
(d) Muon
Figure 2: (a) Correlations between the iterates of SignGD (W,) and margin separators V.c. (W.V .V
22, and Vspac against iterations (correlation defined as [WIlllV V 1 (b, c, and d) Same as (a) with SignGD replaced by NGD, Spectral-GD and Muon, respectively, SignGD and NGD correlate well with Vo and V2, respectively, while Spectral-GD and Muon correlate well with Vsper-
IND
GD
MSo Spectral -DD
MDD CD
Spectral-
Musi
Muan
-1.
Iuraoora
(a) Single Layer(".)) V.
(b) Single Layer("a)
(c) Joint Training( V.W,
(d) Joint Training(Y)
Figure 3: (a) Spectral-norm margin 7/ as a function for SignGD, NGD, and Spectral-GD. (b) Same (a) with algorithms replaced by Signum, NMD-GD, and Muon, respectively. (c) Spectral- norm margin 7 V. as function of for SignGD, NGD, and Spectral-GD, (d) Same (c) with algorithms replaced by Signum, NMD-GD, and Muon, respectively.
algorithms. Hence, the observations in the linear settings also hold in the non-linear settings.
7 Related Works
Starting with GD, the foundational result by Soudry et al. [53] showed that gradient descent op- timization of logistic loss on linearly separable data converges in direction to the La max-margin classifier at rate O(1/ O(1llo)()). Contemporaneous work by Ji and Telgarsky [26] generalized this by relaxing the data separability requirement. Ji et al. [29] later connected these findings to earlier work on regularization paths of logistic loss minimization [49], which enabled extensions to other loss functions ge.g., those with polynomial tail decay). More recently, Wu al. [75] extends these results to the large step size regime with the same O(1/ log(t)) rate. The relatively slow convergence rate to

---

the max- max-margin classifier motivated investigation into adaptive step-sizes. Nacson et al. [43] showed that NGD with decaying step-size Ti: = 1/vł achieves L2-margin convergence at rate O(1/VB) This rate was improved to (L/t)) by Ji and Telgarsky [28] using constant step-sizes, and further to ((1/t²) through a specific momentum formulation [30]. Besides linear classifications, implicit bias of GD has been studied for least squares [21, 22, 51, homogeneous [40, 27, 74] and homooenegse
neural networks [12], as well as matrix factorization [21]; see Vardi [64] for survey.
All the above mentioned works focus almost exclusively binary classification. The noticeable gap in analysis of multiclass classification in most existing literature is highlighted by Thrampoulidis et al. [6]], and more recently emphasized by Ravi al. [48], who extended the implicit bias result of Soudry et al. [53] to multiclass classification for losses with exponential tails, including CE, multiclass exponential, and PairLogLoss. Their approach leverages framework of Wang and Scott [73] that allows multiclass losses and separability conditions to be written in margin- forms similar to binary cases. However, these works only focus on GD with the Le-geometry. In this work, we consider a wide range of algorithms with different geometries for multiclass classification.
Beyond GD, Gunasekar et al. [22] and Nacson et al. [43] showed that steepest descent w.r.t. entry- wise p-norms yields updates that in the limit maximize the margin w.r.t the same norm. Sun et al. [54, 55] showed that the iterates of mirror descent with the potential function chosen as the p-th power of the p-norm converge to the classifier that maximizes the margin w.r.t. the p-norm. In both cases, the convergence rate is slow at O(1/ log (f)) Wang et al. [70] further improved the rates for both steepest descent and mirror descent when E (1, 2). Note that all these results apply only to the exponential loss. More recently, Tsilivis et al. [63] showed that the iterates of steepest descent algorithms converge to a KKT point of a generalized margin maximization problem in homogeneous neural networks. Moreover, the implicit bias of Adam (with or without the stability constant) has been studied in both linear and non- -inear settings. Wang et al. [68] demonstrated the normalized iterates of Adam (with non- non-neglii stability constant) converge to a KKT point of a L -argin maximization problem for homogeneous neural networks. Zhang et al. [77] studied the implicit bias of Adam without the stability constant on (linearly) binary separable data. They showed that unlike GD, the Adam's 's iterates converge to solution that maximizes the margin w.r.t the -nom.. The study of excluding the stability constant also the focus of another recent work on the implicit bias of AdamW [76], where the authors again establish that convergence aligns with the Lo geometry.
8 Conclusion
We have characterized the margin convergence rates of Spectral-GD and Muon for multiclass linear separable data. Given they are special cases of NSD and NMD w.r. the spectral norm, the analysis is done on a wider scale by studying NSD/NMD w.r.t any entry-wise or Schatten p-norms. Thus, the rates also hold for optimizers of other geometries, such the sign-descent (max-norm) or gradient- descent (2-norm) family. We further extend the analysis to Adam using the same framework. Future directions include removing the factor-d from the bound of NMD, obtaining a tighter convergence rate for Adam, and studying other related algorithms such as Shampoo that involves non- -idiggaa preconditioners. It is also important to extend our results to (multiclass) non-separable settings [60] and nonlinear models such as diagonal neural nets [45], self-attention mechanisms [58, 4, 57, 66, 32] and homogeneous neural nets [40, 63, 12], helping further bridge the gap to deep learning practices. Finally, from a complementary statistical perspective, future work could seek identifying specific scenarios where margin maximization with respect to norms other than Frobenius leads to better generalization (extending a long line of prior works, e.g., [50, 16, 34, 42, 71, 18, 56, 65, 2, 62).
Acknowledgement
This work is funded partially by NSERC Discovery Grants RGPIN-2021-03677 and RGPIN-2022- 03669, Alliance GrantAL.LRP 58 881088-2,, CIFAR AI Catalyst grant, and the Canada CIFAR AI Chair Program.
References
[1] Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, 1lge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al. Gpt-4 technical report. arXiv preprint arXiv:2303.088744 2023.
10

---

[2] Danil Akhtiamov, Reza Ghane, and Babak Hassibi. Regularized linear regression for binary classification. In 2024 IEEE International Symposium on Information Theory (ISIT), pages 202-207. IEFE, 2024.
[3] Kang An, Yuxing Liu, Rui Pan, Shiqian Ma, Donald Goldfarb, and Tong Zhang. Asgo: Adaptive structured gradient optimization. arXiv preprint urXiv:2503.20762. 2025.
[4] Davoud Atace Tarzanagh, Yingcong Li, Xuechen Zhang, and Samet Oymak. Max-margin token selection in attention mechanism. Advances in neural information processing systems, 36: 48314 48362, 2023.
[5] Navid Azizan, Sahin Lale, and Babak Hassibi. Stochastic mirror descent on overparameterized nonlinear models. IEEE Transactions Neural Networks and Learning Systems, 33(12): 7717-7727, 2021.
[6] Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine- learning practice and the classical barianee trade-off. Proceedings of the National Academy of Sciences, 116632):15849-1553)
2019.
[7] Jeremy Bernstein and Laker Newhouse. Old optimizer, new norm: An anthology. arXiv preprint arXiv:2409.20325 2024.
[8] Jeremy Bernstein, Yu-Xiang Wang, Kamyar Azizzadenesheli, and Anima Anandkumar. signsgd: Compressed optimisation for non-convex problems. arXiv preprint arXiv: (tt::/880200444 04434, 2018.
[9] Léon Bottou, Frank E Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. SIAM review, 60(2):223-311, 2018
[10] Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
[1]] Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners, 2020.
[12] Yuhang Cai, Kangjic Zhou, Jingfeng Wu, Song Mei, Michael Lindsey, and Peter L Bartlett. Implicit bias of gradient descent for non-homogeneous deep networks. arXiv preprint 250. 2025.
[13] David E Carlson, Edo Collins, Ya-Ping Hsieh, Lawrence Carin, and Volkan Cevher. Precondi- tioned spectral descent for deep learning. Advances in neural information processing systems, 28, 2015.
[14] Ashok Cutkosky and Harsh Mehta. Momentum improves normalized sgd. In International conference on machine learning, pages 2260-2268. PMLR, 2020.
[15] George E Dahl, Frank Schneider, Zachary Nado, Naman Agarwal, Chandramouli Shama Sastry, Philipp Hennig, Sourabh Medapati, Runa Eschenhagen, Priya Kasimbeg, Daniel Suo, et al. Benchmarking neural network training algorithms. arXiv preprint arXiv:2306.07179, 2023.
[16] Zeyu Deng, Abla Kammoun, and Christos Thrampoulidis. A model of double descent for high-dimensional binary linear classification. Information and Inference: A Journal of the IMA, April 2021. ISSN 2049-8772. doi: 10. 00.1093/imaiaiiiaab000.. URL https:/ http:///oooooo/./////// (093/imaia]] /iaa0002.
[17] Steven Diamond and Stephen Boyd. Cvxpy: A python-embedded modeling language for convex optimization. Journal of Machine Learning Research, 17883):15,,201
[18] Konstantin Donhauser, Nicolo Ruggeri, Stefan Stojanovic, and Fanny Yang. Fast rates for noisy interpolation require rethinking the effect of inductive bias. In International Conference on Machine Learning, pages 5397-5428. PMLR, 2022.

---

[19] Euhanna Ghadimi, Hamid Reza Feyzmahdavian, and Mikael Johansson. Global convergence of the heavy-ball method for convex optimization. 2015 European control conference (ECC), pages 310-315. IEFE, 2015.
[20] Roger Grosse and James Martens. A kronecker-factored approximate fisher matrix for con- volution layers. In International Conference on Machine Learning, pages 573-582, PMLR, 2016.
[21] Suriya Gunasekar, Blake E Woodworth, Srinadh Bhojanapalli, Behnam Neyshabur, and Nati Srebro. Implicit regularization in matrix factorization. In Advances in Neural Information Processing Systems, pages 6151-6159, 2017.
[22] Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nathan Srebro. Characterizing implicit bias terms of optimization geometry. In International Conference on Machine Learning, pages 1832-1841. PMLR, 2018.
[23] Daya Guo, Dejian Yang, Haowei Zhang, Junxiao Song, Ruoyu Zhang, Runxin Xu, Qihao Zhu, Shirong Ma, Peiyi Wang. Xiao Bi, et al. Deepseek-rl: Incentivizing reasoning capability in Ilms via reinforcement learning. arXiv preprint arXiv:2501. 12948, 2025.
[24] Vineet Gupta, Tomer Koren, and Yoram Singer. Shampoo: Preconditioned stochastic tensor optimization. In International Conference Machine Learning, pages 1842-1850. PMLR, 2018.
[25] Elad Hazan, Kfir Levy, and Shai Shalev-Shwards Beyond convexity: Stochastic quasi-convex optimization. Advances in neural information processing systems, 28, 2015.
[26] Ziwei Ji and Matus Telgarsky. The implicit bias of gradient descent on nonseparable data. In Conference on learning theory, pages 1772-1798. PMLR, 2019.
[27] Ziwei Ji and Matus Telgarsky. Directional convergence and alignment in deep learning. Ad- vances in Neural Information Processing Systems, 33:17176-17188 2020.
[28] Ziwei Ji and Matus Telgarsky. Characterizing the implicit bias via primal- analysis. In Algorithmic Learning Theory, pages 772 804. PMLR, 2021.
[29] Ziwei Ji, Miroslav Dudík, Robert Schapire, and Matus Telgarsky. Gradient descent follows the regularization path for general losses. In Conference on Learning Theory, pages 2109-2136. PMLR, 2020.
[30] Ziwei Ji, Nathan Srebro, and Matus Telgarsky. Fast margin maximization via dual acceleration. In International Conference on Machine Learning, pages 4860 4869. PMLR, 2021.
[31] Keller Jordan, Yuchen Jin, Vlado Boza, Jiacheng You, Franz Cesista, Laker Newhouse, and Jeremy Bernstein. Muon: An optimizer for hidden layers in neural networks, 2024. URL https:/kkeleerjj ordan. thub. io/ httpposts//me muunn/.
[32] Addison Kristanto Julistiono, Davoud Ataee Tarzanagh, and Navid Azizan. Optimizing attention with mirror descent: Generalized max-margin token selection. arXiv preprint Stt::22410.145888 2024.
[33] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv: 141.69441.66980) 2014.
[34] Frederie Koehler, Lijia Zhou, Danica J Sutherland, and Nathan Srebro. Uniform convergence of interpolators: Gaussian width, norm bounds and benign overfitting, Advances in Neural Information Processing Systems, 34:20657-20668, 2021.
[35] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):221)) (6(11):2278-32222 2002.
[36] Jiaxiang Li and Mingyi Hong. note on the convergence of muon and further. arXiv preprint 250.2.500009000 2025.
12

---

[37] Jingyuan Liu, Jianlin Su, Xingcheng Yao, Zhejun Jiang, Guokun Lai, Yulun Du, Yidao Qin, Weixin Xu, Enzhe Lu, Junjie Yan, al. Muon scalable for Ilm training. arXiv preprint arXiv:2502. 16982, 2025.
[38] Yanli Liu, Yuan Gao, and Wotao Yin. An improved analysis of stochastic gradient descent with momentum. Advances in Neural Information Processing Systems, 33:18261-18271, 2020.
[39] Iya Loshchilov and Frank Hutter. Decoupled weight decay regularization. arXiv preprint arXiv:1711.051001,2 2017.
[40] Kaifeng Lyu and Jian Li. Gradient descent maximizes the margin of homogeneous neural networks. arXiv preprint 1906:0090000090 2019.
[41] Indraneel Mukherjee and Robert E Schapire. A theory of multiclass boosting. Advances in Neural Information Processing Systems, 23, 2010.
[42] Vidya Muthukumar, Adhyyan Narang, Vignesh Subramanian, Mikhail Belkin, Daniel Hsu, and Anant Sahai. Classification regression in overparameterized regimes: Does the loss function matter? arXiv preprint arXiv:2005.08054, 2020.
[43] Mor Shpigel Nacson, Jason Lee, Suriya Gunasekar, Pedro Henrique Pamplona Savarese, Nathan Srebro, and Daniel Soudry. Convergence gradient descent on separable data. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 3420-3428. PMLR, 2019.
[44] Julie Nutini, Mark Schmidt, Issam Laradji, Michael Friedlander, and Hoyt Koepke. Coordinate descent converges faster with the gauss-southwen rule than random selection. In International Conference Machine Learning, pages 1632-1641. PMLR, 2015.
[45] Scott Pesme, Loucas Pillaud-Vivis and Nicolas Flammarion. Implicit bias of sgd for diagonal linear networks: provable benefit of stochasticity. Advances in Neural Information Processing Systems, 34:29218-29230 2021.
[46] Thomas Pethick, Wanyun Xie, Kimon Antonakopoulos, Zhenyu Zhu, Antonio Silveti-Falls, and Volkan Cevher. Training deep learning models with norm-constrained Imos. arXiv preprint arXiv:2502.07552, 2025.
[47] Boris T Polyak. Some methods of speeding up the convergence of iteration methods. Ussr computational mathematics and mathematical physics, 4(5):1-17, 1964.
[48] Hrithik Ravi, Clayton Scott, Daniel Soudry, and Yutong Wang. The implicit bias of gradient descent on separable multiclass data. arXiv preprint arXiv:2411.013355 2024.
[49] Saharon Rosset, Ji Zhu, and Trevor Hastie. Margin maximizing loss functions. In NIPS, 2003.
[50] Fariborz. Salehi, Ehsan Abbasi, and Babak Hassibi. The impact of regularization on high- dimensional logistic regression. arXiv preprint 1xXvv:106.003611 2019.
[51] Noam Shazeer and Mitchell Stern. Adafactor: Adaptive learning rates with sublinear memory cost. In International Conference on Machine Learning. pages 4596-4604. PMLR, 2018
[52] Hao-Jun Michael Shi, Tsung-Hsien Lee, Shintaro Iwasaki, Jose Gallego-Posada, Zhijing Li, Kaushik Rangadurai, Dheevatsa Mudigere, and Michael Rabbat. A distributed data- data-parallel pytorch implementation of the distributed shampoo optimizer for training neural networks at-scale, arXiv preprint arXiv:2309.06473 2023.
[53] Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The implicit bias of gradient descent separable data. Journal of Machine Learning Research, 19 170):1-57, 2018.
[54] Haoyuan Sun, Kwangjun Ahn, Christos Thrampoulidis, and Navid Azizan. Mirror descent max- imizes generalized margin and can implemented efficiently. Advances Neural Information Processing Systems, 15::1089-31100 2022.
13

---

[55] Haoyuan Sun, Khashayar Gatmiry, Kwangjun Ahn, and Navid Azizan. A unified approach to controlling implicit regularization via mirror descent. Journal of Machine Learning Research, 24(393):1-58, 2023.
[56] Hossein Taheri and Christos Thrampoulidis. Generalization and stability of interpolating neural networks with minimal width. arXiv preprint arXiv:2302.09233. 2023.
[57] Davoud Ataee Tarzanagh, Yingcong Li, Christos Thrampoulidis, and Samet Oymak. Transform- ers as support vector machines, 2023.
[58] Davoud Ataee Tarzanagh, Yingcong Li, Xuechen Zhang, and Samet Oymak. Max-margin token selection in attention mechanism, 2023.
[59] Matus Telgarsky. Margins, shrinkage, and boosting. In International Conference on Machine Learning, pages 307-315, PMLR, 2013.
[60] Christos Thrampoulidis. Implicit optimization bias of next-token prediction in linear models.
In The eight Annual Conference on Neural Information Processing Systems, 2024.
[61] Christos Thrampoulidis, Ganesh R Kini, Vala Vakilian, and Tina Behnia. Imbalance trouble: Revisiting neural-collapse geometry. arXiv preprint arXiv:2208.0555 2022.
[62] Alexander Tsigler, Luiz FO Chamon, Spencer Frei, and Peter L Bartlett. Benign overfitting and the geometry of the ridge regression solution in binary classification. arXiv preprint arXiv:2503.07966, 2025.
[63] Nikolaos Tsilivis, Gal Vardi, and Julia Kempe. Flavors of margin: Implicit bias of steepest descent in homogeneous neural networks. arXiv preprint arXiv:2410.22069, 2024.
[64] Gal Vardi. On the implicit bias deep-learning algorithms. Communications of the ACM, 66 (6)86-99 93, 2023.
[65] K Nithin Varma and Babak Hassibi. Benefits of stochastic mirror descent in high- sitb-dimensionll binary classification. In 2024 IEEE International Symposium on Information Theory (ISIT), pages 196-201. IEEE, 2024.
[66] Bhavya Vasudeva, Puneesh Deora, and Christos Thrampoulidis. Implicit bias and fast conver- gence rates for self-attention. arXiv preprint arXiv:2402.05733, 2024.
[67] Nikhil Vyas, Depen Morwani, Rosie Zhao, Mujin Kwun, Itai Shapira, David Brandfonbrener, Lucas Janson, and Sham Kakade. Soap: Improving and stabilizing shampoo using adam. arXiv preprint arXiv:2409. 1321, 2024.
[68] Bohan Wang. Qi Meng, Wei Chen, and Tie-Yan Liu. The implicit bias for adaptive optimization algorithms on homogeneous neural networks. In International Conference on Machine Learning. pages 10849-10855 10858. PMLR, 2021.
[69] Bohan Wang. Qi Meng, Huishuai Zhang, Ruoyu Sun, Wei Chen, Zhi-Ming Ma, and Tie- Yan Liu. Does momentum change the implicit regularization on separable data? Advances in Neural Information Processing Systems, 35:26764-26776, 2022.
[70] Guanghui Wang. Zihao Hu, Vidya Muthukumar, and Jacob Abernethy. Faster margin maxi- mization rates for generic optimization methods. Advances in Neural Information Processing Systems, 01166288-625188 2023.
[71] Ke Wang, Vidya Muthukumar, and Christos Thrampoulidis. Benign overfitting in multiclass classification: All roads lead to interpolation. Advances in Neural Information Processing Systems, 34, 2021.
[72] Nan Wang, Zhen Qin, Le Yan, Honglei Zhuang, Xuanhui Wang, Michael Bendersky, and Mare Najork. Rank4class: ranking formulation for multiclass classification. arXiv preprint arXiv:2112.09727, 2021.
[73] Yutong Wang and Clayton Scott. Unified binary and multiclass margin-based classification. Journal of Machine Learning Research, 25(143):1-51, 2024.
14

---

[74] Jingfeng Wu, Peter L Bartlett, Matus Telgarsky, and Bin Yu. Large stepsize gradient descent for logistic loss: Kon-monotonicity of the loss improves optimization efficiency. arXiv preprint arXiv:2402. 15926, 2024.
[75] Jingfeng Wu, Vladimir Braverman, and Jason D Lee. Implicit bias of gradient descent for logistic regression at the edge of stability. Advances in Neural Information Processing Systems, 36, 2024.
[76] Shuo Xie and Zhiyuan Li. Implicit bias of adamw: L-infinity norm constrained optimization. arXiv preprini arXiv:2404.04454 2024.
[77] Chenyang Zhang. Difan Zou, and Yuan Cao. The implicit bias of adam on separable data. arXiv preprint arXiv:2406. 10650, 2024.
[78] Chiyuan Zhang. Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization, 2017.
[79] Yushun Zhang, Congliang Chen, Tian Ding, Ziniu Li, Ruoyu Sun, and Zhiquan Luo. Why transformers need adam: A hessian perspective. Advances in Neural Information Processing 2024.
3 37:131786-1133
[80] Yushun Zhang, Congliang Chen, Ziniu Li, Tian Ding, Chenwei Wu, Diederik P Kingma, Yinyu Ye, Zhi-Quan Luo, and Ruoyu Sun. Adam-mini: Use fewer learning rates to gain more. arXiv preprint arXiv:2406. 16793, 2024.
[81] Krystyna Ziętak. On the characterization of the extremal points of the unit sphere of matrices. Linear Algebra and its Applications, 106:57-75, 1988.
15

---

Appendix
Additional Experiments
16
Facts about CE loss and Softmax
16
C Lemmas Loss and Proxy Function
21
D Implicit Bias of Normalized Steepest Descent
23
Implicit Bias of Normalized Momentum Steepest Descent
27
Other multiclass loss functions
30
G Implicit Bias of Adam
33
A Additional Experiments
We present additional experiments Signum and NMD-GD in this section. Based on Figure their margin convergence properties are very similar to those of SignGI> and NGD respectively (see Sec. in the main text for the experimental setup).
Comelriie Demilii Alli
Jes,
I',
0:1
107
17
17
(a) Signum
(b) Signum
(c) NMD-GD
(d) NMD-GD
Figure 4: Implicit bias of Signum and NMD-GD multiclass separable data. (a) Relative margin gap of Signum's 's iterates against iterations. (b) Correlation of Signum's 's iterates to Vos, V2, and Vspec against iterations. See Figure and for the definitions of relative margin and correlation. (c) and (d) Same as (a) and (b) with Signum replaced by NMD-GD.
B Facts about CE loss and Softmax
Lemma 9 is on the gradient of the cross-entropy loss. It will be used for showing the form of G(W) in (8) lower bounds ([V in Lemma 16.
Lemma (Gradient). Let CE loss
1 L(W)
Σ log (S (Wh:)). mm(m]
For any W. it holds
VL(W) Eiemn (Cy: -.) --1 SS VVW(W = 0
16

---

For any matrix A Rixdd
(A-WW((W) 1 Σ (1 Sin,)
Eotos Sio e, Ah;
(1 Sigel
sic (Ey; - -e)) Ah,
(11)
11
iE/n] eft
where we simplify S = S(WH) = [1
8n) E Rkxnn The last statement yields
(A.-VL(W)) 2
Sig.) min (e - Ec) Ahi.
(12)
E mg
Proof. First bullet is by direct calculation. Second bullet uses the fact that (y: 8:) = 1 1 = since ITo 8; = 1. The third bullet follows by direct calculation and writing 8; Ah; E Sa Ah; = E. 8ic e Ah;
Lemma 10 is on the Taylor expansion of the loss. It will be used in showing the descent properties of NSD and NMD.
Lemma 10 (Hessian). Let perturbation A E Rexd and denote W W + A. Then,
L(W" = L(W) Σ
(eey - S(Wh:) A) (n
Σ iE[n]
h A
(diag(S(W S(Wh,))(Wh))) A + o ((1) (13)
Proof. Define function by R + parameterized by E [k] as follows:
(l) - (o)
From Lemma 9,
(ly()) (eyy - S(())-
Thus,
V2e,(1) = VS(L) = diag( S(I)
Combining these the second-order taylor expansion of by writes follows for any 1, 5 R
(2 + 5) e() - (e, S(L) 5 -(()g(())))((((())))) S(1)S(())) 5
o(())
To evaluate this with respect change the classifier parameters, set l Wh. and Ah for E Axd Denoting W = W A, we then have
(W')) ( ((e, S(1)) T A
T (diag(S(I)) (())(((()))(((())) Ah + 19)).
This shows the desired since nC(W) = Exeln Ey (Wh;) and we can further obtain
(W') (W) ((e, s(()) A) h A ((() Ah.
(14)
where /' 1 (8 for some < [0, 1].
We prove the relationships (7), which are useful for unifying the analysis of entry-wise and Schatten norms.
Lemma 11. For any mairix A E BRxx and any entry-wise or Schatten p-norm ||-|| with p 2 1, holds that
| mmx <
||||| < ||A Jum
17

---

Proof. The entry-wise p-norm case is trivial. Here, we focus the Schatten p-norm case. Note that ||| coincides with the entrywise 2-norm | but in general Schatten norms are different from entry-wise norms. On the other hand, Schatten norms preserve the ordering of norms. Specifically, por any p 2 1, it holds:
1/p
| 01 S ||||||,
Σ
of
||||||
(15)
i=1
It is also well-known that
max T Au 2 max || I b=
Aii = |A| |
(16)
where the inequality follows by selecting u = sign( (Ali, ey and v = ejr for (i',5) such that (A') |||]] max and ev, Cy corresponding basis vectors.
Using this together with duality, also holds that
||||||| s || laam
(17)
This follows from the following sequnece of incqualities ||||||| = max
||B B) < || sum
max
| mmax S I1
max
B
|1
S
||||
aum
||I|||
BBII
(18)
where the first inequality follows from generalized Cauchy-Sewhare and the second inequality by (16).
Lemma 12 is used in bounding the second order term in the Taylor expansion of L(W).
Lemma 12. For any entry-wise or Schatten p-norm ||-Il with p 2 1, any A in the k-
dimensional simplex, any index E [k), and TR. k it holds that
v T (diag(s) ss ) x S 4(1 wo]l
Proof. See main text.
Lemma 13 is used in the proof of Lemma 12.
Lemma 13. For any 8 E k in the k-dimensional simplex and any index c E [k] it holds that
Eee - (3-)) $ 2(1 8c).
Proof. With bit of algebra and using Ee Se' Se the claim becomes equivalent to
Σ
2/ + 2 28 2
c'
Since this holds true, the lemma holds.
Lemma 14, For any 8 E k-1 in the k-dimensional simplex, any index e E [k], any A E Rexd and any gd it holds:
h T T (diag(s) ss" Ah < 4B" A sc).
Proof. We let v h.. For any Schatten p-norm, have
1w ||| = ||01 s |||
S |||
|All S B² ||||||
For any entry-wise p-norm, have
AhIl = AhIl = Ele Ahl &
|le
A
EI = 1 Σ
R = AM
This implies
voo ||||
| 2 < <
8² A ?
Combine these results and apply Lemma 12, obtain the desired.
18

---

The following lemma summarizes the properties of the softmax map that will be used in the proof of Lemma 25 and 35.
Lemma 15. For any v, v' 9: E Tht and c [k), the following inequalities hold:
(i)
S.(02) Be(0)
1/ S e² 200000 11
(i))
1-8,(v') T-8,(0)
1| s 22110-0'lxx -1
(iil)
(, (.))))
1 S 201l0 +1d'- -
-(0''11)) (iv)
1| S 20ll00 qillo))
(v) (1-8,0')00-8.6 -1)l-- 1 $ 20100' 00
Proof. We prove each inequality:
(i) First, observe that
(e (v)
e" Eie(N) e
1
8 Eie(k) e²
Eie(M) exsta Eielyy e
Evett cuoted
EjERy/ lettt - eootoly
Σie(k) e'ote!
For any i E [k], we have lelctn-aooti = 10% vet--etoorvi-11 S elo--ostu-dll11 S 2111000 = ctotel This implies Eie(y] -enttr-enttriy S (6210-0' - 1) Eie(a enotel, from which we obtain the desired inequality. (ii) For the second inequality:
oo Exe(e c.
1 - (c')
(v)
EveRk) ExS
EjeMsiae e% ) (2ie(e) e%)) 11
ESEMHNHE e" (E)E(EE)))) 0%
EJEM,I+e EVerA| (e e"sto?]
EjEmhite Die(M] enstic
EjeNssto EiEla) le - cnstol/
5 Eje(h)ite Eie(h] enstt!
For any j E [k], j # c, and i E [k], we have و I 821lo-u'llo 1. This implies that
enito! Ejejk Eierk| le edy 5 (6'1lo-0'll> - 1) Ejenkoat Eiers eottel, from which the result follows.
19

---

(iii) For the third inequality:
0%6
e%
S,(o')) (.))))
Eie(o) e²! Eie(o e
1|
1| Eiele) e" 2ie(s) E3i
(,(v)S,(q)
e'c
C9C
note
c²c
ElEro e%i Exe(s) 2%
E e
E1E(1) 5%
69c
Eielk) oni Every o%
Every 0²
EvEry) el
E% DiE(M] e Σ Jje(N ed
c" Eie(w e%! Σ ΣjE(m) e%
eureg EiE(M] e% Zje()) o%
eu Die(M ea
Zje(M) e./
EiE(M] EjE(H) Cooooottttttt
(motoltacta)
EiE(A) DjE(N] e
Ejelk Eje(s] le"otertot tuotetaactt)
EiElh EjE(m @ ecttuttatt
1e lus v/ -e 1o 10% jo 22-6--0-66 1| S
For any [k) and E [k:]. ebo--o/HHo--0 -el +la, - 1 S
+la' allooo) - 1. Then, rearranging and summing
over and j leads to the result.
(iv) For the fourth inequality:
0%
eol
((')((1S.(q') -
EneNy e
[1E() e
1
-
Exc(m) 6%
E(c(4) eai
e%
E Enep
Eneraje e%
1
Lielblize 21E(H) et
E 6"
EVERA)AAO ElERK] Exelay e% dlt-ttturt
EVERE, EvERk] EjElm @ c"c-actosto"
Eie Miite EiE(H) Eee(H) 10% 0o60-(ttrrr - eootacte,+d
Eie(h),te EveRai EnElh ePotatrrtt!!
- For each [k], # C, s E [k]. and t E [k], we obtain le' Io
2(ll "elloo-e|l<++lle +ll'== (ll=) 1. Then, rearranging and summing over i, s, and t leads to the result.
(v) Finally, for the fifth inequality:
0% Exe(a) 6%
Exem 0 )1
(1 - (1-).(0))(1-.(()) -1=
1|
1
(1 (b))
EeeM eva )(1
Exelmssa ee's
Exerhiree e%!
EvENy 6%'s
Enele) e9(
Eechhisee e0 Diciiine eni Luc(Mer e0
Eiclye
EjeMhite E EiE(hT,ite EMETR ESERAY e tottttt
ESEMMIHH EnerHI, EiE(K) ESERA] +05t0ctestd
EjERHhAe EiE EiE(A) EvE(A) 10 (oft -
EjEMh,HE EVERA), 1440 ΣiE(H) Ejely e0)
20

---

For each j E [k] ( c), i E [k] (i c), & E [k], and t E [k]] we have
le - - |e -
+ 1|
c 1 ,,, - S 201'o -v 11 -llo))
Then, rearranging and summing over j. i, 8, and i leads to the result.
C Lemmas on Loss and Proxy Function
Lemma 16 shows that ((W) upper and lower bound the dual norm of the loss gradient.
Lemma 16 (G(W) proxy the loss loss-gradient norm). Under Assumption 4. For any W E Rexd holds that
2B G(W)
[ 2 T G(W)
Proof. First, we prove the lower bound. By duality and direct application of (12)
[VL(W)] max (A, VL(W))
SA
(1 Sigs min( - -ea) Ah;
max |
cFu.
(E
Sigi)
max min (e ex)² Ah, (E
n
A 1
sEin]
Second, for the upper bound, holds by triangle inequality and relationships (7) that
VV((W) (VC(W) auam
< Σ
[V(((W) [|
aumm
(E(m]
where (WW) = (Sg (Wh.)). Recall that
(WWW)) - (ey Sy (w (Wh,))
and, for two vectors v, u:
lue" eum = ||u|| 1|11:///11111 Combining these and noting that
ley. - Sy, (Wh:)li = 2(1 - 2(1-sy,)
together with using the assumption ||h,|| < yields the advertised upper bound.
Built upon Lemma 16, we obtain simple bound on the loss difference at two points.
Lemma 17, For any W, Wo E IR suppose that L L(W) is convex, we have
(<(W) L(W)) < 2B W
Wull-
Proof. By convexity of L, we have
((W)) L(W) s (VL(W)). Wo W) < VZL WIl 2B W|, where the last inequality is by Lemma 16. Similarly, we can also show that L(W) - L(W)) S 2B W. W|
Lemma 18 shows the close relationships between G(W) and L(W). The proxy G(W) not only lower bounds L(W), but also upper bounds L(W) up factor depending on C(W). Moreover, the rate of convergence g(W) Z(W) depends on the rate of decrease in the loss.
Lemma 18 (GW as proxy to the loss). Let W E Rxd we have
ii) >
G(W) W >
2
21

---

(ii) Suppose that W satisfies L(W) I
1og or (WW) S 1 then L(W) - 2g(
2n
/8)) and g(W)= = E (1 (1-s;] st). For the upper bound, simply use the fact that ex- x, forall x E [0, 1], thus log(1/))) 2 1 1 s, for all i [n]].
Proof. (i) Denote for simplicity := Siy, yy (Wh.), thus L(W) = 1 Li log(1 (1/(s)/)
The lower bound can be proved using the exact same arguments in the proof of Zhang et al. [77. Lemma C.7) for the binary case. For completeness, we provide an alternative elementary proof. suffices to prove for 1 that for (0, 1);
1- s 2 log(1/s) log" (1/s).
(19)
The general case follows by summing over 8 = 8, and using Exeaa log (1/ss)
S since log(1/s)) > 0. For (19), let x = log(1/s) > 0. The inequality be- comes e < 1 - x + x² /2, which holds for x > 0 by the second-order Taylor expansion of e around 0.
(Eiejn) log(1/s:) 2
(ii) The sufficiency of L(W)= < log (to guarantee that L(W) S 2G(W)) follows from (i) and L(W) < log < 1. The inequality log(2) s 2(1 - x) holds when x E [0.2032, 1]. This translates
to the following sufficient condition on Siy,
8
Eee(H) elild
1 (t) gl.lc) [. 2 0.2032.
Under the assumption G(W) S 2n we have - S Eie(n) (1 - s:) = nG(WW) S 4. from which
we obtain s; 2 2 0.2032 for all i E [m].
Lemma 19 shows that the data becomes separable when the loss is small. It is used in deriving the lower bound on the un nn-nommalized margin.
Lemma 19 (Low L(W) implies separability). Suppose that there exists W R such that C(W) S Ing then we have
forall ee) W/, 20, for all i E [n] for all e [R]] such that e + yv.
(20)
Proof. We rewrite the loss into the form:
chilk [K]]
((W) = n sEin]
Σ log(
clolo!
Σ log(1 + > e (ellllilleel))))
EeER
vE(n)
Fix any E [n], by the assumption that L(W) I 1og2 we have the following:
log(1 + Σ (4.bbll ((()) < nC(W) < log(2).
This implies:
minemin (f([u:]
max [e(]))-e(cc))
Σ c -esslun)-sso)) $
After taking log on both sides, we obtain the following: (,1v,) - e, = (ey, -e.) -W, 2 0 for any E [k] such that + ys-
Lemma 20 shows that the ratio of ((W) at two points can be bounded by exponentiating the max- norm of their differences. It used in handling the second order term in the Taylor expansion of the loss.
Lemma 20 (Ratio of ((W)) For any 3 E [0, 1). we have the following:
g(W - - < 2B Iaax S BB All
G(W)
22

---

Proof. Note that the second inequality is by relationships (7). Here, we only prove the first inequality. By the definition of g(W). we have:
G( A
EiEiH| (1 ((W - )n))),))
g(W)
EiEjal (1 By hw,)
For any c E [k] and v, v' E R we have:
0%
1 - ST(
EVErA] e%! c"
- (c(
1 E1E(H) 6%
Eiewye en
Eseusse 2icle) e%
Ejelklite Eielki e
Ene(H) ΣiE| e"stoo
I 2ll
cst The last inequality is because easto
S 115s-yltie-0 S ellvo-''l which implies that
E Σiele enI+0= I c2llu-v'lls 10x0
EjE[B,,te s+c Eseray enstrr, Next, we specialize this result to o' (W A 12, v= = Wh,, and y for any i [n] to obtain:
Sy. ((W )))))
< <noiiAn S e 2B A max.
Sy, (Wh;)
Then, we rearrange and sum over E [n]] to obtain: Eieny (1 S1 ((W (nn))ha) < ABl Eigin - Sy, (Wh:)) from which the desired inequality follows. The second inequality in the lemma statement follows from the relationship (7).
D Implicit Bias of Normalized Steepest Descent
Proof Overview We consider decay learning rate schedule of the form 7) +(22 where E (0,1). 1]. The first step is to show that the loss monotonically decreases after certain time and the rate depends on G(W). To obtain this, we apply Lemma 16 and Lemma 12 to upper bound the first-order and second-order terms in the Taylor expansion of the loss (21), respectively, Next, we use the decrease in loss to derive a lower bound on the unnormalized margin which involves the ratio g(W) A crucial step involved is to find a time i2 such that separability (32) holds for all t 2 f2, and Z(W)
the existence of f2 is guaranteed by loss monotonicity such that the condition L(W,) I log2 will be satisfied for sufficitently large t's.
Then, argue that the ratio g(W,) Z(W,) converges to 1 exponentially fast (recalling that g(w.) >
Z(w.)
1 ()())) by showing the loss L(W,) decreases exponentially fast, We first choose time t after to (recall that to is the time that satisfies Assumption 3) such that L(W++1) < L(W,) - G(W)
for all / 2 f1. Next, we lower bound G(W,) using L(W,). By Lemma 18, there are two sufficient conditions (namely, L(W,) < log2 = C or G(W) & 1) that guarantee L(W,) < 2G,W.). We choose time to (after t1) that is sufficiently large such that there exists t" E [tt,,t] for which have ((,,)) < C < 1. This not only guarantees that L(W,)) S 2g((W.) at time t", but also (crucially due to monotonicity) implies that L(W) S L(W,-) < (W, < log2 for all 2 f2- Thus, we observe that the other sufficient condition L(W,) S log2 is satisfied, from which we conclude that L(W,) < WG, for all / 2 12. We remark that the choice of l2 depends on L(W,,) (whose magnitude is bounded using Lemma 17), and l2 can be used as 12 above. To recap, 4 the time (after to) after which the successive loss decrease is lower bounded by the product ne (W,);
2
2nz
n
23

---

to (after (1) is the time after which ((W)) - 1og (thus, both ((W) & (W:) and separability condition (32) hold for all 2 t2).
In this following, we break the proof of implicit bias of NSD into several parts following previous arguments. Lemma 21 shows the descent properties of NSD. It is used in Lemma 22 lower bound the un-normalized margin, and in the proof of Theorem to show the convergence of G(W)
z(W))
Lemma 21 (NSD) Descent). Under the same setting as Theorem holds for all 2 0,
((W++1) S ((W)) mT - (2ay (W)))
where Os, is some constant that depends on B and 7/-
Proof. By Lemma 10, we let W W1+,, W W, A. W+t W., and define Wi,ti. Wi + S(W++1 - Wt). We choose Ç such that W1.+1.5- satisfies (14), we have:
((W(+1) = L(W)) + (VL(W)). A.)
+
Σ h
(diag(S (S S W W.) We h:) A h
2n
iE(n]
(21)
For the + term, we have by Lemma 16:
me V/(W)ll 1 GTe)
For the a term, we let v h, and S(W,,+1c. ht). and apply Lemma 14 obtain
4 h |3 Sy, (i,.+1.. h:)) < 4n B Sy, (W (W.r+1,c+ h:)),
where in the second inequality we have used | || S T7 and hh S h4 |l S 1. Putting these two pieces together, we obtain
C(W(+1) s L(W.) mm9(W.) + 2n B² Σ (1 (We+1.g-h)))
iEjm]
-(W,) mm9(w,) + 2n B2g B"
S L(W.) mwS(W.)) + 2n1 B² sup g(W..+ie)
{E(U,1]
G(W, (A.)
C(W) (W + 2n (WW, (E
sup
G(W,)
2 ((W) (W)) 2m (WW, sup CE(O.]]
( ((W) (WW) 2n 2 2Bo g(W.).
(22)
Eq. (22) simplifies to: where (a) is by Lemma 20 and (b) is by || | |l S Th- Letting d'. 2Bm0
((W++1) < L (W,) 7m az, (,
from which we observe that the loss starts to monotonically decrease after 7)e satisfies nt S I for decreasing learning rate schedule.
For decaying learning rate schedule, Lemma 21 implies that the loss monotonically decreases after a certain time. Thus, we know that the assumption of Lemma can be satisfied. the proof of Theorem 3, we will specify concrete form of in Lemma 22.
24

---

Lemma 22 (NSD Unnormalized Margin). Suppose that there exist such that L(W) I t >> E, then we have
1og for all
G(W.)
min EE|llecy
(ey. -ee) Wi, 21 E ne ((W.)
O1ea Σ
2
where Ox2 is some constant that depends on B.
Proof. We lete 022 Bno, then from (22), we have for t F:
((W2+1) = ((W) (WW)(W,) + as ((WW)
((W)
((())
= =((W) 7T L(W,) + ass ((W))
<((W) exp( -Mm g(W))
+oee ((W))
((W)
((Wi)
g(W.)
< ((W) exp(
no C(W,)
+ +02z Σ n²)
==1
s=i
log 2 exp
G(W.) 75 C(W.)
assz
(23)
s=i
where the penultimate inequality uses Lemma 18, and the last inequality uses the assumption that L(W,) I log2 for all / 2 Then, we have for all >
minnggnl.csu,.e.... (e,, -e.) W.h. -W.).
minestu (ev; - W.h. W.h
maxe xE(m]
1
log (1 + min (ey: W.i.)
max *E[n]
log 2
I max
1
log(1 + Σ
e (ev
-co)= -ec
"iih)) s nL(W))
xE(n] log 2
log 2
(b)
G(W,) L(W.)
1-1
S exp(
n
a.s
Σ
8=İ
(a) is by the following: the assumption L(W.)
S log implies that mine (ey, - ) W,h; 2
for all E [m]] by Lemma 19. We also know the inequality log(1+e 5) 2 log 2 holds for any 2 2 Then, for any i E [n]. we can set = min (ey, e.)) W,h; to obtain the desired inequality: and (b) is by (23). Finally, taking log both sides leads the result.
e
Next Lemma upper bounds the p-norm of NSD's iterates using learning rates. It is used in the proof of Theorem 3.
Lemma 23 (NSD Will). For NSD, we have for any > 0 that
(-1
|W, S W +
Σ n
Proof. By the NSD update rule (3), we have
W Wo Σ n A.
==0
This leads to |Wi]l < |oll + - 7. given A, < 1 for all 2 0.
25

---

The main step in the proof of Theorem 3 is to determine the time that satisfies the assumption in Lemma 22 and show the convergence of G(W.) Then, Lemma 22 and Lemma 23 will be combined to obtain the final result.
((W)))
Theorem 3. Suppose that Assumption 1, 2, and 4 hold, then there exists t,2 tep (n, 7/s B, Wo) such that NSD achieves the following for all t > t2
min el (ey, cc) -W.h
Li The - 2istn of + Exio -1
x--1 + Liztog %
S O
[W.ll
2. 7
Proof. Determination of fs,, In Lemma 21 we choose to, such that 1) S 20 for all t 2 txp. Considering //: = (²)) (where a E (0, I), we sesttss ls =(20k, = 2B3 for all 2 tær
Then, we have
((W S ((W.)
Nh7 Th s(W)).
(24)
Rearranging this equation and using non-negativity of the loss we obtain Ex=t, 7gg(W,) 2C(W,,,) Determination of lag- By Lemma 17, we can bound L(W ) as follows
S
- -
& 2B| W.,, - Woll s 2B
77
A
el
S
2B
n
==0
where the last inequality by A S 1 for all 8 2 Combining this with the result above and letting C -= 1og we obtain
G(W,-)- = min G(W.) < 2C(W)) + +4 + sElta,
E
==
17
2
2n'
sty 11s
from which we derive the sufficient condition on t2p to be stt, n7 1C(W6)+8B Eiih n
76
Convergence of G(Wa) İ for all 2 tag. where the first and second inequalities are due to monotonicity in the risk and Lemma 18, respectively. Thus, the other sufficient condition L(W,) S log in Lemma 18 is satisfied, from which conclude that L(W,) s 2g(W,) for all I lig. Substituting this into (24), we obtain for all t > teg
C(Wi) Given g(W,)) S S 2n we obtain that L(W) S L(W,)) S 29(W
1t
Ph- ( S L(W,,,) -iiin a < Le Eo 9 4
((W) S (1
Then, by Lemma 18, we obtain
21 nLe - Eiston
(
2 n((
2 1 - - Ebminy Th
(25)
C(W)
2
2
Margin Convergence Finally, combine Lemma 22, Lemma 23, and (25) to obtain
Wil 7/5 s WlllWll + Ex=1 u 7 Ex-tan or E'e na) Ossz Ex "1e
minge (n). (ev. -ec) Wih
W + E1-1 ?
Ei " + E'ze ns Ei m
Exsto nse
< 0
1-1 == ?
Next, we explicitly upper bound tag in Theorem 3 to derive the margin convergence rates of NSD.
26

---

Corollary 1. Consider learning rate schedule of the form = (z)) where (0, 1), under the same setting as Theorem 3, then we have for SignGD
if
minie(m) (eg, cce) Te,) Weh;
logttn 277
if
71
IW.ll
if <
a
<
if =
log
Proof. Recall that ts. (1B
Ce. and the condition on tez is
Σe 77 2
4C(Wo)+8B LB Ve, where L
We can apply integral approximations to the terms that involve sums of learning rates to obtain
1og
76
L/2 Cs T. ((W))
Given fa some constant, this further implies that
tug
Σ
7 = (
sm0
Next, focus on the term -1_ 1/. For > 1.2 this term can be bounded by some constant.
For 21 have - tog 1 O(t D(tl-20). 20), and it evaluates to Ollogt) for } Finally,
we have that E:=1 77 Ott for a < and Σ T}s (log for a The term
Exs,, Uhe $ Ertte is bounded by some constant as shown Zhang et al. [77. Corollary 4.7).
E Implicit Bias of Normalized Momentum Steepest Descent
Recall that ||||| refer to either entry-wise or Schatten p-norm with its dual norm denoted as I1-Ila-
Lemma 24, Consider the following Wt = W 7 where A E RR is defined in (4). Ler M Rexd be any matrix. It holds:
(VL(W) W
W) s 2n) [2l m)G(W)
where Z defined to be Ω = M VL(W).
Proof. We define Ω = M VL(W) to obtain
(VL(W), W W) = (VC(W) - M, Wt W)+ (M, Wt w)
(V(C(W - M, A) T(, A)
(4)
7//VC(W) M | M|
(6)
8 7 - VL(W) MI VL(W) + VC(W)..
(2)
7/122 - (-VL(W))l
1umm
(4)
S
7/
/
<[]] [||2]|~)
2
swm 7l|V
|7 pum 77G(W)
2m
where (a) is by Cauchy Schwarz inequality and (M, A) || (b) is by ||| S (c) is via Lemma 11, (d) is by reverse triangle inequality, and (e) is via Lemma 16.
The following Lemma bounds the entries of the momentum (M,) of NMD in terms the product of T with the sume of (W,) and Q. (w,).
27

---

Lemma 25. Suppose that Ass. 1, 3, and 4 hold. Let c E [K] and j E [d]. There exists time to such that for all 2 to:
MM - (
+ (.()))
where OM == B(1 - 31)e2.
Proof. For any fixed c E [k] and j E [d]
(1 (( -(--
Σ (1- (VL(W.)))c.)) vc(W))c.))) )
T-0
(1 B1) -
(26)
We first notice that for any W Øexd we have VL(W)] eVVC(W)e,
- n Eie(nn e" (e,, S(Wh:)))))))))) hif - Exem e² (ey, S(W h.)) Then, the gradient difference term becomes
e (ey: - S(W, s(Wr
+ n vE(m]
Σ
ee.(een (ey; S(W,h:))hu)
71
iE
In]
[S( Wi h:)) s(Wah:))
(B W 1 h1) S. (Whh))
7 vE(n]
< B -
S WW 11)) - So (Wih:)
kE(n)
B 1
S. - S. (W,h,) +B 1
Σ vE(m),
(....,,h))
- S. (W.h,))
ve(n)aute
Next, we link the a and a terms with (W)) Starting with the first term, we obtain:
W h:) -1|
Σ hW,,,)
n
S.WWh:
Σ
WWW 1)
Se (W, 201 W... We Imnx -1) 1)
(e Ih - Σ (W,h,)
(E(n),utt
(d)
x
where (a) by Lemma 15, (b) is by ||x:|| S for all i [n]. (c) is by (3) and triangle inequality, and (d) is by A A
1 (for any entry-wise or Schatten p-norm) and the definition
28

---

of (Wt). For the second term, we obtain:
Σ 1E
By (w))),) -1+ Sy. (W,h,))
yy (W, ,h:) -
Σ - Sy (Wih:))
+
Sy (Whh:)
yy (W,
(1 Sy (whh)))
1
1 Syy (Wih;)
Σ (1- (W:hi))) (Wirr- - 1)
iE
S 2B 2B (W.)).
where (e) is by Lemma 15, and (f) by the same approach taken for d. Based on the upper bounds for 1 and 2. obtain the following: 2B 2a Dis lit-a ()(9 2a(W.) Then,
we substitute this into (26) to obtain:
- - VVV < B(1 B.)(G. Q....)
Σ
87 (
2B Eis
2B ne-a P---1 1)
1=0
(
B(1 (G))) (.()))), $
where (g) by the Assumption 3.
Lemma 26. Let S = M, - VL(W.), where M, is defined in (5). Then, it holds
12 (2BB)(2((W.) + dn
where aM := B(1 - -31022
Proof. For simplicity, we drop the subscripts f. Denote Te(W) = Gc(W) + (.W). Then, by Lemma 25, have for any e [k] and j E [d]:
M[c (1 ) + (W) Jemoo
VL(WW - [(WW)]l. + aMmTo(W))ar Jem.o.h
where aM = B(1 B1 le2 and em,c.j is some constant
lemeall S 1. Recall that Ω
M VL(W), then we have
[[c,illl = |M[c - (cW))l
= =1 - VC(W))(, aw)TT(W)) cm...))
< [ (w)TT
This implies the following:
Ω ||l.aam = Σ P|c,i S 1 Σ [e(W)(e.)) + +OMT) Σ To(W)
= 1 Jmmm + 2awddg((W) < /2 + (W))
where in the last inequality we have used Lemma 16.
29

---

Lemma 27. Suppose that there exist such that L(W)) - 1og2 for all t > f, then we have
1-1
g(W.) .(W.)
min iE|n]eey
ec) We: 2
Tl
02 Σ 1/5 - Q
==1
where a2 = (40r + BBrod and Q = 4B7 18/1/-
Proof. We follow a similar approach as Lemma to show the descent of NMD. Specifically, we apply Lemma 24 to bound the first-order term. For the Hessian term, we apply Lemma 14 and Lemma 20 similar to NSD. Then, we can obtain the following
((W++1) S L(W) (W.)(W)) + 21/. 12 + 2n B² e 28 g(W.)
(a)
S L(W,) (WG + / n.((..) 4a do 2n BB2
(6)
$ ((W)) - (M) + a 2 (((()) +02h dg(W,)
g(W.) .)
$ ((W) exp( - Σ
+a Σ
89/21 17 + a2d Σ ni)
Te ((W.)
==
s=1
e=1
( 1og2 exp(->
G(W,)
+ agd Σ n +Q),
1s C(
n
where (a) is by Lemma 24. In (b), have defined 01 4B and 02 (40 2 )d. In
(c), we have used the assumption and defined Q == 0110 J 2 ai Ei=i 1)ss The rest of the proof follows the same steps as Lemma 22.
/2/2
Theorem 4. Suppose that Ass. 1, 3, and hold. Set learning rate 17: 0 (1tz)) The margin gap of ' iterates satisfy
min (ey, ea)" T
dlogt t dn
WWll
11/2
Proof. Given the updates of NMD are normalized (i.e., | S 1), obtain the following via Lemma 27:
7 mineg(n) (ey: - W.h.
(1lWWll + Ete' Uo + E'=1, nee Lint vr) + and Eest v/3 + Q
W
|Wol E1=1 176
Exst, nEC Et-ig Ei-1 ns + d d n
00
E. n
Then, we follow the same approach as Corollary for decreasing learning rate of the form Tt = (()). Specifically, we have t = (a) and to < Cn + Can L(W)) This leads to
Σ 0 nl1 (L( + dlo((().
#=
Thus, we have the margin gap upper bounded by O (od++))og()))
Other multiclass loss functions
F11
Exponential Loss
The multiclass exponential loss is given
Lexp (W) = 1 Σ
Σ exp (-(e,, - -ea) -e) TWh))
n
sE
[m]
cntys
30

---

The gradient of (W) is
V Loxp W) Σ
ΣΣΣ=
expl- -e,) Wh:)),, -eol!
kE(n] cg
Thus, for any matrix A TRa we have
(4, Cexp W)) 7 Σ ig|m] Eotn. exp (-(eg, (e)Thh)) (e -ca) Ah.
This motivates to define g(W)
gexp W) Σ
E exp (-(eg: ee)
T Whh).
iE/nl oR
from which we recognize that Sexp (W) Lexp( W). Then, the proof follows similar steps as the
CE loss.
F.2 PairLogLoss
The PoirLsgLsss loss [72] is given as
Pn W
Σ iE(m) ca
log (1 + exp (-(ey, - ex) Toh)))
T.
Note that L = 1/2 Eien) Extn. I ((ey, ee) Wh;) where f(l) log(1 + e-t) denotes the
logistic loss. Therefore, the Taylor expansion of PLL writes:
(W (W + A) L(W)
S ((eg -ec) -ee) Wh.) (ey, - ee) Ah: <c)TAh;
VE
Σ
E ((e eo) Whhs) hTj A (ey, - ee - -eo) -eo)TANe Ah;
o (I 13)
ic/n]
(27)
From the above, the gradient of the PLL loss is:
VLnn(W) =
((ey, -ex) Te) (ey, -ex) h??
ic(n) cat.
1
exp (-(ey, - Wh:)
(- e.) Wh:) (ey. to
(28)
1+ exp
xx(
Thus, for any matrix A Rxd
(A, Von
Σ
Σ
I (leg. Te)) 1. (ey, -co) Ah;
(29)
1E(m] ct
This motivates to define
1 Σ Σ f (- -e)) T (.Thhh)))
- ΣΣ -
exp (-(ey, - ee) Wh;
Gpn(
W) Gpn(W)
VEIN c/ exp (-(ey, E6) Wh:)
SEIn] cr
(30)
Lemma 28 (Analogue of Lemma 16 for PLL). For any W, the PairLogLoss (PLL) satisfies:
2B (W) 2 (W)) 2 & Gpu(W).
31

---

Proof. The lower bound follows immediately from (29) and expressing VV WW maxl/llsi (A, VDpn(W)) The lower bound follows from triangle inequality applied (28);
IV L W W) I
1 (- - -ce) Wh;) Iley. eellilh, S 2B g(W),
iE[n]
and use the relationships in (7), i.. p-norm with p 2 1.
VVC (W S VV ( Il for any entry-wise or Schatten
For bounding with (WW) the second-order term the Taylor expansion PLL, note the following. First, for all i E [n], A ye:
h A
(ey. (ev. - e0)² Ah: = ((ey, - (ey - -eo) Ah,h, T A
< (ey, eey, -eo) I1smm
Ah;h; A
max
< |ley. ee)li (11A2;110)
< 4 (| max)?
2 hill I <4B²(11 llmax
I 4 A 1|2.
Second, the (easy to check) property of logistic loss that ("(() S ()((()) Putting these together:
Σ Σ 1" ((eg. (e)TTh.))) h A (ey. ec)(ey, ec)) Ah; g(W) (I)
n VE(n cF
Finally, verify PLL satisfies Lemma 18.
Lemma 29 (Analogue of Lemma 18 for PLL), Let W E IRkxd, we have
(i) 12 (pi(W] (W)
(W)
(ii) Suppose that W satisfies Cau (W) S 1og2 or Gpn(W) S Σm then Con(W) S 2Gpn(WW
Proof. (i) The upper bound follows by the well-known self-boundedness property of the logistic loss, namely (t) < f(t)
To prove the upper bound, it suffices to prove for for > 0:
I 2 log(1 (1 - x) 2 log² + x).
(31)
1 1
The general follows by summing over Vic exp (-(ey: - ee) (Thhh: ; [n], e # ii since then we have
G(W)
Σ iEin
Σ
Σ
log(1 + ric)
log" (1 + xie)
1 Dic
cn
iE(nn)
cF
'E c#
2
Σ
log(1 + xic)
Σ log(1 + xxc)
iE(M) cati
[E|n] cp
where the last line used log(1 2ie)) 2 0. For (19), let log(1 x)) 0. The inequality becomes
< - a - a2/2, which holds for > 0 by the second-order Taylor expansion of e around 0.
(ii) Denote L = Lpll and G = 9pu. Given L < log(2) < we have 1 "c 2
2 2. then the first part
follows from (i). For the second part, denote 4,c = (e e.) W h,, i E [n]. + ye For L < 2g to hold, it sufficient to show that log(1 + hhe) < 2, the for all E [ yi- This holds true when 4, 1.366,, which is clearly satisfied given the assumption & 1 implying li 2 O. Li
-he
2n
Lemma 30 (Analogue of Lemma 20 for PLL). For any vé E [0, 1). we huve the following:
Gpul (W- A
< 22 +2
Spm(
32

---

Proof. For logistic loss f(2) log( 1 + - for any E R, we have the following
f() (=2)
1 + e
1 + c 6 +
|
1 e
1 1 e
e 2
E E
+1
+1
1 e
1+
6²2
1 +1 +1
S - -1 +
Denote ve = (ey, - -e)) T and 1e
= (By - ec) ( 1n4 then we have for [n].
e Vi
f(
(x
S eluic
w -8 w/
+2 enn(ee- Aniil +
+2
f((x))
W
S un/ ا|l mmn
Kao Cyp )h? ?. mm +2
un/ A leo- cv 11.lloa +2
2Bon) max 2.
This leads to Eie(n) Exjy, "( S (ABBl mmm + +2) EiE(()) Eojy. (( Rearrange
and using the definition of Gpn(W) and relationships in (7), we obtain the desired.
Lemma 31 (Analogue of Lemma 19 for PLL). Suppose that there exists W R such that (W) 1og then we have
(ey, -e. 2 0, for all E [n]] and for all E [k] such that e #
(32)
Proof. Denote Dic = (e,, - ec)² Wh; Then, by the assumption, we have for any E [n]] e # y
log(1 + Bie) S
Σ
log(1 + e mic) s log(2).
This implies that Die 2 0 for all E [n]] + ys-
Lemma 32 (Analogue Lemma 17 for PLL). For any W, Wo E Rixd suppose that L(W) is convex, we have
CCnu - Cnu( - 2B W - Woll-
Proof. This lemma is direct consequence of Lemma 28 and can be proved in the same way as Lemma 17.
Thus, we have proved all the Lemmas for Gau and its relationships to Cau W) in analogous to those in section C. The proof of NSD (()) with PairLogLoss follow the same steps as with cross-entropy loss given section D.
G Implicit Bias of Adam
We consider Adam without the stability constant (c), which performs the following coordinate-wist updates for iteration / and initialization Wo [33];
M, B, 1-1 + B1 ((W,)
(33a)
V.
V 1-1 (1 32) V(W,)
(33b)
M.
W W, ntt VV
(33c)
33

---

where M, and V. are the first and second moment estimates of the gradient (with momentum parameters 31 and 32) respectively. The squaring (-)2 and dividing operations are applied entry- wise. In the special case of B1 32 = O, this simplifies to the SignGI updates.
To study the implicit bias of Adam, we further make the following assumption, which ensures that all entries of the second moment buffer Vi of Adam are bounded away from 0 for all t > 0. Previously used by Zhang al. [77] in binary classification, this assumption is satisfied when the data distribution is continuous and non-degenerate. A similar assumption appears in [76].
Assumption 5. The Adam inirialization satisfies V Z( (c))llc, 11a 2 for all E [k] and j [d].
The proof of Adam follows the similar approach as NSD. The key challenge is to connect M, and V, to per-class decomposition of (WW)). The following Lemma in [77, Lemma 6.5] is useful. provides an entry-wise bound on the ratio between the first moment and square root of the second moment.
Lemma 33, Considering the Adam updates given in (5), (33b), and (33c), suppose that 31 S B2 and
(1- Ba] s1y, then we obtain Mz(c, j) /Vi(c, for all c [k] and j E [d].
8a(1-88 8: }
The following Lemma bounds the first moment buffer (M)) of Adam in terms of the product of m with the sume of G.(W, and (.(W) It is used in the proof of Lemma 36.
Lemma 34. Let c E [k]. Under the same setfing as Theorem 5, there exists a time to such that the following holds for all 2 la
[M - (1 - V S (..)( + Q.WW.))
where j E [d] and am is some constant that depends on B and S
Proof. The proof follows the same steps Lemma 25 with |||| replaced by
M VV
max
The following Lemma bounds the first moment buffer (V:) of Adam in terms of the product of and with Ge(W,) and 2. (W,). It is used in the proof of Lemma 36.
Lemma 35. Let E [k]. Under the same setting as Theorem 5, there exists a time to such that the following holds for all 2 to
Vilcc. ([ -M av G.W)))
where j [d], and av is some constant that depends on B and 32.
Proof. Consider any fixed c [k] and j E [d].
-
Σ (1 )
[c(W.)(cc.513)
r=0
(1 82)8 VC(W,->Mc.511 F
(34)
For any W E Rkxd, recall that - E e" (eg. s(Wh:))hup Then, we can obtain VL(W)
[c, j| = मे Exern Epetn high (dey; - (h;))) (55r,, - S. (Wh,)) where dey = if and only if y. Next, we define the function foiip to be foep (5 (Wh:))) (Wh,)). Then, we have
|fca (W,-r) - forp
(Wi) [W)]== = dey, (Wih,)) - (, + dey, (W,h.) - (W...hh)
(w. (W,-,,,) hhp) S.
34

---

We can substitute this result into to obtain
hishes (W.) - (Wi)) Wi))
iE na]
pE[n]
1
Σ
Moipp(Wi1) - (w.)
2²
iE | pE(n)
B
Σ
E
(eee(Wer)) - fc (i)l
(m). the pe tnl0t
+ n
B
Σ
E
Uaip(WrrF) -
-W Saip (Wa)
iE (ell)
+ n
B2
Σ
E
(W,r) - (W,)((.))))
iE Pe pE(n).aptt
+
B² n²
Σ
E
(Wii)( (W,)
k (
We deal with the terms
3. and
separately. Starting with the first term, we have
(. hkp) (. (W,h,))
π
iE(n] to
pe in) to
S. (W, ). h2p)
Σ
E
(W.hh)))
(,,, W.l)pp)
iE Mh to pe R Whe
&...h.sS. (W,h,,)))) (ICW W +1(W, -w.hhplox) - -1)
Σ
Σ
n
iE (imm. pē No
(6)
Σ Σ
(W (W,h,,)) (B
W.-r |
11
:E(n).ui c He
(0)
3 (e
4B E.mm W--
Vo- max 1)
M,_,
Σ
Σ
n2
sE|n) #o ve
( < (e Viz - 1.) QW.)?
where (a) is by Lemma 15, (b) is by |////1 < B for all E [n]. (c) is by (33c) and the triangle inequality, and (d) is by Lemma 33 and the definition of G(W,) For the second term, we have
Σ sE(n). #c B
Σ
(W.h,) - (wi,,hh))
n
(S. h. - (wW
Σ
Σ
(W,h, SI- (W.h,)) -
(1
(E(n) to _
1
S. (Wi,,) - (wWhk)) (1 - (w, (1 S. W,h,, S. (Witz:)
Σ
Σ
n
EE(n).y. to ||| c
< Bo Σi 7
Ce (W.).
35

---

where the last inequality is by Lemma 15 and the same steps taken for 1 The third term can be derived similarly as the second term and we can obtain the same bound as follows:
Σ
S
(1
T1 iE(n) = =c DE Mo
(1 (W (.
< (6 AB Σiz
2. (W))
For the fourth term, obtain:
Σ
E
-1- (1-)
- (.,,(.)))))) (.
SE SEin] .3 =C
p Me
(1 (1 - (1 (1- (Wihi))) (1- (W,hp))))
n Σ
Σ
(1 (w.h))
$ (e Th- - (W,)
where the last inequality is by Lemma 15 and the same steps taken for 1- We combine the bounds
for 2. 3. and 1 to obtain:
4B² 4B² (c4Ba Exm th-- (G. (W,) + (W.)). Then, we
substitute this into (34) to obtain:
[Ve. - (1 VZ.. B² (1 & Σ 85 (e AaBBiii Eimr Ne-e 1)
s B² - 32) + (WW))
where the last inequality is by the Assumption 3. The final result follows from the fact that Ip - gl2 Ip² q²1 when both p and q positive.
The following Lemma bounds the term C)W,,, M.
VV. NEW using 9 ((W)). It is used in Lemma 37 to show the decrease in the risk. The proof is similar to that of Zhang et al. [77, Lemma A.3], but here we need to carefully track the index e E [k] using both G.(W) and (W) to avoid A dependence. The final result crucially relies on the decomposition G(W,) Eee( (WW)
V.(.))
EeERH (W,,
Lemma 36. Under the same setting Theorem 5, we have
M.
V((W))
81+1
(VL(W)
$ 4 41
VL(W,)
Iumm
V..
VC(WO)
32
2d
bav
vtt + 3.
vI 32
32411
Proof. For simplicity, we drop the subscripts t. Denote To(W) Gc((W) + (wW. Then, by Lemmas 34 and 35, we have for any E [k] and j E [d]:
M|c,]] = (1 2 WL( + a. To W).mm.o
(35)
VV = v .0 (VL(W) av Tv (W))
(36)
where
|em,n.sl < and lennl < are some residual terms.
We denote
McaJ] Vaj = [c, V((a
VL(W)c [c.j] [VC(W) No.2]] the set of index Eaj = {j E [d]
VC(W)cc.d] 2 20v (W) and its complement E = [d]VE... The
36

---

goal is to bound
|eal when j E Eig or j E Eas using TwW..
We start with the indices in B
M cc jll
Σ
| -
Σ
(c
V[e, +1)
JEFE
JE
(1 81+
(c((W)...ll) + aa +1)
VI 32 VL(W
(6)
30+1
+1) 2av V TT (W)
aMMi (W)
12
V1
185t1
VI-
JEP
d
40v
VTe + aamm))) (tam))((WW)) T(()..
v1
13
3/+1
where (a) is by (35), km.e I 1, and V [c, 2 (1 (cw) and (b) is by j E E s.t.
[L((W) < 2
M (W) Next, we focus on the indices E Fe..j. In this case, we have
Mccj]
VC(W) [c,j] VC(W) [c,]]]
He. = vc(W)
V1- 52- VL((W]c + ov (TT)(())ocs.
Mc. ( av ToT (W) (e,es)) VC(W)(c)
[C(W)(
(VI VC + av aT TTW VV
where
(1 g/ [
a Tel W Wi
(0)
- 1- 8 +
and
(d) 1
82 [C(W)]..
Inequality (c) is by lem.osi < and lev.osl < 1, and (d) is by av (W >
32 VVL() [c for any j E Eeg-- Putting these two pieces together, we obtain
Wesl S 11-
1 8
VL(WW) [c, + (amm + av av VV
Σ jEF
1 1/1 1/1--t110 (C
jeF
8tt1
2av
2a
4
VC(W)(e. + +d(
V +
111 (W
JEENJ
g
B541
V 1--tt
8++1
d
2ay
< 4
VL
ammmm
Ti +220 To (W))
8.4I
V1 82
3/41
where (e) is by Va S Va- b+ Vb implying 1 the cth row of VL(W). Finally, we note that
35
S $ [+]
and VL(W)(c, denotes
(VL(W),
M
VO() ) = E(en) Deyl S
VV
37

---

E(e,)) |egl Then, we obtain
Σ 6u
Wool = Σ
Wool+ + Σ
(osl
DE [R] JEBE
jeEci
g
d
20v
VC(W) -1,
VTT + 22 TorTTiTTTT (W)
$2
V1
B2
V 12211
CE|R
cE[K]
g8+11
2d
20y
4
1V
VV((W) |1 sum
+
V +
VI 32
V
5/211
where (f) is by Eee(k) Tw( = EeE(H) 2c + Gc( = -.
Lemma 37 (Adam Descent), Under the same setting as Theorem 5, set LA = 2 log( y 82 have for all & 2 LA
then
log ((.)
((W(41) S C(W.) - ne - Cu2 2212 avz dni aes dm: ((W,,,
where Cag Oag and Olag are some constants that depend on B, 7,81, and $2.
Proof. We follow the same
notations
and strategy of Lemma (VC(W), A,) and +
21,
and recall the definitions (TragS((W,,o-1) Wo,,+1, h.)) - (WW,+ ( A,
h A T (diag(S(
h,. In the case of
Adam, we have A M. We bound and o separately. Starting with we have for all
VV.
t 2 l
Mc VV. M,
(V.(W..
VL(W.)
(V)(W))) VC(W.) M.
VV,
VL((W))
VC(W)))
VL(W))
S S-mel/cC(W) ) + m
(VL(WW))
VV
VL(W.)
(0)
-n-(1 (1 $1
B
8211 |[VC(W)
2d
6ov
Ti + 330mmn))((W)
#
sum
VI B2
11-3h47 g141
S <-1((1
Bi
12av
dMl
3/2 g(3))
6aM
(WW)
VI - B2
sum
- B2
VI- B2
(b)
12av 3/2 g(W.) + VI-Ba 32 1- B2
60rM d()))
7 (1 4
VI 32 WW,
dujt
where (a) is by Lemma 36, and (b) is by Lemma 16. For 1, we apply Lemma 12 to obtain
S 4 A (1 Sy, (W (Wit+igc-h. h.)) s 4n a² 2²2 Sy, (Weeti.-hhe),,
where in the second inequality we have used || || $ A 1 || lll I B, and
A Il = 1/1
M.
S aha by Lemma 33 given / 2 LA implying that 1 2 4 VI P2
Combing
VV. this with Lemma 12,
we obtain
Σ h A
(diag(S( (S(W..1,, - S.W.....ch
A. h;
2n [m|n]
Σ
Amia B² Sy, (Wi,t1..:h)) hi)) S 2a² 2 BBx
1E
38

---

where the derivation of the second inequality can be found in the derivation of 22. Putting everything together, we obtain
o7
12ay 3/2 g(W,)+
(W) E((W)
+ (W + 1- 32
dmp
VI -2
60M
-1 + BBn) )
= L(W,) m)((1 Olay 8//²
Olaz dnj
Claz dmp)) (WW.).
where we have defined Ota ==
4 VT-M5 Gag =
12av and Oag == mv 2a 2a² 2
60
Built upon Lemma 37, we can further lower bound the unnormalized margin of Adam iterates for sufficiently large t. The proof is similar to that of NSD (i.e., Lemma 22), which crucially depends on the separability condition obtained after achieving low loss (Lemma 19). The time t will be specified in the proof of Theorem
Lemma 38 (Adam Unnormalized Margin). Under the same setting as Theorem 5, suppose that there log for all > i, then we have for all 1 LA max(lA,] 1}
exist l such that L(W.) S
n
t-1
g(W.)
t-1
min tE(n))ec=
(ey, - -e) ) W.W, 2 7
Σ
ns
C(W,)
Clag
Σ
Cag
Σ
Clazs
s=tA
a=ta
2 logt vI and Clags Clag and Oay are some constants that depend on B, 31, and B2.
where t
(3)
12av and Ong Proof. We denote Clas -1- Clas T-82
2a BBm Under the VI-B,
Gam
assumption that L(W))= S n
1og for all 2 E. we have for all fA max(tA, f) (recall that
tA = 2 2log( V=-#2)
10g(31)
(a) C(W++1) I ((W)) - m + a., B7 (),((w,) + a dn, ((W,) + aaa dn
9(W,) + aaa 8i dn
((W.)(1 TEY ((Wi)
aagdi
g(W,)
< L(Wi,) exp(-> Σ
+ Oas? Σ
B + Oaa d
Σ
n + aag Σ 17
((W.)
s=tA
s=ta
a=la
(6) log
g(W,)
exp
n
aas Σ
1T + aaa d
Σ n2 + Car)
L(W.)
B=tA
s=ta
s=tA
where (a) is by Lemma 37, (b) by
((W)
(shown in Lemma 18), and (c) is by C(Wi,) W.))
log2
((W)
and Oiay 7 E.= LA 3 1/s
<
700
0ar
The rest of the proof follows the same arguments in
1-87
Lemma 22. Namely, the assumption ((W,) S log2 implies that min in (ey, TW,, 2 0 for
n
all i [n]. This separability condition can be used further to show that for all 2 fA
g(W.) Yl L(W,)
t-1
ww (ey.--- W.h. < exp(-7
Σ
angd Σ
n + anag
Σ s=
11 + (ro))
SEEA
s=
Taking the log on both sides leads to the final result.
Next lemma upper bounds the max-norm Adam iterates. involves showing that the risk upper bounds entry-wise second moment, which will become small after the risk starts monotonically decrease. Its proof can be found Zhang et [77, Lemma 6.4]. Here, we only show the steps that specific in our settings.
39

---

Lemma 39 (Adam W max) Under the same setting as Theorem 5, suppose that there exists for all 2 iB, then we have
B > log ) such that ((W)
v /44
Ën Σ
W Wellmax
Cas
Ns
+
Σ
n +
W maxe
8=0
s=te
where Oag is some constant that depends on B, B1, and 82.
Proof. For any E [k:] and [d]. we have for all t ts
(0)
Vl
WV 1A3 I 1
(1 (1- V
aw,)
c 5|2 + avmg(W,))
4B.)(W.) 2 (WW))
(4B² - <o 1
where (a) is by Lemma 34, (b) is by Lemma 16, (c) by Lemma 18, and (d) by the assumption. This implies that for all / 2 in
0 ž loogoVo(c...oooo (V(c.))) 2 log (1 Co). j13) 2 (lgg(32) log(1 (22 + log(w,,
where (e) is by the Assumption 5. The rest proof follows the same arguments in Zhang al. [77, Lemma 6.4].
Theorem Suppose that Assumption 1, 3, 4, and 5 hold, and 31 S B2, then there exists tos loo (n, d, 7, B, Wo, B1, 32, w) such that Adam achieves the following for all t > tez
min ee (ey, - TWW, /
? S S0 Exsto
AsE 7 Dimtn Te
taz-1 ns d 1-1 3/2
Lo=lag 178
Wellmax
Proof. Determination of ter Here, consider learning rate schedule of the form ne = e
where (0, 1]. We choose ta, after (max/to, tA, log(.)) where to satisfies Assumption 3 and
LA 2 log( /1 22] such that the following conditions are met: 0a101/2 S f/6 Oag dult 1/2 < 6. (36a 2 2//1/a (6a,s d) 1/a] =
1
log 31
and aag dn S 8. Concretely, we can set ta. = max -ogg(()).))) log,81
(d8/)). Then, we have for all 2 ta
L(W & L(W,)
7 ((W)) 2
(37)
Rearranging this equation and using non-negativity of the loss we obtain Ei=to, ng9(W,) - 2C(W. Determination of tag. By Lemma 17, bound L(W,,, follows
taj - 2B
taj
M,
(C(W,,,) L(W))l < 2B W.,, Wo max
<
2Ba
n
VV.
==0
max
==0
where the last inequality is by Lemma 33. Combining this with the result above and letting e min log
+aB2+avm }), we obtain
g(W,-)
min se sE(tyyfag)
g(W.) 2C(Wo) + 4Ba Σ lay
17
E
1
fug 1s 7
2
2n'
40

---

(C(Wo)+8Bo Ein
from which we derive the sufficient condition teg to be Ei 7 Convergence of G.W)) that
1/.
96
We follow the same arguments in the proof of NSD (Theorem 3) to conclude [(W)
g W ((W,)
21- - E T
(38)
We note that fag satisfies the assumptions in Lemma 38 and Lemma 39. Margin Convergence Finally, combine Lemma 38, Lemma 39, and (38) to obtain
[ul. (eu: -co)² Wih: |eellmax
1 No0 -1 EEtiiop +
= 1/s
log -1
+ d Σ.
Lostay 1700
3/2
+
di 13
>1 s 00
E/3 1/5
+ +
0
f0z
n/ + d Es=tag
175
3/2
1 00
Ex=0 f
Similar to the case of NSD, we can derive the margin convergence rates for Adam.
Corollary 2. Consider learning rate schedule of the form T/t = ( ( where (0, 1), under the same setting as Theorem 5, then we have for Adam
0 odd 3a 20mm)
Wlo
< if a
p1-2
mml. (cy. - Wih; Wellmax
0
(ood(U)td+n2 [log [log(
if a = 3
7
1/3
+nC(W,) [lg(1//))
0
if 3/ < a <1
d4n d4n log(d) Wo + log log( log(1/w))
0
if a = 1
log
Proof. Recall that tu = O(d2/a) = Co 82/a, and the condition on tag (C(W))+-B3 Ensy
4 Zamta n
}. Then, we apply integral approximations and the rest of the proof can be found in [77, Corollary 4.7 and Lemma C.I].
? where É min log n
2:
Remark These rates match exactly those in the binary case of Zhang et al. [77] with logarithmic dependence on the initialization parameter w (Ass. 5). This is only made possible through the fine-grained per-class bounding of the first and second moments using both G.W and (.W)., Note that Lemma 36 takes the same form as Zhang et al. [77, Lemma A.4]. However, without the tight per-class bound and the equivalent decomposition of ((W) using either (W) or G.(W), ). an extra factor of k would appear. Interestingly, our rates for SignGD in Corollary I reveal a theoretical gap: d dllog(t) while SignGD achieves O log(t)+ ) with a = 3 t313
Adam's 's optimal choice a = 2 yields O Despite achieving tightness w.r.t. class-dimensioe (k), this gap emerges from our entry-wise analysis of the term Lemma 36 across the feature dimension (d) using scalar functions Gol (W), (W). Closing this theoretical gap-revealed through our NSD analysis- that also appears in the binary case [77]. forms an important direction for future work.
1//2
Numerical Validations We test the margin converge of Adam with different stability constants (c)
chosen from the set {0, 10 6 10 10 $]. We make the following observations: (1) SignGD/Adam vs NGD: SignGD and Adam zero stability) iterates favor the max-norm margin over the 2-norm margin. The opposite true for NGD (Figs. 5c, 5d): (2) Speed of convergence: For the learning rate schedules considered, the margin convergence of SignGD is faster than that of Adam (with zero stability constant), consistent with our theoretical results (Fig. 5d): (3) Effect of Adam's 's stability constant: For Adam with zon-zero stability constants, when the magnitude of the gradient (or the second moment) is above the stability constant, the convergence to the max-norm margin is favored over that to the 2-norm margin. However, when the gradient values approach or fall below the stability constant, the max-norm margin starts to decrease while the 2-norm margin increases. This shown in Figs. 6a and 6b (compared against the case of zero stability constant in which the max-norm margin
10--0.
41

---

14
Acems p-jace ACB 1-160
(a) Loss
(b) Gradient Norm
(c) 71-122 = 2.11
(d) 71- max 17.83
Figure 5: Implicit bias NGD, SignGD, and Adam on multiclass separable data (A: 5,d 25, and 50 data points in each class). (a,b) Loss and gradient 2-norm iterations: SignGD converges faster than others. (c) We normalize the iterates w.r.t. 2-norm (aka Frobenius), compute the margin, then plot its difference converges to the max 2-norm margin. (d) Same as (c) with 2-norm replaced by max-norm. Margins of SignGiD/Adam(with
the dataset's max- max-margin w.r.t. 2-norm (given in captions). Only NGD
0) converge max-margin w.r.t max-norm. For SignGD, the training is stopped after 10 iterations due to the numerical instabilities caused by the small gradient norm.
035
120
(a) Relative Loo margin
(b) Relative La-mangin
(c)
(W..V)
WW.V
Valla
W[ V.
Figure 6: Effects of non-zero stability constants for Adam. We focus on late training stage between
iteration 10 iteration 10 (a) Gradient 2-norm iterations. (b) Same quantity as Figure 5d. We observe the max-nore margin of non-zere stability constants decreases after gradient magnitudes approach or fall below the values of the constants (drawn horizontal lines in (a)). (c) Same quantity as Figure 5c. After 10a iterations, the non-zero stability constants start to increase towards the max 2-norm margin. (d, Correlations between W, and max-margin classifiers V2, V.o against iterations. Considering correlations to 22 its value stays nearly constant for the zero stability constant, whereas rise after 10t iterations for non-zero ones. We also observe the transitions occur earlier for larger stability constants. Considering correlations to Voo, the values rise and plateau for non-zero stability constants. However, its value keeps increasing for the zero stability constant.
keeps increasing). Moreover, the max-norm to 2-norm margin transition occurs earlier in training for larger stability constants. The experiments Figs and 6c further confirm this two-phase behavior given the correlations to the 2-norm separator V2 rise while those to the max-norm separator Voe plateau in the late training stage. These experiments confirm that the results of Wang et al. [68] also hold in the multiclass setting provided that the stability constant is non-zero and the magnitudes of the second moment are small (compared against the stability constant). Note, however, that the stability constant is typically chosen to be very small (c 10 and the training is not long enough until all gradients are below this value. Thus, the max-nora margin convergence results are practically relevant.
42

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: See Sec.
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 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: See Sec.
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 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 few datasets 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-ted 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, 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 a complete (and correct) proof?
Answer: [Yes]
Justification: See Sec.
Guidelines:
43

---

The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs 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 if they appear in the supplemental material, the authors are encouraged to provide a 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 supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: See Sec.
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.
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 a 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 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 a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurlPS 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 a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is 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-soure dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, 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
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
The code is provided in supplemental materials.
Guidelines:
44

---

The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm cc/
mablic/guides CaaieesssCoSSuubiiseee casssoooPlly for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / //nips. wwtpccccpcc/ccceccccccccccccclct gww.//g///////ee/// /
/CodeSubmisse wwwssssssiiiooooee.ooooosssissis for more details.
The authors should provide instructions 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 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 in supplemental material (appended to the paper) recommended, but including URLs to data and code 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: See Sec.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to 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: The algorithm is deterministic with no batching involved.
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, 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).
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).
should be clear whether the error bar is the standard deviation 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 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 error rates).
45

---

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
Question:
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?
Answer: [Yes]
Justification: See Sec.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or 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 the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethies
Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: / http///eerrpp.epeee
Question:
Answer: [Yes]
Justification:
The paper follows the code of ethics.
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 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 societal impacts of the work performed?
Answer: [NA]
Justification: The paper is theoretical.
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 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 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 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 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 being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
46

---

The answer NA means that the paper poses such risks. 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 MI.).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: No such risks.
Guidelines:
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 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 the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: No existing assets used.
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 is used and, if 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.
assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of 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 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 assets?
Answer: [NA]
Justification: No new assets released.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodll as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
47

---

The paper should discuss whether and how consent was 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. 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 details about compensation (if any)?
Answer: [NA]
Justification:
No crowdsourcing and research with human subjects are involved.
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 contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According 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 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: No crowdsourcing and research with human subjects are involved.
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.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: No LLMs usage involved.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to LLM policy (httpa: /ttpaaa////urr....//e http://uuipp.cc/oofeeeeeeeeeeeee wwt.///ofeeenee///20000000 for what should or should not be described.
48


Reviews:
[{"review_id": "pO6gEPCCO1", "reviewer": "Reviewer_ZRz3", "summary": "The authors characterize the implicit bias of p-norm normalized steepest descent and its momentum variant for multiclass linear classification with cross-entropy loss, proving that both families of algorithms converge in direction to maximum-margin classifiers defined by the same norm. They derive explicit non-asymptotic convergence rates of $O(1/\\sqrt{t})$ for NSD and NMD. They further show that Adam converges to the $\\ell_\\infty$-margin solution under an appropriate step size.", "questions": "1. How sensitive are the convergence rates and maximum-margin solutions to the choice of p in the p-norm normalization? \nCan you specify how the hidden constants in the $O(1/\\sqrt{t})$ convergence rates depend on the choice of p?\n\n2. Have you conducted any empirical validation to confirm that the theoretical convergence rates or implicit bias manifest in real datasets?  \n\n3.  What intuition can you provide on which norm normalization is most beneficial under different data or task conditions?\n\n4. How do the results change when we deal with non-linear models in experiments?", "limitations": "While this work provides finite-time implicit-bias guarantees for p-norm normalized steepest descent (NSD) and its momentum variant (NMD), its scope is limited. The analysis is confined to fully linear, multiclass separable problems trained with exact, full-precision gradient updates and cross-entropy loss, leaving open the question of whether these results extend to deep or non-linear architectures, as well as stochastic or mini-batch training.  I understand the complexity of the theoretical analysis with more complicated settings, but it would be nice to conduct the experiments to explore whether these results can be extended and made more practically relevant.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The paper’s key contributions stand out in its combination of the finite‐time analysis, a unifying optimization framework, and empirical confirmation:\n\nStrengths:\n- The authors provide the first non‐asymptotic implicit‐bias guarantees for normalized steepest descent (NSD) and its momentum variant (NMD) on linearly separable multiclass classification tasks.\n- The authors consider a broad algorithmic family—p-norm normalized steepest descent (NSD) and its momentum variant (NMD)—which includes practical optimizers such as Muon and  Adam, unifying their implicit-bias dynamics under the steepest descent with unit balls. \n- They provide explicit non-asymptotic convergence rates of $O(1/\\sqrt{t})$ for NSD and NMD.\n- They present rigorous, non-asymptotic proofs that connect the algorithm's convergence directly to maximum-margin classifiers.\n- They also empirically verify that signGD, NGD, spectral descent, and Muon converge in direction to their corresponding maximum-margin solutions. \n\nWeaknesses:\n- Analysis is limited to linear models with cross-entropy loss; extensions to non-linear or deep architectures are not addressed.  \n- No empirical validation is provided to confirm the theoretical convergence rates or practical impact on real datasets.", "was_revised": true, "final_justification": "As I described the paper is good and I maintain the positive score", "rebuttal": "We sincerely thank you for your positive assessment of our work. Here, we address your comments/questions in sequence: \n\n***Other Losses*** The convergence rates also hold for other losses. We have discussed these extensions in Appendix F. \n\n***Dependence of p*** The margin $\\gamma$ naturally depends on p via its definition in eqn. (2), and the convergence rates in Thm 1 and 2 hold for any p. Our current analysis does not explicitly track how the constant depends on p. However, inspecting the analysis steps in Sec. 3 (i.e. lower and upper bounding the first and second-order Taylor terms respectively) reveal some insights. First, for all values of p, the dual-norm of the gradients is lower bounded by the same proxy function multiplied by the margin $\\gamma$. The proxy function itself has no p-dependence. When it is used to upper bound the second-order term (see the display after Line 198), the bound depends on the norm of the features. Currently, we are using the upper bound on $L_1$-norm of the features, denoted as $B$ (i.e. $max\\_{i \\in [n]} \\lVert h_i \\rVert_1 \\leq B, \\forall i \\in [n]$). The constant $B^2$ can be substituted by $max\\_{i \\in [n]} |||h_i h_i^T|||_{p}$ (note that this reduces to $max\\_{i \\in [n]} \\lVert h_i \\rVert_p^2$ for entry-wise norms, see lines 195-197), which captures the geometry of the features. We will include this comment in the final version of the paper.\n\n***Intuition on the choice of norms*** This is a good question and in-part is one of the motivations behind implicit-bias analyses like our paper. Specifically, having shown that different norms in NSD/NMD maximize margins of the dataset w.r.t corresponding norms, facilitates the generalization question: which p-norm generalizes better? Of course, the answer depends on the data in complicated ways. In the linear case, this can be thought as follows: p-norm NSD favors convergence to a classifier that maximizes p-norm margin. Let the underlying data distribution be parameterized by a matrix which can represent the parameters of multinomial logistic model or the mean-vectors of multiclass Gaussian mixture (as an example). If the matrix that generates the data is sparse, SignGD is preferred; if it has a balanced spectrum, Spectral-GD is preferred; if it is low-rank,  low-rank GD is preferred and so on. While we recognize the limitations of this setting, it can provide some initial intuitions towards the choices of algorithms in different cases. \n\n***Experiments (real datasets)/theory on non-linear models*** We performed additional experiments on MNIST dataset (100 data points sampled from each of the 10 classes) in the  non-linear multi-class setting. We use a two-layer MLP with random initializations and the hidden dimension being 100. We only train the first layer and track the spectral-norm margin (as an example) of the overall network defined as follows: $\\min_{i \\in [n], c \\neq y_i} \\frac{(e_{y_i} - e_{c})^T W \\sigma(H x_i)}{||| H |||_2}$, where we denote the first and second-layer weights as $H$ and $W$ respectively, and $\\sigma(\\cdot)$ is the Relu activation function. We observe that the spectral-norm margin of Spectral-GD grows the fastest among the three algorithms considered (SignGD, NGD, and Spectral-GD). This confirms that the norm preferences of NSD algorithms (exhibited in the linear settings) can also show up in the non-linear settings. We will incorporate these experiments in the final version of the paper. From theoretical perspectives, despite being in the linear setting, we are the first to formally prove the implicit bias of NSD/NMD for the multiclass data. The extension to the non-linear (multiclass) settings is challenging and we believe our work provides the ground for such future studies.\n\nTable: Spetral-norm margin of SignGD, NGD, and Spectral-GD at different iterations\n|        |  $t=5000$     | $t=10000$    | $t=15000$   | $t=20000$  |\n|--------|--------|--------|--------|--------|\n| SignGD   |  0.1292 | 0.1248 | 0.1138 | 0.1056 |\n| NGD | 0.1643 | 0.1766 | 0.1821 | 0.1820 |\n| Spectral-GD  |  0.2474 | 0.2920| 0.3142 |  0.3280 |\n\nThank you again for your time and suggestions. Please let us know if there are any further questions."}, {"review_id": "2BXTC3KNr6", "reviewer": "Reviewer_KwWH", "summary": "This paper provides a comprehensive theoretical characterization of the implicit bias of a wide family of normalized steepest descent (NSD) and momentum descent (NMD) algorithms in the setting of multiclass linear classification with cross-entropy loss. It includes special cases such as Spectral Descent and Muon, both of which are shown to converge to the maximum-margin classifier with respect to the spectral norm. The authors present a unified analysis framework using a carefully constructed proxy function $G(W)$ to track both the loss and margin convergence, and they further extend their results to Adam. Experimental results validate the theoretical claims.", "questions": "1. In Figure 2, your results show that Muon and Spectral-GD converge to the same solution $V_{\\text{spec}}$, right? Within your theoretical framework, what is the implicit bias of the momentum term? Is it possible that the linear model setup is too simple to reveal any difference? As we know, in general nonlinear networks, momentum-based methods like Adam and SGD often prefer different solutions.\n\n2. During optimization, we typically do not constrain the norm of the parameter matrix. So in Theorem 1, is the margin gap result obtained by normalizing with $\\|W_t\\|$? In the caption of Figure 1, how exactly is $\\gamma_{\\bar{W}_t}$ computed? Is it also a normalized result?\n\n3. For Adam, you consider the version without the stability constant. In practice, Adam with $\\varepsilon$ is more common. Why was $\\varepsilon$ omitted, and how would including it affect the implicit bias?\n\n4. Do you expect your convergence results for NSD/NMD to generalize to nonlinear models (e.g., two-layer MLPs)? Can the proxy function idea be extended to such cases?\n\n5. How sensitive are your results to non-separable data? Is there still an implicit bias guarantee when separability only approximately holds (e.g., with margin slack)?\n\nOther minor comments:\n\n1. Table 1: \"Refernce\" → should be \"Reference\".\n\n2. The symbol $e_{y_i}$ in Equation (2) appears to be a standard one-hot vector, but this is not explained upon its first appearance.", "limitations": "The experimental scope is limited—restricted to small-scale, linearly separable synthetic data.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\n1. Despite being set in a relatively simple setting, the paper develops an elegant and reusable framework via a proxy function  $G(W)$ that enables generalization across a broad family of optimization algorithms.\n\n2. Muon has recently become popular, and the authors provide new insights into the implicit bias of spectral descent and Muon in multiclass linear settings.\n\n3. The paper is well-organized, with a clear exposition of the background. The related work is thoroughly cited, the theoretical results are solid, and they are supported by experiments. The writing and logical flow are excellent.\n\n**Weaknesses**\n\n1. Strong Linearity Assumption: All analysis is restricted to linear classifier models, which limits the applicability to real-world nonlinear neural networks. There is no discussion of whether or how the results might extend to nonlinear models.\n\n2. Empirical Results Are Limited: The experiments are only conducted on synthetic linearly separable datasets. Whether the approximate implicit bias predicted by theory still holds in more general settings remains an open question worth further exploration. That said, I believe the theoretical contributions of this paper are already substantial.", "was_revised": true, "final_justification": "Resolved Issues:\n\nTechnical issues have been addressed, including clarification of additional experimental details.\n\nUnresolved Issues:\n\nThe work lacks detailed discussion and analysis of nonlinear model results.\n\nWhile most of my questions have been adequately addressed, the paper remains constrained to linear classifier models. This presents a significant gap when considering nonlinear models, limiting the broader applicability of the findings.\n\nOverall, I maintain my score of 4.", "rebuttal": "We sincerely thank you for your positive assessment of our work. Here, we address your comments/questions in sequence:\n\n***Effects of momentum*** For the setting considered in this work, momentum does not change the implicit bias in terms of margin convergence w.r.t a specific norm. Indeed, Figure 1,2 reveal that both spectral-GD and Muon favor the spectral-norm margin over the others. We are not making any claims regarding the non-linear setting. One thing to note is that preconditioning may also play a role in the implicit-bias difference between Adam and GD. \n\n***Normalization*** In Thm 1, the norm used for normalizing the weights is the one used to define the algorithm (eqn. (3)), and the margin (denoted as $\\gamma$) is defined w.r.t. the same norm (eqn. (2)). For example, the margin of (normalized) iterates of SignGD (i.e. NSD w.r.t max-norm) converge to the data margin defined w.r.t the max-norm according to Thm 1. We want to emphasize that normalization in Thm 1 has nothing to do with modifying the algorithm. The algorithm runs as if it has no norm constraints. But because the norm of the parameters diverges in training, normalization is necessary to show convergence. In experiments, we compute the margin of normalized iterates (denoted as $\\gamma_{\\bar{W}_t}$) where the norm used in normalization and defining the data margin are the same. For example, the iterates of SignGD can be normalized w.r.t max-norm, Frobenius-norm, or spectral-norm. Regardless of which norm is used, same norm needs to be used to compute the data margin when plotting their differences. We are doing this for the purpose of demonstrating norm-preferences of a chosen NSD/NMD algorithm.   \n\n***Stability Constant*** The stability constant ($\\epsilon$) can play a role in the implicit bias of Adam. Adam can favor a $L_{2}$-norm margin with a non-negligible $\\epsilon$ [1]. However, this happens when the values of gradients are below $\\epsilon$ (which is often chosen to be very small such as $10^{-8}$). In practice, training is typically not long enough for this realization to occur. Thus, Adam with negligible $\\epsilon$ (i.e. max-norm solution favorance) is still practically relevant. We have provided a detailed discussion on the effect of $\\epsilon$ in Appendix G (see pg 39,40). Our experiments in Figure 5 (in Appendix) demonstrate the transition from max-norm to $L_{2}$-norm margin favorance (after extended training), and hence consolidate that the findings of [1] and [2] also hold in the multi-class setting.   \n\n***Non-linear settings*** Despite the analysis is done in the linear setting, our work is the first to completely characterize the implicit bias of NSD/NMD algorithms for multiclass data. The extension to the non-linear settings is challenging and we believe that our theoretical techniques/insights can be helpful for such future studies. To motivate such theory extensions, we have performed (and will include in the final version of the paper) the following non-linear experiment: train a 2-layer MLP (with Relu activation denoted as $\\sigma(\\cdot)$ and hidden dimension being 100) on MNIST dataset (100 data points sampled from each class) and track the spectral-norm margin of the model defined as $\\min_{i \\in [n], c \\neq y_i} \\frac{(e_{y_i} - e_{c})^T W \\sigma(H x_i)}{||| H |||_2}$ (note that $H$ and $W$ denote the weights of the first and second-layer respectively, and we only train the first layer). We observe that the spectral-norm margin of spectral-GD grows the fastest among the algorithms considered, suggesting that the implicit bias to respective norm (demonstrated with spectral-norm) is preserved in these non-linear settings. \n\nTable: Spetral-norm margin of SignGD, NGD, and Spectral-GD at different iterations\n|        |  $t=5000$     | $t=10000$    | $t=15000$   | $t=20000$  |\n|--------|--------|--------|--------|--------|\n| SignGD   |  0.1292 | 0.1248 | 0.1138 | 0.1056 |\n| NGD | 0.1643 | 0.1766 | 0.1821 | 0.1820 |\n| Spectral-GD  |  0.2474 | 0.2920| 0.3142 |  0.3280 |\n\n***Non-separable dataset*** For the non-separable data setting (e.g. [3]), we would expect margin convergence (w.r.t a specific norm) to hold in the separable subspace. This type of implicit bias has been shown for GD (as a follow-up to implicit bias on the separable binary data) [3]. Our work makes it possible to extend the analysis to NSD on multiclass data, which is an interesting future direction. We will add this in the future work discussion.  \n \n***Additional comments*** Thank you for these comments. We will fix them in the final version of the paper.  \n\n[1] Does Momentum Change the Implicit Regularization on Separable Data, Wang et al\n\n[2] The Implicit Bias of Adam on Separable Data, Zhang et al. \n\n[3] The implicit bias of gradient descent on nonseparable data,  Ji and Telgarsky\n\nThank you again for your time and suggestions. Please let us know if there are any further questions."}, {"review_id": "wCVUokVgDm", "reviewer": "Reviewer_cptr", "summary": "This work analyzes the implicit bias of normalized steepest descent NSD (with and without moment. the version with moment is abbreviated as NMD) family of optimization algorithms for multiclass classification. as the authors point out, even for linear classification The multiclass setting is more rich due to the linear classifiers being matrices rather than vectors.\nThe NSD/NMD families encompass a broad range of gradient-based optimizers currently being studied by the community. \n\nThe authors focuses on spectral-descent, which contains Muon and Shampoo.\nThey show that normalized steepest descent w.r.t either an entrywise matrix norm or a Schatten matrix norm (Lp norm of the spectrum of the matrix) has implicit bias toward that same norm.", "questions": "Eqn (8) looks quite different from the binary one cited on line 172. could you help elucidate/reconcile this difference, at least on an intuitive level?\n\nTheorem 1 gives the convergence in margin. How about convergence in direction? Does that also hold?\n\nSuggestions:\nin the paragraph beginning on line 158, the word \"former\" is used twice and is a bit hard as a reader to parse. consider replacing the word with the actual things the word \"latter\" were intended to reference.\n\nconsider adding a brief comment about how line 211 elementary fact is used to get Property (ii) in Lemma 3", "limitations": "Yes", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 4, "strengths_and_weaknesses": "Strength:\nThe authors nicely fill in a gap in the multiclass analysis.\nThus, there are richer set of norms/regularizers on these matrix linear classifiers, compared to the binary case.\nThe analysis is clean and slick.\n\nWeaknesses:\nTheorem 1 gives the convergence in margin. How about convergence in direction? Does that also hold?\nThere can be a better comparison with the two previous works Zhang et al. [63] and Xie and Li [59] on line 284 and line 289. How does this work's result compare to those obtained in the two cited papers? Are they better/worse/not comparable?", "was_revised": true, "final_justification": "I am happy with the authors' rebuttal and will maintain my positive score and support for the submission.", "rebuttal": "We sincerely thank you for your positive assessment of our work. Here, we address your comments/questions in sequence: \n\n***Comparison to previous works*** We have provided discussions on the convergence rates of Adam (and comparisons to Zhang et al.) in Appendix G, see Remark 3. Here, we reemphasize the key differences on the results/scope of our work and others. The work by Zhang et al. studied Adam in the binary setting [1], instead we study a broad family of NSD/NMD algorithms in the multiclass setting. As a byproduct of our NMD analysis, we get a rate for Adam in the multiclass setting that matches the rate of Zhang et al. In fact, direct use of their result would introduce an extra factor of $k$ (number of classes) into the bound, we are able to avoid this by the tight decomposition of the proxy function (below Lemma 6). Regarding Xie and Li [2], their non-linear setting and asymptotic convergence (to a KKT point of a constrained optimization problem) differ from our setting and the non-asymptotic rate.\n\n***Proxy function*** In the binary case, the proxy function is defined using gradients. As loss decreases, the proxy function converges to $0$ as gradients become small. In the multiclass setting, the logit corresponding the true class saturates as loss decreases. Hence, the proxy function for the multiclass setting also converges to $0$. \n\n***Parameter convergence*** Parameter convergence (and its rate) is more general to show and we can’t conclude formally from our proof although the simulation seems to suggest that this is the case. Note that the more subtle issue is that for certain norms of interest (e.g., max-norm (SignGD) and spectral-norm (specGD/Muon)), the max-margin problem does not necessarily admit a unique minimizer, which further complicates parameter convergence. Moreover, the parameter convergence of NGD (i.e. NSD w.r.t 2-norm) utilizes the properties of Euclidean geometry [3]. Here, the algorithms (and their associated norms) that we consider are much wider and beyond NGD. \n\n***Additional comments*** Thank you for your suggestions regarding line 158 and 211. We will revise them in the final version of the paper. \n\n[1] The Implicit Bias of Adam on Separable Data, Zhang et al\n\n[2] Implicit Bias of AdamW: $L_\\infty$ Norm Constrained Optimization, Xie and Li\n\n[3] Characterizing the implicit bias via a primal-dual analysis, Ji and Telgarsky\n\nThank you again for your time and suggestions. Please let us know if there are any further questions."}, {"review_id": "saI6Wkcada", "reviewer": "Reviewer_VTFD", "summary": "This paper proves implicit bias results for linear multi-class classification on linearly separable data with respect to various matrix norms. Specificially, it considers norms given by entry-wise p-norms and Schatten norms (p-norms of the set of singular values of the matrix) with and without momentum. In each of these cases, the parameters converge in direction to a max-margin solution with respect to the corresponding norm.", "questions": "- Isn't Assumption 4 satisfied automatically since the dataset is finite? Is the purpose of this assumption just to introduce the notation $B = \\max_i \\|h_i\\|_1$?\n- I find it surprising that the learning rate needs to decrease over time to prove convergence in direction, as the proof of implicit bias for linear models with binary data works with a constant step size. Do you have any intuition as to which part of your setting makes this necessary?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "### Strengths\n- The results are comprehensive and consider a variety of different optimization methods, unifying them under the umbrella of normalized steepest descent under different matrix norms.\n- Quantitative rates of how quickly the margin shrinks in the number of iterations of gradient descent.\n- The paper is well-written and easy to follow. It includes proofs/sketches of intermediate steps within the main text.\n- The paper describes how specific quantities tracked in the proof, such as $\\mathcal{G}(\\mathbf{W}),$ are modified from the univariate case. This intuition could be helpful for future results for multiclass classification.\n\n### Weaknesses\n- The dataset is assumed to be linearly separable and only linear models are considered. The types of functions that get learned by a neural network for linearly separable versus non-linearly separable data are qualitatively different, so this limits how much we can interpret from the results. But this is a standard assumption when studying the implicit bias of gradient descent for classification, so this is not a major weakness.\n\nSmall typos:\n- In table 1: \"Refernce\" -> \"Reference\".\n- On line 136, no comma after \"algorithms\".\n- On line 154, $\\mathbb{S}'(\\mathbf{v})$ does not match its original definition.\n- In equation (6), $o(\\|\\Delta\\|_F^3)$ -> $O(\\|\\Delta\\|_F^3)$.", "was_revised": true, "final_justification": "No changes to my score. The weakness of linearly separable data remains, but it is not a big problem considering how common of an assumption it is. The authors addressed my questions.", "rebuttal": "We sincerely thank you for your positive assessment of our work. Here, we address your comments/questions in sequence:\n\n***Linear setting*** We provide a first complete characterization of the implicit bias of NSD/NMD algorithms on multiclass data, and we believe the insights from our work can be helpful for future studies on the non-linear models.\n\n***Feature-norm upper bound*** You are right: Here, we introduce $B$ as the upper bound on the maximum $L_1$-norm of the features. For finite dataset in a finite-dimensional space, such a $B$ always exists. We choose to state this as an assumption for clarity (particularly since $B$ appears throughout the analysis). We will add a remark about the existence of $B$ as mentioned above.\n\n***Constant step-size*** For GD[1,2] and NGD[3], it is indeed true that the implicit bias can be shown with constant step-size for binary data, utilizing the underlying Euclidean geometry. However, the class of algorithms (including Schatten norms) that we consider is much wider and can have different geometries. It is challenging to unify their analyses under the same framework for multiclass data. We manage to do this by constructing a proxy function (that works for all p-norms) to bound both the first and second-order terms in the Taylor expansion of the loss. This results in a bound on the margin gap with explicit dependence on the learning rates as shown in Theorem 3 in Appendix. From there, we observe that the step size needs to satisfy Assumption 2 to ensure convergence. It remains interesting and (potentially) challenging to show the implicit bias of NSD/NMD  with constant step-size for the multiclass setting and for the range of p-norms that we consider (we will add this in the future work discussion). Note also that decreasing step-size has been used in other implicit bias works [4,5].  \n\n***Additional comments*** Thank you for pointing out these typos. We will fix them in the final version of the paper. \n\n[1] The Implicit Bias of Gradient Descent on Separable Data, Soudry et al\n\n[2] The implicit bias of gradient descent on nonseparable data, Ji and Telgarsky\n\n[3] Characterizing the implicit bias via a primal-dual analysis, Ji and Telgarsky\n\n[4] Convergence of Gradient Descent on Separable Data, Nacson et al\n\n[5] The Implicit Bias of Adam on Separable Data, Zhang et al\n\nThank you again for your time and suggestions. Please let us know if there are any further questions."}]

Author rebuttal:

Meta-review: The reviewers agreed that the paper provides a comprehensive theoretical characterization of the implicit bias of a wide family of normalized steepest descent (NSD) and momentum descent (NMD) algorithms in the setting of multiclass linear classification with cross-entropy loss, including special cases such as Spectral Descent and Muon, both of which are shown to converge to the maximum-margin classifier with respect to the spectral norm. 

The authors present a unified analysis using a carefully constructed proxy function to track both the loss and margin convergence, and they further extend their results to Adam, with experimental results to validate the theoretical claims. The NSD/NMD families encompass a broad range of gradient-based optimizers currently being studied by the community. The paper’s key contributions stand out in its combination of the finite‐time analysis, a unifying optimization framework, and empirical evaluation providing new insights into the implicit bias of spectral descent and Muon in multiclass linear settings, with excellent writing and logical flow.

There was clear support for the recommendation to accept this work, and the rebuttals contributed to confirm the support while offering commitments to implement some clarifications and improvements on the manuscript. I strongly encourage the authors to integrate the feedback received into the revised version of their paper.
Decision: Accept (spotlight)