Minimizing FLOPs to Learn Efficient Sparse Representations
Authors: Biswajit Paria
Chih-Kuan Yeh
Ian E.H. Yen
Ning Xu
Pradeep Ravikumar
Barnabás Póczos
Venue:  (2020)
Keywords: sparse embeddings
deep representations
metric learning
regularization

Abstract: 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.

Published as a conference paper at ICLR 2020
MINIMIZING FLOPS TO LEARN EFFICIENT SPARSE REPRESENTATIONS
Biswajit Paria", Chih-Kuan Yehl, Ian E.H. Yen', Ning Xu², Pradeep Ravikumar',
Barnabás Póczos'
*Carnegie Mellon University, *ooffett AI, 8 Amazon
(bparia, cjyeh, pradeepr, bapoczoa (arocczza)0ccc (cs. edu, yan.yantmoffett.ai ningxuO1@gmail.com
ABSTRACT
Deep representation learning has become one of the most widely adopted ap- proaches for visual search, recommendation, and identification. Retrieval of such representations from a large database is however computationally challenging. Ap- proximate methods based learning compact representations, have been widely explored for this problem, such as locality sensitive hashing, product quantiza- tion, 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 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 carefully constructed regular- ization 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- -eeeduvs-accuracy tradeoff on practical datasets"
INTRODUCTION
Learning semantic representations using deep neural networks (DNN) is now a fundamental facet of applications ranging from visual search (Jing et al., 2015 Hadi Kiapour et al. 2015). semantic text matching (Neculoiu et al., 2016), oneshot classification (Koch et al. 2015), clustering (Oh Song et al. 2017), and recommendation (Shankar et al.) 2017). The high-dimensional dense embeddings generated from DNNs however pose a computational challenge for performing nearest neighbor search in large-scale problems with millions of instances. In particular, when the embedding dimension is high, evaluating the distance any query to all the instances in a large database is expensive, so that efficient search without sacrificing accuracy is difficult. Representations generated using DNNs typically have a higher dimension compared to hand-crafted features such as SIFT (Lowe) 2004)) and moreover are dense. The key caveat with dense features is that unlike bag-of-words features they cannot be efficiently searched through an inverted index, without approximations.
Since accurate search in high dimensions is prohibitively expensive in practice (Wang) 201 one has to typically sacrifice accuracy for efficiency by resorting to approximate methods. Addressing the problem efficient approximate Neeihst-Neighhor Search (NNS) (Jegou et al. (011) or Maximum Search (MIPS) (Shrivastava and Li 2014) is thus an active area of research, which we review in brief in the related work section. Most approaches (Charikar) 2002 Jegou et al., [201]) aim to learn compact diwen-dimensional representations that preserve distance information.
While there has been ample work on learning compact representations, learning sparse higher dimensional representations have been addressed only recently (Jeong and Song. 2018 Cao et al. 2018). As a seminal instance, Jeong and Song (2018) propose an end-to-end approach learn
Part of the work was done when BP was a research intern at Snap Inc.
'The implementation is available /ttttps:///tthihi com/bi swa wttpst//cppaaee ttsejtttsspparreeeeeeee embed

---

Published as a conference paper at ICLR 2020
sparse and high- sige-dimessional hashes, showing significant speed-up in retrieval time benchmark datasets compared to dense embeddings. This approach has also been motivated from a biological viewpoint <Li et al., 2018) by relating to fruit fly's 's olfactory circuit, thus suggesting the possibility of hashing using higher dimensions instead of reducing the dimensionality. Furthermore, as suggested by Glorot al. (20TT), sparsity can have additional advantages of linear separability and information disentangiement.
In similar vein, in this work, we propose learn high dimensional embeddings that are sparse and hence efficient to retrieve using sparse matrix multiplication operations. In contrast to compact lower- dimensional ANN-esque representations that typically lead to decreased representational power, a key facet of our higher dimensional sparse embeddings is that they can have the same representational capacity as the initial dense embeddings. The core idea behind our approach is inspired by two key observations: (i) retrieval of d (high) dimensional sparse embeddings with fraction of non-zero values on an average, can be sped up by factor of 1/p. (ii) The speed up can be further improved to a factor of 1/p" by ensuring that the non-zero values are evenly distributed across all the dimensions. This indicates that sparsity alone is not sufficient to ensure maximal speedup; the distribution of the non-zero values plays significant role well. This motivates to consider the effect of sparsity on the number of floating point operations (FLOPs) required for retrieval with an inverted index. We propose a penalty function on the embedding vectors that is continuous relaxation of the exact number of FL.OPs, and encourages an even distribution of the non-zeros across the dimensions.
We apply our approach the large scale metric learning problem of learning embeddings for facial images. Our training loss consists of a metric learning (Weinberger and Saul 2009) loss aimed at learning embeddings that mimic desired metric, and a FLOPs loss to minimize the number of operations. We perform an empirical evaluation of our approach on the Megaface dataset Saaeemmaa-------zamaan (Kemelmacher- Shlizerman et al., 2016), and show that our proposed method successfully learns nigh-dimensional sparse embeddings that are orders-of-men magnitude faster. We compare our approach to multiple baselines demonstrating an improved or similar speed- -scccurryy trade-off
The rest of the paper is organized as follows. In Section 3 we analyze the expected number of FLOPs, for which we derive an exact expression. In Section 4 we derive a continuous relaxation that can be used as a regularizer, and optimized using gradient descent. We also provide some analytical justifications for our relaxation. In Section we then compare our method on a large metric learning task showing improved speed-accuracy trade-off compared to the baselines.
2 RELATED WORK
Learning compact representations, ANN. Exact retrieval of the top-k nearest neighbours is expensive in practice for high-dimensional dense embeddings learned from deep neural networks, with practitioners often resorting to approximate nearest neighbours (ANN) for efficient retrieval.
Popular approaches for ANN include Locality sensitive hashing (LSH) (Gionis et al. 1999 Andoni
ct al. 2015 Raginsky and Lazebnik 2009) relying on random projections, Navigable small world graphs (NSW) (Malkov al. 2014) and hierarchical NSW (HNSW) (Malkov and Yashunin 2018)
based on constructing efficient search graphs by finding clusters in the data, Product Quantization (PQ) (Ge et al., 2013 Jegou et al.] 2011) approaches which decompose the original space into cartesian product of low-dimensional subspaces and quantize each of them separately, and Spectral hashing (Weiss al. 2009) which involves an NP hard problem of computing an optimal binary hash, which is relaxed to continuous valued hashes, admitting simple solution in terms of the spectrum of the similarity matrix. Overall, for compact representations and to speed up query times, most of these approaches use variety of carefully chosen data structures, such as hashes (Neyshabur and Srebro 2015| Wang et al. 2018), locality sensitive hashes (Andoni et al. 2015), inverted file structure (Jegou al. 201 Baranchuk et al. 22018). trees (Ram and Gray 2012). clustering (Auvolat et al.) 20155) quantization sketches (Jegou et al. 2011 Ning et al. 2016)) as well as dimensionality reductions based on principal component analysis and I-SNE (Maaten and Hinton 2008).
End to end ANN. Learning the ANN structure end-to-end is another thread of work that has gained popularity recently. Norouzi et al. (2012) propose to learn binary representations for the Hamming metric by minimizing a margin based triplet loss. EErin Liong et al. (2013) use the signed output of a deep neural network as hashes, while imposing independence and orthogonality conditions on the
2

---

Published as a conference paper at ICLR 2020
hash bits. Other end-to-end learning approaches for learning hashes include (Cao et al. 2016 Li et al., 2017). An advantage of end-to-end methods is that they learn hash codes that are optimally compatible to the feature representations.
Sparse representations. Sparse representations have been previously studied from various view- points. Glorot et al. (20TT) explore sparse neural networks in modeling biological neural networks and show improved performance, along with additional advantages such as better linear separability and information disentangling. |Ranzato et al. (2008 2007); Lee al. (2008) propose learning sparse features using deep belief networks. OOshausen and Field (1997) explore sparse coding with an overcomplete basis, from a neurobiological viewpoint. Sparsity in nuto-encoders have been explored by Ng et al. (20TT): Kavukcuoglu et al. (2010). Arpit et al. (2015) provide sufficient conditions to
learn sparse representations, and also further provide an excellent review of sparse autoencoders. Dropout (Srivastava et al. (2044) and number of its variants (Molchanov et al. 2017]] Park et al. 2018 Ba and Frey] 2013) have also been shown to impose sparsity in neural networks.
High-dimensional sparse representations. Sparse deep hashing (SDH) (Jeong and Song 2018 an end-to-end approach that involves starting with a pre-trained network and then performing alternate minimization consisting of two minimization steps, one for training the binary hashes and the other for training the continuous dense embeddings. The first involves computing an optimal hash best compatible with the dense embedding using min--cstt-axx-fonn approach. The second step is a gradient descent step to learn a dense embedding by minimizing a metric learning loss. A related approach, k-sparse autoencoders (Makhzani and Frey 2013) learn representations in an unsupervised manner with at most k non-zero activations. The idea of high dimensional sparse embeddings is also reinforced by the sparse-lifting approach (Li al., 2018) where sparse high dimensional embeddings are learned from dense features. The idea is motivated by the biologically inspired fly algorithm (Dasgupta et al., 2017). Experimental results indicated that sparse- sparse-lifting is an improvement both in terms of precision and speed, when compared to traditional techniques like LSS that rely on dimensionality reduction.
l regularization, lasso. The Lasso Tibshirami 1996 is the most popular approach to impose sparsity and has been used a variety of applications including sparsifying and compressing neural networks (Liu et al. [015] WWen et al. (016). The group lasso (Meier et al. (2008) is an extension of lasso that encourages all features
specified group to be selected together. Another extension, the exclusive lasso (Kong et al. 2014 Zhou et al. (2010), the other hand, is designed to select single feature in a group. Our proposed regularizer, originally motivated by idea of minimizing FLOPs closely resembles exclusive lasso. Our focus however is sparsifying the produced embeddings rather than sparsifying the parameters.
Sparse matrix vector product (SpMV). Existing work for SpMV computations include (Haffner 2006 Kudo and Matsumoto, 2003), proposing algorithms based on inverted indices. Inverted indices are however known suffer from severe cache misses. Linear algebra back-ends such as
BLAS [Blackford et al. (2022) rely on efficient cache accesses to achieve speedup. [Haffner] (2006);
Mellor-Crumney and Garvin 2004): Krotkiewski and Dabrowski (2010) propose cache efficient
algorithms for sparse matrix vector products. There has also been substantial interest in speeding up
SpMV computations using specialized hardware such as GPUs (Vazquez et al.] 2010: Vázquez et
2011). FPGAs (Zhuo and Prasannal 2005 Zhang et al. 2009). and custom hardware (Prasanna and
Morris 2007).
Metric learning. While there exist many settings for learning embeddings (Hinton and Salakhutdi nov. 2006) Kingma and Welling 2013) Kiela and Bottou, 2014) in this paper we restrict our attention to the context of metric learning (Weinberger and Saul, 2009). Some examples of metric learning losses include large margin softmax loss for CNNs (Liu et al. (016)). triplet loss (Schroff et al., 2015).
and proxy based metric loss (Movshovitz-Attias et al. 2017
3 EXPECTED NUMBER OF FLOPS
In this section we study the effect of sparsity on the expected number of FLOPs required for retrieval and derive an exact expression for the expected number of FLOPs. The main idea in this paper
3

---

Published as a conference paper at ICLR 2020
is based on the key insight that if each of the dimensions of the embedding non-zero with probability p (not necessarily independently), then it is possible to achieve a speedup up to an order of 1/p² using an inverted index the set of embeddings. Consider two embedding vectors u, Computing u" v requires computing only the pointwise product at the indices A where both us and ea non-zero. This is the main motivation behind using inverted indices and leads to the aforementioned speedup. Before we analyze it more formally, we introduce some notation.
Let D {(.;,,:)} be set of n independent training samples drawn from 2 X x y according to a distribution P. where X, denote the input and label spaces respectively. Let & {ff X' F 8 E )} be class of functions parameterized by O mapping input instances to d-dimensional embeddings. Typically, for image tasks, the function is chosen to be suitable CNN (Krizhevsky et al. 2012). Suppose X, Y P. then define the activation probability P/ = P()((X) # O), and its empirical version Pj = Li=1 [[fo( # 0).
We now show that sparse embeddings can lead to a quadratic speedup. Consider a d-dimensional sparse query vector u fo(#,,) E IRd and database of sparse vectors {u, fo( (zx()) ) R
forming a matrix D E Raxdd_ We assume that æ. (+) (i = 1.....27 .n.) are sampled independently from P. Computing the vector matrix product Dug requires looking at only the columns of D corresponding to the non-zero entries of u, given by N₂ = =iil1 ر
d, (u,); o 03. Furthermore,
in each of those columns we only need to look the non-zero entries. This can be implemented
efficiently in practice by storing the non-zero indices for each column independent lists, as depicted in Figure 2
The number of FLOPs incurred is given by,
F(D, E Σ 1-
E
11
I((
#0A Viy 0]
JENg Cnyy00
i= =1
Taking the expectation on both sides w.r.t. Tg. (+) and using the independence of the data, we get
n Σ> (((ug) (((u)))))Pp)) #)) * 0) > P(fo(X)) # 0)2
B[F(D,
(1)
where X ~ P. Since the expected number of FLOPs scales linearly with the number of vectors in the database, a more suitable quantity is the mean-FFLOPs-per-. defined as
F(fe, = =)
wn/n nl/ Σ P(fo(X), + 5=1
Σ Dj
Note that for a fixed amount of sparsity Σj= P, = dp, this is minimized when each of the dimensions are non-zero with equal probability p; p, v1 S j < d, upon which F(fe, P) dp² (so that as a regularizer, F(fo, P) will in turn encourage such a uniform distribution across dimensions). Given such a uniform distribution, compared to dense multiplication which has complexity of (dd) per row, we thus get an improvement by factor of 1 1/1² (p < 1). Thus when only p fraction of all the entries is non-zero, and evenly distributed across all the columns, we achieve a speedup of 1 1/p². Note that independence of the non-zero indices is not necessary due to the linearity of expectation in fact, features from neural network are rarely uncorrelated in practice.
FLOPs versus speedup. While FLOPs reduction is a reasonable measure of speedup on primitive processors of limited parallelization and cache memory. FLOPs is not an accurate measure of actual speedup when it comes mainstream commercial processors such as Intel's CPUs and Nvidia's GPUs, as the latter have cache and SIMD (Single-Instruction Multiple Data) mechanism highly optimized for dense matrix multiplication, while sparse matrix multiplication are inherently less tailored to their cache and SIMD design (Sohoni et al. 2019). On the other hand, there have been threads of research on hardwares with cache and para lelizlliiitiionn tailored to sparse operations that show speedup proportional to the FLOPs reduction (Han al., 2016 Parashar al. 2017). Modeling the cache and other hardware aspects can potentially lead to better performance but less generality and is left to future works.
4

---

end for Published as a conference paper at ICLR 2020
Algorithm 1 Sparse Nearest Neighbour
1: (Build Index)
2: Input: Sparse matrix
3:
for j 1....d do
Dug 4:
Init Cli t {(i, Dij) Di # Isisn)
SpMV product
5:
Stores the non-zero values and their indices
6:
D
7:
8: (Query)
9:
Input: Sparse query Ug threshold t, number of NNs
10:
Init score vector s|i] = 0, S.S siss
11:
for jo j.......d s.t. Ug1]] * 0 do
D SpMV product
12:
for (i, Cbi do
Select top-k
Top
21
13:
s[i] += tu,
G. k)
14:
end for end for
:
15:
S (1i, s(i)) sisin s
Thresholding
17:
S4 + ( in top-k indices i of S based on s[i] Using nth select from C++ STL
19: return S
Figure 2: SpMV product: The colored cells denote non-zero entries, and the arrows indicate the list structure for each of the columns, with solid arrows denoting links that were traversed for the given query. The green and grey cells denote the non-zero entries that were accessed and not accessed, respectively. The non-zero values Du, (blue) can be computed using only the common non-zero values (green). Selecting top-k: The sparse product vector then filtered using a threshold t, after which the top-k indices returned.
4 OUR APPROACH
The & regularization is the most common approach to induce sparsity. However, as we will also verify experimentally, it does not ensure an uniform distribution of the non-zeros in all the dimensions that is required for the optimal speed-up. Therefore, we resort to incorporating the actual FLOPs incurred, directly into the loss function which will lead optimal trade-off between the search time and accuracy. The FLOPs F(fo, P) being a discontinuous function of model parameters, is hard to optimize, and hence will instead optimize using continuous relaxation of it.
Denote by f D). any metric loss on for the embedding function fe. The goal in this paper is to minimize the loss while controlling the expected FLOPs F(fo. P) defined in Eqn. 2 Since the distribution P unknown, we use the samples to get an estimate of F(Jo. (Lfo.P) PP). Recall the empirical fraction of non-zero activations P3 Σー [a)));;), # 0), which converges in probability to
Py. Therefore, with a slight abuse of notation define F(fe. D) = Σt=1 P3. which is consistent estimator for F(fe, P) based the samples D. Note that F denotes either the population or empirical quantities depending on whether the functional argument P or D. We now consider the following regularized loss.
min #EE
+ D)
(3)
2(0)
for some parameter À that controls the FLOPs-accuracy tradeoff. The regularized loss poses a further hurdle, as Py and consequently F(fe. D) are continuous due the presence the indicator functions. We thus compute the following continuous relaxation. Define the mean absolute activation aj = [[]f((X)) (X),l) and its empirical version a _/2 Em= [so(a;;) which is the & norm of the activations (scaled by 1 1/n) in contrast to the to quasi norm in the FLOPPs calculation. Define the relaxations, F(s,, P) E az and its consistent estimator F(Je, (f, D) Ei_ d². We propose minimize the following relaxation, which be optimized using any off-the-shelf stochastic gradient

---

Published as a conference paper at ICLR 2020
descent optimizer.
min ege
((o, D) >F((o;
[(0)
Sparse retrieval and re-ranking. During inference, the sparse vector of query image is first obtained from the learned model and the nearest neighbour is searched a database of sparse vectors forming a sparse matrix. An efficient algorithm to compute the dot product of the sparse query vector with the sparse matrix is presented in Figure I This consists of first building a list of the non-zero values and their positions each column. As motivated in Section Bl given sparse query vector, it is sufficient to only iterate through the non-zero values and the corresponding columns. Next, a filtering step performed keeping only scores greater than a specified threshold. Top-k candidates from the remaining items are returned. The complete algorithm is presented in Algorithm [ In practice, the sparse retrieval step is not sufficient to ensure good performance. The top-k shortlisted candidates are therefore further re-ranked using dense embeddiigs done in SDH. This step involves multiplication of a small dense matrix with a dense vector. The number of shortlisted candidates & is chosen such that the dense re-ranking time does not dominate the total time.
Comparison to SDH (Jeong and Song, 2018). It instructive to contrast our approach with that of SDH (Jeong and Song 2018). In contrast the binary hashes in SDH, our approach learns sparse real valued representations. SDH uses a min-cost-mmx-flovv approach in one of the training steps, while we train ours only using SGD. During inference in SDH, a shortlist of candidates is first created by considering the examples in the database that have hashes with non-empty intersections with the query hash. The candidates are further re-ranked using the dense embeddings. The shortlist in our approach on the other hand is constituted of the examples with the top scores from the sparse embeddings.
Comparison to unrelaxed FLOPs regularizer. We provide an experimental comparison of our continuous relaxation based FLOOPs regularizer to its unrelaxed variant, showing that the performance of the two are markedly similar. Setting up this experiment requires some anal malytical simplifications based on recent deep neural network analyses. We first recall recent results that indicate that the output of batch norm layer nearly follows a Gaussian distribution (Santurkar et al.] 2018), so that in our context, we could make the simplifying approximation that fo(X); (where X P) distributed as p(Y) where Y ~ (O), (0)), p is the ReLU activation used at the neural network output. We have modelled the pre-activation the model parameters 0. We experimentally verify that this assumption holds by minimizing the KS distance (Massey Jr 1951) between the CDF of pYY) where Y ~ ~N(u, o²) and the empirical CDF of the activations. The KS distance is minimized wrt. μ4, a. Figure 3a shows the empirical CDF and the fitted CDF of p(Y) for two different architectures.
Gaussian distribution with mean and variance depending on
While o,) (1 j d) cannot be tuned independently due to their dependence on 6, in practice, the huge representational capacity of neural networks allows (0)(0) and (0) to be tuned almost independently. We consider toy setting with 2-d embeddings. For a tractable analysis, make the simplifying assumption that, for j 1,2, fo(X), is distributed as ReI.U(Y) where Y T N(1,, of), thus losing the dependence on 0.
We now analyze how minimizing the continuous relaxation F(fe, P)) compares to minimizing F(Jo, P). Note that we consider the population quantities here instead of the empirical quantities, as they are more amenable to theoretical analyses due to the existence of closed form expressions. We also consider the & regularizer as baseline. We initialize with (M1,/2, U2, 01, N2, and minimize the three quantities via gradient descent with infinitesimally small learning rates. For this contrastive analysis, we have not considered the effect of the metrie loss. Note that while the discontinuous empirical quantity F(fe, D) cannot be optimized via gradient descent, it is possible to do so for its population counterpart F(fe, P)) since it is available in closed form as a continuous function when making Gaussian assumptions. The details of computing the gradients can be found in Appendix[M
01.02) = (-1/4, 113, 1, 1).
We start with activation probabilities (p1. P2) (0.4. 0.1), and plot the trajectory taken when per- forming gradient descent, shown in Figure 3b) Without the effect the metric loss, the probabilities expected go zero as observed in the plot. It can be seen that, in contrast to the f--regularizer,

---

Published as a conference paper at ICLR 2020
MobileNet zeg
ResNet F reg
1.00
1,000
0.100
0.98
0.075
0,986
0.96
odiiy)
E, 0.000
0.980
Fifo p)
0.54
0.025
F(Je, P)
Activation CDF P(Y CDF
0.985
Activation CDF
Eg.oo.
0.92
A(Y) CDF
0.000
0.0
0.2
0.6
0.2
0.0
0.2
0.4
Pt
(a) The CDF of p(Y) fitted minimize KS distance to empirical CDF of the activations for two different architectures.
(b) The trajectory the activation probabilities when minimizing the respective regularizers.
Figure 3: Figure (a) shows that the CDF of the activations (red) closely resembles the CDF of p(Y) (blue) where Y is a Gaussian random variable. Figure (b) shows that F and F behave similarly by sparsifying the less sparser activation a faster rate when compared the & regularizer.
F and FF both tend to sparsify the less sparse activation (p1) at faster rate, which corroborates the fact that they encourage an even distribution of non-zeros.
F promotes orthogonality. We next show that, when the embeddings are normalized to have a unit norm, as typically done in metric learning, then minimizing F(fe. D) is equivalent to promoting orthogonality on the absolute values of the embedding vectors. Let ( I| 1, Vx E X, we then have the following:
2
n
D) Σ
[
Σ p.9E/1m]]
(1
(5)
7
n2
F(fe. D) is minimized when the vectors {Ifa (Txx are orthogonal. Metric learning losses aim at minimizing the interclass dot product, whereas the FLOPs regularizer aims minimizing pairwise dot products irrespective of the class, leading to tradeoff between sparsity and accuracy. This approach of pushing the embeddings apart, bears some resemblance to the idea of spreading vectors (Sablayrolles et al. 2019) where an entropy based regularizer is used to uniformly distribute the embeddings on the unit sphere, albeit without considering any sparsity. Maximizing the pairwise dot product helps in reducing FLOPs is illustrated by the following toy example. Consider set of d vectors {v, C Rd (here n = d) satisfying || = 1, E [1 dJ. Then [p.ge[ (I0,), (eyl) minimized when Up = Cp. where ep is an one-hot vector with the p th entry equal to 1 and the rest O. The FLOPs regularizer thus tends to spread out the non-zero activations in all the dimensions, thus producing balanced embeddings. This simple example also demonstrates that when the number of classes in the training is smaller or equal to the number of dimensions d, a trivial embedding that minimizes the metric loss and also achieves small number of FLOPs is fa(x) true label for æ. This is equivalent to predicting the class of the input instance. The caveat with such embeddings is that they might not be semantically meaningful beyond the specific supervised task, and will naturally hurt performance on unseen classes, and tasks where the representation itself is of interest. In order to avoid such collapse in our experiments, we ensure that the embedding dimension smaller than the number of training classes. Furthermore, as recommended by Sablayrolles et al. (2017), we perform all our evaluations unseen classes
by where is
Exclusive lasso. Also known as 21,2-, in previous works it has been used to induce competition (or exclusiveness) in features in the same group. More formally, consider d features indexed by (1...., d), and groups g [1,...,d} forming set of groups C 2(.....d)) Let denote the
Denotes the powerset of {1, (1.

---

Published as a conference paper at ICLR 2020
weight vector for a linear classifier. The exclusive lasso regularizer is defined as,
(gww)
Σ
BE9
where wg denotes the sub- suctve (wx)seg corresponding to the indices in g. G can be used to induce various kinds of structural properties. For instance G can consist of groups of correlated features. The regularizer prevents feature redundancy by selecting only a few features from each group.
Our proposed FLOPs based regularizer has the same form as exclusive lasso. Therefore exclusive lasso applied to the batch of activations, with the groups being columns of the activation matrix (and rows corresponding different inputs), is equivalent to the FLOPs regularizer. It can be said that, within each activation column, the FLOPs regularizer induces competition between different input examples for having non-zero activation.
5 EXPERIMENTS
We evaluate our proposed approach on a large scale metric learning dataset: the Megaface Saamelmacche-Shlizeeeeee et al. 2016) used for face recognition. This is much more fine grained retrieval tasks (with 85k classes for training) compared to the datasets used by byJonnn and Song (2018). This dataset also satisfies our requirement of the number of classes being orders of magnitude higher than the dimensions of the sparse embedding. As discussed in Section 4 a few number of classes during training can lead the model simply learn an encoding of the training classes and thus not generalize to unseen classes. Face recognition datasets avoid this situation by virtue of the huge number of training classes and balanced distribution of examples across all the classes.
Following standard protocol for evaluation on the Megaface dataset Keemelmmcherr-Shizeeee 2016), we train on a refined version of the MSCeleb- 1M (Guo et a 2016) dataset released by Deng et al. (2018) consisting of 1 million images spanning 85k classes. We evaluate with million distractors from the Megaface dataset and 3.5k query images from the Facescrub dataset (Ng and Winkler 2014), which were not seen during training.
et al.
Network architecture. We experiment with two architectures: MobileFaceNet (Chen et 2018 and ResNet- 101 (He et al., (016)) We use ReLU activations in the embedding layer for Mobile- FaceNet, and SThresh activations (defined below) for ResNet. The activations are Ez-normllized to produce an embedding on the unit sphere, and used to compute the Areface loss (Deng et al. 2018). We learn 1024 dimensional sparse embeddings for the & and F regularizers; and 128, 512 dimensional dense embeddings as baselines. All models were implemented in Tensorflow (Abadi eet al., (016) with the sparse retrieval algorithm implemented in C++. The re-ranking step used 512-d dense embeddings.
Activation function. In practice, having non-linear activation the embedding layer is crucial for sparsification. Layers with activations such as ReLU are easier to sparsify due to the bias parameter in the layer before the activation (linear or batch norm) which acts direct control knob to the sparsity. More specifically, ReLU(x - X) can be made more (less) sparse by increasing (decreasing) the components of A, where À is the bias parameter of the previous linear layer. In this paper we consider two types of activations: ReLU(x) = max (x. 0). and the soft thresholding operator SThresh(x) = sgn(æ) (z) max((æ) [z| 1/2, 0) (Boyd and Vandenberghe 2004). ReLU activations always produce positive values, whereas soft thresholding can produce negative values as well.
Practical considerations. In practice, setting large regularization weight from the beginning is harmful for training. Sparsifying too quickly using a large À leads to many dead activations (saturated to zero) in the embedding layer and the model getting stuck in local minima. Therefore, we use an annealing procedure and gradually increase À throughout the training using regularization weight schedule X(I) : N + that maps the training step to a real valued regularization weight. In our experiments we choose X(() that increases quadratically as X()) X(I/T)², until step / = T, where T is the threshold step beyond which X(t) = X.
Baselines. We compare our proposed F-regularizer, with multiple baselines: exhaustive search with dense embeddings, sparse embeddings using E regularization, Sparse Deep Hashing (SDH)
8

---

Published as a conference paper at ICLR 2020
MobilleNed
MobileNet.
reg (our))
0.71
rog (muss)
2.00
0.08
f
Dense 125
1.75
0.00
Dence
PCA
1.50
0.0
IVE4Q
0.62
5151
LSH
1.25
Time (ms)
Non-Zence (%)
(a) Time per query vs recall for MobileNet.
(b) Ruub vs sparsity for MobileNet.
ResNet
RoxNet
0.775
0.750
reg (ours)
0.725
F reg (ours)
Dense 128
R.s
f reg
Donse 512
PCA
IVF-PQ
2-
LSU
8D1
Time (mo)
Nom-Zaroa (%)
(c) Time per query recall for ResNet.
(d) Roub sparsity for ResNet.
Figure Figures (a) and (c) show the speed vs recall trade-off for the MobileNet and ResNet architectures respectively. The trade-off curves produced by varying the hyper-parameten of the respective approaches. The points with higher recall and lower time (top-left side of the plots) are better. The SDH baseline being out of range of both the plots is indicated using arrow. Figures (b) and (d) show the sub-optimality ratio vs sparsity plots for MobileNet and ResNet respectively. Ryub closer to 1 indicates that the non-zeros uniformly distributed across the dimensions.
(Jeong and Song 2018), and PCA, LSH, PQ applied to the 512 dimensional dense embeddings from both the architectures. We train the SDH model using the aforementioned architectures for 512 dimensional embeddings, with number of active hash bits & = 3. We use numpy (using efficient MKL optimizations in the backend) for matrix multiplication required for exhaustive search in the dense and PCA baselines. We use the CPU version of the Faiss (Johnson et al. 2017) library for LSH and PQ (we use the IVF-PQ index from Faiss).
Further details on the training hyperparameters and the hardware used can be found in Appendix B
5.1 RESULTS
We report the recall and the time-per-query for various hyperparameters of our proposed approach and the baselines, yielding trade-off curves. The reported times include the time required for re-ranking. The trade-off curves for MobileNet and ResNet are shown in Figures 4a and 4c respectively. We observe that while vanilla L regularization is an improvement by itself for some hyperparameter settings, the F regularizer is a further improvement, and yields the most optimal trade-off curve. SDH has very poor speed-accuracy trade-off, which is mainly due to the explosion in the number of shortlisted candidates with increasing number of active bits leading to an increase in the retrieval time. On the other hand, while having small number of active bits is faster, it leads to smaller recall. For the other baselines we notice the usual order of performance, with PQ having the best speed-up compared to LSH and PCA. While dimensionality reduction using PCA leads some speed-up for relatively high dimensions, it quickly wanes off as the dimension is reduced even further.
We also report the sub-optimality ratio Ryah = F(fe, ddp computed over the dataset D, where p= 1 Σ Py is the mean activation probability estimated on the test data. Notice that R.ub 2 1, and the optimal Roub = 1 is achieved when p, = p, V1 < j < d, that when the non-zeros are evenly distributed across the dimensions. The sparsity-s--subotiinaliy ResNet shown in Figures and 4c respectively We notice that the F-regularizer yields values of
plots for MobileNet and
9

---

Published as a conference paper at ICLR 2020
Rgub closer to 1 when compared to the fj-regularizer. For the MobileNet architecture notice that the & regularizer is able to achieve values of R close that of F in the less sparser region. However, the gap increases substantially with increasing sparsity. For the ResNet architecture on the other hand the & regularizer yields extremely sub-optimal embeddings in all regimes. The F regularizer is therefore able to produce more balanced distribution of non-zeros.
The sub-optimality is also reflected in the recall values. The gap in the recall values of the & and F. models is much higher when the sub- sub-optimality gap is higher, in the case of ResNet, while it is small when the sub-optimality gap is smaller as in the case of MobileNet. This shows the significance of having& balanced distribution of non-zeros. Additional results, including results without the re-ranking step and performance on CIFAR-100 can be found in Appendix
6 CONCLUSION
In this paper proposed novel approach to learn high dimensional embeddings with the goal of improving efficiency of retrieval tasks. Our approach integrates the FLOPs incurred during retrieval into the loss function as regularizer and optimizes it directly through a continuous relaxation. We provide further insight into our approach by showing that the proposed approach favors an even distribution of the non-zero activations across all the dimensions. We experimentally showed that approach indeed leads to a more even distribution when compared to the & regularizer. We compared our approach number of other baselines and showed that it has better
trade-off. Overall we were able to show that sparse embeddings can be around 50x faster compared dense embeddings without significant loss of accuracy.
Acknowledgements
We thank Hong- You Chen for helping in running some baselines during the early stages of this work. This work has been partially funded by the DARPA D3M program and the Toyota Research Institute. Toyota Research Institute ("TRI") provided funds to assist the authors with their research but this article solely reflects the opinions and conclusions of its authors and not TRI or any other Toyota entity.
REFERENCES
Martín Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, et al. Tensorflow: system for large-scale machine learning. In /2th USENIX Symposium on Operating Systems Design and Implementation (OSDI 16), pages 265-283, 2016.
Alexandr Andoni, Piotr Indyk, Thijs Laarhoven, Ilya Razenshteyn, and Ludwig Schmidt. Practical and optimal Ish for angular distance. NeurIPS, 2015.
Devansh Arpit, Yingbo Zhou, Hung Ngo, and Venu Govindaraju. Why regularized auto-encoders learn sparse representation? arXiv preprint arXiv: 1505.05661, 2015.
Alex Auvolat, Sarath Chandar, Pascal Vincent, Hugo Larochelle, and Yoshua Bengio. Clustering is efficient for approximate maximum inner product search. arXiv preprint arXiv: 1507:0500 2015.
Jimmy Ba and Brendan Frey. Adaptive dropout for training deep neural networks. In Advances in Neural Information Processing Systems, pages 3084-3092, 2013.
Dmitry Baranchuk, Artem Babenko, and Yury Malkov. Revisiting the inverted indices for billion-scale approximate nearest neighbors. In Proceedings of the European Conference on Computer Vision (ECCV), pages 202-216, 2018.
I. Susan Blackford, Antoine Petitet, Roldan Pozo, Karin Remington, R Clint Whaley, James Demmel, Jack Dongarra, Iain Duff, Sven Hammarling, Greg Henry, al. An updated set of basic linear algebra subprograms (blas). ACM Transactions on Mathematical Software, 28(2):135-151, 2002.
2002.
Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
10

---

Published as a conference paper at ICLR 2020
Yue Cao, Mingsheng Long, Jianmin Wang, Han Zhu, and Qingfu Wen. Deep quantization network for efficient image retrieval. AAAI, 2016.
Yue Cao, Mingsheng Long, Bin Liu, and Jianmin Wang. Deep cauchy hashing for hamming space retrieval. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 1229-1237, 2018.
Moses Charikar. Similarity estimation techniques from rounding algorithms. In Proceedings of the thiry-fourth anmual ACM symposium on Theory of computing, pages 380-388. ACM, 2002.
Sheng Chen, Yang Liu, Xiang Gao, and Zhen Han. Mobilefacenets: Efficient cnns for accurate real-time face verification on mobile devices. arXiv preprint arX4: 2018.
Sanjoy Dasgupta, Charles F Stevens, and Saket Navlakha. A neural algorithm for fundamental computing problem. Science, 2017.
Jiankang Deng, Jia Guo, and Stefanos Zafeiriou. Areface: Additive angular margin loss for deep face recognition. arXiv preprint arXiv:1801.0700 2018.
Venice Erin Liong, Jiwen Lu, Gang Wang, Pierre Moulin, and Jie Zhou. Deep hashing for compact binary codes learning. CVPR, 2015.
Tiezheng Ge, Kaiming He, Qifa Ke, and Jian Sun. Optimized product quantization for approximate nearest neighbor search. CVPR, 2013.
Aristides Gionis, Piotr Indyk, Rajeev Motwani, et al. Similarity search high dimensions via hashing. VLDB, 1999.
Xavier Glorot, Antoine Bordes, and Yoshua Bengio. Deep sparse rectifier neural networks. In Proceedings of the fourteenth international conference artificial intelligence and statistics, pages 315-323, 2011.
Yandong Guo, Lei Zhang, Yuxiao Hu, Xiaodong He, and Jianfeng Gao. OSS-Cele-1MM M: A dataset and benchmark for large scale face recognition. European Conference on Computer Vision. Springer, 2016.
M Hadi Kiapour, Xufeng Han, Svetlana Lazebnik, Alexander C Berg. and Tamara L Berg. Where buy it: Matching street clothing photos in online shops. In Proceedings of the IEEE international conference on computer vision, pages 3343-3351, 2015.
Patrick Haffner. Fast transpose methods for kemel learning on sparse data. In Proceedings of the 23rd international conference on Machine learning, pages 385-392. ACM, 2006.
Song Han, Xingyu Liu, Huizi Mao, Jing Pu, Ardavan Pedram, Mark Horowitz, and William Dally. Fie: efficient inference engine compressed deep neural network. In 2016 ACM/IEEE 43rd Annual International Symposium on Computer Architecture (ISCA), pages 243-254. IEEE, 2016.
Kaiming Hc, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Identity mappings in deep residual networks. In European conference computer vision, pages 630 630.645. Springer, 2016.
Geoffrey E Hinton and Ruslan Salakhutdinov. Reducing the dimensionality of data with neural networks. science, 313(5786):504-507 2006..
Gary B Huang, Marwan Mattar, Tamara Berg, and Eric Learned-Milee Labeled faces in the wild: A database forstudying face recognition in unconstrained environments. In Workshop on faces in Real-Life Images: detection, alignment, and recognition, 2008
Herve Jegou, Matthijs Douze, and Cordelia Schmid. Product quantization for nearest neighbor search. TPAMI, 2011.
Yeonwoo Jeong and Hyun Oh Song. Efficient end-to-end learning for quantizable representations. ICMI,, 2018.
11

---

Published as a conference paper at ICLR 2020
Yushi Jing, David Liu, Dmitry Kislyuk, Andrew Zhai, Jiajing Xu, Jeff Donahue, and Sarah Tavel. Visual search at pinterest. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 1889-1898. ACM, 2015.
Jeff Johnson, Matthijs Douze, and Hervé Jégou. Billion-scale similarity search with gpus, arXiv preprint vrXiv:/702.0073:: 2017.
Koray Kavukeuoglu, Marc' Aurelio Ranzato, and Yann LeCun. Fast inference in sparse coding algorithms with applications object recognition. arXiv preprint arXiv: 3467.4477 2010.
Ira Semellmacher-Shlizemmnne Steven Seitz, Daniel Miller, and Evan Brossard. The megaface benchmark: million faces for recognition at scale. CVPR, 2016.
Douwe Kiela and Léon Bottou. Learning image embeddings using convolutional neural networks for improved modti- semantics. In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 36-45, 2014.
Diederik P Kingma and Max Welling. Auto-encoding variational bayes. arXiv preprint arXiv: 14, 2013.
Gregory Koch, Richard Zemel, and Ruslan Salakhutdinov. Siamese neural networks for one-shot image recognition. In ICML Deep Learning Workshop, volume 2, 2015.
Deguang Kong, Ryohei Fujimaki, Ji Liu, Feiping Nie, and Chris Ding. Exclusive feature learning on arbitrary structures via 21,2-norm. In Advances in Neural Information Processing Systems, pages 1655-1666 2014.
Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. Cifar- 10 and cifar- 100 datasets. URI: https://www. toronto. edu/kriz/cifar. html, 6, 2009.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolu- tional neural networks. NeurlPS, 2012.
Marcin Krotkiewski and Marcin Dabrowski. Parallel symmetric sparse matrix-vector product on scalar multi-core cpus. Parallel Computing, 36(4):181-198, 2010.
Taku Kudo and Yuji Matsumoto. Fast methods for kernel-based text analysis. In Proceedings of the 41st Annual Meeting on Association for Computational Linguistics- Volume 1, pages 24-31. Association for Computational Linguistics, 2003.
Honglak Lee, Chaitanya Fkanadham, and Andrew Y Ng. Sparse deep belief net model for visual area v2. In Advances in neural information processing systems, pages 873-880, 2008
Qi Li. Zhenan Sun, Ran He, and Tieniu Tan. Deep supervised discrete hashing. NeurlPS, 2017.
Wenye Li, Jingwei Mao, Yin Zhang, and Shuguang Cui. Fast similarity search via optimal sparse lifting. NeurlPS, 2018
Baoyuan Liu, Min Wang, Hassan Foroosh, Marshall Tappen, and Marianna Pensky. Sparse convolu- tional neural networks. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 806-814, 2015.
Weiyang Liu, Yandong Wen, Zhiding Yu, and Meng Yang. Large-marght softmax loss for convolu- tional neural networks. In ICML, volume 2, page 7, 2016.
David G Lowe. Distinctive image features from ceale-invariant keypoints. International journal of computer vision, 2004.
Laurens van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of machine learning research, 9NNv)):579-2265,, 2008
Alireza Makhzani and Brendan Frey. K-sparse autoencoders. arXiv preprint arXiv:1312.5663. 2013.
Yury Malkov, Alexander Ponomarenko, Andrey Logvinov, and Vladimir Krylov. Approximate nearest neighbor algorithm based on navigable small world graphs. Information Systems, 2014.
12

---

Published as a conference paper at ICLR 2020
Yury A Malkov and Dmitry A Yashunin. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. TPAMI, 2018.
Frank J Massey Jr. The kolmogorov-smminoy test for goodness of fit. Journal of the American statistical Association, 46(253):68-78, 1951.
Lukas Meier, Sara Van De Geer, and Peter Bühlmann. The group lasso for logistic regression. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 70(1):53-71, 2008.
John Mellor- Sallor-Crummey and John Garvin. Optimizing sparse matrix-vector product computations using unroll and jam. The International Journal of High Performance Computing Applications, 18 (2):225-255) 2266, 2004.
Dmitry Molchanov, Arsenii Ashukha, and Dmitry Vetrov. Variational dropout sparsifies deep neural networks. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pages 2498-2507. JMLR. org. 2017.
Stylianos Moschoglou, Athanasios Papaioannou, Christos Sagonas, Jiankang Deng, Irene Kotsia, and Stefanos Zafeiriou. Agedb: the first manually collected, in-the-wild age database. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition Workshop, 2017.
Yair Movshovitz-Attias, Alexander Toshev, Thomas K Leung, Sergey Ioffe, and Saurabh Singh. No fuss distance metric learning using proxies. arXiv preprint arXiv: 170.007444, 2017.
Paul Neculoiu, Maarten Versteegh, and Mihai Rotaru. Learning text similarity with siamese recurrent networks. In Proceedings of the Ist Workshop on Representation Learning for NLP, pages 148-157, 2016.
Behnam Neyshabur and Nathan Srebro. On symmetric and asymmetric Ishs for inner product search. In International Conference on Machine Learning, pages 1926-1934. 2015.
Andrew Ng et al. Sparse autoencoder. CS294A Lecture notes, 72(201 1): 2011. 2011.
Hong-Wor Wei Ng and Stefan Winkler. A data-driven approach to cleaning large face datasets. In Image Processing (ICIP), 2014 IEEE International Conference IEEE, 2014.
Qingqun Ning. Jianke Zhu, Zhiyuan Zhong, Steven CH Hoi, and Chun Chen. Scalable image retrieval by sparse product quantization. IEEE Transactions Multimedia, 19(3)5586-597 2016.
Mohammad Norouzi, David Fleet, and Ruslan R Salakhutdinov. Hamming distance metric learning. NeurIPS, 2012.
Hyun Oh Song, Stefanie Jegelka, Vivek Rathod, and Kevin Murphy. Deep metric learning via facility location. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pages 5382-5390, 2017.
Bruno A Olshausen and David Field. Sparse coding with overcomplete basis A strategy employed by v1? Vision research, (1123)33311-322) 1997.
Angshuman Parashar, Minsoo Rhu, Anurag Mukkara, Antonio Puglielli, Rangharajan Venkatesan, Brucek Khailany, Joel Emer, Stephen W Keckler, and Willian J Dally. Scnn: An accelerator for compressed-sparse convolutional neural networks. 2017 ACM/IEE 44th Annual International Symposium Computer Architecture (ISCA), pages 27-40. IEEE, 2017.
Sungrae Park, JunKeon Park, Su-Jin Shin, and II-Chul Moon. Adversarial dropout for supervised and semi-supervised learning. In Thirty-Second AAAI Conference Artificial Intelligence, 2018.
Viktor K Prasanna and Gerald R Morris. Sparse matrix computations on reconfigurable hardware. Computer, 40(3):58-666 64, 2007.
Maxim Raginsky and Svetlana Lazebnik. Locality-sensitive binary codes from shift-invarian kernels. NeurIPS, 2009.
13

---

Published as a conference paper at ICLR 2020
Parikshit Ram and Alexander G Gray. Maximum inner- annerpproduct search using cone trees. In Proceed- ings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 931-939. ACM, 2012.
Mare' Aurelio Ranzato, Christopher Poultney, Sumit Chopra, and Yann Cun. Efficient learning of sparse representations with an energy-based model. In Advances in neural information processing systems, pages 1137-1144, 2007.
Marc' Aurelio Ranzato, Y-Lan Boureau, and Yann L Cun. Sparse feature learning for deep belief networks. In Advances in neural information processing systems, pages 1185-119,, 2008.
Alexandre Sablayrolles, Matthijs Douze, Nicolas Usunier, and Hervé Jégou. How should we evaluate supervised hashing? In 2017 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 1732-1736. IEEE, 2017.
Alexandre Sablayrolles, Matthijs Douze, Cordelia Schmid, and Hervé Jégou, Spreading vectors for similarity search. ICLR, 2019.
Shibani Santurkar, Dimitris Tsipras, Andrew llyas, and Aleksander Madry. How does batch nor- malization help optimization? In Advances in Neural Information Processing Systems, pages 2483-2493, 2018.
Florian Schroff, Dmitry Kalenichenko, and James Philbin. Facenet: A unified embedding for face recognition and clustering, In Proceedings of the IEEE conference on computer vision and pattern recognition, pages
2015.
Devashish Shankar, Sujay Narumanchi, HA Ananya, Pramod Kompalli, and Krishnendu Chaudhury. Deep learning based large scale visual recommendation and search for e-commerce. arXiv preprint 17Xiv:170..02344, 2017.
Anshumali Shrivastava and Ping Li. Asymmetric Ish (alsh) for sublinear time maximum inner product search (mips). Advances in Neural Information Processing Systems, pages 2321-2329, 2014.
Nimit Sharad Sohoni, Christopher Richard Aberger, Megan Leszczynski, Jian Zhang, and Christopher Ré. Low-memory neural network training: A technical report. arXiv preprint 1904. 10631, 2019.
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: a simple way to prevent neural networks from overfitting. The journal of machine learning research, 1599:1199-11988 2014.
Robert Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society: Series B (Methodological), 58(1):267-295 1996.
Francisco Vazquez, Ortega, José-Jesús Fernández, and Ester M Garzón. Improving the performance of the sparse matrix vector product with gpus. In 2010 10th IEEE International Conference on Computer and Information Technology, pages 1146-1151. IEEE, 2010.
Francisco Vázquez, José-Jesús Fernández, and Ester M Garzón. A new approach for sparse matrix vector product on nvidia gpus. Concurrency and Computation: Practice and Experience, 23(8): 815-826, 2011.
Jingdong Wang, Ting Zhang, Nicu Sebe, Heng Tao Shen, et al. A survey learning hash. IEEE transactions on pattern analysis and machine intelligence, 40(4):769-790, 2018.
Xueyi Wang. A fast exact k-nearest neighbors algorithm for high dimensional search using k-means clustering and triangle incquality. In Neural Networks (IJCNN), The 2011 International Joint Conference on, pages 1293-1299. IEEE, 2011.
Kilian Q Weinberger and Lawrence K Saul. Distance metric learning for large margin nearest neighbor classification. Journal of Machine Learning Research, 10(Feb):207-22 2009.
Yair Weiss, Antonio Torralba, and Rob Fergus. Spectral hashing. NeurlPS, 2009.
14

---

Published as a conference paper at ICLR 2020
Wei Wen, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. Learning structured sparsity in deep neural networks. In Advances in neural information processing systems, pages 2074-2082, 2016.
Yan Zhang, Yasser H Shalabi, Rishabh Jain, Krishna K Nagar, and Jason D Bakos. Fpga vs. gpu for sparse matrix vector multiply. In 2009 International Conference on Fiold-Programmable Technology, pages 255-262. IEEE, 2009.
Yang Zhou, Rong Jin, and Steven Chu-Hong Hoi. Exclusive lasso for multi-task feature selection. In Proceedings of the Thirleenth International Conference on Artificial Intelligence and Statistics, pages 988-995, 2010.
Ling Zhuo and Viktor K Prasanna. Sparse matrix multiplication on fpgas. In Proceedings of the 2005 ACM/SIGDA 13th international symposium field-programmabbl gate arrays, pages 63-74. ACM, 2005.
15

---

Published as a conference paper at ICLR 2020
Appendix
A GRADIENT COMPUTATIONS FOR ANALYTICAL EXPERIMENTS
As described in the main text, for purposes of an analytical toy experiment, we consider simplified setting with 2-d embeddings with the jth (j = 1,2) activation being distributed as (Yz)+ ReI.U(Y,) where Y, ~ ()) We assume M4j S 0. which is typical for sparse acti- vations (p, < 0.5). Then the three compared regularizers are F(po, P) Ej=1
0)2.
F(pe, P) ブ +1,, and (po, P) = EE- =[ Computing the regularizer gra- dients thus boils down to computing the gradients of P( > (),,) and [ as provided in the following lemmas. We hide the subscript j for brevity, as computations are similar for all j.
Lemma 1.
12
+ 11 (1 + (-
E[Y+]
exp
(6)
22T
20
and,
P(Y > 0) 11 $
where & denotes the cdf of the Gaussian distribution.
Proof of Lemmal 7
The proof is based on standard Gaussian identities.
E[
x
exp
(x (r-m)²
20
dx =
V2T0²
x +
1
exp
2
x² dx
x²
x²
exp
dr +
exp
dr
2TTT2
20
-H V/TT222
20²
pp
112
11
exp
+ 1
- +
2TT
20
1000 00
(- (x
(-(r--)²)
11)
600
x²
P(Y; > 0) =
exp
dx
exp
dx
V2T02
20
u//
V2x
2
(-#)
-1 1b
Lemma 2.
0
11
112
P(Y+ > 0)
θμ $
/TT
2T
exp
20
(8)
112
11
PP > 0) = +
exp
(9)
0o
Zo
r² /2T/2T
20
Proof of Lemma 2 Follows directly from the statement by standard differentiation.
n
Lemma 3.
0n E[ = 1 - $ (--
(10)
412
E[ =
exp
(11)
do
/xx
20
Proof of Lemma
i
(- 112
θ
11 (1 o (-
Φ 11
(-M
B
exp
+
Dp
ov 2m
20
Op
16

---

Published as a conference paper at ICLR 2020
where the last step follows from Lemma
[[++]
exp
(-
112
+
exp
1
1
+
(-
Oo
20
2T
20
do
1
112
exp
2T
2
where the last step follows from Lemma
Lemma 4.
0
B[Y_]² 2E[Y+] (1 (1-8
(1-((=))
(12)
0yc
0
1
112
B[Y_]² 22|
exp
(13)
0o
2nx
26²
Proof of Lemma
Follows directly from Lemma 3
Lemma 5.
112
pp
P(Y+ > 0)2 2P(Y, > 0)
2V
exp
2r
(14)
0
112
P(Y 0)2 -P 0) Oo
exp
(15)
02
2
20
Proof of Lemma
Follows directly from Lemma
B EXPERIMENTAL DETAILS
All images were resized size 112 x 112 and aligned using a pre-trained aligner For the Arcloss function, we used the recommended parameters of margin m = 0.5 and temperature trained our models on 4 NVIDIA Tesla V-100 GPUs using SGD with a learning rate of 0.001, momentum of 0.9. Both the architectures were trained for total of 230k steps, with the learning rate being decayed by a factor of 10 after 170k steps. We use batch size of 256 and 64 per GPU for MobileFaceNee for ResNet respectively.
64. We
Pre-training in SDH is performed in the same way as described above. The hash learning step is trained on single GPU with a learning rate of 0.001. The ResNet model is trained for 200k steps with batch size of 64, and the MobileFaceNet model is trained for 150k steps with batch size of 256. We set the number of active bits l = 3 and pairwise cost of p 0.1.
prreet-prraeters for MobileNet models.
1. The regularization parameter À for the F regularizer was varied as 200, 300, 400, 600.
2. The regularization parameter À for the regularizer was varied as 1.5, 2.0, 2.7, 3.5.
3. The PCA dimension is varied as 64, 96, 128, 256.
4. The number of LSH bits were varied as 512, 768, 1024, 2048, 3072.
5. For IVF-PQ from the faiss library, the following parameters were fixed: n1ist=4095, M=64, nbit=8, and nprobe was varied as 100, 150, 250, 500, 1000.
17

---

Published as a conference paper at ICLR 2020
0.5
0.77
Becallat
0.0
PomeNee F
BogNNe no I.I
Bessies
BonNie b BR
ModaluNa F
ModeloNee & no RE
0.4
MobiloNee
MobiieNe: DT
6--01
Time
Figure 5: Time vs Recall@) plots for retrieval with and without re-ranking. Results from the same model and regularizer have same colors. Diamonds (0) denote results with re-ranking, and triangles (A) denote results without re-ranking.
for ResNet baselines.
1. The regularization parameter À for the J regularizer was varied as 50, 100, 200, 630.
2. The regularization parameter À for the & regularizer varied 2.0, 3.0, 5.0, 6.0.
3. The PCA dimension is varied 48, 64, 96, 128.
4. The number of LSH bits were varied 256, 512, 768, 1024, 2048.
5. For IVF-PQ, the following parameters were the same in MobileNet: nlist=4096, M-64, n nprobe was varied as 50, 100, 150, 250, 500, 1000.
Selecting top-k. We use the following heuristic create the shortlist of candidates after the sparse ranking step. We first shortlist all candidates with a score greater than some confidence threshold. For our experiments we set the confidence threshold be equal 0.25. the size of this shortlist is larger than k. it is further shrunk by consider the top & scorers. For all our experiments we set 1000. This heuristic avoids sorting the whole array, which can bottleneck this case. The parameters are chosen such that the time required for the re-ranking step does not dominate the total retrieval time.
Hardware.
1. All models were trained 4 NVIDIA Tesla V-100 GPUs with 16G of memory.
2. System Memory: 256G.
3. CPU: Intel(R) Xeon(R) CPU E5-2686 v4 @ 2.30GHz.
4. Number of threads: 32.
5. Cache: Lldd cache 32K, Lli cache 32K, L2 cache 256K, L3 cache 46080K.
All timing experiments were performed on a single thread in isolation.
C ADDITIONAL. RESULTS
C.1 RESULTS WITHOUT RE-RANKING
Figure shows the comparison of the approaches with and without re-ranking. We notice that there significant dip in the performance without re-ranking with the gap being smaller for ResNet with FLOPss regularization. We also notice that the FLOPs regularizers has a better trade-off curve for the re-ranking setting well.
18

---

Published as a conference paper at ICLR 2020
AGEDB NetileNet.
AGEDB ResNet
Damoe 612
Detne 512
G p
6 p
6 3,025
6 0.021
6 p A015
6 p 0.030
6 p
6 p
0.4
0.4
F p 2005
8 p 0.028
F p 3.02
F p 0.024
012
0.2
F p 2012
p 0.055
F p 2017
F p 0.051
0.0
0.0
10
10
10
11
10
30
10
10P
FPR
PFR
LFW MobileNos
LFW RosNes
Deuse 512
Danse 512
p.p=
0.6
6 p- 3.025
0.0
4 0.021
G p- 2005
6 p 0.000
6 p
6 P
11.4
8 p- 2015
0.4
8 p 02008
8 p- 3.22
8 p 0.001
0.2
0.2
F p 3008
5 y 0.055
100
p 200T
0.0
8 p 0.081
10
10
10-1
10P
10" 10
10"
10F
FPR
FPR
Figure 6: FPR-TPR curves. The & curves all shown in shades of red, where the FLOPs curves are all shown in shades of blue. The probability of activation is provided in the legend for comparison. For curves with similar probability of activation p, the FLOPs regularizer performs better compared to f,, thus demonstrating that the FLOPs regularizer learns richer representations for the same sparsity.
C.2 FPR AND TPR CURVES
In the main text we have reported the recall@1 1 which standard face recognition metric. This however is not sufficient to ensure good face verification performance. The goal in face verification to predict whether two faces are similar or dissimilar, A natural metric in such a scenario the FPR-TPR curve. Standard face verification datasets include LFW (Huang et al. 2008) and AgeDB (Moschoglou et al. 2017). We produce embeddings using our trained models, and use them to compute similarity scores (dot product) for pairs of images. The similarity scores are used compute the FPR-TPR curves which are shown in Figure 6 We notice that for curves with similar probability of activation p. the FLOPs regularizer performs better compared to e, This demonstrates the efficient utilization of all the dimensions in the case of the FLOPs regularizer that helps in learning richer representations for the same sparsity.
We also observe that the gap between sparse and dense models smaller for ResNet, thus suggesting that the ResNet model learns better representations due increased model capacity. Lastly, we also note that the gap between the dense and sparse models is smaller for LFW compared to AgeDB, thus corroborating the general consensus that LFW is relatively easier dataset.
C.3 CIFAR- 100 RESULTS
We also experimented with the Cifar- 100 dataset (Krizhevsky et al. 2009) consisting of 60000 examples and 100 classes. Each class consists of 500 train and 100 test examples. We compare the & and FLOPs regularized approaches with the sparse deep hashing approach. All models were trained using the triplet loss (Schroff et al. 2015) and embedding dim d 64. For the dense and DH baselines, no activation was used on the embeddings. For the E and FLOPs regularized models we used the SThresh activation. Similar to Jeong and Song (2018), the train-test and test-test precision values have been reported in Table [ Furthermore, the reported results are without re-ranking. Cifar- 100 being small dataset, we only report the FL.OPs-ee--rww, time measurements can be
19

---

Published as a conference paper at ICLR 2020
Train
Test
Model
F
prec@4
prec@ 16
prec
prec 16
Dense
64
61.53
61.26
57.31
56.95
SDH k:
1.18
62.29
61.94
57.22
55.87
SDH k
3.95
60.93
60.15
55.98
54.42
SDH &
8.82
60.80
59.96
55,81
54.10
F no re-ranking
0.40
61.05
61.08
55.23
55.21
& re-ranking 0..47
60.50
60.17
54.32
54.96
Table I: Cifar-100 results using triplet loss and embedding size 64. For l and F models, no re-ranking was used. F is used denote the FLOPs-per-row' (lower better). The SDH results have been reported from the original paper.
misleading. In our experiments, we achieved slightly higher precisions for the dense model compared to (Jeong and Song 2018). We notice that our models use less than 50% of the computation compared SDH, albeit with a slightly lower precision.
20


Reviews:
[{"review_id": "HyeUOAxaYH", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary\n \nThis 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.\n \nTo 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.\n \nDecision: accept\n\nThe 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. \n\nThe 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. \n\nI 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.\n\nThe 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. \n\nNevertheless, 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). \n\nQuestions\n1. Did confidence thresholds in ranking (Appendix B, re-ranking) affect the results in any way? Did it depend on the algorithm used?\n\nMinor comments that did not affect the rating\n1. Typo in figure 3; the second sentence should say \"curves are produced by\"\n2. Typos in Appendix A\na. Lemmas 2, 5 should have X_+ instead of X in the statements\nb. Second last line of proof of lemma 1 should have X_+\n3. Would be helpful to have whole procedure from learning to retrieval in an algorithm box\n4. Include a summary of the problem setting before section 3. It is at first a bit unclear what the problem is for newcomers\n5. Add algorithm header to the retrieval algorithm presented in fig 1\n\n\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "BkxR8nw95S", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper reads well, with intriguing ideas that challenge the ‘dense’ approach to DNNs, excellent thought experiments and convincing experiments.\n\nThe reviewer is neither an expert in face verification and in K-NN retrieval algorithms but has a solid experience in sparse ML algorithms and group lasso algorithms.\n\nIn this respect, the algorithms proposed in this paper represent an excellent extension of existing sparse algorithms that go against the current trend of focusing on compact dense representations because this is what GPUs handle best.\n\nClarity: an excellent introduction (appreciated by a reviewer not up-to-date in the topic) introduces representation learning for retrieval, though says little about the sparse multiplication state-of-the-art or face verification.  The rest of the paper reads very well (I had to dig deep to find some clarifications in detailed comments). For lack of space, one has to through quite few references to fully understand the experiments.\n\nQuality: there are only few equations in this paper, but they rely on excellent notation. The algorithm is also well formulated. What strikes me as very good are the ‘thought experiments’ that suggest (rather than prove) that the approach is well grounded: the end of section 4 is excellent\n\nOriginality and significance: working on sparse representations is quite ‘original’ now, especially as they are so GPU-unfriendly (I note the sparse algorithm is implemented in C++, and am looking forward to the code release). I hope the excellent results reported in this paper will incite others to revisit them. 15 years ago, such as paper would have been less original. The sparse vector sparse matrix product algorithm is well known and has been used in ML publications before, for instance:\n-\tHaffner, ICML 2006, “Fast Transpose Methods for Kernel Learning on Sparse Data” \n-\tKudo and Matsumoto 2003 “Fast methods for kernel-based text analysis”\nWhat seems to be original is the algorithm to balance sparsity probabilities. The reviewer is well aware that a single non sparse column can kill the performance of the sparse matrix multiplication algorithm, and this is probably the main reason this algorithm has not found broad usage. The derivation and the connection to group and exclusive Lasso are excellent.\n\nDetailed comments:\n-\tpage 5 “where we suppress the dependency of Mu and Sigma”. How do you do that?\n-\tPage 7 “The analysis in figure 2 follows similarly for Stresh”.  Probably more explanation is needed here. Replacing Relu with a sum of Relus over affine transforms of the Gaussian variable is a complex operation:  how does it keep the same curves?\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "BJejmeERKS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes to learn sparse representation in neural networks for retrieval in large database of vectors. Such sparse representation, when the fraction of non-zeros is high, can be computed using sparse matrix multiplication, or variants of inverted index scoring and lead to potentially lower FLOPs needed. This paper proposes to induce sparsity by adding a regularization term, which counts the expected number of FLOPs needed for sparse scoring.\n\nThe final experiments were done on Megaface dataset, where there are 1M distrators and accuracy is measured in Recall@1. The sparse embedding approach is combined with a dense re-ranking stage, and the speed-recall trade is compared to the pure dense approaches (such as using baselines such as FAISS’s IVF-PQ, LSH or SDH). The authors’ evaluation showed that, the performance of FLOPs regularized embedding is better than L1 regularized sparse embedding, or applying IVF-PQ directly to dense embeddings.\n\nPros:\n- The topic of learning sparse embeddings is of great interests. As far as I know, many researchers attempted and there was not an agreement. For example, https://arxiv.org/pdf/1904.10631.pdf [1] claimed \"Using sparse operations reduces the number of FLOPs, as the zero entries can be ignored. However, in general, sparsity leads to irregular memory access patterns, so it may not actually result in a speedup;\" This has been my experience as well. The authors’ embedding seems to be much more sparse (<5% non-zeros) than the sparse embeddings from other approaches and thus works better.\n\n- The formulation is simple and intuitive - it appears easy enough to plug into a variety of embedding architectures (potentially all embeddings, NLP, CV, Audio).\n\nCons:\n- The learned sparse embedding system still requires training a separate dense embedding for re-ranking, so essentially is a hybrid approach. One cannot simply \"get rid of the dense\". Ideally one would hope to not need two inference runs (for sparse and dense) and keep two database (sparse and dense). Maybe the author can report how sparse embedding performs on its own.\n\n- It is widely known that inverted index is not FLOPs bound, as its FLOPs utilization in inverted index is typically low. Inverted index is almost always dominated by random memory accesses and thus ideally the regularizer should be modelling after cache miss / memory access pattern instead of FLOPs. I’d like to see authors gave more discussion on these topics instead of taking a FLOPs centric view (which is not true for inverted index).\n\n- For comparison dense ANN, Faiss’s IVF-PQ is a relatively dated pipeline. It would be good to see how what the curve would look like for other dense technique such as HNSW [2] which performs better than IVF-PQ on http://ann-benchmarks.com/. Also dense ANN can also greatly benefit from the use of batching, which is not considered for this paper. \n\n- Finally, I recommend the authors perform additional experiments on other datasets. As the authors suggested, sometimes sparse embedding learning risks collapse to predicting the classes. The unseen face queries avoid this problem to some extent. But I still worry that the Megaface task somehow allow representation to be much more sparse than other NLP/CV tasks. For example, authors can try BERT tasks with sparse embedding. It would be much more convincing to see this approach generalizes across many tasks.\n\n===\nOverall, I think this is a nice paper which takes a good step to improve the effectiveness of sparse embeddings over existing methods such as simple L1 regularization. However, with the need of training separate dense embeddings, and the fact that experiments were conducted only on 1 tasks with relatively weak ANN baseline, I’d lean towards rejection.\n\n[1] Low-Memory Neural Network Training: A Technical Report\n[2] Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies methods for using weight sparsification to reduce the computational load of network inference.  While there is not absolute consensus on whether this paper should be accepted, one of the main criticisms of this paper is that sparse compute is not always realistic or efficient on a GPU.  While this may be true of the current SOTA in hardware, emerging computing platforms and CPU libraries may handle sparse networks quite well.  For this reason, I am willing to down-weight this criticism. Based on the remaining comments, this paper has the merit to be accepted, even if it is a bit forward looking in terms of the hardware platforms it targets.


Decision: Accept (Poster)