Tight and Fast Bounds for Multi-Label Learning

Thank you for your constructive comments and active interest in helping us improve the quality of the paper.

The following are our responses to the Questions:

1. Response to Weakness.

We will add concrete examples of multi-label methods after the definition of the function class to improve readability and practical interpretation. For example, the DNN-based multi-label method named CLIF [1], which proposes to learn label semantics and representations with specific discriminative properties for each class label in a collaborative way, can be expressed in our function class as:

$$\phi_j(\boldsymbol{x})= \sigma_{ReLU} \\{ W_5 \cdot \left[ \sigma_{ReLU} (W_4 \boldsymbol{x}) \odot \sigma_{sig} (W_3 \psi(Y)_j) \right] \\} .$$

The label embeddings $\psi(Y)$ can be denoted by $\sigma_{ReLU}(\tilde{A} \sigma_{ReLU} (\tilde{A} Y W_1) W_2)$, where $\tilde{A}$ denote the normalized adjacency matrix with self-connections, $Y$ is the node feature matrix of the label graph, $\sigma_{ReLU}$ is the ReLU activation, $\sigma_{sig}$ is the sigmoid activation, $\odot$ is the Hadamard product, $W_i$ are the parameter metrices, $i \in [5]$.

In addition, a class of multi-label methods based on the strategy of label-specific representation, which facilitates the discrimination of each class label by tailoring its own representations, can be formalized in our function class. For example, the wrapped label-specific representation method [2], which presents a kernelized Lasso-based framework with the constraint of pairwise label correlations for each class label, can be expressed in our function class, where $f_j$ is the kernelized linear model and the constraint $\alpha(\boldsymbol{w})$ is $\|\boldsymbol{w}_j\|_1 \leq \Lambda$ for any $j \in [c]$, and each label also has the property of sharing which is reflected by the additionally introduced constraint

$\sum_i^c (1- s_{ji}) {\boldsymbol{w}_j}^\top \boldsymbol{w}_i \leq \tau$,

where $s_{ji}$ is the cosine similarity between labels $y_j$ and $y_i$.

Besides, the function class here is applicable to the typical Binary Relevance methods for multi-label learning, where different methods correspond to different nonlinear mappings $\phi_j$.

[1] Collaborative Learning of Label Semantics and Deep Label-Specific Features for Multi-Label Classification, TPAMI 2022.

[2] Multi-Label Classification with Label-Specific Feature Generation: A Wrapped Approach, TPAMI 2022.

In addition, we will also provide additional explanations on the key ideas in the theoretical proof to help readers better understand the ideas. Please refer to our Response 3 to Reviewer XSTz.

2. Response to Q1.

Our theoretical results require that the base loss is bounded, and therefore cannot cover the case where the base loss is cross-entropy loss. In the future, we will further study the bounds with a faster convergence rate for unbounded and Lipschitz base losses. In addition, for some methods involving specific label correlations, when using our theoretical results to analyze these specific methods, it is necessary to introduce additional assumptions induced by these specific label correlations in the generalization analysis, so as to better reveal the impact of these setting-related factors on the bound. However, how to explicitly introduce label correlations in generalization analysis is still a crucial open problem. We will further explore related work in the future. We will incorporate these discussions into the paper in an appropriate manner.

3. Response to Q2.

As the reviewer suggested, a better presentation of related work and comparisons between them through a summary table can improve the readability of the paper and make the contribution of our results clearer. We will add a summary table in the revised version from the perspectives of loss function, additional assumption, order of bounds, and reference.

Thank you for your constructive comments and active interest in helping us improve the quality of the paper.

The following are our responses to the Questions:

1. Response to Weakness 1.

As the reviewer pointed out, when there is some type of label correlation between the labels of the dataset, the label distribution may satisfy some potential constraints, which may correspond to some additional assumptions such as sparsity assumptions or norm regularization constraints. Therefore, when dealing with these specific problems, we need to introduce some additional assumptions to adjust our analysis and explicitly introduce these potential label correlations into the generalization analysis. This is still an open problem and we will further explore related work in the future.

2. Response to Weakness 2.

When dealing with large-scale datasets, in practice, one often consider introducing specific strategies in the label space to deal with extremely large number of labels. In generalization analysis, it is shown that introducing effective and general specific strategies is not only an important open problem in theory, but also extremely challenging in practice. Therefore, it is indeed necessary to further introduce effective assumptions to better explicitly analyze the role of key factors in generalization that can effectively deal with challenging problems with large number of labels and large-scale datasets.

3. Response to Suggestions.

In line 313, the subscript $S$ in the inequality should be changed to $R$.

In line 1026 to 1030, this is a repeated typo and we will remove one of them.

4. Response to Q1.

As we replied above, effective analysis for more specific problems requires further explicit introduction of valid assumptions to reveal the impact of these setting-dependent factors on the bound. For example, for high-dimensional sparse data, one may need to introduce sparsity assumptions into the analysis, thereby inducing bounds that are weakly dependent on the sparsity rate and the number of key labels.

5. Response to Q2.

Different types of label correlations have an important impact on generalization analysis. How to explicitly introduce them in generalization analysis is a crucial open problem. Traditional Lipschitz methods do have more advantages since they are easier to satisfy the conditions. For example, for deep models, the smoothness of base losses also involves the boundedness of the second-order derivative of the function, which is often difficult to guarantee in deep models, while Lipschitz continuity is often established. Experimental verification can be considered from two aspects. On the one hand, verify whether the functions selected by the algorithm have a small error and whether the generalization performance of the small error functions is better. On the other hand, verify whether the smoothness of the model function can be guaranteed by some regularization, and explore which regularization-induced inductive biases are more effective for generalization in practice, and promote further theoretical research.

We will incorporate these discussions into the paper in an appropriate manner.

Thank you for your constructive comments and active interest in helping us improve the quality of the paper.

The following are our responses to the Questions:

1. Response to Weakness 1.

As the reviewer commented, the theoretical results for unbounded base losses need to be further explored in the future to develop new theoretical techniques to cover this situation. Under the new theoretical analysis method, although the smoothness of the cross-entropy loss may be difficult to hold for models with large capacity, the Lipschitz continuity of the cross-entropy is often established, i.e., tight bounds with no dependency on $c$ for cross-entropy loss can be obtained. However, improving the convergence rate of its bound with respect to $n$ is still an urgent open problem to be solved. In the future, we will further study the bounds with a faster convergence rate for unbounded and Lipschitz base losses.

2. Response to Weakness 2.

Since the $\widetilde{O}(\frac{1}{\sqrt{n}} )$ and $\widetilde{O}(\frac{1}{n} )$ bounds in our theoretical results is independent of the number of labels, up to logarithmic terms, the dependency of the bounds here on $c$ is logarithmic. We use $\widetilde{O}$ to omit the logarithmic terms since the logarithmic dependency is very weak. However, there is no contradiction between the theoretical results and empirical intuition. The increase in $c$ will affect the difficulty of learning, but the empirical success of multi-label methods suggests that the increase in $c$ have limited impact on the difficulty of learning, which means that the ideal bound should not be strongly dependent on $c$.

3. Response to Question 1.

If there are real numbers $s_1, \ldots, s_p$ such that for each $\delta_1, \ldots, \delta_p \in \\{-1, +1\\}$ there exists $f \in \mathcal{F}$ with

$$\delta_i\left(f(\boldsymbol{x}_{i})-s_i\right) \geq \epsilon, \quad \forall i = 1, \ldots, p.$$

We say that $s_1, \ldots, s_p$ witness the shattering.

4. Response to Question 2.

The multiplicative factor of 2 comes from the use of Lemma A.8, which can also be understood through its proof process. The result can often be shown through some derivation as follows:

$$R(f) \leq \widehat{R}_{D}(f) + \widetilde{O}(1/n + \sqrt{R^* / n} ) ,$$

where $R^* = \inf_{f\in \mathcal{F}} R(f)$. This means that in the separable case ($R^* =0$), the bound can be improved to a $\widetilde{O}(1/n)$ rate. The multiplicative factors often appear in bounds based on local Rademacher complexity, as also shown in literature [1-3], etc.

[1] Local Rademacher Complexity-based Learning Guarantees for Multi-Task Learning, JMLR 2018.

[2] Towards Sharper Generalization Bounds for Structured Prediction, NeurIPS 2021.

[3] Generalization Analysis for Ranking Using Integral Operator, AAAI 2017.

Thank you for your constructive comments and active interest in helping us improve the quality of the paper.

The following are our responses to the Questions:

1. Response to the Question in Claims And Evidence.

Here we mention that the bounds with a square-root dependency on $c$ in literature [1] mainly refers to the results for $\ell_2$ Lipschitz loss in literature [1], i.e., Lemma 3.6 and Theorem 3.7. Our improvement is mainly relative to Theorem 3.7. In the proof of Lemma 3.6, the $n$ in equation (9) should be changed to $nc$. This is a typo. In fact, the results in Lemma 3.6 and Theorem 3.7 require the introduction of an additional $\sqrt{c}$ factor, because they ignore the $\sqrt{c}$ factor in the radius of the empirical $\ell_2$ cover of $\mathcal{P}(\mathcal{F})$. Therefore, a $\sqrt{c}$ factor is missing in Lemma 3.6 and Theorem 3.7, and literature [1] improved the dependency of the bounds on $c$ from linear to square-root in the decoupling case for $\ell_2$ norm Lipschitz losses. Although for $\ell_2$ Lipschitz loss, the bounds in literature [1] is only improved by a factor of $\sqrt{c}$, they are still the tightest results in multi-label learning with $\ell_2$ Lipschitz loss. In addition, for Hamming loss, its Lipschitz constant can induce the tight bounds with no dependency on $c$. We found that the square-root dependency of the bound in [1] on $c$ is inevitable for $\ell_2$ Lipschitz loss, which essentially comes from the $\sqrt{c}$ factor in the radius of the empirical $\ell_2$ cover of the projection function class. We also found that the smoothness of the base loss function can eliminate the $\sqrt{c}$ factor in the radius of the empirical $\ell_2$ cover of the projection function class, so that the tight bounds with no dependency on $c$, up to logarithmic terms, can be derived.

[1] Yi-Fan Zhang, Min-Ling Zhang. "Generalization Analysis for Multi-Label Learning", ICML 2024.

2. Response to the Essential Reference.

The literature [2] derived tight bounds with a logarithmic dependency on $c$ for Hamming loss with KNN under the smoothness assumption of the regression function and multi-label margin and sparsity assumptions and also derived tight bounds with a logarithmic dependency on $c$ for Precision@$\kappa$ under the margin condition and the smoothness assumption. The margin condition ensures that the obtained bounds with a faster convergence rate. In our work, the local loss function space is the key to obtaining bounds with a faster convergence rate. The smoothness condition with respect to the $\ell_\infty$ norm in literature [2] is a variant of Holder-continuity. We also find that the $\ell_\infty$ norm has a positive effect on obtaining tight bound with a weaker dependency on $c$, i.e., tight bounds with a logarithmic dependency on $c$ can be derived for $\ell_\infty$ Lipschitz losses. However, how to improve the convergence rate of the bounds for Lipschitz losses is still an open problem, which we will further explore in future work. We will incorporate these discussions into the paper in an appropriate manner.

[2] Regret Bounds for Multilabel Classification in Sparse Label Regimes. NeurIPS 2022.

3. Response to the Suggestion.

In order to avoid the possibility of truncation in understanding, we will adjust Definition 3.2 to $\ell_p$ norm covering number instead of listing the $\ell_2$ norm and $\ell_\infty$ norm covering number separately in the definition.

Thank you for your constructive comments and active interest in helping us improve the quality of the paper.

1. Response to C1

We add concrete examples of multi-label learning (MLL) methods after the function class definition to improve readability and practical interpretation, please refer to Response 1 to Reviewer Wn57 due to character limitation.

2. Response to C2

For the case where base loss is cross-entropy loss, our theoretical results do not cover cross-entropy, mainly because cross-entropy loss is not bounded. Next we will further discuss the smoothness of cross-entropy. When the model is a linear classifier, smoothness of cross-entropy can be achieved by the boundedness of input, but from the perspective of model capacity, such a result is not general. The function class here involves general functions (i.e., nonlinear mappings $\phi_j$), so for nonlinear models, smoothness of cross-entropy involves not only boundedness of the gradient of model function but also boundedness of second-order derivative. For deep networks, changes in parameters may cause drastic changes in second-order derivative, resulting in the norm of second-order derivative being unbounded. Hence, smoothness of cross-entropy is often difficult to hold. However, the Lipschitz continuity of cross-entropy is often established, and the boundedness of gradient of model function is guaranteed by various strategies in practice, e.g., input normalization, weight initialization, gradient clipping, and regularization. This implies the need to develop new theories and analytical methods for unbounded base losses. Under the new theoretical analysis method, tight bounds with no dependency on $c$ for cross-entropy loss can be obtained using its Lipschitz continuity, but improving the convergence rate of its bound wrt $n$ is still an urgent open problem to be solved. In the future, we will further study bounds with a faster convergence rate for unbounded Lipschitz base losses.

3. Response to C3

Since the output of MLL is a vector-valued function, we need to convert Rademacher complexity of the vector-valued class into complexity of a tractable scalar-valued class. For $\ell_2$ Lipschitz losses, the analysis of MLL can be traced back to a basic bound with a linear dependency on $c$ that comes from a typical inequality:

$\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]$

$\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].$

The dependency of bounds on $c$ can be improved to square-root. Such improvements essentially come from preserving the coupling among different components reflected by constraint $\\|\boldsymbol{w}\\| \leq \Lambda$.

As a comparison, when $\\|\boldsymbol{w}_j\\|_2 \leq \Lambda$ for any $j \in [c]$,

if we consider group norm $\\|\cdot \\|_{2, 2}$,

we have $\\|\boldsymbol{w}\\|_{2, 2} \leq \sqrt{c}\Lambda$, which means that these improved bounds still suffer from a linear dependency on $c$. [1] improved the dependency of bounds on $c$ from linear to square-root in decoupling case for $\ell_2$ Lipschitz losses. We found that square-root dependency of bound in [1] on $c$ is inevitable for $\ell_2$ Lipschitz losses, which essentially comes from a $\sqrt{c}$ factor in the radius of empirical $\ell_2$ cover of projection function class. We also found that smoothness of base loss can eliminate the $\sqrt{c}$ factor, so that tight bound with no dependency on $c$, up to logarithmic terms, can be derived. In addition, according to the above core ideas, we combine smoothness of base loss with local loss space to develop novel local vector-contraction inequalities, thereby obtaining sharper bounds with a weak dependency on $c$ and a faster convergence rate wrt $n$. We have also explained proof processes, ideas and specific theoretical techniques in proof sketches, which mainly includes conversions between complexities of different classes and some lemmas required to achieve these conversions.

[1] Generalization Analysis for Multi-Label Learning, ICML 2024.

4. Response to C4

We explain the multiplicative factor of 2, please refer to Response 4 to Reviewer ZadH.

5. Response to Literature

We give a detailed discussion of the paper pointed out, please refer to Response 2 to Reviewer dgGN.

We will incorporate these discussions into the paper in an appropriate manner.

6. Response to Weakness

We will carefully check and revise the notation to ensure consistency, e.g., the definition of base losses $\ell_b$. $\widetilde{\Re}_{nc}(\mathcal{P}(\mathcal{F}))$ is worst-case Rademacher complexity of projection function class. We define worst-case Rademacher complexity in Definition 3.1,

$\widetilde{\Re}_{nc}$ is the analog of the definition of worst-case Rademacher complexity for class $\mathcal{P}(\mathcal{F})$.