Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper improves RFF-based hashing methods, and verfies it empirically.
main_review: I have the following concerns of the paper:

* limited method novelty: the proposed method SignRFF (eq. (7)) simply replaces the stochastic rounding into a deterministic form. In the whole section 3, only Proposition 3.4 is new, which proves that SignRFF is also locality-sensitive.

* The empirical observation "the results also reveals that LSH-type methods are better than data-dependent and deep hashing methods when the code length is moderately large" is not new as well, [1] has the exactly same, and comprehensive study.

* The empirical performance of SignRFF is not very competitive against other LSH methods.

* The adopted hamming ranking retrieval method is not very efficient. It'd be better to use hashing table(s) for evaluating retrieval performance.


[1] A Revisit of Hashing Algorithms for Approximate Nearest Neighbor Search, TKDE




summary_of_the_review: Given the limited method novelty and empirical findings, I'd recommend a reject.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposed an improved version of Random Fourier Feature (RFF) based binary feature coding method as well as a new measure(ranking efficiency) to compare different Locality-Sensitive Hashing (LSH) methods. Under the new measure, the proposed method is better than previous methods. The authors also validated by visualization the consistency between theoretical comparisons based the proposed measure and the empirical results.
main_review: 1. The proposed ranking efficiency measure gives an objective measure of different Locality-Sensitive Hashing method.
2. The proposed hashing method was able to surpass other method. It is impressive given the simple modification based on SQ-RFF;


summary_of_the_review: The author does a great job explaining the idea, concepts, procedures and experiments.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: In this paper, the authors propose a simple strategy to extract random Fourier feature based binary codes. The authors also propose a new measure, ranking efficiency, to compare the search accuracy over two datapoints for locality-sensitive hashing methods. Experiments are conducted on several image retrieval datasets to validate the effectiveness of the proposed SignRFF.
main_review: Strengths:
1. The proposed SignRFF is simple. It is a simplified version of SQ-RFF by taking out the random perturbation. 
2. A new measure called the ranking efficiency is proposed to measure the practical performance rather than the worst case performance of LSH methods. This measure makes sense to consider the probability of retrieving a wrong/reversed similarity ranking.
3. The paper is well written and easy to follow.

Weaknesses:
1. The technical contribution is the comparison of different LSH methods with the new defined ranking efficiency measurement. While the ranking efficiency measure is computed with theoretical analysis and some approximations, the comparison is conducted empirically. Thus, I am concerned about the author's claim of this contribution to be theoretically comparison between LSH methods.
2. While the experimental results in Sec 5.2 look good, the results in Sec 5.3 (Figure 6) suggest the proposed method falls behind the KLSH. Any explanation for such performance gap or solution to remedy the problem would make the experiments and conclusion convincing.
3. The authors argue that using short codes (less than 128 bits) cannot achieve a desirable level of search accuracy for practical purposes. The authors show the variation of recall w.r.t different bits in Figure 3, but fail to show whether the studied bit length is the desirable one in practical situations. Also, the precision is expected to be reported in this study.

Minor:
The \hat{S} is not defined in (12)
There are research papers that study deep learning based hashing methods before 2019, such as 
Deep Hashing via Discrepancy Minimization, 2018
Simultaneous feature aggregating and hashing for large-scale image search, 2017
Deep supervised hashing for fast image retrieval, 2016
Simultaneous feature learning and hash coding with deep neural networks, 2015
Supervised hashing for image retrieval via image representation learning, 2014
it's better to mention these works when introducing hashing with deep models.



summary_of_the_review: My research experience is on design hashing for computer vision tasks and I am familiar with work on LSH.
The paper is overall well organized. The technical contribution is the derivation of the ranking efficiency measurement, which is lower than the bar of ICLR. There are some flaws as identified in the weaknesses.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper revisits the binary hashing from Random Fourier Feature (RFF) for approximate nearest neighbor search. The authors propose a simple and effective RFF-based hashing method SignRFF and demonstrate its locality-sensitive property. They also introduce a new measure called ranking efficiency to evaluate the performance of different LSH methods theoretically. Extensive experiments on three real-life image data sets validate the effectiveness of SignRFF and the consistency of the ranking efficiency from theoretical evaluation.
main_review: Pros:
1. The authors develop a simpler hashing function for binary coding, which removes the random shifting $\xi$ compared with SQ-RFF. They further demonstrate the new hashing function is also locality-sensitive. 

2. The new proposed ranking efficiency looks interesting. The authors provide some insights from the perspective of distortion or order-preserving (actual distance in original space vs. hamming distance after hashing) to illustrate the formula of ranking efficiency. They also use extensive results to justify the correctness of their formula. 

3. The authors conduct comprehensive experiments to validate the effectiveness of SignRFF. 

4. The paper is well organized and easy to follow.

Cons:
1. The critical concern of this paper is its contribution. The new hashing scheme SignRFF and the ranking efficiency make me feel like two separate works but combine together. Both of them lack further investigation and analysis. More details can be found from Points 2 & 3 below.

2. After introducing the new hashing function SignRFF and showing its locality-sensitive property, the authors did not further investigate its property. Based on Equation 9, we can compute the new $p_1$ and $p_2$ for $\rho_1$ and $\rho_2$. Can they be amplified compared with the $p_1$ and $p_2$ from SQ-RFF? They argue the stochastic rounding introduces extra variance caused by $\xi$, so can SignRFF reduce the variance? Can it reduce a lot or a little, or depend on other factors? 

3. The authors claim the LSH efficiency ($R = \log p_1 / \log p_2$) is based on a worst-case analytical bound, but the LSH efficiency is still trendy. More investigations and comprehensive comparisons between the LSH efficiency and ranking efficiency can make it more convincing. Therefore, it is interesting to show the LSH efficiency of LSH, KLSH, SQ-RFF, and Sign-RFF with respective to $c$, $\rho$, and $\gamma$, and analyze whether the observed pattern from Figure 1 is consistent with that of the LSH efficiency. 

4. In the experiments, since different methods use different LSH functions, their computation time may be quite different. As the query response time is important, can the authors also show the recall vs query time with respect to different b values? 

Minor Comments or Typos:
1. In Figure 5, the recall vs. $\gamma$ for the data set Mnist is missing. Can the authors also show this curve in Figure 5?

2. In Page 5, the paragraph before Equation 11, "namely, the ranking accuracy, that can better compare LSHs in practice", "ranking accuracy" should be "ranking efficiency".

3. In Page 6, the $\hat{S}_y$ and $\hat{S}_x$ in Equation 12 should be $\hat{p}_y$ and $\hat{p}_x$, respectively. 



summary_of_the_review: In summary, this work looks interesting, but the concern about the contribution (details in Cons 1,2,3) justifies my current rating. I am glad to increase my rating if the authors can solve my questions. Thanks.
review_title: null

Meta-review: Thanks for your submission to ICLR.

This paper considers binary hashing schemes, and makes two related contributions.  First, it analyzes a simple extension to SQ-RFF; second, it introduces and analyzes a novel metric for ranking called ranking efficiency.  Some experiments are also performed on standard data sets.

This is very much a borderline paper, and could go either way.  I took a close look at the paper to offer my opinions in addition to the reviewers.  The paper itself is well written and seems to be correct.  I do like the simplicity of the proposed SignRFF method as well as the ranking efficiency measure.  However, the contributions are somewhat limited, and it's in an area that hasn't seen much work in the last several years (this paper mainly builds off of methods from 10+ years ago).  Further, it doesn't seem that methods such as KLSH and SignRFF are used much in practice, so I don't know if this will have substantial impact.  So while it's a reasonably interesting paper with some nice insights, I think it falls just below the acceptance threshold for me.
Decision: Reject