Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The paper provides regret bounds for large-scale multilabel classification with Hamming loss and precision-at-k, for both nonparametric (k-nn) and parametric estimation. Efficient scaling of the bounds is achieved by making a sparsity assumption on the labels, which combines a hard sparsity constraint (at most s labels with high probability) with a soft sparsity constraint (all other labels at most probability t < 0.5). 
strengths_and_weaknesses: The paper provides a step in closing the gap in theory between binary classification and large-scale multilabel classification. The authors manage to incorporate the sparsity property in a way that does not require an unrealistically strict sparsity assumption (i.e. at most s labels, ever). The multilabel-generalization of the Tsybakov-condtition also seems sensible to me, but I doubt that the k-vs-k+1 separation condition needed for the precision-at-k result is realistic.

For the most part, I found it easy enough to follow the writing in the paper. In the regret bounds, the formulas get quite long, so they can become a bit difficult to parse, but I'm not sure if there is anything the authors could have done to improve this.
questions: I'm not convinced that 5.6 is a realistic condition to impose. The number of relevant labels typically varies per data-point, so it seems very strict to demand that the marginals have a steep change exactly between k and k+1 for most of instances. Do you have an argument why this condition would be fulfilled in real data?

l. 235 announces the introduction of two reductions, but the second does not seem to do so.

Assumption 5.1.
should this really be a seminorm, and not an actual norm? A seminorm could just ignore a few of the components (=marginals of labels), so that in these labels there would not need to be any smoothness? Is that deliberate? A norm would also have the nice effect that you need not worry about which norm to use, since this is finite dimensional and any factor could be absorbed by C.

== Supplementary ==
Unfortunately, I have not yet had the time to go through the proofs in the supplementary. When I'm done with that, I will update the review accordingly.
limitations: the main limitation I see is assumption 5.6, which I doubt is realistic.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper focus on the regret bounds for multi-label classification. Under a novel low noise assumption and a sparsity constraint on the posterior possibility $\eta(x)$, the regret upper bounds are provided for surrogate risk minimization w.r.t. Hamming loss and Precision@k. With the sample assumptions and a widely used constraint on smoothness, the high probability bounds are given for a MLC variant of KNN. Regret lower bounds are also provided for KNN to show the tightness of its upper bounds. The given results show that the interplay between low noise assumption and label sparsity can lead to non-trivial improvement on the regret bounds.

strengths_and_weaknesses: Strengths:
1. The assumptions made in this paper are mild and are closely related to the widely accepted ones. 

2. The analyses on the MLC variant of KNN are detailed and novel. To the best of my knowledge, there is no work that contributes to the regret bound analysis  of KNN in the regime of MLC. 

Weaknesses:

Though the analyses of the MLC variant of KNN are rigorous, the analyzed variant may not be a widely accepted one, which can cause the gap between practice and theory.
questions: Since $\nu\geq 1$ usually holds, I'm not sure if (5) is better than a common regret bound of $O_p(1/\sqrt{n})$ that is induced without dependence on the low noise and sparsity assumptions.
limitations: The authors addressed the limitations of the used assumptions and the absence of regret lower bounds for surrogate risk minimization.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This works studies multi-label classification (MLC) problems. Focusing on sparse label regime (in which the number of active labels is small) and an MLC variant of Tsybakov's low-noise condition,  the paper shows upper and lower regret for two typical performance measures in MLC, namely Hamming Loss and Precision@k, in two settings: non-parametric tackled by K-NN classifiers, and empirical risk minimization (ERM) of surrogate loss functions. It is clearly demonstrated in the paper that sparse label regime and low-noise condition, which are two reasonable conditions for practical considerations as well, can improve the regret bounds.
strengths_and_weaknesses: Overall this paper is a very strong piece of theoretical work. It is also well-polished. I really enjoyed reading it. Good work!

**Originality:**
This work is novel. The related work is adequately cited and discussed.

**Quality:**
The work is sound and rigorous. 

**Clarity:**
The paper is well-polished. The notations are used consistently. Insights are provided to help readers understand the crux of the theoretical results.

**Significance:**
The paper is an important piece of work in advancing the theoretical guarantees in MLC community. Moreover, it is well-presented, so it could have even more influence.

---
After rebuttal: I have read the other reviews and the authors' responses. My rating for this paper has not changed.
questions: In the conclusion section, you said that the analysis can be extended to rank loss, 0/1 loss, and micro/macro F-measures. I don't see how this extension can come easily. As far as I understand, for Hamming Loss and Precision@k, in order to derive Bayes optimal classifiers, it is indeed sufficient to have good estimates of $\eta_j(x)$ for each label $j$. In some sense, the labels are independent of each other. For other complex performance measures, the relations among different labels are crucial in designing Bayes optimal classifiers. Therefore I don't see how the analysis can be extended easily. Can you elaborate on this point?
limitations: One limitation is that the paper does not have experiments. It would be nice to see some empirical verifications of the results on synthetic and real data sets.
review_title: null

Meta-review: metareview: This paper studies regret bounds for multi-label classification and derives new upper bounds for surrogate risk minimization under a low-noise assumption. Although there is some concern regarding the conditions, all reviewers support accepting this paper.
confidence: Certain
Decision: Accept