Generalization Analysis for Label-Specific Representation Learning

Authors: yi-fan  zhang
min-ling  zhang
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 21:14:28

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.

Main paper: 
 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 a single instance associated with multiple class labels [Zhang and Zhou, 2014, Liu et al., 2022] . The goal of multi-label learning is to model real-world objects with multiple semantics. It has made important advances in multimedia content annotation [Cabral et al., 2011 , You et al., 2020 ], text categorization [Rubin et 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 an instance for dealing with multi-label data being perhaps suboptimal [Zhang and Wu, 2015 , Huang et al., 2016 , Hang and Zhang, 2022] . In recent years, label-specific representation learning (LSRL) [Zhang 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 an effective strategy to improve the performance of multi-label learning [Huang et al., 2015 , 2016 , 2018 , Yu and Zhang, 2022 , Hang and Zhang, 2022 , Hang et al., 2022] . Although LSRL has achieved impressive empirical advances in multi-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 an important open problem in multi-label learning community. The empirical success of LSRL makes the generalization 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-root dependency on c are difficult to explain empirical success of multi-label learning. For example, the bounds with a linear dependency on c are vacuous (i.e., no longer less than 1) for commonly used multi-label datasets such as CAL500, corel5k, rcv1-s1, Corel16k-s1, delicious, iaprtc12, espgame, etc., since c is larger than √ n (the number of examples) for these datasets. The bounds with a linear or square-root dependency on c 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 multilabel learning also applies to LSRL. Hence, this suggests that only the bounds with weaker dependency on c can provide effective theoretical guarantees. Second, existing theoretical results preserve the coupling among different components [Lei et al., 2015 , 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 a better understanding of multi-label learning.In this paper, we derive novel and tighter bounds based on the Rademacher complexity for LSRL. Specifically, we develop a novel vector-contraction inequality with the assumption that the loss function is Lipschitz continuous w.r.t. the ∞ norm, then we derive the bound for general function classes of LSRL with no dependency on c, up to logarithmic terms, which is tighter than the state of 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.Our bounds for LSRL improve the dependency on c. Major contributions of the paper include:• We develop a novel vector-contraction inequality for ∞ 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 labelspecific representations on the generalization analysis. The theoretical techniques and results on k-means clustering, Lasso, and DNNs involved here may be of independent interest.2 Related Work 
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, 2007 , Zhang et al., 2018] which tackle multi-label learning problem by decomposing it into a number of independent binary classification problems, second-order methods [Elisseeff 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 et al., 2020] , 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 (LSRL) have been proven to be another effective strategy to improve multi-label learning by manipulating the input space. Existing methods can be roughly grouped into three major categories based on the construction method of label-specific representations, i.e., prototype-based label-specific representation transformation methods [Zhang and Wu, 2015 , Zhang et al., 2015 , Weng et al., 2018 , Guo et al., 2019 , Zhang and Li, 2021] which generate label-specific representations by treating the prototypes of 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, 2022] 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-end manner by exploiting deep models. In particular, k-means clustering-based 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 inputs and the cluster centers for each class label. Lasso-based LSRL, i.e., LLSF [Huang et al., 2016] , is the representative method of label-specific feature selection methods, which presents a Lasso-based framework with the constraint of pairwise label correlations for each class label. DNN-based LSRL, i.e., CLIF [Hang and Zhang, 2022] , is the representative method of deep label-specific 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.Dembczynski et al. [2010] derived the relationship between the expectations of Hamming and Subset loss based on the regret analysis on Hamming and Subset loss, and Dembczynski 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-contraction inequality [Maurer, 2016] (i.e., assume that the loss function is Lipschitz continuous w.r.t. the 2 norm), one can obtain generalization bounds of order O(c/ √ n) for multi-label learning. Wu and Zhu [2020] , Wu et al. [2021a] showed that the order of the generalization bounds for Subset loss, Hamming Loss and reweighted convex surrogate univariate loss can be improved to O( c/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 a generalization bound of order O(log(nc)/nσ) for norm regularized kernel function classes with the assumptions that the loss function is Lipschitz continuous w.r.t. the ∞ norm and the regularizer is σ-strongly convex with respect to some norms. Yu et al. [2014] obtained a generalization bound of order O(1/ √ n) for trace norm regularized linear function classes with Decomposable loss. Xu et al. [2016] used the local Rademacher complexity to derive a generalization bound of order O(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 O(1/ √ n) bounds for Macro-Averaged AUC and gave thorough discussions about its relationships with the label-wise class imbalance, which transformed the macro-averaged maximization problem in multi-label learning into the problem of learning multiple tasks with graph-dependent examples. Here we obtain O(1/ √ n) bounds with the state-of-the-art dependency on the number of labels for LSRL function classes under the assumption that the loss function is Lipschitz continuous w.r.t. the ∞ norm. 
preliminaries: 
 Let [n] := {1, . . . , n} for any natural number n. In the context of multi-label learning, given a dataset D = {(x 1 , y 1 ) , . . . , (x n , y n )} with n examples which are identically and independently distributed (i.i.d.) from a probability distribution P on X × Y, where X ⊂ R d denotes the d-dimensional input space and Y denotes the label space with c class labels, x ∈ X , y ∈ Y ⊆ {-1, +1} c , i.e., each y = (y 1 , . . . , y c ) is a binary vector and y j = 1 (y j = -1) denotes that the j-th label is relevant (irrelevant), j ∈ [c]. The task of multi-label learning is to learn a multi-label classifier h ∈ H : X → {-1, +1} c which assigns each instance with a set of relevant labels. A common strategy is to learn a vector-valued function f = (f 1 , . . . , f c ) : X → R c and derive the classifier by a thresholding function which divides the label space into relevant and irrelevant label sets.For any vector-valued function f : X → R c , the prediction quality on the example (x, y) is measured by a loss function : R c × {-1, +1} c → R + . The goal of learning is to find a hypothesis f ∈ F with good generalization performance from the dataset D by optimizing the loss . The generalization performance is measured by the expected risk: R(f ) = E (x,y)∼P [ (f (x) , y)]. We denote the empirical risk w.r.t. the training dataset D as R D (f ) = 1 n n i=1 (f (x i ), y i ). We denote the optimal risk as R * = inf f ∈F R(f ), the minimizer of the optimal risk as f * = arg min f ∈F R(f ) and denote the minimizer of the empirical risk as f * = arg min f ∈F R D (f ). In addition, we define the loss function space as L = { (f (x), y) : f ∈ F}, where F is the vector-valued function class.Label-specific representation learning aims to 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 c binary classification problems, i.e., decoupling the relationship among different components, where each binary classification problem corresponds to a possible label in the label space. We consider the prediction function for each label of the general form f j (x) = w j , ζ j (φ j (x)) , where the inner nonlinear mapping φ j corresponds to the nonlinear transformation induced by the construction method of label-specific representation, while the outer nonlinear mapping ζ j refers to the nonlinear mapping corresponding to the classifier learned on the generated label-specific representation. We define a vector-valued function class of LSRL as follows:F = {x → f (x) :f (x) = (f 1 (x), . . . , f c (x)), f j (x) = h j (φ j (x)) = w j ζ j (φ j (x)), w = (w 1 , . . . , w c ) ∈ R d×c , α(w) ≤ Λ, β(ζ j (•)) ≤ A, γ(φ j (•)) ≤ C, x ∈ X , j ∈ [c], Λ, A, C > 0}, (1)where α represents a functional that constrains weights, β represents a functional that constrains nonlinear mappings ζ j , γ represents a functional that constrains nonlinear mappings φ j .A number of evaluation metrics are proposed to measure the generalization performance of different multi-label learning methods. Here we focus on commonly used evaluation metrics, i.e., Hamming Loss, Subset Loss, Ranking Loss and Decomposable Loss. However, the above mentioned loss functions are typically 0/1 losses, which are actually hard to handle in optimization. Hence, one usually consider their surrogate losses, which are defined as follows:Hamming Loss :H (f (x), y) = 1 c c j=1 b (y j f j (x)) ,where the base convex surrogate loss b can be various popular forms, such as the hinge loss, the logistic loss, the exponential loss and the squared loss.Subset Loss :S (f (x), y) = max j∈[c] { b (y j f j (x))} . Ranking Loss : R (f (x), y) = 1 |Y + | |Y -| p∈Y + q∈Y - b (f p (x) -f q (x)) ,where Y + (Y -) denotes the relevant (irrelevant) label index set induced by y, and | • | denotes the cardinality of a set.: D (f (x), y) = c j=1 b (y j f j (x)) .Here we introduce the complexity measures involved in theoretical analysis. The Rademacher complexity is used to perform generalization analysis for LSRL. G) = E D [ ˆ D (G)]as the Rademacher complexity of G. In addition, we define the worst-case Rademacher complexity as ˜ n (G) = sup D∈X n ˆ D (G), and its expectation is denoted as˜ (G) = E D [ ˜ n (G)].In multi-label learning, f ∈ F is a vector-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-sensitive complexity measures, such as the covering number and fat-shattering dimension [Srebro et al., 2010, 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 vectorvalued function are bounded:x i 2 ≤ R, (•, •) ≤ M , |f j (•)| ≤ B for i ∈ [n], j ∈ [c] where R > 0, M > 0 and B > 0 are constants. Assumption 2. Assume that the loss function is ρ-Lipschitz continuous w.r.t. the ∞ norm, that is: (f (x), •) -(f (x), •) ≤ ρ f (x) -f (x) ∞ , where ρ > 0, t ∞ = max j∈[c] |t j | for t = (t 1 , . . . , t c ).Assumption 1 and 2 are mild assumptions. For Assumption 1, normalization of input features is a common data preprocessing operation. When we consider the function class (1), we often use the assumptions w j 2 ≤ Λ, ζ j (•) 2 ≤ A for any j ∈ [c] to replace the boundedness of the components of the vector-valued function, i.e., B := ΛA. For Assumption 2, the Lipschitz continuity w.r.t. the ∞ norm has been considered in some literature [Foster and Rakhlin, 2019 , Lei et al., 2019 , Wu et al., 2021b] . The following Proposition 1 further illustrates that the commonly used loss functions in multi-label learning actually satisfy Assumption 2. Proposition 1. Assume that the base loss b defined in Subsection 3.2 is µ-Lipschitz continuous, then the surrogate Hamming Loss is µ-Lipschitz w.r.t. the ∞ norm, the surrogate Subset Loss is µ-Lipschitz w.r.t. the ∞ norm, the surrogate Ranking Loss is 2µ-Lipschitz w.r.t. the ∞ norm, and the surrogate Decomposable Loss is cµ-Lipschitz w.r.t. the ∞ norm.We define a function class P consisting of projection operators p j : R c → R for any j ∈ [c] which project the c-dimensional vector onto the j-th coordinate. Then, we haveP(F) = {(j, x) → p j (f (x)) : p j (f (x)) = f j (x), f ∈ F, (j, x) ∈ [c] × X }.The projection function class decouples the relationship among different components. With the assumption of ∞ 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: Lemma 1. Let F be a vector-valued function class of LSRL defined by (1). Let Assumptions 1 and 2 hold. Given a dataset D of size n. Then, we haveˆ D (L) ≤ 12 √ 2ρ √ c nc (P(F)) 1 + log 1 2 (8e 2 n 3 c 3 ) • log M √ n ρB ,whereˆ D (L) = E sup ∈L,f ∈F 1 n n i=1 i (f (x i ))is the empirical Rademacher complexity of the loss function space associated with F, and nc (P(F)) is the worst-case Rademacher complexity of the projection function class.Proof Sketch. First, the Rademacher complexity of the loss function space associated with F can be bounded by the empirical ∞ norm covering number with the refined Dudley's entropy integral inequality. Second, according to the Lipschitz continuity w.r.t the ∞ norm, the empirical ∞ norm covering number of F can be bounded by that of P(F). Third, the empirical ∞ 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 P(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 a vector-valued function class of LSRL defined by (1). Let Assumptions 1 and 2 hold. Given a dataset D of size n. Then, for any 0 < δ < 1, with probability at least 1 -δ, the following holds for any f ∈ F:R(f ) ≤ R D (f ) + 24 √ 2ρΛA 1 + log 1 2 (8e 2 n 3 c 3 ) • log M √ n ρB √ n + 3M log 2 δ 2n .Proof Sketch. We first upper bound the worst-case Rademacher complexity ˜ nc (P(F)), and then combined with Lemma 1, the desired bound can be derived.Remark 1. Although Lemma 1 shows a factor of √ c, the term nc (P(F)) ≤ ΛA/ √ nc, which makes the Rademacher complexity of the loss function space associated with F (i.e., ˆ D (L)) actually independent on c, up to logarithmic terms, and results in a tighter bound than the existingO(c/ √ n) and O( c/n) bounds with a faster convergence rate O(1/ √ n).The bound in Theorem 1 with no dependency on c can provide a 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 √ n. The main challenge of generalization analysis for LSRL is that existing theoretical results and existing generalization analysis methods for multi-label learning are not applicable to LSRL. Specifically, existing theoretical bounds often involve the typical vectorcontraction inequality [Maurer, 2016] for 2 Lipschitz loss:E sup f ∈F 1 n n i=1 i (f (x i )) ≤ √ 2µE sup f ∈F 1 n n i=1 c j=1 ij f j (x i) , which will lead to bounds with a linear dependency on c for multi-label learning. Lei et al. [2015] , Wu and Zhu [2020] , Wu et al. [2021a] improve the dependency of the bounds on c to square-root, which preserve the coupling among different components reflected by the constraint w ≤ Λ. Lei et al. [2019] also improves the bounds of multi-class classification to be independent on c (up to logarithmic terms) for ∞ Lipschitz loss by preserving the coupling among different components, and Wu et al. [2021b] further generalizes these results to multi-label learning. However, LSRL decomposes the multi-label learning problem into c binary classification problems, which means that the relationship among different components needs to be decoupled in the generalization analysis. Hence, how to develop novel vector-contraction inequalities that can induce O(1/ √ n) 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-contraction inequalities by a factor of √ c and decouples the relationship among different components (which is also reflected by the constraint w j ≤ Λ for any j ∈ [c]). Our tighter O(1/ √ n) bound in Theorem 1 with no dependency on c (up to logarithmic terms) solve the limitations of existing theoretical results for multi-label learning and can provide a general theoretical guarantee for LSRL.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 1, the Lipschitz constants ρ 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 ζ(•) ≤ A := κR (κ is the Lipschitz constant of the nonlinear mappings ζ(•)) to take into account the differences or characteristics of different LSRL 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 1. For each LSRL method, we first give a brief introduction, then give its formal definition corresponding to the class of LSRL defined in (1), and finally derive the generalization bound.As a seminal work, k-means clustering-based LSRL method, i.e., LIFT [Zhang and Wu, 2015] , uses k-means clustering to construct label-specific representation that effectively capture the specific characteristics of 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 asc j k for the j-th label, k ∈ [K], j ∈ [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 (1),φ j (x) = d(x, c j 1 ), . . . , d(x, c j K ) , d(x, c j k ) = x -c j k .Finally, a family of c classifiers f j with κ-Lipschitz nonlinear mapping are induced based on the generated label-specific representations.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 2 → R + is a pairwise distance-based function used to measure the dissimilarity between pair observations, andZ = [Z 1 , . . . , Z K ] is a collection of K partition functions Z k : X 2 → R + for k ∈ [K].The clustering framework can be cast as the problem of minimizing the following criterion:R D (V, Z) = 1 n(n -1) n i,j=1,i =j K k=1 V (x i , x j ) Z k (x i , x j ) over all possible functions V and Z k for k ∈ [K]. In k-means clustering, we have V (x i , x j ) = x i -x j 2 2 , and Z k (x i , x j ) = I (x i , x j ) ∈ C 2 k , c k = 1 |C k | x∈C k x,where C 1 , . . . , C K are the partitions of the feature space X . Let g k (x i , x j ) = V (x i , x j ) Z k (x i , x j ) and g = (g 1 , . . . , g K ) be a vector-valued function, clu (g(x, x )) = K k=1 g k (x, x ), then R D (V, Z) can be written asR D (V, Z) = 1 n(n -1) n i,j=1,i =j clu (g(x i , x j )) = 1 n(n -1) n i,j=1,i =j K k=1 g k (x i , x j ) .We then define a vector-valued function class of k-means clustering as follows:G = {(x, x ) → g(x, x ) :g(x, x ) = (g 1 (x, x ), . . . , g K (x, x )), g k (x, x ) = x -x 2 2 • I (x, x ) ∈ C 2 k , x, x ∈ X , k ∈ [K]}, where |g k (•, •)| ≤ G for k ∈ [K] and G > 0 are constants.We denote the function class of k-means clustering corresponding to the j-th label as G j . With the above definitions, we can derive the tight bound for k-means clustering-based LSRL method: Theorem 2. Let F be a vector-valued function class of k-means clustering-based LSRL defined by (1). Let Assumptions 1 and 2 hold. Given a dataset D of size n. Then, for any 0 < δ < 1, with probability at least 1 -δ, the following holds for any f ∈ F:R(f ) ≤ R D (f ) + 3M log 2 δ 2n + 48 √ 2ρκΛ √ KR 1 + log 1 2 (8e 2 n 3 c 3 ) • log M √ n µB √ n + 24 2 √ 2ρ √ KG √ n 1 + log 1 2 (e 2 n 3 c 3 ) • log M √ nc G 1 + log 1 2 (8e 2 n 3 c 3 ) • log M √ n µB .Remark 2. There are three key points in the generalization analysis of k-means clustering-based LSRL method. 1) Since k-means clustering-based LSRL method is two-stage, i.e., the centers of 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 a multi-label classifier in the second stage, we cannot formally express these two stages in a closed-form expression through a composite function (K centers are generated by the arg min function). Furthermore, K centers generated in 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 function class as the sum of the function classes F + L clu • G corresponding to the methods of these two stages. Then, combined with Lemma 1, the generalization analysis is transformed into the bounding of the complexity of the projection function class P(F + L clu • G). 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-based 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.i.d case for traditional Rademacher complexity inapplicable for k-means clustering. We convert the non-sum-of-i.i.d pairwise function to a sum-ofi.i.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 can be bounded byˆ D (L clu • G) := E sup g∈G 1 n 2 n 2 i=1 i clu (g(x i , x i+ n 2 )). 3) In order to derive tight bounds for k-means clustering, we develop a novel vector-contraction inequality that can induce bounds with a square-root 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-based LSRL method is tighter than the state of the art with a faster convergence rate O( K/n), which is independent on the number of labels. Since the lower bound for clustering is Ω( 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 1 corresponds to 2κ √ KR here.Lasso-based LSRL method, i.e., LLSF [Huang et al., 2016] , assumes that the label-specific representation 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 be large.Formally, since each label corresponds to a Lasso, this means that in the class of LSRL defined by (1), the base loss b is the squared loss, the nonlinear mappings ζ(•) and φ(•) are both identity transformations for any j ∈ [c], and the constraint α(w) is w j 1 ≤ Λ for any j ∈ [c]. For the j-th label, the property of sharing is reflected by the additionally introduced constraint c i (1s ji )w j w i ≤ τ , where s ji is the cosine similarity between labels y j and y i , here we refer to it 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 on the Lipschitz continuity of the loss functions in Proposition 1 cannot be applied to Lasso-based LSRL method. To overcome this challenge, we define the pseudo-Lipschitz 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 a function f : R → R is pseudo-Lipschitz of order k if there exists a constant L > 0 such that the following inequality holds for all x, y ∈ R:|f (x) -f (y)| ≤ L 1 + |x| k-1 + |y| k-1 |x -y|.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 of order 2, the surrogate Decomposable Loss is (3 + 2B)c-Lipschitz w.r.t. the ∞ norm if the base loss b 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 (1). Let Assumptions 1 and 2 hold. Given a dataset D of size n. Then, for any 0 < δ < 1, with probability at least 1 -δ, the following holds for any f ∈ F:R(f ) ≤ R D (f ) + 24 √ 2(3 + 2B)cΛR 1 + log 1 2 (8e 2 n 3 c 3 ) • log M √ n ρB √ n + 3M log 2 δ 2n .Remark 3. 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 LSRL function class where each label corresponds to a Lasso. Hence, the complexity analysis of the LLSF function class can be converted into upper bounding the Rademacher complexity of the LSRL function class where each label corresponds to a Lasso. The constant A of the generalization bound in Theorem 1 corresponds to R here, and the value of ρ is (3 + 2B)c, which induce the O(c/ √ n) bound here. If other loss functions are used, e.g., Hamming, Subset or Ranking loss, instead of Decomposable loss, the dependency of the bounds for Lasso-based LSRL method on c can be improved from linear to independent, up to logarithmic terms.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 endto-end manner. Since the construction of label-specific representation involves graph convolutional networks (GCNs), we first introduce the relevant definitions for GCN.Let G = {V, E} be a given undirected graph, where V = {x 1 , x 2 , . . . , x n } is the set of nodes with size |V| = n and E is the set of edges. Let A and D be the adjacency matrix and the diagonal degree matrix respectively, whereD ii = n j=1 A ij . Let Ã = (D + I n ) -1 2 (A + I n ) (D + I n ) -12 denote the normalized adjacency matrix with self-connections, where I is the identity matrix. The feature propagation process of a two-layer GCN is σ( Ãσ( ÃXW 1 )W 2 ), where W 1 and W 2 are parameter matrices, X is the node feature matrix, and the i-th row X i * is the node feature x i . 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.e., the label embeddings can be denoted by ψ(Y ) = σ ReLU ( Ãσ ReLU ( ÃY W 1 )W 2 ), where Y is the node feature matrix of the label graph with size c and the nodes are also bounded by R, σ ReLU is the ReLU activation. Second, the label embedding of the j-th label is decoded into the importance vector by a one-layer fully-connected neural network, i.e., σ sig (W 3 ψ(Y ) j ), where σ sig is the sigmoid activation, and the input feature is mapped into the latent representation through a one-layer fully-connected neural network, i.e., σ ReLU (W 4 x). 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φ j (x) = σ ReLU {W 5 • [σ ReLU (W 4 x) σ sig (W 3 ψ(Y ) j )]} .Finally, the j-th model is implemented by a fully-connected layer, i.e., f j (x) = σ sig (w j φ j (x)).In the generalization analysis of the above deep neural network, we introduce the following assumption, 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 i ≤ D, i ∈ [5], where D > 0 is a constant.With the above definitions, we can derive the generalization bound for DNN-based LSRL method: Theorem 4. Let F be a vector-valued function class of DNN-based LSRL defined by (1). Let Assumptions 1, 2, and 3 hold. Given a dataset D of size n. Then, for any 0 < δ < 1, with probability at least 1 -δ, the following holds for any f ∈ F:R(f ) ≤ R D (f ) + 6 √ 2ρΛD 5 R 2 (g max + 1) 1 + log 1 2 (8e 2 n 3 c 3 ) • log M √ n ρB √ n + 3M log 2 δ 2n ,where g max is the maximum node degree of the label graph.Remark 4. The term nc (P(F)) ≤ ΛD 5 R 2 (g max + 1)/4 √ nc, which makes the Rademacher complexity ˆ D (L) actually independent on c, up to logarithmic terms, and results in a tight bound for DNN-based LSRL method with a faster convergence rate O(1/ √ n). The constant A of the generalization bound in Theorem 1 corresponds to D 5 R 2 (g max + 1)/4 here. For deep GCNs, the increase in depth means that the generalization performance will deteriorate, which is consistent with empirical performance and 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 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., hypernetworks [Galanti and Wolf, 2020 , Chen et al., 2023 , Shen et al., 2023] , deep kernel networks [Zhang and Liao, 2020, Zhang and Zhang, 2023] , and provide generalization analysis for the corresponding DNN-based LSRL methods. 
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 performance of multi-label learning. On the one hand, existing results can improve the dependency of the bound on c 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 √ cΛ with Λ in the constraint to some extent, and preserving the coupling corresponds to the stricter assumption [Zhang and Zhang, 2024] . Our 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. On the other hand, based on our results, we can find that LSRL 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 vector-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 vectorvalued learning problem. For multi-class classification, multi-class margin-based loss, multinomial logistic loss, Top-k hinge loss, etc. are all ∞ Lipschitz [Lei et al., 2019] . For multi-label learning, the surrogate loss for Macro-Averaged AUC is also ∞ Lipschitz [Zhang and Zhang, 2024] . 
conclusion: 
 In this paper, we propose a novel vector-contraction inequality for ∞ 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 a 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. 
 
 Appendix: In the appendix, we give the detailed proofs of those theoretical results in the main paper. Our main proofs include:• The ∞ Lipschitz continuity of the commonly used losses for LSRL (Proposition 1).• The novel vector-contraction inequality for ∞ Lipschitz loss (Lemma 1).• The generalization bound of the general LSRL class with no dependency on c (Theorem 1).• The generalization bound for k-means clustering-based LSRL method (Theorem 2).• The (pseudo-) Lipschitz continuity of the squared and Decomposable loss (Proposition 2).• The generalization bound for Lasso-based LSRL method (Theorem 3).• The generalization bound for DNN-based LSRL method (Theorem 4).Definition 3 ( ∞ norm covering number). Let F be a class of real-valued functions mapping from X to R. Let D = {x 1 , . . . , x n } be a set with n i.i.d. samples. For any > 0, the empirical ∞ norm covering number N ∞ ( , F, D) w.r.t. D is defined as the minimal number m of a collectionof vectors v 1 , . . . , v m ∈ R n such that max i∈[n] f (x i ) -v j i ≤ (v j i is the i-th component of the vector v j ). In this case, we call v 1 , . . . , v m an ( , ∞ )-cover of F with respect to D. We also define N ∞ ( , F, n) = sup D N ∞ ( , F, D).Definition 4 (Fat-shattering dimension). Let F be a class of real-valued functions mapping from X to R. We define the fat-shattering dimension fat (F) at scale > 0 as the largest p ∈ N such that there exist p points x 1 , . . . , x p ∈ X and witnesses s 1 , . . . , s p ∈ R satisfying: for any δ 1 , . . . , δ p ∈ {-1, +1} there exists f ∈ F with δ i (f (x i ) -s i ) ≥ , ∀i = 1, . . . , p.D = {(x i , y i ) : i ∈ [n]}, let D = {(x i , y i ) : i ∈ [n]} be the training dataset with only one sample different from D, where the k-th sample is replaced by(x k , y k ). Let Φ(D) = sup f ∈F [E (x,y)∼P [ (f (x), y)] -1 n n i=1 (f (x i ), y i )] = sup f ∈F [R(f ) -R D (f )], then Φ (D ) -Φ(D) = sup f ∈F [R(f ) -R D (f )] -sup f ∈F [R(f ) -R D (f )] ≤ sup f ∈F [ R D (f ) -R D (f )] = sup f ∈F [ (f (x k ), y k ) -(f (x k ), y k )] n ≤ M n .According to McDiarmid's inequality, for any 0 < δ < 1, with probability at least 1 -δ 2 over the training dataset D, the following holds:EQUATIONThen, we will estimate the upper bound ofEQUATIONThen apply McDiarmid's inequality to E sup f ∈FEQUATIONCombining with (2), ( 3) and (4), thenEQUATIONA.3 General Bounds for LSRLWe first prove that the surrogate Hamming Loss is µ-Lipschitz continuous with respect to the ∞ norm.H (f (x), y) -H f (x), y = 1 c c j=1 b (y j f j (x)) - 1 c c j=1 b y j f j (x) = 1 c c j=1 b (y j f j (x)) -b y j f j (x) ≤ 1 c c j=1 µ f j (x) -f j (x) ≤ 1 c µc max j∈[c] f j (x) -f j (x) =µ f (x) -f (x) ∞ .Second, with the elementary inequality|max {a 1 , . . . , a c } -max {b 1 , . . . , b c }| ≤ max {|a 1 -b 1 | , . . . , |a c -b c |} ,we prove that the surrogate Subset Loss is µ-Lipschitz continuous with respect to the ∞ norm.S (f (x), y) -S f (x), y = max j∈[c] b (y j f j (x)) -max j∈[c] b y j f j (x) ≤ max j∈[c] b (y j f j (x)) -b y j f j (x) ≤µ max j∈[c] f j (x) -f j (x) =µ f (x) -f (x) ∞ .Third, we prove that the surrogate Ranking Loss is 2µ-Lipschitz continuous with respect to the ∞ norm.R (f (x), y) -R f (x), y = 1 |Y + | |Y -| p∈Y + q∈Y - b (f p (x) -f q (x)) -b f p (x) -f q (x) ≤ max p∈Y + ,q∈Y - b (f p (x) -f q (x)) -b f p (x) -f q (x) ≤µ max p∈Y + ,q∈Y -(f p (x) -f q (x)) -f p (x) -f q (x) ≤µ max p∈Y + f p (x) -f p (x) + max q∈Y -f q (x) -f q (x) ≤2µ max j∈[c] f j (x) -f j (x) =2µ f (x) -f (x) ∞ .Finally, we prove that the surrogate Decomposable Loss is cµ-Lipschitz continuous with respect to the ∞ norm.D (f (x), y) -D f (x), y = c j=1 b (y j f j (x)) - c j=1 b y j f j (x) = c j=1 b (y j f j (x)) -b y j f j (x) ≤ c j=1 µ f j (x) -f j (x) ≤cµ max j∈[c] f j (x) -f j (x) =cµ f (x) -f (x) ∞ .Proof Sketch: First, the Rademacher complexity of the loss function space associated with F can be bounded by the empirical ∞ norm covering number with the refined Dudley's entropy integral inequality. Second, according to the Lipschitz continuity w.r.t the ∞ norm, the empirical ∞ norm covering number of F can be bounded by the empirical ∞ norm covering number of P(F). Third, the empirical ∞ 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 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-Kahane inequality [Lust-Piquard and Pisier, 1991] ). Let v 1 , . . . , v n ∈ H, where H is a Hilbert space with • being the associated p-th norm. Let 1 , . . . , n be a sequence of independent Rademacher variables. Then, for any p ≥ 1 there holdsmin( p -1, 1) n i=1 v i 2 1 2 ≤ E n i=1 i v i p 1 p ≤ max( p -1, 1) n i=1 v i 2 1 2, and [Srebro et al., 2010] ). For any function class F, any S with a finite sample of size n and any > ˆ S (F), we have that Srebro et al., 2010 , Lei et al., 2019] ). If any function in class F takes values in [-B, B], then for any S with a finite sample of size n, any > 0 with fat (F) < n, we haveE n i=1 i v i ≥ 2 -1 2 n i=1 v i 2 1 2 . Lemma 3 (Lemma A.2 infat (F) ≤ 4n ˆ 2 S (F) 2 . Lemma 4 ([log N ∞ ( , F, S) ≤ fat (F) log 2eBn .The following lemma is a refined result of Proposition 22 in [Ledent et al., 2021] , where we replace the function class taking values in [0, 1] with the B-bounded function class, the refinement is obvious. Lemma 5 (Refined Dudley's entropy integral inequality). Let F be a real-valued function class with f ≤ B, f ∈ F, B > 0, and assume that 0 ∈ F. Let S be a finite sample of size n. For any 2 ≤ p ≤ ∞, we have the following relationship between the Rademacher complexity ˆ S (F) and the covering number N p ( , F, S).ˆ S (F) ≤ inf α>0 4α + 12 √ n B α log N p ( , F, S)d .Step 1: We first derive the relationship between the empirical ∞ norm covering number N ∞ ( , L, D) and the empirical ∞ norm covering number N ∞ ( ,P(F), [c] × D).For the dataset D = {(x 1 , y 1 ), . . . , (x n , y n )} with n i.i.d. examples:max i | (f (x i ), y i ) -(f (x i ), y i )| ≤ρ max i f (x i ) -f (x i ) ∞ (Use Assumption 2) ≤ρ max i max j |f j (x i ) -f j (x i ) | ≤ρ max i max j |p j (f (x i )) -p j (f (x i )|.(The definition of the projection function class P(F))Then, according to the definition of the empirical ∞ covering number, we have that an empirical ∞ cover of P(F) at radius /ρ is also an empirical ∞ cover of the loss function space associated with F at radius , and we can conclude that:EQUATIONStep 2: We show that the empirical ∞ norm covering number of P(F) can be bounded by the fatshattering dimension, and the fat-shattering dimension can be bounded by the worst-case Rademacher complexity of P(F).According to Lemma 3, for any > ˆ [c]×D (P(F)), we havefat (P(F)) ≤ 4nc ˆ 2 [c]×D (P(F)) 2 .Then, combining with Lemma 4, we havelog N ∞ ( , P(F), [c] × D) ≤ 4nc ˆ 2 [c]×D (P(F)) 2 log 2eBnc .Use inequality > ˆ [c]×D (P(F)), we haveEQUATION)Step 3: According to Assumption 1 in the main paper, we can obtain the lower bound of the worst-case Rademacher complexity nc (P(F)) by the Khintchine-Kahane inequality with p = 1:EQUATION)Step 4: According to Lemma 5 and combined with the above steps, we haveˆ D (L) ≤ inf α>0 4α + 12 √ n M α log N ∞ ( , L, D)d ≤ inf α>0 4α + 12 √ n M α log N ∞ ( ρ , P(F), [c] × D)d (Use inequality (6)) ≤ inf α>0   4α + 12 √ n M α 4ncρ 2 ˆ 2 [c]×D (P(F)) 2 log 2eBnc ˆ [c]×D (P(F)) d    (Use inequality (7)) ≤ inf α>0   4α + 12 √ n M α 4ncρ 2 2 nc (P(F)) 2 log(2 √ 2eBn 3 2 c 3 2 )d  (Use inequality (8) and the definition of the worst-case Rademacher complexity)≤ inf α>0 4α + 12 √ 2ρ √ c nc (P(F)) log 1 2 (8e 2 n 3 c 3 ) M α -1 d ≤12 √ 2ρ √ c nc (P(F)) + 12 √ 2ρ √ c nc (P(F)) log 1 2 (8e 2 n 3 c 3 ) • log M 3 √ 2ρ √ c nc (P(F)) (Choose α = 3 √ 2ρ √ c nc (P(F))) ≤12 √ 2ρ √ c nc (P(F)) + 12 √ 2ρ √ c nc (P(F)) log 1 2 (8e 2 n 3 c 3 ) • log M √ n ρB (Use inequality (8) ) =12 √ 2ρ √ c nc (P(F)) 1 + log 1 2 (8e 2 n 3 c 3 ) • log M √ n ρB .We upper bound the worst-case Rademacher complexity nc (P(F)) as the following:nc (P(F)) = sup [c]×D∈[c]×X n ˆ [c]×D (P(F)) = sup [c]×D∈[c]×X n E   sup pj (f (xi))∈P(F ) 1 nc n i=1 c j=1 ij p j (f (x i ))   = sup [c]×D∈[c]×X n E   sup fj ∈Fj 1 nc n i=1 c j=1 ij f j (x i )   = sup ζj (φj (xi)) 2≤A:i∈[n],j∈[c] 1 nc E   sup wj 2≤Λ n i=1 c j=1 ij w j , ζ j (φ j (x i ))   = sup ζj (φj (xi)) 2≤A:i∈[n],j∈[c] Λ nc E n i=1 c j=1 ij ζ j (φ j (x i )) ≤ sup ζj (φj (xi)) 2≤A:i∈[n],j∈[c] Λ nc   E n i=1 c j=1 ij ζ j (φ j (x i )) 2   1 2(Use Jensen's Inequality)≤ sup ζj (φj (xi)) 2 ≤A:i∈[n],j∈[c] Λ nc   n i=1 c j=1 ζ j (φ j (x i )) 2   1 2 ≤ ΛA √ nc . (Use Lemma 2) (9)Then, we haveˆ D (F) ≤12 √ 2ρ √ c nc (P(F)) 1 + log 1 2 (8e 2 n 3 c 3 ) • log M √ n ρB ≤ 12 √ 2ρΛA 1 + log 1 2 (8e 2 n 3 c 3 ) • log M √ n ρB √ n .Combining with (5), thenR(f ) ≤ R D (f ) + 24 √ 2ρΛA 1 + log 1 2 (8e 2 n 3 c 3 ) • log M √ n ρB √ n + 3M log 2 δ 2n .A.4 Generalization Bounds for Typical LSRL MethodsThe generalization analysis of LIFT involves the generalization analysis for k-means clustering. According to 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:ˆ D (L clu • G) = E   sup g∈G 1 n(n -1) n i,j=1,i =j i clu (g(x i , x j ))   .Rademacher complexity has proved to be a powerful data-dependent measure of hypothesis space complexity. 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.i.d case for traditional Rademacher complexity inapplicable for kmeans clustering. We convert the non-sum-of-i.i.d pairwise function to a sum-of-i.i.d form by using permutations in U-process [Clémençon et al., 2008] .We first proof the following lemma: Lemma 6. Let q τ : X × X → R be real-valued functions indexed by τ ∈ T where T is some set. If x 1 , . . . , x s and x 1 , . . . , x t are i.i.d., r = min{s, t}, then for any convex non-decreasing function ψ,Eψ   sup τ ∈T 1 st s i=1 t j=1 q τ x i , x j   ≤ Eψ sup τ ∈T 1 r r i=1 q τ (x i , x i ) .Proof. The proof of this lemma is inspired by [Clémençon et al., 2008] .Eψ   sup τ ∈T 1 st s i=1 t j=1 q τ x i , x j   =Eψ   sup τ ∈T 1 s! πx 1 t! π x 1 r r i=1 q τ x π(i) , x π(i)   ≤Eψ   1 s! πx 1 t! π x sup τ ∈T 1 r r i=1 q τ x π(i) , x π(i)   (ψ is nondecreasing) ≤ 1 s! πx 1 t! π x Eψ sup τ ∈T 1 r r i=1 q τ x π(i) , x π(i) (Jensen's inequality) =Eψ sup τ ∈T 1 r r i=1 q τ (x i , x i ) .(Use the similar technique to the proof in inequality (8), the lower bound of n2 (G k ) ≥ G 2 n 2 ) ≤ inf α>0 4α + 12 √ K max k n 2 (G k ) log 1 2 (e 2 n 3 ) M α -1 d ≤12 √ K max k n 2 (G k ) + 12 √ K max k n 2 (G k ) log 1 2 (e 2 n 3 ) • log M 3 √ K max k n 2 (G k ) (Choose α = 3 √ K max k n 2 (G k )) =12 √ K max k n 2 (G k ) 1 + log 1 2 (e 2 n 3 ) • log M n 2 (G k ).Since k-means clustering-based 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 and Mendelson, 2002] , with Lemma 1, we haveH = F + L clu • G. Since nc (P(H)) ≤ nc (P(F)) + nc (P(L clu • G) [Bartlettˆ D (L • H) ≤ 12 √ 2ρ √ c nc (P(F)) + nc (P(L clu • G)) 1 + log 1 2 (8e 2 n 3 c 3 ) • log M √ n µB .According to Lemma 7, we have that the worst-case Rademacher complexity of the loss function space associated with P(G) can be bounded by the worst-case Rademacher complexity of the restriction of the function class along each coordinate P(G k ). Hence, for k-means clustering-based LSRL method, Lemma 7 involves the upper and lower bounds of nc 2 (P(G k )). We then obtain the lower bound of the worst-case Rademacher complexity nc 2 (P(G k )) by the Khintchine-Kahane inequality with p = 1:nc 2 (P(G k )) = sup [c]×D ∈[c]×X n 2 ˆ [c]×D (P(G k )) = sup [c]×D ∈[c]×X n 2 E   sup pj (g k (xi,x i+ n 2 ))∈P(G k ) 1 n 2 n 2 i=1 1 c c j=1 ij p j (g k (x i , x i+ n 2 ))   = sup [c]×D ∈[c]×X n 2 E   sup g j k ∈G j k 1 n 2 c n 2 i=1 c j=1 ij g j k (x i , x i+ n 2 )   = sup Z j k (xi,x i+ n 2 ) ≤1 E   sup V (xi,x i+ n 2 ) ≤4R 2 1 n 2 c n 2 i=1 c j=1 ij V (x i , x i+ n 2 )Z j k (x i , x i+ n 2 )   = sup Z j k (xi,x i+ n 2 ) ≤1 4R 2 n 2 c E n 2 i=1 c j=1 ij Z j k (x i , x i+ n 2 ) ≥ sup Z j k (xi,x i+ n 2 ) ≤1 4R 2 n 2 c 1 √ 2   n 2 i=1 c j=1 Z j k (x i , x i+ n 2 ) 2   1 2 . Since Z j k (x i , x i+ n 2 ) ≤ 1, we set sup Z j k (xi,x i+ n 2 ) ≤1 1 n 2 c n 2 i=1 c j=1 Z j k (x i , x i+ n 2 ) 2 1 2 = 1 √ n 2 c . So, nc 2 (P(G k ))) ≥ 4R 2 √ nc = G √ nc .Then, we replace the lower bound of n 2 (G k ) in the proof of Lemma 7 with the lower bound of nc 2 (P(G k ))), and we havenc (P(L clu • G)) ≤ 12 √ K max k nc 2 (P(G k ))) 1 + log 1 2 (e 2 n 3 c 3 ) • log M √ nc G .We then upper bound the worst-case Rademacher complexity nc 2 (P(G k )) as the following:nc 2 (P(G k )) = sup [c]×D ∈[c]×X n 2 ˆ [c]×D (P(G k )) = sup [c]×D ∈[c]×X n 2 E   sup pj (g k (xi,x i+ n 2 ))∈P(G k ) 1 n 2 n 2 i=1 1 c c j=1 ij p j (g k (x i , x i+ n 2 ))   = sup [c]×D ∈[c]×X n 2 E   sup g j k ∈G j k 1 n 2 c n 2 i=1 c j=1 ij g j k (x i , x i+ n 2 )   = sup Z j k (xi,x i+ n 2 ) ≤1 E   sup V (xi,x i+ n 2 ) ≤4R 2 1 n 2 c n 2 i=1 c j=1 ij V (x i , x i+ n 2 )Z j k (x i , x i+ n 2 )   = sup Z j k (xi,x i+ n 2 ) ≤1 4R 2 n 2 c E n 2 i=1 c j=1 ij Z j k (x i , x i+ n 2 ) ≤ sup Z j k (xi,x i+ n 2 ) ≤1 4R 2 n 2 c   E n 2 i=1 c j=1 ij Z j k (x i , x i+ n 2 ) 2   1 2 ≤ sup Z j k (xi,x i+ n 2 ) ≤1 4R 2 n 2 c   n 2 i=1 c j=1 Z j k (x i , x i+ n 2 ) 2   1 2 ≤ G n 2 c ≤ 2G √ nc .Hence, we havenc (P(L clu • G)) ≤ 24 √ KG √ nc 1 + log 1 2 (e 2 n 3 c 3 ) • log M √ nc G .Use the similar technique to the proof of the inequality above, the upper bound of nc (P(F))is 2κΛ √ KR √ nc , since φ j (x) = K k=1 (d(x, c j k )) 2 ≤ √ K max k x -c j k ≤ √ K max k ( x + c j k ) ≤ 2 √ KR.Finally, combining with the above inequalities and (5), we haveR(f ) ≤ R D (f ) + 3M log 2 δ 2n + 48 √ 2ρκΛ √ KR 1 + log 1 2 (8e 2 n 3 c 3 ) • log M √ n µB √ n + 24 2 √ 2ρ √ KG √ n 1 + log 1 2 (e 2 n 3 c 3 ) • log M √ nc G 1 + log 1 2 (8e 2 n 3 c 3 ) • log M √ n µB .First, we prove that the squared loss is 1 pseudo-Lipschitz of order 2.b (y j fj (x)) -b y j f j (x) = (y j -f j (x)) 2 -y j -f j (x) 2 = (y j -f j (x)) + y j -f j (x) • (y j -f j (x)) -y j -f j (x) ≤ |y j -f j (x)| + y j -f j (x) • (y j -f j (x)) -y j -f j (x) ≤ 1 + |y j -f j (x)| + y j -f j (x) • (y j -f j (x)) -y j -f j (x)According to the definition of the pseudo-Lipschitz function, the squared loss is 1 pseudo-Lipschitz of order 2. Then, we haveb (y j f j (x)) -b y j f j (x) ≤ 1 + |y j -f j (x)| + y j -f j (x) • (y j -f j (x)) -y j -f j (x) ≤ 1 + 2 |y j | + |f j (x)| + f j (x) f j (x) -f j (x) ≤(3 + 2B) f j (x) -f j (x) .Second, we prove that the surrogate Decomposable Loss is (3 + 2B)c-Lipschitz continuous with respect to the ∞ norm if the base loss b is the squared loss.D (f (x), y) -D f (x), y = c j=1 b (y j f j (x)) - c j=1 b y j f j (x) = c j=1 b (y j f j (x)) -b y j f j (x) ≤ c j=1 (3 + 2B) f j (x) -f j (x) ≤c(3 + 2B) max j∈[c] f j (x) -f j (x) =(3 + 2B)c f (x) -f (x) ∞ .Compared with the function class of LSRL where each label corresponds to a 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 of LLSF can be bounded by the complexity of the function class of LSRL where each label corresponds to a 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 to a Lasso.According to the definition, the function class of LSRL where each label corresponds to a Lasso means that in the class of LSRL defined by (1), the base loss b is the squared loss, the nonlinear mappings ζ(•) and φ(•) are both identity transformations for any j ∈ [c], and the constraint α(w) is w j 1 ≤ Λ for any j ∈ [c]. The proof process is similar to Lemma 1 and Theorem 1, but the upper bound of the worst-case Rademacher complexity nc (P(F)) here is different from Theorem 1. According to the above definitions, we have We denote N (j) as the index set of the one-hop neighbors of the j-th node, and denote g as the node degree, g max as the maximum node degree. Then, we bound Ã ∞ as followsEQUATION)Combining with Lemma 1, inequalities (12), ( 13), ( 14), and (5), then we haveR(f ) ≤ R D (f ) + 6 √ 2ρΛD 5 R 2 (g max + 1) 1 + log 1 2 (8e 2 n 3 c 3 ) • log M √ n ρB √ n + 3M log 2 δ 2n . 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
2. 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.
questions: 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?
2. Could the authors provide the key theoretical tools and intermediate steps involved in the  derivation steps of the vector-contraction inequality?
3. 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: 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.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
	
2）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.
questions: 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?

2) 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?
3) 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: limitations: See the above
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
2. 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.
3. While the theoretical advancements are significant, the paper does not provide guidance on implementing LSRL in real-world applications.
questions: questions: 1. How can the theoretical bounds proposed in the study be translated into practical enhancements in real-world multi-label learning tasks?
2. 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: limitations: NA
paper_summary: paper_summary: This paper proposes a new vector contraction inequality and derives a tighter label-specific representation learning (LSRL) generalization bound based on it.
This 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.
strength_weakness: strength_weakness: 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).
questions: 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: limitations: Yes.

Comments: title: Kind Reminder to Reviewer Axy4
comment: Thank you again for your support.
Thank you for the author's detailed response. My issue has been resolved, and I will keep my score.
Dear reviewer,

Thank you for your insightful feedback and constructive comments! We have answered and explained your questions in the rebuttal (along with the global rebuttal). We are eager to hear back from you if you have any feedback or further questions, and we would love to know your updated reviews.

Regards,

Authors