Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: ### Summary
The paper proposes a heuristic version of top-k negative sampling which is computationally effective. The main toolbox for this heuristic is locality sensitive hashing. The contribution is mainly algorithmic with an implementation. Experimental results support the effectiveness of the heuristic.

### Strengths
+ The use of LSH in machine learning applications is very promising, and this paper takes this trend to yet another direction where it can make a difference.
+ The approach is simple to describe and implement.

### Weaknesses
- There are several claims that are mostly marketing, namely “adaptivity” and “distribution awareness”. Yes, the sampling depends on the updated weights. But exactly how and in what manner that relates to, say, approximating the true objective, are not treated. The best intuition we can get is by thinking of the new method as a heuristic to top-k negative sampling, leading to believe that maybe some of the latter’s statistical/optimization properties are inherited. But this relationship is not made at all.
- The Theorems are mostly ornamental, they do not add anything new or relevant.
- It’s true that the proposed algorithm is amenable to a CPU implementation. But the CPU on which the experiments are run is a behemoth (28 core, 224 thread). So it clearly still needs the added parallelism to be competitive.
- The significance of the result are weakened when compared against one of the simplest alternatives, the sample softmax (orange curves in Figure 4). It is evident that in terms of reaching the vicinity of the ultimate accuracy, the sample softmax takes the same (if not less) time than the new method [the per-iteration plots are not very relevant, they demonstrate interim accuracy but have no bearing on ultimate accuracy and speed up].
So claims like “[these alternatives] fail to demonstrate any training time improvements” (page 2) are clearly false. Granted, sample softmax would be of order $O(\log N)$, but in practice this clearly is not a handicap.
- ~~For an application such as this, the details of LSH’s choices are critical, yet the paper only glosses over them. For example, the similarity metrics should differ between the “embedding” version and the “label” version, this is briefly alluded to in the experiments section without much explanation or references.~~ [Edit: thanks for clarifying this.]

### Overall
The motivation and approach of the paper are very strong. But the results are not as strong as they are hyped up to be, since a simple alternative achieves the same practical accuracy/time benefits and no guarantees are given for the accuracy of the new heuristic sampling, not even in terms of approximation of another heuristic such as top-k. This means any potential adoption would be based merely on experimental evidence. The fact that the algorithm can be implemented on a (highly parallel) CPU is not a good enough selling point, especially when not pitted against an equivalent optimized CPU implementation of the simple alternative.

_[Edit: The authors do not give any substantive feedback to my review, except for clarifying the hash choices. It is surprising that they object so vehemently to my intuitive description of their method as a heuristic to top-k, when they themselves write "Our proposed negative sampling scheme is a proxy to topK-softmax. It selects the top-k classes via LSH [...]". Also my reading of the sampled softmax is directly from their paper, showing a comparable accuracy-time tradeoff, but I was not refuted on this and instead was given other references claiming the inferiority of that method. I have updated my recommendation to reflect these shortcomings.]_

review_title: LSH for negative sampling, as heuristic for top-k softmax. Implementation on multi-threaded CPU. Does not beat sampled softmax on GPU, gives no accuracy or approximation guarantees.

final_score: rating: 3: Clear rejection
review_content: This paper proposes a neighbor search method for negative sampling in extreme classification. The core idea is to use hash tables to select neighbors of a query.

I agree with the authors that:
i) The proposed hashing method can quickly retrieve neighbors for arbitrary queries in nearly constant time.
ii) Selecting hash functions is important for potential gain.

However, I think there are still missing pieces in this paper that need to clarify:
i) How do you calibrate the negative sampling results?
ii) How do you tune K and L in your experiments. To my understanding, using either too large or too small K and L is suboptimal in your setup.
iii) You mentioned that you are using CPU or computation. But the CPU and GPU precisions may contribute to the final result. Have you studied that in your experiments?

There are still some points that I disagree with:
i) There is no consensus that whether “easy negatives” or “hard negatives” should be selected in extreme classifications. For a recent survey on this topic, see “Embedding-based retrieval in Facebook search” by J. Huang et al. So I wonder if the hashing algorithm has the capacity to choose both easy and hard negatives?

ii) You claim you are using an O(1) algorithm independent of negative classes N. But this is simply not true and not reasonable because your K and L may need to increase when N grows in order to keep a constant collision probability.

iii) You mentioned you propose two schemes: “LSH Embedding” and “LSH Label”. But those two methods only differ in query representations. It would be interesting to compare these two carefully in experiments.

Overall, I think this paper over-claim its contribution even though it proposes a tractable solution to extreme classification.

review_title:  I think this paper over-claim its contribution even though it proposes a tractable solution to extreme classification.

final_score: rating: 7: Good paper, accept
review_content: The paper studies extreme classification, where the number of classes is very large.

In that case, previous work came up with a technique to subsample bad classes for each data point to approximate cross-entropy or other used loss. Prior work used uniform samples, but this paper proposes an approach based on locality-sensitive hashing. One particular challenge that the authors need to overcome is updating LSH tables during the backpropagation (where parameters get updated).

The experiments are very convincing and show that CPU C++ implementation that uses new sampling can outperform GPU-based approach based on uniform sampling.

One comment is that the writing is fairly sloppy and could use additional polishing.
review_title: Looks like a great paper, somewhat sloppy writing

final_score: rating: 5: Marginally below acceptance threshold
review_content: When the number of classes is very large, calculating softmax for classification (e.g., in backpropagation) is computationally costly. Approaches based on negative sampling have been used in literature to alleviate this problem. However, most of existing approaches are (argued to be) either inaccurate or computationally costly. This paper proposes to use the well-known LSH (locality sensitive hashing) method to address this problem. In particular, two variants, LSH label and LSH Embedding are showed to speed up the training in terms of time needed to converge compared with a number of baseline methods over three large scale datasets. 

+ The suggested approach is simple, making it potentially useful in practice. 
+ The methodological contribution of the paper is more or less an off-the-shelf use of LSH for negative sampling. This being said, the application of LSH in this context is (seemingly) new, and the two basic similarity measures are interesting.
+ I would be cautious about calling the method "A truly constant-time" method. If we assume K and L are constant then yes; but theoretically in order to get good result we need to have larger values especially for L. Please elaborate on this.
+ The two theorems offered in the paper are the theorems from the LSH literature. Since a proxy is being used for similarity (e.g., label or embedding) these do not translate into the final classification result. The authors can perhaps elaborate on this and also give clues on how large K and L should be set depending on the parameters of the dataset, etc.
+ In intro we have "We show that our technique is not only provable but .."; it is not clear what is exactly provable, and how it relates to the classification result. 
review_title: Simple yet effective approach for efficient negative sampling

Meta-review: All reviewers agree that this paper is interesting, but needs improvement in order to be suitable for a highly competitive venue such as ICLR. Reviewer 3 is especially incisive and detailed, but other reviewers make similar points.
Decision: Reject