The Implicit Bias of Gradient Descent on Separable Multiclass Data
Authors: Hrithik Ravi
Clayton Scott
Daniel Soudry
Yutong Wang
Venue: NeurIPS 2024 poster (2024)
Keywords: gradient descent
multiclass classification
hard-margin SVM
implicit bias
Primary area: learning_theory
TL;DR: We prove implicit bias of gradient descent for linearly separable multiclass problems.

Abstract: Implicit bias describes the phenomenon where optimization-based training algorithms, without explicit regularization, show a preference for simple estimators even when more complex estimators have equal objective values. Multiple works have developed the theory of implicit bias for binary classification under the assumption that the loss satisfies an *exponential tail property*. However, there is a noticeable gap in analysis for multiclass classification, with only a handful of results which themselves are restricted to the cross-entropy loss. In this work, we employ the framework of Permutation Equivariant and Relative Margin-based (PERM) losses [Wang and Scott, 2024] to introduce a multiclass extension of the exponential tail property. This class of losses includes not only cross-entropy but also other losses. Using this framework, we extend the implicit bias result of Soudry et al. [2018] to multiclass classification. Furthermore, our proof techniques closely mirror those of the binary case, thus illustrating the power of the PERM framework for bridging the binary-multiclass gap.

The Implicit Bias of Gradient Descent on Separable Multiclass Data
Hrithik Ravi'
Clayton Scott'
Daniel Soudry² Yutong Wang' 3
University of Michigan TTechnion Israel Institute of Technology Illinois Institute of Technology
(hrithikr, clayscot ) @umi edu
sandel.. com ywang562eiit.cm
Abstract
Implicit bias describes the phenomenon where optimization-based training algo- rithms, without explicit regularization, show preference for simple estimators even when more complex estimators have equal objective values. Multiple works have developed the theory of implicit bias for binary classification under the as- sumption that the loss satisfies an exponential tail property. However, there is noticeable gap in analysis for multiclass classification, with only handful of results which themselves are restricted to the cross-entrops loss. In this work, we employ the framework of Permutation Equivariant and Relative Margin based (PERM) losses [Wang and Scott, 2024] introduce multiclass extension of the exponential tail property. This class of losses includes not only cross-entropy but also other losses. Using this framework, we extend the implicit bias result of Soudry et [2018] to multiclass classification. Furthermore, our proof techniques closely mirror those of the binary case, thus illustrating the power of the PERM framework for bridging the binary-min mulay-lmlticlass gap.
bargin-based
Introduction
Overparameterized models such neural networks have shown state-of-the-arr performance in many applications, despite having the potential to overfit. Zhang et al. [2021] demonstrate that this potential indeed realizable by training real-world models to fit random noise. In recent years, there have been several research efforts that aim to understand the impressive performance of overparametrized models despite this ability overfit. Both the model architecture and the training algorithms for selecting the weights have been investigated in this regard.
Work implicit bias [Soudry et al., 2018, Ji et al., 2020, Vardi, 2022] has focused on the latter factor. Implicit bias is the hypothesis that gradient- based methods have a built-in preference for models with low-complexity. This hypothesis is perhaps best understood in the setting of (unregularized) empirical risk minimization for learning a linear model under the assumption of linearly separable data. Soudry et al. [2018] showed that in binary classification, implicit bias holds when the loss has the exponential tail property [Soudry et al., 2018, Theorem 3]. The same work also demonstrated implicit bias in the multiclass setting for the cross-entropy loss, but implicit bias for more broadly defined class of losses in the multiclass case is left open. In this work, we extend the notion of the exponential tail property to multiclass losses and prove that the property is sufficient for implicit bias to occur in the multiclass setting. Toward this end, we employ the framework of permutation cquivariant and relative margin-based (PERM) losses [Wang and Scott, 2024].
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

1.1 Contributions
Multiclass extension of the exponential tail property (Definition 2.2) is unclear how the exponential tail property for binary margin losses should be extended to the multiclass setting. By using the PERM framework, we provide a multiclass extension that generalizes the exponential tail property multiclass (Definition 2.2 in Section 2.3). We further verify that this property holds for some common losses.
Sufficiency of the exponential tail property for implicit bias (Theorem 3.4) We prove that the proposed multiclass exponential tail property is sufficient for implicit bias. More precisely, we show in Theorem 3.4 that for almost all linearly separable multiclass datasets, given a convex, (3-smooth, strictly decreasing) PERM loss satisfying the exponential tail property in Definition 2.2, gradient descent exhibits directional convergence to the hard-margin multiclass SVM.
1.2 Related Work
Soudry et al. [2018] show that gradient descent, applied to unregularized empirical risk minimization. converges to the hard-margin SVM solution at a slow logarithmic rate, provided the loss satisfies the exponential tail property (defined below). Nacson et al. [2019] improve the convergence rate using a specific step-size schedule. Ji and Telgarsky [2019] extend implicit bias to the setting of quasi-complete separation [Candès and Sur, 2020], where the two classes are linearly separated but with a margin of zero. Many works have also considered gradient-based methods beyond gradient descent. For example, Gunasekar al. [2018] examine the implicit bias effects of mirror descent [Beck and Teboulle, 2003], steepest descent [Boyd and Vandenberghe, 2004], and adaptive gradient descent [Duchi et al., 2011, Kingma and Ba, 2015]. Cotter al. [2012], Clarkson et al. [2012], Ji et al. [2021] study first order methods that are designed specifically to approach the hard-margin SVM quickly possible.
Results for the multiclass setting are more scarce, and are always specific to cross-entrope Soudry al. [2018] establish implicit bias for cross-entropy loss. Lyu and Li [2019] focus homogeneous predictors and prove convergence of GD on cross-entropy loss to a KKT point of the margin- maximization problem. Lyu and Li [2019] proves convergence of gradient flow generalized max- margin classifier for multiclass classification with cross-entropy loss using homogeneous models.' I In the special case when the model are linear classifiers, the generalized max-margin classifier reduces to the classical hard-margin SVM. Lyu et al. [2021] consider two-layer neural networks and prove convergence of GD on cross-entropy loss the max-margin solution under an additional assumption on the data, that both x and its negative counterpart -x must belong to the dataset. Wang et al. [2023] prove that in certain overparameterized regimes, gradient descent on squared loss leads to an equivalent solution to gradient descent on cross-entropy loss.
Beyond work establishing (rate of) convergence to the max-margin classifier, there is also separate line of work [Shamir, 2021, Schliserman and Koren, 2022, 2023] focusing on the generalization aspect of implicit bias. These works examine the binary classification setting, with the exception of Schliserman and Koren [2022] who consider cross-entropy.
1.3 Notations
Let K > 2 and d 2 denote the number of classes and feature space dimension, respectively. Let [K] := (1.2...., K}. Vectors are denoted by boldface lowercase letters, e.g., v E RK whose entries are denoted by vj for [K]. Likewise, matrices are denoted by boldface uppercase letters, e.g., W E [ The columns of W are denoted wi...., w.- By O,, and 1, we denote the n-dimensional vectors of all 0's and all I's respectively. The n x identity matrix is denoted by I,,
By || we denote the Euclidean norm of vector v. || is the spectral norm of matrix A. Given two vectors w, v E R$, we write w 2 v (resp. w > v) if wy 2 Uj (resp. Wi >> 2,)) for all j E [k]; similarly we write
(resp. < v) if w, I By (resp. wy 02) for all [k]. On the other
Lyu and Li [2019] could be thought of as analyzing losses beyond CE, but the optimization problem would be non-convex, so convergence might not be to a global minimum. See Appendix A for a more detailed discussion.

---

hand, if A and B are equally-sized symmetric matrices, then by A = B (resp. A = B) we mean that B (resp. B A) is positive semi-definite, i.c. A B (resp. 0)
bijection from [k] to itself is called a permutation on [b.]. Denote by Sym(k) the set of all permutations [k:. For each E Sym(k), let S denote the permutation matrix corresponding to In other words, if v I is vector, then [S, vl, Voiz)-
2 Multiclass Loss Functions
In multiclass classification, a classifier typically represented in terms of a class-score function f .fk.....k)). R2 - IR which maps input I vector f(x) of class scores. For instance, f may be a feed-forward neural network and v in this context is sometimes referred to the logits. The label set is [K], and label is predicted as argmax, (x). A K-ary multiclass loss function is a vector- valued function L = (CI...., ,,) : R - EK where (f is the loss incurred for outputting (x) when the ground truth label is y.
In binary classification, a classifier is typically represented using a function g R2 + R. The label set is { {-1, 1]. and labels predicted as x sign(g(x))- A binary margin loss function of the form x/= R + where (x)())) is the loss incurred for outputting g(x) when the ground truth label is y- Margin losses have been central to the development of the theory of binary classification,, and the lack of a multiclass counterpart to binary margin losses may have impaired the development of corresponding theory for multiclass classification. To address this issue, Wang and Scott [2024] introduce PERM losses as bridge between binary and multiclass classification.
2.1 Permutation equivariant and relative margin-based (PERM) losses
Assume the label set is [K] Define the matrix D [-Ix-1 1x-1] R(K-)) Observe that : UK U for all _
Dv (UK V1, VK U2,... ....
Definition 2.1 (PERM loss [Wang and Scott, 2024]). Ler K 2 2 be an integer, and L be K K-ary multiclass loss function. We say that C is
1. permutation equivariant if L(S.v) = -SL(l) all v E R and a E &Sym(K),
2. relative margin- based ffr each [K] there exists a function by RK-11 + R so that (v) Ey (Dv) = (UK
UK - ................................ UKK -1. for all v E RRK, We refer to the vector-valued function == (f1....,Ex [K) as the reduced form of L.
3. PERM if C is both permutation equivariant and relative margin-baseed In this case, the function == Eg referred to as the template of L.
Wang and Scott [2024] show that PERM losses are characterized by their template v.. To show this, they introduce the matrix label code, an encoding of labels as matrices. Thus, for each y E [K - 1]. let Y, y be the (K 1) X (K - 1) identity matrix, but with the y-th column replaced by all - 's. For y = K, let Y, be the identity matrix. Note that when K 2, this definition reduces to Y, = (-1),, the standard encoding of labels in the binary setting. Observe that (after permutation)
r Dv (u, U1, Uy ........ By -Ux)" T E R- where the Uy - By 0 entry is omitted. Please see Wang and Scott [2024. Lemma B.2] for a simple proof.
Theorem 2.1 (Wang and Scott [2024]). Let L B. + R be PERM loss with template si and let E K and y E [K] be arbitrary. Then vp is symmetric function. Moreover,
by (v) = vo (Y,Dvv)
Conversely, let 2b KB + IR be symmetric function. Define multiclass loss function L = (Li...., Lx) RK + K according Eqn. (1). Then L is a PERM loss with template sb.
Theorem 2.1 shows that a PERM loss is characterized by its template v. The right hand side of Eqn. (1) is referred to as the relative margin form of the loss, which extends binary margin losses to multiclass, As noted by Wang and Scott [2024], an advantage of the relative margin form is that it
Also [Wagg and Scott, 2024, Definition 2j.
3

---

C.
Figure I: An illustration of the exponential tail property for the cross entropy.multiiomiial logistic loss when K 3. Panel Plot of (b( log(1 exp(-u1) exp(-u2)), the template for the multinomial logistic loss. Note that the complement of the positive orthant in the domain R shown in gray. Panel b. and c. Plot of the upper bound (shown in black) and lower bounds (red) of aug (blue) respectively. These bounds are from Appendix C.1.3 where v= = and = Note that the lower bound is valid in the positive orthant, i.e., the red surface is below the blue one there.
decouples the labels from the predicted scores, which facilitates analysis. Our results below support this understanding.
Many losses in the literature are PERM losses, including the cross-entropy loss whose template is (u) = log(1 + > K-1 2013] whose template (u) ΣK-
exp(- (o0()-;)), the multiclass exponential loss [Mukherjee and Schapire,
-- exp(-u:). uz), and the PairLogLoss [Wang al., 2022] whose log(1 1 + exp(-u,)) See Wang and Scott [2024] for other examples.
template is = (u) = E K-1
2.2 Regularity assumptions on loss functions
Let be a PERM loss with differentiable template tb.
Oy Du,
uu) < 0, for all (1.2.... 13, RK
i.e. the gradient of the template is entrywise strictly negative, then we say that the PERM loss L strictly decreasing. this case, we write Vah < 0, where 0 is the O-vector. If the template is differentiable, then it is convex if:
(un) 2 (uz) + Vub(u2) (( (w,
-2), for all u1, E R-1
If sb is twice- difee-differrettable, this is equivalent to saying that the Hessian is positive-semidefniie:
V (u) > for all u E RK-1
Finally, the template is said to be 3-smooth if its gradient is 3-Lipschitz:
| (u,) V (u2)
|| $ Bl|u uzll. for all u1, u2 E RR--
is twice- diice-differentiable, this is equivalent to saying that the maximum eigenvalue its Hessian is bounded by 8:
2 u la S 3
for all E RK-1
where |||| is the spectral norm of matrix A.
2.3 Multiclass analogue of exponential tail property
In the binary setting, the exponential tail property defined in prior work (Soudry et al. [2018], Nacson et al. [2019], Ji et al. [2020]) is assumed to hold for the negative derivative of the loss. Similarly, in the multiclass setting we are interested bounding the negative gradient of the PERM loss template.
Definition 2.2 (Multiclass exponential tail property). multiclass PERM loss with template k- - I. has the exponential tail (ET) property there exist u4, u_ E R and positive >> 0 such

---

that for all i E [K- - 1] the following holds:
Yu s.t. min Uj > u+, we have JE[K-1]
(u) - ccxp(-ui); and
0u
vus. s.t. min Uj > u-, we have JE[K-1]
(u) 2 c
Σ
exp exp(-us) expl-ui).
Ou:
jElK -1
Remark 2.2 We show Appendix that cross-entropy (CE), multiclass exponential loss, and PairL.ogLoos all have this property.
3 Main Result
Consider a dataset {(xa, ya)) > with Xn E RRd and class labels yn E [K] == (1....,, K). The class score function for class is fx(x) = -w.x x. Define X E IRdxN to be the matrix whose nihh column is Xn. Define W Rax K to be the matrix whose kth column is wk- The learning objective
N Σ Cyn (W xn)
R(W)
(2)
n=l
From Eqn. if C PERM loss, then Ly (v) = vp (v), and the learning objective becomes
N
R(W)- = Σ 4 (Y DW x:)
(3)
1=1
Up to permuting the entries, Y, DW x; is equal to the (K- 1)-dimensional vector of relative- margins [(wg. wi) X,, (Wy. W2)
W Tx;
(W.. v. wx) Tx,] where the O-valued entry
(Wy. wy.) ""x] x; is omitted. This follows from Wang and Scott [2024, Lemma B.2].
We are now ready state our assumptions on the loss:
Assumption 3.1. The PERM loss's template vi is convex, B-smooth, strictly decreasing and non- negative." 3
Assumption 3.2. The PERM loss has exponential tail as defined in Definition 2.2.
To optimize Eqn. (2) employ gradient descent with fixed learning rate 1). Define vec(W) where vec denotes vectorization by column-stacking (See Definition B. and let the gradient descent iterate time be w (t). Then:
(1-1) w (1) VR (w()))
Define the "matrix-version of the trajectory W() E Bx such that w(1) vec (t)() Through- out this work, we frequently work with the risk as matrix-input scalar-output function R(W), and as vector-input output function R(w).
These two formulations will each be useful in different situations. For instances, adopting the matrix perspective facilitate calculation of bounds, e.g., in Section 4.2. On the other hand, the vectorized formulation easier for defining the Hessian of the risk R2)(ww. See Appendix B for detail.
We focus on linearly separable datasets:
Assumption 3.3. The dataset is linearly separable, i.e. there exists w E BB such that Yn e [N]. vk [K])( w ym X,, Z w, x, + Equivalently, there exists W gx such that Vn E [N]. Y, x, 1.
We note that in the binary the implicit bias result in [Soudry al., 2018, Theorem 31 docs not require the loss to be convex. Closing this multiclass gap open question.
Note that multiclass exponential loss v (u) does not have global smoothness constant. However, we show in Appendix C.2.2 that any learning rate < 1/ (B²R (w(0))) is sufficient for the gradient descent iterates to achieve local smoothness, where B (2K MN ||xi]].
5

---

Finally, let w be the multiclass hard-margin SVM solution for the linearly separable dataset:
argminw / w/l2 s.t. Vn, Ak o Yn W Xn X, + 1.
(4)
Now we state the main result of the paper:
Theorem 3.4. For any PERM loss satisfying Assumptions 3.1 and 3.2, for all linearly separable datasets such that Assumption 4. holds, any sufficiently small learning rate < 1l < 2 1 (X),
max
and any initialization w w(O), the iterates of gradient descent will behave as
w(t) = w log(t)) + p(t)
where the norm of the residual, [Ip(t)),, is bounded. This implies a directional convergence behavior:
(t)
w
lim
(t)
|wl
In Appendix show experimental results demonstrating implicit bias towards the hard margin SVM when using the PairLoggLsss, in line with Theorem 3.4.
Proof Sketch
In this section we will overview the proof of the result. Along the way, we prove lemmas that extend to the multiclass setting results from Soudry et al. [2018]. The extensions are facilitated by the PERM framework, in particular the relative margin from of the loss.
We adopt the notation of Soudry et al. [2018] where possible throughout this proof. Recalling the notation and definitions from the paper: let us define the standard basis e₁ E IR k such that (ex); бµz (where ò is the Kronecker-delta function), and the d-dimension identity matrix L2. Define A E RdKxd as the Kronecker product between с₁ and La. i.e. A C₁ ld. We can then relate the original -lass predictor Wa to the long column- vector as follows: A w Wg. Next define Xn, = (Ag. A&) )
Xn. Using this notation, the multiclass SVM becomes
argmin, ||ll s.t. Vn, vk + yn w Kn,k 2
(5)
For each [K]. define Sn arg min,, (w w X,, {n (Wy.. Wx) Xn 1}. i.c. the tthh class support vectors. From the KKT optimality conditions for Eqn. (5), have for some dual variables an,k >> 0 that
K
W
On, x
(6)
n
1=1
Finally, define
(t) = w (1) - -log (1) w w
(7)
where w is solution to
Vk E [K]. Vn E S₁ 17 exxp (-x,, (W... - WK)) = On.k-
(8)
In Soudry et al. [2018], the existence w is proven for the binary case for almost all datasets, and assumed in the multiclass case. Here, also state the existence of w additional assumption: Assumption 4.1. Eqn. has a solution, denoted w.
We pose the problem of proving Assumption 4.1 for almost all datasets as a conjecture in Appendix H, where also show experimentally that on large number (100 instances for each choice of d E {2, 3, 4, 5, 6} and K E {3, (3,4,5,))) of synthetically generated linearly separable datasets, Assumption 4.1 indeed holds.
Note that r(t)= = p(t) w, and w is independent of t, so bounding r(t) is equivalent to bounding p(t). Following the same steps Soudry et al. [2018, Appendix E.3]:
|| (t + 1)11 - ||r (1) = || (t + 1) r (I) 2 11) (1)) T r (1)
First Term
Second Term
The high-level approach is to bound the two terms of the above expansion for r(() and then use a telescoping argument to bound r(l) for all > Below we provide the main arguments; for complete proof of the second term's 's bound, please refer to Appendix F.

---

4.1 Bounding the First Term
Using log(1 + +2 - x for all O, we expand the first term as follows:
(1++))-r(() < n²² VR ww (f))l + [w]]2 2 21/wr VR (w (f) (1+
S 1 VR (w (0)II= + |
Obtaining the second inequality requires proving that
21/w" VR (w (t)) log (1 + 1 0, or equivalently, w VR (w (t)) <
(10)
We will spend the rest of this subsection going over the complete proof of this inequality.
First state the following lemma (derived in Appendix B.2) that gives useful expression for the gradient of the risk w.r.t. W:
Lemma 4.2. For any W E RRdXK, we have that VR(W)=
x, Vib (Y, x
DWT x:) Y D.
This expression involves weight matrix W. However the inequality we set out to prove (Eqn. (10)) in terms of w = vec W). Throughout our main result proof, these two different forms weight matrix versus vectorization of that matrix will each be useful in different situations. Thus, to shuttle back and forth between these forms, the following well-knows identity is useful:
Lemma 4.3. For equalty sized matrices M and N, we have vec(M) vec(N) tr(MMM NN.
Now we can prove our inequality of interest, i.e., Eqn. (10).
Lemma 4.4. (Multiclass generalization of Soudry el al. [2018, Lemma 1]) For any PERM loss that 3-smooth, strictly decreasing, and non-negative, (Assumption 3.1) and Assumption 3.2, and for almost all linearly separable datasets (Assumption 3.3), we have w VR(w(t)) < O.
Proof. Define matrix W such that w vec (W) Since w()) = vec( Lemma 4.3 implies
VR(w(()) = tr ( VR(W(()))
(11)
To see how the PERM framework allows for a simple generalization of binary results, we will compare our multiclass proof side-by bidebb with the binary proof discussed in Soudry al. [2018, Lemma 1]. In the binary case, we have R (w) = Eiz v (yew" xx)x = VR (w) = Σ v (y.w xx) y:x, Thus w VR (w) E w (yew x:) y: x;. In the multiclass case, the analogous quantity is tr(WTrRWWW) (R))(t)) which can be computed as
N
N
tr tr( x, V (Y,,, DW()) xx)) r D)
V (r DW
(T)()))))) x.) r DWT x,.
In the multiclass proof we used the risk gradient from Lemma 4.2 as well as the cyclic property of the trace operator. Then we dropped the trace because Ve (Ir,, (t) Yy DWW x, is scalar (since Vih (-) E R K- Y, proof, in both the binary and multiclass setting, side-by-side:
DW E k For illustrative purpose, we place the rest of the
Binary: w (R(w())).
Multiclass: tr tr(W (t)W(
Focusing just the i-th term of this sum:
Focusing on just the i-th term of this sum:
/ (t:w(t) x;) y:w Tx;
V (Ty, DW()) xx) T Y, DW
assumed be strictly decreasing, i.e. g/ (1) x)) < O. The dataset is lin-
is assumed to be strictly decreasing, i.c. V Dt)
Tx;) xx) x 0. The dataset
early separable, so y: w x; 2 1. Thus we obtain sum (from 1 to N) of negative terms.
linearly separable, so Y DW x, 2 1. Thus we obtain a sum (from negative terms.
to N) of
Thus we see how the PERM framework allows us to essentially mirror the binary proof. In Remark 4.5, we elaborate more on the necessity of the relative margin form here.
D
7

---

Lemma 4.4 directly implies the auxiliary inequality we set out to prove (see Eqn. (10)). Thus we obtain:
(I (+) r()))) I
||
(12)
Remark 4.5. Let us see what happens to our proof if we just used the general risk form in Eqn. (2)
without the PERM framework. First, need expression for the gradient of the risk: VR (W)
EN -E X, VR (WTx) Proocediig similarty to the binary case, we focus on just the i-th term of
tr W VR()).
tr (WTxVVR (WTxi) (VTx))))= =tr (VRg, (WTx) xi)
W Wxx, xi
VRy, (W Xi) W
From here is not clear how to proceed. The linear separability condition (Assumption 3.3) 3) is not useful anymore- it does not make statement about the scores in the vector WTx, X,, but rather their relative margins (produced by the multiplication Y DW TW.x. xi).
4.2 Bounding the Second Term
In the previous subsection we established bound on the first term of Eqn. (9). Here we sketch the
main arguments required to bound the second term, i.e. (r (1 + 1) r (l). For more details please refer to Appendix F. We state our final bound below lemma:
Lemma 4.6. (Generulization of Soudry et al. 12018, Lemma 20]) Define 0 to be the minimum SVM margin across all datapoints and classes, iee. A = ming minggs. XT, w > 1. Then
3C1, C2 41 Vt t1 ((( r (t) S C + C2t-2
(13)
remark is in order on the difference of the above result to Soudry et al. [2018, Lemma 20]: on a high-level, able generalize the argument of Soudry et al. [2018, Lemma 20) to account for both binary and multiclass classification, as well as general PERM ET losses beyond just CE.
We now proceed with the proof sketch. The first step is to rewrite (r (t + 1) - 1 (t)) r (t) as
V- (w (1)) w (log (L + 1) - log (1))) r (1)
DDefinition of r()) in Equation (7)
N
Tr() (t- log (1 +1+))) + tr
Σ
x V (r, DW()) (x)) y.
R(t)
- Tr(t) :. Expression for VR (w (t)) from Lemma 4.4
(14)
We defer the bound the first term w T r(()) (t- log (1+1-1)) of Equation (14) to the appendix, and instead focus on the second two terms. Using the cyclic property of the trace, the term in the above final line involving the trace can be further simplified as:
N
V DW x:) Y, DR(() x;
(15)
Note that for each E [N]. summand in Equation (15) is inner product between two (K 1)- dimensional vectors, i.e., - V DW(( x,) and Y, DR(() x; To proceed, to expand this inner product out as
Σ Σ
1-V
,,, x,]
(16)
1=
RE(KT(/BL)
Remark 4.7. Here, [1l RK-1 R is defined as the coordinate projection such that [Y, DW x1Is L. Note that I implicitly depends on i (the Ka,y, O-entry is omitted). But abuse notation for brevity. Please see Appendix D for more precise definition.
8

---

Using Equation (6) and Equation (8) we express the last two terms in Equation (14) as
N
Σ
Σ
",,"", -
1=1 k())]((b))
-
Σ E
(I-V (I,, x:)la 1all----- tt exp( w 1 ( )x(
(17)
Finally, to upper bound the above expression, we consider a single tuple (i, k) case-by-case, depending on the sign of r(t). This is the step where the upper and lower bounds in Definition 2.2 come in. Lemma D.2 in the appendix essentially applies Definition 2.2 to the relative margins to yield
( DW X x )l& I exp( -xp w())) and , (t) x, ) 2 (1 Ee((K]) exp(-xt w(t)) exp(- -x,
(18)
(19)
for all &s E [K]] \ {u.}. We use Definition 2.2's exponential tail bounds by proving that the relative margins x (t) that appear in Lemma D.2 eventually become positive. This is true due to the following lemma (see Appendix for the proof, which again mirrors the binary case):
Lemma 4.8. (Multiclass generalization of Soudry et al. [2018, Lemma I]) Consider any linearly separable dataset, and any PERM loss with template 1p that is convex, 3-smooth, strictly decreasing, and non-negative. For all (1,... K}, lel wx: (1) the grudient descent iterates at ileration for the thth class. Then Vi NJ, Vj (L.... Iiim; ( (t) w,())) x; - 0C.
This lemma lets upper (18) and lower bounds (19) to the summation in Equation (17), and reduce the problem to that of Soudry et al. [2018, Appendix E], thereby proving Lemma 4.6. See Appendix F for details.
the exponential tail bounds with any finite u To conclude, apply the
4.3 Tying It All Together
We use the logic of Soudry et al. [2018, Appendix A.2] conclude the analysis. Define
2
C Σ |r (1(1))
S r PIRR (w (1) 1|
In the latter inequality we used Eqn. (12). Thus, C is bounded because from Soudry et al. [2018, Lemma 10]. we know that Σ VR (w (t)) < 0c. Here we note that Soudry et al. [2018. Lemma 10] requires the ERM objective R (w) to be 3'-smooth for some positive 8r. It is easy to show that if the loss is 3-smooth, then R (w) is Bo max (X)-smooth. This explains the learning rate condition < 2/ (Bo max (X)) in our theorem. Also, a P power series converges for any p > 1.
Recalling the initial expansion of [|r([ + 1)ll from Eqn. (9):
||r (t + 1) = ||r (t + 1) - (1) + 2 + - (1)) (()) || (D)I..
(20)
Combining the bounds in Eqn. (12) and Lemma 4.6 into Eqn. (9), we find
4-
|| (t)] ||r (t+)l
Σ [Ir(u 2
|r [w]]] SC+2 Σ
Ciu Czu -2l
u=ti
Therefore, ||r (t)l is bounded, which proves our main theorem.
Limitations
Here we describe some of our work's limitations/possible future research directions. We note that these questions have been analyzed for the binary classification setting, but not for multiclass.

---

Non-ET' losses In our paper we only analyze multiclass implicit bias for losses with the ET property. Another possible line of future work is analyze the gradient descent dynamics for non-El losses. Nacson et al. [2019] and Ji et al. [2020] prove that in the binary setting, ET and well-hehaved super-polynomial tailed losses ensure convergence to the maximum-margin direction, while other losses may converge to different direction with poor margin. Is such a characterization possible in the multiclass setting?
Other gradient-baset methods This paper only analyzes vanilla gradient descent. Another line of work involves exploring implicit bias effects of other gradient-based methods, such as those characterized in Gunasekar et al. [2018]. Nacson et al. [2022] uses similar proof techniques to prove results for SGD, which is prevalent in practice and often generalizes better than vanilla GD ([Amir et al., 2021]).
Non-asymptotic analysis Our result proves that the gradient descent predictors asymptotically do overfit. However, in the binary classification case, Shamir [2021] goes step further and proves that for gradient-based methods, throughout the entire training process (not just asymptotically). both the empirical risk and the generalization error decrease at an essentially optimal rate (or remain optimally constant). Does the same phenomenon occur in the multiclass setting?
Conclusion
We use the permutation equivariant and relative margin-based (PERM) loss framework provide an multiclass extension of the binary ET property. On high level, while the binary ET bounds the negative derivative of the loss, our multiclass ET bounds each negative partial derivative of the PERM template vb. We demonstrate our definition's 's validity for multinomial logistic loss, multiclass exponential loss, and PairLogLoss. We develop new techniques for analyzing multiclass gradient descent, and apply these to generalize binary implicit bias results to the multiclass setting. Our main result that for almost all linearly separable multiclass datasets and a suitable ET PERM loss, the gradient descent iterates directionally converge towards the hard-margin multiclass SVM solution.
Our proof techniques in this paper demonstrate the power of the PERM framework facilitate extensions of known binary results to multiclass settings and provide a unified treatment of both binary and multiclass classification. Thus it is possible that the binary results discussed in the Limitations section can also be extended using the PERM loss framework. In the future we would like to consider more complex settings that have been analyzed primarily for the binary case, such as non-separable data (Ji and Telgarsky [2019]) and two-layer neural nets (Lyu et al. [2021]).
Acknowledgments and Disclosure of Funding
CS was supported in part by the National Science Foundation under award 2008074, and by the Department of Defense, Defense Threat Reduction Agency under award HDTRAA-2002-000 The research of DS was funded by the European Union (ERC, A-B-C-Deep. 101039436). Views and opinions expressed are however those of the author only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency (ERCEA), Neither the European Union nor the granting authority can be held responsible for them. DS also acknowledges the support of the Schmidt Career Advancement Chair AI. YW was supported part by the Eric and Wendy Schmidt AI in Science Postdoctoral Fellowship. a Schmidt Futures program.
References
Idan Amir, Tomer Koren, and Roi Livni. Sgd generalizes better than gd (and regularization doesn't t help), 2021.
Amir Beck and Mare Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Reseurch Letters, 31(3):667-755, 2003.
Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge University Press, 2004.
10

---

Emmanuel J. Candès and Pragya Sur. The phase transition for the existence of the maximum likelihood estimate in high-dimensional logistic regression. The Annals of Statistics, 48(1):27-42 2020.
Kenneth L Clarkson, Elad Hazan, and David P Woodruff. Sublinear optimization for machine learning. Journal of the ACM (JACM), 59(5):1-49, 2012.
Andrew Cotter, Shai In Proceedings of the 29th International Coference on International Conference on Machine Learning, pages 739-746, 2012.
and Nathan Srebro. The kernelized stochastic batch perceptron.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal machine learning research, 12(7), 2011.
Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nathan Srebro. Characterizing implicit bias terms of optimization geometry. In International Conference on Muchine Learning, pages 1832-1841. PMLR, 2018.
Ziwei Ji and Matus Telgarsky. The implicit bias of gradient descent on nonseparable data. In Conference on Learning Theory, pages 1772-1798. PMLR, 2019.
Ziwei Ji, Miroslav Dudik, Robert E Schapire, and Matus Telgarsky. Gradient descent follows the regularization path for general losses. In Conference Learning Theory, pages 2109-2136.
PMLR, 2020.
Ziwei Ji, Nathan Srebro, and Matus Telgarsky. Fast margin maximization via dual acceleration. In International Conference on Machine Learning, pages 4860-4869. PMLR, 2021.
CG Khatri and C Radhakrishna Rao. Solutions to some functional equations and their applications to characterization probability distributions. Sankhyā: The Indian Journal of Statistics, Series A, pages 167-180, 1968.
Diederik P. Kingma and Jimmy Ba. Adam: method for stochastic optimization. In International Conference Learning Representations, volume 6, 2015.
Shuangzhe Liu. Matrix results on the khatri-rao and tracy-singh products. Linear Algebra and its Applications, 289(1-3):267-277 1999.
Kaifeng Lyu and Jian Li. Gradient descent maximizes the margin of homogeneous neural networks. 05890, 2019.
arXiv preprint
Kaifeng Lyu, Zhiyuan Li, Runzhe Wang, and Sanjeev Arora. Gradient descent two-layer nets: Margin maximization and simplicity bias. Advances in Neural Information Processing Systems, 34:12978 12991, 2021.
Jan R Magnus and Heinz Neudecker. Matrix differential calculus with applications statistics and econometrics. John Wiley & Sons, 2019.
Indraneel Mukherjee and Robert Schapire. A theory of multiclass boosting. Journal of Machine Learning Research, 2013.
Mor Shpigel Nacson, Jason Lee, Suriya Gunasekar, Pedro Henrique Pamplona Savarese, Nathan Srebro, and Daniel Soudry. Convergence of gradient descent on separable data. In The 22nd International Conference on Artificial Intelligence and Statisties, pages 3420-3428. PMLR, 2019.
Mor Shpigel Nacson, Nathan Srebro, and Daniel Soudry. Stochastic gradient descent on separable data: Exact convergence with a fixed learning rate, 2022.
Robert R Phelps. fonveiifunctinn monotone operators and differentiabilityy, volume 1364. Springer, 2009.
Matan Schliserman and Tomer Koren. Stability vs implicit bias of gradient methods on separable data and beyond. In Conference Learning Theory, pages 33944339. PMLR, 2022.
11

---

Matan Schliserman and Tomer Koren. Tight risk bounds for gradient descent on separable data. arXiv preprint arXiv:2303.01133, 2023.
Ohad Shamir. Gradient methods never overfit on separable data. The Journal of Machine Learning Research, 22(1 (211):34773886) 2021.
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The implicit bias of gradient descent on separable data. The Journal of Machine Learning Research, 19(1): 2822-2878, 2018. See arxiv.... org/ abs 111.. 10345v7 for the most up-to-date version.
Gal Vardi. On the implicit bias in deep-learning algorithms. arXiv preprint arXiv:2208.12550 2022.
Ke Wang, Vidya Muthukumar, and Christos Thrampoulidis. Benign overfitting in multiclass classifi- cation: All roads lead interpolation, 2023.
Nan Wang, Zhen Qin, Le Yan, Honglei Zhuang, Xuanhui Wang, Michael Bendersky, and Mare
Najork. Rank4class: A ranking formulation for multiclass classification, 2022.
Yutong Wang and Clayton Scott. Unified binary and multiclass margin-bused classification. Accepted to Journal of Machine Learning Research, arXiv:231 1.17778. 2024.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3):107-115, 2021.
A Discussion of Lyu and Li [2019]
Lyu and Li [2019] allow the class score functions be linear classifiers, e.g., w Xi, but also nonlinear, e.g.. "cubed" linear classifier (w x,) By shifting the cubing operation to the loss, can view the implicit regularization result of Lyu and Li [2019] as a result for losses beyond the cross entropy. This resulting loss is rather exotic and we are not aware of it being used in the literature; it is interesting nevertheless. However, the optimization problem would become non-convex, so convergence would not necessarily be a global minimum:
min w
w/1
S.L. (w]]x.)' (w. x
2 for i [N], [K]]
Moreover, the decision region for the k-th class, i.e., the set of x E IRd such that (w x)3 > (w]xx)² x)3 for all j * k, is an intersection of sets constructed via cubic hypersurfaces.
More precisely, the k-th decision region can written as
{x E Rd: (wTx)² = jegmaxje[x]( x}}}= = n JE(K]osK
fx RERR: (w]])) (w]x)²)
Let us define H, = (x RR (w, x)3 x))]. Note that H, S Rdd is the zero set of degree polynomials with variables in x, hence, a cubic hypersurface. Now, the set {x E Rd (w x) > (w) x} is subset of the set-theoretic complement of H, in Rd. Thus, the decision regions are complicated geometric objects, compared to the classical hard-margin SVM.
B Matrix Calculus
This section of the appendix establishes matrix identities that will be useful for us to calculate the gradient/Hessian of the empirical risk objective Rww).
Vector-input scalar-output function. Suppose f TR -> IR is continuously differentiable function. Let [.,,... _z,]" E R be vector of variables for differentiation. Define the (column) vector
of partial derivatives w.r.t. x: 0x
a The gradient of f. denoted V is the function Dr JE(m)
V R" + R", where Vs(x) 0x](xx)= =
[a1 de
(x)
0f
(x))
(x)
(21)
12

---

Suppose that f is twice continuously differentiable. The Hessian of f, denoted f. is the function
A R
R"x=,
where v2 v²I(x)
8 (x) L.j(())
(22)
Matrix-input scalar-output function. Let f Ruxn + R be differentiable function. Let
X [=y]ke[m]je([]] E Rm*x be an arbitrary matrix. Define the matrix of partial derivatives w.r.t.
X:
0x
Oees (e(m)
Define the gradient of denoted f. be the function
V Rmxn
R mx
where V()(X) 0x xx
Jz.y"
8
f(x)
(23)
ie(m)
We do not define the Hessian matrix-input scalar-output function f |R + R. Instead, we will define the Hessian for its vectorization vec(f) IR + R.
Definition B.1 (Vectorization operator). Let vec denote the vectorization operator by stacking the columns of a vector, other words, if E mmx= is a matrix with columns ai..... an 1 then
vec A) == a
a2
a
Definition B.2 (Vectorization of a matrix-input function). Let f R function, define vec(f) Rm + I to be the vector-input funttiiiont such that
be a matrix-input
((A) = vec(s)(vec(A) ()))
In particular, if f is already a vector-inpul funttiiio then vec(f)
See [Magnus and Neudecker, 2019, Ch.5-$15). Below in Lemma B.4, we give a convenient formula to calculate the Hessian of (ww), the vectorization of R RWW).
The following relates the vectorization operator with the Kronecker product:
Lemma B.1. Let A RPX", B E R=xm C E mm be matrices. Then
vec(ABC) (C A)vec(B).
Proof. This [Magnus and Neudecker, 2019, Theorem 2.2].
B.1 Special case of the chain rule for linear functions
Proposition B.2. Let M E puxn be matrix. Let f R - R. be continuously differentiable function and define g IR"h - by g(x) == f(Mx). Then
Vg(x) M \/(M)), and V²g(x) = M (
Proof. See [Magnus and Neudecker, 2019, Ch.9-$13] for the first identity and [Magnus and Neudecker, 2019, Ch.10-$8 for second identity.
The next two results will be referred to the "gradient formula" and the "Hessian formula". respectively, for the function gXX = f(AX B).
Lemma B.3. Let f RPxq - R be matrix-input scalar-ouput differentiable function with Jacobian denoted Vf RRx4 4 RPxq, Ler A E TRxx,, X E TR and B E RRmxq, Define a function g I mm by (X) f(AX B). Then
V 0xf(AX = BVF(AX
Lemma B.4. Let ff IP + R be a vector-input scalar-output twice differentiable functton. Let A E Rpxn X E paxn be matrices and b E m. be (column) vector. Let V be another matrix with the same shape as X. Let x = vec(X) and v == vec(V). Define g(X) = fAX b) and let g vec(g) be the vectorization of g. Then have the following formula for computing VVg((x)v:
v VVgx))y== (AV b) T bbAV bT.
13

---

B.2 Proof of the gradient formula: Lemma 4.2
In the notation of Section 2.8.1 of the Matrix Cookbook, define matrix E R by U := A. Note that U is function of X. Then by Eqn. (137) of the Matrix Cookbook, we have for each (i.j) (m] x [n]
a 0x,
(A
0 ((U)
-Th
(
( (aa
aU 0xi;
Note that by definition, we have
8S(U) 80
VS(U). Therefore
0U à fAX B) Tr Vf(U) dx,
Next, write U = [Uee)kelp),tegg in the "mmatrix-compreeesiion" notation. Recall that Uke, i.e., the (k, 4) entry of U. is precisely computed by Alk, :]x []][:) = A|k, A {].
B|;
For each
k, E [p] [4). we have
OÜke 0(A X B axij
0xi
where "[k, =I" and "I [] " denote taking the k--th row vector and l-th column vector, respectively. Now, by Eqn. (71) of the Matrix Cookbook, we have the following expression of the matrix matrix-partial derivative as an outer product
OUke 0X
0Alk, ] T B E
B[; [A[k;
0X
From this, it follows that computing the entry-wist wise partial derivative X.j is simply obtained by indexing (i,j), i.e., 0Uix product of two scalars). Thus, ax.,
0Xi3 Bli, [ [k, jl A [k. Bi, (we emphasize that this is just
au
A i :]. Consequently,
J(AX B) = Tr (V)(U) | B B B V A[.J].
ax ij
In other words, & For our purposes, we replace f with vi A with Y D, X with W, and B with x,. Thus we obtain
(AX B) BVS(U) A.
8x
N
N
OW 1 (Y DW x,) = Σ V (Y, DW x,) _ T,D
VR(W)
i=1
as desired.
B.3 Proof of Hessian formula: Lemma B.4
Our goal is to calculate the Hessian of vec(g). First, we note that by definition
vec(g)(x) vec(y) vec( b))
Note that the last equality is simply vec()) (Ax f(AXTb), but we work in the more general case of matrix B right now. We will need to simplify vec(A. b). it more convenient during the first phase of the proof viewing b as m x matrix and denote using uppercase letter B. First, applying Lemma B. to vec( AX B), we get
Ae B) (B" @ A)vec(XTT)
However, vec(XT) * vec(X) in general. However, these two expressions are related using the commutation matrix:
Definition B.3 (Commutation matrix), Define Kmn to be the permutation matrix in mm such that K Ve((A) vec(A) T) for all matrices A E pmxn
14

---

See [Magnus and Neudecker, 2019, Ch.3-S7J. Below, we drop the subscripts in Definition B.3 and simply write K == Km Now, have
vec B)
(
X A)K vec(X) = (B @ AA
Thus
vec vec(y) = vec(S((( AA)KT)
By Proposition B.2, we have
(x)
(B T & A)K (B & AjK (B & AAK
((B & A)K ('ve(()(VeC(AA (B) & A)K
From this, we see that (recall that v = vec(V))
T (x) = ((B T & AA) V=Vec[[(VV(((XXX & A)
Now, by Lemma B.I, we have
(B T @ A)K v= (B" @ A))Kvee((V) vec(V) vec(AV B).
Now, since is just vector, we have
vec (V TUTB B) = b.
and
V'vec(f) (Ae A B)) v f'XX Putting all together, we get the desired equality.
C PERM Losses That Satisfy Assumptions 3.1 and 3.2
C.1 Cross-Entropy
By Wang and Scott [2024, Example 1], the cross-entropy loss Ly (v) log
EE exp(ve) has
exp(ex)
template v (u) = log
[1 + (I+ exp (-ux)) We calculate the partial derivatives:
Oob
du: (u)
exp u4;)
(24)
1+ Σ k=1
exp (-w))
where C. EkejK-Ijae 1|:kst exp (-ux).
(25)
1+ (C; + exp (u:)
C.1.1 Convexity
Let us analyze the entries of the Hessian of the template, i.e. 2 (u). Let [A] denote the element of A at the 1-th row and m-th column. We get for all i, E [K 1] where
82 (u)
(C: + 1) uu
V db (w),,;
Ou?
(1+ 2kml e-mx
K-1
Eob
-6-4
(2 = /2 (w))
Duzy
(1+ K- e-
From the definition of C, this implies that:
V ( (w))
Σ
V (w) 2,
+
ui
2
1 1k
JEIK 11
k=1 e
Thus, the Hessian is symmetric diagonally dominant matrix, and hence is positive semi-def,nite.
15

---

C.1.2
B-smoothness
For any diagonally dominant matrix B, let B be the matrix obtained by taking the absolute value of each element B, that is:
B k,m = [B) 1. for all I, m.
Additionally, let diag(-) R Rexx (for any p N) be the function that maps vector diagonal matrix in the obvious way.
Then have the following lemma:
Lemma C.1. Let B' := diag ( 1) where 1 is the appropriaaely-sized vector of all-I's. Then B 3 B'.
Proof. This can be proven simply by observing that B' -B is symmetric and diagonally dominant (and thus positive semi-definite).
Lemma C.I can be directly applied to analyze the Hessian (and eventually bound its maximum eigenvalue). Define H' diag 2 (u)l 1). In other words, from Eqn. (25);
(2C; + 1)e
(u)
(26)
(1+ 1+=kk1 K-1 E e-u))
H
b.
Thus, by directly applying Lemma C.I, we obtain
( 3 H'
So now since H' is defined to be a diagonal matrix, all that's is left to do is bound the diagonal entries by positive constant. First note that from the definition of C₁ it follows that 1 K-1 e-
O + 11++ Combining this with Eqn. (26), we get:
(2C; + 1)
(2C, +1)
((C; + 1) --- ((C, +1e+1)) ((C: + 1)
We can find a global minimum of the denominator of the above expression and thus arrive at an upper bound for the expression. Differentiating with respect u, and setting 0 yields a single critical point at = log (C; - 1), which produces a value of 4 (C; + 1) when substituted in the denominator (this is global minimum of the denominator expression). Thus, we get
(2C,+1)
H <
(CC +1)+1
((C++)
In the binary i.c. K = 2 case, C; = O, so our bound is exactly 1/4. However, in the multiclass case (i.e. K 2), C, can be arbitrarily large. Setting C, oo yields final upper bound of 1/2.
So our final bound can be summarized as follows:
1/4 = if 2.
2 (u) ll < H
1/2
Thus, 1/4 for binary cross-entropy (logistic loss), but B 1/2 for K-class cross-entropy.
C.1.3 Exponential Tail
We claim that for the cross-entropy Definition 2.2 holds with 4y and e a 1. We are interested in analyzing the (negative) gradient of the template. From Eqn. 24:
ar
(u)
Ou.
1+ ΣR-1
e
< c 14;
K-1
2
e
1
Σ
c
Vx 2
0,
>
km
16

---

This proves that the cross-entropy loss satisfies Definition 2.2 with uy = 0 and c 1.
C.2 Multiclass Exponential Loss [Mukherjee and Schapire, 2013]
The multiclass exponential loss C _g IR can be written as Cv(() [ exp(- u+)). Thus, the template function v IR K + R can be expressed as (u()) -iE(K-1) e- The partial derivatives of the template are then simply:
(u)) - 14 for all E [K - 1].
(27)
Ou;
C.2.1 Convexity We have
V2)( diag(exp(-a.)) :1 K --1..
(28)
The Hessian is diagonal matrix with all diagonal entries positive. Hence it is positive definite.
C.2.2 "s"smothhsess"
Recall the identity derived in Lemma B.4:
V'g(x)v = (AV (AXX(XA)) DT.
We are interested in the special case where X W is linear classifier (represented matrix) and X + vec( W) w is its vectorization as in Section 3. Moreover, gXX) represents the risk R(W), viewed matrix-input scalar-output function (defined in Appendix B), while 7(x) represents the vectorized risk R(w), viewed as a vector-input scalar-ouipul function (defined in Appendix B). We will use the formula in Lemma B.4 to calculate V V2R(w)v, where we substitute in
A T D (K
b 6 X; E ER,
S+ vb.
where (x,, y1) is training sample and 1b is the template of PERM loss. Since V is linear (i.e., distributive over additions), we have by Lemma B.4 that
(2R(w)v = vec(V) V²R(w)vec(V)
Σ r D: D V (T D D Wx D VX.
Note that ||v|| /vcc V\
| by the definitions of the Frobenius norm and vectorization.
Thus,
max
ReR(wv
VER vec(V) (oc(V)TT>> V'R(())ee(V))
(29)
VERUN =|[||
We note that we never defined the Hessian of matrix-input function, i.e., we do not work with V²R(W). Combining the two previous identities, we have proven
Corollary C.2. Let R(W) be the risk viewed as matrix- matrix-input scalar- scalar-output function defined in Equation (3). Let R(w) be the vectorization of R R(W). Then we have
V2R(w)V
VERMX:|M[|[]
max VEReXK:| V|p Dvr V
TVx,
We have
V = diag(exp(-un) -u:) ;i= ;i= l,...,K K 1).
(30)
Let vdiag(-) be the "inverse" of diag(.), i.e., vdiag(.) takes diagonal matrix and returns the vector of the diagonal elements.
17

---

The max eigenvalue of the Hessian of R(w), i.e., Equation (29), is computed below:
RV2RR
max
VERUR
[|]]=
N Σ
max
DV x.) T ( DW x.) DVTx, X; ( ve
Corollary C.2
VERd*X:[Vil
12
V DW x;) Y DV x, ( DV x
mnax
VERdx [|[||
(K 1)--)) outer product
vdiag ( DW DW x)) (T DV x, )22
max
VERdxK VVVxx://|VII---..
Voctor of diagonal elements of 7
entrywise square
Σ
R(W)1 DV x,) 00
)02 replace each entry of vdiag with risk
max VER4X [
In equality we took trace of a scalar (the expression in equality is a scalar, so taking the trace of will not change the value) and used the cyclic property. For equality 3: as per Equation (28), V is a diagonal matrix. Finally, in the last inequality, we bound each element of the diagonal vector (i.e. exp (-u:) for all i [K- ID. Dropping the R(W) and < from the front:
Σ 1 T (r y. DV DVxx))02
N
N
(T DV x;) x DV x;
Σ tr ((Y, yV x;) Tr, DV x;)
N
tr
T M/
DV xxx]V)
Note that V x, BERK
D T
D
V
x
VIl :. Sehphy--Schaazzznequllll
Note that we applied Cauchy-Schward to the inner product space K with inner product (A, B) tr(A (AT B). Now, continuing with the calculation:
N
D D 36
Y
DI
IV
x,x VIl VVll
x
|1 [
: =|ABB|> - ||||||||||
yi
i=1
$ (2K- 2)
Σ
|X;||2
Lemma C.3, ||xxx] ||r ||x; |
$ (2K -2) 2)
Σ
||x|||
for aj > 0. M 1, ΣM
oz S M
as)²
Therefore we have proven that || (w) ||2 S BRR (w), where
N
B = (22 - 2)
|
(31)
18

---

Now we will also analyze the Euclidean norm of the gradient, for reasons that will become clear later.
VR = ( (V) |F
x; V (T,, DW x.) Y
x Vi [T, y DW x,) r D
triangle inequality
|xs||2 A4 (T DW x1)112 Y D|l
||
||
V(2K 2) Σ
|21 (T DW xx)
Lemma C.3
N
S V2K- - 2)
Σ
||x||| R (w)
for all aj > 0, M21, 1. E of s E
Gradient descent a special case steepest descent with the Euclidean norm [Boyd and Vanden- berghe. 2004]. Thus, we can apply Gunasekar et al. [2018, Lemmas 11 & 12] to see that VR (w) + 0 even for multiclass exponential loss. Flaborating on this: these lemmas from Gunasekar et [2018] assume convex risk objective (which we have in the case of multiclass exponential loss). Addition- ally, they assume that I/VR (w) < BR (w) and R (w)ll2 S B²R (w). the above section we prove these exact results with B defined in Eqn. 31. Finally, Lemma C.3 below proves that
|T 2K for all & E K - 1].
In conclusion, by Gunasekar et al. [2018, Lemma 11], if our learning rate B=R(w(0])) use Soudry et al. [2018, Lemma 10].
Finally, we calculate | which was used in several places above:
Lemma C.3. For each & E [K]. we have |rDD| 22(K 1).
Proof. First, if k = K, then Yx is the identity matrix. In this case, we have Y&D D [-IK-I Ik-1] the negative (K 1)-by-(K K - 1) identity matrix concatenated with the all-ones vector. Thus,
IYD = D | = 1 1 2 -
k & K, then
T&D r Yg1k-1]
and
D r 1
Now, we recall from the definition of Y; (Definition 2.4 of Wang and Scott [2024]) that Y; is obtained by replacing the k-th column of the identity matrix by the "all-negative-ones vector. Thus
| 11 2(K 1) 1, and |M,1k- = ex =
This proves Lemma C.3, desired.
C.2.3 Exponential Tail
From Eqn. (27), the negative partial derivative of the template is clearly always positive:
( - 0.
au,
From the above, it is clear that the upper and lower bounds in Definition 2.2 hold when tn 0 and
= 1.
19

---

C.3 PairLogLoss [Wang et al., 2022]
Recall that the template of the PairlLogLoss is v (u) calculus, we see that
K-1 2k=1
log (1 + exp (-ux)). By elementary
@vp(u)
e-
Ou:
1 uu
C.3.1 Convexity We have
( diag (e* :.... -..).
The Hessian is diagonal matrix with all diagonal entries positive. Hence it is positive definite.
C.3.2 f-smoothness
Notice that the partial derivative the template exactly the same expression as the derivative of the logistic loss (i.e. binary cross-entropy). Thus, the exact same proof as logistic loss can be used to prove 3-smoothness for the PairLogLoss as well. Thus, from Appendix C.1.2, 1/4 (logistic loss simply the K 2 case for cross-entropy).
C.3.3 Exponential Tail
@v(())
S e -uk
Ouk
e-
This gives us the desired upper tail. As for the lower tail:
@mb(u) 6 uu
Ouk
1 1+0 em
e (1 - c =kk)
1
21 for all 2 0
1tx
K-1
Thus, PoirLogLoss satisfies Definition 2.2 with uy = 0 and c a 1.
D Pseudo-index
Note that Y DR (t) x, produces (K 1)-dimensional vector with entries of the form of (Iy, (f) - (t)) (t))) x.. Vk E [K]]Bt} For & [K]] let us represent the corresponding en- try of the vector as [ 9. DR(() x.JR. Note that this indexing is not the same as the 4tth entry of the vectors, since the y:a th entry (ry, (t) ry. (t)
x; is not present in the vector. Similarly, let define (T) x:)I& be the corresponding entry of Vtb.
(I V
This section makes this indexing trick rigorous.
Lemma D.1. Let W Baxk K be arbitrary and vec W) be its vectorization. Let (x;, Vi) be training sample. Then there exists a bijection that depends only on yi that maps the entries of
T,DW x; K-
the elements of the "y.-versus- relative margins, i.e., ( W [K] {ud).
The following definition makes the bijection from Lemma D.1 concrete.
Definition D.1 (Pseudo-index). In the situation of Lemma D.I, define ll : RK-1 R to be the coordinate projection such that [Y, DWx = xT, w. In other words, [.]s. selects the -ivveruu-k relative margin. When the sample index i clear from context, we drop from the subscript and simply write [[]]
20

---

The pseudo-index is useful for working with the exponential tail bounds:
Lemma D.2. In the situation of Lemmna D.I, consider V y: DW xx)) which the (K 1)-
dimensional vector of partial derivatives of the template evaluated Y, DW X;. If ib satisfies Definition 2.2, then
[-Ve(2 2: DW x, S w)
and
I- DW x 2 Σ [E(R)((( exp( -x w)) exp( xx, w)
de
for all k E [K]] {m.).
D.1 Proofs of Lemma D.1 and Lemma D.2
In both lemmas, work with fixed sample, i.e., the index does not change. As such, we simply drop the index and write & yr. x + X,, X2 < X2, and [IIx f Ili.k Below, we fix & [K- 1] throughout the proof. Let = w T [11, ux] Note that
UK
Y, W x= Yy
(32)
UK UK-
We prove Lemma D.I by considering the case = K and y + separately, First, let us consider the case when y K. Then Y, is the identity matrix and so
k-th component Equation (32) is = rk uk = (wx Wx x x= & w.
Thus, we' ve proven Lemma D.1 when K. In this case, [l simply picks out the k-th entry of the input (K d)-dimensional) vector. In other words,
|z]]
Zk. for all
[21, ..., -I E RR when K.
(33)
By definition, we note that the k-th row Y, is
Ak
By
k ys otherwise.
Y
[k
Cc,
Thus, when y # K
(UK - UUn) : k # fy
k-th component of Equation (32)
= - 1gy) : : y.
(w, wx) xx= Xx
: ke x y. : k y.
(w,, - wx) Tx AK
Thus, we've proven Lemma D.1 when & K as well. In this case, [.] picks out the k-th element of the input (K 1)-dimensiona)) vector when * y. Otherwise when y, we have that [+ picks out the y-th element. More explicitly,
|2]]
=
2k
Zy
k ===y"
+
for all = [21, .2.,,..22. 11 T K- when y 7 K.
(34)
Next, we prove Lemma D.2 by considering the case K and o K separately. First, assume that we are in the K case. From Equation (33), we get that
Oy Ouk
[ (-V m1 D WT
x;) =
(Y, TTTTx xx)
Now, we have that for u = [u1, uk-1 E I -- the upper and lower exponential tail bounds
Ov Oup
(u) S cexp(-ux), and
(u) 2 c
Σ exp (-u,)
eep(p-up uu))
Ouk
rE -1]
21

---

Letting u : Y B. W
D' X,, using Lemma D. and Equation (33), we immediately prove Lemma D.2 the case when y K. This is because we have
exp( u un) = exp( IT D
DW! x:1x) = exp(-x,,,
W
and
Σ exp (-u,)
exp (-ur)
exp (-X,, w)
rE[R-1]
(
(E(K]]aA
When K, a similar argument proves Lemma D.2 using Equation (33) for the pseudo-index [-la-
E Proof of Lemma 4.8
Re-stating the lemma:
Lemma 4.8. (Multiclass generalization of Soudry et al. [2018, Lemma 11) Consider any linearly separable dataset, and any PERM loss with template v that is convex, 3-smooth, strictly decreasing, and non-negative. For all k {1,..., K}, let (&(()) be the gradient descent iterates at iteration for the hth class. Then vi E (1,...,N), Nj E (1,..., MWs -ilm, -lim,
(1) w,())) co.
Proof. We know that lim4-poc VR (w (t)) 0 by Soudry et al. [2018, Lemma 10].
This implies that w T (VR(((() > 0. Following the same steps as in the proof of Lemma 4.4, this equivalent to saying:
(R(((()) = tr(Ver (W x.) Y. DWDTTTX x,) -
However, for linearly separable data know that Y y. DW x; ł (since W here is the hard- margin SVM solution). Thus for the above limit to be true, the limit
lim Vel (Y,, DW() = 100
must hold. By Proposition G.I, have
lim Y DW(()
Vi [N]
where oo is the "vector" whose entries are all equal to infinity. This is equivalent to
lim (Wy, (t) (t) 00 Vie [N] [K]]{s
500
(since [Y, (f) [x.,, (Wy, (t) x.).
Note that in the binary case, the above "convergence-tto-nfiiii condition is for scalar quanity, where the assumption that the loss strictly decreasing and non-negative suffices. the multiclass setting, we must ensure that all entries of the vector T y: DW(() x, converges to infinity. This is nontrivial result and is addressed by our Proposition G.
Proof of Lemma 4.6
Let us first re-state the lemma we want prove.
Lemma 4.6. (Generalization of Soudry et al. [2018, Lemma 20]) Define 0 to be the minimum SVM margin across all data points and classes, ie., ming minngs, x xT, Then:
42, VE t:
(t) - -Ott
22

---

Proof. Proceeding the same way as Soudry et al. [2018], we have
((t+1)-r())) (t)
=- (w (t)) - w log (t+ 1) - log (t)]) (t)
(-nVR (w (1))) r(1) - w ((1) log (1+1-1)
N
=wTr(t) (t -og
(1+ llg
+ tr
x, V (r,, DW(I) Σ
R(t)
-
(35)
The last equality is new step required for our multiclass generalization, in which we used Lemma 4.2 and introduced the matrices (t) and R(t), where vec (W(t)) = w(t) and vec(R(t)) rtt).
Let us focus just on the second term of this expansion.
((m
Σ
x, V (r DW()) (x)) r. R(t)
N
(1)
Σ
R(1) x; (Tr, ("() y
1ytr
(2)
yjtr
V 4 (T,, DW(() Y, DR(( x;
(36)
In step (1) we used the fact that for any square matrix M. tr(M) tr (M)). In step (2) used the cyclic property of the trace.
Similar to in the proof of Lemma 4.4, the trace's cyclic property has enabled us to convert a matrix- product into a simple dot product. Since dot products are scalars, we can now drop the trace and rewrite our expression in Eqn. (36) as dot product:
Σ
1-V0 (T (Yg, DW xx), DW)
x,]
kElK]N(u.
Using this form, we can rewrite Eqn. (35):
(r(++1)-r()) r (1) w
r(t) (t wT
log (1 (1+1-1))
N
Σ -- DW((() ,. T x,Ik
"
i RE ME(
r())
(37)
The first term w r(t) (t-1 log (t- is bounded in [Soudry al., 2018, Eqn. (139)). We will focus on the second and third terms. Recall by Equation (6) and Equation (8) that
N
N
Σ
w
and a
nexp( w -
x..b) (SESE) Risk
i=1 ky
i=1
Thus, the third term on the RHS of Equation (37) can be written as
N
-' (T(() = Σ
1 1x w
23

---

Therefore, the last two terms on the RHS of Equation (37) can be written as
Σ (W(() DR(t) "xxxxxxxx x,I1x ww Tr()
KE (37))
N
E kE(KT(BB)
1-V
(W, (R((t) x.Ix
exp( - w xx, (KES.))
Since 17 > 0 is constant, we ignore below and consider only the term inside the parenthesis:
N Σ
Σ
(Y I DR(t) T x,Il
1=1 kE[K]((u
- -t exp(- w (x
Σ
Σ
( DW((t x1)1
KE(KIN(U
t exp( w -x,,) ((Es))
(2)
Σ
Σ
(exp x1,2,)
1=1 (vA)
-t- eexl-vi x1,1 (x (KTT
Σ
exp (-w(t) T xx,,)) (1 Σ (ep(-w(t) x;,k))
1=1 kE[KTHWb
KE[K]
exp( 8 (sESE)) & r(()] (8T, (()
(38)
In (1) we used Lemma D.I, which implies that x x.Txr(tt) [r,, DR(() xilkk For (2), from the exponential tail upper/lower bound and Lemma D.2, have that
exp (t) , 2 V (IC v: DW(1) xx;]la
Z exp ((( x.,)) (1-
Σ
exp( exp(-w(I)T&<;
kE(KTN(u
We note that Eqn. (38) above is identical to the right hand side of inequality (1) in [Soudry et al., 2018, Eqn. (141)). Thus, the remainder of the analysis proceeds identically as Soudry al. [2018. Lemma 20).
G A structural result on symmetric and convex functions
Proposition G.1. Let 1h k- RR be the template of a PERM loss that satisfies our Theorem 3.4.
Let u' E R- be any sequence, where t = 1,2...., such that
lim Vvp(u')
is the zero vector. Then lim ut for every j [K - 1].
prove Proposition G.1 by first proving structural result (Theorem G.2) concerning symmetric and convex function f _ R. The proof of Proposition G.1 will be presented in Appendix G.2 as an application of the structural result, where we take f = v/, the template of PERM loss, and K 1, number of classes minus one.
24

---

Given vector X E R" and a real number C' E R, define x V C E IR" to be the vector such that
x CJ == m C)2 for all i E [n].
In other words, x "boosts" entries of x up to C' if those entries are smaller than C. Entries of x larger than C are kept as-is.
Define min(x) minj zj and argmin(x) = {i E [n]] 2, min(x)). We note the following easy-to-prove properties of the "v" operation:
min(x V C) 2 with equality if min(x) C.
2. arg V C) argmin(x)..
Theorem G.2. Suppose that f: _ IR is a symmetric, convex, and differentiable function. Then for any real number C. and any x E IR", we have
0f
(x)
of (xV C), for any i argmin(x). dz:
Before proceeding with the proof (which is in Appendix G.I), we first introduce some necessary preliminary notations and facts. Given a vector x E R", we define
val(x) == {2; ......
be the of values consistings of the entries of x. For example, if x is the all-ones vector, then val(x) = {1}. Given E val(x), we let idx(u, x) = {i E x I2 = v} be the set of indices that attains the value v.
Fact 1: For a convex and differentiable function f : RR + R, we have that
(Vx(x) ff(y), y) 0, for all x, E R"
(39)
This is simple and well-known consequence of convexity. See this stackexchange answer for short proof. When n 1, Ineq. (39) is the fact that a convex differentiable function has nondecreasing derivative. Ineq. (39) is also a consequence of [Phelps, 2009, Theorem 3.24].
Fact For symmetric and differentiable function f RR - R. we have that
of 0zc
(x)
8f 0æ,
(x), whenever Tz-
(40)
This fact follows from the chain rule and the definition of a symmetric function. To be precise, let T R" + R. be the permutation matrix that switches the and j-th coordinate. Then f(x) f f(Tx) and moreover
8f of (x) of (Tx) TV (Tx)); [ [Tx)) fx) Sæ, (x).
De.
G.1 Proof of Theorem G.2
Now, prove the above theorem, will use induction on "m" in the following lemma, which is simply a "stratification" of Theorem G.2 into cases indexed by the "parameter" m:
Lemma G.3. Suppose that f R8" + R is a convex, symmetric, and differentiable function. Let m E (0, n.). Then for any real number C E IR and any x Rn with the property that Hu val(x) < C}l = we have
01 (x) Uz.
0f Dz.
(xVV),,
for any i argmin(x)..
Note that if we have proved Lemma G.3 for each m E 10,1,....,u then Theorem G.2 holds.
The base step: we prove Lemma G.3 when m = 0 and m = 1. Strictly speaking, the proof-by- induction technique typically only involve only the base case, which would be the m case in this instance. But below, we will see that in the induction step, the m = 1 case is helpful.
Note that the 0 case holds vacuously, since C Below, focus the case, where there exists a unique v E val(x) such that S C. Let E argmin(x)). Note that we have idx(v, x) ax)min(x). Using Equation (39) (Fact 1), we have that
(Vf(vVC) (xVX) x) 0.
25

---

Definition G.1. Given any set 5 _ [m]. we let Xs E I² denote the characteristic vector on S: is the vector whose jth entry is if j E S and otherwise.
By construction, we have
(x VX x= (C Xidx(vxx) = (C U)) Xargmin(xx)
The " 01 (.)" notation for partial derivatives is a bit cumbersome. Instead, we will write "[VS());"
de. from now on. By Equation (40) (Fact 2), we have
[V(()], = [Vf()) for all j.j' E idx(v, x)
and likewise
V C)), = (V/ for all j, E idx(u,
Thus, by Equation (40), we have
(Vf(xV Vx(), - x) = |argmminx))] (C- (Vf(()))
Now, since > v and Jargmin(x)) > 0, we must have that [V/(x C)): [V[(x)] 2 0, as desired. This proves the base step.
Induction step: Suppose Lemma G.3 holds for every integer m where < m n. we must show that Lemma G.3 also holds for m + 1. To this end, let x E R" and C E IR be such that He (x) v C} m+1. Let U1. Um+1 E RR be all the elements of {u val(x) v < C} enumerated in increasing order, i.e., 81 < ..... Um+1-
Note by construction, we have that {u val(xx)
Um+1) (V1, (.1..... Um } and we immediately get that Hv E val(x) v < (m++1] | = m. By the m-th case of Lemma G.3 (i.e., the induction hypothesis) using u1+1 C, get
V fx V Um+1)]; [ for any i argmin(x).
(41)
Below fix some E argmin(x)) (x) arbitrarily. Let x' := x V Mm+11 We note that by construction, all the entries of x' that are less than C are set to equal to 0m-1- other words,
{u val(x')
C) (Um+1}
singleton set. Thus, by the m case of Lemma G.3 applied x', we get that
[x C) 2 [x('')> for any i' argmin(x').
Since argmin(x') 2 ar), we have that i E argmin(x') well (recall that i was chosen earlier from argmin (x) arbitrarily). Thus the above inequality implies in particular that
[V/(x' V C)], /V (x'))
[V](x V um41)]ss
Combined with Equation (41), get
V V C)); 2 [x[())]
Finally, we note that x' V = (x 11) VC= = x V C. Thus, the above implies
[V((VV)) [x())] for any i E argmin(x)
since the choice of i E argmin(x) was arbitrary.
G.2 Application to our setting
The condition lim;~ro u², by definition means that for every real number M E R. there exists
T' such that for all T' we have ut M. Thus, suppose that there exists j [K 1] such
that lim ut # oo, then there exists a real number M E such that for all T = 1,2, ... there exists some t 2 T such that w/ < M. Passing to a subsequence, we assume that u² < M (and so
min(u') < M) for all I. = 1, ..... Note that lim (vn(n)) continues to hold.
Below, whenever say "for all/every t", we mean "for all/every t 1.2...."
26

---

Onto the proof. First recall the lower bound portion of the exponential tail property:
For all u E R such that min(u) u-; have
K-1
-[Ve(u)); 2 c
Σ exp(-uy) uz)) uz). for all i E [K 1].
(42)
Let == m 2|u-1, M, - log( ( } and := u² V C for all t. This choice of C' (and v²)
has the following consequences:
1. The fact that C 2 - log( (())T) implies (1 Σ exp(-1;)
2. If RK is such that min(v) 2 C, then we have by Equation (42) that
1
[vb(v)] 2 ccepp(-n)
(43)
2
3. min(u') < C. This is true since min(u') - M.
4. Choose E argmin(u') for every Then vf. min C for every t. This is simply consequence of the fact that argmin(u") S argmiinvv)..
5. We have lim ( ss.
This follows from the assumption that
lim (v((u))= =.
By Theorem G.2, we have for every i that
Vel(')), 2 (Vo(v")).
By plugging in v² for in Equation (43) above and the fact that of, C, have
Vv((')) -feexp(-vo) vv.) -eeeep(--CC
Since - -epcexpp-CCC C) is constant that doesn't 't depend on t, is impossible for lim (vb(v'), to hold. This proves Proposition G.I.
H On the existence of w
The goal of this section is to explain the challenge and the current gap in the proof of the existence of w that satisfies the condition in Equation (8) for almost all linearly separable datasets. To this end, recall Equation (4), the hard-margin SVM formulated
constrained optimization:
w argmin w 2
//|2 s.t. Vn, vk + Un.
w Un. Xn,
W X, 1.
(44)
Moreover, recall that S₁ the set of support vectors for each A: E [K]. is defined by
S = {n (wy. w.) Xn = 1}.
The Lagrangian of the objective in Equation (44) is
L(w, x) = Σ w, 2 + ΣV Σ
an,r (Wy, wr) Xn
(45)
m=1r/um
where Os,r are the dual variables. Let di,5 denote the Kronecker delta, i.e., 8i,5 if = j and d.g = 0 otherwise. Taking the gradient of L(w, a)) with respect to wP. we get
N
Wi: +
Σ
ana (6r.gm 6r.1) x,, = W +
8k Σan - ank Xn.
=== r
==
rzyn
27

---

So the KKT conditions satisfied by stationary point w (hence globally optimal for Equation (44))
are
vk E [K] We
On
Σ ric
an,
Xn
(46)
an 2 0 and (Wy. - -wx) Xn
1k. E [K] Vn one of the following holds
(47)
On = 0 and (Wy.. -wk Xn >
where Eqn. (47) (the second line) above is the complementary slackness condition.
The goal of this section is to prove the following result regarding the existence w that satisfies the condition in Equation (8), which we restate below:
vk E [K] Yn E S& exx (-x,, ( - ww)) = O',,k-
(48)
Conjecture H.1. For almost all linearly separable multiclass datasets, Assumption 4.1 holds, ie.. Eqn. (48) has solution w.
Below, we use the word "generically" to mean "for linearly separable datasets outside set of Lebesgue measure zero". In order for (48) to have solution in w generically, two conditions need to hold (generically).
Condition 1. On,k for all k and such that n E S == {n: (wy. wx) x, = 1}.
Condition 1 is already nontrivial and gap in proving the Conjecture, will see below. For the sake of explaining Condition 2 below, let us assume Condition holds. Then we can rewrite (48) as
Wk: E [K], Vn E Se x (Wa.. w.) log Olz,k
(49)
Define the vector mn.k obtained by taking the difference between the k-th and ya-th elementary basis vector in I i.c.
my.k ex Eyn, RRK
Then we can further rewrite (49)
VA: E [K], Vn E Sy (m,,, @ xx)TTw = log 17
(50)
Oln,k
It is more convenient to pool all the class-specific support vectors Sş into single set: S (n, k): (w,.. - -w& Xn =]] For readability, we linearly order the tuples in S, i.c. we as- sign to each (n, k) unique index E (S)).. In other words, we define n(1), n(() and k(1), k([S)) such that
S = ((a(1),((1)), (n(2), k(2)), (n(SS),, A(())))
To reduce notational clutter in the subscript, define x, Xa(i) and m; - mm())A(() Finally, define
M with denoting the Khatri-Ras product. which is, by definition, the matrix obtained by taking the Kronecker product of corresponding columns [Khatri and Rao, 1968]. Note that the Khatri-Rao product is only defined for two matrices that have the same number of columns. See Liu [1999] for reference. We now state
R K x
A X X x E ds] and e (M X) E ddK (S)
Condition 2. rank G) [S] generically.
Note that given Condition Eqn. (50) has solution in w, while Condition is necessary for the logarithm in (50) to be valid in the first place.
The challenge in proving Condition in the multiclass case that the column vectors of may have repeats, i.c., it is possible for nii)) n(i') when * i'. It is easy generate synthetic linearly
28

---

iterate
GD iterate @
1000
100000
<5
-10
margin
-15
Figure 2: Small simulation with N = 10, d and K 3. The loss used is the "PairLogLoss". Top row. Decision regions of classifiers along the gradient path w(t) at = 100, 1000, and 100000, respectively from left to right. Bottom Note that most the progress is made between iterations 100 and 1000.
Decision regions of the hard-margin multiclass SVM.
separable multiclass datasets satisfying this condition. Nonetheless, we observe that even in such case, the matrix G has rank [S), i... Condition 2 holds. We verify this experimentally in the Python notebook check httpeeeeiiocoooooottuuuieiiaaeae
ipynb available at
ht httpa////ggghaaaacccc////ooaatap
figures
In the binary case, linear classifiers are parametrized simply as single vector, rather than the more cumbersome one- mne-veetor-per-cllat parametrization. Under the one-vector parametrization, the M matrix hecomes a S- matrix consistings of only +s's, and G reduces to X. Moreover X has no repeats. Thus, Condition holds trivially. both the multiclass and binary settings, given Condition 2, the proof for Condition can proceed exactly as in Lemma 12 from Soudry et al. [2018] where their Xs is replaced by G.
I Additional Experiments
We provide additional experimental support for our main theoretical result for the PairLogLoss [Wang al., 2022]. Code for recreating the figures can found at
The code can be hwtp:///ooottooggggg/////eeeeeee wtt.errrppp2ammmllaaaeeeee multiclass IR- figures
https:/ / //ggggttuuub com/
Google Colab with CPU runtime in under one hour.
29

---

F
10
F
W
1 F
A
10-1
10 10
102
103
10*
105
Steps
Figure 3: Large simulations with N 100, d d= 10 and K 3. The loss used the Log The curves 10 independent runs with randomly sampled data and random initialization for gradient descent over 100000 iterations. Note that the convergence in direction of the gradient descent iterates the hard-margin SVM slows down in log-log space.
NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Our abstract clearly introduces the problem considered (implicit bias), identifies gap in research (few multiclass results, which themselves are only for cross-entropy), and states our contributions (new ET property and implicit bias theorem for new losses). For the sake of brevity we do not state additional assumptions on the loss apart from ET (which we state later in the main text, i.e. smoothness, strictly decreasing, non-negative), because the ET property a novel contribution and deserves appear in the abstract.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: We have separate section where talk about work's limitations. We highlight 2 natural questions one can ask: non-ET loss characterization, and non-asymptotic analysis (answering whether overfitting occurs after some finite number of (S)GD timesteps).
Guidelines:
30

---

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 how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't It acknowledged the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: All assumptions are stated clearly in bold at the beginning of section 3, and also re-iterated multiple times throughout the paper, The assumption the learning rate being sufficiently small is mentioned in the theorem statement. Partial proofs are provided in the main text because they highlight salient features of our techniques (namely, simple generalization of binary proof techniques to multiclass). Complete proofs are provided in the appendix.
Guidelines:
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.
statement of any theorems. The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
All assumptions should be clearly stated or referenced
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: We use a simple synthetic setup which can reproduced easily with Google Colab.
31

---

Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed 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, or other means that are appropriate to the research performed.
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- open-source 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 to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: In Appendices H and we include a link to our GitHub repo which contains the complete code reproduce the experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https:/ //ne:///nppp.e.e cc/
public/ /tcicc//ggss//eeeeeeeeee CoooeSuoeeiiieeee www.mmmsssoooooooooooooooooooooo
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 NeurIPS code and data submission guidelines (ht tps: //nips cttccc//puaa wwwpp//pppccccccc.cc...ccc...ltt /uu//uiieeee des Cood/ Submis as canPolicy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
32

---

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 is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
All details can be found in the GitHub repository.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented the core paper to a level 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, 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: Our experiments are used to illustrate the main theoretical result, which is of mathematical nature. All experiments support the convergence behavior that we analyzed.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at 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 run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to 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.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: Yes, the experiments can be run with a Google Colab CPU runtime as men- tioned in the Appendix.
Guidelines:
33

---

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 estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics htt /ttprrieusppp//pe/ cc wttpppblic/Ehiicciiieeeeeeeeeee
Answer: [Yes]
Justification: [NA]
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- cration 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: [NA]
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA 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 unintended uses (c.g., disinformation, generating fake profiles, surveillance), fairness considerations 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 to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
34

---

Justification: [NA]
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not existing assets. The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms of use the package should be provided. For popular datasets, paper swi thoode com. dataset has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Question:
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not release assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
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)?
35

---

Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does 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 Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does 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 NeurlPS 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.
36


Reviews:
[{"review_id": "0G0NRDnvc5", "reviewer": "Reviewer_gcyJ", "summary": "This paper uses the framework of permutation equivariant and relative margin-based losses of (Wang and Scott, '24) to extend the implicit bias result of (Soudry et al.,'18) to multinomial classification. Namely, the authors prove that when the loss satisfies a multiclass generalisation of the exponential tail property and the dataset is linearly separable, gradient descent with a sufficiently small learning rate converges to the multiclass max-margin solution.", "questions": "-Definition of $\\tilde{x}$ in Eq.~(9)?\n-There must be some typo in the first equation of section 41;\n-The definition of coordinate projection after Eq. (19) in the proof of Lemma 4.5 is unclear;\n-The explanation preceding Eq. (20) in the same proof could mention that Eq. (11) is also used.", "limitations": "The authors have addressed some of the paper's limitations, but not the limited significance with respect to previously existing results on the implicit bias of multiclassification.", "rating": 4, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 1, "strengths": "The paper's goal is clearly stated and framed within the relevant literature. The definitions and statements of the main results are easy to follow and, except for a few inaccuracies, so is the proof sketch.", "weaknesses": "From a conceptual point of view, the results of the present paper do not provide additional insight into the implicit bias of multiclassification with respect to previous works limited to the cross-entropy loss.\n\nAlso at the technical level, as the authors themselves state, using the PERM framework allows for a simple generalisation of the results of (Soudry et al., '18) to the multiclass case, to the point that a large fraction of the proof is identical or almost identical.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "$\\newcommand{\\bfx}{\\mathbf{x}}$\n$\\newcommand{\\bfW}{\\mathbf{W}}$\n$\\newcommand{\\bfw}{\\mathbf{w}}$\n$\\newcommand{\\bfD}{\\mathbf{D}}$\n$\\newcommand{\\mlc}{\\boldsymbol{\\Upsilon}}$\n$\\newcommand\\pseudoindex[1]{[#1 ]}$\n\n> From a conceptual point of view, the results of the present paper do not provide additional insight into the implicit bias of multiclassification with respect to previous works limited to the cross-entropy loss.\n\nOur novel insight is characterizing the conditions on a loss that suffice to endow it with the implicit bias towards the max-margin solution. This is significant because, while cross-entropy is the most popular loss used, there are many new losses being proposed that offer competitive performance (PairLogLoss being an example). Our work fills in a gap in the loss design literature regarding how to design losses that have the same implicit regularization property as the cross entropy. Also, our technique can be of wider interest due to the unified treatment of binary and multiclass classification, which your next feedback covers which we now address.\n\n> Also at the technical level, as the authors themselves state, using the PERM framework allows for a simple generalisation of the results of (Soudry et al., '18) to the multiclass case, to the point that a large fraction of the proof is identical or almost identical.\n\nOur work offers a *unified* treatment of both binary and multiclass, and shows that the proof strategy from the binary case carries over. This is a strength of our analysis.  Although some of our proofs simply mirrors the pre-established binary case, a large portion of our analysis is novel and nontrivial. For example, our new definition of exponential tail is itself a novel contribution. This definition captures the specific property that is needed for the implicit bias to hold for a broad class of losses *beyond just cross-entropy*. Additionally, verifying that existing multiclass losses satisfy our exponential tail definition (as well as the beta-smoothness condition) is nontrivial- the proofs are in Appendix C. Finally, we develop some novel tools and techniques to lay the groundwork for future binary-to-multiclass generalizations in the PERM framework. These techniques are captured in Lemmas 4.1 and 4.2, as well as Appendices B and D. This puts us at about 12 pages of novel analysis not present in (Soudry et al., '18).\n\n> Definition of $\\tilde{\\mathbf{x}}$ in Eq.~(9)?\n\n$\\tilde{\\mathbf{x}}$ is defined on line 187.\n\n> The definition of coordinate projection after Eq. (19) in the proof of Lemma 4.5 is unclear;\n\nThis is an understandable confusion since we use a lot of different notation. Additionally, thank you for helping us notice a typo. On line 254, instead of \"the $\\tilde{\\bfx}_{i,i}$ 0-entry is omitted\", \n\nit should say \"the $\\tilde{\\bfx}_{i,y_i}$ 0-entry is omitted\". This entry is 0 because looking at the definition on line 187, the $\\mathbf{A}$ matrices will cancel out.\n\nWhat we mean by our coordinate projection notation is essentially the following:\n\n$\\pseudoindex{\\mlc_{y_{i}} \\bfD \\bfW^{\\top} \\bfx_{i}}_{k}$ \n\nis equal to\n\n$\\tilde{\\bfx}_{i,k}^{\\top} \\bfw$\n\nif $k < y_i$. else if $k \\geq y_i$, we have\n\n$\n\\tilde{\\bfx}_{i,k+1}^{\\top} \\bfw\n$\n\nPlease also see the beginning of Appendix D for an intuitive explanation. Finally, we have added a remark in the paper to clarify this.\n\n> The explanation preceding Eq. (20) in the same proof could mention that Eq. (11) is also used.\n\nThank you for your suggestion; we will make this fix.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "gRWTlSbn6l", "reviewer": "Reviewer_AJJ5", "summary": "This paper investigates the implicit bias of gradient descent on separable multiclass data using a broad class of losses termed Permutation Equivariant and Relative Margin-based (PERM) losses, which include cross-entropy loss, multiclass exponential loss, and PairLogLoss. The main contribution is the extension of the concept of the exponential tail property, commonly used in the analysis of implicit bias in binary classification, to multiclass classification with PERM losses. The proof techniques (and main results) are analogous to those used in the binary case, suggesting that PERM losses can bridge the theoretical gap between binary and multiclass classification.", "questions": "Maybe a minor typo: in Assumption 3.3, line 171, $k$ should not be there.", "limitations": "Yes.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The paper is very well-written and well-organized, making it easy to follow.\n2. While the implicit bias of gradient descent has been widely studied for binary classification, its extension to multiclass classification is relatively sparse and mainly restricted to cross-entropy loss. This paper addresses a broad class of PERM losses, extending the concept of the exponential tail through the \"template\" of the loss. The result is both interesting and significant.\n3. The theoretical results are convincing. While the proof largely follows Soudry et al. [2018], the analysis is nontrivial. Additionally, the proof idea is laid out in a clear manner.", "weaknesses": "1. The main weakness is the lack of numerical results to verify the theoretical claims. While this is understandable given that the convergence is exponentially slow, some simulations could be presented to illustrate the gap between theory and practice (where networks are not trained to achieve zero loss).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and catching the typo. We appreciate your time and the supportive feedback. We've added numerical simulations demonstration implicit regularization towards the hard margin SVM when using the PairLogLoss, in line with our theory's prediction. It is attached to the \"global rebuttal\" above.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "TZaKPiLpKB", "reviewer": "Reviewer_47NU", "summary": "This paper leverages the PERM (Permutation Equivariant and Relative Margin-based losses) framework proposed in [Wang and Scott, 2024], and extends the implicit bias result of binary classification to multiclass classification.\n\nSpecifically, the authors extend the exponential tail property to multiclass setting, and proved that for almost all linearly separable datasets with suitable PERM loss, with sufficiently small step size, the gradient descent iterates directionally converge towards the hard-margin multiclass SVM solution.", "questions": "- As the authors have mentioned in Section 5, it has been proved in [Shamir, 2021] that for gradient-based methods in binary classification, throughout entire training process, both empirical risk and generalization error decrease at an optimal rate, I am curious if similar phenomenon has been observed in numerical experiments for multiclass setting?\n\n- It seems to me that the condition learning rate $\\eta<\\frac{2}{\\beta\\sigma_{\\textrm{max}}^2(X)}$ could be strong for dataset $X$ with a large spectral norm. I’m curious if it is more of a necessity for the proof, or the numerical experiments do require this condition to have directional convergence?", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper is strongly motivated, well structured and pleasant to read. It studies the problem of implicit bias for multiclass classification with losses not limited to cross-entropy, bridging the binary-multiclass gap.\n\nThe PERM framework provides an elegant tool for analyzing multiclass classification problems, and in my opinion, this paper is technically solid. I have not gone through the proofs of lemmas in the appendix, but the analysis in the main paper looks correct to me.", "weaknesses": "As the authors have discussed in the Limitations section, it would also be interesting to consider beyond the asymptomatic setting and end tail property.\n\nSome typos:\n- It has been discussed in 4.3 that $\\mathcal{R}$ is $\\beta\\sigma_{\\textrm{max}}^2(X)$-smooth, and the learning rate should be $\\eta<\\frac{2}{\\beta\\sigma_{\\textrm{max}}^2(X)}$, but the upper bound is stated as $2\\beta^{-1}\\sigma_{\\textrm{max}}^2(X)$ in the statement of Theorem 3.4. \n- In page 3 line 85, the meaning of $[\\textbf{v}]\\sigma(j)$ doesn’t seem clear to me, is it $[\\textbf{v}]_{\\sigma(j)}$?\n- Line 116: from direct calculation ${{\\Upsilon}_y}\\textbf{Dv}$ is not  $(v_y-v_1,v_y-v_2,\\cdots,v_y-v_K)^T$ but its permutation. Although this difference should have no influence in the proofs under PERM loss assumptions, it could still be a bit misleading. \n- Line 200: in the RHS of the equation, $\\left\\|\\hat{\\textbf{w}}\\right\\|$ should be $\\|\\hat{\\textbf{w}}\\|^2t^{-2}$\n- Line 219: $\\hat{\\textrm{w}}^T\\mathcal{R}(\\textbf{w})$ should be $\\hat{\\textrm{w}}^T\\nabla\\mathcal{R}(\\textbf{w})$", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the careful reading and catching these typos! We will update our paper to reflect these changes. We also clarify line 116.\n\n> In page 3 line 85, the meaning of $[\\mathbf{v}]\\sigma(j)$ doesn't seem clear to me, is it $[\\mathbf{v}]_{\\sigma(j)}$?\n\nYes. This was a typo, we will remove $[\\mathbf{v}]\\sigma(j)$ from the paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DIu0NRHnNu", "reviewer": "Reviewer_RrKo", "summary": "The authors study the problem of multiclass SVM in the realizable (i.e., separable) case.\nThey show that under several assumptions on the loss function, the gradient descent converges in direction toward the (unique) solution of the hard-margin problem.\nFor that, they used the notion of Permutation Equivariant and Relative Margin-based losses (introduced elsewhere) in order to extend the notion of exponential tail (from binary SVM) to multiclass SVM.\nThey also show that three loss functions, including cross-entropy, satisfy the assumptions of the theorem.", "questions": "- Equation after line 200, first line: the equality seems wrong to me because I would expect a factor $\\log(1+t^{-1})$ multiplying $\\lVert\\hat{w}\\rVert$, but it is not there.\nFurthermore, I do not understand either how we get the inequality simply by showing that the third term is negative, since there is an extra $t^{-2}$ factor multiplying $\\lVert\\hat{w}\\rVert$.\n- Line 262: Why is $u_{\\pm}=0$, while in Def. 2.2, it can be anything?\n- Lines 609 to 611: I understand from the argument that *at least one* component of $u$ must converge to $\\infty$, because indeed $\\nabla\\phi(u)\\prec0$ for all finite $u$, but why do *all* the components of $u$ have to converge to $\\infty$?", "limitations": "The authors acknowledge correctly the limitations of their work.\nHowever, a small discussion somewhere in the paper of how restrictive the assumptions on the loss function are would be welcome.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "This is a strong technical paper (even though I would like to ask several questions to the authors to be convinced of the soundness of the proof; see \"Questions\" section).", "weaknesses": "The main weakness of the paper in my opinion is the difficulty to understand several technical steps of the proof due to the lack of details/explanations.\nThis is a general comment but I have several specific questions in the \"Questions\" section about steps that I did not understand and made me question the overall soundness of the proof.\nI would be happy to have answers from the authors about these questions.\n\nOther comments:\n- Line 193: Lemma 12 in the other paper does not directly give the result, one needs to browse to Eq 18 to complete the argument.\n- Eq. 20: $\\eta$ missing somewhere.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> Line 262: Why is $u_{\\pm} = 0$, while in Def. 2.2, it can be anything?\n\nWe could have worded this better, thank you for the question! All the relative margins (which comprise $\\mathbf{u}$, the vector argument to the template) go to infinity so that lets us pick any finite value for $u_{\\pm}$. The value 0 in particular works for us because the 3 losses we analyze (cross-entropy, exponential loss, PairLogLoss) satisfy exponential tail with this parameter setting, as proven in Appendix C. We will re-word this in the paper to avoid any confusion in readers' minds.\n\n> Lines 609 to 611: I understand from the argument that...\n\nThank you for the careful reading! We note that one can easily verify this property for the 3 losses analyzed in our paper. Nevertheless, we are able to fill this gap for *general* losses using a new structural result on convex, symmetric, differentiable functions that we proved. The caveat is that now, our results require an additional assumption that the loss template be convex. It is easy to see that all 3 losses analyzed are convex by computing the second derivatives and verifying they are non-negative. We note that this condition is not required in the binary case in Soudry et al 2018. This is an interesting difference between the binary and multiclass case which we hope to address in future work.\n$\\newcommand{\\bbR}{\\mathbb{R}}$\n$\\newcommand{\\bfx}{\\mathbf{x}}$\n$\\newcommand{\\bfu}{\\mathbf{u}}$\n$\\newcommand{\\bfv}{\\mathbf{v}}$\n\nOur new structural result is stated below. First we need an additional piece of notation: Given a vector $\\bfx \\in \\bbR^{n}$ and a real number $C \\in \\bbR$, define $\\bfx \\vee C \\in \\bbR^{n}$ to be the vector such that  the $i$-th component of $\\bfx \\vee C$ is equal to $\\max(x_{i}, C)$, for all $i \\in [n]$.\n\n> **Theorem**.  Suppose that $f : \\bbR^{n} \\to \\bbR$ is a symmetric, convex, and differentiable function. Then  for any real number $C \\in \\bbR$ and any $\\bfx \\in \\bbR^{n}$, we have $ \\tfrac{\\partial f}{\\partial x_{i}} ( \\bfx ) \\le \\tfrac{\\partial f}{\\partial x_{i}} (\\bfx \\vee C) $ for any $i \\in \\mathrm{argmin}(\\bfx)$.\n\nUsing this theorem, we show that if not all components of $\\bfu$ go to infinity, then we can derive a contradiction to $\\nabla \\psi(u) \\rightarrow \\mathbf{0}$, using the exponential tail property. We sketch the details of this.\n\n1. Suppose that $\\bfu^t$ is a sequence such that $\\lim_t \\nabla \\psi(\\bfu^t) \\to 0$, but there exists a component $j$ such that $u^t_j$ does not go to infinity.\n2. There must be a finite number $M$ such that $u^t_j \\le M$ for infinitely many $t$. We pass to the subsequence so that $u^t_j \\le M$ always.\n3. Define $C := \\max (\\quad 2|u_{-}|, \\quad M,\\quad -\\log (\\tfrac{1}{2(K-1)}) \\quad )$.\n4. Define $\\bfv^t := \\bfu^t \\vee C$. Then $\\min(\\bfv^t) \\geq C$. Using the lower exponential tail bound combined with $C \\geq -\\log (\\tfrac{1}{2(K-1)})$, this implies that $-\\tfrac{\\partial \\psi(\\bfv^t)}{\\partial v_i} \\geq \\tfrac{1}{2}c\\exp(-av_i)$.\n5. Applying the theorem for all $i \\in \\mathrm{argmin}(\\bfu^t)$, we get $\\tfrac{\\partial \\psi(\\bfu^t)}{\\partial u_i} \\leq \\tfrac{\\partial \\psi(\\bfv^t)}{\\partial v_i} \\leq -\\tfrac{1}{2}c\\exp(-av_i) < 0$. This contradicts what we proved on line 608, i.e. $\\lim_t \\nabla \\psi(\\bfu^t) \\to 0$.\n\nWe are happy to follow up with more details of this sketch if you are interested.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
Thank you all for the fantastic reviews! Please find attached figures to numerical simulations. 

One typo that was brought to our attention was in the first equation on line 200. Here is the correct inequality, derived:

$\| \mathbf{r}(t+1) - \mathbf{r}(t)\|^2 = \|\mathbf{w}(t+1) - \mathbf{w}(t) + \hat{\mathbf{w}}\log(t+1) - \hat{\mathbf{w}}\log(t) + \tilde{\mathbf{w}} - \tilde{\mathbf{w}}\|^2$

$=\|-\eta\nabla\mathcal{R}(\mathbf{w}(t)) +  \hat{\mathbf{w}}\log(1+t^{-1}) \|^2$

$= \eta^2\|\nabla\mathcal{R}(\mathbf{w}(t))\|^2 + \|\hat{\mathbf{w}}\|^2\log(1+t^{-1})^{2} - 2\eta\hat{\mathbf{w}}^{\top}\nabla\mathcal{R}(\mathbf{w}(t))\log(1+t^{-1})$

$\leq \eta^2\|\nabla\mathcal{R}(\mathbf{w}(t))\|^2 + \|\hat{\mathbf{w}}\|^2 t^{-2} - 2\eta\hat{\mathbf{w}}^{\top}\nabla\mathcal{R}(\mathbf{w}(t))\log(1+t^{-1})$

In the last step we used $\log(1+x) \leq x$ for all $x > 0$.

Meta-review: This paper provides a variety of refinements of max margin analyses to the multiclass case, using the proof of Soudry et al.  Reviewers are uniformly positive and I recommend acceptance.
Decision: Accept (poster)