Fully Understanding The Hashing Trick
Feature hashing, also known as the hashing trick, introduced by Weinberger et al. (2009), is one of the key techniques used in scaling-up machine learning algorithms. Loosely speaking, feature hashing uses a random sparse projection matrix A : R n → R m (where m n) in order to reduce the dimension of the data from n to m while approximately preserving the Euclidean norm. Every column of A contains exactly one non-zero entry, equals to either −1 or 1. Weinberger et al. showed tail bounds on Ax 2 2 . Specifically they showed that for every ε, δ, if x ∞ / x 2 is sufficiently small, and m is sufficiently large, then
These bounds were later extended by Dasgupta et al. (2010) and most recently refined by Dahlgaard et al. (2017), however, the true nature of the performance of this key technique, and specifically the correct tradeoff between the pivotal parameters x ∞ / x 2 , m, ε, δ remained an open question. We settle this question by giving tight asymptotic bounds on the exact tradeoff between the central parameters, thus providing a complete understanding of the performance of feature hashing. We complement the asymptotic bound with empirical data, which shows that the constants "hiding" in the asymptotic notation are, in fact, very close to 1, thus further illustrating the tightness of the presented bounds in practice.
The authors carry out a fine-grained analysis of locality sensitive hashing, and prove data-dependent bounds in order to provide a better understanding of how much random compression can be applied to data in realistic settings, while still preserving Johnson-Lindenstrauss guarantees on the compressed data. This is useful to know, since existing lower bounds on the projected dimension generally proceed by finding the minimal projection dimension required to compress the worst case (e.g. data lying at the vertices of the \ell_1 ball or some similarly structured scenario) but in practice observed data frequently have much more forgiving structure. The paper is interesting and, as far as I can see, correct although I did not check *all* the details thoroughly.  Although there is nothing really wrong with this paper - and I commend the authors for their work - I do however have two reasons why I think it may not be suitable for NIPS: The first is that I think this work is likely of more interest to a databases, KDD, or theoretical CS audience and therefore NIPS is perhaps not the best venue to gain this work the widest audience of interested readers. The authors clearly feel otherwise, but this is my well-intended advice. The second, more serious, concern I have is that - as a purely theoretical paper - I think that the main contributions here are really the proof techniques in the supplementary material, and I think there is not enough room to include even a reasonable sketch of these within the NIPS page limit. That is, I don't think the contributions in the manuscript are enough for NIPS but, notwithstanding my comment above, I do think that the longer paper in the supplementary paper could have been. Since NIPS papers should be self-contained I think that is a problem.  FWIW I think the supplementary version of this paper is clearly of a publishable standard at a very good venue, and believe the authors would be helping themselves by either disseminating their work as a journal paper or else submitting to a conference with a more generous page limit (e.g. ECML-PKDD 16 pages in LNCS style) or a tighter style (e.g. KDD 9 pages inc. refs. in ACM style).  Please note also that I do not object to this paper because it is theoretical: I think that theory papers are important contributions to all of the serious conferences, and personally I would be happy to see more of them. However in my own experience it is not always easy to balance providing enough detail about how the results were obtained with substantial outcomes in a short conference paper, and here I don't think the authors have found that balance.  Addendum: The authors did not address my comments in rebuttal, but checking post-review I see that the supp mat version is available on the ArXiv. I prefer that version to the NIPS version a lot, and encourage the authors (if they need any encouragement) to link to it from their NIPS submission should it be accepted. Since a guarantee of the details absent in the NIPS version in some archival form was my main concern here, I have accordingly raised my rating to "accept".