Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: Summary of the paper:

This paper introduces a framework that uses an LSH sketches to improve time an memory bottlenecks neural network training. Specifically, an LSH sketch is used to approximate the matrix multiplications involved in training. It is observed that networks' weights get stable after small number of epochs therefore frequent updates to LSH sketches (which is expensive) are not required. This paper uses data dependent/learnable LSH methods that better adapt to data in order to improve the performance (query and update) of the sketches. Ample experiments are provided to validate the results.

Quality:

Needs improvements in notations. For example, in assumption 3.1, sum is over what? If the indexing is over $i$, then does that means over rows of $w$s (since $w \in \mathbb{R}^{n \times d}$)? Then should the quantities be L2 norms since they are vectors?

Clarity and the presentation can be improved significantly. For example, "Rehash", "Rebuild" functions in algorithm 2 needs to be defined or explained. In general it is better to explain the intuition behind both algorithms 1 and 2.  I believe the figure 1 should clarify the LSH update scheduling, but it is not very clear.

Originality and significance:

I believe that the ideas presented in this paper adds nice contributions to the ICLR community. The idea of using learnable LSH that adapts to the data together with the observation that the weights stabilize after a few epochs is a clever approach to improve the bottlenecks associated with using vanilla LSH sketches.

Other comments:

In regards to the observation with figure 3, I am curious what properties of a dataset leads to this kind of behavior? are there any quantifiable properties? Is this true for any dataset? Are there previous works that explains why this is the case?

Final feedback:
I understand the idea of the proposed framework and the theoretical claims look natural and believable, but the presentation needs to be improved. I am willing to increase my score if the concerns mentioned above are properly addressed.


=====================================================================================================

Added after author response

----------------------------------------

I believe authors have clarified many things I asked and addressed the issues I and other reviewers raised. Therefore, I increase my score. I believe the idea of using LSH for efficient training has a lot of promise and this paper brings a possible way to do this into light.
review_title: The framework presented in the paper adds decent contributions, but substantial improvements are needed in writing and presentation.

final_score: rating: 7: Good paper, accept
review_content: Some neural network runs involve layers with a large number of neurons. These require large matrix-vector or matrix-multiplication which can slow their training/inference. However, if the output of mat-vec/mul is dominated by a few neurons with which the activation has large inner product (a matmul can be thought of as a weighted sum of inner products), then the computation can be sped up by approximating mat-vec/mul by a limited weighted sum with the dominant terms. This requires maintaining an ANNS data structure that is up to data with the back prop. These updates to ANNS have to be done carefully -- too frequent and the training will slow down, or too infrequent and the results of the mat-mul are way off.  This paper studies how to do this in a principled way using data-dependent LSH updates and backs it up with experimental data.

The ideas and algorithms explored in the papers are as follows:
1. The weights changed in a limited manner over time, so it should be possible to take advantage of this.
2. Concentrated changes to a subset of weights can be tracked and patched upon.
3. An LSH update rule to make these changes effectively
4. An earlier algorithm that is reused to decide when the LSH scheme is updated.

The paper also talks about how to identify the layers that benefit the most from this scheme. then it goes on to show the training time benefits of the smart scheduler and the update scheme on extreme classifications tasks as well as transfomers.


Few questions:
1. Why no serious consideration of graph based ANNS? They are data dependent and SOTA for search efficiency and it is possible to update them. Why is LSH the better choice for ANNS here? This needs a rigorous argument. 
2. Is this really a general and serious enough problem amongst practitioners that a solution merits publication at a popular conference? It might be, in which case a better quantification of potential impact can help. 
3.   Is wiki-325K really the largest dataset for XC? What about larger language models -- sec 4.1.2 seems to study more medium sized networks. Larger scale experiments could make this paper more compelling.

I would more strongly recommend this paper if these questions  can be addressed.
review_title: A principled approach to updating LSH based ANNS for faster matrix multiplication in NN training

final_score: rating: 7: Good paper, accept
review_content: Summary:
The authors make a good insight into the slowly changing of Locality-Sensitive Hashing (LSH) hash codes for the weights (or model parameters) during the Neural Network (NN) training. With this new insight, they introduce a framework Mongoose with a newly designed schedule mechanism to reduce the LSH update overhead. The authors also analyse their model and show some bounds for batch speedup and LSH maintenance. Experimental results validate the efficiency and effectiveness of Mongoose over original LSH methods in NN training.

Pros:
1. First of all, I like the problem the authors focus on. Efficient NN training is very necessary. The idea of using LSH for acceleration is a good direction. 
2. The observation of the slow change of LSH hash codes is good and impressive. The authors also conduct many experiments to validate this observation. 
3. The idea of using a scheduler for lazy updating is interesting, and they add theoretical analysis about it. And based on the experiments, it seems that this scheduler can capture the changing of model parameters. 
4. The proposed framework Mongoose seems to be general for different deep learning model.

Cons:
1. Compared to the good insight and the promising framework, the practical improvement is fair. Although the authors provide many experiments to demonstrate the effectiveness of Mongoose, I still suggest the authors conduct more experiments about parameter studies and memory usage which may be good to improve the paper quality. More details can be found in minor comments (1 & 2) later. 
2. Since the idea of the scheduler is inspired by a former work (Cohen et al., 2019), I suggest the authors add a discussion about their connection and difference. 
3. The presentation is not very clear. Many notations are used without pre-defined. More details can also be found in minor comments (3 ~ 6) later.
4. For the learnable LSH (Section 3.3.1), when selecting positive/negative samples, the authors use the inner product, while for the loss function, they consider cosine similarity. I suggest the authors make an illustration about the use of these two different measures. 

Minor Comments or Typos:
1. The framework Mongoose consists of many parameters. A fresh user may do not know how to set up them. A discussion of parameter settings or some experiments about parameters studies seems to be necessary.
2. The authors claim Mongoose is memory-efficient for NN training. However, I cannot find analysis about space overhead or experiments about memory usage. It should be done to correspond to this claim. 
3. For Assumption 3.1, what are the definitions of C_1 and C_2? Is user-defined or auto determined? Since Theorem 3.3 and some Lemma in the appendix also use these two notations, are they the same? For a rigorous expression, I think some declarations are necessary. Also, in Theorem 3.3, the condition of r for g_r is not clear.  
4. More problems can be found in Algorithm 1. It seems the core idea of this paper, but there are many typos and errors. For example, 
The parameter ‘A’ is not defined and may be unnecessary in Initialize function (line 2). 
In line 4, what is the definition of \epsilon_{mp}? Does it have any connection with \epsilon_{mds}? In order to have guarantee for LSH, c_1 - \epsilon_{mp} should be larger than c_2 + \epsilon_{mp}. How to ensure this?
Why setting 1.5 for a smooth cut (lines 13-15)? Is it an empirical value or has any benefit?
In line 17, LSH may update with w^{new}_{\pi([r])} instead of \pi([r]).  
5. The y-axis of Figure 3 should be \Delta H (left-subfigure) and \Delta W (right-subfigure) instead of Hamming and L2 distance. 
6. The caption of Figure 5 is not clear. And for the sentence “Figure 5 shows P@1 and P@5 for Mongoose and other baselines…” in the paragraph of results in Section 4.1.1, “and P@5” should be removed. 

In summary, I like the motivation and the observation in this paper, and the method Mongoose looks good, but I still have many concerns about the idea. So at this stage, I first give a borderline for this paper. I hope the authors can address my concerns. 

====================================================================================================

Update: Thank you for your new experiments and detailed feedback. Most of the concerns have been addressed and the experimental results look better. I believe this paper will provide new insight into efficient neural network training. Thus, I raise my rating and recommend this paper to be accepted.

review_title: Good intuition and novel method, but fair practical performance

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: +++Pros.  
-----The observation that model parameters evolve slowly is quite inspiring for more efficient neural network training.  
-----The paper proposes MONGOOSE, which is equipped with a scheduler to adaptively perform LSH updates and learnable hash functions to improve query efficiency.  
-----Experiments demonstrates the effectiveness of the proposed method, and ablation studies give the readers further insights.  

+++Cons.  
-----The paper is overall good, but with some minors, such as “Figure 5 shows P@1 and P@5 for MONGOOSE and other baselines during the training process.” in Section 4.1.1.  
-----Besides, there are several mathematical symbols should be explained clearly when they first appeared, such as “w” in definition 2.1, “C1, C2” in assumption 3.1, “t_r” in assumption 3.2.  

+++Conclusion.  
-----Based on the above analysis, I would prefer to make an “ACCEPT” recommendation.  
-----By the way, I’m curious about why you named your method “MONGOOSE”? Could you give some reasons?  

+++Suggestions.  
-----Better make the mathematical symbols more clearly for readers.  



review_title: Enabling LSH in a learnable framework to speed up neural network training is quite interesting and critical in deep learning era. Experiments on recommendation and language modeling tasks verify the effectiveness of MONGOOSE. Besides, the related formal analysis also seems solid.

Meta-review: Thanks for your submission to ICLR.

When the initial reviews were written, three of the four reviewers were positive about the paper.  Everyone felt it was overall a solid contribution, but there were some concerns about the clarity and presentation, as well as some suggestions for additional experiments.  During the rebuttal/response period, the authors did a very nice job in responding to the concerns of the reviewers.  Ultimately, all of the reviews were in agreement after discussion that the paper is strong and ready for publication.   I also like this paper a lot, and find it to be a nice way to combine LSH with NN training.  I am happy to recommend this paper for publication.
Decision: Accept (Oral)