NeurIPS 2019
Sun Dec 8th through Sat the 14th, 2019 at Vancouver Convention Center
Paper ID:5787
Title:Random Projections with Asymmetric Quantization

Reviewer 1

This is a tricky article to review. It clearly makes some significant contributions, especially when it comes with a methodology for obtaining a quantization scheme that minimizes debiased variance. On the other hand it is very hard to read with multiple grammatical and syntactic mistakes. The main topic of the paper, asymmetric quantization, is not formally defined until page 6 and then is discussed for less than half a page. Meanwhile other results, mostly having to do with debiased estimator variance for the symmetric case, cover the lion's share of the paper. As far as I can tell these results end up having no connection with the asymmetric case. In the end this paper feels like a collection of cool results that were rushed into a paper with no common thread. In the end it doesn’t form a cohesive unit. I don’t like the idea of turning down a valuable paper for structure alone but in the end this paper just lacks the necessary polish to be published (which it ultimatly should be).

Reviewer 2

Overall an interesting paper, with useful results. I would consider the ordering question to be the most interesting contribution. However, the ordering matters when the nearest neighbors are of different classes (i.e., if the ordering of distances changes after quantization, it doesn't matter if both neighbors are in the same class). It is not clear how to properly model and analyze that, but it is worth some discussion in the paper. ==== I've seen and taken into account the author's response, and it does not change my score.

Reviewer 3

I think this paper is in good quality. The problem is not very complicated, but the authors studied the problem thoroughly, from theoretic analysis of mean and variance in different scenarios, to proposed refined method and experimental studies. I think this paper meets the standard of NeurIPS. Here are some minor suggestions. 1. I wish to see more discussions about previous work on quantized random projections, especially for cosine-similarity or inner-product estimation. The authors provide some references in the introduction, but I wish to see more detailed comparisons of results of the previous work and the current work. This will make the main contribution of this work more clear. 2. In Figure 1, please make the y-axis of the first two figures aligned. Also for Figure 2. 3. In the supplemental materials, the section numbers are wrong. (should be Section 3 in the title of Section A, etc.) ============================================================== I'm satisfied with the authors' feedback and I would like to increase my score from 6 to 7. I vote to accept this paper because of its high technical quality. I wish the authors could improve the paper's organization and presentation to match the technical quality of this paper.