Multiclass Loss Geometry Matters for Generalization of Gradient Descent in Separable Classification
Authors: Matan Schliserman
Tomer Koren
Venue: NeurIPS 2025 poster ()
Keywords: Gradient Descent
Separable Data
Generalization bounds
Primary area: theory

Abstract: We study the generalization performance of unregularized gradient methods for separable linear classification. While previous work mostly deal with the binary case, we focus on the multiclass setting with $k$ classes
and establish novel population risk bounds for Gradient Descent for loss functions that decay to zero.
In this setting, we show risk bounds that
reveal that
convergence rates are crucially influenced by the geometry of the loss template, as formalized by Wang and Scott (2024), rather than of the loss function itself.
Particularly, we establish risk upper bounds that holds for any decay rate of the loss whose template is smooth with respect to the $p$-norm.
In the case of exponentially decaying losses, our results indicates a contrast between the $p=\infty$ case, where the risk exhibits a logarithmic dependence on $k$, and $p=2$ where the risk scales linearly with $k$.
To establish this separation formally, we also prove a lower bound in the latter scenario, demonstrating that the polynomial dependence on $k$ is unavoidable.
Central to our analysis is a novel bound on the Rademacher complexity of low-noise vector-valued linear predictors with a loss template smooth w.r.t. general $p$-norms.

Multiclass Loss Geometry Matters for Generalization of Gradient Descent in Separable Classification
Matan Schliserman
Tomer Koren
Blavatnik School of Computer Science and AI Tel Aviv University
Blavatnik School of Computer Science and Al Tel Aviv University and Google Research tkoren@tauex. tau. ac.
cchlisermannmall ac.il
Abstract
We study the generalization performance of unregularized gradient methods for sep- arable linear classification. While previous work mostly deal with the binary case, we focus on the multiclass setting with & classes establish novel population risk bounds for Gradient Descent for loss functions that decay to zero. In this setting, we show risk bounds that reveal that convergence rates are crucially influenced by the geometry of the loss template, as formalized by Wang and Scott [24), rather than of the loss function itself. Particularly, we establish risk upper bounds that holds for any decay rate of the loss whose template is smooth with respect the p-norm. In the case of exponentially decaying losses, our results indicates a contrast between the p on k, and p = where the risk scales linearly with k. To establish this separation formally, also prove lower bound in the latter scenario, demonstrating that the polynomial dependence on & is unavoidable. Central to our analysis is a novel bound the Rademacher complexity of low-noise vector-valued linear predictors with a loss template smooth w.r.t. general p-norms.
case, where the risk exhibits logarithmic dependence
Introduction
The generalization properties of gradient-based learning methods, particularly overparameterized regimes, is a central topic of study in contemporary machine learning. Á key question is how unregularized gradient methods achieve good generalization despite their potential to overfit. Early work by Soudry et al. [21] demonstrated that gradient descent (GD) applied to linearly separable data with the logistic loss asymptotically converges to the max-marga solution. This result suggests that gradient descent, when properly tuned, can avoid overfitting without explicit regularization. Extensions of this result to other optimization algorithms and loss functions have further deepened our understanding of this phenomenon in various scenarios
5].
particularly interesting regime for these investigations is multi- class classification. In this setting, Soudry et al. (21] achieved convergence max-margin with the cross-entropy loss, and Lyu and Li 8. Lyu et al. [9] extended the results to homogeneous models and two-layer networks. More recently, Ravi et al. [15] generalized the implicit bias analysis broader class of exponentially tailed loss functions using the PERM framework (24), thereby bridging the binary and multi-class settings in this context.
Beyond these asymptotic results, recent work has focused on the generalization performance of bradient-based methods in finite-time regimes. In the binary classification setting, several recent works examined gradient-based methods applied to smooth loss functions that decay to zero at infinity (20] 17 19 23 These results show that strong generalization without explicit regularization, even in finite time, can be achieved by gradient methods also beyond the regime of exponentially
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

tailed loss functions. In terms of bounds, their results reveal that generalization performance is fully characterized by the decay rate of the loss function.
Despite these advancements in understanding gradient methods in separable classification, finite-time generalization in the multi-class setting remains rather poorly understood even for exponentially decaying loss functions, and particularly with regard to the dependence of risk bounds on the number of classes. In particular, several fundamental questions remains open: does unregularized GD generalize well also after finite number of iterations? Does the algorithm's 's generalization ability extend beyond the exponential decay setting? How do the properties of a loss function influence the achievable test loss bounds? Additionally, does the sole dependence of generalization performance on the decay rate of the loss function, as observed in the binary case, also extend multi-class classification? In fact, the first two questions were stated as open problems by Ravi et al. [[5]
In this work, address these questions by studying the finite-time generalization properties of gradient descent when applied with a multi-class loss function & R x k - R. Our findings reveal key distinctions from the binary classification case. Whereas in the binary regime risk bounds depend solely on the decay rate of the loss function, we show that in the multi-class setting risk bounds crucially depend on the geometry of the multi-class loss function, as determined by the norm with respect to which it is smooth. This differs from the results of Ravi et al. [15], that suggest that all exponentially tailed loss functions behave asymptotically similarly.
The class of functions that we consider is similar to the class considered by Wang and Scott 24 who showed that in the setting of classification with k classes, losses characterized by their template: a function & RK - R that has a simpler form than the original loss function f. For multi-class classification losses with template that is B-smooth with respect to the Lp norm and decays to zero at infinity, we establish the following upper bounds on the risk of the output of gradient descent (when the step size is tuned optimally).
BL2iPp p- (E/k))
y2 minin.. m)
where p :R IR represents the decay rate of the loss function, denotes the number of classes, is the number of gradient steps, is the sample size, and is the separation margin. These results suggest that gradient descent can generalize well for a reasonable number of classes (k < T, n). As with the bounds in the binary case established in [19], the risk bounds depend on the decay rate of the function, through the expression p (e/k) (though here the decay function p=1 is evaluated at E e/k, compared to in the binary case).
Next, noticing the fact that our upper bounds behave differently for templates that are smooth with respect to the I. -orm for sufficiently large p, and the case of p 2, giving better generalization bounds in the former case, we establish this separation formally, by showing tight lower bounds for any decay rate in the 12 regime. We also provide examples for this separation in popular loss classes.
In terms of techniques, our analysis requires some new technical tools. First, we derive a Rademacher complexity bound for multi-class losses whose templates are smooth with respect to the Lp norm (2 S P I co), in the low-noise regime. Next, we show that the choice of step-size of gradient descent also depends on the geometry of the loss, achieving improved optimization performance as p becomes larger. Putting these technical pieces together, we obtain the affremmentioned risk upper bounds. We remark that this approach applies to essentially any gradient method that produces a model with low norm and low optimization error, making it applicable beyond gradient descent.
1.1 Summary of Contributions
To summarize, our contributions are as follows:
Our first main result (Theorem M establishes an upper bound for unregularized gradient descent in separable multiclass classification for any loss function that decays to zero. Our bound suggests that the dependence on the number of classes improves as p increases.
Our second main result (Theorem 3 shows a tight lower bound for losses with templates that are smooth with respect to L2 and decays to zero. Our lower bound reveals strict separation between templates that are smooth with respect to the l. --ponorm for sufficienlly large p. and the case of p = 2, where polynomial dependence on the number of classes is unavoidable.
2

---

As direct applications of our general bounds, we derive upper and lower bounds for templates with several decay rates (see Section 5). For example, in the exponential rate case, our result reveals that if the template is smooth with respect to the L.o norm, the risk bounds align with those of the binary case and depend only logarithmically on k; in contrast, for p = 2 the rate has an unavoidable linear dependence on the number of classes.
Finally, as an additional technical contribution that underlies our analysis, we show a new upper bound on the Rademacher complexity for multi-class classification losses in the low-noise regime, where the loss template is smooth with respect to any Lp norm with p 2 2, refining and extending the results in 7 16] In particular, our assumptions apply the template rather than the individual loss functions, which represents new perspective (see Section 1.2 for further discussion).
Put together, our results reveal that the geometry of the loss template plays a crucial role in the generalization behavior of gradient descent. Prior work on separable classification showed that for exponentially tailed losses, gradient descent implicitly converges toward max-margin solutions [5], and that in the particular case of binary classification with more general tails, generalization depends primarily on the decay rate of the loss [9]. In the more general multiclass setting, our results indicate that this behavior strongly influenced by the smoothness properties of the loss template with respect to geometries. In particular, losses with similar decay rates can induce very different generalization bounds, depending on their underlying geometry. This can serve to explain why -mooth losses such as the cross-entropy scale more favorably with the number of classes as compared to f2-smooth losses.
1.2 Additional related work
Convergence rates for unregularized GD in separable classification. The risk of Gradient Descent separable classification has been extensively studied. Firstly,, the asymptotic analysis in the fundamental work of Soudry et al. (21) showed an upper bound of 1 1/log(T)) for the classification error of gradient descent. Then, using a more refined analysis Shamir [20] established tight bounds on for gradient descent applied to binary cross-entropy loss. Later, Schliserman and Koren [77. Telgarsky
23]. Schliserman and Koren [99 extended this analysis. Schliserman and Koren [7 showed generalization bounds for basee methods with constant step sizes in using an additional self-boundedness assumption. Telgarsky [23] established high troh-prbbbbblityy risk bound for 7 S n for batch Mirror Descent with non-constant step size for linear models. Schliserman and Koren [19] showed tight risk bounds for the binary case were given for any smooth loss decaying to zero. While all of the aforementioned work (except Schliserman and Koren (17 that discussed the particular case of the cross entropy loss), studied binary classification, in this work we address the multi-class setting and establish risk bounds applicable to any classification loss with smooth template that decays to zero, without any additional assumptions.
Lower bounds for unregularized GD in separable classification. There are several lower bounds in the context of binary classification. Firstly, Ji and Telgarsky 4 presented a lower bound of ((log(n)/ (oog((n//ogdde log(()) for the distance between the output of GD and max margin solution with the same norm. In other work, Shamir (20) proved a lower bound of (((//²T) for the empirical risk of GD when applied to logistic loss. More recently, Schliserman and Koren [9] showed a tight lower bounds for the risk of GD, that are valid for any decay rate of the loss function. In this work, we establish the first lower bounds for unregularized GD when applied in the multi-class setting. Our lower bound is valid for losses with template with any decay rate that is smooth with respect to the L2 norm.
Vector-valued predictors (VVPs). Extensive research has been dedicated to understanding the sample complexity of vector-valued predictors. For the non-smooth regime with bounded domain, Maurer [1]] established upper bounds scaling as O(k) for Lipschitz predictors with bounded Frobe- nius norm. In addition, Lei et al. [6] and Zhang and Zhang (26) derived logarithmic bounds in & for foo fo-LLiscchiz VVPs with arbitrary initialization. In another work, Magen and Shamir [10] studied the role of initialization and established bounds independent of when the algorithm is initialized at the origin. However, these bounds grow exponentially with the error e, the Lipschitz constant I., and the radius of the initialization ball. For lower bounds, Magen and Shamir [TO] established generalization lower bound of 2(log k) for convex predictors, while Schliserma and Koren [18]
3

---

improved this to match the upper bounds of Maurer [[]] under the Lz-Lipschitz condition for the nonsmooth case. Unlike these previous studies, our work focuses on the smooth and unregularized setting, where the effective norm of the iterates and the Lipschitz constant may be depend on k, optionally introducing additional multiplicative factors in the bounds.
There is large body of work that achieves fast rates for VVPs. For example, Reeve and Kaban [16] showed Rademacher complexity bounds that are logarithmic in for smooth losses with respect to the Loe norm with bounded domain, while Li et al. (7] provided rates linear in for L2-smooth losses. Another related work is the work of Wu al. [25] that established fast rates generalization bounds for SGD in strongly convex settings. Importantly, in this study, we show that multi-class classification, suffices to assume the smoothness of the template of the loss function, rather than the actual loss function, and demonstrate that this property characterizes the generalization of gradient descent in this setting. addition, we show Rademacher complexity bounds for the general Lp norm, recovering the bounds of Li et al. and Reeve and Kaban [16] as special cases.
Fast rates for VVPs.
2 Problem Setup
We consider the following multi-class linear classification setting. Let D denote distribution over pairs (x. where E Rd is d-dimensional feature vector, and [k] is the class index corresponding to x. We assume that the data is scaled such that ||ж||| s with probability with respect to D. Our focus is the separable linear classification setting with margin. Specifically, denoting the Frobenius norm of a matrix W E R axd by [W]l and its j row by W we assume the following separability assumption:
Assumption 1 (Separability). There exists a matrix W. E Rexd with rows w w such that ||W.Ile and, with probability over (x. y) D,
Vj [k] (v) (W.' w
Given a multi-clase loss function & R [k] - R*, the goal is find model W Redd that minimizes the (population) risk, defined as the expected loss over the distribution D:
L(W)= (ew)),
For this, we use a dataset S = (1) (xn. yn) of training examples drawn i.idd. from D, and optimize the empirical risk:
" i(W)=
Σ
(Wxx, yi).
n i=1
For convenience, we define the function by : R - R as Ey = ((.y). In addition, for every vector v e Rd we denote its j'th entry by v[j].
2.1 Loss Functions and Templates
Here we detail the class of loss functions that we consider. First, following template of multi-classification loss function.
24 we define the
Definition 1 (Multi-class loss template). Given multi-class loss function & R x [k] Rt say that ē -- - a template of E, if for every class y E [k], holds that
((f.y) (D),))
where Dy e IR (K- (k-11)xx 1)xk
is the negative identity matrix when the yth row is omitted and the yth column replaced by the vector that all of its entries are 1.
Note that for every vector it holds that, D, (vly) - - -1))....... vlyl - v[k]), where the zero entry, v[y] - v(y], omitted.
The templates considered in this work are f-smooth with respect to Lp norm for 2 2, as described in the following definition.
Definition 2 (smoothness w.r.t. Lp). A differentiable function f: Rd - R is s-soooth function w.r.t Lp norm if f(v) vf( s Bllv allp p for all v e Rd, where 1 q =

---

The primary goal of this paper is to quantify how the risk bounds depend on properties of the template especially the rate at which decays zero as imput approaches infinity and the particular norm Lp which it is smooth with respect to it. To formalize this, we use the following definition, following [19]
Definition (Tail Function). A function p [0, oo) - R is called a tail function if p:
(i is nonnegative, 1 1-Lipschitz, and fssmoooth convex;
is strictly decreasing and - p(u) O: (iii) satisfies p(0) 2 1 and I (0) 2
In addition, we can define the following class of templates,
Definition (p-Tailed Class). For given tail function p. the class C..PP is defined as of all nonnegative and convex functions i R R such that:
(a) i is B-smooth with respect to the Lp norm.
(b) lim, E(ru)= = O for all (IR+))=1.
(c) {(u) z Σ p(u[i)) for all u E (B
Now, the actual class of functions we consider is the following class, which contains multi class classification losses.
Definition (p-Tailed MCC Class). The class c.P.P is defined as all loss functions : R x [k] R for which there exists i e Gp.P such that is template of t.
The vast majority of loss functions used multi-class classification are in Cf for some tail function
p. p and B. In Section 5 we detail several applications of our bounds for popular multi-class functions.
2.2 Unregularized Gradient Descent
In this work, we focus on standard Gradient Descent with a fixed step size 7 0, applied to the empirical risk L. The algorithm is initialized at W1 = and performs updates at each step = I...., follows:
W1+1 W, -7vV.(.,).
The algorithm outputs the final model Wy.
While our primary focus is GD, the majority of our results can also be adapted other gradient methods.
3 Risk Bounds for GD on Multiclass Losses
In this section we establish our upper bound for the risk of GD, when the loss function & is taken from the class c.P.r. The bound appears in the following theorem,
Theorem 1. Let p be tail function and let e be any loss function from the class C..P. Fix T, and ó > O. Then, with probability at least - ô (over the random sample of size n), the output of GD applied on L with step size 17 1/6k2/r initialized at W1 has for any such that Ty²T (E))) for for p
(2, 00), holds that
Bk2 pー (E/K))
BK2 (
L(w7) = Ō
22T
y2n
In addition, p=
L(Wr) =0(0) (Bp-(e/k)
(e/k)2
Bp (E/k)2
22T
y2n
In the rest of the section detail the main techniques which we use for proving Theorem
5

---

3.1 Bounds for the Rademacher Complexity of VVPs
Firstly, we explain our main technique, which is based on local Rademacher complexity of vector- valued function classes. We first recall the definition of the Rademacher complexity (e.g., M.
Definition (Rademacher complexity), Let Z be a measurable space and D distribution over Z Let F be class of real-valued functions mapping from Z F. Given a training set S (ZI..... 2n) of n exmples that sampled i.i.d. from Z. The empirical Rudemucher complexity of F defined by
1 sup fEF
Rs (F) E
{z((zi) 1=1
where Ei.....6. G2 are i..dd Rademacher random variables. addition, the worst-case Rademacher complexity is defined as R, (F) sups=z" Ry (T).
In particular, in our work, given loss function & E C...P. we are interested in bounding the worst case Rademacher complexity of the class
LP (x. ((Wx,y) W E B L(W) s sr).
where B (W Rexd| || F B). We establish the following upper bound for the worst case Rademacher complexity of L.
Lemma Let p be tail function and let e cf.P. Given B, r 2 O, let L. be as defined above.
Moreover, let M be such that every f E Lb is bounded by M. Then, it holds that,
Rn (cB = =
@VBrkk
B+1
Vn
For the proof of Lemmal a multi class classification training set S = [(x1, y1) ..).... yn), define a new training set with nk examples denoted Š follows and is defined as follows
1
we use the approach of Lei et al. (6). Reeve and Kaban [16], that given
5 (6b (x)) j By s.t (1), E S).
where (x) Rdxk is the matrix which its jth column is x and the rest of the columns are zero. Then, is possible to relate the covering number of L to the covering number of the following class of linear predictors when applied on S,
HB= = (V + (W.V) W kxd Ve B
The full proof of Lemma appears in Appendix A Notably, in contrast to those works, which uses the properties of the loss, we show that in the multi-class classification setting, is sufficient to use the properties of the template t.
The next step of the proof is Lemma bound the difference between the empirical risk and the population risk of a specific model in multi-class losses. Such a result appears in the following theorem,
Theorem Let p be tail function and let E Cf.PP P. Given B.r 2 O, Let L be as defined above. Moreover, Let M be such that every E LBr is bounded by M. Then, for any ö > O we have, with probability at least 5 over random sample of size n, for any W Bkxd
L(W) δ [(W)+ Bk (B 1)2
M
n
3.2 Implications of Template Geometry on Optimization
Next, we discuss how the geometry of the template influences the optimization error of GD. The key insight is that while the template is 0(1) -smoooo,, this smoothness does not necessarily extend to the loss function & with respect to the model of the template, formalized in the following lemma (see proof in Appendix A):
fact, the latter is highly dependent on the geometry

---

Lemma 2. Ler ||x|22 & y, [k] and & E Op for 2 2. Let ((x,) B - B be ((x,y) (,(x)) E(D,W>) Wx) Then, for every W, W E Rkxd
[x (W) (xx,y> s 3Bk ||W WW
Since the optimal step size for GD general B-smooth functions (with respect to W) is approximately 1/8, Lemma 2 shows that the optimal step size increases with Substituting this into the convergence bound for the optimization error of GD leads to improved convergence rates as p grows. as formalized in the following lemma (see proof in Appendix A).
Lemma 3. Let p be tail function and let l C..P. Fix any and point W BRkxd such that [(W*) Σ E. Then, the output of Titterations GD, applied on L with step size nj = 1/6k2ip B initialized at W1 = 0 hus,
6k 6k²B|
I(Wr)
+ +E
T
3.3 Proof of Theorem 1
We are now ready to prove Theorem [ The proof proceeds by first showing that the iterates of GD remain within bounded region around the origin; this is established in Lemma [4] Appendix (
Next, we combine the bound on the generalization gap bound from with the low-noise guarantee
implied by Lemma 3 to complete the argument for Theorem The full proof is detailed below.
Proof of Theorem First, let (2, oo). First, for such that " s (o (f)(()) we get by Lemma 14 and Lemma 12 (see Appendix A).
4p 4p Be = || x 21l 2 s 2 29) + 2n s
Y
y
For the same e, by Lemmas
and 12
||Wal*
p- (9)
Te = ((Wr)
+ S 3
n/
221l
Now, we denote B, (W E R S B.). Moreover, by Lemma 14 and Lemmas 12 to 14 (see Appendix we know that, with probability
M max |[(Wx)] WeB.
max E(D,wx) Wx) WEB.
$ 22,,(W2)) + +Bkr max I|W 1e WeB.
s (W' + 22Bk 3
||W] + 2Bk I|
max WEB,
I 2 + 8Bk 2/4 P (E)
+ 2Bk 2 (E)
y2
y2
$ 2e + 2 (T)
p (T)2
S 5 (F)
ny²
2ny²
ny²
Now, by Theorem 2 for any 5 > 0 we have, with probability at least - ô over random sample of size n, for any e, there exists a constant C such that depends poly-logarithmically on k, n, M B, 1 and
L(W) s 2 + CBKk
(B +
(B++))
+ C
Me
$ 2[(W) + 4ČBk 1 B²
Me
c C n
n
G4ČBkTp-1o s +
sčp-1($)
n2n
n
7

---

For Wr by the choice of we get,
L(WT) & (92
6AČ (C)
y"n
24Bk P (2) P
+
2²
y
For = oo, since any B- smooth function w.r. Loe also B smooth with respect to the Lę norm, we get that, since x1/x c < for any x E R.
24Bk (F)2
84ČBkáp-
L(WT) S
y²T
y2n
216Bp- (4)
1OCČBp-'($)
y²T
y-n
Tightness in the Euclidean case
In this section, we show that the non-trivial dependence on k given in Theorem ! for = 2 is unavoidable. We prove this by establishing the following lower bound:
Theorem Let p 2 and y S 5.2 For any tail function p. sample size 2 35 and any T, there exist distribution D and loss function & B... such that for T -steps GD over sample S = ((xi, vi) sampled i..dd from D, initialized at W with stepsize dl 1/6ßk, holds that
E[L(WT)] = Bk(p 256e )2
Bk(p -1 16e )2
y
T
for any
1 such that 2 ((p=)((()))
256
For the proof of Theorem 3
prove two lemmas. first show the following lemma, which provides tight lower bound for the case in which T 2 n,
Lemma 4. Let y S and e be such that o (t) u8² SES I. For any tail function sample 236- size n 2 35 and any and T, there exist a distribution D with margin a loss function f E B.P for p = 2 such that for GD over sample {21)/1 sampled i...d. from D, initialized W1 with step size 1 S 6Bk it holds that
[kp 10pp-1(2)) 2556 )2
E[L(WT)] =Q
y2n
Second, in the following lemma give tight lower bound for the case where T
Lemma 5. Let y s & and e 0 be such that (2)
Yn S To. For any tail function p. T, there exist distribution D with margin y. loss function & c..P such that for GD over sample S (2))
sampled i..dd from D, initialized at W1 with step size S opk. it holds that
p (01()
E[L(w7)] =
ny
Below, we provide sketch of the proof for Lemmas and The full proofs and the derivation of Theorem 3 can be found in Appendix
To construct hard instance for the Euclidean case and prove Lemmas and 5 our main observation R. the template {
that for a univariate loss function each entry of its input and sums the results, satisfies & &R.P for This established in the following lemma (see proof in Appendix B
R. which applies ø to

---

Lemma 6. Let E R - R such that there exists a function & E R - R and ((w) Σ 6(w(jl). Then, if & is nonnegative, convex, B-smooth and monotonically decreasing loss function such that ((u) & p(u) for all u 2 0 and some function tail function it holds that E Cp. for p 2.
Next, to construct the hard instance, we design loss functions that represent the sum of k hard binary classification instances. Combining this with a construction similar to that Schliserman and Koren [9] for the latter case, derive multi-class classification lower bound for loss functions with smooth templates with respect to L2.
5 Examples
In this section, we apply our general generalization bounds for gradient methods in the setting of multi-class classification with several popular choices of loss function, demonstrating how the geometry of the loss function affect the generalization properties of Gradient Descent.
5.1 Exponentially-taile losses
First, we show a risk bound for Gradient Descent, when the decay rate of loss the loss is exponential, iee when & c..P for p(x) = =e= We can apply Theorem | with and get the following.
Corollary 4. Let l cp.P for p(x) = Then, the output of Gradient Descent on L. with step size and W1 satisfies
17 6R
kス k
[[(W))) =
y2T
y
particular loss function in the class of losses with exponentially decaying template the cross entropy loss, i.e., for every y [k], (f) log + Σ jay exp(}ly) (xp({x)-{(j))) whose template is smooth with respect to the L. norm (see Lemma 22 in Appendix C Next, we can derive an upper bound for GD which is logarithmic in the number of classes. For this, apply Theorem D with + and obtain the following result,
Corollary 5. If is the cross entropy loss function, the output of Gradient Descent on L with step 1 and W1 = satisfies
size 11 T2
[[((W))]
2T
y
This bound matches the upper bound of Schliserman and Koren 17 for Gradient Descent the cross entropy loss, and, up to logarithmic factors matches the bounds given in Schliserman and Koren [99 for the case of setting of binary classification with smooth losses with exponential tail. In contrast, using Theorem with log' (kT) we get:
"T"
Corollary 6. There exists function & B.P for = 2 and p(x) = e such that the output of Gradient Descent L with step size 1 and W1 0 holds,
k k
E [[L(W>)] = Ω
TT
y
Combining Corollaries]land[] we get separation between exponentially tailed losses with templates that are smooth w.r.t the Lor- senoomm-uchh as the cross-entropy loss, where risk matches the binary case up to logarithmic factors, and the L2-norm case, the upper bounds exhibit unavoidable linear dependence on the number classes. This differ but not at odds with the results of [5), which suggest that exponentially tailed losses exhibit similar asymptotic behavior.

---

5.2 Polynomially-tailed losses
Now show application of our generalization bound for Gradient Descent, when the decay rate of loss the loss is polynomial, i.e., when É ε c for p(x) x- for some O. For giving an upper bound for polynomially tailed losses, we can apply Theorem I with for this class of functions & Laiz (gy²T)
and get the following upper bound,
Corollary Let & C for p(x) = = Then, the output of Gradient Descent on L with step size 17 = and W1 = holds,
k k (1
[[(W>)] Ō
(y²T) Iia
2a y n
Discussion and Limitations
In this work, we provide the first finite-time population risk bounds for gradient descent linearly separable multiclass classification. Our results show that the geometry of the loss, captured through the lp -moooootssssss of its template, plays a central role in both convergence and generalization. In contrast to prior views that emphasize the decay rate of the loss or the implicit bias of gradient methods, our analysis reveals that smoothness geometry determines how generalization of gradient descent depends on the number of classes across different multiclass regimes.
Our analysis assumes linear predictors and linearly separable data, which, while standard in theoretical studies, limits direct applicability to nonlinear or noisy settings. As result, our results should be seen theoretical foundation that helps explain generalization in simpler settings, rather than direct description of deep learning in practice. Despite these assumptions, our insights may suggest broader implications. The dependence of the bounds on Ep -moothheess offers an explanation for the empirical success of cross-entropy and other -moothh losses in large-scale or extreme classification, where the number of classes high.
Future work. Having established the first finite-time risk bounds for gradient descent in the multi- class separable setting, several open directions remain. A natural next step is extend our analysis to nonlinear predictors and nonseparable data, and to examine empirically whether the geometric separation between smoothness norms also arises in more complex regimes. An especially relevant example is classifier-heat fine-tuning in deep networks, where the data are typically nonseparable and multi-labeled, in contrast to the single-label setting considered in this work. Another promising direction is to further study the implicit bias of gradient methods for loss functions with general, potentially non-exponential tail decay rates (e.g.. polynomial tails), and investigate whether im- plies nontrivial multiclass risk bounds, similar to those established in this paper. This question is particularly interesting given that, in the binary case, the implicit-bias characterization of the gradient descent solutions leads to strictly suboptimal bounds as compared to the state-of-the-art more elaborate discussion therein).
[19]
(see
Acknowledgments
This project has received funding from the European Research Council (ERC) under the European Union's 's Horizon 2020 research and innovation program (grant agreement No. 101078075). Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council. Neither the European Union nor the granting authority can be held responsible for them. This work received additional support from the Israel Science Foundation (ISF, grant numbers 2549/19 and 3174/23), grant from the Tel Aviv University Center for AI and Data Science (TAD) and from the Len Blavatnik and the Blavatnik Family foundation.
10

---

References
[1] L. Bartlett and S. Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov):463 442-222,, 2002.
[2] O. Bousquet. Concentration inequalities and empirical processes theory applied the analysis of learning algorithms. Journal of Machine Learning Research, 01 2002.
[3] Z. Ji and M. Telgarsky. Risk and parameter convergence of logistic regression. arXiv preprint 18X3v01803.07:0 2018.
[4] Z. Ji and M. Telgarsky. A refined primal-dual analysis of the implicit bias. Journal of Environ- mental Sciences (China) English Ed, 2019.
[5] Z. Ji, M. Dudík, R. E. Schapire, and M. Telgarsky, Gradient descent follows the regularization path for general losses. In J. Abernethy and S. Agarwal, editors, Proceedings of Thirty Third Conference on Learning Theory, volume 125 Proceedings of Machine Learning Research, pages 2109-2136. PMLR, 09-12 Jul 2020.
[6] Y. Lei, U. Dogan, D.-X. Zhou, and M. Kloft. Data-dependent generalization bounds for multi-class classification. IEEE Transactions on Information Theory, 65(5):2995-3021, 2019.
[7] J. Li, Y. Liu, R. Yin, H. Zhang, L. Ding, and W. Wang. Multi-class learning: From theory to algorithm. Advances in Neural Information Processing Systems, 31, 2018.
[8] K. Lyu and J. Li. Gradient descent maximizes the margin of homogeneous neural networks. arXiv preprint arXiv: 05890, 2019.
[9] K. Lyu, Z. Li, R. Wang, and Arora. Gradient descent on two-layer nets: Margin maximization and simplicity bias. Advances in Neural Information Processing Systems, 14::1297--1299 2021.
[10] R. Magen and O. Shamir. Initaliizationdeeendenn sample complexity of linear predictors and neural networks. Advances in Neural Information Processing Systems, 36, 2024.
[11] A. Maurer. vector-contraction inequality for rademacher complexities. In Algorithmic Learning Theory: 27th International Conference, ALT 2016, Bari, Italy, October 19-21, 2016, Proceedings 27, pages 3-17. Springer, 2016.
[12] M. S. Nacson, Lee, S. Gunasekar, H. P. Savarese, N. Srebro, and D. Soudry. Convergence of gradient descent separable data. In The 22nd International Conference on Artificial Intellignce and Statistics, pages 1420-3428. PMLR, 2019.
[13] M. S. Nacson, N. Srebro, and D. Soudry. Stochastic gradient descent on separable data: Exact convergence with fixed learning rate. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 3051-3059. PMLR, 2019.
[14] A. Rakhlin, K. Sridharan, and A. Tewari. Sequential complexities and uniform martingale laws of large numbers. Probability Theory and Related Fields, 161(1):111-53,, 2015. doi: 111100//00040001--5555200
URL URLhttps. hattps:://ooto org/ 10. 1000/000040000 013-0045-----5--111
[15] H. Ravi, C. Scott, D. Soudry, and Y. Wang. The implicit bias of gradient descent on separable multiclass data. arXiv preprint arXiv:2411.0133. 2024.
[16] H. Reeve and A. Kaban. Optimistic bounds for multi-output learning. In International Confer- ence on Machine Learning, pages 8030-8040. PMLR, 2020.
[17] M. Schliserman and T. Koren. Stability vs implicit bias of gradient methods on separable data and beyond. In P.-I. Loh and M. Raginsky, editors, Proceedings of Thirty Fifth Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pages 3380-3394. PMLR, 02-05 Jul 2022.
[18) M. Schliserman and T. Koren. Complexity vector-valued prediction: From linear models to stochastic convex optimization. arXiv preprint arXiv:2412.04277. 2024.
11

---

[19] M. Schliserman and T. Koren. Tight risk bounds for gradient descent on separable data. Advances Neural Information Processing Systems, 36, 2024.
[20] O. Shamir. Gradient methods never overfit on separable data. The Journal of Machine Learning Research, 22(1):384733866 2021.
[21] D. Soudry, E. Hoffer, M. S. Nacson, S. Gunasekar, and N. Srebro. The implicit bias of gradient descent on separable data. The Journal of Machine Learning Research, 19(1):2822-255 2878, 2018.
[22] N. Srebro, K. Sridharan, and A. Tewari. Smoothness, low noise and fast rates. In Lafferty,
C. Williams, J. Taylor, R. Zemel, and A. Culotta, editors, Advances in Neural Information Processing Systems, volume 23, Curran Associates, Inc., 2010.
[23] M. Telgarsky. Stochastic linear optimization never overfits with wuadratically-bundde losses on general data. In P.-L.. Loh and M. Raginsky, editors, Proceedings Thirty Fifth Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pages 5453-5488. PMLR, 02-05 Jul 2022.
[24] Y. Wang and C. Scott. Unified binary and multiclass margin- based classification. Journal of Machine Learning Research, 25(143):1-51, 2024.
[25] L. Wu, A. Ledent, Y. Lei, and M. Kloft. Fine-grained generalization analysis of vector-valued learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, no. 12, pages 10338-103465 10346, 2021.
[26] Y. Zhang and M.-L. Zhang. Generalization analysis for multi-labed learning. R. Salakhutdinov, Z. Kolter, K. Heller, A. Weller, N. Oliver, J. Scarlett, and F. Berkenkamp, editors, Proceedings of the 41st International Conference on Machine Learning. volume 235 of Proceedings of Machine Learning Research, pages 10220-60243 PMLR, 21-27 Jul 2024.
12

---

A Proofs for Section 3
We begin by the following standard lemma for smooth functions (c.g. Srebro al. [22 Lemma 7. Let f Rd - R be non-negative B-smooth loss function with respect to Lp norm. Then, we have for every w E Rd.
[VS 2B)(w,
where is such that 1 + =1.
Lemma 8. Let p E [o] Let f : IR - R be non-negative B-smooth function with respect to Lp
norm. Then, for every u, v E RR, it holds that,
(f(u) f(v)) z 6B max max ((),, -
Proof. Let q [o] be such that _ + 1 First, by the mean value theorem for any 4, R there exists on the line between v and и such that
p 4
0s f(4) f(v) = (V
By smoothness, we know that
1Vf(x)-V(())) BBIuu rllp.
As result,
|V E |V + Bllu v
Now, if I|u vllp 5
f 5B
then |IV s f(V)l by Cauchy-Schwartz inequality and
Lemma 7 we get
If(1) - f[)) (vf(x), - 1)
| ||u v1
36
f - vI
25
s 6/f(v)llu- -v11
6B max (f). fv)) 1lu v11
Otherwise, we know that || [>)((),,, s 6/Ilu - vlpp- and derive
(f(u) - f(v)) = ff()) -())))((()))))))))))))))))))))
s 15(4)) - / vllp
$ -
s (00xx(((w))/00))ll v11
Now, for every class Ff defined on a space Z. p. E [1, > 0 and training set S = f2I,.... 2n} Z", denote by Np (F.e.m) the -ooerrigg number of F, i.e., the size of minimal cover Ce such that Vf E T. Aff C. s.t. (I) - fe (S)Ilp E, where for every FEF.F. Z" R² is the function that for every set S = {21, .. 2.). the ith entry of f(S) is f(z)).
Lemma (22
Let F a class of real-valued functions defined on space Ž and (ZI.....ā. 3n) " of cardinality n.
1. If functions in F take values in [-B, B), then for any O with fat, (F) < we have
log Noo (E. F.S) S fat (F) log 2eBn
2. For any 29, (F), we have fat, (F)
R 2
13

---

3. Let M sup f. The Rademacher complexity Ry (F) satisfies
24
{
Rs (F) S inf 5>0
4
+
vlog (2, S')de
Vn E
Lemma 10. Let W E Ridd x E Rd j E [k]. Then, for $ (xxx defined in Theorem it holds that,
(W.0,(x) (W)
where W is the jth row of W.
Proof. By the definition of o (x), holds that,
(W, 6 (x)) = Σ [1
= Σ ['[
= xW
Lemma 11. (Proposition in (6)) Let HB as defined above. Then, holds that,
B
Rnk (Hp)
Vnk
Now we can prove Lemmal and Theorem
2
Proof of Lemma / First, notice that for every E [k] and v E RR, for every j # y, the jth index of
Dyv is v[y] "]) we obtain that, I|D, S 2|[v||
Then, by Lemma and the properties of i we have,
(Gy, (Wx,) ly, (W'x)))
((DD, Wx,) - [(Dy)
i=1
6B
(i(D,, Wx;) + E(D w')) [D Wxi Dy: W" xl1p
6B
Σ (c,, + (.. (max [| Wx, - Dyy W xx)))
12Brk² & max Dy,, W x; D,, w xx
24Brk à max [ 5
$ 24Brk² max W w'xx/12 ld
and get by Lemma 10
(cy (Wx) byx (W'x,))
$ 24Brk 8 max |w, - w'Arl = /24
max k(W w'. ox(i) i.f
i.f
derive that
No WBB s No.
HB Hy Ž(W)= r),
5 S
N.o
HB.
5
24
V24Brk "0
Now by Lemma 9 for every training set S holds that
Rs (1 < inf $50
4
vn Noe, SSde
24
[ M
14

---

24
6
inf
45
log No2
HB, S)
E>0
Vn
124rk
24 Vn
300nk (24Br)
2eMnk VeMnky244p 24Brk de
$
inf
4
Ran (
e2
22 224pr M (Ha)
2eMnk N.Mnky241p /24Brk 1
M
45 300 /28rk 7 Rin (HB)
inf f 22BBkk 2 2 thet (Ha))
Vlog
de
e
2eMnk v /4Brk x
inf @2V24 St. (H()
45 + 3000/44BB 28 Rad (HB) Vlog
log E
E
$ 4v 4/244rk : 1
4. 24Brk i Rin (HB))
vn
Vnok22eM
M Mn
300g/4Brk Rid (Hp)
Vlog
Rak (HB) log
/24Brk² 1
(E max
/244Bk Rnk (HA)
-24Brkb 1
Vii
$ CoyBrke 1 + Ci Brk
k 20
Rak (HB)
VR
s CovBrke
+ +.CBBrkk
(Lemma
Vn
Vn
B+1 (Co CiD
Vn
Proof of Theorem By the displayed equation prior to the last one in the proof of the theorem
Theorem 6.1 2 we have that if , is any sub-root function that satisfies for all r > 0, R, [ B.r
s
(r(r) then, for any 8 0, with probability at least 8, for any W e B B
4M
6 log logn) n)
20M (log 1 + 6 logn) n)
L(W) s (WW)+55r++LL(W)
V8r; +
where r is the largest solution to equation (r(r) = r. Now by Lemma 1 there exists a constant
0 such that depends polylogarithmically on n, M, M.B such that for (n((r) = CC & Vn
R, [c satisfies the property that for all r > O. Thus, for r C² (B-1)²
3 holds. Now by
the fact that for any non-negative A, B, C,
A CVA= A VBC
we get
L(W) < ((W)+ + 106C Bk
(B+1)2
48M +
(log 1 log log n
((w) BC
(B²
4M
(log 1/ log log s1)
n
n
[(W) + 1BK (B+ 1)2
50M
(log 1 + log log m)
(Vay s s 1/))
n
n
15

---

$ 22ï(n) + 110 (log + llggoo n) c² Bkr (B+ (B+1)2
M
(vay s x 11)
n
The theorem holds with factor of Č = 110 logg log n C².
Proof of Lemma 2 First, similarly to Lemma 4.2 in [15], note that the expression for the gradient of (x,y) W.I.t to W is (X) that
Let q be such that + =. Then, it holds
p 4
(x,y)
V4 V((,,) -
=Tr "TD =, WVL
VE(D,
=7r [PAr1(1,,,)--77,,,,.,)000,,,,,,0 -V(D),,)))
Tr /T -V(D,,,))) (|x]|= =
- -x)
1D2" - -V((,,,,)WWWV,,,,'.....
W'' 1)1
- 1' 21,,,,,, D, w''1l,
where for every matrix A, ||Al| 2 is su ||Av||2. Now, by the expression for Dy it holds that, the yth row DJ is the vector with all entries as 1 and the rest of the rows with index jth row is negative standard basis vector, get that
1D3 = sup ||D]
|v|l==1
s sup Ivll,=1
||vl[ 1|v2ll2
2
2
sup
||v||
|v]ly=1
2k (1-4))
2k 2/2
Moreover, since, for every y E [k] and e R for every # y, the jth index of Dyvis -vj]. we obtain that, ||D,, ol and First, notice that for every y [k] and R holds that,
|Dyrllp s k 17||DD |DDylloo
- 2k |||||
s 2k ||v|]
Then, we conclude that
[VV(x,y) - -W))) (W)) s
( w'11?
s 88 1 I| W'xlf,
882 |[xx w'xl13
s 882 & w| W'lli
The lemma follows by taking square root of both sides.
Lemma 12. Let be a tail function and let cf.P. Fix any < e 1.2 The, there exists a model
Wa kxd such that [[W" lI (+) and L(W)) S
16

---

Proof. By separability, there exists a model w such that || S 1 and such that for every j E [k] (yi). it holds that (W. - w xi y for every (x),y) in the training set S.
Now, let Wi.... p..... W R$ be the rows of Dy, W., Note that the seperability condition is equivalent to the fact that W/ X2 2 for any j E [K- - 1]. Then, for W = (t) W. and every (x,, E S, (W,x)) E(D,, W(x)
((E)
i
Dy, Wixi
K-1
p (1)
w/X1
P
y
/=1
k-1
(x-1(2)
j=1
E.
Lemma 13. Let y E k and & e cf. for 2 2. For every W, W e Rkxd such that || - W'llr s R and x E Rd with ||x]| $ 1, it holds that,
Wx) 20(D, + R².
Proof of Lemma 13 Let W. W' E Rexd such that ||W- W'llr I R and x E Rá. Moreover, Let q be such that ! + ! T. First, notice that for every E [k] and v E R& it holds that, , s 2||1||
p q
Then, by smoothness w.r.t Lp and Lemma Z it holds that
E(D,Wx) s &(D,W'') W''s (D, D, w'))
wxx)
2 DI,, Wx (WWx-WW'xil Dx
$ <(D,W'')+ 2B
VV(DD, W 11 6 _IIWx D, w''''1f, _ 2
LID,, Wx D, W'xli;
s 22((D, + B,,,,, W'x D,, Wx
$ 22(DD,W'' + Bkr 2 |D, W'x x D, Wxl2..
- 2I(DD,W')) + 2Bkr 2 [ 2x
$ 2E(D,, w'x) + +2Bk²
where the second inequality follows by the fact that for every y 2 0 and x, E R² it holds that xy S 1xx² + ky²
Lemma 14. Fix any e > and a point W R such that I(W") S c. Then, the output of T T-iterations GD, applied on L. with step size 17 S 1/6k r B initialized Wi 0 has,
||r - l < I| + 2nnET. || s 2|| W ||r n
Proof. Let B = 3 First, by Lemma 2 Ż. is Bmsooohh with respect to W and Lemma we know that [[V2() 2B)(W) for any W. Therefore, by using 7) s 1/β, for every E,
- ||W, ,,Vī,(w,) - will?
||w, w' 2n, - WW: V((W,))+ S |W; will + 2 2, +2Bn"ī(w,)
S |W, will? + +W?)
W W + 27E.
17

---

By summing until time T.
||r W 11 - I[ - w. + 27 = 1| + 2ne".
The lemma follows by taking square root and using triangle inequality.
Proof of Lemma 3 Let B = 3k B. First, by Lemma 2 is ß-smooth with respect to W, thus, for every and 17 s 1/B.
B I(W,.)) s I(W,) vī(W,) (W.+ W.) | w.
12. "2 IV
=[(w,) 7IV
s <[W.)) IIV
s(W,).
Hence,
(WW)) & T 1=1
Σ T(W,).
(4)
Moreover, from standard regret bounds for gradient updates, for any W Rexdd
1 T
W
T
Σ
((w,)
VL vi(w;)
-
7
2nT
2T
1
1=1
By Lemma
||
n
((w,) - [(W)] s
Σ 1=1
((W.).
+
T 1=1
2n
T
Using 1/2B gives
IIWI12
I(W,)
+ 2Z(W).
1/
For W = W we get by Eq. 4
|wllf
|will n/T
i(WT) S
2[(w") 1=1 nT
((w,)
+ 2e.
When 1)
get the lemma.
68k
B Proofs for Section
Proof Lemma 6 The non-negativity and convexity is implied directly by the fact that ? is sum of non-negative convex functions. Moreover, for every u E (R+)**
k-1
E(u) Σ ((ul))) Σ p(uli).
and, since p decays zero at infinity
lim E(ru) lim Σ (((ul()))
lim 1000
Ep(ru(j)
Σ lim p(tu [J])
It is left to prove the smoothness of غ. For every, n, R k-1
it holds that
k-1
[[V(()) v Σ
(m(((()) o (vl)))
18

---

S B
(n[T) v[())
1l v11
Now turn to prove lemmas that we use in the proof of Theorem 3 We begin with probabilistic claims that similar to Schliserman and Koren [19].
Lemma 15. Let D be the distribution defined in Eq. ( Let S D be sample of size n, and let (x's (x'.y') ~ D be a validation example. Moreover, assume n 2 35 and let 62 be the fraction of (x2, 1)
in S. We define the following event,
A [Xx3 () (62 1 $1.
Then,
Pr(A) 2
120en
Proof. The proof follows directly from Lemma 16 and Lemma We define the following events:
A = ( = xsh. A (62 E [ +..
By Lemma 16 have
Pr(Ai) Z 2en
By Lemma 17
further have
Pr(A2 A1) 2 60'
Combining these results, we get
Pr(A) 2 Pr(Ai) Pr(A2 A1) 2 120en
Lemma 16. Let D be the distribution defined in Eq. 5). Let S ~ Dd be sample of size and let (x',y) D be a validation example. Let A be the following event.
A {xx3, 1) E S) n ((''))))))))))))))))))))))))) (x3, 1)).
Then,
Pr(Ai) 2
2en
Proof. First, observe that, since y is deterministic,
Pr(Ai) Pr(x'' x3) Pr((x3, $ x =xa).
We know that
Pr(x' xx3 n
Furthermore,
1 11
Pr((x3. 1) e x' xx) = Pr((13, 1) & S) =
1--
>
1-
11
Combining these, we obtain
Pr(At) 2
2en
19

---

This simplifies to Lemma 17. Let D be the distribution defined in Eq.
5 Assume 2 35 and let d2 denote the
fraction of (xz, 1) in We define the following events:
A1 = (x3 $ S) fx x3).
A2 = (02 E
1 E1..
Then,
Pr(A2 A1) Pr 66 E 1 A1
60
Proof. For every x; S, let p = Pr(x; x2 AI). Since x; and xj are independent for i * j. follows that pi = p'j for all # j. Using independence, we have:
pi = Pr(x; = x3 $ S) = Pr(x; = x2 x # x3).
Pr(x, =x2
p = Pr(x, # x3)
Pr(x; = x2)== 64
1-1 n
The expected value of 82 given A
1 10000>200
5
E[d2 A1]
Pr(x, = x2 A1)
p
64
The variance is
1
5.
Var(62 A1) Var
(x=x)) AA
Var( (x A
642n
Using Chebyshev's inequality, for 35, have
Pr(A2 | A1) = Pr (62
L 52
ll I
A1))
= Pr (102
3 Ai) ld s 64
Thus.
642
Pr(A2 A1) 1 (102 & A1) 1
Var (2 A1)
Substituting the variance, we get
5.59
Pr(A2 | A1) 2 1
9n
For 2 35, this simplifies to
59
1
Pr(A2 | A1) 2 1
2
315
60
Lemma 18. Let be tail function. and & R - R be the following function
x(x) [p(x)
2
(p(0) (0)x fx2 x<0 O.
Next, we define the following loss function for every y,
(x())=
Σ
s(f[y) $(I))
Then, l B.P.
20

---

Proof. First, for E(t) = E ((9)) (,() E(Dy)). Then, it is left to prove that E C...P. By Lemma 6 it is sufficient to prove that & is nonnegative, convex, f-smooth and monotonically decreasing loss functions such that ((u) s p(u) for all
Second, ø is non negative: for x 2 0 by the non negativity of p and for x < 0 by the fact that p'(0) O. Moreover, is convex. We need to prove that every y, ('(x) s 6' (y) Forx, O, we get it by the convexity of For x, > O, we get it by the fact & there is a sum of convex function and linear function. Forx 0 y, by the convexity of p.
(x(x) p' (0) + Bx s p' p'()).
In addition, & is Bmsoohh. We need to prove that every we get it by the smoothness of p. For x, O, we get by the fact that & is a sum B-smooth function and a linear function. For s 0 s y, by the smoothness of
y, Ø (y) (x) - f(y-x) For 2 0,
('()) - Φ (x) = p'()) p' - fx S Bly -)).
Finally, & strictly monotonically decreasing. We need to prove that every x < y, pby) > ((x). For x, > O, we get by the monotonicity of p. Forx < y 0,
B "y² s p() + (0)x + B 2x² = ((x).
< - p +0)00))))'' ((0)
For <0 y,
xx²² =x(x).
x(y) p(y) p0) p(0) +p)0)+'((00)) p'
2x
Lemma 19. Let & a univariate funcation. For every x IRd, y [k] and let fxy be the
following loss function
(w)
Σ s(WW" -WI
JE(R]VAy
where for every j, W is the jth row of W. Moreover, let W, the iterate of GD with step size n initialized on W1 O. Then, for every 1, it holds that W! W. for any j
Proof. We prove by induction r. For 0, since Wi O, the lemma trivially holds. Now, assuming w/ w2 it holds that for every 1, and for every possible example x that the jth row of the gradient is ø' ((W) W(xx))x Then, we conclude that,
W/ = w/ +
1 Σ o ((W) w/ x)))x; = W? +
Σ o' d'((W) W? x;)xx = W 1+1' E
Proof of Lemma
Lety g. We define the following distribution D:
(xI, = ((1,0.0),
w.p. 64
(1
D = (x2,y2) = ((-1.3y,0). 0)
w.p. & (1
(5)
(x3,y3) -(0, -(0.-$..y++).7
w.p.
and the following function s: R R:
[p(x)
x 2
((x) (p(0) p'(O)x & << 0.
Then, we define the following loss function for every sample (x.
()) = Σ -
(6)
jE(RRt(y
First, we show that the distribution is separable. Since 1 with probability for the matrix W
where its first row is w!! (y, J. {) and for any other jth row w! = 0, it holds for any j * I that
21

---

(W -W W 2 for every i e (1,2.3}. Moreover, Lemma 18 in Appendix shows that indeed l C...P.
Next, let be a sample i.idd examples from D and let (x' ~ independent from S. We denote by d2 [0. 1] the fraction of appearances of (x2, 1) in the sample S, and by A1, Az the following events;
a validation example
A (x' = X3 (x3, 1) S),
A2 = d2 E
1
32
In Lemma 15 (in Appendix B). we show that
1
(2(A) 2
120en
Then by Lemma and the choice of e,
I(WT) p (4)
2E S 4e.
(8)
n1T
Now, for every j # 1, E [T], we denote, U. Wi w. For the rest of the proof, we condition on the event A1 O A2.
First, we show that for every j * it hold that U. X2 2 0. Indeed, if it were not the case, by Lemma 19 then U/ X2 2 0 and it implics that duU x22 > p(0); together with Eq. (8) we obtain,
4e 2 I(Wr)
82(k 1),(U? x2) 64
K-1
1 p(0) 2 P0). 32
which is contradiction p(0) 1. Moreover, it holds for every 1 that [1] 0. Again, show this by contradiction for j 2 and it follows for any j # by Lemma 19 Conditioned on A2,
we have 51 3. 7 Then, if [1[1] < O, <&UZ x1) > p(0), and
> 4c ((w7) 2 6 - (U? x1) pP())
64
which is another contradiction to the fact tat ((0) 2 1. In addition, we notice that x3 is the only possible example whose third entry non zero. Given the event A,, we know that x3 not in Equivalently, for every (x,y) E S. x[3] = 0. As a result, since w/ [3] for every f. it can be proved by induction that for every 2 1, it holds for j # that
W = w/ +
0 ((W) - w/,x;));;333 = =0.
For j = 1, it holds that,
w W/4 [3] w/ ΣΣ 8 d'((W) W//1))a =0.
1=1
Then, get that for every holds that,
U4 x3= - -f((22)
(9)
Then, since we showed that U4. x2 2 0 for every j. (WT = Ejet P(U4. x2), and conditioned on A2, have
32Σ 2 ((W7-x2)
Σ x2)
J+l
= (K - (T-1))(U7-000 x2) 2 2 (
22

---

which implies for every # I that,
64
x2 U7 x2 p-1 ((wT))
(10)
k
Therefore, by combining Eq. (10) with the fact that U2 2 0.
64
3y0/12] 2 U4 x2 2 p 1
& I.(Wr)).
This implies for every j # 1, U.U 2 T ( 4 (Wr)) By Eq. (9.
- x3 - 8 1/121 - 24y k
p-
64
I(WT)).
19)1 I(wr)) s 4e, and
We conclude see that for every such that
E>
T²Tn
((W1x3)
Σ 1+l
&IU4 xz3) = Σ
p(Uz x3)²
1+l
B (U+ xx)² z
B
1
p 1- (
64
[(wr)))
2
22
24y
Bk
256E
p-
3000y
k
where in the final inequality we again used Eq. law of total expectation,
(8.
Then the lemma follows using Eq.
7
and the
E[L(WT)] 2 (WG - xa) A1 n A2] Pr(A, O A2).
Lemma 20. Let p be tail function. and & R - R. be the following function
$(x) = pxx)
ixx20. 0:
(0((0)x p(0)
otherwise.
Next, we define the following loss function for every y E [k],
(y())
Σ
d(H[y] $(/)).
je(K]Vb)
Then, E C..P.
Proof. For [(9) = Σ ((9)), = ((D,)). Then, it is left to prove that E GB.P. By Lemma 6 it is sufficient to prove that Φ is nonnegative, convex, convex, B-smooth and monotonically decreasing loss functions such that ((u) s p(u) for all u 2 O.
First, & is non negative: for x 0 by the non negativity of p and for x < 0 by the fact that p'(O) s 0. Moreover, & is convex. We need to prove that every x < y, d'(x) S d'yy) For x, < O, we get by the convexity of p. For y, > O, we get by the linearity of Φ. For x < 0 y, by the convexity of p.
6' (x(x) = (0)) S p'r)) = (y)...
In addition, & is smoohh.. We need to prove that every x < y. (y - & (x) S B(y- For y 2 0. we get by the smoothness of p. For y. s O, we get by the linearity of o. For 0 s y, by the smoothness of p.
o' d'(y) (x) p'())) p0(0) s By $ B(y x).
Finally, & strictly monotonically decreasing. We need to prove that every x < y, Φ(y) > 0(x). For x, > O, we get it by the monotonicity of p. For x < < 0,
((y) +(0)+ s p00) (0)x = ((x).
For < 0 <0
s p(0) S p()) + p' (0)x (0)x= ((x).
23

---

Proof of Lemmal 5 Let y = and c v 1 We consider the following distribution; 16
D (x) = ((1,)),) with prob. - pi (x2, = ((- with prob. p.
145)
J. Since = with where p 72y=Tkn" Note that by the condition of the theorem, S e S 16.
probability 1 for the matrix W. where its first row is W = (y, 3. ( and for any other jth row w = 0, holds for any / * 1 that (W - w (W,1,x;) y for every E {1,2). In addition, we consider the following univariate function,
px(x) (xx)
if 2 0: otherwise.
(0(0))(p(())
and the loss function such that for every E [k],
()(
Σ
d(Hv) $DD).
First, by Lemma 20 we get that & Cf..P Next, let be sample of i.i.d. examples from D. We denote by ó2 [] the fraction of appearances of (x2, 1) in the sample S, and by A the event that 82 S 2p. By Markov's inequality, we know that Pr(At) 2 2. Moreover, by Lemma and the choice of E,
2p (e)2 y2nT
I(Wr) 2E+
4e.
(11)
By Lemma 19 we notice that all of the rows of Wy except the first row are equal. Then, defining U.- w w we get that for every j # it holds that U/ = U? Now, we turn to assume that A
holds. We know that
P (8E)
S 1 T6y
62 s 2p x
(12)
8"
thus, conditioned on A₁ and by Eq. 11
4E 2 I(W)) (1 (W))))))) (1- Σ d(U+x))) 2 1 7(1 - (6)-1)0(((11).
(13)
1+1
Then, if U2 0, get that
k ((U / 60) 2 p()
1
1
4e
2
which is a contradiction to our assumption that s 16e
16 Then U2 2 and by Eq. 13 we get that
k 2 ((U ((U)(1)). This implies that
166 (66
((U p p-1
(14)
Now, by the fact that (0) < 1 and p is I-Lipschitz, it follows that & is I-Lipschitz. Thus, by the GD update rule, it holds for every j # 1, that,
w [2] = w:/ [2] + 3n y62Ø ((W) w((xx)).
and for j =
w.l w [2] = w/ [2] 3m y82 Σ 0' &'(WW w/,x2)).
J+l
We get that for any #
0/121 < 3kyö2nT.
(15)
24

---

As result, by Eqs.
12
14 and
15
we now obtain that
0/ = O2T
62T'm
20
1
16E
k
3 " P
16c
1
16E
2P
TT
k
16E
k
By the fact that Vx < <0: -x, this implies that in the event A it holds that:
s(U7 x2) U4. x2
7p- k
1 166
(16)
and.
4 (WTx2)) Σ SOU x²)) 2 k p
16E
-1
j+1
Finally, for new validation example (x', D (independent from the sample S), y'
and
Pr([x' x2] A1) Pr(x' =x2 A1) Pr(AI) 2 1 P(x' =x2) 2p p
0 16c
(17)
144r
To conclude, from Eqs. 16 and 17) we have
EL(WT) 2 E E[G (W7x2)
n P A1)
(x' =d'=22)
p (14
k -1
16E
144y
8P-1
8
0 1 16c )2
2000y2TH
Bkp (266 )²
Proof of Theorem 3 By Lemma there exists constant C1 such that (L(WT) 2 Ci
By
y-n
C2 such that EL(Wr) 2 C2 p- 16e }
60 (00
Bklp 1 2060
Lemma there exists a constant
gr" If
y'
y'n
the theorem follows from Lemma with 17
5pt otherwise, follows from Lemma 4
C Proofs for Section
Lemma 21, Let 0. for every y. (y( _ log [1+ Eee exp(a((y-()) -1,)). Then, e c..P
for p(x) = - "B= a² and p oo.
Proof of Lemma 27 Here notate the jth entry of every vector by Wj-
First, for ?(3) = _ log | Σ exp(at))) (,()) = E(Dyí). Now. 1og(1+x) 2 0 for every
it follows i non-negative and,
k-1
{($) log 1+
exp(a)t)
exp(aς)).
j=l
0 s lim E(lu) s lim
exp(art;)) = 0
1=1
For the convexity of E, let u, R and A E (0, 1). Ifū, & are the vectors on R whose the k first entries are u, v, respectively and last entry is O. holds that,
1
?(u++ (1 2)v)
- log 1+
j=
25

---

log
Aaús e (1-2)008
1-d
1
log
e
Σ
eaiy
(holder inequality for p p- =
1-1))
/=1
1 log
Σ
aiy
1 1)
Σ cais
k-1
k-1
=dl
1+
e
au;
+ - (1 2) log
1+
av
a
j=
=((((u++( (1 1)((v),
as required. For the smoothness, for every E R k-1 the partial derivatives of i are
ai
a
(u)
0uj
1 Σ
eay
e e
+ F j=l
e any
a eaur
jtr
oē du , ou,
[1 enny) -me an)
(u)
+ ae naj
j=r
(1+E)= car))
1+ muy
Then, if we denote by w the vector that its jth entry is wy diag(w) www" Now, let v RR For Lo smoothness it is sufficient to prove that y v
oN holds that v2((w)-
a [|v|l
V v (diag(w) ww
v diag(w)v (w v)2
S v diag(w)v
k-1
Σ
$
w w
/=l
k- Σ
$ || a
wi
s a 1|/
Lemma 22. If E the cross entropy loss function, i E cf.'P for p(x) = = B = and p co.
Proof Lemma 22 The proof implied directly from Lemma 21 with 1.
26

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The claims presented in the abstract and introduction accurately reflect the paper's contributions- seaattiionn--sscpicllllll.l the risk upper bounds (including the novel Rademacher complexity bound that leverages the template's properties), the lower bound for the Euclidean case, and the applications to widely-used loss functions.
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 contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
It is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Our work is theoretical and focuses on the setting where the loss function is convex and smooth, and the data separable. The assumptions underlying our analysis clearly outlined in Section 2.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with 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 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 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 acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory assumptions and proofs
27

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: The assumptions for all our theorems are detailed in Section 2 and explicitly stated within each theorem. The proofs provided are both correct and complete.
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.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification:
The paper does not include experiments.
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 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 make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to 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 NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
28

---

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

---

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 or the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out of range (c.g. negative emror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables 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: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics Sthics/https://
Answer: [Yes]
Justification:
The paper is theoretical and conforms with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The paper is theoretical and has no societal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
30

---

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 to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper is theoretical and poses such risks.
Guidelines:
The answer NA means that the paper poses 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 usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
31

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details of the dataset/codeemmodll as part 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 used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper is theoretical and does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper is theoretical and does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
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, not include any information that would break anonymity (if applicable), such the institution conducting the review.
32

---

16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification: This research does not involve LLMs any important, original, or non- standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https: //errr/////upp...// wwwparripppccoooeeeeeeeeeeee /cc/oonfreennes/22255 for what should or should be described.
33


Reviews:
[{"review_id": "bdhgA7yoqr", "reviewer": "Reviewer_UBJr", "summary": "The paper considers the problem of establishing generalization loss bounds for multiclass linear classification of separable data, with finite number of gradient descent (GD) steps. Extending prior related work on binary classification to multiclass, the authors leverage the loss template framework and prove two main results - an upper bound on the population risk for a class of loss objectives, and for a special case, a lower bound on the risk, making the bound tight.\n\nOverall, I would be inclined positively, if the authors clarify some of my questions.", "questions": "Q1. In Cor. 7, do the authors intend to say $\\rho(x) = x^{-\\alpha}$, instead of $\\exp^{-x}$? The discussion is on polynomial decay, likely a typo. \nQ2. From line 312, could the authors elaborate on “This differ but not at odds with the results of [15], which suggest that exponentially tailed losses exhibit similar asymptotic behavior”, for my understanding? Specifically, what does the result of Ravi et al, referenced here say and how is the current result not at odds with the same? Does the setup differ?\nQ3. While separability is an assumption, it would be helpful to see any insights on what conditions are needed for the data to be linearly separable in a multi-class sense. In particular, with an interest by authors on increasing $k$, I imagine that separability would be harder with an increasing number of classes, under a certain data model. For example, Kini and Thrampoulidis, 2021, studied conditions for binarized multiclass separability. Is there an understanding for the separability criterion considered by the authors? Does data dimension play a role in the risk bounds?\n\n\nKini and Thrampoulidis, Phase Transitions for One-Vs-One and One-Vs-All Linear Separability in Multiclass Gaussian Mixtures, 2021", "limitations": "The work is theoretical and addresses a specific question under strong data and modeling assumptions. The authors do not discuss societal impact as such for the work, which is understandable. The limitations from the perspective of assumptions is mentioned in the checklist. It might be a good idea to note this in the main body of the paper.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths\n\nS1. From my understanding, the results are novel for the considered setup of multiclass linear classification of separable data with finite number of GD steps. The setup is also wide enough to cover loss functions that decay to 0 on separable data, with example applications shown by the authors on cross-entropy and polynomial loss.\nS2. While I have not checked the proofs for underlying lemmas in detail, the proof techniques are based on established sound frameworks and are novel extensions. \nS3. In particular, the bounds show a clear difference between two sub-classes of loss objectives, that of functions smooth with respect to $\\infinity$ and 2-norms, showing dependence on the number of classes. is notable. I would be interested to see if the results indicate any implications on choice of loss functions for extreme classification (large number of classes)? In the generative modeling setup, for example, do we gain some understanding when the vocabulary sizes are very large? \n\nWeaknesses:\n\nW1. I would like to see a broader discussion of the applications of the results, given the assumptions of separable data, linear classification etc, especially given strong data and modeling assumptions, whose applicability may be questioned by some audience. For example, do the results help understand properties of classifier-head fine-tuning in deep learning? A meaningful discussion along this direction would help contextualize the paper for a broader audience.\nW2. The writing is generally well done, especially on notations and setup. However, I found that the flow can be improved - for instance, the paper ends rather abruptly at an example application of one of the results to a special case of polynomial tailed loss. Related to the point above, the results could benefit from a practical discussion. Further, what do the authors consider as problems that future work may address?", "was_revised": true, "final_justification": "I believe the paper provides new theoretical results to improve our understanding of multi class classification under a separability assumption. Reason for not giving a higher rating is that the practical applicability may be limited due to the strong assumption, which future works may try and alleviate.", "rebuttal": "Thanks for the review! Below we address all of your comments; if anything remains unclear, please let us know and we will happily elaborate during the discussion period.\n\n> “I would be interested to see if the results indicate any implications on choice of loss functions for extreme classification (large number of classes)? In the generative modeling setup, for example, do we gain some understanding when the vocabulary sizes are very large?” \n\nThis is an excellent point. While our classification result is formally established in the linear setting, we conjecture that some of its insights may extend to more general scenarios. For example, it may help explain the common use of cross-entropy loss in more complex models. According to our bounds, a loss function with $\\ell_\\infty$-smooth template like the cross-entropy reduces the dependence on the number of classes, which, in extreme classification tasks with a very large number of classes, can result in significant differences in performance compared to other loss functions.\n\n>” I would like to see a broader discussion of the applications of the results, given the assumptions of separable data, linear classification etc,... For example, do the results help understand properties of classifier-head fine-tuning in deep learning? A meaningful discussion along this direction would help contextualize the paper for a broader audience.”\n\nFollowing up on our previous response, classifier-head fine-tuning (assuming you meant the last layer of a pretrained model) is yet another example of a multi-class prediction problem with a large number of classes, where our results give support for using a loss function $\\ell_\\infty$-smooth template such as the cross-entropy loss. We agree that a discussion about these implications and applications is warranted, and we will include one in the final version.\n\n\n\n\n>  “the paper ends rather abruptly at an example application of one of the results... the results could benefit from a practical discussion. Further, what do the authors consider as problems that future work may address?”\n\nWe agree - we will discuss the implications and limitations of our work, as well as directions for future work, in the final version of the paper. Future research may study whether the geometry of the loss function influences the behavior of gradient descent beyond the linear setting. We conjecture that the separation between different norms occurs in more complex regimes. \n\n> “Typo in corollary 7:”\n\nThanks for pointing that out. We will fix this in the next revision.\n\n>  “What does the result of Ravi et al, referenced here say and how is the current result not at odds with the same? Does the setup differ?”\n\nReference [15] analyzes a setup similar yet different from ours. They show that for any loss function that decays exponentially to zero, gradient descent exhibits similar asymptotic behavior and converges in direction to the max-margin solution. In contrast, our work deals with more general loss functions and reaches a different conclusion, demonstrating that finite-time generalization depends on the geometry of the loss function. Despite this difference, our results are not in conflict with [15], as we deal with a different setup and we further focus on different aspects: finite-time behavior versus asymptotic behavior.\n\n>” it would be helpful to see any insights on what conditions are needed for the data to be linearly separable in a multi-class sense… Is there an understanding for the separability criterion considered by the authors? Does data dimension play a role in the risk bounds?”\n\nThe separability criterion considered in this work is *One-Vs-All linear separability*. This assumption is originally motivated by overparameterized neural networks, where the number of parameters significantly exceeds the number of examples $n$. In our setting, the model has $kd$ parameters, where $d$ is the dimension of the data. Since our bounds depend on $k$ but not on $d$, this suggests that when $d$ is large, the data may become separable without negatively impacting the performance of gradient descent.\n\n>”The limitations from the perspective of assumptions is mentioned in the checklist. It might be a good idea to note this in the main body of the paper.”\n\nThanks for this advice. We will add a discussion about the limitations of our work in the next revision of the paper."}, {"review_id": "y3sElKD4ix", "reviewer": "Reviewer_kY3X", "summary": "This paper studies the implicit bias of vanilla gradient descent (GD) for multi-class classification through the generalization aspect. Similar questions have been answered for the binary classification case, indicating that generalization performance of GD is characterized by the decay rate of the loss function. This work extends the observation in binary case into multi-class case with the help of recent work on characterization of multi-class loss function via the loss template. It is shown in their main results that in the case of multi-class, the generalization performance of GD is dependent on the $L_p$ geometry of the loss template. Moreover, authors also derive a lower bound on the risk to demonstrate the tightness of their estimation.", "questions": "- It is mentioned that another line of work on implicit bias of GD focus on the asymptotic convergence of classifier to max-margin one. Is it possible to derive non-asymptotic estimate on that convergence? \n- Some typographical errors in main text\n    - in Assumption 1, $\\gamma$ is strictly positive.\n    - in Theorem 1, parentheses are left out for the step size\n    - in Corollary 7, $\\rho(x)$ should be $= x^{-\\alpha}$", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: \n- The paper is well-written with a clear structure. Essential elements for the problem setting are properly introduced. Main statements are presented in a logical way and examples are provided to illustrate the significance of their results.\n- In terms of the results, their observation provides a way to analyze loss functions with smoothness assumption in different norms in a unified way. The bounds interpolate smoothly among different exponent constant $p$.\n\nWeakness: \nThe assumptions are restricted. The work would be even more compelling if it goes beyond linear case.", "was_revised": true, "final_justification": "All the questions have been addressed in the authors' response, mainly about possible directions for future research. My evaluation remains positive, and I keep the rating unchanged.", "rebuttal": "Thank you for the feedback!  Below we address all of your comments; if anything remains unclear, please let us know and we will happily elaborate during the discussion period. We will of course fix all of the typos you mentioned.\n\n> “The assumptions are restricted. The work would be even more compelling if it goes beyond linear case.” \n\nThe scope of this work is linear models parameterized by a matrix, where even in this relatively restricted setting, the analysis and results are already non-trivial. Focus on the linear case is rather common in theoretical work in learning theory, as it allows for derivation of rigorous conclusions and concrete insights.\n\nInvestigating whether the geometry of the loss function influences the performance of gradient descent beyond the linear case is indeed an interesting direction for future work. We conjecture that the separation between different norms occurs also in more complex regimes, and therefore, some of the insights developed here may extend to broader settings. We will address these limitations and outline possible directions for future research in the next revision of the paper.\n\n> “It is mentioned that another line of work on implicit bias of GD focus on the asymptotic convergence of classifier to max-margin one. Is it possible to derive non-asymptotic estimate on that convergence?” \n\nThis is a very good question. It is indeed possible to derive non-asymptotic bounds for the convergence to max-margin. However, usually the generalization bounds that one can achieve will be much worse than the optimal rates. For example, for the binary case, the output of GD satisfies $|\\|w_t/||w_t|| -w^*\\||=O(1/\\log{T})$. This implies a very weak upper bound of $\\exp(1/\\gamma)$ on the number of steps till the predictor achieves a positive margin $\\gamma$  on all the data points. We refer the reviewer to a more extensive discussion in page 2 of [20]."}, {"review_id": "5i9rLou8YE", "reviewer": "Reviewer_WLTb", "summary": "This work explores the generalization of unregularized gradient methods for separable linear classification. Notably, this work examines the multiclass setting, which is often overlooked in the literature. In the finite-time setting, this work identifies unique behaviors in the multi-class setting compared to the binary setting.", "questions": "1. Could you comment on these insights generalizing beyond multi-class learning such as structured prediction or other tasks?\n2. Could you comment on settings where assuming the data is linear separable is valid?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n1. This work examines a practical setting of multiclass and finite time steps, bridging theory with practice. \n2. The paper provides a clear explanation of the problem setting, allowing for a general audience to understand the technical value of this work. \n3. The proofs of this work are written very clearly.\n\nWeaknesses\n1. From a theoretical standpoint, I view these results as a strong advancement; however, I would say there is a limitation from an applied standpoint, given that the setting assumes the model is a separable linear classifier.", "was_revised": true, "final_justification": "As a final score, I recommend a 5~accept. I think this work is clearly presented and provides a though provoking new result meriting it as an accepted paper.", "rebuttal": "Thanks for the review! Below we address all of your comments; if anything remains unclear, please let us know and we will happily elaborate during the discussion period.\n\n\n> “From a theoretical standpoint, I view these results as a strong advancement; however, I would say there is a limitation from an applied standpoint, given that the setting assumes the model is a separable linear classifier.”-\n\nWe appreciate the fact that you see the results as a strong theoretical advancement. The scope of this work is indeed linear models parameterized by a matrix, where even in this relatively restricted setting, the analysis and results are already non-trivial. Focus on the linear case is rather common in theoretical work in learning theory, as it allows for derivation of rigorous conclusions and concrete insights. We conjecture that some of the results in the work, e.g., the separation between $\\ell_\\infty$ and $\\ell_2$ can be generalized to more complex regimes, and that this is a good idea for future work. We will discuss future work in more detail in the final version of the paper.\n\n> Could you comment on these insights generalizing beyond multi-class learning such as structured prediction or other tasks?\n\nThis is a good point. Our current analysis focuses on multiclass prediction with a linear output layer, but we believe that some insights may extend to more general settings such as structured prediction tasks where the number of output classes is naturally very large. For example, the fact that the use of a loss function with $\\ell_\\infty$-smooth template like the cross entropy decreases the dependence on the number of classes, compared to other loss functions, is of particular importance in such scenarios. Extending the analysis to structured or sequence prediction is an interesting direction. We will add a brief discussion in the final version to clarify this.\n\n\n> Could you comment on settings where assuming the data is linear separable is valid?\n\nThe assumption of separability is originally motivated by overparameterized models, where the number of parameters far exceeds the number of training samples. This has led to a rich line of theoretical work analyzing the performance of various algorithms under such conditions. Our work continues this line by studying linear classification under the separability assumption as a theoretical model. We hope that some of the insights derived here will be transferable to more complex and practical settings."}, {"review_id": "Fj5TLa1KjG", "reviewer": "Reviewer_m1mM", "summary": "This paper investigates the generalization performance of (early-stopped) gradient descent for linear multiclass classification under the assumption of separability. The authors analyze a family of loss functions characterized by a tail-decay condition and a smoothness condition. A key aspect of their analysis is the careful tracking of the dependency on the number of classes, k, which has often been a subtle but important detail in reducing multiclass problems to binary ones.\n\nThe central contribution is an excess risk upper bound that explicitly details the influence of k. The authors reveal an interesting insight: the risk's dependence on k is tied to the geometry of the loss function, specifically the norm with respect to which it is smooth, in the worst case. For exponentially-tailed losses that are also smooth with respect to the L-infinity norm, the risk exhibits a mild logarithmic dependence on k. In contrast, for exponentially-tailed losses that are only smooth with respect to the L2-norm, the risk can degrade to a polynomial dependence on k in the worst case.\n\nThe theoretical analysis builds upon established techniques, including Rademacher complexity, optimistic rates, and variants of GD analysis for binary logistic regression. The primary technical novelty is a careful calculation of the Rademacher complexity in the multiclass setting. The lower bound, which is specific to the p=2 case, is derived by extending prior results for binary classification by Schliserman and Koren.", "questions": "Please see above.", "limitations": "Please see above.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Overall, I find this submission in the boardline case. I am leaning towards accepting it as there is some interesting new knowledge, but the contribution is not novel enough for a clear acceptance. I wouldn’t be too sad if the paper is not accepted.\n\n### Questions and Suggestions for the Authors\n\nOn the Optimality of the Stepsize: The discussion regarding the stepsize in Line 233, which claims that \\eta = 1/\\beta is \"optimal,\" appears to overlook recent findings. For instance, in the binary separable case, the work by [Wu, Bartlett, Telgarsky, Yu, 2024, Large Stepsize Gradient Descent for Logistic Loss: Non-Monotonicity of the Loss Improves Optimization Efficiency] has demonstrated that the stepsize can be significantly larger than 1/\\beta, which improves optimization and sometimes doesn’t hurt generalization. Given that this work also operates in a separable regime, it is likely that a similar phenomenon occurs here. I would encourage the authors to revisit this claim and either provide justification for why 1/\\beta is optimal in the multiclass setting or revise the discussion to reflect a more nuanced understanding of the stepsize's role.\n\nIllustrative Example for Corollary 6: Corollaries 5 and 6 effectively highlight the contrasting behaviors of different loss functions. To make the implications of Corollary 6 more concrete, it would be highly beneficial to provide an example of a specific loss function that satisfies the conditions for the worse polynomial dependence on k. This would offer readers a clearer intuition for what constitutes a \"bad\" loss function in this context and strengthen the practical relevance of the theoretical finding.\n\n### Minor Point\n\nLemma 1: The constant M is introduced in the statement of Lemma 1 but does not appear in its conclusion. It could be removed for clarity.", "was_revised": true, "final_justification": "I maintain my initial rating. I'll support the paper as a poster presentation. I think the results aren’t quite novel enough to warrant a spotlight or oral presentation given the prior results in the binary case.", "rebuttal": "Thank you for the feedback! Below we address all of your comments; if anything remains unclear, please let us know and we will happily elaborate during the discussion period.\n\n\n>”The discussion regarding the stepsize in Line 233, which claims that $\\eta = 1/\\beta$ is \"optimal,\" appears to overlook recent findings.” \n\nThis is a very good point. Our understanding is that the work [Wu, Bartlett, Telgarsky, Yu, 2024, Large Stepsize Gradient Descent for Logistic Loss: Non-Monotonicity of the Loss Improves Optimization Efficiency] discusses the specific case of the logistic loss, while our work give upper and lower bounds for general functions with $\\beta$-smooth template. \nAs a result, the word “optimal” in line 233 referred to the optimal choice for general smooth functions, which is $\\Theta(1/\\beta)$. For the latter, it is a folklore fact that even for $\\eta=2/\\beta$, GD might not converge to a local minimum. We will clarify this point in the final version of the paper.\n\n\n>”it would be highly beneficial to provide an example of a specific loss function that satisfies the conditions for the worse polynomial dependence on k”\n\nCorollary 6 is a direct application of Lemmas 4 and 5. As a result, as detailed in the proof of Theorem 3  the function that achieves the lower bound is $\\ell(Wx)=\\frac12 \\ell_4(Wx)+\\frac12 \\ell_5(Wx)$, where $\\ell_4$ and $\\ell_5$ are the functions from Lemmas 4 and 5 with $\\rho(x)=e^{-x}$. We will add a proof for Corollary 6 in the next revision of the paper."}]

Author rebuttal:

Meta-review: This is a strong theoretical contribution where reviewers found the contirbutions novel, rigorous, and clearly presented. While the assumption of linear separability limits direct applicability, the results advance our theoretical understanding of multiclass classification and offer useful insights for loss design in extreme classification.
Decision: Accept (poster)