Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper provides theoretical studies on the ranking loss in multi-label learning. For ranking loss, usually, two surrogate losses are used: pairwise and univariate. The paper is motivated by the fact that the pairwise surrogate loss is theoretically unfavored but empirically well performed. To study the surrogate losses, the paper analyzed the original loss function and some proposed reweighting of the loss function by both consistency and generalization analysis. The generalization analysis is conducted by analyzing the upper-bound relationship between different loss functions and the corresponding risks. This analysis shows that the instance-wise class imbalance affects the relationship between these surrogate losses. The paper further analyzed the generalization performance for two extreme cases: extremely imbalanced (all predictions are zero or one for one instance) and absolutely balanced (exact half of the predictions are one for an instance). The paper further analyzed the consistency of these surrogate loss functions and gave some experimental results.
main_review: This paper is a theoretical study, analyzing commonly used surrogate losses for ranking loss in multi-label learning. The paper is motivated by the gap between existing theory and practice for the commonly used pairwise surrogate loss and univariate surrogate loss. I think this direction is novel and worth study. It can contribute to multi-label learning in both theoretical and practical aspects. 

The paper proposes two reweighted versions of the univariate losses and analyzed the relationship between these surrogate loss functions, and the generalization error of the algorithms optimizing these loss functions. The most interesting part of the study is it tries to discuss the relationship between the “balance” per instance and the choice of surrogate loss functions. This part provides the most informative insight of the study: pairwise surrogate loss is favoured if data are imbalanced at the instance level. However, the study is based on two extreme cases of imbalance, and there is no study on the in-between cases, or analyze how the surrogate loss’s performance is impacted by a continuous changing imbalance level. 

Generally, the paper is clearly written and easy to follow. Especially it gives a thorough intuitive explanation and insights drawn after each formal theoretical result. This may enlarge the impact of the paper to more general readers due to the efficient delivery of its idea.

After rebuttal:
I appreciate the authors' rebuttal in addressing one special case of imbalanced learning out of the two extreme cases in the paper. I keep my positive rate for this paper. 

limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies theoretical analysis such as generalization error and consistency of the pairwise and univariate (i.e., pointwise) loss functions for multi-label classification. The main contributions are two folds: (1) propose two reweighted convex surrogate pointwise losses (2) consider the number of labels and the label imbalance into the theoretical analysis.
main_review: In general, the theoretical analysis of generalization error bound and consistency seems technically sound. The writing is clear and the presentation is comfortable to follow. I outline some detailed questions or comments below.

Q1: The assumption of class imbalance in Definition 1 seems too strict. In practice, for large-scale multi-label classification datasets, we often see the number of labels following a long tail distribution and the number of labels per instance is in the order of log(L), where L is the number of labels. Are you able to extend the theoretical analysis for such a case?

Q2: Following Q1, when L is in an extreme scale, such as millions or more, the O(L) computation time complexity for loss functions is prohibitive, and practitioners often resort to various negative sampling methods. While this is not the main focus of this work, perhaps it would be more informative to readers by adding one paragraph regarding this aspect.

Q3: This manuscript would be more strong If there’s some simulated studies that verify the complexity rate of the generalization error as stated in Table 1. For example, we can simulate the imbalance label distribution from some P(x,y), and learn the OVA classifiers with L_{pa}, L_{u_k}, k=1,..,4 and compare their generalization error when the number of class L grows.

limitations_and_societal_impact: No negative social impact.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper analyzes theoretically the consistency and the generalization error of multilabel ranking algorithms. More specifically, some generalization error bounds are obtained for different loss functions, that are surrogates of the ranking loss or the partial ranking loss. 

The analysis is restricted to two extreme cases: (1) instance-wise class balanced distribution (when the number of positive and negative classes is the same for all samples), and (2) extremely imbalanced distribution (when only one class is positive or only one class is negative, for all samples).  It turns out that, while the generalization error bounds for the balanced case are independent on the number of classes, $c$, the  bounds for the imbalanced case are $O(c)$ for some univariate losses (like $L_{u_2}$)  while it is $O(\sqrt{c})$ for pairwise losses (like $L_{pa}$). 

Since, in practice, real datasets are highly imbalanced, the theoretical results might explain why $L_{pa}$ shows a better performance than $L_{pa}$ in the experiments with finite datasets, even thought only the latter is consistent.

Based on these findings, the paper proposes some re-weighting versions of the univariate losses with $O(\sqrt{c})$ generalization bounds. The consistency is lost, but some of the reweighting version of $L_{u_2}$ (in particular, $L_{u_3}$) outperform $L_{u_2}$  in the experiments.

main_review: The main contribution of this paper is theoretical. The paper shows some generalization error bounds that can provide a better understanding of multi-label ranking (MLR) algorithms. In particular, the paper highlights the relevance of the class imbalance as a key factor in the behavior of MLR algorithms.

Up to my knowledge, the contribution of the paper is original. Sec. 5 provides some related work. In particular, the reweighting scheme in Eq. (9) was proposed before with base hinge loss, though it is analyzed here in a more general context.

The experimental results are aimed to corroborate the theoretical results, and, in particular, to verify the influence of the re-weighting scheme on the classification performance. Although the value of the experimental work is limited for a practitioner, the paper may suggest that, using a re-weighting scheme for univariate losses is advisable for datasets with large $c$ and class imbalance.

I have checked only about 30% of the proofs, but they are technically correct, under my view.

Summarizing, the paper may have a small expected impact on real applications, but the theoretical contribution is valuable.

limitations_and_societal_impact: The authors and the reviewer are not aware of potential negative societal impacts.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper attempts to fill the gap between existing theory and practice for Multi-Label Ranking (MLR) problems: why inconsistent pairwise losses often achieve better performance in practice than consistent univariate losses? The authors try to answer this question from the prospective of generalization error bounds, besides the consistency.  Two factors of the distribution (from which the data is drawn) are identified that affect the learning guarantee. Motivated by the observation, the authors propose two new surrogate losses, one of which not only enjoys nearly the similar performance as the popular pairwise surrogate loss, but is also computationally more efficient. The results are well-supported with theoretical results and empirical studies.

Overall I think the paper is clear and well executed.
main_review: Thanks for this interesting and well-written paper. Below are comments for each dimension.

Originality.
This paper tries to rigorously study this question in MLR: why inconsistent pairwise losses often achieve better performance in practice than consistent univariate losses? The authors answer the question from the angle of generalization error bounds and consistency analyses. Overall this work is original, though the techniques are standard. Although the relevant papers are cited, the related work section (Section 5) is somewhat inadequate. It would be better if the authors can explain more how this paper is related to the papers discussed in Section 5.

Quality.
The method and the claims are overall correct, though I did not verify the proofs line by line. The empirical study is valid and supports the theoretical claims. The authors are honest about the weakness of their work (e.g. they make it clear that the proposed algorithms are not consistent). My only concern is about comparing upper bounds for the generalization errors (see comment below).

Clarity.
The paper is well-written and well-organized. 

Significance.
This paper attempts to solve an interesting, important and practical problem in MLR from the theoretical prospective: why some inconsistent algorithms can often outperform consistent algorithms on real data sets. The question itself is important and valuable to the multi-label community. The study in this paper can potentially inspire new algorithms that not only can perform well in practice, but also enjoy some theoretical guarantees. However, I find that the main technique used (comparing upper bounds for the generalization error) is somewhat limited and may not generalize easily to other settings (e.g. distributions other than extremely imbalanced and balanced).

---

Extra comments:

My concern is how well the upper bound for the generalization error can reflect on the true generalization error. I know that it might be difficult (or even impossible) to directly compare generalization errors of different algorithms, so I can see why the authors choose to compare the upper bounds, and I agree this is a valid approach because a tighter upper bound usually suggests better performance. I have read the improvements the authors made since the ICML 2021 submission, and I can see that the authors have added more discussions about the upper bounds to provide more insights and justifications. I still think it might be better if the authors could show some synthetic experiments justifying the use of upper bounds. The advantage of synthetic experiments is that the generalization error can be calculated, so that one can see if the upper bound for the generalization error can reflect on the true generalization error reasonably well.

---

Typo:

Page 9, line 343: "two extremely cases" -> "two extreme cases"

---

After rebuttal: Thank the authors for providing additional results. I keep my rating for this paper.


limitations_and_societal_impact: Yes.
review_title: null

Meta-review: The reviewers and I agree that this paper offers several valuable insights, both theoretically and empirically, into a class of methods for multi-label classification. I also agree with a reviewer that error bounds are not necessarily the best proxies for the actual error, and that the authors should include additional content on this point, e.g., through simulation studies as suggested by the reviewer, in the final version.
Decision: Accept (Poster)