Generalization Analysis for Label-Specific Representation Learning
Authors: Yifan Zhang
Min-Ling Zhang
Venue: NeurIPS 2024 spotlight (2024)
Keywords: Learning Theory
Multi-Label Learning
Primary area: learning_theory

Abstract: Label-specific representation learning (LSRL), i.e., constructing the representation with specific discriminative properties for each class label, is an effective strategy to improve the performance of multi-label learning. However, the generalization analysis of LSRL is still in its infancy. The existing theory bounds for multi-label learning, which preserve the coupling among different components, are invalid for LSRL. In an attempt to overcome this challenge and make up for the gap in the generalization theory of LSRL, we develop a novel vector-contraction inequality and derive the generalization bound for general function class of LSRL with a weaker dependency on the number of labels than the state of the art. In addition, we derive generalization bounds for typical LSRL methods, and these theoretical results reveal the impact of different label-specific representations on generalization analysis. The mild bounds without strong assumptions explain the good generalization ability of LSRL.

Generalization Analysis for Label-Specific Representation Learning
Yi-Fan Zhang Min--ing 2.3+
1 School of Cyber Science and Engineering, Southeast University, Nanjing 210096, China
School of Computer Science and Engineering, Southeast University, Nanjing 210096, China Key Laboratory of Computer Network and Information Integration (Southeast University). Ministry of Education, China fyfzh, zhangml) @seu. edu.
Abstract
Label-specific representation learning (LSRL), i.c., constructing the representation with specific discriminative properties for each class label, is effective strategy multi-label learning. However, the generalization
to improve the performance analysis of LSRL is still in its infancy. The existing theory bounds for multi- label learning, which preserve the coupling among different components, are invalid for LSRL. In attempt overcome this challenge and make up for the gap in the generalization theory of LSRL, we develop novel vector-contraction inequality and derive the generalization bound for general function class of LSRL with weaker dependency on the number of labels than the state of the art. In addition, we derive generalization bounds for typical LSRL methods, and these theoretical results reveal the impact of different label-specific representations on generalization analysis. The mild bounds without strong assumptions explain the good generalization ability of LSRL.
Introduction
Multi-label learning has received continued attention in machine learning community due to its widespread encounters in real-world applications, where each object is represented by single instance associated with multiple class labels (Zhang and Zhou 2014 Liu et al. 2022]. The goal of multi-label learning is model real-world objects with multiple semantics. It has made important advances in multimedia content annotation [Cabral et 2011 You et al. 2020 text categorization [Rubin al., 2012 Xun et al., 2020), bioinformatics (Cesa-Bianchi et al. 2012 Chen et al. 2017] and other fields Yu et al. 2005). The failure to take into account that each class label may possess its own discriminative properties results in the most straightforward strategy which exploits the identical representation of instance for dealing with multi-label data being perhaps suboptimal [Zhang and Wu 2015] Huang et al. [2066] Hang and Zhang 2022]. In recent years, label-specific representation learning (LSRL) [hhang and Wu 2015] has been proposed to facilitate the discrimination of each class label by tailoring its own representations. Due to its ability to model distinct characteristics for each class label, LSRL has become effective strategy to improve the performance of multi-label
learning [Huang et al. 2013 2016 2018 Yu and Zhang 2022 Hang and Zhang 2022 Hang et al. 2022). Although L.RRL. has achieved impressive empirical advances in lalti-label learning, the problem of understanding LSRL. theoretically remains completely under-explored.
In recent years, efforts to explain why multi-label models generalize well is important open problem in multi-label learning community. The empirical success LSRL makes the generalization
"Corresponding author
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

analysis of LSRL an important problem in multi-label learning. However, existing theoretical results and analysis methods are not applicable to LSRL. which leads to a serious lack of progress in its generalization analysis. A satisfactory and complete study of the generalization analysis for LSRL should include two aspects: 1) the dependency of the generalization bounds on the number of labels (i.e.. c) should be weaker than square-root, and 2) the relationship among components should be decoupled in the generalizability analysis. First, existing bounds with a linear or square-rool dependency on are difficult to explain empirical success of multi-label learning. For example, the bounds with a linear dependency on e are vacuous (i.e., no longer less than 1) for commonly used multi-label datasets such as CAL500, corel5k, revl-sl, Corel16k-s1, delicious, iaprte 12, espgame, etc., since c is larger than vn (the number of examples) for these datasets. The bounds with a linear or square-root dependency
are vacuous for commonly used extreme multi-label datasets such as Wiki 10, Amazon-670K, etc., since c is larger than n. The above failure of existing bounds for multi- label learning also applies to ISRLL. Hence, this suggests that only the bounds with weaker dependency on e can provide effective theoretical guarantees. Second, existing theoretical results preserve the coupling among different components [Lei et al.) [015 Wu and Zhu 2020, Wu et al. 2021a b). However, LSRL decomposes the multi-label learning problem into multiple binary classification problems, which means that the relationship among different components needs to be decoupled in the generalization analysis. Hence, we need to develop new analysis methods for LSRL. As a matter of fact, theoretical research on LSRL can also promote better understanding of multi-labe learning.
In this paper, we derive novel and tighter bounds based on the Rademacher complexity for LSRL. Specifically, we develop novel vector-contraction inequality with the assumption that the loss function is Lipschitz continuous w.r.t. the &o norm, then we derive the bound for general function classes of LSRL with dependency the art. In addition, we also analyze the bounds for several typical LSRL methods, and we show that the construction method of label-specific representations will affect the generalization bound.
c, up to logarithmic terms, which is tighter than the state of
Our bounds for LSRL improve the dependency on c. Major contributions of the paper include:
We develop a novel vector-contraction inequality for &oo norm Lipschitz continuous loss, which overcomes the limitations of existing theoretical results and provides a theoretical tool for the generalization analysis of LSRL.
We derive bounds for general function classes of LSRL with a weaker dependency on c than the state of the art, which provides a general theoretical guarantee for LSRL.
We derive bounds for typical LSRL methods, which reveals the impact of different label- specific representations on the generalization analysis. The theoretical techniques and results on m-maa clustering, Lasso, and DNNs involved here may be of independent interest.
2 Related Work
2.1 Multi-Label Learning
Multi-label learning is one of the most studied and important machine learning paradigms in practice (Zhang and Zhou| 2014 Liu et al., 2022]. To cope with the challenge that the output space is exponential in size to the number of class labels, modeling label correlations is adopted as a feasible strategy to facilitate the learning process. Generally speaking, existing methods can be roughly grouped into three major categories based on the order of label correlations being considered, namely first-order methods [Boutell et al. 2004 Zhang and Zhou| [0077] Zhang et al. 2018 which tackle multi-label learning problem by decomposing it into a number of independent binary classification problems, second-order methods [Elissceff and Weston 2001 Zhu et al., 2018 Sun and Zhang 2021] which tackle multi-label learning problem by considering pairwise relationships between labels, and high-order methods [Ji et al. 2010 Xu and Guo 2021] which tackle multi-label learning problem by exploiting high-order relationships among labels. Recent years, benefiting from the good generalization performance of deep learning, deep methods such as recurrent neural networks Yazici
(Chnon et al. 2, graph neural networks (Chen et al. 2020). , and embedding models (Bai et al. 2020 Dahiya et al. 2021 have been explored to model label correlations.
As a complement to the exploitation of label correlations. label-specific representation learning (L.SRI)) have been proven to be another effective strategy to improve multi-label learning by ma- nipulating the input space. Existing methods can be roughly grouped into three major categories
2

---

based on the construction method of label-specific representations, i.c. prototype- based label-specific representation transformation methods [Zhang and Wu 2013 Zhang et al. 2015 Weng et al. 2018
Guo et al. 2019 Zhang and Li [021] which generate label-specific representations by treating the
prototypes each class label as the transformation bases, label-specific feature selection methods [Huang et al. 2015 2016 2018 Weng et al. 2020 Yu and Zhang [022] which generate label-specific representations by retaining a feature subset as the most pertinent features for each class label, and deep label-specific representation methods (Hang and Zhang 2022 Hang et al. 2022) which learn label-specific representations in an end-to-ent manner by exploiting deep models. In particular, k-means clustering -bsed LSRL, i.e., LIFT (Zhang and Wu 2015], is the representative method of prototype- based label-specific representation transformation methods, which constructs label-specific representations by querying the distances between the original imputs and the cluster centers for each class label. Lasso-based LSRRI, i.e., LLSF (Huang et al., 2016], is the representative method of label-specific feature selection methods, which presents Lasso-based framework with the constraint of pairwise label correlations for each class label. DNN-based LSRR,, i.e CLIF (Hang and Zhang 2022]. is the representative method of deep label-specifie representation methods, which proposes to learn label semantics and label-specific representations in a collaborative way. In this paper, we will analyze the generalization bounds of these three representative LSRL methods.
2.2 Generalization Bounds for Multi-Label Learning
Dembczynski et al. (2100) derived the relationship between the expectations of Hamming and Subset loss based on the regret analysis on Hamming and Subset loss, and Dembezynski et al. [2012
further performed regret analysis on Ranking loss, which provided preliminary theoretical insights
for understanding Hamming, Subset and Ranking loss. With the typical vector-contractio inequality
[Maurer| 2016] (i.e., assume that the loss function is Lipschitz continuous w.r.t. the Lg norm). one can obtain generalization bounds of order O(c/ /n) for multi-label learning. Wu and Zhu (2020). Wu et al. (021a] showed that the order of the generalization bounds for Subset loss, Hamming Loss and reweighted convex surrogate univariate loss can be improved to O(vc/n), which preserved the coupling among different components and exploited the relationship between loss functions. Liu et al.
(2018) also obtained a generalization bound of order O( /c/n) ) for the dual set multi-label learning, which was analyzed under the margin loss and kernel function classes.
Wu et al. 2021b] derived generalization bound of order ((log(nc)/no) for norm regularized kernel function classes with the assumptions that the loss function is Lipschitz continuous w.r.t. the foo norm and the regularizer is o-strongly convex with respect to some norms. Yu et al.) (2014) obtained generalization bound of order O(1/ /n) for trace norm regularized linear function classes with Decomposable loss. Xu et al. [016)] used the local Rademacher complexity to derive a generalization
bound of order Ö(1/n) for trace norm regularized linear function classes with the assumption that the singular values of the weight matrix decay exponentially. These theoretical results all preserved the coupling among different components. In addition, Wu et al. (2023) obtained (11/ bounds for Maero-Averaged AUC and gave thorough discussions about its relationships with the label-wise class imbalance, which transformed the macro-average maximization problem in multi-label learning into the problem of learning multiple tasks with traph-ddpendent examples. Here we obtain ((1/ VV) bounds with the state-of-the-an dependency on the number of labels for LSRL function classes under the assumption that the loss function is Lipschitz continuous w.r.t the foo norm.
3 Preliminaries
Let [n] = [1) for any natural number n. In the context of multi-lahel learning, given a dataset D D= (x11 11) ...., (Ix, (i..d.) from probability distribution P on X' x V, where X' C Rd denotes the d-dimensional input space and Y' denotes the label space with c class labels, I E X, y E E S (-1,+1)", i.e., each y= (y1..... .Be) is a binary vector and yj = 1 (y, = - 1) denotes that the j-th label is relevant (irrelevant), j E [c]. The task of multi-label learning is to learn multi-label classifier h E H X + (-1,+1} which assigns each instance with set of relevant labels. A common strategy to learn a vector-valued function f = (f1, ..,, fa) 2' + R and derive the classifier by thresholding function which divides the label space into relevant and irrelevant label sets.
)n)} with n examples which are identically and independently distributed
3

---

For any vector-valued function f x R", the prediction quality on the example (æ, y) is measured F with good generalization performance from the dataset 1) by optimizing the loss E. The generalization performance measured by the expected risk: R(f) = ((.)))))((((()) (x)) (x;), y)]. We denote the empirical risk w.r.t the training dataset D as RD(f) risk as R inf fEF R( the minimizer of the optimal risk as f arg fe R(f) and denote the minimizer of the empirical risk as f arg min (f( In addition, we define the loss function space as L = (x) y) : ff E Fj, where F is the vector-valued function class.
by loss function f IR (-1,+1}++ Rt The goal of learning is to find a hypothesis
Ei=1 (ff()))) M:). We denote the optimal
3.1 Label-Specific Representation Learning
Label-specific representation learning aims construct the representation with specific discriminative properties for each class label to facilitate its discrimination process. The basic idea of LSRL is to decompose the multi-label learning problem into binary classification problems, i.e., decoupling the relationship among different components, where each binary classification problem corresponds to possible label the label space. We consider the prediction function for each label of the general form (x) (w,, Sj (() where the inner nonlinear mapping Φ corresponds to the nonlinear transformation induced by the construction method of label-specific representation, while the outer nonlinear mapping ç refers the nonlinear mapping corresponding to the classifier learned on the generated abbl-specific representation. We define a vector- valued function class of LSRL as follows:
F = x + (() (ax (..( Sc(x)),
[ (x) = h, (0) - w/ (()) = (w.,...., w.) E Rdx aw S A,3(G()) - A, S C EX, E (, 0}, (I)
where a represents a functional that constrains weights, 3 represents a functional that constrains
nonlinear mappings Sj- represents functional that constrains nonlinear mappings Φj.
3.2 Related Evaluation Metries
A number of evaluation metrics are proposed to measure the generalization performance of different multi-label learning methods. Here focus on commonly used evaluation metrics, i.c., Hamming Loss, Subset Loss, Ranking Loss and Decomposable Loss. However, the above mentioned loss functions are typically 0/1 losses, which are actually hard handle in optimization. Hence, one usually consider their surrogate losses, which are defined as follows:
LH (f(f(z)))) = Σ lo (z))
Hamming Loss
where the base convex surrogate loss la can be various popular forms, such the hinge loss, the logistic loss, the exponential loss and the squared loss.
Subset Loss
{s(f(x), y) = max (6 (x)f(()))).
JEle
Ranking Loss
(n(f(x))))
Σ
Σ 4 (fp(() faaa))-)(())))) fx())
Y
PEY gEY
where + (Y-) denotes the relevant (irrelevant) label index set induced by y, and denotes the cardinality a set.
Decomposable Loss
Ep (p(((x))))
Σ ls (z))
3.3 Related Complexity Measures
Here we introduce the complexity measures involved in theoretical analysis. The Rademacher complexity is used to perform generalization analysis for LSRL.

---

Definition 1 (Rademacher complexity), Let G be class of real-valued functions mapping from X' to R. Let D = (2 be set with n i.i.d. samples. The empirical Rademacher complexity over G is defined by RD(G) = Ee ssupee Ei=1 cgg (z:)]. where C1,...,Cn are i.i.d. Rademacher random variables, and we refer the expectation R(G) = Ep (9) as the Rademacher complexity of G. In addition, we define the worst-cuse Rademacher complexity as RG) = supnex" (g)),, and its expectation is denoted as Rig)= = ED RR,
In multi-label learning. E is a pector-valued function, which makes traditional Rademacher complexity analysis methods invalid. Hence, we need to convert the Rademacher complexity of a loss function space associated with the vector-valued function class F into the Rademacher complexity of a tractable scalar-valued function class. The Rademacher complexity can be bounded by other scale-sensine sensitve complexity measures, such as the covering number and fat-shattering dimension (Srebro et al., 20100 Zhang and Zhang 2023 The relevant definitions are provided in the appendix.
General Bounds for LSRL
In this section, we first introduce the assumptions used. Then, we develop a novel vector-contraction inequality for the Rademacher complexity of the loss function space associated with the vector-valued function class F. Finally, with the novel vector-contraction inequality, we derive the generalization bound for general function classes of LSRL with no dependency on the number of labels, up to logarithmic terms, which is tighter than the state of the art. The detailed proofs of the theoretical results in this paper are provided in the appendix.
Assumption 1. Assume that the input features, the loss function and the components of the vector- valued function are bounded: ||ær S R, E(.,-) S M, 15,()) S B for i E [n], j E [c] where R 0, M > 0 and B >> 0 are constants.
Assumption 2. Assume that the loss function is p-Lipschitz continuous w.r.t. the foo norm, that is:
(K) s fl)f(x) f' (x))l
where p > 0, ||t|| maxje (s) ftrl = tt).
Assumption D and 2 mild assumptions. For Assumption 1 normalization of input features is common data preprocessing operation. When we consider the function class I.. we often use the assumptions ||w, < A. (+)(12 < A for any j E [c] to replace the boundedness of the components of the vector-valued function, i.e., B == AA. For Assumption the Lipschitz continuity w.r.t. the lo norm has been considered in some literature (Foster and Rakhlin [019 Lei et al.) 2019 Wu et al.) 2021b). The following Proposition [ further illustrates that the commonly used loss functions in multi-label learning actually satisfy Assumption
Proposition 1. Assume that the base loss Ea defined in Subsection 3.2 is p-Lipschitz continuous, then the surrogate Hamming Loss p-Lipschitz w.r.. the Eo norm, the surrogate Subset Loss is u- u-Lipschitz w.r.t. the toe norm, the surrogate Ranking Loss is 24-Lipschitz w.r.t. the foe norm, and the surrogate Decomposable Loss is eu-Lipschitz w.r.t. the Loo norm.
We define a function class P consisting of projection operators Py : R + R for any j E [c] which project the c-dimensional vector onto the j-th coordinate. Then, we have P(F) {(j, x) > P. (fx)) (f))) = [a(,,, FF (j, ar) E [c] x X). The projection function class decouples the relationship among different components. With the assumption of f.o norm Lipschitz loss and the above definitions, we show that the Rademacher complexity of the loss function space associated with F can be bounded by the worst-case Rademacher complexity of the projection function class P(F). We develop the following novel vector-contraction inequality: 7 Let Assumptions 7 and
Lemma 1. Let F be vector-valued function class of ISRLI. defined by hold. Given a dataset D of size n. Then, we have
M
RD(C) <
1og (8e2n log
pB
where RD(C)= = E. [SuPIEC.SEF + Ei ell (f())) is the empirical Rademacher complexity of the loss function space associated with F, and is the worst-case Rademacker complexity of the projection function class.
5

---

Proof Sketch. First, the Rademacher complexity of the loss function space associated with F can be bounded by the empirical fox norm covering number with the refined Dudley's 's entropy integral inequality. Second, according to the Lipschitz continuity w.r.t the for norm, the empirical fox norm covering number of F can be bounded by that of P(FF). Third, the empirical foc 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). Hence, the problem is transferred to the estimation of the worst-case Rademacher complexity. Finally, we estimate the lower bound of the worst-case Rademacher complexity of ((F), and then combined with the above steps, the Rademacher complexity of the loss function space associated with F can be bounded.
With the vector-contraction inequality above, we can derive the following tight bound for LSRL:
Theorem 1. Let F be veltor- function class of LSRL defined by (7). Let Assumptions Lan hold. Given a dataset D of size n. Then, for any 0 < ó < 1, with probability at least 1 - 8, the Following holds for any f F:
R(f) S. RD(f)+ + 24V2pAA (1 log (8c2n3
log Myn p
log 2
3.M
V
n
2n
Proof Sketch. We first upper bound the worst-case Rademacher complexity Rno(P(FF). and then combined with Lemma [ the desired bound can be derived.
Remark 1. Although Lemma 1 shows a factor of Vc, the term Rnn((P(F) I AA/VIC. which makes the Rademacher complexity of the loss function space associated with F (i.e., RD(C)) actually independent on c, up to logarithmic terms, and results in a tighter bound than the existing O(c/ vn) and O O(/c/n) bounds with a faster convergence rate On). The bound in Theorem 7 with no dependency on can provide general theoretical guarantee for LSRL, even for extreme multi-label learning where the number of labels far exceeds the number of examples {Yu et al.)
2014 Prabhu and Varma 2014 Yen et al., 2016 Liu and Shen 2019% since it is easy to get that log c is much smaller than vn. The main challenge of generalization analysis for LSRL is that existing theoretical results and existing generalization analysis methods for multi- learning are not applicable to LSRI., Specifically, existing theoretical bounds often involve the typical vector- contraction inequality |Maurer 2016) for l2 Lipschitz loss: E2 [sup n
1/2 -E=1<((f (æ:)) S
V2yB. (supFEr to EE=EE Jz (ax)) which will lead to bounds with a linear dependency on e for multi-label learning. Lei al.) (2015). Wu and Zhu [2020]. Wu al. [2021a) improve the dependency of the bounds on c to square-rood which preserve the coupling among different components reflected by the constraint | < A. Lei et al. [2019] also improves the bounds of multi-class classification to be independent on c (up to logarithmic terms) for Eo Lipschitz loss by preserving the coupling among different components, and Wu et al. (2027b) further generalizes these results to multi-label learning. However, LSRL decomposes the multi-label learning problem into binary classification problems, which means that the relationship among different components needs to be decoupled in the generulization analysis. Hence, how to develop novel vector-contraction inequalities that can induce ((1/ Vn) bounds and deal with the case of decoupling the relationship among different components are the two most critical difficulties in deriving tighter bounds for LSRL. The introduction of the projection function class plays an important role in solving these two difficulties. It improves the vector-contraett relationship among different components (which is also reflected by the constraint ||w S A for any (c)) Our tighter Ö(L/ vT) bound in Theorem I with no dependency on e (up to logarithmic terms) solve the limitations of existing theoretical results for multi-label learning and can provide a general theoretical guarantee for LSRL.
inequalities by a factor of /c and decouples the
The differences in generalization bounds of different LSRL methods are mainly reflected in two aspects. On the one hand, the Lipschitz constant of the loss functions, as we proved in Proposition []] the Lipschitz constants p corresponding to different loss functions are various. On the other hand, the nonlinear mappings induced by different LSRL methods. In fact, when we analyze the generalization for LSRL,, we will further have ||<(-)]l < A == xRt (K is the Lipschitz constant of the nonlinear mappings (()) to take into account the differences or characteristics of different LSRRL methods. We provide detailed analysis for A of typical LSRL methods in the next section.

---

Generalization Bounds for Typical LSRL Methods
In this section, we analyze the generalization bounds for several typical LSRL methods, i.e., k-means clustering- based [Zhang and Wu. 2015]. Lasso-based [Huang et al. 2016 and DNN-based (Hang and Zhang 2022 LSRL methods. We show that different construction methods of label-specific representation will lead to significant differences in the constant A of the generalization bound in Theorem I For each LSRL method, we first give a brief introduction, then give its formal definition corresponding to the class of LSRL defined in T and finally derive the generalization bound.
5.1 Generalization Bounds for k-Means Clustering-Basee Based LSRL Method
As seminal work, k-means clustering- based LSRL method, i.e., LIFT [Zhng and Wu 2015]. uses k-means clustering to construct label-specific representation that effectively capture the specific characteristics each label. Specifically, first, for each label, k-means clustering is used to divide the training instances into K' clusters, and the centers of the K clusters are obtained, which is denoted as cj for the j-th label, k E [K], E [c]. Then, these K centers are used to construct the label-specific representation, i.e., in the vector-valued function class of LSRL defined by (T). dl(z, e o d. Finally, family of classifiers f, with e-Liischitz nonlinear mapping are induced based on the generated label-specific representations.
3 (z) d(x,, ei),... d(x,, <kk) ((xx,,c))_
Next, we formally define the process of k-means clustering. Here we follow some of the settings and definitions in [Li and Liu 2021]. Assume that V : X² + R4is a pairwise distance-basee function used to measure the dissimil dissimilarity between pair observations, and Z 1Z1,.... Zx] is collection of partition functions Z : X² - R, for & E [K]. The clustering framework can be cast as the problem of minimizing the following criterion:
1
ün (V, 2) n(n 1) 1,f=1,i k=1
V (æ;, 2zÿ) Zu (a:;, xz2))
over all possible functions V and ZB for he E [K]. In k-means clustering, we have V (mi; F.,) ||æ. - æ5 and Zz. (2;; æ2)) = T { (2;, 2z,) E C Ca = Te Exec. Φ, where Ci...., : CK are the partitions of the feature space X. Let gk (I,, (z, V (z)) Z& (z), and g (91,...99K) be a vector-valued function, let (g(a x')) ) = ER=1 Ik (x, x'), then RD(V, Z)
can be written as
K
(V, 2) nnn
Σ 1.f1,
Letu leulg((a,,
9k (x;, wz))
n(n 1 k=1
k=1
We then define a vector-valued function class of k-means clustering as follows: {12 x²) + g(x x') :g(#, x²) (g) (ax, x' "'',,..., 9K (2,xx²= x²));
Ih (x, x¹) = || x' 1 - (x(xx=²) E c2) x a' 0
E
where
[g((-.-) & G for & E [K] and G > 0 are constants.
We denote the function class of k-means clustering corresponding to the j-th label as GJ. With the above definitions, we can derive the tight bound for k-means clustering- based LSRL method:
Theorem 2. Let FF be a vector-valued function class of k-means clustering-base LSRL defined by 7. Let Assumptions and (2 hold. Given a dataset D of size n. Then, for any 0 < < 1, with probability least 6, the following holds for any f E F:
log
48 ASv2pRAVII (1+ logz (862((0)))) log aB
Myñ
R(f) <RD(f) + +3M
2n
VT
24 V2PKKG +
(1+
(e2 (c2n²c)
log
M M
) (8e log
M / μB
Vn
G
Remark 2. There are three key points in the generalization analysis of k-means clustering- LSRL method. 1) Since k-means clustering baasdd LSRL method is two-stage, i.e., the centers of
7

---

clusters is generated by using k-means clustering in the first stage, then these centers are exploited to generate label-specific representations which are used to learn multi-label classifier in the second stage, we cannol formally express these two stages in a closed-form expression through a composite centers generated in
function (K centers are generated by the arg min function). Furthermore, the first stage are actually used as fixed parameters rather than inputs in the second stage. Hence, in order to fully consider the capacity of the model corresponding to the first stage, it is reasonable to define the whole finntion class as the sum of the function classes F + -ett. G corresponding to the methods of these two stages. Then, combined with Lemma 7 the generalization analysis is transformed into the bounding of the complexity of the projection function class PPF Let GG). The introduction of class G induces an additional increase in complexity, i.e., the last term in Theorem 2 2) The generalization analysis of k-means clustering -banndd LSRL method involves the generalization analysis for k-means clustering. However, since the k-means clustering framework involves pairwise functions, a sequence of pairs of i.i.d. individual observation in k-means clustering is no longer independent, which makes standard techniques in the i.ddd case for traditional Rademacher complexity inapplicable for k-means clustering. We convert the non-sum-of-ii.i4 pairwise function Li.d form by using permutations in U-process [Clémençon et al. [2008]. We show that the empirical Rademacher complexity of a loss function space associated with the vector-valued function class G -
sum-of-
1 EI=l (skatalg (2it L ( 3) In order to can be bounded by RD (folu o 9) := Ee supges [
derive tight bounds for k-means clustering, we develop a novel pector-contraction inequality that can induce bounds with a square-roor dependency on the number of clusters. The theoretical techniques and results involved here may be of independent interest. The generalization bound of k-means clustering-basee -aadd- LSRL method is tighter than the state of the art with faster convergence rate Ö(V which is independent on the number of labels. Since the lower bound for clustering is O( K/n) |Bartlett et al. 1998], our bound is (nearly) optimal, up to logarithmic terms, even from the perspective of clustering. The constant A of the generalization bound in Theorem 7 corresponds to 2 K R here.
5.2 Generalization Bounds for Lasso-Based LSRL Method
Lasso-based LSRL method, i.e., LLSF (Huang et al. 2016), assumes that the label-specific represen- tation of each label should have sparsity and sharing properties. For sparsity. LLSF uses Lasso as the model corresponding to each label. The property of sharing is achieved by considering that two strongly correlated labels will share more features with each other than two uncorrelated or weakly correlated labels and the corresponding weights will be similar, i.e., their inner product will large.
Formally, since each label corresponds to I Lasso, this means that in the class of LSRL. defined by (1. the base loss la is the squared loss, the nonlinear mappings ((-) and ((-) are both identity transformation for any j E [c]. and the constraint a(w) is |/w, I1 < A for any j E [c]. For the j-th label, the property of sharing is reflected by the additionally introduced constraint )) Sys) ; T w. S T, where sys is the cosine similarity between labels yj and ys. here we refer as the sharing constraint. The loss function used by Lasso-based LSRL method is the Decomposable loss.
Since the squared loss is not Lipschitz continuous, the theoretical results the Lipschitz continuity of the loss functions in Proposition T cannot be applied to Lasso-based LSRL method. To overcome this challenge, define the geeudoLipschhic function, which is also used in the theoretical analysis of approximate message passing algorithms [Bayati and Montanari 2011].
Definition 2. For k 1, we say that function f : R + R is pseudo-Lipschitt of order is if there exists a constant L > 0 such that the following inequality holds for all x, y E R:
lfx) f(v) S L (1 + | |y
2 |
vl-
Note that any pseudo-Lipschitz function of order 1 is Lipschitz continuous. The following Proposition shows that the Decomposable loss is still Lipschitz continuous if the base loss is the squared loss. Proposition 2. The squared loss is 1 pseudo-Lipschitz Lipschitz of order 2, the surrogate Decomposable Loss is (3 + c w.r.t. the for norm if the base loss lg is the squared loss.
With the above definitions, we can derive the generalization bound for Lasso-based LSRL method: Theorem 3. Let F be a vector-valued function class of Lasso-based LSRL defined by 77). Let Assumptions Land hold. Given a dataset D of size Then, for any 0 << ô < 1, with probability at
8

---

least 1 - 8, the following holds for any f E F:
R(J)= S RD(s)+ 24v2(3 2B)cAR (1 log (8c2
log
My pB
log 2 8
3M
V 2n
Vn
The complexity of the LLSF function class can be bounded by the complexity of the LSRL function class where each label corresponds to a Lasso, since the introduction of the sharing constraint in the LLSF function class reduces the complexity of the function class compared with the Lasso. Hence, the complexity analysis of the LLSF function class can be converted into upper bounding the Rademacher complexity of the L.RL function class where each label corresponds a Lasso. The constant A of the generalization corresponds to R here, and the value of is (3 + 2B)c, which induce the used, e.g., Hamming, Subset Ranking loss, instead of Decomposable loss, the dependency of the bounds for Lasso-based LSRL method on c. can be improved from linear independent, up logarithmic terms.
Remark 3.
LSRL function function class where each label corresponds
bound in Theorem 7
O(c/ bound here. If other loss functions
5.3 Generalization Bounds for DNN-Based LSRL Method
DNN-based LSRL method, i.e., CLIF (Hang and Zhang 2022]. exploits the powerful representation learning capability of deep neural networks (DNNs) to learn label-specific representation in an end- to-end manner. Since the construction of label-specific representation involves graph convolutional networks (GCNs), we first introduce the relevant definitions for GCN.
Let = {V,E) be given undirected graph, where V {ær 22,,... vn.. the set of nodes with size |V| = and E is the set of edges. Let A and D be the adjacency matrix and the diagonal degree
matrix respectively, where Dü = Σリ= Ay. Let À = (D + la)= (A 4,) (D + In) denote the normalized adjacency matrix with confeconnessooss, where I the identity matrix. The feature propagation process of a two-layer GCN is a (Ao xWW)W2) where W, and W2 are parameter matrices, X is the node feature matrix, and the i-th row X; is the node feature Z;,
Specifically, for DNN-based LSRL method, first, a graph (here we call it the label graph) is constructed over the label space and a GCN is used to generate the label embeddings, i.c., the label embeddings can be denoted by (\Y = RaLU ( Ret. (ÁY Wi) W2),, where Y is the node feature matrix of the label graph with size e and the nodes are also bounded by R. R is the ReLU activation. Second, the label embedding of the j-th label is decoded into the importance vector by one-layer fully-connected neural network, i.c., ssgg Uasg(W2 (W3 (Wgt(Y); where Ssig is the sigmoid activation, and the input feature is mapped into the latent representation through one-layer fully- fully-connected neural network, i.e., o RELU az). Third, for the j-th label, the Hadamard product of the importance vector and the latent representation is defined as the pertinent representation, and then the label-specific representation for the j-th label is obtained by feeding the pertinent representation into another one-layer fully-connected neural network. Hence, the label-specific representation for the j-th label is
و (z) &RLLU (Ws [o (Wax) ssg (W))(Y)))1
Finally, the j-th model is implemented by a fully-connected layer, i.e., (z) asig ( (w) (z)).
In the generalization analysis of the above deep neural network, we introduce the following assump- tion, which is a common assumption in the generalization analysis for DNNs [Bartlett et al. 2017
Golowich et al., 2018 Zhang and Zhang 2023 Tang and Liu 2023
Assumption 3. Assume that the parameter metrices in DNN-based LSRL method are bounded, i.e.,
||W|l| < D, i (5), where D > 0 is constant.
With the above definitions, we can derive the generalization bound for DNN-based LSRL method:
Theorem 4. Let FF be vactor-valued function class of DNN-based LSRL defined by M... Let Assumptions 7 [ and Given a dataset D of size n. Then, for any 0 < 8 < 1, with probability at least o, the following holds for any f E F:
Te (gmax + 1) (1+ log's (862n802) log M.7 6v2pAD= re
DB
log
R(f) < Rf
+ 3M
Vn
2n
where Jmax is the maximum node degree of the label graph.

---

Remark 4. The term (P(F) S AD* (gmax + 11//4/ne, which makes the Rademacher complexity (D( actually independent on up to logarithmic terms, and results in a tight bound for DNN-based LSRL method with a faster convergence rate ((1/ /n). The constant A of the here. For deep GCNs, the increase in depth means that the gene performance will deteriorate, which is consistent with empirical performance and guides us not to design too many layers of GCN. In addition, the bound linearly dependent on the maximum node degree of the label graph, which suggests that when the performance of the model is always unsatisfactory, degree is large and consider using some techniques to remove some edges, e.g., DropEdge (Rong) et al. 2020], to alleviate the over-fitting problem. We will further explore more network structures to learn more effective label-specific representations, e,g,, hyppereewoors [Galanti and Woll [2020 Chen et al. 2023 Shen al. 2023), deep kernel networks (Zhang and Liao 2020 Zhang and Zhang 2023]. and provide generalization analysis for the corresponding DNN-based LSRL methods.
(9max + +1/4 generalization bound in Theorem [ corresponds to D R2
can check whether the maximum node
6 Discussion
Compared with existing methods considering label correlations, which mainly focus on the processing of the label space by exploiting or modeling relationships between labels, LSRL. mainly focuses on the operation on the input space and implicitly considers label correlations in the process of constructing label-specific representations. For example, in the construction of label-specific representations in LLSF and CLIF, the label correlation information is embedded into the label-specific representations in the input space by introducing the sharing constraint and using a GCN over the label graph to generate label embeddings, respectively. LSRL methods are more effective since the label correlation information is considered in the construction of label-specific representations.
Our theoretical results explain why LSRL, is an effective strategy to improve the generalization perfor- mance of multi-label learning. On the one hand, existing results can improve the dependency of the bound on e from linear to square-root by preserving the coupling among different components, which corresponds to high-order label correlations induced by norm regularizers. However, the improvement in the preservation of coupling by a factor of /C benefits from replacing VeA with A in the constraint to some extent, and preserving the coupling corresponds to the stricter assumption IZhang and Zhang 2024]. Our results for LSRL decouple the relationship among different components, and the bounds with weaker dependency
are tighter than the existing results that preserve the coupling, which also explains why LSRL methods outperform the multi-laber methods that consider high-order label correlations induced by norm regularizers. On the other hand, based on our results, we can find that ISRL. methods substantially increase the data processing, i.e., the process of constructing label-specific representations. From the perspective of model capacity, compared with traditional multi-label methods, since the introduction of construction methods of label-specific representations, the capacity of the model is significantly increased, especially if deep learning methods are used to generate label-specific representations, which improves the representation ability of the model. Or more intuitively, LSRL means an increase in model capacity and stronger representation ability, which makes it easier to find the hypotheses with better generalization in the function class.
The centrr-contraction inequality and the theoretical tools developed here are applicable to the theoretical analysis of other problem settings, such as multi-class classification, or more general vector- valued learning problem. For multi-class classification, multi-class margin-based loss, multinomial logistic loss, Top-k hinge loss, etc. are all Zx Lipschitz (Lei et al. 2019). For multi-label learning, the surrogate loss for Macro-Averaged AUC is also 6x Lipsehitz /Zhang and Zhang 2024
7 Conclusion
In this paper, propose a novel vector-contraction inequality for loo norm Lipschitz continuous loss, and derive bounds for general function classes of LSRL with a weaker dependency on c than the state of the art. In addition, we analyze the bounds for several typical LSRL methods, and study the impact of different label-specific representations on the generalization analysis.
In future work, we will extend our bounds to more LSRL methods, and derive tighter bounds for LSRL with faster convergence rate w.r.t. the number of examples, and further design efficient models and algorithms to construct label-specific representations with good generalization performance.
10

---

Acknowledgements
The authors wish thank the anonymous reviewers for their helpful comments and suggestions. This work was supported by the National Science Foundation of China (62225602) and the Big Data Computing Center of Southeast University.
References
Junwen Bai, Shufeng Kong, and Carla P. Gomes. Disentangled variational autoencoder based multi- label classification with covariance-awar multivariate probit model. In Christian Bessiere, editor, Proceedings of the 29th International Joint Conference Artificial Intelligence, number IJCAI 2020, pages 4313-4321, 2020.
Peter I.. Bartlett and Shahar Mendelson. Rademacher and gaussian complexitis: Risk bounds and structural results. Journal of Machine Learning Research, 3:463-482, 2002.
Peter L.. Bartlett, Tamás Linder, and Gábor Lugosi. The minimax distortion redundancy in empirical quantizer design. IEEE Transactions on Information Theory, 44(5):1802-188) 1998.
Peter L. Bartlett, Dylan J. Foster, and Matus Telgarsky. Speccrally-normaaizeed margin bounds for neural networks. Advances in Neural Information Processing Systems, 30(NIPS 2017):6240-62 6249, 2017.
Mohsen Bayati and Andrea Montanari. The dynamics of message passing on dense graphs, with applications compressed sensing. IEEE Transactions on Information Theory, 57(2):664-78 2011.
Matthew R. Boutell, Jiebo Luo, Xipeng Shen, and Christopher M. Brown, Learning multi-label scene classification. Pattern Recognition, 3779):157 2004.
Ricardo Silveira Cabral, Fernando De Torre, João Paulo Costeira, and Alexandre Bernardino. Matrix completion for multi-label image classification. Advances in Neural Information Processing Systems, 24(NIPS 201 19:190-198, 2011.
Nicolò Cesa-Bianchi, Matteo Re, and Giorgio Valentini. Synergy of multi-label hierarchical ensem- bles, data fusion, and cost-sensitive methods for gene functional inference. Machine Learning, 88 (1-2):209-22) 2, 2012.
Di Chen, Yexiang Xue, Daniel Fink, Shuo Chen, and Carla P. Gomes. Deep multi-species embedding. In Proceedings of the 26th International Joint Conference Artificial Intelligence, number IJCAI 2017, pages 3639-3646. ijcai.org, 2017.
Sirui Chen, Yuan Wang, Zijing Wen, Zhiyu Li, Changshuo Zhang, Xiao Zhang, Quan Lin, Cheng Zhu, and Jun Xu. Controllable multi-obeective re-ranking with policy hyperntworks.. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, number KDD 2023, pages 3855-3864, 2023.
Tianshui Chen, Liang Lin, Riquan Chen, Xiaolu Hui, and Hefeng Wu. Knowledge-guider multi-label few-shot learning for general image recognition. IEEE Transactions on Pattern Analysis and Machine Intelligence, 3713)1177 2020.
Stéphan Clémençon, Gábor Lugosi, and Nicolas Vayatis. Ranking and empirical minimization of u-statistics. The Annals of Statistics, 36(2):844-874, 2008
Kunal Dahiya, Ananye Agarwal, Deepak Saini, K Gururaj. Jian Jiao, Amit Singh, Sumeet Agarwal, Purushottam Kar, and Manik Varma. Siamesexml: Siamese networks meet extreme classifiers with 100m labels. In Proceedings of the 38th International Conference Machine Learning, pages 2330-2340, 2021.
Krzysztof Dembezynski, Willem Waegeman, Weiwei Cheng, and Eyke Hüllermeier. Regret analysis for performance metrics in multi-label classification: The case of hamming and subset zero-one loss. In Joint European Conference on Machine Learning and Knowledge Discovery Datahases. volume 6321, pages 280-295, 2010.

---

Krzysztof Dembezynski, Wojciech Kotlowski, and Eyke Hüilermeier. Consistent multilabel ranking through univariate losses, arXiv: 6401, 2012.
André Elisseeff and Jason Weston, A kernel method for multi-labelled classification. In Advances in Neural Information Processing Systems, number NIPS 2001, pages 68 681-687, 2001.
Dylan J. Foster and Alexander Rakhlin. arXiv:1911.06466VV 2019.
Eo vector contraction for rademacher complexity.
Tomer Galanti and Lior Wolf. On the modularity of hyperetworks.. Advances in Neural Information Processing Systems, volume 33, pages 10409-10419, 2020.
Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-independent sample complexity of neural networks. International Conference Computational Learning Theory, 75(COLT 2018): 297-299, 2018.
Yumeng Guo, Fulai Chung, Guozheng Li, Jiancong Wang, and James C. Gee. Leveraging label- specific discriminant mapping features for multi-label learning. ACM Transactions Knowledge Discovery from Data, 13(2):24:1-24:25 2019.
Jun-Yi Hang and Min-Ling Zhang. Collaborative learning of label semantics and deep label-specific features for multi-label classification. IEEE Transactions Pattern Analysis and Machine Intelligence, 44(12):9860-953) 2022.
Jun-Yi Hang, Min-Ling Zhang, Yanghe Feng, and Xiaocheng Song. End-to-end probabilistic label- specific feature learning for multi-label classification. In Proceedings of the 36th AAAI Conference on Artificial Intelligence, number AAAI 2022, pages 6847-6855, 2022.
Jun Huang, Guorong Li, Qingming Huang, and Xindong Wu. Learning label specific features for multi-label classification. In Charu C. Aggarwal, Zhi-Hua Zhou, Alexander Tuzhilin, Hui Xiong, and Xindong Wu, editors, Proceedings of the 15th IEEE International Conference on Data Mining, number ICDM 2015, pages 181-190, 2015.
Jun Huang, Guorong Li, Qingming Huang, and Xindong Wu. Learning label-specific features and class-dependent labels for multi-label classification. IEEE Transactions on Knowledge and Data Engineering, 28( 1 12):3309 3323, 2016.
Jun Huang. Guorong Li, Qingming Huang, and Xindong Wu. Joint feature selection and classification for multilabel learning. IEEE Transactions on Cybernetics, 48(3):876-889, 2018
Shuiwang Ji, Lei Tang, Shipeng Yu, and Jieping Ye. A shared-subspace learning framework for multi-label classification. ACM Transactions on Knowledge Discovery from Data, 4(2):1-29, 2010.
Antoine Ledent, Waleed Mustafa, Yunwen Lei, and Marius Kloft. Norm-based generalisation bounds for deep multi-class convolutional neural networks. In Proceedings of the 35th AAAI Conference on Artificial Intelligence, volume 35, pages 8279-8287, 2021.
Yunwen Lei, Ürün Dogan, Alexander Binder, and Marius Kloft. Multi-class syms: From tighter data-dependent generalization bounds novel algorithms. In Advances in Neural Information Processing Systems, volume 28, pages 2035-2043, 2015.
Yunwen Lei, Ürün Dogan, Ding- Xuan Zhou, and Marius Kloft. Data-dependent generalization bounds for multi-class classification. IEEE Transactions Information Theory, 65(5):2995-302 3021, 2019.
Shaojie Li and Yong Liu. Sharper generalization bounds for clustering, Proceedings of the 38th International Conference Machine Learning, volume 139, pages 3392-6402 2021.
Chong Liu, Peng Zhao, Sheng-Jur Jun Huang, Yuan Jiang, and Zhi-Hua Zhou. Dual set multi-label learning. In Proceedings of the 32nd AAAI Conference on Artificial Intelligence, number AAAI 2018, pages 3635-3642, 2018
Weiwei Liu and Xiaobo Shen. Sparse extreme multi-label learning with oracle property. In Proceed- ings of the 36th International Conference on Machine Learning, volume 97, pages 2019.
12

---

Weiwei Liu, Haobo Wang, Xiaobo Shen, and Ivor W. Tsang. The emerging trends of multi-label learning. IEEE Transactions on Pattern Analysis and Machine Intelligence, 44(11):7955-7977 2022.
Françoise Lust-Piquard and Gilles Pisier. Non commutative khintchine and paley inequalities. Arkiv för matematik, 29:241 260, 1991.
Andreas Maurer. A ventor-contraction inequality for rademacher complexities. Proceedings of the 27th International Conference on Algorithmic Learning T'heory, volume 9925, pages 3-17, 2016.
Yashoteja Prabhu and Manik Varma. Fastxml: a fast, accurate and stable tree-classifier for extreme multi-label learning. In Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, number KDD 2014, pages 263-20 263-272, 2014.
Yu Rong, Wenbing Huang, convolutional networks on node classification. In Proceedings of the 8th International Conference on Learning Representutions, number ICLR 2020, 2020.
Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph
Timothy N. Rubin, America Chambers, Padhraic Smyth, and Mark Steyvers. Statistical topic models for multi-label document classification. Machine Learning, 18(--2): 2012.
Chenglei Shen, Xiao Zhang, Wei Wei, and Jun Xu. Hyperbandit: Contextual bandit with hypernewtork for time-varying user preferences in streaming recommendation. In Proceedings of the 32nd ACM International Conference on Information and Knowledge Management, pages 2239-2248, 2023.
Nathan Srebro, Karthik Sridharan, and Ambuj Tewari. Smoothness, low noise and fast rates. In Advances in Neural Information Processing Systems, volume 23, pages 2199-2207, 2010.
Yan-Ping Sun and Min-Ling Zhang. Compositional metric learning for multi-label classification.
Frontiers of Computer Science, 1553),, 2021.
Huayi Tang and Yong Liu. Towards understanding the generalization of graph neural networks. 235.003355.. 2023.
Wei Weng, Yaojin Lin, Shunxiang Wu, Yuwen Li, and Yun Kang. Multi-label learning based on
label-specific features and local pairwise label correlation. Neurocomputing, 273:385-394, 2018.
Wei Weng. Yan-Nan Chen, Chin-Ling Chen, Shunxiang Wu, and Jinghua Liu. Non-sparse label specific features selection for multi-label classification. Neurocomputing, 374,85994, 2020.
Guoqiang Wu and Jun Zhu. Multi-label classification: do hamming loss and subset accuracy really conflict with each other? Advances Neural Information Processing Systems, (NeurlS 2020), 2020.
Guoqiang Wu, Chongxuan Li, Kun Xu, and Jun Zhu. Rethinking and reweighting the univariate losses for multi-label ranking: Consistency and generalization. Advances in Neural Information Processing Systems, 34(NeurIPS 2021):14332. 14311-1434444,,, 2021a.
Guoqiang Wu, Chongxuan Li, and Yilong Yin. Towards understanding generalization of macro-auc in multi-label learning. In Proceedings of the 40th International Conference on Machine Learning, volume 202, pages 37540-375777 2023.
Liang Wu, Antoine Ledent, Yunwen Lei, and Marius Kloft. Fine-grained generalization analysis of vector-valued learning. Proceedings of the 35th AAAI Conference on Artificial Intelligence, number AAAI 2021, pages 10338-10346 2021b.
Chang Xu, Tongliang Liu, Dacheng Tao, and Chao Xu. Local rademacher complexity for multi-label learning. IEEE Transactions on Image Processing, 25(3): 19555117951577, 2016.
Miao Xu and Lan-Zhe Guo. Learning from group supervision: the impact of supervision deficiency multi-label learning. Science China Information Sciences, 64(3), 2021.
Guangxu Xun, Kishlay Jha, Jianhui Sun, and Aidong Zhang. Correlation networks for extreme multi-label text classification. In Proceedings of the 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, number KDD 2020, pages 1074-1082, 2020.
13

---

Vacit Oguz Yazici, Abel Gonzalez- Garcia, Arnau Ramisa, Bartlomiej Twardowski, and Joost van de Weijer. Orderless recurrent models for multi-label classification. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, number CVPR 2020, pages 13440-13449, 2020.
lan En-Hsu Yen, Xiangru Huang, Pradeep Ravikumar, Kai Zhong, and Inderjit S. Dhillon. Pd- sparse A primal and dual sparse approach to extreme multiclass and multilabel classification. In Proceedings of the 33nd International Conference on Machine Learning, volume 48, pages 3069-3077, 2016.
Renchun You, Zhiyao Guo, Lei Cui, Xiang Long, Yingze Bao, and Shilei Wen. Cross-modality attention with semantic graph embedding for multi-label classification. In Proceedings of the 34th AAAI Conference on Artificial Intelligence, number AA 2020, pages 12709-12716, 2020.
Hsiang-Fu Yu, Prateek Jain, Purushottam Kar, and Inderjit S. Dhillon. Large-scale multi-label learning with missing labels. In Proceedings of the 31th International Conference on Machine Learning, volume 32, pages 593-601, 2014.
Kai Yu, Shipeng Yu, and Volker Tresp. Multi-label informed latent semantic indexing. In Ricardo A. Baeza- Yates, Nivio Ziviani, Gary Marchionini, Alistair Moffat, and John Tait, editors, Proceed- ings of the 28th Annual International Conference on Research and Development in Information Retrieval, number SIGIR 2005, pages 258-265, 2005.
Ze- Bang Yu and Min-Ling Zhang. Multi-label classification with label-specific feature generation: A wrapped approach. IEEE Transactions on Puttern Analysis and Machine Intelligence, 44(9): 5199-5210, 2022.
Chunyu Zhang and Zhanshan Li. Multi-label learning with label-specific features via weighting and label entropy guided clustering ensemble. Neurocomputing. 419:59-69 2021.
Jujie Zhang, Min Fang, and Xiao Li. Multi-label learning with discriminative features for each label. Neurocomputing, 154:305-316, 2015.
Min-Ling Zhang and Lei Wu. Lift: Multi-label learning with label-specific features. IEEE Transac- tions Pattern Analysis and Machine Intelligence, 37(1):107-122, 2015.
Min-Ling Zhang and Zhi-Hua Zhou. ML-KNN: A lazy learning approach to multi-label learning. Puttern Recognition, 40(7):2038-2448, 2007.
Min-Ling Zhang and Zhi-Hua Zhou. A review on multi-label learning algorithms, IEEE Transactions on Knowledge and Data Engineering, 26(8):1819-183) 2014.
Min-Ling Zhang, Yu-Kun Li, Yu-Ying Liu, and Xin Geng. Binary relevance for multi-label learning: an overview. Frontiers of Computer Science, 12(2):191-202, 2018.
Yi-Fan Zhang and Shizhong Liao. A kernel perspective for the decision boundary of deep neural networks. In Proceedings of the 32nd IEEE International Conference on Tools with Artificial Intelligence, number ICTAI 2020, pages 653-660, 2020.
Yi-Fan Zhang and Min-Ling Zhang. Nearly-tight bounds for deep kernel learning. In Proceedings of the 40th International Conference on Machine Learning, volume 202, pages 41861-41879, 2023.
Yi-Fan Zhang and Min-Ling Zhang. Generalization analysis for multi-label learning. In Proceedings of the 41 st International Conference on Machine Learning, number ICML 2024, 2024.
Yue Zhu, James T. Kwok, and Zhi-Hua Zhou Multi-label learning with global and local label correlation. IEEE Transactions Knowledge and Data Engineering,
2018.
14

---

A Appendix
A.1 Appendix Outline
the appendix, we give the detailed proof' of those theoretical results the main paper. Our main proofs include:
The &o Lipschitz continuity of the commonly used losses for LSRL (Proposition !
The novel vector-contraction inequality for &oo Lipschitz loss (Lemma
The generalization bound of the general LSRL class with no dependency on (Theorem)
The generalization bound for k-means clustering- based LSRL method (Theorem)
The (pseudo-) Lipschitz continuity of the squared and Decomposable loss (Proposition
The generalization bound for Lasso-based LSRL method (Theorem
The generalization bound for DNN-based LSRL method (Theorem
A.2
Preliminaries
A.2.1
Definitions of the corresponding complexity measures
Definition 3 (loo norm covering number). Let F be class of real-valued functions mapping from X to R. Let D = {II...., Fn be a set with n ii.d samples. For any e > the empirical fox norm covering number (c, D) w.r.t. D is defined the minimal number of collection of vectors v² v',...,,"* . E IR" such that maxie(n) vector v²). In this case, call { vm) (e, (., of IF with respect to D. We also define (E, sup D).
I (ax) toa S 6 (VV) is the i-th component of the
....,
Definition 4 (Fat-shattering dimension). Let F be class of real-valued functions mapping from X to R. We define the fat- cat-shattering dimension fat, (F) at scale > as the largest p E N such that there exist p points 21....,IIp X' and witnesses $1...., Sp E R satisfying: for any 51, .1,...,5
5p E
[-1,+1} there exists E with d, (J(z,) - 8:) 2 6, Vi 1,....p
A.2.2 The Bound for the loss function space
For any training dataset D {( y:) [m]], let D' = {(,, y.) i [m]} be the training dataset with only one sample different from D, where the k-th sample is replaced by (at v()). Let
(DD) = sur ((a 3)1 Σ. ((f(x;) y.)l = sup (R(f) RD(f)), then
① (D') - (DD)
sup [(f) -)() Rn((f) feF
sup R(() Rn(S))
JEF
< sup fef
Rp (f) (f)(
(((f(xx). 31)) -(f((())
sup
feF
< M
n
According McDiarmid's inequality, for any < 5 < 1, with probability least 1 training dataset D, the following holds:
5 over the
In (2/66)
((D) < ED( + M
(2)
2n
Then, will estimate the upper bound of Ep + (D)]
15

---

Ep
((D)
ED Rf)(f) -
=Ep
sup fer
RD)(f) - Ro(ss]
<Ep.D'
sup SEF
=Ep,D'
sup fEF n
-E,,D,D'
sup
c (e(f(z))) w(i) - e(f(zz)), Bi))
JEF n
1 Σ
<Be,D'
sup
+ +E,,D
sup
-e((((()))))
SEF n
|EF n i=1
1 sup fET
BD
n
Then apply McDiarmid's inequality to E. [sup]er 1 Ei (((f(z;),,)) we have
EDDD sup sEF ni
1 (li())))) vi)
Σ
s Ee
sup SEF n
1
ex((f();)) 4.)
+M
(n(2/0)
2n
i.e.
ln(2/0)
R(C) (n)()++ + M M
(4)
2n
Combining with 2 3 and 4). then
log 2
R(f) < 2 3M
(5)
2n
A.3 General Bounds for LSRL
A.3.1 Proof of Proposition I
We first prove that the surrogate Hamming Loss is p-Lipschitz continuous with respect to the foc norm.
En (n v) - (f((
1 - ls (Hif((0)) 4 (x) -
1o (w)ff())) (1, fxx)))
Σ (l)5(a)) - 1/(=))
1=1
s - uc max (x) (x) fa(0 sEle]
= f - f((xx) loac
16

---

Second, with the elementary inequality
beHl & max fla1 - bil,...,laa la. bel} |ma (a1,.... ae} - max (di,- (b1,...,b..)
we prove that the surrogate Subset Loss j-Liischitz continuous with respect to the &o norm.
((s(f(z),)) - ls (z))
max lu (a))}(z=) max la (1)1
jelel
jeld
max 1s (w)l)())) lo (1)8a(0)))
sElel
Su max [])(()) - f(()
jE(c]
= f - f [z)]
Third, we prove that the surrogate Ranking Loss is Lipschit continuuus with respect the foo norm.
[e((f()).)) - En (f))
1
Σ
Σ (f) - 4o (f,(a) f((=))
|
PEY+ 9EY les (ff(z)) - f,(x)) to (ff(z) - f((2))
max
SM max PEY .gEY
(Vz(x)) f2(2)) (f)(2)) f0()))
Sp max (fp(z) -0----p ff((0) + max (f((z) |((3م\) (PEYt
gEY
24 max [1)(2) (0)
SE(m]
22 || fxx - f lo
Finally, we prove that the surrogate Decomposable Loss is cu-Lipschitz continuous with respect to the lo norm
(n(f(x). - LD (f))))
Σ 4 (z,{(())
Σ lo (v)f((2)))
1e (2)fi(x)) eo (x)1(()))
1 (z)) [x)
Squ max [x)()) - f((
jE|c]
=cu [l((z)) - f (x)
A.3.2 Proof of Lemma 1
Proof Sketch: First, the Rademacher complexity of the loss function space associated with F can be bounded by the empirical for norm covering number with the refined Dudley's 's entropy integral inequality. Second, according to the Lipschitz continuity w.r.t the fxx norm, the empirical fxo norm covering number of J can be bounded by the empirical lxx. norm covering number of P(F). Third, the empirical for norm covering number of P(F) can be bounded by the fat-shattering dimension, and the fat- fat-shattering dimension can be bounded by the worst-case Rademacher complexity of P(F).
17

---

Hence, the problem is transferred to the estimation of the worst-case Rademacher complexity. Finally, we estimate the lower bound of the worst-case Rademacher complexity of P(F), and then combined with the above steps, the Rademacher complexity of the loss function space associated with F can be bounded.
We first introduce the following lemmas:
Lemma 2 (Khintchine- KahhnanhineKKahnee inequality [Lust-Piquard and Pisier 1991]). Let 01
Un E H. where H a Hilbert space with || being the associated p-th norm. Let -1....: :n be a sequence of independent Rademacher variables. Then, for any z there holds
min(vp-1) (1p(pp-11)) 1,
Σ
11
E
Σ
C2us
max vp 1,1)
Σ 1 !??
and
Eg
Σ
6
2
2-
i=1
Lemma 3 (Lemma A.2 in (Srebro al.) 2010). of size and any (FFF), have that
For any function class F. any S with a finte sample
3 (F) 2
fat
Lemma ([rrebro et al. 2010 Lei et al. 2019 ). If any function in class F takes values in [-B, then for any S with a finite sample of size n, any >> 0 with fat, we have
BeBn
log (e) < fat, fat log
The following lemma is refined result of Proposition 22 in [Ledent et al. 2021]. where replace the function class taking values in [0, 1] with the B-bounded function class, the refinement obvious.
Lemma 5 (Refined Dudley's s entropy integral incquality). Let F be a real-valued function class with f S. B, f F, B O, and assume that E F. Let S be finite sample of size For any 2 S p S co, have the following relationship between the Rademacher complexity Rs(F) and the covering number N,(e,F,S)
12
(B
(F) S inf
4a +
Vn Vl SSyde
Step 1: We first derive the relationship between the empirical Lo norm covering number N (e, C, D) and the empirical for norm covering number (c, PFF), [c] x D).
For the dataset D = ((1..))) ..... .. Un)) with i.i.d. examples:
max ((ff(x;) v.) (('(( (m.).
:
<pmax [lf(z;) f (2:) (Use Assumption 2
5 <pmax [f; (x:) f (x;) Spmax max bp (f(x:)) p3 (f
(The definition of the projection function class P(F))
Then, according to the definition of the empirical fo covering number, we have that an empirical for cover of P(F) at radius c/p also an empirical lo cover of the loss function space associated with F at radius and we can conclude that:
Noc (c, D) s No
P(F),((
(6)
18

---

Step 2: We show that the empirical foc norm covering number of P(F) can be bounded by the fat- shattering dimension, and the ttattttte dimension can be bounded by the worst-case Rademacher complexity of P(F).
According to Lemma for any
R Rce)D(((FF), we have
4nch 1c)x
(P(F)
fat, (P(F)) -
62
Then, combining with Lemma 4 have
R
2
(c)x (P(F)((FF)
(P(F)
2c Bnc
lo ((F)( x D) $
log
e²
Use inequality > RcxxD(P(FF), we have
4nch
(c)x
(P(F))
Bne
log
e²
R ((xxD(((F))
Step 3: According Assumption[] in the main paper, we can obtain the lower bound the worst-case
Rademacher complexity Rne (P(F) by the Khintchine- Kahane inequality with = 1:
Rnc (P(F))
R (P(F)(P(F))
sup [c] x x
sup [d
E
sup ()((()))P(F)) ne
Cypy (f(:))
1 n
sup Eg [dxDE[[xx"*
sup
Cifyy (xt)
E ne
j=1
sup
Es
sup IRee I. i=
Eig s ((b,(())))
(5s00/.aa))llssAAeeel..... ne
sup
Bell
(x)r)))(
==
A
sup [c(00s(e))]llssseeee)e))) ne 2
Σ
(0,
(Use Lemma 2
Since (6)( < A, set (cs.etsspppccee.(aaallllss..
1
EL Eラ=1 |I (1(())
ne
Vnc. So,
AA
B
R Rnn (P(F))
>
(8)
v 2nc
V2nc
19

---

Step 4: According to Lemma and combined with the above steps, we have
RC(
12
M
inf
4a +
Le, Dide
020
vn.
12 MM
inf
4a +
log.No( P(F),(c D)de)
(Use inequality (
a20
Vn
12 MM
4ncp² 22
[x)x (P(F)) 2
2eBnc de (c)xD(P(FF)
< inf
4a +
log
(Use inequality 7
Vn
12 MM
Ancp R2
Re (P(F))
< inf a>0
4a
log Dog(2VeeBn de
Vn
(Use inequality
8 and the definition of the worst-case Rademacher complexity)
< inf as0
4a + 12v 12222V/RR.... (no (P(F)) log
(8e2
de
M 3 Ree
log² (8e2 (8))
log
(Choose a ( 3V
M Mvn pB
S12 11) (8=)n
log
(Use inequality
Dn (1+ (Be2 log
M Mvn
pB
A.3.3 Proof of Theorem
We upper bound the worst-case Rademacher complexity Rnc as the following:
Ruc (P(F))
sup xM
(c(xD(P(F))
sup [e]xDe(c)xx=
Ee
sup Ps (((())))) nc
Σ M of
j=l
sup E. xe
sup
Eijfi (x:)
S ne
i=1 j=1
sup
E.
sup
(l nC
I i=
sup
EE
c (b)(()))
nc
1=
A
sup Wise ne
Eell
(2))))
(Use Jensen's Inequality)
1=1
A
AA Vnc
sup
ΣV
(x,))1
(Use Lemma
I1s, (el ne
(9)
20

---

Then, we have
1 RD(F) S12V / (1 log 1og2((82222 (862n"
M Vvn
log
pB
Mya 12v2pAA (1+ log (8)) log pB
vn
Combining with ( then
24v 24v2pAA [1 ++ log² (8
log Myn
log 2 8
R(f) S R
3M
n
A.4
Generalization Bounds for Typical LSRL Methods
A.4.1 Proof of Theorem 2
The generalization analysis of LIFT involves the generalization analysis for k-means clustering, Ac- cording the definitions of k-means clustering in Subection 5.1] we have the empirical Rademacher complexity of a loss function space associated with the vector-valued function class G:
RD(Cau () Ee
sup gEg n(n 1) (,j=1ii
Σ (d1,
Rademacher complexity has proved to be powerful data-dependent measure of hypothesis space complexity. However, since the k-means clustering framework involves pairwise functions, sequence of pairs of i.i.d. individual observation in k-means clustering is no longer independent, which makes standard techniques in the i.i.d case for traditional Rademacher complexity inapplicable for k- means clustering. We convert the non-sum-offi.i.d pairwise function a sum-of-i.i.d form by using permutations in U-process [Clémençon et al., 20088
We first proof the following lemma:
Lemma 6. Let 97 : X x + R be real-valued functions indexed by T E T where T is some set. If I..... Fg and x',,-.. ...... oy are i.i.d., minfs, t), then for any convex non-decreasing function 2/.
Exp
sup rET st
Or (a:;, za))
S
Eub
sup FET
4r (xi,, ar')
Proof. The proof of this lemma is inspired by [Clémençon et al. 2008
Esb
sup TET st
Ur (z); 24/)
j=1
-Bu
sup
1
gr (IT(1) 2'(())
rET 8!
r
1
sup-
gr (b)( 2 m'((0)
(1b is nondecreasing)
!
Tia TET r
1
Enp
sup
Σ gr (i) 25(())
(Jensen's inequality)
TET
1=1
=Ea
sup
Σ
Or (a:;; ai{)
TET
i=1
21

---

According to Lemma
(Clu () can be bounded by
RD (Cela o = E.
sup
9
where each & is an independent Rademacher random variable.
In order to obtain tighter generalization bounds for k-means clustering, we develop the following novel vector-contraction inequality:
Lemma 7. Let G be vector-valued function class of k-means clustering defined in Subection 5.1 Given a dataset D of size n. Then, we have
M
)
(D 99 I 12VK max R [g. (9x) log (e2n²) log
R L[ (1e)(Ge)
where [[ (9k) is the worst-case Rademacher complexity, 9k the restriction of the function class along the k-th coordinate, 9k E Gk-
Proof. We first introduce the following lemma:
Lemma 8 (Lemma in Foster and Rakhlin 2019). Let Let (f and let $1,...,
each be L Lipschitz with respect to the to norm. For any D with a finite sample of size n and have that
1og (c. K maxlog No Fr.
(10)
where Fg is the restriction of the function class along the k-th coordinate, fs E Fr. ke [K]
The empirical foo norm covering number of G& can be bounded by the fat-shattering dimension, and the fat-shattering dimension can bounded by the worst-case Rademacher complexity Gt. Combined with the above steps, we have
RD o 9) < Rp (Celu 9)
12
M
inf as0
4a +
Vlog Coive o G, D'jde
(Use Lemma 5
Vni
12
MM
inf 020
4a: +
K max log Noo (c, GR, D'yde
Vn
(Use inequality
(10
i- 1-Lipschitz w.r.t. loo norm for k-means clustering) and lesa() (-) is
12
2eB de
inf 020
4a +
K max max (Gk) log
(Use Lemma
vn
12
417 (Gtt)
22
(Gt)
2eGl a RD (Gx)
inf 050
4a +
K max
log
de
(Use Lemma
e2
12
4 (9h)
2eG [ de (9x)
inf 0.50
4a +
max
log
e2
R
(The definition of the worst-case Rademacher complexity)
12 M
2nK max,
Ri (9x)
inf as0
4a
log(en à )de
Vn
22
22

---

C
(Use the similar technique to the proof in inequality (), the lower bound of R[ (9x)
V2
4a 12V K max Ri [ (Gx) log (e²n²) /,a M
S inf a>0
M
<12v K max R $1 (9x) + 12v K max 1 (Gk) log (c2n)) log
3v K max R (1
(Choose 3v K max R | (9x))
=12v K max R } (Gn)
(1+ (c2n²)
log R 3 (9x)
Since k--maas clustering- LSRL method is two-stage, the k-means clustering is used to generate
label-specific representations in the first stage, and the second stage is conventional multi-label learning. Therefore, the corresponding whole function class is actually denoted as H = F + Cetu o G.
Since Rnn(P(()) I Rnd (P(F) + Rne (P(Cetu o G) |Bartlett and Mendelson
2002 with Lemma
1. we have
RD(C H) s 12v2pVc (Rnc(((F)) + Rn og))
1 log (8e2n3
log
M μ.B
According Lemma 7 we have that the worst-case Rademacher complexity of the loss function space associated with Pg) can be bounded by the worst-case Rademacher complexity of the restriction of the function class along each coordinate P(Gx). Hence, for k-means clustering- -eaeeinn--asedd LSRL method, Lemma 7 involves the upper and lower bounds of A as (P(G))).
We then obtain the lower bound of the worst-case Rademacher complexity R. (P(G)) by the Khintchine-Kahhe inequality with 1:
R 4 (P(G)))
sup
1
sup
Ec
sup
Ps (o (EE)))))
|
sup
Ex
sup
Gygh (zi, #1+1+1)
xxx
2
1
sup
Ec
sup
Gi Va,, ) (z x14141)
|| 19
[|V 5AR2
L#
4R²
sup
EAll
i (m,, #+111))1
1=1
4R
sup
7 (2,,
2
11 (2)
Since || [2(22,, *++1E])]| A 1, we set sup s (1
E
L
(Z (.., 2111)))1
So, R # (P(G))))
41²"
Vnc
VTC
23

---

Then, we replace the lower bound of Ri [g]] (9k) (g)())) in the proof of Lemma 7 with the lower bound of R (1 (P(Gx))) and we have
Rno - 9)) & 12VK K max R L ( ( (1+ loggo log G
M Myne
&
We then upper bound the worst-case Rademacher complexity R [ (P(Gx)) the following:
R | (P(Ee))
sup [x [dx
[ (P(Ge)) (P(G+))
131
sup
Er
sup
eyp (a (2s (1
n ps (ou (EP())))))))) (EP(S))
1xxx'r(c)xxx
2
sup
Ee
sup
Gygh [c, F++1#))
n .2
1=
sup
Eg
sup
Gg (a 11 ( 01411))
(0..0 4R
1
4R²
sup
Eell
ΣΣ>
Ety (x (0,, x++131|||
i=1
E ΣΣ
4R
sup
Ee
Gj Z (x; 2 x
(m (1: 1ll
i=1 j=j=1
[ ΣΣ
4R
sup
Σ
(x) 2
c
(00, me 11 |l
1=1
VT
2G
Vnc
Hence, we have
24VKG
(1+ (6:12)) log G
M Mune
Rnd (P(Lsu G))
Vnc
Use the similar technique to the proof of the inequality above, the upper bound of Rno
RR since (x:)] / E (d(x,, /K max || cbll VK maxe (120
nCC
| I) < 2VKR.
Finally, combining with the above inequalities and (5) we have
48 + log (8)2
Myn log
log 2
R()) <kp(s)(+++ 3M
uB
2n
Vni
242 242 Vn
M /nee
) (1+ (oe2(722)) (8e21363)
M /
[ log (c21²0²)
log
log
G
μB
24

---

A.4.2 Proof of Proposition 2
First, we prove that the squared loss is 1 pseudo-Lipschitz of order 2.
E (z))((()) (z))
(y) [,(x))² (リ5 - f=()))
(us fy(x)) + (us - -[(=)) 100; - fz(x)) (vj - f)(x))
S (lV> f(()) + |b5 f((x))) (0) - f)())) - (Vj f)(2))
$ (1 + |0; (z)) + |0 ff(x))) |(1s fy(#)) (uy f](2))
According to the definition of the pseudo-Lipschitz function, the squared loss is pseudo-Lipschitz of order 2. Then, we have
6s (w)l(())) la (w5 (x)))
<(1 + by - [,(2)] + My - [](())) (10 - [2(2)) -V; - fz(2)) $ (1+2 +
+ (f((a) ( [a)
fj(x)
<(3+ 2B) [x) f((z)/
Second, we prove that the surrogate Decomposable Loss is (3 + Biip-sisshitz continuous with respect to the foo norm if the base loss l is the squared loss.
(D(f(x). v) - LD (f()))
Σ (znff Σ 4o (v.f((z))
le (1)5}(m)) - la (1)1((
[3 (BB2B) [x(()) f()
Sc(3 + 2B) max [55(z) - [5(
je(c
-33 + 2B)c f((()) f (2)
A.4.3 Proof of Theorem 3
Compared with the function class of LSRL where each label corresponds to Lasso, the function class of LLSF introduces the additional sharing constraint. In fact, the introduction of the sharing constraint reduces the complexity of the function class compared with the original class. Then, the complexity for the function class LLSF can bounded by the complexity the function class of LSRL where each label corresponds to Lasso. Hence, the complexity analysis of the function class of LLSF can be converted into giving the bound of the Rademacher complexity of the LSRL function class where each label corresponds
Lasso.
According to the definition, the function class of I.SRI. where each label corresponds to a Lasso means that in the class of LSRL defined by ( the base loss Eg is the squared loss, the nonlinear mappings (()) and Φ(-) are both identity transformations for any j E [c]. and the constraint aww) [c). The proof process is similar to Lemma and Theorem I but the upper bound of the worst-case Rademacher complexity Rne (P(F)) here is different from Theorem According to the above definitions, we have
is |ww I < A for any
25

---

(nF(P(F))
[=)xD[|)xxx> (PxxD(((F))
sup
sup
Ee sup ()(((E)))P(())
(fp)()(z)))
nc i=
E
sup
City (ai)
[e)xDe(exx**
fiET; nC
im 1 1
sup
-E Ee
sup
Ei (w0 ax))
[
|wy]lISA i=1 j=1
sup
Er
sup |wylliSA
||00 |11/1
2 1000
(Use Hölder's Inequality)
[
nc
1=1 j=1
A
sup
Fell
nc
==1
A
sup
Ee
e 11
(Use Jensen's 's Inequality)
[
A
sup Ree
|
11
(Use Lemma
i=1 j=1
AR
(11)
Vnc
Combining with Lemma
inequalities 11. 5 and = =33+ 2B)c, then we have
R(f) < RD( 24v2(3 2B)cAR log (86222c²)
log
Mya pB
log 2
33
Vn
2n
A.4.4 Proof of Theorem
First, we upper bound the worst-case Rademacher complexity Rnd (P(F)) for DNN-based LSRL method. With the definitions in the main paper, we have
Rno(P()))
R (P(FF(((F))
sup
Eg [c]
sup
sup
Eiply (f(z))
(E(( ne
j=1
sup
E
sup
Giff (x:))
[c]x (E(c) x
E ne
sup
E. sup
Eijo (w) o, (2()))
De|xDele xm
1=1
26

---

1
1
2
sup
E
sup ||..,
Eij , dy(x)))
4 [c]x x
i=
(The Lipschitz constant of sigmoid activation is bounded by
1
sup
Ee sup dy ne
(x:))
2
[e)x D
sup
Ex sup
ReLU (Ws [onse (Wa,,) o asg (Wa
[c]x (c) x
nC
j=1
1
22 - 2
sup [e)
Eg sup [WallsD ne
Gy W/s no (onat((aa))) @ osig (W (Wa)((M)))
1=1
(ReLU activation is 1-Lipschitz)
1
<AD
sup [e(x
E. sup ne
Cij ROLL (Waa, O ssg (Wad(Y);)
j=1
<AD sup Issi (Wa))(Y)))l
sup [e\xDe<|xx**
Ee sup
RegOR (W)
| ne
<2AD sup ( (Wa)(Y)))
sup
E, |[alllSD
sup
Σ
63 WaD:
| SR
<2AD sup
(Wa))()))
sup
E,
CijDi
||
ne
i=1 1=
2 $
<2AD sup (Wa+(()))) sup
Ee
(Use Jensen's Inequality)
|| R ne
iml
jul
1
<2AD TMADD>up//i (aapeoooi(aaa(())))))
sup
ΣΣ 1=1
x
1|2
|| nc
R
< sup a (Was))
(12)
VNc
Then, have to bound sup ||ossg (Yst(Y))))l
sup [lo (Wab(Y))))
1 2/2
S sup [Ya*(Y)))l (The Lipschitz constant of sigmoid activation is bounded by swlll
D sup [Y))l (Use Cauchy-Schwarz Inequality)
4
D
(Aonaa
sup sup
4
[Wa <D
D
| JAY (AY,..))
sup
sup SDD
27

---

D
sup
4
D
sup
Σ
ASIOR
4
i=1
D2
e
sup Σ
Ajillo
Wi)YiWWi)l
4
D2
$
sup sup
Σ Afi Σ
An A. Will
4
||WillsD
j=1
D3
sup
Σ
Afi
Σ
Aig Y
(Use
Inequality)
4
1=1
j=l
D
Aze Σ
Aij
sup
4
1=1
D R
$ 4
A
(13)
denote NG) as the index set of the one-hop neighbors the j-th node, and denote g as node degree, 9max as the maximum node degree. Then, we bound ||A|] as follows
A
Aij
9b
+1
j=1
V +1
Vli +
V +1
JEN(()
V +I
VI+1
VI+I
JEN(()
1
9: +1
91 +
Jmax + 1
(14)
Vgi
+
V2
2
Combining with Lemma I
inequalities
12). 13 and (5). then we have
R(f) RD( + 6 6v2pAD R (Jmax + 1) 1 + log (862n303) log
M
log 2
p
+ 3M
2n
28

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The paper's contributions and scope are reflected accurately by the main claims
made in the abstract and introduction. Please Abstract and Introduction sections.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: This is purely theoretical work which improves existing theoretical results. The assumptions involved the theoretical results are explained detail and are satisfied in the relevant settings. Please Conclusion section.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: This a purely theoretical work which improves existing theoretical results. The assumptions involved in the theoretical results are explained in detail and are satisfied in the relevant settings. In the appendix, we give the detailed proofs those theoretical results in the main paper.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification: This is purely theoretical work. This paper does not include experiments.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification: This is purely theoretical work. This paper does not include experiments requiring code.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [NA]
Justification: This is purely theoretical work. This paper does include experiments.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: This is purely theoretical work. This paper does not include experiments.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
29

---

Answer: [NA]
Justification: This is purely theoretical work. This paper does not include experiments.
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: This is theoretical research and the research conducted the paper conform with the NeurlPS Code of Ethics.
10. Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: impact.
This is theoretical research that does not have potential negative societal
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: This is a purely theoretical work. This paper poses no such risks.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
This is purely theoretical work.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This is purely theoretical work.
Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This is purely theoretical work. This paper does not involve crowdsourcing nor research with human subjects.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This is purely theoretical work. This paper does not involve crowdsourcing nor research with human subjects.
30


Reviews:
[{"review_id": "YA3pQUls0r", "reviewer": "Reviewer_Axy4", "summary": "The paper focuses on the theoretical analysis of Label-Specific Representation Learning (LSRL) within the context of multi-label learning. LSRL aims to improve multi-label learning by creating representations with distinct discriminative properties for each label. While LSRL has shown empirical success, its theoretical underpinnings, especially regarding generalization bounds, have been less explored. The authors propose a novel vector-contraction inequality and derive tighter generalization bounds for LSRL. These bounds offer a better dependency on the number of labels compared to existing theories. The paper also discusses the implications of these bounds for various LSRL methods, emphasizing the mild assumptions that explain the good generalization abilities of LSRL.", "questions": "1. The paper seems somewhat unclear when emphasizing the innovative aspects of its proof process. Could the authors clearly articulate the unique innovations in their proof of the generalization bounds and explain how their approach differs from and improves upon the generalization proofs of other multi-label methods?\n2. Could the authors provide the key theoretical tools and intermediate steps involved in the  derivation steps of the vector-contraction inequality?\n3. For the k-means clustering-based LSRL method, how does the two-stage approach affect the derivation of generalization bounds? Specifically, how do the clustering center generation and label-specific representation generation stages interact in the derivation process?", "limitations": "Theory should serve practice or guide the design of better algorithms. However, this paper lacks experimental validation of the theory, particularly including a comparison of the effectiveness of multi-label methods under the LSRL framework with other methods that have larger generalization errors. The paper also lacks numerical validation of the theory and verification of whether the theoretical assumptions are easily met.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. Novel Theoretical Contributions: The paper introduces a new vector-contraction inequality specific to LSRL, providing a theoretical framework that was previously lacking.\n2. Improved Generalization Bounds: The derived generalization bounds have a weaker dependency on the number of labels, offering better theoretical guarantees.", "weaknesses": "1. The main issue addressed in the paper is viewing the multi-label problem as multiple binary classifications and then identifying the most discriminative features for each label. However, it is well known that the key aspect of multi-label problems lies in label correlations, which are crucial for improving the effectiveness of the methods. If a model considers each label independently and ignores label correlations, it is no different from solving a multi-class classification problem. This paper does not consider label correlations, raising questions about whether the proposed theoretical framework can substantially enhance multi-label learning methods.\n2. It is well known that in the era of big data, multi-label problems often face the issue of extreme multi-labels, where the scale of labels is very large. In such cases, implementing the LSRL framework is nearly impossible due to its high complexity. Therefore, although the authors propose better generalization bounds, the computational cost required to achieve this generalization is extremely high. The paper lacks an analysis of the complexity of multi-label methods under the LSRL framework. The authors are requested to provide further analysis in this regard.", "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 Weakness 1.**\n\na. The basic idea of LSRL is to decompose multi-label problem into c binary classification problems. This idea is effective for handling multi-label problems, since Binary Relevance is a popular and important multi-label method. \n\nb. Label correlations mainly focus on the processing of label space by exploiting relationships between labels, while decomposition-based LSRL focuses on the operation on input space and implicitly considers label correlations in the process of constructing label-specific representations (LSR). For example, in construction of LSR in LLSF and CLIF, label correlation information is embedded into LSR in input space by introducing the sharing constraint or using a GCN over the label graph to generate label embeddings. LSRL is more effective since label correlation information is considered in construction of LSR.\n\n**2. Response to Weakness 2.**\n\nIt is not a trivial problem to extend existing multi-label methods to handle extreme multi-label (EML) problems. For the treatment of EML problems, it is often necessary to introduce specific strategies in label space. Existing LSRL methods have not considered handling EML situations. LSRL needs to combine some specific strategies to deal with EML problems, which is more of an algorithm design problem. The main goal of our work is to provide an effective theoretical framework and analysis tools. After exploring an effective specific strategy for LSRL, we can formally define the strategy (i.e., characterize it more precisely in function class) and conduct further detailed analysis in combination with the theoretical framework provided here.\n\n**3. Response to Question 1.**\n\nThe analysis of multi-label learning can be traced back to a basic bound with a linear dependency on the number of labels (c), which comes from the following inequality: \n\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\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$. \n\nThe dependency of bounds on c can be improved to square-root. Such improvements essentially come from preserving the coupling reflected by the 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. \n\nHence, the improvement in preservation of coupling by a factor of $\\sqrt{c}$ benefits from replacing $\\Lambda$ with $\\sqrt{c}\\Lambda$ in the constraint to some extent. The bounds can be improved to be independent on c for $\\ell_\\infty$ Lipschitz loss by preserving the coupling. However, these theoretical results based on preserving the coupling do not apply to LSRL. Hence, we introduce the projection function class to decouple the relationship for LSRL and derive new vector-contraction inequality, which lead to tighter bounds than the SOTA. Other theoretical innovations on typical LSRL methods mainly include: new vector-contraction inequality for k-means that can induce bounds with a weaker dependency on K, introduction of pseudo-Lipschitz function, and generalization analysis of GCN, as we discussed in Remarks.\n\n**4. Response to Question 2.** \n\nFirst, Rademacher complexity of the loss function space associated with $\\mathcal{F}$ can be bounded by empirical $\\ell_\\infty$ norm covering number with refined Dudley's entropy integral inequality. Second, based on $\\ell_\\infty$ Lipschitz continuity, empirical $\\ell_\\infty$ norm covering number of $\\mathcal{F}$ can be bounded by empirical $\\ell_\\infty$ norm covering number of $\\mathcal{P}(\\mathcal{F})$. Third, empirical $\\ell_\\infty$ norm covering number of $\\mathcal{P}(\\mathcal{F})$ can be bounded by fat-shattering dimension that can be bounded by worst-case Rademacher complexity of $\\mathcal{P}(\\mathcal{F})$. Hence, the problem is transferred to the estimation of worst-case Rademacher complexity. Finally, we estimate the lower bound of worst-case Rademacher complexity by Khintchine-Kahane inequality, and then Rademacher complexity of the loss function space can be bounded. \n\n**5. Response to Question 3.**\n\nIn k-means clustering-based LSRL, for each label, we first use k-means to get centers of K clusters, and then we use K centers to construct LSR. We cannot formally express the two steps in a closed-form expression by a composite function since K centers are generated by arg min function. A common and trivial analysis method for two-stage methods is to start analysis directly from second stage, thereby simplifying the difficulty of theoretical analysis caused by the difficulty of formalization in first stage, which actually ignores the complexity of the method in first stage. \n\nHere, K centers generated in first stage are actually used as fixed parameters rather than inputs in second stage. Hence, to fully consider the model capacity corresponding to first stage, it is reasonable to define the function class as sum of classes $\\mathcal{F} + \\mathcal{G}$ corresponding to the methods of two stages. Then, combined with novel vector-contraction inequality, the analysis is transformed into bounding the complexity of projection function class $\\mathcal{P}(\\mathcal{F}+\\mathcal{G})$. Benefiting from the structural result of complexity, we can bound the complexity of $\\mathcal{P}(\\mathcal{F})$ and $\\mathcal{P}(\\mathcal{G})$ separately, where bounding $\\mathcal{P}(\\mathcal{F})$ is obvious. To bound $\\mathcal{P}(\\mathcal{G})$, we develop a novel vector-contraction inequality for k-means that can induce bounds with a square-root dependency on K, as we discussed in Remark 2 and line 623-627.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "18tyZJoBO3", "reviewer": "Reviewer_xFN1", "summary": "This work makes one step towards the generalization analysis for label-specific representation learning. Compared with previous generalization studies on multi-label learning, this work provides a generalization bound with a much weaker dependency on the number of labels and decouple the relationship among components of different classes. This work also analyzes the generalization bounds for three typical LSRL methods, including k-means clustering-based method, LASSO-based method and DNN-based method, and these results reveal the impact of different label-specific representations.", "questions": "1) In Eqn. (1), why does each label require defining two nonlinear mapping functions? Can one be used instead? Or could you please explain the different roles of these two non-linear functions?\n\n2) As for the vector-contraction inequality given in Lemma 1, could it be applied to the analysis of other problems? For example, for multi-class classification, we sometimes convert the original problem into training multiple oneVsAll binary classifiers. Can the theoretical tools proposed in this article be used to explain the generalization of these methods?\n3) Could the theoretical results explain why LSRL improves the performance of multi-label learning, compared with some traditional methods exploring the correlations among different labels?", "limitations": "See the above", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1) Overall, I think this is a nice work with significant contribution. The proposed generalization bound takes a much weaker dependency on the number of labels, and this is quite important since a large number of labels may occur in the multi-label tasks. Besides, previous theoretical works for multi-label learning preserve the coupling among different components, and this is invalid for LSRL. This work decouples the relationship among different labels during the analysis, which is consistent with the process of LSRL. Therefore, I consider this work as a milestone for the theoretical understandings of LSRL methods.\n\n2) The major technical contribution lies in the vector-contraction inequality given in Lemma 1, and the core idea is to introduce a projection function to decouple the relationship among labels. This may shed lights on relevant studies on LSRL. This work also analyzes the generalization bounds for three mainstream LSRL methods, and some techniques may be of independent interest for the studies of KNN, Lasso and deep neural networks.\n\n3) This work is well written and the structure is nice. Both the motivations and contributions have been stated clearly. Necessary analysis has also been presented for the proposed theoretical results. Besides, a detailed review of related work is also provided to help readers understand the background of this work.", "weaknesses": "1）As pointed out in lines 165-168, the Rademacher complexity cannot be directly applied to the class of vector-valued functions F. Therefore, this work considers the complexity of the loss function space with respect to F. Here, I suggest formally defining the Rademacher complexity of this loss function space to avoid any misunderstanding.\n\t\n2）This work provides definitions for the covering number and Fat-shattering dimension in Definition 2 and Definition 3. However, these complexities are not mentioned again in the main text. I suggest explaining how these complexities are used in the main text or directly moving their definitions to the appendix.", "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 Weakness 1.**\n\nAs the reviewer said, formally defining the loss function space can avoid any misunderstanding. This problem is mainly caused by the limitation of paper length. We give the definition of the loss function space in Appendix and mix the two function classes with a description in the main paper. We will formally define the loss function space in the main paper:\n$$\n\\mathcal{L}=\\\\{\\ell (\\boldsymbol{f}(\\boldsymbol{x}), \\boldsymbol{y}) : \\boldsymbol{f} \\in \\mathcal{F}\\\\},\n$$\nwhere $\\mathcal{F}$ is the vector-valued function class of LSRL defined in the main paper. Then, the empirical Rademacher complexity of the loss function space associated with $\\mathcal{F}$ is defined by \n\n$\\hat{\\Re}_{D}(\\mathcal{L})$\n\n$=\\mathbb{E} \\left[\\sup_{\\ell \\in \\mathcal{L}, \\boldsymbol{f} \\in \\mathcal{F}}\\left| \\frac{1}{n} \\sum_{i=1}^n \\epsilon_{i} \\ell \\left(\\boldsymbol{f} (\\boldsymbol{x}_{i})\\right)\\right|\\right]$. \n\nIn addition, we will modify the relevant symbols accordingly, e.g., changing $\\hat{\\Re}_D(\\mathcal{F})$ on the left side of the vector-contraction inequality in Lemma 1 \n\nto $\\hat{\\Re}_{D}(\\mathcal{L})$.\n\n**2. Response to Weakness 2.**\n\nThese complexities are used to prove the vector-contraction inequality, the proof sketch is as follows:\n\nFirst, Rademacher complexity of the loss function space associated with $\\mathcal{F}$ can be bounded by empirical $\\ell_\\infty$ norm covering number with refined Dudley's entropy integral inequality. Second, according to $\\ell_\\infty$ Lipschitz continuity, empirical $\\ell_\\infty$ norm covering number of $\\mathcal{F}$ can be bounded by empirical $\\ell_\\infty$ norm covering number of $\\mathcal{P}(\\mathcal{F})$. Third, empirical $\\ell_\\infty$ norm covering number of $\\mathcal{P}(\\mathcal{F})$ can be bounded by fat-shattering dimension, and fat-shattering dimension can be bounded by worst-case Rademacher complexity of $\\mathcal{P}(\\mathcal{F})$. Hence, the problem is transferred to the estimation of worst-case Rademacher complexity. Finally, we estimate the lower bound of worst-case Rademacher complexity, and then the Rademacher complexity of the loss function space can be bounded. \n\nThis proof sketch is moved to Appendix since the limitation of paper length. We will add it in the main paper to improve the readability.\n\n**3. Response to Question 1.**\n\nThe purpose of 2 nonlinear mappings in definition is to emphasize the construction of label-specific representation (LSR). Since the goal of LSRL is to construct the representation with specific discriminative properties for each class label to facilitate its discrimination process, so the inner nonlinear mapping $\\phi$ corresponds to the nonlinear transformation induced by the construction method of LSR, while the outer nonlinear mapping $\\zeta$ refers to the nonlinear mapping corresponding to the classifier learned on the generated LSR. If only one nonlinear mapping is used to define the prediction function, it means learning a nonlinear classifier directly on the input data, which is the function class of general multi-label learning rather than LSRL. \n\n**4. Response to Question 2.**\n\nThe vector-contraction inequality and the theoretical tools here are applicable to the analysis of other problem settings, such as multi-class classification, or more general vector-valued learning. Multi-class classification and multi-label learning are typical vector-valued learning problems. When applying the vector-contraction inequality and related theoretical results here, it is only necessary to check whether the loss function is $\\ell_\\infty$ Lipschitz continuous. In addition to the multi-label loss involved here, for multi-class classification, multi-class margin-based loss, multinomial logistic loss, Top-k hinge loss, etc. are all $\\ell_\\infty$ Lipschitz continuous.\n\n**5. Response to Question 3.**\n\nFirst, existing theoretical results can improve the dependency of the basic bound on c from linear to square-root by preserving the coupling, which is reflected by the constraint $\\\\|\\boldsymbol{w}\\\\| \\leq \\Lambda$. Preserving the coupling corresponds to high-order label correlations induced by norm regularizers. Decoupling the relationship in LSRL is reflected by the constraint $\\\\|\\boldsymbol{w}_j\\\\| \\leq \\Lambda$ for any $j \\in [c]$. \n\nAs a comparison, when $\\\\|\\boldsymbol{w}_j\\\\|_2 \\leq \\Lambda$ for any $j \\in [c]$, \n\nif we consider the 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. Hence, the improvement in preservation of coupling by a factor of $\\sqrt{c}$ benefits from replacing $\\Lambda$ with $\\sqrt{c}\\Lambda$ in the constraint to some extent, and preserving the coupling corresponds to a stricter assumption. Our theoretical results decouple the relationship, and the bounds with a weaker dependency on c are tighter than existing results that preserve the coupling, which also explains why LSRL methods outperform multi-label methods that consider high-order label correlations induced by norm regularizers.\n\nSecond, based on our theoretical results, we can find that LSRL methods substantially increase the data processing, i.e., the process of constructing LSRs. From the perspective of model capacity, compared with traditional multi-label methods, since the introduction of construction methods of LSR, the capacity of the model is significantly increased, especially if deep learning methods are used to generate LSRs, which improves the representation ability of the model to a certain extent. Or more intuitively, LSRL means an increase in model capacity and stronger representation ability, which makes it easier to find the hypotheses with better generalization in function class. Hence, it is reasonable that LSRL can improve the performance of multi-label learning.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "U0y6wubxrn", "reviewer": "Reviewer_iWbs", "summary": "The article discusses the theory bounds of Label-Specific Representation Learning (LSRL) in multi-label learning. It highlights the need for a deeper understanding of LSRL's generalization properties and proposes novel bounds based on Rademacher complexity. This paper derives bounds for general function classes of LSRL with a tighter dependency on the number of labels than the state of the art, and these theoretical results reveal the impact of different label-specific representations on generalization analysis.", "questions": "1. How can the theoretical bounds proposed in the study be translated into practical enhancements in real-world multi-label learning tasks?\n2. To what extent can the assumptions in the theoretical analyses be relaxed to encompass a wider array of diverse and intricate problems? For instance, could these assumptions be extended to other loss functions?", "limitations": "NA", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "1. This paper develops a novel vector-contraction inequality and derive the generalization bound for general function class of LSRL, which has not been explored in previous research.\n2. By deriving tighter bounds and analyzing typical LSRL methods, the paper enhances theoretical guarantees and shed light on the impact of label-specific representations on generalization.\n3. By exploring the effects of different label-specific representations, this paper provides insights into the generalization of LSRL and contributes to a deeper understanding of multi-label learning.\n4. The assumptions posited in this paper are reasonable and aligned with real scenarios, with a logically coherent process of reasoning and argumentation.", "weaknesses": "1. Section 5.3 of this paper precisely assumes a fixed structure for the DNN-based LSRL method, which appears somewhat biased. It could be more comprehensive to indicate bounds for a subset of network structures sharing common characteristics.\n2. Different label-specific representations exhibit substantial variations in their effect on Generalization Bounds. The paper solely undertakes theoretical analyses of a limited number of label-specific representations, potentially lacking comprehensiveness.\n3. While the theoretical advancements are significant, the paper does not provide guidance on implementing LSRL in real-world applications.", "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 the Weakness 1.**\n\nWe appreciate the reviewer's suggestion for a broader scope of applicability of the analysis method for DNN-based LSRL. The analysis of the precise structure of the network is mainly affected by the specific model corresponding to the specific LSRL method being analyzed. However, the applicability of the analysis method can be relaxed, and the network structure corresponding to the theoretical result can be appropriately relaxed to a deep GCN connected to a deep feedforward neural network (FNN). \n\nThe analysis of DNN-based LSRL here uses the capacity-based generalization analysis method. For deep models, the common capacity-based analysis method is to use a \"peeling\" argument, i.e., the complexity bound for l-layer networks is reduced to a complexity bound for (l-1)-layer networks. In this method, a product factor of the constant related to the Lipschitz property of the activation function and the upper bound of the norm of the weight matrix will be introduced for each reduction due to scaling. After applying the reduction l times, the multiplication of product factors with exponential dependency on l will make the bound vacuous. So far, effective capacity-based analysis for DNN (with a weak dependency on l) remains an open problem. \n\nHowever, the theoretical result in Section 5.3 is not negatively affected by l, since the network involved in GCN has only 3 layers, and the subsequent connected FNN has only 2 layers. These shallow networks do not make the bound vacuous, which is reflected by $D^5$ in bound.\n\nWhen considering a broader scope of applications, we have to consider deep GCNs and FNNs. If the \"peeling\" argument is used, it will bring concerns about l to bound. However, for deep GCNs, the increase in depth means the bound with a heavy dependency on l, which means that the performance will deteriorate, which is consistent with empirical performance, since in experiments, increasing the number of layers of GCN will lead to worse performance. Hence, there is still a need to develop new theoretical tools to analyze capacity-based bounds for deep FNNs and other deep network structures. We will focus on solving this open problem in future work.\n\n**2. Response to the Weakness 2.**\n\nWe appreciate the reviewer's suggestion for the comprehensiveness. The main goal of this work is to address the deficiencies of existing theoretical results (i.e., existing bounds with a linear or square-root dependency on c cannot provide general theoretical guarantees for multi-label learning, and existing analysis methods that preserves the coupling are not applicable to LSRL), establish a theoretical framework and provide analysis tools for the generalization analysis of LSRL. Based on the proposed theoretical framework, to provide theoretical guarantees for existing LSRL methods as much as possible, we conduct analysis on several typical LSRL methods and provide new theoretical results and tools for k-means, Lasso, and DNNs. Although the LSRL methods analyzed here are limited, it is difficult for us to fully cover all LSRL methods with just one work. Our work fills the gap in theoretical analysis of LSRL, and in future work we will continue to expand the analysis of other LSRL methods to improve the comprehensiveness of theoretical analysis.\n\n**3. Response to Weakness 3 and Question 1.**\n\nFirst, existing theoretical results can improve the dependency of the basic bound on c from linear to square-root by preserving the coupling, which is reflected by the constraint $\\\\|\\boldsymbol{w}\\\\| \\leq \\Lambda$. Preserving the coupling corresponds to high-order label correlations induced by norm regularizers. Our theoretical results for LSRL decouple the relationship among different components, and the bounds with a weaker dependency on c are tighter than the existing results that preserve the coupling, which also explains why LSRL methods outperform the multi-label methods that consider high-order label correlations induced by norm regularizers. Hence, when choosing the multi-label method in practice, one should prefer the LSRL methods rather than the latter.\n\nSecond, the bound indicates that when we handle multi-label problems in practice, the method designed should ensure that the constant terms in the bound (other than c) are as small as possible. For example, when using DNN-based LSRL to handle multi-label problems, theoretical analysis shows that the bound is highly dependent on depth of GCN, which guides us not to design too many layers of GCN. In addition, the bound is linearly dependent on the maximum node degree of the label graph, which suggests that when the performance of the model is always unsatisfactory, we can check whether the maximum node degree is large. If so, we should consider using some techniques to remove some edges, e.g., DropEdge, to alleviate the over-fitting problem.\n\n**4. Response to the Question 2.**\n\nThe assumption of Lipschitz continuity of the loss w.r.t. the $\\ell_\\infty$ norm is applicable to the theoretical analysis of other problem settings, such as multi-class classification, or more general vector-valued learning. Multi-class classification and multi-label learning are typical vector-valued learning problems. The assumption of Lipschitz continuity of the loss here is easy to satisfy. For multi-class classification, multi-class margin-based loss, multinomial logistic loss, Top-k hinge loss, etc. are all $\\ell_\\infty$ Lipschitz continuous. For multi-label learning, the surrogate loss for Macro-Averaged AUC is also $\\ell_\\infty$ Lipschitz continuous:\n\n$\nL_M (\\boldsymbol{f}(\\boldsymbol{x}, \\boldsymbol{x}^\\prime), \\boldsymbol{y}) \n$\n\n$\n=\\frac{1}{c} \\sum_{j=1}^c \\ell \\left(f_j(\\boldsymbol{x})-f_j(\\boldsymbol{x}^\\prime)\\right),\n$\n\nwhere $\\boldsymbol{x}^{(\\prime)}$ corresponds to the instances that are (ir)relevant to the $j$-th label.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "FMpw9Ub7Ls", "reviewer": "Reviewer_BRgR", "summary": "This paper proposes a new vector contraction inequality and derives a tighter label-specific representation learning (LSRL) generalization bound based on it.\nThis paper derives bounds for general function classes of LSRL with a tighter dependency on c than the SOTA, which provides a general theoretical guarantee for LSRL.And it also derives bounds for typical LSRL methods, which reveals the impact of different label- specific representations on the generalization analysis.", "questions": "The essence of LSRL is to divide multi-label classification into c binary classification problems. So why not refer to the binary classification problem's boundaries when deriving the boundary, such as k-means clustering-based LSRL method?", "limitations": "Yes.", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "1. The paper proposes a new vector contraction inequality and derives a tighter LSRL generalization bound based on it, which has a more concise dependence on the number of labels compared to existing results.\n2. The paper analyzes the generalization bounds of three typical LSRL methods, revealing the impact of different label-specific representations on generalization analysis, which helps better understand the good practical performance of LSRL. \n3. The projection function class improves the vector-contraction inequalities  and decouples the relationship among different components.", "weaknesses": "The description of the derivation of the general bound in the main text is too brief. For better reading experience, the paper should give more details and some more intuitive description (such as lemma 1 and Theorem 1).", "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 Weakness.**\n\n$\\bullet$ We will add the proof sketch for Lemma 1 as follows:\n\nFirst, the Rademacher complexity of the loss function space associated with $\\mathcal{F}$ can be bounded by the empirical $\\ell_\\infty$ norm covering number with the refined Dudley's entropy integral inequality. Second, according to the Lipschitz continuity w.r.t the $\\ell_\\infty$ norm, the empirical $\\ell_\\infty$ norm covering number of $\\mathcal{F}$ can be bounded by the empirical $\\ell_\\infty$ norm covering number of $\\mathcal{P}(\\mathcal{F})$. Third, the empirical $\\ell_\\infty$ norm covering number of $\\mathcal{P}(\\mathcal{F})$ can be bounded by the fat-shattering dimension, and the fat-shattering dimension can be bounded by the worst-case Rademacher complexity of $\\mathcal{P}(\\mathcal{F})$. Hence, the problem is transferred to the estimation of the worst-case Rademacher complexity. Finally, we estimate the lower bound of the worst-case Rademacher complexity of $\\mathcal{P}(\\mathcal{F})$ by the Khintchine-Kahane inequality, and then combined with the above steps, the Rademacher complexity of the loss function space associated with $\\mathcal{F}$ can be bounded. \n\nThis proof sketch has been moved to the appendix due to the limitation of paper length. \n\n$\\bullet$ We will add the proof sketch for Theorem 1 as follows:\n\nWe first upper bound the worst-case Rademacher complexity $\\tilde{\\Re}_{nc}(\\mathcal{P}(\\mathcal{F}))$, and then combined with Lemma 1, the desired bound can be derived.\n\nWe will add these proof sketches to the main paper in the revised version to improve the readability of the paper.\n\n**2. Response to the Question.**\n\nSince the prediction function of multi-label learning is a vector-valued function, which makes traditional Rademacher complexity analysis methods applicable to the class of scalar-valued functions or binary classification functions invalid. Hence, we need to convert the Rademacher complexity of a loss function space associated with the vector-valued function class $\\mathcal{F}$ into the Rademacher complexity of a tractable scalar-valued function class or binary classification function class. We can then use existing analysis methods to bound the complexity of the class of scalar-valued functions or binary classification functions.\n\nA basic bound with a linear dependency on the number of labels (c) comes from the following inequality: \n\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\n$\n\t\\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$, \n\nwhere we can use the generalization analysis method of the binary classification problem to bound the Rademacher complexity on the right side of the inequality. The dependency of the bounds on c can be improved to square-root by preserving the coupling among different components. However, these existing analysis methods based on preserving the coupling are not applicable to LSRL, and the induced generalization bounds are not tight enough and have a strong dependency on c. Hence, we introduce the projection function class to decouple the relationship for LSRL and derive new vector-contraction inequality, which convert the Rademacher complexity of a loss function space associated with the vector-valued function class $\\mathcal{F}$ into the Rademacher complexity of the projection function class (i.e., binary classification function class), then we can derive tighter bounds with a weaker dependency on c than the SOTA. \n\t\nFor k-means clustering-based LSRL method, when we bound the complexity of the projection function class, in the binary classification problem corresponding to each label, we use k-means clustering to generate the centers of the K clusters. Hence, the complexity of the function class of k-means clustering needs to be considered in bounding the complexity, as we discussed in Remark 2. When bounding the complexity of the function class of k-means clustering, we did not consider directly using existing analysis methods for clustering, since existing analysis methods often lead to bounds with a linear or stronger dependency on the number of clusters (K). Hence, in order to obtain a tighter generalization bound that matches the lower bound $\\Omega(\\sqrt{{K}/{n}})$ for k-means clustering, we formalize k-means clustering as a vector-valued learning problem, and develop a novel vector-contraction inequality for k-means clustering that can induce bounds with a square-root dependency on K. The generalization bound of k-means clustering-based LSRL method is tighter than the state of the art with a faster convergence rate $\\tilde{O}(\\sqrt{{K}/{n}})$, which is independent on c. Our bound is (nearly) optimal, up to logarithmic terms, both from the perspective of clustering and from the perspective of multi-label learning.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We would like to thank all reviewers for your efforts in reviewing this paper, as well as your constructive comments and active interest in helping us improve the quality of the paper. 

We provide detailed responses to the questions of each reviewer. Here we first make a brief summary of our responses:

**$\bullet$ On the derivation process of the novel vector-contraction inequality (i.e., Lemma 1):** The proof sketch for Lemma 1 is moved to the appendix due to the limitation of paper length. We will add the corresponding proof sketches to the main paper to improve the readability of the paper.

**$\bullet$ Explanations and discussions of problems such as the wider applicability of theoretical results and their guidance for practice:** We have provided detailed responses to each reviewer's specific questions, and we will add a Discussion section to incorporate these explanations and discussions of these problems into the paper in an appropriate manner.

----

Next, since the limitation of 6000 characters in each rebuttal, we will provide detailed response to the limitation raised by Reviewer Axy4 in this global rebuttal.

**$\bullet$ Response to the Limitation by Reviewer Axy4**

**(1)** This is a purely theoretical work on capacity-based generalization analysis. There was no theoretical analysis on LSRL before. The main goal of this work is to address the deficiencies of existing theoretical results (i.e., existing bounds with a linear or square-root dependency on c cannot provide general theoretical guarantees for multi-label learning, and existing generalization analysis methods that preserves the coupling among different components are not applicable to LSRL), establish a theoretical framework and provide effective and general theoretical analysis tools for the generalization analysis of LSRL. Based on the proposed theoretical framework, we focus on the capacity of models corresponding to several typical LSRL methods, analyze the complexity of these LSRL models, obtain capacity-based generalization bounds, and provide new theoretical results and tools for k-means clustering, Lasso, and DNNs. Compared with algorithm-based generalization analysis, experimental verification is not necessary for capacity-based generalization analysis. The style of this type of purely theoretical work is similar, as in literature [1-9], etc.

[1] Tomer Levy, Felix Abramovich. "Generalization Error Bounds for Multiclass Sparse Linear Classifiers", JMLR 2023.

[2] Yi-Fan Zhang, Min-Ling Zhang. "Nearly-tight Bounds for Deep Kernel Learning", ICML 2023.

[3] Yunwen Lei, Tianbao Yang, Yiming Ying, Ding-Xuan Zhou. "Generalization Analysis for Contrastive Representation Learning", ICML 2023.

[4] Shaojie Li, Yong Liu. "Sharper Generalization Bounds for Clustering", ICML 2021.

[5] Peter L. Bartlett, Nick Harvey, Christopher Liaw, Abbas Mehrabian. "Nearly-tight VC-dimension and Pseudodimension Bounds for Piecewise Linear Neural Networks", JMLR 2019. 

[6] Noah Golowich, Alexander Rakhlin, Ohad Shamir. "Size-Independent Sample Complexity of Neural Networks", COLT 2018.

[7] Andreas Maurer. "Bounds for Linear Multi-Task Learning", JMLR 2006.

[8] Sara van de Geer. "On Tight Bounds for the Lasso", JMLR 2018.

[9] Nathan Srebro, Karthik Sridharan, Ambuj Tewari. "Smoothness, Low Noise and Fast Rates", NIPS 2010.

**(2) On the rationality and satisfiability of assumptions.** In fact, the mild assumptions here are easy to satisfy. The only assumptions involved in our analysis are the boundedness of the functions and the Lipschitz continuity of the loss functions. These assumptions are relatively mild and are satisfied in practical applications. As we explain in the main paper, the $\ell_\infty$ Lipschitz continuity of the loss functions is satisfied for the commonly used loss functions we analyzed, as proved by Proposition 1. 

The assumption of the boundedness of the functions is a common assumption in generalization analysis for various learning settings, such as deep learning [2], [6], clustering [4], kernel methods [10], [11], [12], multi-classification [13], etc. In addition, in practice, the boundedness of functions can often be guaranteed, which appears in empirical evidences as support for constraints (i.e., boundedness) on weights and nonlinear mappings.

For shallow models, such constraints are easy to satisfy. Since normalization of input features is a common data preprocessing operation in machine learning, performing single nonlinear mapping on the normalized data will not significantly change the scale of the data, which ensures the boundedness of nonlinear mappings. Through proper data preprocessing and normalization, the scale of weights of the final model with good performance is controllable, i.e., the numerical values of weights are bounded.

For deep models, in order to achieve good generalization performance, many strategies and techniques commonly used in practice are actually to ensure that these constraints hold. For example, in order to prevent exploding gradient in the training of DNNs, commonly used techniques such as weight regularization and Xavier initialization are to ensure that the weights are within a certain range (i.e., the boundedness of weights), and commonly used techniques such as mean normalization and batch normalization are to ensure that the inputs and outputs of each layer are within a certain range (i.e., the boundedness of nonlinear mappings).

[10] Corinna Cortes, Mehryar Mohri, Afshin Rostamizadeh. "Generalization Bounds for Learning Kernels", ICML 2010.

[11] Corinna Cortes, Marius Kloft, Mehryar Mohri. "Learning Kernels Using Local Rademacher Complexity", NIPS 2013.

[12] Nathan Srebro, Shai Ben-David. "Learning Bounds for Support Vector Machines with Learned Kernels", COLT 2006.

[13] Yunwen Lei, Ürün Dogan, Ding-Xuan Zhou, Marius Kloft. "Data-dependent generalization bounds for multi-class classification", IEEE Transactions on Information Theory 2019.

Meta-review: The reviewers of this paper provided thorough reviews and engaged with the authors during the discussion period. The authors propose a new (tighter) bound for label-specific representation learning based on a novel vector-contraction inequality. The reviewers have praised the work and have been satisfied with the answers given by the authors during the feedback period.
Decision: Accept (spotlight)