Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 8: Accept
review_content: This work addresses the problem of training softmax classifiers when the number of classes is extreme. The authors improve the negative sampling method which is based on reducing the multi-class problem to a binary class problem by introducing randomly chosen labels in the training.  Their idea is generating the fake labels nonuniformly from an adversarial model (a decision tree). They show convincing results of improved learning rate.
The work is very technical in nature, but the proposal is presented in detail and in a didactic way with appropriate connections to alternative methods, so that it may be useful for the non-expert (as me).
That is the reason why I recommend to accept this work: even not being an expert I found the paper educative in introducing the problem and interesting in explaining the proposal. 
review_title: Official Blind Review #2

final_score: rating: 6: Weak Accept
review_content: This paper focuses on efficient and fast training in the extreme classification setting where the number of classes C is very large. In this setting, naively using softmax based loss function incurs a prohibitively large cost as the cost of computing the loss value for each example scales linearly with C. One way to circumvent this issue is to only utilize a small subset of negative classes during the loss computation. However, uniformly sampling this subset from all the negative classes suffers from the slow convergence as such sampled negatives are not very informative for the underlying classification task. 

The paper proposes a method to sample the negatives in a non-uniform manner. In particular, given an example, an adversarial auxiliary model that is tasked with tracking the data distribution samples the hardest (adversarial) negatives for the example. The proposed method to sample negatives has a computational cost log(C) and reduces the noise in the gradient. The authors then demonstrate the utility of their proposed approach on two well-established extreme classification datasets, i.e., Wikipedia-500K and Amazon-670K. The proposed method shows improvement over some natural baselines in terms of the wall-time for the convergence of the training process.

Comments

1. The paper has some nice contributions and discusses the key ideas in reasonable detail. However, the reviewer feels that the authors gloss over many relevant prior works and fail to put their results in the right context. There has been quite a bit of work on non-uniformly sampling "hard" negative classes. For example, see [1], [2], [3], [4]. In fact, [3] and [4] propose methods to sample negatives from a distribution that closely approximates the softmax distribution at the cost that scales logarithmically in C, essentially providing the hard negative without having to keep an auxiliary model. Can the authors discuss their work in the context of these works?

[1] Reddi et al., Stochastic Negative Mining for Learning with Large Output Spaces.
[2] Grave et al., Efficient softmax approximation for GPUs.
[3] Blanc and Rendle, Adaptive Sampled Softmax with Kernel-based Sampling.
[4] Rawat et al., Sampled Softmax with Random Fourier Features.
 
2. In experiments, the authors do not include the performance of softmax loss (eq. (1)) due to its large computational cost. However, it would be nice to compare the proposed method with eq. (1) at least for slightly smaller datasets from the extreme classification repository. 

3. In Sec. 4, "We formalize and proof..." --> "We formalize and prove..."

4. In Sec. 1, "We present experiments on several two classifications..." ---> "We present experiments on two classifications..."

5. Table 1 seems to have some typos. E.g., N is the same for both the data sets. Please fix these issues.
review_title: Official Blind Review #1

final_score: rating: 3: Weak Reject
review_content: The paper presents a method for negative sampling for softmax when dealing with classification of data to one from a large number of classes. Its main idea is to negative sample those classes which lead to higher signal to noise ratio than for uniform negative sampling. This is based on building an auxilary model using decision tree from which the adversarial negative classes are sampled, so that the distribution of the negative samples can be close to the positive ones leading to higher SNR while training. The proposed method is compared to other methods for negative samping on two publicly available large-scale datasets from the extreme classification with XML-XNN features. 

Positives :
1. The proposed approach with adversarial negative sampling using an auxilary model seems interesting 
2. It scales well to datasets with large number of classes.

Negatives :
The experimental evaluation of the proposed approach lacks completeness and does not look convincing for the following reasons : 
1. It misses out a recent state-of-the-art method (Slice) for negative sampling on same datasets [1], which also addresses the same problem of sampling most promising negative classes but in a different way. Furthermore, [1] also compares against many other sota methods missed out in this paper on the many other datasets datasets including those in this paper but in a more general multi-label setting.
2. The paper only compares against other negative sampling approaches such as AandR, NCE, and does not show what happens when no negative sampling is done such as done in (DiSMEC) [2]. This is important to understand what (if at all) is lost by doing approximation as proposed. For instance, a quick experiment reveals that DiSMEC can give about 19% accuracy on Wiki500 dataset, which is better than that achieved by the proposed method. Though it is computationally expensive but due to its simplicity, it must be discussed nevertheless to give a complete picture.
Instead the OVE baseline used in the paper seems quite sub-optimal in the first place, and hence stronger baselines [1,2] for which the code and results are readily available and have been duly tested in the community must be used and discussed.

Another aspect that the paper misses out is the role of fat-tailed distribution [3,4] of the instances among labels, which is a property of typical datasets in this regime. It is possible that one can get good accuracy but poor performance on tail-labels due to approaximations. The performance on tail-labels on appropriate metrics other than accuracy, such as MacroF1, should be evaluated.

Also, the proposed approach must be tested on more datasets including the smaller ones such as EURLex (also used in works referenced in the paper) on which it is easier to compare with other methods (such as DiSMEC, Slice and AttentionXML [5]) without encountering computational constraints and also bigger ones such as Amazon3M, also avilable from the repository. 

Finally, it must be investigated if the proposed method can be extended to the multi-label setting or are there inherent limitations of the model in this setting. The possibility to extend it to the general multi-label setting would make this approach more promising and directly comparable to wide range of algorithms.

[1] H. Jain,  V. Balasubramanian,  B. Chunduri and M. Varma, Slice: Scalable linear extreme classifiers trained on 100 million labels for related searches, in WSDM 2019.
[2] R. Babbar, and B. Schölkopf, DiSMEC - Distributed Sparse Machines for Extreme Multi-label Classification in WSDM, 2017.
[3] H. Jain, Y. Prabhu, and M. Varma, Extreme Multi-label Loss Functions for Recommendation, Tagging, Ranking & Other Missing Label Applications in KDD, 2016.
[4] R. Babbar, and B. Schölkopf, Data Scarcity, Robustness and Extreme Multi-label Classification in Machine Learning Journal and European Conference on Machine Learning, 2019.
[5] AttentionXML: Extreme Multi-Label Text Classification with Multi-Label Attention Based Recurrent Neural Networks, NIPS 2019
review_title: Official Blind Review #3

Meta-review: The paper proposes a fast training method for extreme classification problems where number of classes is very large. The method improves the negative sampling (method which uses uniform distribution to sample the negatives) by using an adversarial auxiliary model to sample negatives in a non-uniform manner. This has logarithmic computational cost and minimizes the variance in the gradients. There were some concerns about missing empirical comparisons with methods that use sampled-softmax approach for extreme classification. While these comparisons will certainly add further value to the paper, the improvement over widely used method of negative sampling and a formal analysis of improvement from hard negatives is a valuable contribution in itself that will be of interest to the community. Authors should include the experiments on small datasets to quantify the approximation gap due to negative sampling compared to full softmax, as promised.
Decision: Accept (Poster)