Deep representation learning has become one of the most widely adopted approaches for visual search, recommendation, and identification. Retrieval of such representations from a large database is however computationally challenging. Approximate methods based on learning compact representations, have been widely explored for this problem, such as locality sensitive hashing, product quantization, and PCA. In this work, in contrast to learning compact representations, we propose to learn high dimensional and sparse representations that have similar representational capacity as dense embeddings while being more efficient due to sparse matrix multiplication operations which can be much faster than dense multiplication. Following the key insight that the number of operations decreases quadratically with the sparsity of embeddings provided the non-zero entries are distributed uniformly across dimensions, we propose a novel approach to learn such distributed sparse embeddings via the use of a carefully constructed regularization function that directly minimizes a continuous relaxation of the number of floating-point operations (FLOPs) incurred during retrieval. Our experiments show that our approach is competitive to the other baselines and yields a similar or better speed-vs-accuracy tradeoff on practical datasets.
Summary
 
This paper focuses on learning a representation that facilitates efficient content-based retrieval. Although the representations that are learned from deep neural networks can contain rich information, it is computationally expensive to use those representations to perform a search for the best match. In particular, computing the Euclidean distance between a query and an instance scales linearly with the size of the representation. Prior approaches to this problem have focused either on: (1) compactifying the learned representations into another form, such as a Hamming code, in a way that preserves the identifiability of an instance; (2) resorting to approximate methods that sacrifice accurate search for efficiency.
 
To address these inconvenient trade-offs, this paper proposes an algorithm to learn a high-dimensional, sparse representation that is directly used in retrieval, instead of learning a separate, more compact representation. The novelty of this algorithm is its focus on minimizing the number of FLOPs in computing queries of instances, taking note as well of the role of the distribution of non-zero values in determining the number of FLOPs. A continuous relaxation of the equations thus derived provides the proposed algorithm. The paper notes differences between the algorithm and SDH, a recent candidate that learns a sparse, high-high dimensional hash. Based on experiments, the paper claims that the proposed algorithm yields a similar or better speed vs. recall tradeoff compared to baselines. The paper also provides additional experiments demonstrating the sparsity of the representations and the even distribution of non-zero values of the proposed regularizer.
 
Decision: accept
The algorithm is clearly and succinctly motivated from the standpoint of reducing the number of FLOPs. The presentation of the distribution that minimizes FLOPs is convincing, and there is easy-to-follow buildup into the continuous relaxation of the FLOPs minimization problem. 
The proposed algorithm is itself relatively simple (just an additional regularizer term that can be optimized with any SGD-based optimizer), compared to other methods that learn a separate representation or that use approximate nearest-neighbour search, and directly tries to address aforementioned trade-offs between efficiency of retrieval and richness of the representation. 
I found helpful the comparison both to the nearest competitor method (SDH) and the unrelaxed regularizer. The additional experiments comparing the continuous relaxation and the unrelaxed regularizer were interesting, but I found Figure 2b a little hard to understand. I also appreciated the intuition developed at the end of section 4 for how the regularizer promotos orthogonality.
The recall/time trade-off curves in figure 3 support the main empirical claim of the paper. The sparsity plots in figure 3 contributed to a broader understanding of the algorithm besides based on metrics other than accuracy. 
Nevertheless, there were some experimental presentation issues. Are errors bars possible for figs 3ac? Some evaluation metrics that are present in other papers are also missing, which might provide a more complete understanding of algorithm's advantages and disadvantages. Specifically, precision@k (Jeong and Song, 2018) and true-positive/false-positive curves (Kemelmacher-Shlizerman et. al., 2016) could help readers in making an informed algorithmic choice. It also seems that the paper could have included more comparisons to other ways of learning sparse representations (e.g., L2, top-k autoencoders, dropout), and included a broader literature review of learning sparse representations (see here: https://arxiv.org/pdf/1505.05561.pdf). 
Questions
1. Did confidence thresholds in ranking (Appendix B, re-ranking) affect the results in any way? Did it depend on the algorithm used?
Minor comments that did not affect the rating
1. Typo in figure 3; the second sentence should say "curves are produced by"
2. Typos in Appendix A
a. Lemmas 2, 5 should have X_+ instead of X in the statements
b. Second last line of proof of lemma 1 should have X_+
3. Would be helpful to have whole procedure from learning to retrieval in an algorithm box
4. Include a summary of the problem setting before section 3. It is at first a bit unclear what the problem is for newcomers
5. Add algorithm header to the retrieval algorithm presented in fig 1