Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 3: Clear rejection
review_content: The paper proposes to use high-dimensional sparse representation as opposed to low-dimensional dense representation for representing input text. This can be useful in information retrieval applications. The proposed model is evaluated on a "product to product recommendation" dataset and shows superior performance compared to the prior work.

The paper's strengths:
1. Studying an important and interesting research problem (i.e., learning sparse representation for information retrieval)
2. The paper is well-written and easy to follow. It is also well-structured. The results are well presented.

The paper's weaknesses:
1. In several places there are some overclaims that should be fixed. For example, in abstract and introduction (when describing the paper's contributions) it is mentioned that "In this paper, we make a novel and unique argument that sparse high dimensional embeddings are superior to their dense low dimensional counterparts." This is simply not true. As we go forward in the related work, we can see that the authors mention that SNRM [40] has exactly the same idea with empirical evidences. I think the authors should be more careful in claiming what is novel in their paper and what is borrowed from prior work.

2. I think the weakest part of the paper is its evaluation. Here is the detailed comments:
2.1. First of all, it has been only evaluated on a single dataset. It would be nice to see how the results can be generalized across datasets. Second, the task they used for evaluating their model is pretty artificial. There is no such real-world task as "product to product recommendation" and the experimental setting is not realistic at all. I believe using such synthetic datasets for evaluating models is acceptable when there is no good alternative publicly available. However, in this case, there are numerous large-scale datasets that can be used to evaluate the model. For example, MS MARCO dataset from Microsoft has been widely adopted by the research community and can be used for evaluating the model. A lot of Open-Domain QA datasets are available too. 

2.2. As mentioned multiple times in the paper, SNRM is the only paper with the same idea of learning high-dimensional sparse representation. However, the results reported in the table are strangely low. Looking at the SNRM paper (which was published in 2018, so it's not an old paper) we can see that it outperformed a lot of strong baselines on a number of benchmark. I understand that sometimes it is difficult to reproduce the results from some papers. However, the SNRM paper seems to be cited by over 60 papers and some of them reported its results on different datasets and they all reported a reasonable performance for the model. I personally think that the authors did not carefully select the sparsity hyper-parameter in the SNRM model. I also recommend the authors to include some non-neural baselines, such as BM25 and RM3 as they sometimes outperform neural network models on information retrieval related tasks.

3. It is not clear how scalable the model is and actually I have some doubt about its scalability. What will happen when the number of items goes beyond tens of millions or even billions? These questions are important to be answered when a model is proposed for information retrieval or recommender systems.

All in all, I believe the authors are working on an interesting problem but the experimental results are not convincing and some claims should be changed. Some questions about scalability remain unanswered.
review_title: Interesting problem but  poor evaluation and some unjustified claims

final_score: rating: 7: Good paper, accept
review_content: The work describes an extreme classification strategy which leverages the computational efficiency of multiclass (and multilabel) efficiency on small label sets (circa 10K) composed with the near-orthogonality of random sparse embeddings; while exploiting inherent parallelism of repeated independent instantiations of this primitive technique to mitigate statistical issues.  

The use of fixed near-orthogonal label embeddings is elegantly motivated, the computational properties of the technique are favorable (especially, amenability to inverted indexing), and the statistical performance is competitive.

Inference only gets passing treatment in the entire exposition, without any supporting rationale.   For instance, this reviewer was surprised that inference involves summing over predicted probabilities, rather than summing logs of predicted probabilities.  Essentially there are a collection of K independent predictors that we are trying to ensemble, a problem that has received lots of attention in the literature.  Making these connections would both help the reader and also potentially improve the technique.
review_title: Compelling rationale and experiments, but inference is barely discussed

final_score: rating: 7: Good paper, accept
review_content: The paper studies the problem of document retrieval using embedding based models. It argues that performing near-neighbour search on a large number of dense embeddings hurts performance and accuracy. As an alternative, the paper proposes SOLAR (SPARSE ORTHOGONAL LEARNED AND RANDOM EMBEDDINGS), a model which uses high-dimensional, ultra sparse embeddings, on which near-neighbour search can be done using simple lookup operations. In SOLAR the document labels are divided into equal chunks of sparse vector, and independent models are learned for mapping the query to each chunk. Hence, SOLAR could be trained on multiple GPUs in an embarrassingly parallel way without requiring any communication between the GPUs. The paper demonstrates the effectiveness of SOLAR by comparing it against strong baselines on various recommendation and extreme classification datasets. It also provides theoretical justification for SOLAR by showing how “one-sided” learning (i.e. fixing label embedding but learning mapping from query to label) is mathematically equivalent to “two-sided” learning (i.e. jointly mapping the label and query to a common space).

#### Strong points: 
- **Well-motivated problem:** The paper does a very good job in motivating the problem, and highlighting the potential issue with dense embedding based models for large scale problems.
- **Interesting result:** The paper argues the current convention for document retrieval is of using low dimensional dense embeddings. It is thus interesting that a method that against the standard notions could perform so well. 
- **Practical approach:** The proposed method seems to be simple to implement and easily scalable to a large number of parallel processes. This makes it practically valuable, especially in large-scale problems.
- **Empirical evidence:** The paper provides strong empirical evidence. SOLAR outperforms industry standard embedding models while taking less query time on a 	Product to Product Recommendation dataset. SOLAR also performs equally well on various extreme classification benchmarks.
- The paper is well written and well structured. The theoretical results are also presented in an easy-to-follow format with consistent notations.

#### Weak points: 
- **Potential Issues/Questions about the baselines:** I was wondering why are the baselines in Table 1 trained for only 5 epochs and not until convergence.  Can the performance of the baselines be improved by training more?
- Similarly, I could not find information about the compute used during inference for the baselines and SOLAR. Can the inference speed of the baselines and SOLAR be improved by simply using more compute?
- How sensitive is SOLAR with respect to the random seeds chosen for the K models? In other words, how much would the performance vary if we start with a different set of random seeds? 
 
#### Overall Recommendation:
Although some information about the baselines is missing, overall I feel that the paper presents an interesting and practical method with strong empirical evidence. The paper is also well presented and is easy to follow. I currently support acceptance, but would form a final opinion based on the authors response.

review_title: Official Review

final_score: rating: 7: Good paper, accept
review_content: This submission addresses the problem of learning document embeddings for document retrieval/recommendation tasks. Such tasks are characterized by a large number of documents and a large set of semantic class labels. In contrast to the now standard approach of representing documents and their labels as dense low dimensional embeddings, this work proposes to use sparse high dimensional embeddings for documents/labels and claims that the proposed approach has certain advantages over state of the art:
	1. It results in memory efficient and load balanced inverted index that facilitates fast index based lookup for retrieval  
	2. It enables distributed training on disjoint parts of the label vector and thereby speeding up training.

Unlike the common approach of jointly learning the document and label embeddings, the proposed approach employs random binary embeddings for labels.  The label embeddings are high dimensional, sparse and mostly orthogonal by design. Each label in the training data is assigned a random K-sparse (only K > 0 bits are 1 and rest are 0) binary embedding independent of other labels as well as documents associated with the label and any semantic features (such as label text/title) the label might have. When they are sufficiently high dimensional, random embeddings ensure that the resulting inverted index is both balanced and  each bucket in the index has only a small number of labels. 

As the label embeddings are random and each bit in the embedding is independent of all other bits by design, the embeddings can be partitioned into multiple disjoint blocks and each block can be used to independently learn partitioned embeddings for the documents. As this requires no communication between the different threads working on different blocks, training can be very fast.  

To keep the model size low, the work proposes to use a simple feed-forward network with only one hidden layer. There is one such network for each block and as they are trained independently, there is no sharing among the models.  Also, unlike other approaches, the proposed work doesn't make use of pre-trained word embeddings for training document embeddings. Instead it uses a feature hashing scheme to map the very high dimensional text data to reasonably low dimension. This eliminates the need to store word embeddings in memory. As feature hashing is memory efficient, the only structures that need to be in memory are the parameters of the feed-forward network and the inverted index thereby achieving memory efficiency at query time.

The submission presents experimental results comparing the proposed approach with a few baselines. The results are promising in terms of retrieval efficacy on multiple data sets.

While the proposed approach is well engineered to achieve its twin goals of memory efficient and load balanced inverted index and distributed training, there are a few concerns about the methodology. 

First is about the rationale behind using random binary embeddings for labels. As observed earlier, such an embedding is independent of other labels as well as documents associated with the label and any semantic features (such as label text/title) the label might have. This seems to be a rather poor utilization of the rich semantic relatedness in the data for the sake of engineering gains. It can be argued that methods that ignore label correlations and other semantic relationships in the data are suboptimal.

Second concern is about the harmful consequences of random embeddings. As authors note in the appendix, unrelated labels fall into the same bucket. As each bucket has only a small number of labels, it is unlikely that a significant number of the labels assigned to a bucket are related. Therefore, it is unclear to this reviewer what does a bucket represent semantically other than being a collection of unrelated labels. Would this not affect the training of the classifier mapping documents to the bucket adversely? Empirical results seem to suggest otherwise, but this is an issue that needs both deeper theoretical and empirical investigation. Further, in the proposed approach, semantically related labels are likely to have dissimilar embeddings. This goes against the traditional view, particularly in semantic hashing, that similar labels should have similar embeddings. 

Third, authors claim that one-sided and two-sided learning are mathematically equivalent. This is true only when label embeddings are orthogonal. When the embeddings are low dimensional as in other methods, orthogonality of label embeddings is neither strictly guaranteed nor necessary. 

Fourth, though authors don't say it, K and B are hyper parameters in the proposed approach. The tuning of these hyper parameters does add a significant overhead to training which is not shown in the experiments. So the claim on significant training speed gains over baselines is suspect. 

Fifth, it is not clear whether the proposed work uses the same tokenization scheme as used by the authors of DSSM, viz Unigrams+Bigrams+Char Trigrams+OOV, in the experimental comparison with DSSM. As observed in DSSM paper, the choice of tokenization affects the retrieval accuracy significantly and a fair comparison would necessarily need to use the best tokenization scheme. 

Some suggested corrections:
	1. In figure 1, classifier 1 appears twice.
	2. In figures 1 and 3, k should be K.
	3. In the feature ablation study, the best performing setting is B = 30K, K = 32 (based on P@1, P@3, P@5 reported in Table 3) whereas the submission claims that B = 20K, K = 32  is the optimal setting.
	

---

Based on author feedback, here are some additional comments:
I would like to thank the authors for their response to the reviews. As noted in my original review, the proposed method is a well-engineered method for a particular type of document recommendation problem. Empirical performance on the chosen data sets is impressive compared to the baselines. The claim on gain in training speed is suspect as there is a hyper parameter tuning step that has been not taken into account while reporting the speed gain over the baselines. Label correlations are not taken into account for label embeddings and might hurt the performance when there are not many documents in the training data for the long tail of labels in many real-world applications. Random embedding puts unrelated labels into the same bucket. Though this doesn't seem to hurt retrieval performance in the experiments reported in the submission thanks to filtering, it is not clear how training will be affected by this non-semantic bucketing of labels. Overall, I think the submission has several things going in its favor though there is substantial scope for strengthening. 

I've updated the rating. 



review_title: Well engineered solution for document recommendation tasks with some concerns about the methodology

Meta-review: The paper proposes an approach to learn sparse embeddings for documents/labels which can be trained by using multiple GPUs in parallel, and are more amenable to nearest neighbor search. 

The paper certainly seemed to have botched  comparison to SNRM and requires to fix the claims in  section 5.1. 
But, the impressive performance on extreme classification tasks is quite convincing. Also, reviewers in general are quite enthusiastic about the paper. So we would recommend the paper for acceptance, but authors certainly need to take comments of reviewers into account (especially around baselines and comparison to SNRM).
Decision: Accept (Poster)