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: This paper tackles the missing label problem in the Extreme Classification setting. In particular -
1) It provides unbiased estimation of all kind of losses (decomposable or non decomposable over labels) under the missing label setting. Previous papers mostly focused on decomposable losses.
2) Shows that if propensities are low then these losses can have very high variance and may lead to ill-posed optimization problems.
3) Proposes to use convex upper bounds of these losses which significantly reduces the variance at cost of slight increase in bias.
 
strengths_and_weaknesses: Originality: While the issue of high variance with inverse propensity models has been explored previously such as in [1], this paper studies it in the extreme classification setting where it hasn't been explored much. 

Quality: In terms of experimental results I feel like the paper is a bit weak. It would have been good to see some comparison of the proposed technique with other popular variance reduction methods such as one proposed in [1]


[1] Swaminathan, Adith, and Thorsten Joachims. "Counterfactual risk minimization: Learning from logged bandit feedback." International Conference on Machine Learning. PMLR, 2015
questions: It would have been nice to see if the proposed convex upper bound framework actually improves the performance on standard tasks/datasets. I believe for a lot of public datasets the propensity scores have been provided [1] so it should be pretty simple to try them out and compare against methods which do not take variance reduction into account.

[1] The Extreme Classification Repository: Multi-label Datasets & Code: http://manikvarma.org/downloads/XC/XMLRepository.html
limitations: Yes
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: In this paper, the authors address the problem of unbiased estimates for multi-label reductions of extreme classification with missing labels. Specifically, the unbiased estimates for four cases of multi-label reductions are discussed. The authors first show the unbiased estimates for general multi-label losses capable for pick-all-labels and normalized reductions, and then prove the upper-bounds for two reductions, which trade-off bias and variance. The empirical experiments demonstrate the influence of missing labels, as well as unbiased estimates. The results also indicate that although unbiased loss functions work well with sufficient training data, normalized reductions can still be starving. Besides, the authors also show that generic multi-label losses with achievable unbiasedness could not be suitable for optimization while the presented trade-off method works well for handling training with fewer data.
strengths_and_weaknesses: Strengths
* Comprehensive coverage on different types and cases reductions.
* Theorems and proofs for both unbiased estimates and convex upper-bounds.
* Empirical studies and practical conclusions that emphasize the contributions

Weaknesses
* Lack of discussions on the relations to tree-based XMC methods, which are one of the most popular conventional methods for tackling XMC problems.
* Lack of discussions of different types of noises.
questions: * Most of the existing state-of-the-art methods for XMC problems are tree-based methods. In each layer, not all of the labels will participate in optimization and loss calculations. Moreover, the predictions and inference also usually are based on beam search. I wonder if the conclusions and guidelines can be also applied to those methods.

* The authors model missing-label setting by treating them as independent noises, but real-world noises can be more complicated with many different distributions and correlations among labels. I wonder if the methods can be further extended to more different types of noises (or distributions of missing labels).
limitations: The authors did not address any limitations and potential negative societal impact.
review_title: null

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: This paper discusses the problem of  missing labels in extreme multi-label classification (XMC). First a framework for defining the loss function is defined, which can be applied to various one-vs-all (OVA) and pick-all-labels reduction methods. Next, unbiased estimators for the loss functions based on propensity  are discussed, and it is shown that such estimators have high variance. Next, convex upper-bounds for the loss functions are discussed, in order to obtain efficient solvers. Numerical results on two datasets are presented to illustrate the various aspects of missing labels in XMC problems.

strengths_and_weaknesses: The strengths of the paper  are:
1. An important problem in XMC, that of missing labels is discussed.
2. Unbiased loss functions and their convex upper bounds are discussed.
3. The framework is general and addressed a range of XMC methods that can be written as OvA or PAL.

The weaknesses of the paper  are:
1. Significance of the results are not clear.
2. Numerical results seem limited.
3. Scalability issues are not addressed.
questions: Missing labels is an important problem in XMC literature. The paper might be presenting an interesting framework for solving XMC problems with missing labels. 
However, the current version of the paper has the following shortcomings:  

1. Significance: Unbiased loss functions for XMC with missing labels have been proposed before, see [1],[2]. It is not clear how the proposed estimators in this paper differ from the existing ones and what are the significance of the proposed estimators. Also, certain aspects are  not clear, eg., why the upper bounds would have reduced variance and how the bias looks like in these cases.

2. Numerical results: The experiment results seem limited. Only two datasets are considered. Many aspects of the framework are not studied, e.g., whether the considers loss functions solve the original XMC problem efficiently, what type of XMC algorithms perform best (OvA or PAL), also, comparison to [1],[2] would be helpful to better understand the advantages of the popped framework. 

3. Scalibity: Since in XMC set up, the number of instances and labels can be very large (in millions), it is not clear if OvA or PAL is scalable. There are many other reduction methods (label reduction or tree based methods) that are scalable. So, it is not clear if studying OvA type methods is useful in XMC settings.


4. Minor comment:
i. In Theorem 2, under the conditions of Theorem 2 --> under the conditions of Proposition 2?


References:

[1] Schultheis, Erik, and Rohit Babbar. "Unbiased Loss Functions for Multilabel Classification with Missing Labels." arXiv preprint arXiv:2109.11282 (2021).

[2] Schultheis, Erik, et al. "Unbiased Loss Functions for Extreme Classification With Missing Labels." arXiv preprint arXiv:2007.00237 (2020).

limitations: Yes, the paper addresses these.
review_title: null

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 studies the problem of extreme multi-label learning with missing labels. To solve the problem, the paper considers reducing the multi-label problem into a serious binary or multi-class problems. To deal with missing labels, the paper proposes unbiased estimates for multi-label reduction loss functions. To reduce the variance of estimates, the paper proposes convex upper-bound for the OVA and PAL-reduction.
strengths_and_weaknesses: Strength

1.The paper proposes a framework for dealing with missing labels in extreme multi-label setting. In the proposed framework, the unbiased estimates in terms of decomposable reduction and non-decomposable losses under missing-label setting are derived.

2.To deal with issue of increased variance, the paper proposes convex upper bounds for normalized PAL reduction, which provides trade-off between bias and variance.

Weakness

1.The experiments are weak. The paper only conducts a toy experiment and an experiment on a real-world dataset. Furthermore, the proposed method does not compare with other counterpart methods. The experimental results on the current submission are insufficient to validate the effectiveness of the proposed method.

2.The paper is not well written. Many important details are missed or placed on the appendix, which make the paper hard to understand. For example, Eq.(4) is difficult to understand without any detailed introduction (in appendix). This makes this paper become difficult to follow. The organization of this paper should be improved. For example, the figures in experiments are too large with limited information.

3.The paper fails to sufficiently discuss its pioneering works. Many related works are missed. For example, authors do not discuss the relevant works in extreme multi-label classification that are very relevant to this work. The very relevant works about multi-label noise are also missed.

questions: In experiments, why use BCE for OVA reduction and CCE for PAL reduction? 

In Related Work, authors claim that “learning with missing labels is a specific” instance of learning with class-conditional noise. Why? Is it there any reference?
limitations: The experiments are weak due to the lack of comparison with counterpart methods. The results on real-world scenarios are also insufficient.
review_title: null

Meta-review: metareview: This is a borderline paper. The reviewers lean towards acceptance but do have reservation about the paper. I have also read the paper in order to make an informed recommendation. In the end I've decided to recommend against acceptance at this point for the reasons I'll describe below. I do understand, and sympathize with the authors' frustration at my decision, but I truly believe that the paper can be significantly improved with some additional work.

The authors tackle an interesting and important problem in the area of extreme classification (and multi-label classification in general): the problem of missing labels due to various biases in how the data is annotated. This is a well recognized and important problem both in the extreme classification literature, and also in the benchmark creation literature, especially for computer vision tasks. (I recommend the authors look at the work on Imagenet 2.0 and similar papers where due to the shortcoming of the annotation protocol relevant labels are missing).  The paper makes an interesting theoretical contribution on how to obtain unbiased loss estimates in this case, identifies an issue with the high variance of these estimates, and proposed a lower-variance upper-bound that could be used as a surrogate loss. 

The main drawback of the paper, as originally submitted is the very limited experimental evaluation. The authors explain the lack of empirical results by the fact that there are no datasets that have accurate propensity scores available, so even evaluating on such datasets would be meaningless. While it is true that existing datasets do have this problem, it is incumbent on the authors to find an application where their work would be applicable. Otherwise, if there is no application that can benefit from this work, what is it useful for?  One suggestion I can make to do the following evaluation: take a (sub-sample) of the instances  that method M assigned label L to and, using human labelers, determine how many of those documents should truly be assigned label L and how many should not have label L. Do this for multiple labels L.  While I admit that this would be a tedious endeavor, it would be possible to achieve with current crowdsourcing technology, and it would significantly improve the paper.  

During the author response period, the authors have submitted additional results on some real datasets. These results do look pretty strong, but, because they have been rushed and not really integrated in the paper, I fear is difficult for the reviewers to truly scrutinize their validity, and to draw the correct conclusions from them.  The paper would benefit from having the authors integrate the results in the paper and fully analyze them. 

I do believe this is interesting work, and I encourage the authors to revise and resubmit their paper at a future conference. But as it is, the paper is not yet ready for publication. 
confidence: Less certain
Decision: Reject