Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper proposed a new method called Clustered Compositional Embeddings (CQR) for learning compressed embedding tables. The method is a QR concat method with a set of specially initialized embedding tables and carefully chosen hash functions. The authors claim that CQR may achieve compression ratios close to those of post-training quantization with the training time memory reductions of hashing-based methods.
strength_and_weaknesses: **Strength**
1. The authors propose a simple method to bridge the gap between post-training quantization and hashing-based methods for embedding compression.
2. Existing methods are fully surveyed and introduced in the paper.

**Weaknesses**
1. The empirical comparisons are incomplete.
(a) The Tensor Train method (Yin et al., 2021) is not compared in the experiments.
(b) The results of PQ is missing in Figure 5 and Figure 6(b).
2. The step-1 of CQR still requires firstly training the embedding tables, and hence the current paper title and the statement, "Our algorithm is the first that deviates from random (or fixed) sketching as the first step of embedding", are both imprecise.
3. Figure 1 is confusing and cannot help understanding the proposed method.
4. Why are the results of PQ in Figure 6(a) and Figure 7(a) so different? It seems that PQ was not correctly applied to the Terabyte dataset.

**Minor problem**

"increases" -> "decreases", end of page 6.
clarity,_quality,_novelty_and_reproducibility: The paper is mostly clear. The proposed method is novel and can be easily implemented.
summary_of_the_review: The proposed method may be useful in practice. However, I wish the authors can address the issues mentioned above.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: Authors point out the pros and cons of two existing methods for table compression. Authors demonstrate that combining hashing and clustering based algorithms provides the best of both worlds. Authors prove that this technique works rigorously in the least-square setting. 
strength_and_weaknesses: Strengths:
1) Authors give thorough literature survey and give intuition on how they proposed their method
2) Authors have strong empirical evidence on datasets used 

Weaknesses: 
1) Paper is poorly written. Each of the sections separately can be well written but it is hard to get a connection between each section.
2) Some of the details are missing to properly evaluate the paper 
3) It is not clear if some of the claims are supported by empirical evidence (e.g. least square setting) and it is also not clear if the evaluation metrics used are the right ones for the imbalanced dataset (e.g. BCE). 

clarity,_quality,_novelty_and_reproducibility: Clarity and Quality: Paper is poorly written.
Novelty: Even though there are no groundbreaking ideas, paper uses existing ideas in novel way. 
summary_of_the_review: 
1) "Unfortunately, in our experiments, DHE did not perform as well as the other methods": Have authors tried other deep hashing methods [1-4]?

2) There is a big jump from section 3 to section 4. What is X and what is Y in the context of hashing or clustering embedding tables that authors talked about in the section 3? It is left to the reader to make the connection. 

3) "We thus give results both for 1 epoch training, 2 epoch training and “best of 10 epochs”: Can authors define what's best here? Is it on a validation set or test set?

4) Figure 5 shows the results with respect to the number of parameters. Would it be possible to share actual computation time comparison?

5) How was hyperparameter selection done for each of the methods, if any? For example, learning rate. 

6) Is BCE the right metric in this case? As it is a click data, it would be too imbalanced. Can authors share more details here?  

7) Most of the plots contain standard deviations. What are these? Were each of the experiments done multiple times? 

8) "We prove that this technique works rigorously in the least-square setting": How is BCE loss used in experiments related to this claim? 

8) Writing: Each section seems disconnected from other sections. Section 2 gives a good overview of existing literature and sets up the proposed method introduced in section 3. But there is a huge jump from section 3 to 4. Section 4 looks like a completely new paper. Start of section 5 is abrupt too and it is not clear what authors are trying to convey without knowing details of the exact dataset and how evaluations of each of the methods are done. Some of the dataset details are missing and not connected to variables used in section 4 where actual optimization is described. Writing should be improved so that readers can easily understand what authors are trying to convey. 

[1] Cao, Yue, Mingsheng Long, Bin Liu, and Jianmin Wang. "Deep cauchy hashing for hamming space retrieval." In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 1229-1237. 2018.
[2]Jang, Young Kyun, Geonmo Gu, Byungsoo Ko, Isaac Kang, and Nam Ik Cho. "Deep Hash Distillation for Image Retrieval." In European Conference on Computer Vision, pp. 354-371. Springer, Cham, 2022.
[3] Boyles, Levi, Aniket Anand Deshmukh, Urun Dogan, Rajesh Koduru, Charles Denis, and Eren Manavoglu. "Semantic Hashing with Locality Sensitive Embeddings." (2020).
[4] Hoe, Jiun Tian, Kam Woh Ng, Tianyu Zhang, Chee Seng Chan, Yi-Zhe Song, and Tao Xiang. "One loss for all: Deep hashing with a single cosine similarity based learning objective." Advances in Neural Information Processing Systems 34 (2021): 24286-24298.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a new quantization method to deal with high dimensional categorical features in recommendation systems. 

strength_and_weaknesses: Strengths:

The background and related work parts are very well written. It is easy to understand the different approaches, even a bit easier than the proposed approach itself.
  
The method is supported by experiments made on two publicly available datasets. 

Figure 5 with accuracy against the number of parameters serves as complexity analysis of the cost of storage.

I liked the authors also explain what they tried and did not work.

Weaknesses:

I think the clarity of the paper can be improved for the part describing the model itself:

Figure 1 is supposed to describe the proposed model “Clustered Compositional Embeddings” (CQR) but in the caption the model is denoted as Cluster QR. Two different nominations can be misleading. 

Figure 1 and Figure 4 (b) which refer both to CQR do not seem to show the same model.

In Figure 6, “CQR half” is mentioned before introduction (definition is done only in Appendix). 

There are several references to training time but it is unclear to me whether this is the one to obtain the embeddings or the one for training the recommender system. 

What would be missing is a complexity analysis of the computation time? Figure 6 shows only the impact of 1 ou 2 epochs on the accuracy (depending on the number of model parameters).

I have several questions:

Q1: p.6: How many samples are considered for step 2? 256 * k but how is k defined?
1000 cluster points: is 1000 the size of S? Are the cluster points the centroids so k = 1000? A diagram flow of the 3 steps would be helpful to understand. 

Q2: Where does fit the analysis (section 4) compared to the 3 steps described before? It seems the result of the clustering is used for sparse approximation of $T_i$ but the authors say later: “it could also be done in other ways”. And theorem 1 which follows brings guarantees for a random $H_i$.

Q3: p.7: Figure 5 is with which Criteo dataset? Two are introduced. 
“Our method was able to reach the baseline”: what is the baseline? We have to wait for paragraph 5.2 for a description of the baseline. Can we have a reference in the caption for clarity? Or indicate that dashed points are for the baseline? 

Q4: p.8: Dataset paragraph: How the pre-hashing is made for Terabyte dataset?

Q5: Do you have reference(s) on the fact recommendation systems are not trained until convergence? 

Minor (typos):
-p.3, fig.2: missing bracket for reference to the DLRM model \citep instead of \cite?
-p.9, fig 6 (b): missing “s” to “2 epoch”.

clarity,_quality,_novelty_and_reproducibility: Clarity can be improved as per my remarks above. 
In terms of reproducibility, use of public packages and datasets is very helpful. 

summary_of_the_review: I missed several key points of the paper: 
1) how CQR works overall from the paper. I think the authors can clarify because the related work section was very well explained. 
2) The link of theorem 1 for a random matrix instead of à learned one with CQR
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper presented Clustered Compositional Embeddings (CQR) compressing embedding tables. The method combines QR concat  with hashing based methods to achieve the best of both worlds. The paper argues that CQR may achieve compression ratios close to those of post-training quantization with the training time memory reductions of hashing-based methods.

However, the paper during submission was not written properly and reviewers cannot verify a lot of interesting claims and arguments. Their reviews clearly points out their lack of excitement.  The authors did a major revision of the paper post response. 

justification_for_why_not_higher_score: NA
justification_for_why_not_lower_score: NA
Decision: Reject