Tight and Fast Bounds for Multi-Label Learning
Authors: Yi-Fan Zhang
Min-Ling Zhang
Venue: ICML 2025 poster (2025)
Keywords: Multi-Label Learning
Generalization Bound
Primary area: theory->learning_theory

Abstract: Commonly used evaluation metrics in multi-label learning all involve base loss functions, and the theoretical guarantees of multi-label learning often rely on the properties of base loss functions. Some recent theoretical works have used the Lipschitz continuity of base loss functions to prove the generalization bounds for multi-label learning, but the impact of the smoothness of base loss functions on the generalization bounds is completely unknown. In an attempt to make up for this gap in the generalization theory of multi-label learning, we develop some novel vector-contraction inequalities for smooth base loss functions and derive tight generalization bounds with no dependency on the number of labels, up to logarithmic terms. We then exploit local Rademacher complexity to develop some novel local vector-contraction inequalities for smooth base loss functions, which induce generalization bounds with a tighter dependency on the number of labels and a faster convergence rate with respect to the number of examples. In addition, we derive tight generalization bounds with no dependency on the number of labels, up to logarithmic terms, for Macro-Averaged AUC by exploiting the Lipschitz continuity and smoothness of base loss functions, respectively. Our state-of-the-art theoretical results provide general theoretical guarantees for the generalization of multi-label learning.

Tight and Fast Bounds for Multi-Label Learning
Yi-Fan Zhang Min-Ling Zhang
Abstract
(Wang & Sukthankar, 2013; Sun al., 2014; Nam al., 2019), where each object is represented by single instance associated with multiple class labels (Zhang & Zhou, 2014; Liu et al., 2022; Hang & Zhang, 2022). The goal of multi- label learning is to build proper classification models for objects assigned with multiple class labels simultancously. In fact, multi-label scenarios widely exist in various real- word applications, such as text categorization (Schapire Singer, 2000; Xun et al., 2020; Rubin al., 2012), multi- media content annotation (Boutell et al., 2004; Cabral et al., 2011; Wu et al., 2014; You et al., 2020), bioinformatics (Barutçuoglu et al., 2006; Cesa- Bianchi et al., 2012; Chen et al., 2017) and other fields (Yu et al., 2005). Despite im- pressive advances in algorithms for multi-label learning, the theoretical analysis of generalization is still in its infancy.
Commonly used evaluation metrics in multi-label learning all involve base loss functions, and the theoretical guarantees of multi-label learning of- ten rely on the properties of base loss functions. Some recent theoretical works have used the Lip- schitz continuity of base loss functions to prove the generalization bounds for multi-label learning, but the impact of the smoothness of base loss func- tions on the generalization bounds is completely unknown. In an attempt to make up for this gap in the generalization theory of multi-label learn- ing, we develop some novel vector-contraction inequalities for smooth base loss functions and derive tight generalization bounds with no depen- dency the number of labels, up logarith- mic terms. We then exploit local Rademacher complexity to develop some novel local vector- contraction inequalities for smooth base loss func- tions, which induce generalization bounds with a tighter dependency on the number of labels and a faster convergence rate with respect to the num- ber of examples. In addition, we derive tight gen- eralization bounds with no dependency on the number of labels, up to logarithmic terms, for Averaeee AUC by exploiting the Lipschitz continuity and smoothness of base loss functions, respectively. Our state-of-the-ar theoretical re- sults provide general theoretical guarantees for the generalization of multi-label learning.
Some recent theoretical works have made preliminary explo- rations into the generalization of multi-label learning, and have made some progress in the reduction of the dependency of the generalization bounds on the number of labels c and the explicit introduction of label correlations in the general- ization analysis (Wu & Zhu, 2020; Wu al., 2021a;b; Zhang & Zhang, 2024a). However, from the perspective of learning theory, in some aspects, the generalization performance of multi-label learning is still completely unknown. These as- pects that need to be explored include: 1) the establishment of faster convergence rates with respect to the number of ex- amples n of the generalization bounds, and 2) the impact of the smoothness of base losses on the generalization bounds. First, existing multi-label learning guarantees are centered around the concepts of Rademacher complexities (Bartlett & Mendelson, 2002; Koltchinski & Panchenko, 2002), and the fastest convergence rate of the generalization bounds in- duced by Rademacher complexity is of the order Ö(1/Vm).
1. Introduction
The analysis based on local Rademacher complexity is ca- pable producing bounds with faster convergence rates than those obtained by Rademacher complexity (Bartlett et al., 2005; Koltchinskii, 2006), but it has not been well explored in multi-label learning. Hence, the development of general theoretical tools that can induce generalization bounds with faster convergence rates with respect to n is a crucial open problem in the theory of multi-label learning. Second, although evaluation metrics with Lipschitz base losses have been extensively studied in existing theoretical work of multi-label learning, the bounds for evaluation met-
Multi-label learning has attracted significant attention due to its ability to model real-world objects with rich semantics
'School Cyher Science and Engincering, Southeast Univer- sity. Nanjing 210096, China "Key Laboratory of Computer Net- work and Information Integration (Southeast University), Ministry of Education, China "Scoool of Computer Science and Engineer- ing, Southeast University, Nanjing 210096, China. Correspon- dence to: Min-Ling Zhang Zchanggl@@assccc @cc..cdu.c.>
Proceedings of the 4nnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 20255 by the author(s).

---

Tight and Fast Bounds for Multi-Label Learning
ries with smooth base losses remain completely unexplored, while the squared loss, representative of smooth base losses, is widely used by many multi-label learning meth- ods (Huang et al., 2015; 2016; 2018; Weng et al., 2020; Yu & Zhang, 2022). Hence, generalization analysis is needed to provide general theoretical guarantees for multi-label learning methods with smooth base losses.
chitz loss in (Zhang & Zhang, 2024a) by ve factor.
Wu et al. (2021b) derived a (llog(nc//me /no) bound for Coo Lipschitz loss with norm regularized kernel classes and the additional assumption that the regularizer is o-strongly con- vex. Zhang & Zhang (2024a) derived a ((1/v bound for so Lipschitz loss, which decouples the relationship among different components. In addition, Yu al. (2014) obtained ((1/vn) bound for trace norm regularized linear func- tion classes for the decomposable loss. Xu et al. (2016) used the local Rademacher complexity to derive a ((1/n) bound for trace norm regularized linear function classes with the assumption that the singular values of the weight matrix decay exponentially. Busa-Fekete et al. (2022) de- rived Õ(1/n) bounds for Hamming loss with KNN under sparsity, margin and smoothness assumptions and sharp bounds for Precision @x under margin and smoothness as- sumptions. Wu et al. (2023) obtained O(1/vT) /r) bounds for Macro-Averaged AUC and gave thorough discussions about its relationships with the label-wise class imbalance. Here we derive sharp ((1/n) bounds for smooth base losses by exploiting local Rademacher complexity.
In this paper, we derive tight bounds with no dependency on and faster convergence rate w.r.t. n for multi-label learning, which connects the smoothness of base losses with the tighter and faster bounds. In addition, we improve the dependency of the bounds on c to be independent for Macro- Averaged AUC both under Lipschitz and smooth conditions of base losses. Our theoretical analysis induces tighter and faster bounds and reveals the impact of smooth base losses on generalization. Major contributions of the paper include:
We develop novel vector-contraction inequalities for smooth base losses, which induces tight bounds with no dependency on and provides general theoretical guar- antees for multi-label learning methods with smooth base losses.
3. Preliminaries
We develop novel local vector-contractin inequal- ities for smooth base losses, which exploits local Rademacher complexity and can induce bounds with no dependency on e and faster rate w.r.t. n.
Let [n] := {1.....n) for any natural number n. In the context of multi-label learning, given a dataset D ((m1,y)),- y..,... ( Un)) with n examples which are iden- tically and independently distributed (i.i..) from a proba- bility distribution P on X x V. where X' S Rd denotes the d-dimensional input space and y denotes the label space with c class labels, æ E X, y E Y S (-1,, +1]. i.e., each y (Vi...., Me) is binary vector and y/ 1 (リj 1) denotes that the j-th label is relevant (irrelevant). j E [c]. Multi-label learning aims to learn a multi-label prediction function h E H X + +11 which assigns each instance with set of relevant labels.
We derive tight bounds with no dependency on for Macro-Averaged AUC with both Lipschitz and smooth base losses.
2. Related Work
We introduce the related work on generalization analysis for multi-label learning. Wu & Zhu (2020) first showed that one obtain bounds of order O(c/ /n) for multi-label learning with the typical vector-contraction inequality (Mau- rer, 2016) (i.e., for &2 Lipschitz losses), which drew on the analysis of the relationship between the expectations of sev- eral evaluation metrics in (Dembczynski et al., 2010; 2012). Wu & Zhu (2020); Wu et al. (2021a) showed that the order of the bounds for Subset, Hamming and reweighted con- vex surrogate univariate loss can be improved to ((ve/n) when preserving the coupling among different components for kernel classes under the assumption of & Lipschitz loss. Liu et al. (2018) also obtained a O( (vee/n) bound for the dual set multi-label learning with the margin loss and kernel function classes. Zhang & Zhang (2024a) developed novel vector-contracee inequality for lg Lipschitz loss and de- rived ((ve/)) bound, which decouples the relationship among different components. Here we derive Õ(1 /n) bounds for several evaluation metrics with smooth base losses, which improves the ((ve/n) bounds for lg Lips-
3.1. Multi-Label Learning
A common strategy to solving multi-label learning is to learn a vector-valued function f = (f1,...,,f)) : + Re and derive the prediction function by a thresholding function which divides the label space into relevant and irrelevant label sets. We follow some definitions and notations in (Zhang & Zhang, 2024a). The general form of the prediction function for each label is fx) = (w,, ()())), where Φj represents a nonlinea mapping. The function class of the mubti-label learning is defined as follows:
F= fz+ + f(x) (zx = (fi(z)....... fc(x)),
fy(x)) = w.] (y(x), xc X, E [c]
w = (wi...., w.) E dxe a(w) < A (1)
B(,,()) S $AAA 0, 0,1000 0}.
2

---

Tight and Fast Bounds for Multi-Label Learning
where a represents a functional that constrains weights, 3 represents a functional that constrains nonlinear mappings.
where X = {a, yj +1, E [n]] (X = { زز
1 (nl]) corresponds to the set of test instances that relevant (irrelevant) to the j-th label. The expected risk w.r.t. Macro-Averaged AUC is defined as R(f)) = (f()
Here we give some concrete examples as an explanation of the function class. For example, the DNN-based method named CLIF (Hang & Zhang, 2022), which proposes to learn label semantics and representations with specific dis- criminative properties for each class label in a collaborative way, can be expressed in the function class as Φ2(x))
3.2. Related Evaluation Metries
Many evaluation metries are developed to measure the gen- eralization performance of different multi-label learning methods. Here we focus on commonly used evaluation metrics, i... Hamming loss, Subset loss, Ranking loss and Macro-Averaged AUC. However, the corresponding losses in the above metrics are typically the 0-1 loss, which is hard to handle in practice. Hence, one usually consider their surrogate losses, which are defined as follows:
TRELU (Ws Ru (Waz) o Ssig (WsbWW Hi),, the la- ReLu bel embeddings (b) == Re RELU (2)),) where À denote the normalized adjacency matrix with self- connections, Y is the node feature matrix of the label graph, RBLU is the ReLU activation, Ssig is the sigmoid activa- tion, @ is the Hadamard product, W; are the parameter metrices, i E [5]. In addition, a class of multi-label meth- ods based on the strategy of label-specific representation (Zhang& & Zhang, 2024b), which facilitates the discrimina- tion of each class label by tailoring its own representations, can be formalized in our function class. For example, the wrapped label-specific representation method (Yu & Zhang, 2022), which presents a kerneiized Lasso-based framework with the constraint of pairwise label correlations for each class label, can be expressed in our function class, where fy is the kernelized linear model and the constraint auw) is ||w S A for any j E [c]. and each label also has the property of sharing which is reflected by the additionally introduced constraint (1 sy,)u,," w, S T, where 8/i is the cosine similarity between labels yy and ys- Besides, the function class here is applicable to the typical Binary Relevance methods for multi-label learning, where different methods correspond different nonlinear mappings Φ--
Hamming Loss: E (f(x), y) = = ビÿ= 4 (f)(z)),),
where l is the base convex surrogate loss.
Subset Loss: (s((((), y) = maxjetd (6 (J} (z),,)))
Ranking Loss:
(n(f(z). v) |
E - PEY 9EY
ΣE
where Y+ (Y-) denotes the relevant (irrelevant) label index
set induced by y, and |- denotes the cardinality of a set.
The induced surrogate loss for Macro-Averaged AUC:
1 Σ l (f,(z))) - fz(o))
(f v) =
(3)
where æ; (x)) corresponds to the instances that are relevant (irrelevant) to the j-th label.
For any vector-valued function f X + RR the predic- tion quality on the example is measured by a loss function é: IR x {-1, +1] + R.,. The goal of learning is to find a hypothesis f E F with good generalization performance from the dataset D by optimizing the loss f. We define the loss function space as L = {((f(x)) y) : f E F). The generalization performance is measured by the ex- pected risk: R(((f)) = (( w)]. We denote the empirical risk w.r.t the dataset D as (e(f)) = 1 >E_, (x;))))))) For simplicity, we slightly abuse R(f) and RD(f) to represent R(E(F)) and (D((())).
The base surrogate loss functions l, involved in the above commonly used evaluation metries can be various popu- lar forms, such as Lipschitz loss functions with bounded derivative (including the hinge, margin, absolute-value, and logistic loss, etc) or smooth loss functions with the second derivative is bounded (including the squared, squared hinge, squared margin (Li et al., 2018) and smoothed ramp (Cortes et al., 2021) loss, etc). In this paper, we use l to refer to the collective name for evaluation metrics such as Hamming loss, subset loss, and Ranking loss, etc, while 4, is used specifically to refer to the base loss functions involved in the above commonly used evaluation metrics.
The above definitions apply to Hamming, Subset and Rank- ing losses. However, the corresponding risk for Macro- Averaged AUC needs to be additionally defined since it involves the pairwise loss. The empirical risk w.r.t. Macro- Averaged AUC is defined as follows:
3.3. Related Complexity Measures
Here we introduce the related complexity measures in- volved in theoretical results. The Rademacher and local Rademacher complexity are used to perform generalization analysis for multi-label learning.
RD)
(2)
1
Σ x a(Ex
Σ
faz2 -
Definition 3.1 (Rademacher complexity). Let F be a class of real-valued functions mapping from X' to TR. Let D =
Xj
3

---

Tight and Fast Bounds for Multi-Label Learning
{o11..... Fnf be set with n i.i.d. samples. The empirical
Definition 3.4 (Local Rademacher complexity). For any >> 0, the expected local Rademacher complexity of the local loss function space L associated with real-valued function class F is defined by
Rademacher complexity over F is defined by
RD(F) = -R sup FEF
Gf (a:4 t=1
RD(CT) = (R(((((()))))) IEE F.((((( (r)),
where E1....,, En are i.i.d. Rademacher random variables. In addition, we define the worst-case Rademacher complexity as Rr (F) suppex" (FF.
where = ((E
4. Tighter Bounds for Smooth Base Losses
The vector-valued function class F of multi-label learn- ing makes traditional analysis methods developed for the Rademacher complexity of scalar-valued function class in- valid. The typical vector-contraction inequality in (Maurer, 2016) shows that the Rademacher complexity of the class F composited with an & Lipschitz function Á can be bounded by the maximum Rademacher complexity of the restrictions of the function class F along each coordinate and a factor c, and the induced bounds are not tight enough (Zhang & Zhang. 2024a). Therefore, we need new theoretical methods to convert the Rademacher complexity of loss function space into the Rademacher complexity of a tractable scalar- valued function class for multi-label learning, especially for smooth base losses. The Rademacher complexity can be bounded by other scale-sensitive complexity measures, e.g. covering number and fat-shattering dimension (Srebro et al., 2010; Zhang & Zhang, 2023).
In this section, we first introduce the assumptions used in the generalization analysis, i.e., the assumption about the boundedness of functions and the assumption about the
smoothness of base loss functions. Then, we develop some novel vector-contraction inequality for the Rademacher com- plexity of the loss function space L with smooth base loss functions. Finally, with these novel vector-contraction in- equalities, we derive tight bounds for the general function class of multi-label learning with no dependency on the number of labels, up to logarithmic terms, which achieve the state of the art. The proof sketches and detailed proofs of the theoretical results in this paper are provided in the appendix.
Assumption 4.1. Assume that the loss function and the components of the vector-valued function are bounded: ((--) S M, 1f,(-) < B for E [c] where M, B > 0 are constants.
Definition 3.2 (Covering number). Let FF be a class of veal-valued functions mapping from X' TR. Let = (#),.... } be a set with n i.idd samples. For any O and p 2 1, the empirical lp norm covering num- ber (e, D) w.r.t. D is defined as the minimal number m of a collection of vectors v ...., " E R" such that (o) is the i-th component of the vector w²)
Assumption 4.1 is pretty mild assumption. When we con- sider the function class (1) for multi-label learning, we will further use the constraint on weights (1:w,l S A) and the constraint on nonlinear mappings (110) (a>) ]| S A) to replace the boundedness of the components of f. i.e., B : AA. When we analyze the generalization of the specific methods models, will further have (z))] S |||=||| (Ø, is p- Lipschitz continuous) to take into account the differences of various methods or models. The differences in the Lipschitz constants between deep and shallow models are particularly obvious. The differences in the generalization of various methods or models are further reflected in the corresponding Lipschitz constants p. This work aims explore capacity- based generalization bounds for smooth base loss functions and derive bounds that are weaker dependent on the number of labels, thereby providing general and effective thcoretical guarantees for multi-label learning methods with smooth base loss functions. Therefore, here we only make general assumptions and do not specify specific methods or models, which is similar Zhang & Zhang (2024a).
1
n
Σ 1f (xx:) - u/(P) -o( SC
In this case, we call (o',..., . u an (e, -oveer of F w.I.t. D. We also denote Npple F,n) = supp Cupp-NN(e,22 Np(e,F, D). Definition 3.3 (Fat-shattering dimension). Let F be a class of real-valued functions mapping from X' to R. We define the fat-shattering dimension (F) scale 0 as the largest p E N such that there exist p points .i,...,,e Tpp E X' and witnesses Spp E R satisfying: for any 51, SI,...,5, E [-1,+1} there exists f E F with
8/ (f(x.) - st) 2 e, Vi = I.....p
Assumption 4.2. Assume that the base loss functions 6 involved in the commonly used evaluation metries are 7- smooth, that is:
We also use the local Rademacher complexity to derive sharper bounds with a faster convergence rate with respect to the number of examples for lubti-label learning methods with smooth base loss functions.
[+((s) - V(o(1) S 7/s t).

---

Tight and Fast Bounds for Multi-Label Learning
Assumption 4.2 is a relatively mild condition. The squared, the squared hinge, the squared margin (Li al., 2018) and the smoothed ramp (Cortes et al., 2021) losses all satisfy Assumption 4.2, especially the squared loss, which is widely used by many multi-label learning methods (Huang et al., 2015; 2016; 2018; Weng et al., 2020; Yu & Zhang, 2022).
and the following holds for Ranking loss with smooth base losses and any I E F:F
log A
24M
768
3M +3M R(f) +3M
+
2n
Vn
VnM
(1 + logz (192en 2 MM
In
We then show that the smoothness of base loss functions combined with the projection operator can induce novel tight cectrr-contraction inequalities. The projection operators are defined as Pj I + IK for any E [c] which project the c-dimensional vector onto the j-th coordinate. The projection function class is defined as P(F) = ((.z)) pf(((x)) (f(()) = fz), FF x) With the above definitions, we develop some novel vector-contraction inequalities for smooth base loss functions, which show that the Rademacher complexities of loss function spaces can be bounded by the worst-case Rademacher complexity of the projection function class:
VBB
Remark 4.5. The term Red (P(F) S B//ne in Lemma 4.3, which makes the Rademacher complexity RD (Cn), RD(Cs) and RD actually independent on c, up to logarithmic terms, and results in tighter bounds than the O(e/ym) bounds (Wu & Zhu, 2020; Wu et al., 2021a) and O(Ve/ bounds (Liu et al., 2018: Wu et al., 2021a; Zhang & Zhang, 2024a). Evaluation metrics with Lipschitz base loss functions have been extensively studied in previ- ous work of multi-labe, learning. Wu & Zhu (2020) and Wu et al. (2021a) derived the bounds with linear dependency e for & norm Lipsehitz losses, which comes from the typical vector-contraction lemma in (Maurer, 2016). and showed that the dependency of the bounds on c can be im- proved to square-root by preserving the coupling among different components (i.e., with the constraint ||w||| s A). Zhang & Zhang (2024a) improved the dependency of the bounds on from linear to square-root in the decoupling case for lg norm Lipschitz losses. Generalization bounds for evaluation metrics with smooth base losses are still com- pletely unexplored. Our theoretical results here show that the dependency of the bounds in (Zhang & Zhang, 2024a) on c can be improved from square-root to be independent by exploiting the smoothness of base loss functions, up to loga- rithmic terms, in the decoupling case. Our tight bounds with dependency on c, up to logarithmic terms, can provide general theoretical guarantees for multi- learning meth- ods with smooth base loss functions (Huang et al., 2015; 2016; 2018; Weng et al., 2020; Yu& & Zhang, 2022).
Lemma 4.3. Let F be the class of multi-label learning defined by (1). Let Assumptions 4.1 and 4.2 hold. Given a dataset D of size Then, we have
12M
RD(CH) S Vn
+ 192V Rnc (P(FF)
VnM VBB )
(1 + 1ogg (48en 2 MM) In
12M
RD(ss) - vn
+ M Rm((((F)) (P(F))x
M
VnM
(1 + (00cn
22 In
v7B
12M S
(Cn)
384
McyM 1-38//30yMMB (P(F))x
Vn
(1 + log, (192en 2 M) In VnM
VAB
where RD)(H)) RD((s) and (D() are the empirical Rademacher complexities of Hamming, Subset and Ranking loss space, respectively, and Rnc(P(F)) is the worst-case Rademacher complexity of the projection function class.
Remark 4.6. Zhang & Zhang (2024a) improved the depen- dency of the bounds on e from linear to square-root in the decoupling case for &2 norm Lipschitz losses. In fact, the results in Lemma 3.6 and Theorem 3.7 in (Zhang & Zhang, 2024a) require the introduction of an additional ve factorr because the third step of the proof of Lemma 3.6 in (Zhang & Zhang, 2024a) ignores the ve factor in the radius of the empirical le cover of P(F), i.e., the process below equation (10) in the proof of Lemma 3.6 in (Zhang & Zhang, 2024a) should be modified as follows:
Then, we can derive the following tight bounds for multi- label learning with smooth base loss functions:
Theorem 4.4. Let F be the class of multi-label learning defined by (1). Let Assumptions 4. I and 4.2 hold. Given a dataset D of size n. Then, for any 0 < 8 < 1, with probability at least 1- ō, the following holds for Hamming and Subset loss with smooth base losses and any f E F:
RD(
R(f) (f) + 3M
log 2 1
24M
+
384/3yMB
x
S inf asu
4a +
Vū Jo
12 /'M
/
NlogN2( E uVe"
P(F), x D)de
2n
Vn
Vn
VnM
4a + 48 Vew./Rno logg: 1 -'
(1 + Logg,(48::)) 2e18enn222A00 MM) In
< inf a>0
VTB"
5

---

Tight and Fast Bounds for Multi-Label Learning
which will cause the bounds in Lemma 3.6 and Theorem 3.7 to be square-root dependent c. We find that the square- root dependency of the bound in (Zhang & Zhang, 2024a) cis inevitable for Ey norm Lipschitz losses, which essentially comes from the /c factor in the radius of the empirical & cover of the projection function class. We also find that the smoothness of the base loss function can eliminate the v factor in the radius of the empirical l2 cover of the projection function class, that the tight bound with dependency on c, up to logarithmic terms, can be derived. In addition, the method based on Sudakov's minoration used in (Zhang & Zhang, 2024a) to upper bound the &g norm covering number of the projection function class is no longer applicable here. According to the above key points and proof ideas, for the bound with a square-root dependency on for lg Lipschitz loss in (Zhang & Zhang, 2024a), we consider the smoothness of the base loss and improve the bound by factor of vr. In addition, the smoothness of the base loss combined with the local loss function space allows the development of novel local vector-contraction inequalities, which can induce bounds that not only have a faster convergence rate but also have a weaker dependency on c. Although for & Lipschitz loss, the bounds in (Zhang & Zhang, 2024a) is only improved by factor of vc. they are still the tightest results in multi-label learning with & Lipschitz loss. In addition, for Hamming loss, its Lipschitz constant can induce the tight bounds with no dependency on C.
2021). Combined with the definition of the Rademacher complexity, we define the local Rademacher complexity for multi-label learning follows:
Definition 5.1 (Local Rademacher complexity for multi-la- bel learning). Let F. be the class of multi-label learning defined by (1). For any r > O, the local function class of multi-label learning restricted by a functional is defined as:
f + f(x) : f E F, Ro(((f)) sr),
= where = ((f y.). The local loss function space corresponding J is defined as L := (f(f(z). y) : E F. The expected local Rademacher complexity of the local loss function space f associated with the local multi-label learning class F is defined by
RD = (D f F'))
This means that a much smaller class L" consisting of the functions f with small error can yield sharper generaliza- tion bounds with a faster convergence rate.
With the assumption about the smoothness of base loss functions, we show that the local Rademacher complex- ity of the local loss function space L" can be bounded by the worst-case Rademacher complexity of the projection function class. We develop the following novel local vector- contraction inequalities:
Lemma 5.2. Let FF be the class of multi-label learning defined by (1). Let Assumptions 4.1 and 4.2 hold. Given a dataset D of size n. Then, we have
5. Faster Bounds for Smooth Base Losses
48 48/33r(B 1) vn
In this section, we first introduce the local Rademacher complexity used in the generalization analysis for multi- label learning. Then, we develop some novel local vector- contraction inequality for the Rademacher complexity of the local loss function space L" with smooth base loss functions. Finally, with these novel vector-contraction inequalities, we derive sharper bounds for the general function class of multi- label learning with not only no dependency the number of labels, up to logarithmic terms, but also faster convergence rate with respect to the number of examples, which achieve the state of the art.
RD
+ Rene
(1+ 4ogg (4Bn
(o
48 48 B + 1) + 4 Roy (P(F))
RD(C)) -
vn
(1+ 4log (4Bn () loga(VBB))
96 96 RD(CF) S
B + 1) + / (P((F))))(((F))
vn
(1 + 4loga (4 logz((BB).
In fact, the Rademacher complexity considers the worst-case estimates of the complexity of the function class, it ignores the fact that the functions selected by the algorithm have small error, and they are only favorable small subset of the entire function class. As result, the best convergence rate that can be obtained via the Rademacher complexity is at least of order O(1/ /n). The local Rademacher complexity considers the Rademacher complexity of a small subset of the function class and is more reasonable as a complexity measure that yields faster convergence rates (Bartlett al., 2005; Srebro et al., 2010; Reeve& & Kaban, 2020; Li & Liu,
where RD RD(('s) and RD(CR) are the empirical local Rademacher complexities of local Hamming, Sub- set and Ranking loss function spaces, respectively, and Re (P(F)) the worst-case Rademacher complexity of the projection function class.
The challenge in using local Rademacher complexity im- prove existing learning rates is to find the optimal radius that trades off the size of the subset we select and the asso- ciated complexity, which can be reduced to the calculation of the fixed point of a sub-root function. We introduce the definition and properties of the sub-root function as follows:
6

---

Tight and Fast Bounds for Multi-Label Learning
Definition 5.3 (Sub-root function). A function t [0, oo) + [0,, oc) is sub-root if and only if it is non-decreasing and
the loss function space associated with the vector-valued prediction function class in (Wu & Zhu, 2020; Wu et al., 202 Zhang & Zhang, 2024a) leads to the improvement of the dependency on the number of labels by factor of Vć. Hence, under these strong assumptions, the bound in (Xu et al., 2016) is independent of the number of labels. On the other hand, the faster convergence rate O(1/n) of the bound in (Xu et al., 2016) comes from the assumption that the singular values of the weight matrix decay exponentially. It is not obvious to satisfy such an assumption and requires careful design of the algorithm. Hence, the bound in (Xu et al., 2016) is not general and is heavily specific to their pro- posed algorithm. Our bounds here are not only independent of the number of labels, but also have a faster convergence rate. The only assumption is that the base loss functions involved in evaluation metrics are smooth, which is very mild in multi-label learning since many multi-label learning methods use smooth base loss functions (Huang et al., 2015; 2016; 2018; Weng et al., 2020; Yu & Zhang, 2022). Hence, our bounds can provide general theoretical guarantees for learning methods and datasets, and also explain the good generalization performance of multi- label learning methods with smooth base loss functions.
the function + (5()// vr is non-increasing for > O.
Lemma 5.4 (Lemma 3.2 in (Bartlett et al., 2005)), If is non-trivial sub-root function, then it is continuous on [0, oo), and the equation eb(r) = r has a unique positive solution r", which is known as the fixed point of tb. Moreover, for any r > O, it holds that r > (p(r) if and only ifr* ST.
Then, with these novel local rector-contraction inequalities above and the properties of sub-root functions, we can derive the following sharper bounds for multi-labed learning with smooth base loss functions:
Theorem 5.5. Let F be the class of multi-lubel learning defined by (1), Let Assumptions 4.1 and 4.2 hold. Given a dataset D of size n. Then, for any 0- < 5 < 1, with probability at least 1 - 6, the following holds for Hamming and Subset loss with smooth base losses and any f E F:
R(f) 22RD(f)+ + bM 1 - 6 6log logn) 3. 4.48aa ary
n2
n
(B (B+1) (1+
(1+ + 4 ( (4Bn à loga VTB))
Remark 5.7. Busa-Fekete et al. (2022) also derived tight bounds with logarithmic dependency on c for Hamming loss with KNN under the smoothness assumption of the regression function and multi-label margin and sparsity as- sumptions and also derived tight bounds with logarithmic dependency on e for Precision k under the margin condi- tion and the smoothness assumption. The margin condition ensures that the obtained bounds with a faster convergence rate. In our work, the local loss function space is the key to obtaining bounds with a faster convergence rate. The smoothness condition with respect to the & norm in (Busa- Fekete et al., 2022) is a variant of Holder-continuity, which is weaker than the standard smoothness condition. We also find that the fox norm has a positive effect on obtaining tight bound with a weaker dependency on c, i.c., tight bounds with a logarithmic dependency on e can be derived for to Lipschitz losses. However, how to improve the convergence rate of the bounds for Lipschitz losses is still open prob- lem, which we will further explore in future work.
and the following holds for Ranking loss with smooth base losses and any f E F:
+ bM } 6 log log
3- 9-962ar ary
R(f) (f)((f)
n
n
(B+ 1)2 (1 + (1+ 4 (1Bn3 logg((
where a = 106, b = 48.
Remark 5.6. The term (P S B/Vnc in Lemma 5.2, which makes the local Rademacher complexity (Fz)) (CT) and (CR) actually independent on e, up to logarithmic terms, and results in sharper bounds than the Õ(1/vn) bounds in Theorem 4.4 with a faster con- vergence rate ((Lnn). Theorem 5.5 is the most advanced theoretical result for multi-label learning so far. Although Xu et al. (2016) also derived generalization bound of order ((1/n) by using the local Rademacher complexity, this bound is accompanied by the trace norm regularized linear function classes and the assumption that the singular values of the weight matrix decay exponentially. These strong as- sumptions lead to their bound being completely independent of the number of labels. On the one hand, the trace norm regularizer actually preserves the coupling among different components. Wu & Zhu (2020) first revealed that preserv- ing the coupling can improve the dependency of the bound on the number of labels by factor of Ve in multi-label learning. Zhang& & Zhang (2024a) revealed that the trace norm regularizer actually corresponds to the case of pre- serving the coupling. In addition, the analysis of the linear prediction function class in (Xu et al., 2016) rather than
6. Tighter Bounds for Macro-Averaged AUC
In this section, we derive some tight bounds for Macro- Averaged AUC. Specifically, we first exploit the Lips- chitz continuity of base losses develop a novel vector- contraction inequality, which can induce tight bounds with no dependency on for Macro-Averaged AUC. Then, we exploit the smoothness of base losses to develop novel vector-contraction inequality, which can also induce tight bounds with no dependency on c for Macro- Aaerro-veeraee AUC. These bounds achieve the state of the art and also reveal
7

---

Tight and Fast Bounds for Multi-Label Learning
the relationship between Macro-Averaged AUC and class- imbalance (Wu et al., 2023; Zhang & Zhang, 2024a).
Theorem 6.3. Let F be the class of malti-label learning defined by (1). Let Assumptions 4. and 6. I hold. Given dataset D of size n. Then, for Macro-Averaged AUC with Lipschitz base losses, for any 0 < 8 < 1, with probability at least 1 - 6, the following holds for any f F:
We first introduce the following assumption about the Lips- chitz continuity with respect to the foe norm:
Assumption 6.1. Assume that the loss function & is p- Lipschitz continuous w.r.t. the too norm, that is:
R(f) <RD(f)+ 24v2M
In
384 2p x
+ +18M
V
+
[ ((f) ) s f1( f'(x))
VTo
To
vro
M Mvro
where p > 0. ||4|| - max |4/1 for t = (41,..,,6)). te).
(1 + logg (erreepp)) p?)
In
pB
The Lipschitz continuity with respect to the Eoo norm has been considered in several literature (Foster& & Rakhlin, 2019; Lei et al., 2019; Wu et al., 202 Zhang & Zhang, 2024a). Zhang & Zhang (2024a) showed that when the base loss functions are p -Lipschitz continuous, the induced surrogate loss for Macro-Averaged AUC in Subsection 3.2 is p-Lipschitz continuous. Next, we exploit the Lipschitz continuity of base loss functions to develop a novel vector- contraction inequality for 2 norm Lipschitz loss:
where ro n min Pj, (1 - p2)}
Remark 6.4. We define the empirical Rademacher complex- ity of a loss function space associated with the lulti-label learning class F over the set of i.i.d disjoint positive and negative sample pairs for the j-th label RD, (Cas)
Ee [supfer ry E Gill (I) fa by using the U-process technique, we find that the gener- alization error can be bounded by RD, (CM). Since ry is random, we incorporate an additional Chernoff-type argu- ment to obtain a bound that does not involve any random quantities, and upper bound the generalization error by RDD S 12M + 192p (o-ooggrrrrre" -In Myrro) ). vro
Lemma 6.2. Let F be the class of multi-label learning defined by (1), Let Assumptions 4.1 I and 6.1 hold. Given a dataset D of size n. Then, we have
12M Rt((C) S Vn
vro
+ 96p (P((F)
Remark 6.5. The ((1/vro) bound with no dependency on in Theorem 6.3 improve the Ö(Ve/ro) bound in (Zhang & Zhang, 2024a) by factor of Vc. When class-imbalance is more serious, ro will be smaller, the bound for Macro- Averaged AUC will be looser. The ((vefro) bound in (Zhang & Zhang, 2024a) is more likely to be vacuous (i.e., > 1)) since class-imbalance makes e >> ro more likely to occur. Hence, the ((L//ro) bound here, rather than the Ö(Vc/ a/ro) bound in (Zhang & Zhang, 2024a), can provide a general theoretical guarantee for Macro-Average AUC.
M Mvn pB
(1 + 11+1
2 6p))
In
where Ren (P(F) is the worst-case Rademacher complex- ity of the projection function class.
We follow the definitions and notations of Macro-Averaged AUC in (Zhang& & Zhang, 2024a). Let Pj be the probability that the samples are relevant to the j-th label. DJ denotes the conditional distribution of the samples over X' given that the samples are relevant to the j-th label, and Dj denotes the conditional distribution of the samples over X given that the samples are irrelevant to the j-th label. We denote xx and |X,|| in (2) as 8j and ty. 8, + t2 = n for any E [c]. and denote the number of disjoint positive and negative sample pairs for the j-th label rj min(sj, }. We construct the set of positive and negative sample pairs (a?" )
Then, we develop novel contorconttacttion inequality for Macro-Averaged AUC with smooth base loss functions:
Lemma 6.6. Let F be the class of multi-label learning defined by (1). Let Assumptions 4.1 and 4.2 hold. Given dataset D size n. Then, we have
12M Rp((M) S Vn
+ 192 3ey M (P(F))x
) (i E (ry]) by matching the samples from the set of the samples that are relevant to the j-th label with the samples from the set of the samples that are irrelevant to the j-th label until one of the sets of the positive samples and the negative samples exhausts its available samples for selection. We denote the set of i.i.d disjoint positive and negative sample pairs for the j-th class label as Dj. and
VnM
+ logg (2)M)
In
VTB
where (D()))) is the empirical Rademacher complexities of the loss function space of the induced surrogate loss for Macro-Averaged AUC, and (p)(P(F)) is the worst-case Rademacher complexity of the projection function class.
[Dyl= -r. ry. Then, with these definitions and permutations in U-process (Clémençon et al., 2008; Zhang& & Zhang, 2024a), we derive the tight bound for Macro- Averaged AUC with Lipschitz base losses as follows:
With the above vector inequality, we derive tight bound for Macro-Averaged AUC with smooth base losses:
8

---

Tight and Fast Bounds for Multi-Label Learning
Theorem 6.7. Let F be the class of multi-label learning defined by (1). Let Assumptions 4.1 and 4.2 hold. Given dataset D of size n. Then, for any 0 < 5 < 1, with probability at least 1- - 6, the following holds for Macro- Averaged AUC with smooth base losses and any f E F:
to introduce sparsity assumptions into the analysis, thereby inducing bounds that are weakly dependent on the sparsity rate and the number of key labels.
Our theoretical results do not cover the case where the base loss is the cross-entropy loss, mainly because the cross- entropy loss is not bounded. On the smoothness of the cross-entropy loss, when the model is a linear classifier, the smoothness of the cross-entropy loss can be achieved by the boundedness of the input, but from the perspective of model capacity, such a result is not general. The function class here involves general functions (i.e.. nonlinear map- pings Qz), so for nonlinear models, the smoothness of the cross-entropy loss involves not only the boundedness of the first-order gradient of the model function but also the bound- edness of the second-order derivative. For deep networks, changes in parameters may cause drastic changes in the second-order derivative, resulting in the norm of the second- order derivative being unbounded. Hence, the smoothness of the cross-entropy is often difficult to hold. However, the Lipschitz continuity of the cross-entropy is often estab- lished, and the boundedness of the gradient of the model function is guaranteed by various strategies in practice, such as input normalization, weight initialization, gradient clip- ping. and regularization. This implies the need to develop new theories and analytical methods for unbounded base losses. Under the new theoretical analysis method, tight bounds with no dependency on e for cross-entropy loss can be obtained using its Lipschitz continuity, but improving the convergence rate of its bound with respect to the number of examples is still urgent open problem to be solved. In the future, we will further study the bounds with faster convergence rate for unbounded and Lipschitz base losses.
24/2M
In
R(f) (f=(f) +
+
+18M1
8
+
Vro
ro
768/67MB
VroM
(1 + logz (48erffe7) In
vTB )
VTo
where ro- = n min Pj. (1inn(1-p55)
Remark 6.8. We derive tight ((1//ro) bounds for Macro- Averaged AUC by exploiting both Lipschitz continuity and smoothness of base losses. Wu et al. (2023) also obtained bounds with no dependency on è for Macro-Averaged AUC by their proposed new McDiarmid-type inequality, and pro- vided thorough analysis on its relationships with the label- wise class-imbalance. However, we focus studying the impact of the properties of base losses on the bound, and are committed to developing new analysis methods and theo- retical tools under Lipschitz and smooth conditions of base losses to reduce the dependency of the bound on c.
7. Discussion
When there is some type of label correlation between the labels of the dataset, the label distribution may satisfy some potential constraints, which may correspond to some addi- tional assumptions such as sparsity assumptions or norm regularization constraints. Therefore, when dealing with these specific problems, we need to introduce some ad- ditional assumptions to adjust our analysis and explicitly introduce these potential label correlations into the general- ization analysis. Different types of label correlations have an important impact on the generalization analysis. How to explicitly introduce them in generalization analysis is a crucial open problem, and we will further explore related work in the future. When dealing with large-scale datasets, in practice, one often consider introducing specific strate- gies in the label space to deal with extremely large number of labels. In generalization analysis, it is shown that intro- ducing effective and general specific strategies is not only an important open problem in theory, but also extremely challenging in practice. Therefore, it is indeed necessary to further introduce effective assumptions to better explic- itly analyze the role of key factors in generalization that can effectively deal with challenging problems with large number of labels and large-scale datasets. In summary, ef- fective analysis for more specific problems requires further explicit introduction of valid assumptions to reveal the im- pact of these tetting-depeneen factors on the bound. For example, for high-dimensional sparse data, one may need
8. Conclusion
In this paper, we develop novel vector-contractionn inequali- ties for smooth base losses, which induces tight Õ(1/ /n) bounds with no dependency on c. We also derive ((1/n) bounds with no dependency on e and faster rate w.r.t. n by exploiting local Rademacher complexity. In addition, we derive tight bounds with no dependency Averaged AUC with both Lipschitz. and smooth base losses.
for Macro-
In future work, we will consider experimental verification from two aspects. On the one hand, verify whether the functions selected by the algorithm have a small error and whether the generalization performance of the small er- ror functions is better. On the other hand, verify whether the smoothness of the model function can be guaranteed by some regularization, and explore which regularization- induced inductive biases are more effective for generaliza- tion in practice. We will also develop new theoretical results to investigate the lower bound for multi-label learning to test whether our bounds here are optimal.

---

Tight and Fast Bounds for Multi-Label Learning
Acknowledgements
Cesa-Bianchi, N., Re, M., and Valentini, G. Synergy of multi-label hierarchical ensembles, data fusion, and cost- sensitive methods for gene functional inference. Machine Learning, 88(1-2):209-2 -411 2012.
The authors wish to thank the anonymous reviewers for their helpful comments and suggestions. This work was supported by the National Science Foundation of China (62225602).
Chen, D.. Xue, Y., Fink, D., Chen, S., and Gomes, C. P. Deep multi-species embedding. In Proceedings of the 26th International Joint Conference Artificial Intel- ligence, number IJCAI 2017, pp. 2017.
Impact Statement
ijcai.org.
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which feel must be specifically highlighted here.
Clémençon, S., Lugosi, G., and Vayatis, N. Ranking and empirical minimization of u-statistics. The Annals of Statistics, 36(2):844 2008.
References
Cortes, C., Mohri, M., and Suresh, A. T. Relative deviation margin bounds. In Proceedings of the 38th International Conference Machine Learning, volume 139, pp. 2122- 2131, 2021.
Anthony, M. and Bartlett, P. L. Neural network learn- ing: Theoretical foundations. cambridge university press, 2009.
Dembezynski, K., Waegeman, W., Cheng, W., and Hüllermeier, E. Regret analysis for performance met- ries in multi-label classification: The case of hamming and subset zero-one loss. In Joint European Confer- ence on Machine Learning and Knowledge Discovery in Databases, volume 6321, pp. 280-295, 2010.
Bartlett, P. L. and Mendelson, Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3:463-482, 2002.
Bartlett, P. I.,, Bousquet, O., and Mendelson, S. Local rademacher complexities. The Annals of Statistics, 33(4): 1497-1537, 2005.
Dembezynski, K., Kotlowski, W., and Hüllermeier, E. Consistent multilabel ranking through univariate losses. arXiv: (:Xiv:200.6440) 2012.
Barutçuoglu, Z., Schapire, E., and Troyanskaya, O. G. Hi- erarchical multi-label prediction of gene function. Bioin- formatics, 22(7):830-88) -33-83,, 2006.
Foster, and Rakhlin, A. Loo vector contraction for rademacher complexity. 1.X1::9911066488111 2019.
Boucheron, S., Lugosi, G., and Massart, P. Concentration Inequalities Nonasymptotic Theory of Independence. Oxford University Press, 2013.
Guermeur, Lp-norm sauer-shelah lemma for margin multi-category classifiers. Journal of Computer and Sys- tem Sciences, 89:450 473, 2017.
Bousquet, O. Concentration inequalities and empirical processes theory applied to the analysis of learning algo- rithms. PhD thesis, École Polytechnique: Department of Applied Mathematics Paris, France, 2002.
Hang. J.-Y. and Zhang, M.-L. Collaborative learning of label semantics and deep label-specific features for multi-label classification. IEEE Transactions on Pattern Analysis and Machine Intelligence, 44(12):9860- 9871, 2022.
Huang, J., Li, G., Huang, Q., and Wu, X. Learning label specific features for multi-label classification. In Aggar- wal, C. C., Zhou, Z., Tuzhilin, A., Xiong, H., and Wu, (eds.), Proceedings of the 15th IEEE International Conference on Data Mining, number ICDM 2015, pp- 181-190, 2015.
Boutell, M. R., Luo, J., Shen, X., and Brown, C. M. Learn- ing multi-label scene classification. Pattern Recognition, 37(9):1577-1771, 2004. 2004.
Busa-Fekete, R., Choi, H., Dembczynski, K., Gentile, C., Reeve, H., and Szörényi, B. Regret bounds for multilabel classification in sparse label regimes. Advances in Neu- ral Information Processing Systems, 35(NeuSIPS 2022), 2022.
Huang, J., Li, G., Huang, Q., and Wu, X. Learning label- specific features and class-dependent labels for multi- label classification. IEEE Transactions on Knowledge and Data Engineering, 28(12)3300-33233 2016.
Cabral, R. S., la Torre, F. D., Costeira, J. P., and Bernardino, A. Matrix completion for lubti-label image classification. Advances in Neural Information Processing Systems, 24 (NIPS 1011)11901111 2011.
Huang, J., Li, G., Huang, Q. and Wu, X. Joint feature selection and classification for multilabel learning. IEEE Transactions on Cybernetics, 48(3):876-88) 2018.
10

---

Tight and Fast Bounds for Multi-Label Learning
Koltchinskii, V. Local rademacher complexities and oracle
Pollard, D. Convergence of stochastic processes. Springer
inequalities in risk minimization. The Annals of Statistics, 34(6):2593-2656, 2006.
Science & Business Media, 2012.
Reeve, H. and Kaban, A. Optimistic bounds for multi- output learning. In Proceedings of the 37th International Conference Machine Learning, number ICML 2020, pp. 8030-8044 2020.
Koltchinskii, V. and Panchenko, D. Empirical margin dis- tributions and bounding the generalization error of com- bined classifiers. The Annals of Statistics, 30(1):1-50, 2002.
Rubin, T. N., Chambers, A., Smyth, P., and Steyvers, M. Statistical topic models for multi-label document classifi- cation. Machine Learning, 88(1-2):157-008, 2012.
Lei, Y., Dogan, U., Zhou, D., and Kloft, M. Data-dependent generalization bounds for multi-class classification. IEEE Transactions on Information Theory, 6555)31995,,, 2019.
Schapire, R. E. and Singer, Y. Boostexter: A boosting- based system for text categorization. Machine Learning, 39(2/3):135-168, 2000.
Lei, Y., Yang. T., Ying. Y., and Zhou, D. Generalization anal- ysis for contrastive representation learning. In Proceed- ings of the 40th International Conference on Machine Learning, volume 202, pp. 19200-19227, 2023.
Srebro, N., Sridharan, K., and Tewari, A. Smoothness, low noise and fast rates. In Advances in Neural Information Processing Systems, volume 23, pp. 2199-2201 2010.
Li, J., Liu, Y., Yin, R., Zhang, H., Ding, L.,, and Wang. W. Multi-class learning: From theory to algorithm. Advances in Neural Information Processing Systems, 31 (NeurrSS 2018):1593-1600 2018
Sun, F., Tang, J., Li, H.,, Qi, G., and Huang. T. S. Multi-label image categorization with sparse factor representation. IEEE Transactions on Image Processing. 23(3):1028- 2014.
Li, S. and Liu, Y. Sharper generalization bounds for cluster- ing. In Proceedings of the 38th International Conference on Machine Learning. volume 139. pp.
Wang. X. and Sukthankar, G. Multi-label relational neighbor classification using social context features. In Proceed- ings of the 19th ACM SIGKDD International Conference Knowledge Discovery and Data Mining, number KDD 2013, pp. 464 472,4472.2 2013.
2021. Liu, C., Zhao, P., Huang, S., Jiang, Y., and Zhou, Z. Dual multi-label learning. In Proceedings of the 32nd AAAI Conference Artificial Intelligence, number AAAI 2018, pp. 3635-3642. 2018.
Weng, W., Chen, Y., Chen, C., Wu, S., and Liu, J. Non- sparse label specific features selection for multi-label classification. Neurocomputing, 377:85-94, 2020.
Liu, W., Wang, H., Shen, X., and Tsang, W. The emerging trends of multi-label learning. IEEE Transactions on Pattern Analysis and Machine Intelligence, 44(11):7955- 7974, 2022.
Wu, B., Zhong. E., Horner, A., and Yang, Q. Music emo- tion recognition by multi-label multi-layer multi-instance multi-view learning. Proceedings of the ACM Interna- tional Conference on Multimedia, number MM 2014, pp. 117-126, 2014.
I Luqu-Piq F. and Pisier, G. Non commutative khintchine and paley inequalities. Arkiv för matematik, 29:241-260, 1991.
Maurer, A. A vector-contractioon inequality for rademacher complexities. In Proceedings of the 27th International Conference on Algorithmic Learning Theory, volume 9925, pp. 3-17, 2016.
Wu, G. and Zhu, J. Multi-label classification: do hamming loss and subset accuracy really conflict with each other? Advances in Neural Information Processing Systems, 33 (NeurIPS 2020), 2020.
McDiarmid, C. et al. On the method of bounded differences. Surveys in combinatorics, (11(1):448-188) 1989.
Wu, G., Li, C., Xu, K., and Zhu, J. Rethinking and reweight- ing the univariate losses for multi-label ranking: Con- sistency and generalization. Advances in Neural Infor- mation Processing Systems, 34(NeurIPS 2021):14332- 14344, 2021a.
Mohri, M., Rostamizadeh, A., and Talwalkar, A. Founda- tions of machine learning. MIT press, 2018.
Nam, J., Kim, Y., Mencía, E. I., Park, S., Sarikaya, R., and Fürnkranz, J. Learning context-dependent label permu- tations for multi-labe classification. In Proceedings of the 36th International Conference on Machine Learning, volume 97, pp. 9733-4742 2019.
Wu, G., Li, C., and Yin, Y. Towards understanding general- ization of macro-auc in multi-label learning. In Proceed- ings of the 40th International Conference on Machine Learning, volume 202, pp. 37540-37570, 2023.

---

Tight and Fast Bounds for Multi-Label Learning
Wu, L., Ledent, A., Lei, Y., and Kloft, M. Fine-grained generalization analysis of vector-valued learning. In Pro- ceedings of the 35th AAAI Conference on Artificial Intel- ligence, number AAAI 2021, pp. 10338-10340 2021b.
Xu, C., Liu, T., Tao, D., and Xu, C. Local rademacher complexity for multi-label learning. IEEE Transactions Image Processing, 25(3):1495-1555 2016.
Xun, G., Jha, K., Sun, J., and Zhang, Correlation net- works for extreme multi-label text classification. Pro- ceedings of the 26th ACM SIGKDD Conference on Knowl- edge Discovery and Data Mining, number KDD 2020, pp. 1082, 2020.
You, R., Guo, Z., Cui, L., Long, X., Bao, Y., and Wen, S. Cross-modality attention with semantic graph embedding for multi-label classification. In Proceedings of the 34th AAAI Conference Artificial Intelligence, number AAAI 2020, pp. 12709-12716, 2020.
Yu, H., Jain, P., Kar, P., and Dhillon, I. S. Large-scale multi- label learning with missing labels. In Proceedings of the 31th International Conference Machine Learning, volume 32, pp. 593-601, 2014.
Yu. K., Yu, S., and Tresp, V. Multi-label informed latent se- mantic indexing. In Baeza- Yates, R. A., Ziviani, N., Mar- chionini, G., Moffat, A., and Tait, J. (eds.), Proceedings of the 28th Annual International Conference on Research and Development in Information Retrieval, number S1- GIR 2005, pp. 255, 2005.
Yu, Z. and Zhang, M. Multi-label classification with label- specific feature generation: A wrapped approach. IEEE Transactions on Pattern Analysis and Machine Intelli- gence, 44(9):5199-522 5210, 2022.
Zhang, M.-L. and Zhou, Z.-H. A review multi-label learning algorithms. IEEE Transactions on Knowledge and Data Engineering, 26(8):1819-1837, 2014.
Zhang, Y. and Zhang, M. Nearly-tight bounds for deep kernel learning. In Proceedings of the 40th Interna- tional Conference on Machine Learning, volume 202, pp. 41861-41879, 2023.
Zhang, and Zhang, M. Generalization analysis for multi- label learning. In Proceedings of the 41st International Conference on Machine Learning, number ICML 2024, 2024a.
Zhang, Y.-F. and Zhang, M.-L. Generalization analysis for label-specific representation learning. Advances in Neu- ral Information Processing Systems, 3N 2024): 104904-104933, 2024b.
12

---

Tight and Fast Bounds for Multi-Label Learning
A. Appendix
A.1. Appendix Outline
In the appendix, we give the detailed proofs of our theoretical results in the main paper. Our main proofs include:
The tight vector-contractioon inequalities for multi-label learning with smooth base losses (Lemmaa 4.3).
The tight bounds for multi-label learning with smooth base losses (Theorem 4.4).
The local vector-contraction inequalities for multi-label learning with smooth base losses (Lemma 5.2)
The faster bounds for multi-label learning with smooth base losses (Theorem 5.5)
The novel vector-contraction inequality for &oo norm Lipschitz loss (Lemma 6.2)
The tight bound for Macro-Averaged AUC with Lipschitz base losses (Theorem 6.3)
The novel vector-contraction inequality for Macro-Averaged AUC with smooth base losses (Lemma 6.6)
The tight bound for Macro-Averaged AUC with smooth base losses (Theorem 6.7)
A.2. Preliminaries
A.2.1. THE BOUND FOR THE LOSS FUNCTION SPACE
According McDiarmid's inequality (MeDiarmid al., 1989) and the symmetrization technique (e.g., Theorem 4.4 in (Mohri al., 2018)), it easy to obtain that for any training dataset D {(.,, ys) E [m]]], ((.,)) S M, with probability at least 1 8, the following holds:
log am
R((()) S RD(((f)) 2R)(C) 3M
2n
A.3. Tighter Bounds for Smooth Base Losses
A.3.1. PROOF OF LEMMA 4.3
Proof Sketch: For Hamming loss, according to the smoothness of base loss functions, we first derive the relationship between the empirical & norm covering number N2(e, Ln,, D) of the loss space L and the empirical &o norm covering number No (c, P(F), [c] D) of the projection function class P(F). Then, we show that the empirical &oo norm covering number N ((F) [c] D) of the projection function class P(F) can be bounded by the fat-shattering dimension, and the fat-shattering dimension can be bounded by the worst-case Rademacher complexity of the projection function class PPF). Finally, combining the above results and the refined Dudley's entropy integral inequality, the Rademacher complexity of the loss function space Cи can be bounded by the worst-case Rademacher complexity of the projection function class P(F), and the desired bound can derived. For Subset loss and Ranking loss, we derive the relationships between the empirical & norm covering number N2 Ls, D). Ne CR, D) and the empirical foo norm covering number Noc (e, P(F), [c] x D), respectively. Then, using the similar technique the tight vector-contraction inequality for Hamming loss, the desired bounds for Subset and Ranking loss can be derived.
We first introduce the following lemmas:
Lemma A.1 (Lemma A.1 in (Srebro et al., 2010)). For any H-smooth non-negative function f + R and any I, E R we have that
(f(t) - f(r)) S (H(((t) + f()))
Lemma A.2 (Khintchine-Kaahee Kahane inequality (Lust-Piquard & Pisier, 1991)). Let vI...., n E H. where H. is a Hilbert space with || being the associated p-th norm. Let EI,..., En be a sequence of independent Rademacher variables. Then, for any p 2 there holds
p7
min( (in(vp-- 1,1)
1
<
E
c
max v
1,
1 2
13

---

Tight and Fast Bounds for Multi-Label Learning
and
n
Σ
2
c
13
Lemma A.3 (Lemma A.2 in (Srebro et al., 2010)). For any function class F, any with a finite sample of size n and any <> RF(F), we have that
(F)
fat.
22
Lemma A.4 (Theorem 12.8 in (Anthony& & Bartlett, 2009), (Lei et al., 2023)). If any function in class F takes values in [- B, B). then for any S with finite sample of size any 0 with (F) < n, we have
4eBn 4nB² de
Nog (c, S 1 doog2
log
where d = (F).
Lemma A.5 (Refined Dudley's entropy integral inequality, Lemma C.5 in (Zhang & Zhang, 2024a)). Let real-valued function class with f S B. / E F, O, and ussume that F. Let be a finite sample of size n. For any 2 S p S oc, we have the following relationship between the Rademacher complexity Rs(F) and the covering number Ng
/ Vn
12
B
Rs(F) S inf a>0
4a +
Fo,
First, we derive the tight vector-contraction incquality for Hamming loss with smooth base loss functions.
Step We first derive the relationship between the empirical lg norm covering number N2(e, LH, D) and the empirical Eo norm covering number No (c, P(F), [c] D) by the smoothness of base loss functions.
For the dataset D (111,2)) v2), (Xn, )n)) with i..d. examples:
m
- l (f)(z))
lo (f3(z))) - -
(ls (6,(()))))))) cs (f)(2))) vx))) (Use Jensen's Inequality)
Gr(ls (.((())))) - fa))) (Use Lemma A.1)
(3(((()))))) + C,(0 v(s))
max (Jz(m)) (xx))) iE(n]
<V 1
max +E(r),E[d
(f;( - (a()) (Use Assumption 4.1)
SV 12yM max max (xx:)) p, (f'(x))
(xx)..
(The definition of the projection function class P(F))
Then, according to the definitions of the empirical f2 and lx covering number, we have that empirical t.o cover of P(F)
at radius e/ M11 is also empirical Eg cover of the loss function space LH radius and can conclude that:
No Ce, D) Noc ( (V12, P(F),(() x
(5)
14

---

Tight and Fast Bounds for Multi-Label Learning
Step 2: We show that the empirical lo norm covering number of P(F) can be bounded by the fat-shattering dimension, and the fat-shattering dimension can be bounded by the worst-case Rademacher complexity of P(F).
According to Lemma A.3, for any (dxx(((FFF) we have
lat. (Pt)() 4nc c D (P(F))
Then, combining with Lemma A.4, for any E (0, 2B), we have
Se Be
log.Noc (c, x D) //tt:/(((//))) log2
e²
64nc.2
(P(F)
B
(c) x
$ +
log
2²
1 + Ra (P(F)
Se B2 nc
log
(6)
2
Step 3: According to Assumption 4.1 the main paper, we can obtain the lower bound of the worst-case Rademacher complexity Rno(P(F)) by the Khintchine-Kahaln inequality with 1:
(P(F))
sup [c]xDE(c]xx*
R (ddx((((F))
sup
Ex
sup
Egps Eap (f(:))
[e]]je(c)x." x
((((())))P(() ne
1=1
sup [d]DE([])xx* x.m
Ee
sup
GJ (x:)
E ne
1= j=1
72
sup
E
sup
Eg (w (z(()
(6)( ne
1=1 1=1
A E.
sup
Ey (x::))
(,, S ne
i=1
A
sup
Σ
(
(Use Lemma A.2)
10, (.) [ ne 2
1=1
Since [x,)( < A, we sup ne
E ES= (0:))=
Vnc- So.
AA
B
(P(F))
(7)
2nc
V2nc
Step According to Lemma A.5 and combined with the above steps, we have
RD(CH)
12 M
< inf a>0
4a +
C,
Vn
12 PM
| No0
( ( P(F), x xD)dt)
inf a>0
4a
(Use inequality (5))
Vn
Ja
15

---

Tight and Fast Bounds for Multi-Label Learning
12 MM
64nc12y, R
(P(F)
ne de R (P(F))
inf
40: +
1
log2
(Use inequality (6))
030
Vn
2²
12 (MM
64nc12y P R (P(F))
inf a20
4a +
1
log (2
(Use inequality (7))
vn
12M
192 (Pgg) (48en)c27:1)) / M
inf
4a +
c'
020
vn
12M
M
inf
4a
30y
Vn
az0
a
12M
M
+ 192 3ey
(4g In (P
Vn
(R
(Choose 48
12M
VnM
Vn + 192
log, (48en (48en2cxMM)
(Use inequality (7))
VBB
Second, we derive the tight vector-contraction inequality for Subset loss with smooth base loss functions.
Step I: We first derive the relationship between the empirical &2 norm covering number (e, Ls; D) and the empirical tx0 norm covering number (E, P(F), [c] x D) by the smoothness of base loss functions.
For the dataset D = (( v1)
(In, v with i..d. examples:
(4s(f(x:).)) v.) - - (f
max {&o (f)( max Eo (f](2)). jElc]
sElc
1=1
max (Es (ff(()))) - to (f3(2z))
jElc
max (4s (2;)) (bf f(xz)) (Use Lemma A.1)
%Eld
1=1
6y
max ve)) + (o(F)( U())
max (f)(z;) - f3))) sell)JEld
%Elc
12yM
max
1f,(z;) - fz()))1
(Use Assumption 4.1)
tE|n],jEd
SV 12yM max max (f;()) Ps, Pf
(The definition of the projection function class P(F))
Then, according to the definitions of the empirical f2 and l. covering number, we have that empirical t.o cover of P(F)
at radius e/ /12yM is also empirical E cover of the loss function space Ls at radius and we can conclude that:
(VLE ( P(F),c XD)
N₂ D) 5 No.
Step The following proof process is similar the proof Step 2-4 of the tight vector-contraction inequality for Hamming
16

---

Tight and Fast Bounds for Multi-Label Learning
loss. Hence, we have:
12M RD((s) - vn + Men + +ogg (488n222 In
VnM
VyB
Third, we derive the tight vector-contraction inequality for Ranking loss with smooth base loss functions.
Step I: We first derive the relationship between the empirical & norm covering number N2(e; LR, D) and the empirical 6o norm covering number No (c, P(F), [c] x D) by the smoothness of base loss functions.
For the dataset {(x1. // (In, vn)) with i.i.d. examples:
2 Σ l (f%(2))) f((x:))
72
Σ PEY+ qEY-
E
-(((())))(((1))
Σ
7
|
|
PEY+ 9EY-
11
Σ
Σ
(Gs - (1%(20)) - - f2(
(Use Jensen's Inequality)
Y+ -
PEY+ gET-
1
Σ
E
(1((a)))))))) f((().) (f)()))) - fa(()) f2 (x,)))
n
Y+ Y
PEY! DEY
(Use Lemma A.I)
Σ PEY+ -EX
Σ (fx(z) - fa(a);) + ls (ff(2:) - f((xx)))x
n
|
max
(fp(z:) fa(x)) - k((x)) + fz(()))
-EY-- iEE pEY.,EYY++++
S SV
PE p y 11f(2x)) fg(x,) ff(x,) + fax)) (Use Assumption 4.1)
max
S </127M
(E -.E- ((5p(ar)) (x,) (f((2,)) f(()))
max
max S /22 sE(n)
[x)(x;) - f3((a)1
< / M max max (x(()) - ps (f(((z))) (The definition of the projection function class P(F))
Then, according to the definitions of the empirical l and fa covering number, we have that empirical loo cover of P(F)
at radius c/2 is also an empirical b cover of the loss function space La at radius and we can conclude that:
(e, < No.
2 P(F),((
Step 2: The following proof process is similar the proof Step 2-4 of the tight vector-contraatioo inequality for Hamming loss. Hence, we have:
12M Vn
(1+ (192 In
VnM
S
+ MR
v7B
17

---

Tight and Fast Bounds for Multi-Label Learning
A.3.2. PROOF OF THEOREM 4.4
We upper bound the worst-case Rademacher complexity (PF)) as the following:
(P(F))
sup [d]
R (P(F(((FF)
sup
E
sup
Esp (f(a))
[dx
(;(((N))EP(F) ne
sup
Ee
sup
CifT (xx+)
EETT
i=1 j=1
sup
Ex
sup
Eij (W 23(():))
(
|ww :=1 ==1
A
sup
Ex
G5 (x:))
(m]] nc
1=
sup
Eell
Σ
(Use Jensen's Inequality)
j=1
A
AA
B
sup
1 (x:))1
(Use Lemma A.2)
(8)
nC
//c
Then, we have
12M
vnM
RD(CH) and RD((s)
192 3Cy.MRR (P(F))
logeen In
/n
VBB
192 (1+ (1+ (48en In
VMM
12M
VTB
Vn
Vn
and
12M
/844 (1+ (192e
VnM
Rp (C)) 5
Vn
v7B
384
(1 logg (192n22 In vnM
12M
RRB
Vn
Combining with (4), then for Hamming and Subset loss with smooth base losses, we have
24M 384/3yMB (1+ log, (48em2c2 In XnM Vn
V
log
R(f) < RD(f) +
+ 3M
2n
for Ranking loss with smooth base losses, we have
R(f) < RD( + 24M 768/37MB (1 (1+ log, (192en (192en227
XnM
log 2
+ 3M
Vn
2n
18

---

Tight and Fast Bounds for Multi-Label Learning
A.4. Faster Bounds for Smooth Base Losses
A.4.1. PROOF OF LEMMA 5.2
Proof Sketch: For Hamming loss, according to the smoothness of base loss functions, we first derive the relationship between the empirical & norm covering number N2(c, D) of the local Hamming loss space Lij and the empirical to norm covering number oe, P(F), [d] D) of the projection function class. Then, since the empirical &o norm covering number Noc ((FF), x D) can be bounded by the worst-case Rademacher complexity of the projection function class P(F), combining the above results and the discretized variant of Dudley's integral inequality, the local Rademacher complexity of the local Hamming loss function space L'z can be bounded by the worst-case Rademacher complexity the projection function class, and the desired bound can be derived. For Subset loss and Ranking loss, we derive the relationships between the empirical l2 norm covering number N2(c, Lis, D), NN2(,, R: D) and the empirical fo norm covering number No (e, P(F), [c] D), respectively. Then, using the similar technique to the local vector-contraction inequality for Hamming loss, the desired bounds for Subset and Ranking loss can be derived.
We first introduce the following lemmas:
Lemma A.6 (Discretized variant of Dudley's 's integral inequality (Guermeur, 2017)). Let be a real-valued function class and S {S1,..., 8 be a finite sample of size n. Let (ej); be monotone sequence decreasing to O and any (o1...., an) E I". !f
sup Σ (f - a:)² n-
60 2
JEF i=1
then for any non-negative integer N we have the following relationship between the Rademacher complexity Rs(FF and the covering number N2(e,,
N Rs(F) S 2
log N2 F,, cNN
1022260 (e j=1
(c)+
Lemma A.7 (Pollard, 2012)). Let F be a class of functions from X to R. and let Fo be a subset. Then for any E 0, we have the following relationship on covering numbers: Nylc. S N,,
First, we derive the local vector-contraction inequality for Hamming loss with smooth base loss functions.
Step 1: We first derive the relationship between the empirical & norm covering number N2(e, L'H D) and the empirical exo norm covering number (e, PcF), x D) by the smoothness of base loss functions.
For the dataset D
{(x1. 91 (In, v with i..dd examples:
(en(f(2)).v) - [f:(f(
i=1
2
ls (f)(z)) Σ
4 (f((a.)))
i=1
j=1
5=1
1
Lb (ff(z))) - to (f)(z)), )=
(Use Jensen's 's Inequality)
67 (cll://fcccoooo+ooo//ee)))))))l) (x:))) (Use Lemma A.
(66 (Z)( Mey) (ol
max (f)(t,)) f3() iEim).SElc
1/17/
max kE())jE(d
(xx)) (x,)
(Use Definition 5.1)
19

---

Tight and Fast Bounds for Multi-Label Learning
S 12 max max by (f(x))) - Py (xx))) (The definition of the projection function class P(F))
5
Then, according to the definitions the empirical & and &o covering number, we have that an empirical &oo cover of P(F") radius c/ s/v12 T2yr is also an empirical &g cover of the local loss function space L at radius c, and combined with Lemma A.7, can conclude that:
No (e, LH D) S Nox
{ (122 P(F),(()) SNo
E
P(F),le)
2//277
Step According to the inequality (6), we have that the empirical foo norm covering number of P(F) can be bounded by the worst-case Rademacher complexity of P(F). Let eN /8y3 max + (P(FF) and Ej - 2 -N-eeN, where
N [log2 / max ve (P(F))
B
According to Lemma A.6 and combined with the above steps, we have
RD((
Nog CH,, D)
$2
Σ
(g +G-1)
n CN
N
log
P(F),Ic(
Σ
(g (--)
22/229
+ EN
(Use inequality (9))
n
j=1
64mo(2, (T2r) R (P(F))
N
log2
1
2
(e, (c-1) Vn
+ Σ
(e, (
EN
n
j=1
5=1
(Use inequality (6))
64no|2 /2nr) Me 12. (P(F)
log2
ne
GED
+2
Σ6
(c, + c
EN
Vn
n
j=1
48 /
+ >
N
(eg + (-1)
8/22//12y Rno (P(F)
loga
( +EN (Use
6o
S 2B)
Vn
2/12n1
jml
48/3yrB
N
SeB2 (n
+ 48 4v Royr (P(F)
Σ
loga
EN
(Use = =2e,)
Vn
o)
j=l
/8yByBB
1 ?
+ 48 4v Roy (P(F)
log, 32 2 noyr + log,
+EN
Vn
48 /8
1
48 4v
Royr (P(F)) log, 32 1 noyr + 48 4/ Royr (P(F)
log EN
vn
E
j=1
48 / Vn
N
2
48 48
log, 32 12eB' noyr + 48 4 4/30yr (P(FF)
logg
2 +
EN
60
j=1
(Use 2 - 6n)
/ Vn
+ 48 4, RPFFR 32. 12eB2
N
N
48 4v R (P(F))
loga
+ log, 2
i) + cN
c
1=1
j=1
20

---

Tight and Fast Bounds for Multi-Label Learning
48 B
1
+ 48 4/ +88.4v
log, 32 12eB² neyr
12eB'neyr + 48 4
2 + (N + 1) 2) + EN
Vn
60
48 B + 4. (ee log, 32 12eB2 + 48 4/ (e
2
1
_)
) + cN
Vni
6o
CN
(Use 6O = =2% .N)
48 /
+ 48 33yreRBBe (P (lgg 32 12r
Vn
2
48. 4 4 Beo (P(F)) log2(
I (Use 2/12 2 B and eN 2 48 /
37m
4v33rB
48/3,T Vn
Vn
B VTi
vn
+ 48
Ree (P(F)) logg 32 12eB"noyr + 48 4v 30y Rod (P(F)) log2 6 y8
EN
4 Vn
vn
48 ( 32
12eB2 log2
6 48 + CN
48 /8rByBB
deBuèe
4/3yrB B
+ 48 Ree logg(
Mlgg
1 + CN
vn
3
48 /8/
v
B
(Use N = [log2
/ max
Vio Rnd (P(F))
48 /8/ByBB
4e
vnB
+ 48 4v Red logg(
flog2
+
Vn
12
48 B
VnB
+ 48
Bee.e///nnnnnnnnFT. (4Bn
log2
+ 48 3yr /
maxt (P((F))
Vni
6
48 3
B 1)
4 (4Bm 2c) loga (VBB). (Use max b} S a
Vn
Second, derive the local cector-contraction inequality for Subset loss with smooth base loss functions.
Step 1: We first derive the relationship between the empirical & norm covering number (c, Lg. D) and the empirical Ex norm covering number (e, (FF), [c] x D) by the smoothness of base loss functions.
For the dataset = {(x1, v1). .... (In, yn)) with n i.i.d. examples:
- ls( ((s():)),)))((((((((((()()))))))
1=1
max (6o (fb(2z), max E (f)())) (((())))))) JE(C]
sE(0]
max (Es (f.) lo (o(()))) %E|d
max 6'6 (()) (1f fx)1) (Use Lemma A.1) %Eld|
6%
max(k (4s (f)( M1z) + (o(l)(()).))))) jEld
max (1)(2,) (()) [E|m),E[c]
12yr
max ie ie(
(f,( (3())
(Use Definition 5.1)
21

---

Tight and Fast Bounds for Multi-Label Learning
5V12 max max (f(()) py (f())) (The definition of the projection function class P(F))
Then, according to the definitions of the empirical l2 and ls covering number, we have that an empirical foc cover of P(F") radius e/v/11y is also empirical l2 cover of the local loss function space Ls at radius e, and combined with Lemma A.7, can conclude that:
D) &oc (
No (e. D) Noc
(12TT P(F))
c
2/T27T (2T P(F)ld
The following proof process is similar to the proof Step 2 of the local vector-contraction inequality for Hamming loss. Hence, we have:
Step 2:
48 + 1) RD(())
Reyr (P(())))(P(())))) ( log2 (vnB)).
Vn
Third, we derive the local vector-contraction inequality for Ranking loss with smooth base loss functions.
Step 1: We first derive the relationship between the empirical & norm covering number N2(c, Lx D) and the empirical co norm covering number (e, ((F), [c] x D) by the smoothness of base loss functions.
For the dataset = {(x1, y2), ..., (In, yn)) with n i..dd examples:
(LR(f(Z;)))) Mi) Rf )
7
Σ
Σ
4 (fp(z)) - f(((x)))
Σ
Σ
&s (fb(ar) f(((x))
|
| |
i=1
PEY+ gEY
PEY+ 9EY
Σ
Σ
(Bs (fplzx)) - fg(xx)) - Cb (f%((x)) - fx(x
(Use Jensen's 's Inequality)
Y+ Y-
PEY+ -EA-
Σ
Σ
(f((aa) fa(xx)) + Cs (f/(2:) fa(=:))) - fy(ax) fz( + fx:)):))
Y+ Y-1
PEY! DEY
(Use Lemma A.I)
Σ Σ (lo (fx(z)) - fy(x,)) + ls (ff(0:) f((x)))xx
Y+ -
P -
max kE(n),EY+,qEE -EY- (fr(2;) - -a((s) - (xx) + fxx)))
127r
iEInI,PEY --E- 1f5(2x;) - fx(1)) - ((.) + fa:))) (Use Definition 5.1)
max
127T
max ((f fx(x))) (fg ff-() (z)))
12
max
(2; - (xx))
iE(n]JE(c
<2 12 max max py (f(x)) (f (f(()))) (z:).. (The definition of the projection function class P(F))
Then, according to the definitions of the empirical & and lo covering number, we have that an empirical foc cover of P(F") radius e/2r/12rr is also an empirical &g cover of the local loss function space 2 radius e, and combined with Lemma A.7, conclude that:
P(F)). x D) S Noo ( c ( P(F).ldx
Ch, D) S SNo
22/12 (2/1ET
(411777
22

---

Tight and Fast Bounds for Multi-Label Learning
Step 2: The following proof process similar the proof Step 2 of the local vector-contraction inequality for Hamming loss. Hence, we have:
96 96 + 96 Bee
RD((')
1 (4gg(4 loga (vnB)).
vn
A.4.2. PROOF OF THEOREM 5.5
We first introduce the following lemma:
Lemma A.8 (Theorem 6.1 in (Bousquet, 2002)). Let F be a class of non-negative functions such that 0 S f S c clmmost surely. Let (f) = Σi= f(x;). Let vn be a sub-root function such that for all O.
RD(I Rf( S <r]) S vr(r).
Define r as the largest solution of the equation (r) = r. For æ > 0, with probability at least E= =fo Jolall J E F
R(f) (f 106r + 48ro.
where ro = c(x 6log log n)/n.
According to Lemma A.8, for a sub-root function (nn r > 0, RD((T) I (r((r), we have the following holds with probability least 1 6,
R(J) 2RD(s) + 100r 4log 6 log logn)
n
where r is the largest solution of the equation ()) r, i.e., the fixed point of tin
For Hamming loss and Subset loss, we set 2 (r) = 18/3 + 48.
(ogg(
V
which is sub-root function, and RDD(C)) I (r). RD(()) s (r). Hence, solving the equation ()) gives the fixed point
B+1 Vn
r 3-44
((nn)(((F))(
VeR
410g, (lg
According to the inequality (8), we have that the upper bound of the worst-case Rademacher complexity is (ene(P(F) s vne- then combined with the above steps, we have
3- 3-48 a8 1)3 (1+ (1 (11+41lgaall (logg(4Bn log2(VnB))) bM 1 + 6 log log m)
R(F) < 2R)(f) +
where a = 106, b = 48.
Using similar techniques and local vector- centrrccont inequality of Ranking loss, we can derive the sharp bound for Ranking loss with smooth base loss functions:
3- 969 26-96a aB 1)² (1 (1 41og, log2(VnB))
bM (log 1 + 6 log log n)
R()) < 2fp
Y
n
where a = 106, b = 48.
A.5. Tighter Bounds for Macro-Averaged AUC
1. PROOF OF LEMMA 6.2
We first derive the relationship between the empirical & norm covering number N L, D) of the loss function space and the empirical lo norm covering number No (e, [cF), x D) of the projection function class. Then, since the empirical foo norm covering number (e, P(F), [c] D) can be bounded by the worst-case Rademacher
Proof Sketch:
23

---

Tight and Fast Bounds for Multi-Label Learning
complexity of the projection function class, combining the above results and the refined Dudley's integral inequality, the Rademacher complexity of the loss function space be bounded by the worst-case Rademacher complexity of the projection function class, and the desired bound can be derived.
Step 1: We first derive the relationship between the empirical Lo norm covering number number.Noofe Ne, 8o norm covering number No (c, P(F), x D).
L, D) and the empirical
For the dataset = {(01, 21 (2', ) with n i.i.d. examples:
max [(ff(x))) v:) (x)' v.)l
Spmax [If(x:) - (xx;)) (Use Assumption 6.1)
Spmaxmax Ifz (z:) - fj (x:))
Spmaxmax py (f(:)) - P, (xx)). (The definition of the projection function class P(F))
Then, according to the definition of the empirical foo covering number, we have that an empirical e cover of P(F)) at radius p/p is also an empirical fo cover of the loss function space L at radius and we can conclude that:
No (e, D) N (())
(10)
According to the inequality (6), we have that the empirical for norm covering number of P(F) can be bounded by the worst-case Rademacher complexity of P(F). According to Lemma A.5 and combined with the above steps, we have
RD(
12 M
inf 020
4a +
Le, Dide
Vn.
12 MM
inf 020
4a +
V log log (-, P(F), D)de
(Use inequality (10))
Vn.
a
4a + 12 M
64ncp R2 (P(F))
Bep de (P(F))
inf a>0
1
log2
(Use inequality (6))
VT
2²
R2
12 PM
64nep (P(F)
inf
4a +
Vi+ 1+
logg 2 22p)de
(Use inequality (7))
020
Vn a
12M
log, (en (4g, 2 1 M
inf
4a +
c'de)
a20
Vn
12M
inf
loge D4gg
4a + D
M
)
Vn
a>0
a
12M
M
(oo In
Vn
(Choose
12M
M Mvn, ). pB (Use inequality (7))
+
96p Rno
log, (onn In
Vn
A.5.2. PROOF OF THEOREM 6.3
Proof Sketch: First, for the induced surrogate loss for Macro- Macro-Averaged AUC, by using the U-process technique, we define the empirical Rademacher complexity a loss function space associated with the multi-label learning class F over the set of i.i.d disjoint positive and negative sample pairs for each j-th label, then with two-sided multiplicative Chernoff bound, the
24

---

Tight and Fast Bounds for Multi-Label Learning
generalization error can be bounded by RD, (CM) = Ee supper 1/ E // -Ej=1 eilo ) (a ))] Second, combining with Lemma 6.2 and the Lipschitz continuity with respect to the &o norm of the induced surrogate loss for Finally, we Macro-Averaged AUC, we have (C., = 12M + 96p (P + logz(4er (2) In n/
upper bound the worst-case Rademacher complexity (P(F)) S
vrge the desired bound can be derived.
2B
Rademacher complexity has proved be a powerful data-dependent measure of hypothesis space complexity. However, since Macro-Averages AUC involves pairwise functions, a sequence of pairs of i.i.d. individual observation in (2) is no longer independent, which makes standard techniques in the i.idd case for traditional Rademacher complexity inapplicable. We convert the con-sum-of-ii.d pairwise function to a sum-of-i.i.e form by using permutations in U-process (Clémençon et al., 2008; Zhang& & Zhang, 2024a).
According to the definitions of the empirical risk w.r.t Macro- Alero-Averaged AUC and the induced surrogate loss for Macro- Averaged AUC in (2) and Subsection 3.2, for the induced surrogate loss for Macro-Averaged AUC, we define the empirical Rademacher complexity of a loss function space associated with the multi-label learning class J over the set of i.i.d disjoint positive and negative sample pairs for the j-th label as follows:
(C,) = Ee sup
Σ FEF
1 Tj (el((fa]"" af)
EEe
sup JEF
alb (f)latt) -B(c))))(oo))) (11)
where each e an independent Rademacher random variable. The corresponding expected Rademacher complexity is defined as Rr (fm) ED, RD, (CM). We denote supyes H Ex' eaM (f( ax;- R
According to the symmetrization technique, we can obtain
R()) - Ro(r))
En sup fEr
<ED, v
sup fEF
Σ
(lar(f(att, 2 ()))-R(())))
X
X
xt exxx x,t EX,
sup <En
Σ
(1)) (0) -(0)))))))))))))))))))))) -
FEF
85!
Tj i=1
<ED,y
sup fEF 83! .ty!
Σ
(Cm(F((a2t
10y o (0)) ()))-
(0))) -R(())
rj
<ED,y
Σ
sup JEF
1
Σ (Cu(l((at) ar
-0, (0) - m(Si) (o())))(()))))))))))()))))
(vb nondecreasing)
8g! tz!
rj
T 1:
Σ (Car(f(a (1)) 22t1)))) (11t))))==)))))))) -
EDD vb
sup SEF
(Jensen's 's inequality)
83!. tyl
(er(f(a!t, xb - BB(5))
1
sup <ED JEF
<ED,y 1/
sup fEF
1
Σ
;,+[((t)),x))))))) (em(f(a) x( - ED, (falttt
25

---

according to McDiarmid's inequality, we Tight and Fast Bounds for Multi-Label Learning
ED v
sup fEF [j i=1
Σ
(eu(f(( a ED ( 2 ))
(Dj is the set of samples with the same distribution as D2)
(m (f , 1))
sup FEF
(Jensen's inequality)
rj
Ty
D'D,
sup SEF
C (la((f(tttaa Las (f xt
Jj
1
Σ (f ;0 .m2
+ 1
Fa (f aat
ED
2 sup SEP
2 sup SEF
rj
T
(f ab11)) (D) with the same distribution as Dj).
SEDD
2 sup feF
Σ
rj
i=1
Hence, we have
R(f) - Ro(ss) s EDG,eV (2R
ED, +
sup fEF
(12)
Since the maximum difference caused by replacing one element in D, or e; 2M, have
P( -R,, (fM)) 2 E) S 2e 2x2
Then, according to the tail bound for sub-Gaussian random variables and Theorem 2.1 in (Boucheron et al., 2013), R2x is a uub-Gaussian random variable with variance proxy 16 M²
16. r; With the definition of the nab-Gaussian random variable, we have
n EDy,ee
8R (R,(ss))) 22 Vt > 0.
I e
(13)
Then, for any > 0. we have
sup R(F) -(f)-R((())) Ro)(s) -Ro(s) 2 fer
=P (Ssuppes ((J) (cOOU)ES(((T))-OO)) ((()- 2 kt)
ED (touppees R(f) R Ro(s))
ED,
(Use Markov's Inequality)
ete
ED 2RR ete
Dj
(Use inequality (12) with v/(x)) exar)
2tRrr (Car)+ 202
(Use inequality (13)).
ete
2r2 25Me, (Ba23 2 "y
We set
8, then we have E = 2R,, (CM) + 32tM2
+ 1
o+c
ry
1
Hence, upper bound the term with probability at least 88: 8:
321M/
In
sup FEF
R(f) - RD((f)
52RR, +
+
t
2ln 3
<2R,, (Cm) + 8M
(14)
Ti
26

---

Tight and Fast Bounds for Multi-Label Learning
Next, transform R, (LMr) in inequality (14) into RD, (Car), according to McDiarmid's inequality, it is easy obtain that the following holds with probability least 1 8:
In
R (Lm) S RD, (LM) + M
(15)
2rj
Combining inequalities (14), (15), and Union bound Inequality, we have the following holds with probability at least 1
6:
In R
2 2
R(f) - -R((f) & 2RD, (CM) + 2M
+ SM,
(16)
2rz
Next, we incorporate an additional Chernoff-type argument to obtain bound that does not involve any random quantities.
First, since sj Binomial(n1pp) P2), we have EE- = mpp. With the two-sided multiplicative Chernoff bound, we have
PPpp
P([sj np5l 2 rnpj) S 2e
Vr E (0,
Then, we have
P
8j
pyl 2 rp,)
8j pjl rp;})
<P
8j
P
pyl
2 rps)
(Use Union Bound Inequality)
2e
2. mimin Pi
<2ce
Pu P1
3ln 3o nmmnn Ps
We set 2cc"
6, then have
Hence, the following holds with probability least 1 1 8:
3 20 ninn Pj
$j pyl S ppp
Solving the above inequality yields 8, np,
3la +
Similarly, we have 1 (1 p,)] (1 p))
3lu + n miny Ps
n miny Pj
3la ). and solving this inequality yields ty 2 n11 P1)(1
n miny Pj
Hence, we have the following holds with probability at least 5:
mn 2c n1 P1)(1
3 In 2c V min, Pj
rj min min(s),t 2 min[np,(1 V min, Pj
))-
(17)
In order to ensure that for every j-th label, disjoint positive and negative sample pairs can constructed, we need to derive the lower bound for miny(ry } to obtain the number of disjoint positive and negative sample pairs that can be constructed for every j-th label. Since
ry 2 min(ry} (min
3ln
3
2 (opp
min ( -p)((1 n miny Pj
}}}}
mmin Pj 3
27

---

Tight and Fast Bounds for Multi-Label Learning
3ln 2c miming Pj
3ln 2c
min mi min P2(1
).n minnnn P2)(1
}}
mimin Pj
1n 2e
min( min Pjr 2" minn1 - Pÿ)} (Assume that
min; Pj
1
2 g P,, min(1 pp)}}
n min (onnmmnnnp
(Define ro min min(1 p;)}),
2 ro
3
then we have 2 ro with probability at least 1 - 6.
Combining the inequality (16) and Union bound Inequality, we have the following holds with probability at least - 6:
R(f) RD(
In 1
In
(CM) + 2M
V
16M
To
To
In 0
=2V22D (CM) + 18M
(18)
70
Then, according to Lemma 6.2, we have
12M
M /To
(C S
+ 96p/eRroc (P(F))(
In
Vru
pB
We then upper bound the worst-case Rademacher complexity (P(c()(FF) the following:
Rygc (P(F))
=
sup
P R (P(F))
ro c
sup [e'xDr((dxx'"0
Ee
sup
cop of 211)
py PE((() roc
j=1 4i (f)(2,) ,5(x1))
1
sup
Ee
sup
f,EF, Puc
i=
sup
Ee
sup
Ei (y (,((,) 2z
Toc
||w ISS
i= 1=
sup
Eel
Es (2)) - 2g |I
[
Toc
1=1
2A Eel
sup
3 (x:))
|
Toe
im1 j=1
sup
2A
Edll Σ
ro
(Use Jensen's Inequality)
1 [11 Toe
iml jml
2A
2AA
2B
sup
Σ
11 (2::))
(Use Lemma A.2)
(19)
M [ Pac
Tuc
TDC
i=1
28

---

Tight and Fast Bounds for Multi-Label Learning
Then, have
12M -
M Mynu,
RD (CM)
+
Vru
PB
12M
192p
(1 (og In Mvro pB
vro
ro
Combining with (18), then
24V2M
384v2pB
TT
In
R(f) - R
+
Vru (1+ (4er
pB ) + 18M
To
A.5.3. PROOF OF LEMMA 6.6
We first derive the relationship between the empirical lg norm covering number N2(c, LMs D) and the empirical &oc norm covering number No ((F), x D) by the smoothness of base loss functions.
For the dataset D {(x1 2/) ...,... (In, yn)) with i..d. examples:
(1); 9) (m(s' (x),
72
la (U5(am)- Σ Es (J)(ax)) (13(a))-(((ut))
1=1
(Z)())))) - 6a (1j( f3(2
(Use Jensen's Inequality)
(f,(2)) -1(())))((())))))))))))))))))))) + 4. -()))))(()) +((x)))(((())) 13(x)))
+
(Use Lemma A.1)
67 12
(le (f)(z)) - (((((()))1((())) + 6 (f)(a,) - f(((4)))
max (z)(2:) - f((x)) - fz(x)) + f3()))))
n
kE(n),jEEd)
SV
12 kE(M],E[d
max
15((;)) - [5(x5) f5())) + s5(11(1 (Use Assumption 4.1)
S 12
max kE(n).jE[d
(f x\) - fj x1))
S M2 max max py (f, x))) ps (f'( m/)1- (The definition of the projection function class P(F))
Then, according to the definitions of the empirical l and lo covering number, we have that an empirical too cover of P(F)
at radius e/ /12yM is also an empirical Eg cover of the loss function space Cas at radius e, and we can conclude that:
c (VISTA (1))
(c, D) Noo
The following proof process is similar the proof of Lemma 4.3. Hence, we have:
12M Vn
192 M (P(F)) + log, (4 VnM
RD((M) s
vTB
29

---

Tight and Fast Bounds for Multi-Label Learning
A.5.4. PROOF OF THEOREM 6.7
The overall proof process is similar to the proof of Theorem 6.3, the difference is that according to Lemma 6.6 have
12M
+ Be + logg In VroM
(Cor S
Vro
VYB
Combined with the upper bound of the worst-case Rademacher complexity (roc(P(F)) in inequality (19), we have
12M
384/3yMB
VraM vTB
(Cx) v
(1 + log (48er))
Vro
TT
Combining with (18), then
24v2M
768/67 VTo
Vro.
In 4
R(F) RD(
(1 + logg (48er In
18M
Vro
vJB
rb
30


Reviews:
[{"review_id": "0uvojF4YVE", "reviewer": "Reviewer_XSTz", "summary": "This paper focuses on the problem of multi-label classification, where each instance can be associated with multiple labels simultaneously. The authors derive several generalization bounds for this setting, assuming smooth loss functions. Their analysis relies on standard techniques for characterizing the complexity of function classes, such as local Rademacher complexity.\n\n\nThe core novelty of the paper lies in the development of specific vector contraction inequalities tailored to a particular class of multi-label classifiers. These inequalities are then used to establish generalization bounds. This approach leads to the derivation of slower convergence rates with respect to the sample size. Notably, the authors obtain rates of $\\sqrt{c}$ and $c^{3/2}$ for several well-known multi-label losses, including Hamming loss, subset loss, and macro-averaged AUC (Area Under the Curve).", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your constructive comments and active interest in helping us improve the quality of the paper.\n\n**1. Response to C1**\n\nWe add concrete examples of multi-label learning (MLL) methods after the function class definition to improve readability and practical interpretation, please refer to **Response 1 to Reviewer Wn57** due to character limitation.\n\n**2. Response to C2** \n\nFor the case where base loss is cross-entropy loss, our theoretical results do not cover cross-entropy, mainly because cross-entropy loss is not bounded. Next we will further discuss the smoothness of cross-entropy. When the model is a linear classifier, smoothness of cross-entropy can be achieved by the boundedness of input, but from the perspective of model capacity, such a result is not general. The function class here involves general functions (i.e., nonlinear mappings $\\phi_j$), so for nonlinear models, smoothness of cross-entropy involves not only boundedness of the gradient of model function but also boundedness of second-order derivative. For deep networks, changes in parameters may cause drastic changes in second-order derivative, resulting in the norm of second-order derivative being unbounded. Hence, smoothness of cross-entropy is often difficult to hold. However, the Lipschitz continuity of cross-entropy is often established, and the boundedness of gradient of model function is guaranteed by various strategies in practice, e.g., input normalization, weight initialization, gradient clipping, and regularization. This implies the need to develop new theories and analytical methods for unbounded base losses. Under the new theoretical analysis method, tight bounds with no dependency on $c$ for cross-entropy loss can be obtained using its Lipschitz continuity, but improving the convergence rate of its bound wrt $n$ is still an urgent open problem to be solved. In the future, we will further study bounds with a faster convergence rate for unbounded Lipschitz base losses. \n\n**3. Response to C3** \n\nSince the output of MLL is a vector-valued function, we need to convert Rademacher complexity of the vector-valued class into complexity of a tractable scalar-valued class. For $\\ell_2$ Lipschitz losses, the analysis of MLL can be traced back to a basic bound with a linear dependency on $c$ that comes from a typical inequality: \n\n$$\\mathbb{E}\\left[\\sup_{\\boldsymbol{f} \\in \\mathcal{F}} \\frac{1}{n} \\sum_{i=1}^n \\sum_{j=1}^c \\epsilon_{ij} f_j\\left(\\boldsymbol{x}_{i}\\right)\\right]$$\n\n$$\\leq  c \\max_j \\mathbb{E}\\left[\\sup_{f_j} \\frac{1}{n} \\sum_{i=1}^n \\epsilon_{ij} f_j\\left(\\boldsymbol{x}_{i}\\right) \\right].$$\n\nThe dependency of bounds on $c$ can be improved to square-root. Such improvements essentially come from preserving the coupling among different components reflected by constraint $\\\\|\\boldsymbol{w}\\\\| \\leq \\Lambda$. \n\nAs a comparison, when $\\\\|\\boldsymbol{w}_j\\\\|_2 \\leq \\Lambda$ for any $j \\in [c]$, \n\nif we consider group norm $\\\\|\\cdot \\\\|_{2, 2}$,\n\nwe have $\\\\|\\boldsymbol{w}\\\\|_{2, 2} \\leq \\sqrt{c}\\Lambda$, which means that these improved bounds still suffer from a linear dependency on $c$. [1] improved the dependency of bounds on $c$ from linear to square-root in decoupling case for $\\ell_2$ Lipschitz losses. We found that square-root dependency of bound in [1] on $c$ is inevitable for $\\ell_2$ Lipschitz losses, which essentially comes from a $\\sqrt{c}$ factor in the radius of empirical $\\ell_2$ cover of projection function class. We also found that smoothness of base loss can eliminate the $\\sqrt{c}$ factor, so that tight bound with no dependency on $c$, up to logarithmic terms, can be derived. In addition, according to the above core ideas, we combine smoothness of base loss with local loss space to develop novel local vector-contraction inequalities, thereby obtaining sharper bounds with a weak dependency on $c$ and a faster convergence rate wrt $n$. We have also explained proof processes, ideas and specific theoretical techniques in proof sketches, which mainly includes conversions between complexities of different classes and some lemmas required to achieve these conversions.\n\n[1] Generalization Analysis for Multi-Label Learning, ICML 2024.\n\n**4. Response to C4** \n\nWe explain the multiplicative factor of 2, please refer to **Response 4 to Reviewer ZadH**.\n\n**5. Response to Literature** \n\nWe give a detailed discussion of the paper pointed out, please refer to **Response 2 to Reviewer dgGN**.\n\nWe will incorporate these discussions into the paper in an appropriate manner.\n\n**6. Response to Weakness** \n\nWe will carefully check and revise the notation to ensure consistency, e.g., the definition of base losses $\\ell_b$. $\\widetilde{\\Re}_{nc}(\\mathcal{P}(\\mathcal{F}))$ is worst-case Rademacher complexity of projection function class. We define worst-case Rademacher complexity in Definition 3.1, \n\n$\\widetilde{\\Re}_{nc}$ is the analog of the definition of worst-case Rademacher complexity for class $\\mathcal{P}(\\mathcal{F})$.", "claims_and_evidence": "In summary, while the paper presents valuable generalization bounds for multi-label classification, there are several points that need clarification and improvement. Providing concrete examples of the model class, addressing the applicability to cross-entropy loss, clearly explaining the novelty of the vector contraction inequalities, and correcting the error in Theorem 5.5 would significantly strengthen the paper and enhance its accessibility and impact.", "methods_and_evaluation_criteria": "No empirical evidence is given.", "theoretical_claims": "*Specific Points and Concerns:*\n\n1) *Model Class Examples:*\n* It would be beneficial if the authors could provide concrete examples of state-of-the-art (SOTA) multi-label classification methods that fall within the specific class of classifiers considered in this paper. This would help readers understand the scope and applicability of the theoretical results. Clarifying which existing models align with their defined model class is crucial for practical interpretation.\n\n2) *Smoothness and Cross-Entropy Loss:*\n* In practice, a common approach for multi-label classification involves using cross-entropy loss for each label independently as a surrogate loss function. It is essential to clarify whether the authors' definition of \"smoothness\" encompasses this widely used cross-entropy loss. If it does, this should be explicitly stated. If not, the limitations of the analysis concerning this practical loss function should be discussed.\n\n3) *Novelty of Vector Contraction Inequalities:*\n* The paper's primary contribution seems to be the new vector contraction inequalities. However, the explanation of their novelty is lacking. It would greatly improve the paper if the authors highlighted the key insights or \"core idea\" behind their improved inequalities. What specific techniques or arguments allowed them to derive better bounds compared to existing vector contraction inequalities? Clearly articulating this contribution is essential for the paper's impact.\n\n4) *Error in Theorem 5.5:*\n* Theorem 5.5 appears to contain an error. The empirical error term seems to have a multiplicative factor of 2, which is likely incorrect. This should be carefully checked and corrected. Such errors can significantly undermine the credibility of the theoretical results.", "experimental_designs_or_analyses": "No experiments are provided.", "relation_to_broader_scientific_literature": "Not included a paper which gives actually much better dependence on the number of labels under a more mild  assumption on the function class than that of considered in the submission. Please see: Busa-Fekete et al.: Regret Bounds for Multilabel Classification in Sparse Label Regimes. NeurIPS 2022", "essential_references_not_discussed": "see comments above", "other_strengths_and_weaknesses": "The notation is quite hard to follow. And there are many inconsistency in the notation. Like $\\ell_b$ has one argument, and some cases two arguments. And R_nc is not defined, or I have not found it.", "other_comments_or_suggestions": "None.", "questions_for_authors": "See above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5kSNgqXK0A", "reviewer": "Reviewer_dgGN", "summary": "By incorporating smoothness assumption, author provides generalization guarantee achieving a tighter bound - independent of c, the number of labels up to log factors, a faster bound - 1/n, and a similar tighter bound for Macro-averaged AUC.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your constructive comments and active interest in helping us improve the quality of the paper.\n\nThe following are our responses to the Questions:\n\n**1. Response to the Question in Claims And Evidence.**\n\nHere we mention that the bounds with a square-root dependency on $c$ in literature [1] mainly refers to the results for $\\ell_2$ Lipschitz loss in literature [1], i.e., Lemma 3.6 and Theorem 3.7. Our improvement is mainly relative to Theorem 3.7. In the proof of Lemma 3.6, the $n$ in equation (9) should be changed to $nc$. This is a typo. In fact, the results in Lemma 3.6 and Theorem 3.7 require the introduction of an additional $\\sqrt{c}$ factor, because they ignore the $\\sqrt{c}$ factor in the radius of the empirical $\\ell_2$ cover of $\\mathcal{P}(\\mathcal{F})$. Therefore, a $\\sqrt{c}$ factor is missing in Lemma 3.6 and Theorem 3.7, and literature [1] improved the dependency of the bounds on $c$ from linear to square-root in the decoupling case for $\\ell_2$ norm Lipschitz losses. Although for $\\ell_2$ Lipschitz loss, the bounds in literature [1] is only improved by a factor of $\\sqrt{c}$, they are still the tightest results in multi-label learning with $\\ell_2$ Lipschitz loss. In addition, for Hamming loss, its Lipschitz constant can induce the tight bounds with no dependency on $c$. We found that the square-root dependency of the bound in [1] on $c$ is inevitable for $\\ell_2$ Lipschitz loss, which essentially comes from the $\\sqrt{c}$ factor in the radius of the empirical $\\ell_2$ cover of the projection function class. We also found that the smoothness of the base loss function can eliminate the $\\sqrt{c}$ factor in the radius of the empirical $\\ell_2$ cover of the projection function class, so that the tight bounds with no dependency on $c$, up to logarithmic terms, can be derived. \n\n[1] Yi-Fan Zhang, Min-Ling Zhang. \"Generalization Analysis for Multi-Label Learning\", ICML 2024.\n\n\n**2. Response to the Essential Reference.**\n\nThe literature [2] derived tight bounds with a logarithmic dependency on $c$ for Hamming loss with KNN under the smoothness assumption of the regression function and multi-label margin and sparsity assumptions and also derived tight bounds with a logarithmic dependency on $c$ for Precision@$\\kappa$ under the margin condition and the smoothness assumption. The margin condition ensures that the obtained bounds with a faster convergence rate. In our work, the local loss function space is the key to obtaining bounds with a faster convergence rate. The smoothness condition with respect to the $\\ell_\\infty$ norm in literature [2] is a variant of Holder-continuity. We also find that the $\\ell_\\infty$ norm has a positive effect on obtaining tight bound with a weaker dependency on $c$, i.e., tight bounds with a logarithmic dependency on $c$ can be derived for $\\ell_\\infty$ Lipschitz losses. However, how to improve the convergence rate of the bounds for Lipschitz losses is still an open problem, which we will further explore in future work. We will incorporate these discussions into the paper in an appropriate manner.\n\n[2] Regret Bounds for Multilabel Classification in Sparse Label Regimes. NeurIPS 2022.\n\n**3. Response to the Suggestion.**\n\nIn order to avoid the possibility of truncation in understanding, we will adjust Definition 3.2 to $\\ell_p$ norm covering number instead of listing the $\\ell_2$ norm and $\\ell_\\infty$ norm covering number separately in the definition.", "claims_and_evidence": "Mostly seems sound, but I have a question.\nZhang & Zhang 2024, states in the introduction, remark 3.8, and remark 3.18 that their bound is also independent of c.\nBut in this paper, you only mention sqrt(c) factor bound in the related work section for Zhang & Zhang. \nAm I missing something? It would be good to state the improvement.", "methods_and_evaluation_criteria": "No experiments.", "theoretical_claims": "I did not go over the proofs.", "experimental_designs_or_analyses": "No experiments.", "relation_to_broader_scientific_literature": "I think this is well discussed in the introduction and related works.", "essential_references_not_discussed": "I recommend considering discussing the paper,\nBusa-Fekete, Róbert, et al. \"Regret bounds for multilabel classification in sparse label regimes.\" Advances in Neural Information Processing Systems 35 (2022), since the paper discusses obtaining fast rates (or ultra fast rates)  in multi-label setting, which is an important contribution of the paper.", "other_strengths_and_weaknesses": "I find the paper well grounded.", "other_comments_or_suggestions": "I think some part of definition 3.2 is cut-off around line 166.", "questions_for_authors": "I mentioned by question in \"Claims And Evidence\" above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "rl7NhDWynJ", "reviewer": "Reviewer_ZadH", "summary": "This paper investigates the generalization bound of multi-label loss functions. Specifically, for smooth base loss functions, the authors improve the generalization bounds by removing the dependency on the number of labels $c$. By exploiting local Rademacher complexity, the authors further improve the bound from $\\tilde{O}(1/\\sqrt{n})$ to $\\tilde{O}(1/n)$. In addition, they. also derive tight bounds for Macro-Averaged AUC.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your constructive comments and active interest in helping us improve the quality of the paper.\n\nThe following are our responses to the Questions:\n\n**1. Response to Weakness 1.**\n\nAs the reviewer commented, the theoretical results for unbounded base losses need to be further explored in the future to develop new theoretical techniques to cover this situation. Under the new theoretical analysis method, although the smoothness of the cross-entropy loss may be difficult to hold for models with large capacity, the Lipschitz continuity of the cross-entropy is often established, i.e., tight bounds with no dependency on $c$ for cross-entropy loss can be obtained. However, improving the convergence rate of its bound with respect to $n$ is still an urgent open problem to be solved. In the future, we will further study the bounds with a faster convergence rate for unbounded and Lipschitz base losses. \n\n**2. Response to Weakness 2.**\n\nSince the $\\widetilde{O}(\\frac{1}{\\sqrt{n}} )$ and $\\widetilde{O}(\\frac{1}{n} )$ bounds in our theoretical results is independent of the number of labels, **up to logarithmic terms**, the dependency of the bounds here on $c$ is logarithmic. We use $\\widetilde{O}$ to omit the logarithmic terms since the logarithmic dependency is very weak. However, there is no contradiction between the theoretical results and empirical intuition. The increase in $c$ will affect the difficulty of learning, but the empirical success of multi-label methods suggests that the increase in $c$ have limited impact on the difficulty of learning, which means that the ideal bound should not be strongly dependent on $c$.\n\n**3. Response to Question 1.**\n\nIf there are real numbers $s_1, \\ldots, s_p$ such that for each $\\delta_1, \\ldots, \\delta_p \\in  \\\\{-1, +1\\\\}$ there exists $f \\in \\mathcal{F}$ with \n $$\n\\delta_i\\left(f(\\boldsymbol{x}_{i})-s_i\\right) \\geq \\epsilon, \\quad \\forall i = 1, \\ldots, p.\n$$\n We say that $s_1, \\ldots, s_p$ witness the shattering.\n \n \n**4. Response to Question 2.**\n\nThe multiplicative factor of 2 comes from the use of Lemma A.8, which can also be understood through its proof process. The result can often be shown through some derivation as follows:\n\n$$\nR(f) \\leq  \\widehat{R}_{D}(f) +  \\widetilde{O}(1/n + \\sqrt{R^* / n} ) ,\n$$\n\nwhere $R^* = \\inf_{f\\in \\mathcal{F}} R(f)$. This means that in the separable case ($R^* =0$), the bound can be improved to a $\\widetilde{O}(1/n)$ rate. The multiplicative factors often appear in bounds based on local Rademacher complexity, as also shown in literature [1-3], etc.\n\n\n[1] Local Rademacher Complexity-based Learning Guarantees for Multi-Task Learning, JMLR 2018.\n\n[2] Towards Sharper Generalization Bounds for Structured Prediction, NeurIPS 2021.\n\n[3] Generalization Analysis for Ranking Using Integral Operator, AAAI 2017.", "claims_and_evidence": "The theoretical claims are.supported by proofs and comparisons with previous works.", "methods_and_evaluation_criteria": "NA.", "theoretical_claims": "I only read the proof sketches, which seem to make sense.", "experimental_designs_or_analyses": "NA.", "relation_to_broader_scientific_literature": "NA.", "essential_references_not_discussed": "NA.", "other_strengths_and_weaknesses": "**Strengths.**\n1. This paper is overall well written, with sufficient discussions on the differences from previous works.\n2. The derived bounds are tighter removing the reliance on the number of classes, while introducing no additional strong assumptions.\n\n**Weakness.**\n1. The theoretical results do not cover unbounded base loss functions, e.g. cross entropy loss.\n2. Lack of experimental validation of the theoretical results. e.g. does the generalization gap really not depend on $c$? (Perhaps it is not possible to calculate the population risk?)", "other_comments_or_suggestions": "NA.", "questions_for_authors": "1. Definition 3.3. The fat-shattering dimension seems to depend on the witnesses $s_1,\\ldots,s_p$. What are the meanings of these witnesses? \n2. Theorem 5.5. The population risk $R(f)$ is bounded by $2\\hat{R}_D(f)$ instead of $\\hat{R}_D(f)$. Does it mean that this bound is somewhat loose? As $n\\to\\infty$, the bound becomes $R(f)\\leq 2R(f)$, which is not tight.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "dLgV1NlNly", "reviewer": "Reviewer_tz9D", "summary": "The paper focuses on the theoretical analysis of multi-label learning, particularly in the context of smooth base loss functions. The authors introduce novel vector-contraction inequalities and derive tighter generalization bounds for multi-label learning with smooth base loss functions. These bounds exhibit improved dependency on the number of labels, reducing it to logarithmic terms, and demonstrate faster convergence rates with respect to the number of examples. The paper also discusses the application of these bounds to various multi-label learning methods, highlighting how these results provide general theoretical guarantees for the generalization performance of multi-label learning, especially for methods with smooth base loss functions.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your constructive comments and active interest in helping us improve the quality of the paper.\n\nThe following are our responses to the Questions:\n\n**1. Response to Weakness 1.**\n\nAs the reviewer pointed out, when there is some type of label correlation between the labels of the dataset, the label distribution may satisfy some potential constraints, which may correspond to some additional assumptions such as sparsity assumptions or norm regularization constraints. Therefore, when dealing with these specific problems, we need to introduce some additional assumptions to adjust our analysis and explicitly introduce these potential label correlations into the generalization analysis. This is still an open problem and we will further explore related work in the future.\n\n**2. Response to Weakness 2.**\n\nWhen dealing with large-scale datasets, in practice, one often consider introducing specific strategies in the label space to deal with extremely large number of labels. In generalization analysis, it is shown that introducing effective and general specific strategies is not only an important open problem in theory, but also extremely challenging in practice. Therefore, it is indeed necessary to further introduce effective assumptions to better explicitly analyze the role of key factors in generalization that can effectively deal with challenging problems with large number of labels and large-scale datasets.\n\n**3. Response to Suggestions.**\n\nIn line 313, the subscript $S$ in the inequality should be changed to $R$. \n\nIn line 1026 to 1030, this is a repeated typo and we will remove one of them.\n\n**4. Response to Q1.** \n\nAs we replied above, effective analysis for more specific problems requires further explicit introduction of valid assumptions to reveal the impact of these setting-dependent factors on the bound. For example, for high-dimensional sparse data, one may need to introduce sparsity assumptions into the analysis, thereby inducing bounds that are weakly dependent on the sparsity rate and the number of key labels.\n\n**5. Response to Q2.**\n\nDifferent types of label correlations have an important impact on generalization analysis. How to explicitly introduce them in generalization analysis is a crucial open problem. Traditional Lipschitz methods do have more advantages since they are easier to satisfy the conditions. For example, for deep models, the smoothness of base losses also involves the boundedness of the second-order derivative of the function, which is often difficult to guarantee in deep models, while Lipschitz continuity is often established. Experimental verification can be considered from two aspects. On the one hand, verify whether the functions selected by the algorithm have a small error and whether the generalization performance of the small error functions is better. On the other hand, verify whether the smoothness of the model function can be guaranteed by some regularization, and explore which regularization-induced inductive biases are more effective for generalization in practice, and promote further theoretical research.\n\nWe will incorporate these discussions into the paper in an appropriate manner.", "claims_and_evidence": "Yes. Specifically, the authors derive theoretical support for tight generalisation bounds and more efficient convergence rates for smooth basis loss functions in multi-label learning by means of mathematical proofs and local Rademacher complexity analyses. The authors also give a proof of broad applicability.", "methods_and_evaluation_criteria": "Yes. The theoretical analysis presented in the article, especially the tight generalisation bounds based on the common smoothed basis loss function, directly addresses the generalisation problem in multi-label learning.In addition, the generalisation bounds proposed in the article not only consider the effect of the number of labels on the model, but also improve the traditional Rademacher complexity analysis by localising the Rademacher complexity, providing faster convergence for large-scale datasets.", "theoretical_claims": "Yes. 1. A new vector contraction inequality. This proof is based on the existing Rademacher complexity theory and an extension of local Rademacher complexity that rationally simplifies the otherwise complex multi-label learning problem by smoothing the basis loss function. 2. Application of local Rademacher complexity. This proof describes the complexity of samples in multi-label learning more finely by introducing local complexity.", "experimental_designs_or_analyses": "No, the paper is purely a theoretical derivation without any numerical experimental analysis.", "relation_to_broader_scientific_literature": "Earlier generalisation analyses on multi-label learning, e.g. Wu and Zhu (2020) based on the loss function of Lipschitz continuity can derive generalisation bounds, but the part of the bounds that depends on the number of labels is linear.This thesis successfully reduces the effect of the number of labels on the generalisation bounds, in particular so that the generalisation bounds no longer depend on the number of labels but are only related to the logarithmic term, demonstrating a significant theoretical advance. Bartlett et al. (2005) proposed local Rademacher complexity and showed that it can provide faster convergence than traditional Rademacher complexity.In this thesis, the speed of convergence and generalisation bounds in multi-label learning are improved by introducing the local Rademacher complexity, which provides a faster convergence speed than the traditional method, and the effectiveness of this method is verified theoretically. Wu et al. (2023) proposed a generalisation analysis on macroscopic AUC and explored the effect of label imbalance on the results, without delving into how to reduce the dependence of the number of labels on the generalisation bounds.In this thesis, by combining the Lipschitz and smooth basis loss functions, tight generalisation bounds for macroscopic AUC are given and there is no dependence on the number of labels, which provides a new theoretical guarantee to deal with the label imbalance problem.", "essential_references_not_discussed": "No.I keep up with the literature in this area.", "other_strengths_and_weaknesses": "1. A new vector contraction inequality is introduced in the article to derive tight generalisation bounds for multi-label learning. the proof method is very rigorous, but in practice, if the label distribution of the datasets does not exactly match the assumptions, it may affect the applicability of the method.\n2. Although the introduction of local Rademacher complexity provides an improvement in convergence speed, the estimation of local complexity may face high computational costs, especially when the number of labels and sample size are very large.The correctness and practical feasibility of the proof relies on being able to efficiently estimate the local complexity and this may be challenging on large-scale datasets.", "other_comments_or_suggestions": "1. The subscript on the left side of the inequality in line 313 is incorrect？\n2. The inequality in line 1026 to line 1030 are the same. Please check again.", "questions_for_authors": "1. The universality of generalisation bounds, although theoretically proven, might there be some limitations for some special types of multi-label problems? Such as high-dimensional sparse data or highly unbalanced label scenarios.\n2. The article provides a comparison with existing methods and demonstrates clear improvements.However, inter-label correlation may affect the theory in specific cases. For example, is the traditional Lipschitz approach likely to be more advantageous in the case of strong label correlation? How can more experiments be designed to verify the validity of these theories in practical applications.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "vVp0O6lze5", "reviewer": "Reviewer_Wn57", "summary": "This paper provide general theoretical guarantees for the generalization of multi-label learning. By developing and leveraging a novel vector-contraction inequalities for smooth base losses, the author induces tight generalization bounds for multi-label learning that have no dependency on the number of labels. Besides, the author develops novel local vector-contraction inequalities for smooth base losses, it can have a bound with faster convergence rate. A tight generalization bounds with no dependency on the number of labels is derived for Macro-Averaged AUC by considering both Lipschitz continuity and smoothness of base loss functions.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your constructive comments and active interest in helping us improve the quality of the paper.\n\nThe following are our responses to the Questions:\n\n**1. Response to Weakness.** \n\nWe will add concrete examples of multi-label methods after the definition of the function class to improve readability and practical interpretation. For example, the DNN-based multi-label method named CLIF [1], which proposes to learn label semantics and representations with specific discriminative properties for each class label in a collaborative way, can be expressed in our function class as: \n\n$$\n\\phi_j(\\boldsymbol{x})= \\sigma_{ReLU} \\\\{ W_5 \\cdot \\left[  \\sigma_{ReLU} (W_4 \\boldsymbol{x}) \\odot  \\sigma_{sig} (W_3 \\psi(Y)_j) \\right] \\\\} .\n$$\n\nThe label embeddings $\\psi(Y)$ can be denoted by $\\sigma_{ReLU}(\\tilde{A} \\sigma_{ReLU} (\\tilde{A} Y W_1) W_2)$, where $\\tilde{A}$ denote the normalized adjacency matrix with self-connections, $Y$ is the node feature matrix of the label graph, $\\sigma_{ReLU}$ is the ReLU activation, $\\sigma_{sig}$ is the sigmoid activation, $\\odot$ is the Hadamard product, $W_i$ are the parameter metrices, $i \\in [5]$. \n\nIn addition, a class of multi-label methods based on the strategy of label-specific representation, which facilitates the discrimination of each class label by tailoring its own representations, can be formalized in our function class. For example, the wrapped label-specific representation method [2], which presents a kernelized Lasso-based framework with the constraint of pairwise label correlations for each class label, can be expressed in our function class, where $f_j$ is the kernelized linear model and the constraint $\\alpha(\\boldsymbol{w}) $ is $\\|\\boldsymbol{w}_j\\|_1 \\leq \\Lambda$ for any $j \\in [c]$, and each label also has the property of sharing which is reflected by the additionally introduced constraint \n\n$\\sum_i^c (1- s_{ji}) {\\boldsymbol{w}_j}^\\top \\boldsymbol{w}_i \\leq \\tau$, \n\nwhere $s_{ji}$ is the cosine similarity between labels $y_j$ and $y_i$. \n\nBesides, the function class here is applicable to the typical Binary Relevance methods for multi-label learning, where different methods correspond to different nonlinear mappings $\\phi_j$.\n\n[1] Collaborative Learning of Label Semantics and Deep Label-Specific Features for Multi-Label Classification, TPAMI 2022.\n\n[2] Multi-Label Classification with Label-Specific Feature Generation: A Wrapped Approach, TPAMI 2022.\n\nIn addition, we will also provide additional explanations on the key ideas in the theoretical proof to help readers better understand the ideas. Please refer to our **Response 3 to Reviewer XSTz**.\n\n\n**2. Response to Q1.** \n\nOur theoretical results require that the base loss is bounded, and therefore cannot cover the case where the base loss is cross-entropy loss. In the future, we will further study the bounds with a faster convergence rate for unbounded and Lipschitz base losses. In addition, for some methods involving specific label correlations, when using our theoretical results to analyze these specific methods, it is necessary to introduce additional assumptions induced by these specific label correlations in the generalization analysis, so as to better reveal the impact of these setting-related factors on the bound. However, how to explicitly introduce label correlations in generalization analysis is still a crucial open problem. We will further explore related work in the future. We will incorporate these discussions into the paper in an appropriate manner.\n\n**3. Response to Q2.**\n\nAs the reviewer suggested, a better presentation of related work and comparisons between them through a summary table can improve the readability of the paper and make the contribution of our results clearer. We will add a summary table in the revised version from the perspectives of loss function, additional assumption, order of bounds, and reference.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "Incorrect statements are not observed in the key claims (e.g., tighter bounds for smooth base losses, faster bounds,  tighter bounds for macro-averaged AUC).", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "This paper introduces vector-contraction inequalities for smooth base loss functions, rather than Lipschitz ones. It shows tight generalization bounds for multi-label learning that have no dependency on the number of labels.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Strengths\n\n- This paper extend the previous work and introduce novel vector-contraction inequalities for smooth base losses.\n- This paper achieves the SoTA generalization bounds and also reveal the relationship between Macro-Averaged AUC and class-imbalance.\n- Compared with prior methods, this apper removes the dependency on label count and achieves faster bounds.\n\nWeaknesses\n\n- This paper is highly technical and not reader-friendly, it would be great to show some intuitive explanations or some demos to help the reader understand the key ideas.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "- Any limitations when the results are applied to the real-world multi-label learning scenarios?\n\n- Since there are many related papers mentioned and compared with the derived results, a more clear and explicit comparison like a summary table with the results and limitations can make the contribution clearer.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This is a theoretical paper focused on multi-label classification. The authors derive generalization bounds for a specific class of classifiers, which depend only logarithmically on the number of labels.

The Reviewers are generally positive about the submission. However, they raised several concerns, including the limited model class and the specific class of loss functions to which the results apply, as well as the lack of references to related work (e.g., Busa-Fekete et al., 2022) and the unclear connection to results presented in (Zhang and Zhang, 2024). If accepted, the paper should be thoroughly revised to address these issues, incorporating the Reviewers' feedback and the clarifications provided by the Authors during the rebuttal phase.
Decision: Accept (poster)