New Loss Functions for Fast Maximum Inner Product Search
Authors: Ruiqi Guo
Quan Geng
David Simcha
Felix Chern
Phil Sun
Sanjiv Kumar
Venue:  (2020)

Abstract: Quantization based methods are popular for solving large scale maximum inner product search problems. However, in most traditional quantization works, the objective is to minimize the reconstruction error for datapoints to be searched. In this work, we focus directly on minimizing error in inner product approximation and derive a new class of quantization loss functions. One key aspect of the new loss functions is that we weight the error term based on the value of the inner product, giving more importance to pairs of queries and datapoints whose inner products are high. We provide theoretical grounding to the new quantization loss function, which is simple, intuitive and able to work with a variety of quantization techniques, including binary quantization and product quantization. We conduct experiments on public benchmarking datasets \url{http://ann-benchmarks.com} to demonstrate that our method using the new objective outperforms other state-of-the-art methods. We are committed to release our source code.

Under review as a conference paper at ICLR 2020
NEW Loss FUNCTIONS FOR FAST MAXIMUM INNER PRODUCT SEARCH
Anonymous authors Paper under double-blind review
ABSTRACT
Quantization based methods are popular for solving large scale maximum inner product search problems. However, in most traditional quantization works, the ob- jective is minimize the reconstruction error for datapoints to be searched. In this work, we focus directly on minimizing error in inner product approximation and derive a new class of quantization loss functions. One key aspect of the new loss functions is that we weight the error term based on the value of the inner product, giving more importance to pairs of queries and datapoints whose inner products are high. We provide theoretical grounding to the new quantization loss function, which is simple, intuitive and able work with variety of quantization techniques, including binary quantization and product quantization. We conduct experiments on public benchmarking datasets http:: //ann- ben com to demon- strate that our method using the new objective outperforms other state-of-the-art methods. We are committed to release our source code.
INTRODUCTION
Maximum inner product search (MIPS) has become popular paradigm for solving large scale classi- fication and retrieval tasks. For example, in recommendation systems, user queries and documents are embedded into dense vector space of the same dimensionality and MIPS is used to find the most relevant documents given a user query (Cremonesi et al.) 2010). Similarly, in extreme classification tasks (Dean et al., 2013), MIPS is used predict the class label when a large number of classes, often on the order of millions or even billions are involved. Lately. MIPS has also been applicd to training tasks such as scalable gradient computation in large output spaces (Yen et al. 2018), efficient sampling for speeding up softmax computation (Mussmann and Ermon 2016) and sparse updates in end-to-end trainable memory systems (Pritzel et al. 2017).
To formally define Maximum Inner Product Search (MIPS) problem, consider database X {z; )==12..... with N datapoints, where each datapoint x; E Rd in a d-dimensional vector space. In the MIPS setup, given a query q E Rd, we would like to find the datapoint x E X that has the highest inner product with g, i.e., we would like to identify
x arg max((aa. x.)..
x,EX
Exhaustively computing the exact inner product between and N datapoints is often very expensive and sometimes infeasible. Several techniques have been proposed in the literature based on hashing and quantization to solve the approximate maximum inner product search problem efficiently. and the quantization based techniques have shown strong performance (Ge et al., 2014 Babenko and Lempitsky 2014: Johnson et al.) 2017). Quantizing each datapoint x.; d; not only reduces storage costs and memory bandwidth bottlenccks, but also permits efficient computation of distances. It avoids memory bandwidth intensive floating point operations through Hamming distance computation and look up table operations (Norouzi et al. [2014] Jegou al., 2011 Wu al. 2017). In most traditional quantization works, the objective in the quantization procedures is to minimize the reconstruction ervor for the datapoints to be searched.
In this paper, we propose new class of loss functions in quantization to improve the performance of MIPS. Our contribution is threefold:
We derive novel class of loss functions for quantization, which departs from regular reconstruction loss by weighting each pair of q and based on its inner product value. We prove that such weighting leads to an effective loss function, which can be used by wide class of quantization algorithms.

---

Under review as a conference paper at ICLR 2020
We devise algorithms for learning the codebook, as well quantizing new datapoints, using the new loss functions. In particular, we give details for two families of quantization algorithms, product quantization and binary quantization.
We show that on large scale standard benchmark datasets, such as Glove 100, the change of objective yields significant gain on the approximation of true inner product, as well as the retrieval performance.
This paper is organized as follows. We first briefly review previous literature on quantization for Maximum Inner Product Search, as well as its links &g nearest neighbor search in Section 2 Next, we give our main result, which is the derivation of our objective in Section D Applications of the new loss functions to binary quantization and product quantization are given in Section 4 Finally, we present the experimental results in Section
2 RELATED WORKS
There is a large body of similarity search literature on inner product and nearest neighbor search. We refer readers to (Wang et al., 2014: 2016) for comprehensive survey. Some methods also transform MIPS problem into its equivalent form of &g nearest neighbor using transformation such as (Shrivastava and Li 2014] Neyshabur and Srebro 2014), but in general are less successful than the ones that directly work in the original space. In general, these bodies of works can be divided into two families: (1) representing the data as quantized codes so that similarity computation becomes more efficient (2) pruning the dataset during the search so that only a subset of data points is considered.
Typical works in the first family include binary quantization (or binary hashing) techniques (Indyk and Motwani| 1998, Shrivastava and Li,, (014) and product quantization techniques (Jegou al. [201]
Guo et al. 2016). although other Families such as additive quantization (Babenko and Lempitsky al. 2016 2018) and trenary quantization Zhu et al. (2016) also apply. There
2014)
many subsequent papers that extend these base approaches to more sophisticated codebook learning
strategics, such as (He et al. 2013 Erin Liong et al., 2015; Dai et al. 2017) for binary quantization
and and (Zhang et al.) (2014); Wu al. (017)) for product quantization. There are also lines of work that focus on learning transformations before quantization (Gong et al.] 2013 Ge et al., 2014). Different from these methods which essentially minimize reconstruction error of the database points, we argue in Section 3 that reconstruction loss is suboptimal in the MIPS context, and any quantization method can potentially benefit from our proposed objective.
The second family includes non-exhaustive search techniques such as tree search (Muja and Lowe 2014, DDsgupta and Freund 2008),, graph search (Malkov and Yashunin, 2016 Harwood and Drummond 2016). or hash bucketing (Andoni et 22015) in nearest neighbor search literature. There also exist variants of these for MIPS problem (Ram and Gray| 2012:; Shrivastava and Li] 2014). Some of these approaches lead to larger memory requirement, or random access patterns due the cost of constructing index structures in addition to storing original vectors. Thus they are usually used in combination with linear search quantization methods, in ways similar to inverted index (Jegou
al. 2011 Babenko and Lempitsky 2012
Matsui al. 2015).
In addition, many researchers have devoted to high quality implementation of such libraries, including SPTAG|Chen et al. (2018), FAISS Johnson et al. (2017). hnswlib Malkov and Yashunin (2016) etc..
We compared with ones available on ann benchmarks in Section.
3 PROBLEM FORMULATION
Common quantization techniques focus on minimizing the reconstruction error (sum of squared error) when is quantized to J. It can be shown that minimizing the reconstruction errors is equivalent to minimizing the expected inner product quantization error under a mild condition on the query distribution. Indeed, consider the quantization objective of minimizing the expected total inner product quantization errors over the query distribution:
E
(g. xr) (g. 2
Eg
1g 2.
(1)
2

---

Under review as a conference paper at ICLR 2020
C1
C1
q3
x
q1
X
C2
Cr cx)
C3
n(x,e)
C3
Best quantizer for (41.x)
More important pair of (q.x)
42
Orthogonal error
Parallel error
Closest quantizer to
A
(a)
(b)
(c)
Figure I: (a) Not all pairs of and are equally important: for it is more important to accurately quantize the inner product of (91,)) than (02. 2) or (93; 2), because (q1, x)) has higher inner product and thus is more likely to be the maximum; (b) Quantization error given one of its quantizer co can be decomposed to parallel component rij and orthogonal component ri. Notice that e3 incur more parallel loss (ri)). while C2 incur more orthogonal loss (ri). (c) Graphical illustration of the intuition behind Equation 7 Even if c3 is closer to in terms of Euclidean distance, is better quantizer than C3 in terms of inner product approximation error of (q1, x c).
Under the assumption that q is isotropic, i.e., E[q9"] = cI, where is the identity matrix and c E RR+, the objective function becomes
N
N Σ (1; = (x; - F.)
N
B 1l x, =
- 1
1=1
Therefore, the objective becomes minimizing the reconstruction errors of the database points E ||,;- - 12, and this has been considered extensively in the literature.
One key observation about the above objective function (I) is that it takes expectation over all possible combinations of datapoints x and queries q. However, equally important. The approximation error on the pairs which have a high inner product far more important since they are likely to be among the top ranked pairs and can greatly affect the search result, while for the the pairs whose inner product low the approximation error matters much less. In other words, for given datapoint æ, we should quantize with a bigger focus on its error with those queries which have high inner product with x.
easy to that not all pairs of (æ, q) are
Following this key observation, we propose a loss function by weighting the approximation error of the inner product based on the value of true inner product. More precisely, w(() 2 be monotonically non-decreasing function, and consider the following inner-produc, weighted quantization error
Σ / w(t)E 1g xz) = t)dP((gg xz) S t). (2)
Egg Fy[ww(o (q, m;)) 21)
One common choice can be w(()) I(t 2 T), in which case care about all pairs whose inner product is greater or equal certain threshold T, and disregard the rest of the pairs.
3.1 NEW LOsS FUNCTION
We decompose the inner-product weighted quantization emoos based the direction of the datapoints. We show that the new loss function (2) can be expressed as weighted sum of the parallel and orthogonal components of the residual errors with respect to the raw datapoints. Formally, let r(z,
denote the quantization residual function. Given the datapoint with |æ=|| > 0 and its quantizer ž, we can decompose the residual error two parts, the one parallel to x and the one orthogonal to æ::
r (x, == (x ã
(3)
|
P (z. .) = (x - .
r 3)
(4)
It's 's easy to see that r(x, x) .) + TT (z. Z). Next we develop our new loss function. Without
loss of generality, we assume:

---

Under review as a conference paper at ICLR 2020
1. |gll = 1. The norm of q does not matter to the ranking result;
2. |2|| S 6. The norm of is finite and bounded.
Theorem 3.1. Assuming the query is uniformly distributed in d-dimensional unit sphere. Given the datapoint x and its quantizer i, conditioned on the inner product (q, x) t for some t > O, we have
B Sg x - 1), =1 =1=
| (2
12
+
1
(x, 8)11
(5)
Proof. First, we can decompose q := + 9 with ?ni == (g. x)
" ||l||
and qı = where 9l is
parallel to r and qr is orthogonal to r. Then, we have
Byg(g, x x)) =
+ 21 (n (2, = =
= () (z)) (1, = =1]
(g.z) E.k (z)
= t]. (6)
The last step uses the fact that (a), r (z. 3) (1, (4, = 1 = 0 due to symmetry. The
= |r 322 For
first term of (6 Fy Ka ri (x, (x, 2)) (g .) = (yy [| || x) |/ the second term, since qu uniformly distributed the (d 1) dimensional subspace orthogonal
-
we have E, (2, 3) x) = 1- Tall
to x with the norm VI Therefore,
22
|| (1. R)|
1²
t² In (x) +
re, =t]
1 (2,
||
Now compute the inner- inner-produc product weighted quantization error (2 for the case w(t) I(t 2 T).
One can do similar derivations for any reasonable wt). Given >> 0 and a datapoint x::
Eg I((g .)) 2 (g. x 2) (T, ||= (x, 21 g(T, ||=]])
| (x. 2)
(7)
1
where /(T, ||=]]) and g(,, [|=|]] are defined as
||=]|
f(T. ||=l Je=min(T.lla
|| dP((g, x) tt),
g(T ||-|])
dP (g. x)) < t). |
Je=min(T.]le
It is easy to see that f(T, [|=l]) and (TT, [|=l]] are decreasing functions of T and increasing functions of ||
N
2111 + (T, || (1)1)
E. [[ mz) 2 (g.
||r 2.1.. d d-1 1
9(T,b) d
(T,,
||
#1)l
x (d 1)A(T,8) b) Σ
|n F 12 2 +
|| (1s, 2.)l (8)
where X(T,b) ((T.b)
a(T,b)*
4

---

Under review as a conference paper at ICLR 2020
3.2 COMPUTING b)
The new loss functions (2) we proposed is upper bounded by (8) and the equality is achieved when all of || = b for all Tj. (8) can be viewed as the weighted sum of the parallel quantization errors and the orthogonal quantization errors, with respect to the original data points. Note that when 6(T,6) = 1, ( reduces to the traditional reconstruction loss.
We can also characterize the asymptotic behavior of X(T,b) and show that (1) X(T, b) can be (T/b)²
analytically computed, and (2) A(T,b) b) + I-(27677 as the dimension - oc. In practice, we can choose X(T, b) empirically or through cross-validation, However, we found that X(T, b) when d + oo offers very good estimate. We discuss the sensitivity X(T, b) in Section. 7.5 of the Appendix.
So
parccos (T/6) sin d-2 0d0
Theorem 3.2. For b >> O, b, we have X(T.b)
1.
So parceos (T/b) sin 0d0
Proof. See the Section. 7.1 of Appendix.
We furthermore prove that the limit of A(T, b) exists and that it equals [d-1XT/b)
as d + co. In
(7/6)
Figure 2a we plot À with (T/b) = 0.2 and we can see it approaches its limit quickly d grows.
Theorem 3.3. When T 2 0, we have lima-soo X(T, [b)
1-(7/6)
Proof. See the Section. 7.2 of Appendix.
APPLICATION TO QUANTIZATION TECHNIQUES
In this section, we derive algorithms for applying new loss functions in to common quantization techniques, including vector quantization, product quantization. Discussion binary quantization can be found in Section 7.8 of Appendix.
4.1 VECTOR QUANTIZATION
Recall that in vector quantization, given a set of N datapoints, we want to find a codebook of size k and quantize each datapoint as one of the k codes. The goal is to minimize the total squared quantization error. Formally, the traditional vector quantization solves
min
Σ
||,, - 2,
One of the most popular quantization algorithms partition the datapoints into & quantizers where the centroid of each partition is set to be the mean of the datapoints assigned in the partition.
k-Means algorithm, where we iteratively
Motivated by minimizing the inner product quantization error for cases when the inner product between queries and datapoints is high, our proposed objective solves:
N
Σ (1s, || (24, 1
min C1 Cr ERd (a..1.................
where μ = (d ((dd11)4 b)) is hyperparameter function of d and T following
X
We solve 99) through a k- &-Means style Lloyd's algorithm, which iteratively minimizes the new loss functions by assigning datapoints partitions and updating the partition quantizer in each iteration. The assigmment step is computed by enumerating each quantizer and finding the quantizer that minimizes 9 The update step finds the new quantizer 2" IRd for partition of datapoints E RR i.c.,
I1, F22
F" min
(2,, [ (1)),
(10)
ZERR
5

---

Under review as a conference paper at ICLR 2020
Because of the changed objective, the best quantizer is no longer the center of the partition. Since (TO) a convex function of there exists an optimal solution. The update rule given fixed partitioning can be found by setting the partial derivative of (TO) with respect to each codebook entry to zero. This algorithm provably converges in finite number of steps. See Algorithm in Appendix for complete outline of the algorithm. Note that, in the special case that μ 1, it reduces to regular k-Means algorithm.
Theorem 4.1. The optimal solution of 10 is
x :=
riml
3i
(11)
Proof. See Section. 7.3 of the Appendix.
Theorem 4.2. Algorithm converges in finite number of steps.
Proof. This immediately follows from the fact that the loss defined in is always non-increasing during both assignment and averaging steps under the changed objective.
4.2 PRODUCT QUANTIZATION
A natural extension of vector quantization is product quantization, which works better in high dimensional spaces. In product quantization, the original vector space E R is decomposed as the Cartesian product of m distinct subspaces of dimension m and vector quantizations are applied in each subspace separately For example, let x E IR be written as
I x= (=((x") (2) ...., x (m)) E Rd
where x(()= IR mh is denoted as the sub-vector for the j-th subspace. We can quantize each of the xff) to 206) with its vector quantizer in subspace j. for < j S m. With product quantization, is Rd and can be represented compactly using the assigned codes.
quantized as (E()),...,;(m)) ((m)
Using proposed loss objective objective of reconstruction error:
8 minimize the following loss function instead of the usual
min C₁ Ca.Ca....Com Ag (1.2......kk) X
Σ
(ulliy ||r (x),
(12)
where z; denotes the product quantization of o; iee.
F == (CI.A,, C2... Cm.A..).
To optimize 12p.
apply the vector quantization of Section 4.1 over all subspaces, except that the subspace assignment chosen to minimize the global objective over subspaces (12). instead of using the objective in each subspace independently. Similarly, the update rule is found by setting the derivative of loss in (12) with respect each codebook entry to zero. The complete algorithm box of Algorithm (T) is found in Section 7.6 the Appendix.
5 EXPERIMENTS
In this section, we show our proposed quantization objective leads to improved performance on maxi- mum inner product search. First, we compare using productization mechanism with reconstruction loss and our proposed loss show that the new loss leads better retrieval performance and more accurate estimation of maximum inner product values. Secondly, we compare in fixed-bit-rate settings with QUIPS, which achieves state-of-the art in multiple MIPS tasks. Finally, analyze the end- to-end MIPS retrieval performance of our algorithm terms of speed-recall trade-off in controlled hardware environment and timing. We follow the benchmark setting from ann ann-bern bbenchma rk rks, which provides 1I competitive baselines with pre-tuned parameters. We plot benchmarks recalrrecall curve and show our algorithm achieves the state-of-the-a-
Random rotation permutation of the original vectors can he done hefore doing the Cartiscan product.

---

Under review as a conference paper at ICLR 2020
1,0
Change A dimension
0.92
Recall 1@10 an Glove 1.2M, bitrate-200
Relative of Top-1 Glove-1.22
0.8
74/01 T9).--07 0.2
A(6), 2.2
0.90
Propased
Reconstruction
0.30
Propesed
Recanstruction
0.88
0.25
0.86
Rocall
0.84
0.15
0.82
0.10
0.2
0.80
0.0
50
150
300
0.1
0.3
0.6
150
250
# bits
(a)
(b)
(c)
Figure 2: (a) A(T = 0.2,b in Theorem 3.2 computed analytically as function of d using
recursion of [3 quickly approaches its limit. Therefore we use its limit for computing À in
experiments. (b) The retrieval Recalll @ 10 for different I when b = 1. (c) The relative error of inner
product estimation for true Top-1 on Glovel. 2M dataset, across multiple number of bits settings.
5.1 ANALYSIS OF THE PROPOSED LOSS FUNCTION
We compare the result of same quantization mechanism with different loss functions (reconstruction loss and the proposed loss (8) ). We use Glovel 2M which is a collection of 1.2 million 100- dimensional word embeddings trained with the method described in Pennington al. (2014), and we provide rationale on using Glovel. 2M for evaluation in Section 7.9 of the Appendix. We set À as lima-too A(T 0.2, b
for all our experiments.
Figure. 2b illustrates the Recall1 @ 10 of product quantization on Glovel 2M, with reconstruction loss and proposed loss. We can see that our algorithm leads to large improvement over the one with reconstruction loss. In addition to retrieval, many application scenarios also require estimating the value of the inner product (g,r). For example, in softmax functions, inner product values often logits and are later used to compute the probability. One direct consequence of (8) is that the objective weighs pairs by their importance and thus leads to lower estimation error on top-ranking
pairs. We measure (g.z)-(9..3 (9.0)
as the relative error on true inner product. New objective clearly
(9.2)
produces smaller relative error over all bitrate settings (Figure. 2c
5.2 MAXIMUM INNER PRODUCT SEARCH RETRIEVAL
Next, we show our MIPS retrieval performance with fixed number of bits. We compare to that of QUIPS Guo SeutP/GGeeer al. (2016) which achieves the state-of-the-ar on MIPS tasks. QUIPS describes three variants, QUTPS Cov (x), QUIPS -oov (q) and QUIPS-OP --ttt which uses covariance of database vectors, covariance of query vectors and sample queries respectively. In Figure 3 We measure the performance at fixed bitrate by Recall I @N, which corresponds the fraction that Top-1 ground truth result is recalled in N retrieved results. Clearly the results using our proposed loss function out out-performs all of the variants in QUIPS.
Other quantization methods may benefit from new loss function by switching from reconstruction. For example, binary quantization such as Dai et al. (2017) uses reconstruction loss in its original paper, which be casily swapped for the proposed loss by one line change of the loss objective. We show the results which illustrated the improvement of loss function in Section 7.8 of Appendix. is possible that other quantization methods also see a moderate improvement. We will discuss our attempt with Local Search Quantization (LSQ) Martinez et al. (2018) in Section 7.7 7 of the Appendix.
5.3 EXTREME CLASSIFICATION INFERENCE
Extreme classification with large number of classes requires evaluating the last layer (classification layer) with all possible classes. When there O(M) classes, this becomes a major computation bottleneck as involves huge matrix multiplication followed by Top-K. Thus this is often solved using Maximum Inner Product Search to speed up the inference. We evaluate our methods on extreme classification using the Ama zon- 670k dataset Bhatia et al. (015)). An MLP classifier is trained over 670,091 classes, where the last layer has dimensionality on the classification layer and show the results in Figure. 3b. by comparing it against brute force matrix multiplication.
024. We evaluate retrieval performance
7

---

Under review as a conference paper at ICLR 2020
Recall- Quelll-ueery per second (1/s) tradeoff and to the right is better
Recall of Glove-1.2 2M 100 bits
10*
Recall 1@N
104
0.6
Queries per second (13s)
0.5
0.4
QUIPS Covix)
20a
QUIPS-C Covil))
0.3
QUIPS-Opt
Ours
0.3
102
20
10a
0.9
Rocall 18V
0.8
100
0.5
0.6
0.7
0.8
0.9
0.7
QUIPS Covil))
annoy
Recall (k-10)
hnswill SW-graph (nmsllb)
QUIPS-Covla)
BallTree (nmslib)
QUIPS-Opt
faiss-Ivi
aurs
Ours
hnsw (fallss
ours (batch=1000
0.1
spforest NGT-panng mrpt
kd
20
60
80
100
NGT-onng
(a) MIPS recall on Glovel 2M.
(c) Speed-recall trade-off on Glovel 2M Recall 10
Bitrate
I@1
I@ 10
I @ 100
Bitrate
[@]
I@ 10
I @@ 100
256 bits, PQ
0.652
0.995
0.999
512 bits, PQ
0.737
0.998
1.000
256 bits, Ours
0.656
0.996
1.000
512 bits, Ours
0.744
0.997
1.000
I024 bits, PQ
0.778
1.000
1.000
2048 bits, PQ
0.782
1.000
1.000
1024 bits, Ours
0.812
1.000
1.000
2048 bits, Ours
0.875
1,000
1.000
(b) Extreme classification on Amazon670k.
Figure 3: (a) Recall 1 @@ curve on Glovel 2M comparing with variants of QUIPS Guo al. (2016) on MIPS tasks. (b) Extreme classification on Anazon performed through MIPS, compared to baseline product quantization that uses reconstruction loss. (c) Recall-Spece benchmark with 11 baselines from Aumüller et al. (2019) Glovel 2M. The parameters of each baselines pre-tuned and released on: http:: aaaannnaaa bee.hhannhhssseeeeeeeee com/) Our approach compare favorably on speed-recall trade-off over popular -fth-offthee-rr, production ready methods.
5.4 RECALL- BENCHMARK
Fixed-bit-rate experiments mostly compare asymptotic behavior, and often overlook preprocessing overhead such as learned rotation or lookup table computation, which can be substantial. To evaluate effectiveness of MIPS algorithms in realistic setting, it is important to perform end-to-end benchmarks and compare the speed-recall curve. We adopted the methodology of public benchmark WUN-benchmarke Aumüller et al. (2019). which plots a comprehensive set of 11 algorithms for comparison, including faiss Johnson et al. (2017) and hnswl ib Malkov and Yashunin (2016).
Our benchmarks conducted same platform of Intel Xeon W-2135 with CPU single thread, and followed the benchmark's 's protocol. Our implementation builds on product quantization with the proposed quantization and SIMD based ADC Guo et al. (2016) for distance computation. This is further combined with vector quantization based tree Wu et (017)), and curve is plotted by varying the number of leaves to search in the tree. Figure 3P shows our performance on G1 blovel 2M significantly outperforms the competing methods, especially in high recall region, where Recall of 10 over 80%. We committed our open source implementation and parameter tunings.
6 CONCLUSION
In this paper, we propose new quantization loss function for inner product search, which replaces traditional reconstruction error. The new loss function is weighted based on the inner product values, giving more weight to the pairs of query and database points with higher inner product values. The proposed loss function is theoretically proven and can be applied to wide range of quantization methods, for example product and binary quantization. Our experiments show superior performance on retrieval recall and inner product value estimation, compared to methods that use reconstruction error. The speed-recall benchmark on public datasets further indicates that the proposed method outperform state-of-arts baselines which are known to be hard beat.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Paolo Cremonesi, Yehuda Koren, and Roberto Turrin. Performance of recommender algorithms on top-n recommendation tasks. In Proceedings of the Fourth ACM Conference on Recommender Systems, pages 39-46, 2010.
Thomas Dean, Mark Ruzon, Mark Segal, Jonathon Shlens, Sudheendra Vijayanarasimhan, and Jay Yagnik. Fast, accurate detection of 100,000 object classes a single machine: Technical supplement. In Proceedings of IEEE Conference on Computer Vision and Pattern Recognition. 2013.
lan En-Hsu Yen, Satyen Kale, Felix Yu, Daniel Holtmann- Rice, Sanjiv Kumar, and Pradeep Raviku- mar. Loss decomposition for fast learning large output spaces. In Proceedings of the 35th International Conference on Machine Learning, volume 80, pages 5640-5649, 2018.
Stephen Mussmann and Stefano Ermon. Learning and inference via maximum inner product search. In Proceedings of The 33rd International Conference Machine Learning, volume 48, pages 2587-2596, 2016.
Alexander Pritzel, Benigno Uria, Sriram Srinivasan, Adrià Puigdomênech Badia, Oriol Vinyals. Demis Hassabis, Daan Wierstra, and Charles Blundell. Neural episodic control. In Proceedings of the 34th International Conference on Machine Learning, volume 70, pages 2827-2836, 2017.
T. Ge, K. He, Q Ke, and J. Sun. Optimized product quantization. IEEE Transactions on Patlern Analysis and Machine Intelligence, 36(4):744-755 April 2014. ISSN 0162-8822 TPAMI.2013.
doi: 10.1109/
Artem Babenko and Victor Lempitsky. Additive quantization for extreme vector compression. In Computer Vision and Pattern Recognition (CVPR), 2014 IEEE Conference on, pages 931-938. IEEÉ, 2014.
Jeff Johnson, Matthijs Douze, and Hervé Jégou. Billion-scale similarity search with gpus. arXiv preprint arXiv: ww.Xiv:170.008777 2017.
Mohammad Norouzi, Ali Punjani, and David Fleet. Fast exact search hamming space with multi-index hashing. IEEE transactions on pattern analysis and machine intelligence, 36(6):
1107-1119, 2014.
Herve Jegou, Matthijs Douze, and Cordelia Schmid. Product quantization for nearest neighbor search. IEEE transactions on pattern analysis and machine intelligence, 3371):117-128, 2011.
Xiang Wu, Ruiqi Guo, Ananda Theertha Suresh, Sanjiv Kumar, Daniel N Holtmann- Rice, David Simcha, and Felix Yu. Multiscale quantization for fast similarity search. In Advances in Neural Information Processing Systems 30, pages 5745-5755 2017.
Jingdong Wang, Heng Tao Shen, Jingkuan Song, and Jianqiu Ji. Hashing for similarity search: A 2014.
survey. arXiv preprint arXiv:
Jun Wang, Wei Liu, Sanjiv Kumar, and Shih-Fu Chang. Learning to hash for indexing big data survey. Proceedings of the IEFE, 104() ):34-57, 2016.
Anshumali Shrivastava and Ping Li. Asymmetric Ish (alsh) for sublinear time maximum inner product search (mips). In Advances in Neural Information Processing Systems, pages 2321-2329, 2014.
Behnam Neyshabur and Nathan Srebro. On symmetric and asymmetric Ishs for inner product search. arXiv preprint vrXivv/410.555 2014.
Piotr Indyk and Rajeev Motwani. Approximate nearest neighbors: towards removing the curse of dimensionality. In Proceedings of the thirtieth annual ACM symposium on Theory of computing, pages 604 613. ACM, 1998.
Ruiqi Guo, Sanjiv Kumar, Krzysztof Choromanski, and David Simcha. Quantization based fast inner product search. In Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, AISTATS 2016, Cadiz, Spain, May 9-11, 2016, pages 482-490, 2016. URL http:://m/ wwwprrorrrg//oreeeeeeoo wttp
guol 6a. htm.

---

Under review as a conference paper at ICLR 2020
Julieta Martinez, Joris Clement, Holger H Hoos, and James Little. Revisiting additive quantization. In European Conference on Computer Vision, pages 137-153. Springer, 2016.
Julieta Martinez, Shobhit Zakhmi, Holger Hoos, and James Little. Lsq++: Lower running time and higher recall in multi-codebook quantization. In Proceedings of the European Conference on Computer Vision (ECCV), pages 491-506 2018.
Chenzhuo Zhu, Song Han, Huizi Mao, and William J Dally. Trained ternary quantization. arXiv preprint 16Xiv:16/2.0100 2016.
Kaiming He, Fang Wen, and Jian Sun. K-means hashing: An srfinityprreservinng quantization method for learning binary compact codes. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 2938-2945, 2013.
Venice Erin Liong, Jiwen Lu, Gang Wang. Pierre Moulin, and Jie Zhou. Deep hashing for compact binary codes learning. In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2015.
Bo Dai, Ruiqi Guo, Sanjiv Kumar, Niao He, and Le Song. Stochastic generative hashing. In Proceedings of the 34th International Conference on Machine Ceirninn-Volumme 70, pages 913- 922. JMLR. org. 2017.
Ting Zhang, Chao Du, and Jingdong Wang. Composite quantization for approximate nearest neighbor search. In ICML, volume 2, page 3, 2014.
Yunchao Gong, Svetlana Lazebnik, Albert Gordo, and Florent Perronnin. Iterative quantization: A procrustean approach learning binary codes for large-scale image retrieval. IEEE Transactions on Pattern Analysis and Machine Intelligence, (111)):29162222 2013.
Marius Muja and David G Lowe, Scalable nearest neighbor algorithms for high dimensional data. IEEE Transactions Pattern Analysis and Machine Intelligence, 36(11):227722440) 2014.
Sanjoy Dasgupta and Yoav Freund. Random projection trees and low dimensional manifolds. In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 537-546.
ACM, 2008.
Yury A. Malkov and D. A. Yashunin. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. CoRR, 05s/1603.093322 2016. URL http:
a farxiv..om wwt.boggg/bbbbo.oo 1603. 09320
Ben Harwood and Tom Drummond. FANNG: Fast approximate nearest neighbour graphs. In Computer Vision and Pattern Recognition (CVPR), 2016 IEEE Conference on, pages 5713
IEEE, 2016.
Alexandr Andoni, Piotr Indyk, Thijs Laarhoven, Ilya Razenshteyn, and Ludwig Schmidt. Practical and optimal Ish for angular distance. In Advances in Neural Information Processing Systems, pages 1225-1233, 2015.
Parikshit Ram and Alexander G Gray. Maximum inner-product 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.
Artem Babenko and Victor Lempitsky. The inverted multi-index. In Computer Vision and Pattern Recognition (CVPR), 2012 IEEE Conference on, pages 3069-3076. IEEE, 2012.
Yusuke Matsui, Toshihiko Yamasaki, and Kiyoharu Aizawa. Pqtable: Fast exact asymmetric dis- tance neighbor search for product quantization using hash tables. In Proceedings of the IEEE International Conference on Computer Vision, pages 1940-1948, 2015.
Qi Chen, Haidong Wang, Minggin Li, Gang Ren, Scarlett Li, Jeffery Zhu, Jason Li, Chuanjie Liu, Lintao Zhang, and Jingdong Wang. SPTAG: library for fast approximate nearest neighbor search, 2018. URL pectps://githnne
com httmm//icooooo////// TAG
Jeffrey Pennington, Richard Socher, and Christopher D. Manning. Glove: Global vectors for word representation. In Empirical Methods in Natural Language Processing (EMNLP), pages 1532-1543, 2014.
10

---

Under review as a conference paper at ICLR 2020
Kush Bhatia, Himanshu Jain, Purushottam Kar. Manik Varma, and Prateck Jain. Sparse local embeddings for extreme multi-label classification. In Advances neural information processing systems, pages 730-738, 2015.
Martin Aumüller, Erik Bernhardsson, and Alexander Faithfull. Ann-benchmarks: A benchmarking tool for approximate nearest neighbor algorithms. Information Systems, 2019.
Miguel A Sarreira-Perpinán and Ramin Raziperchikolaei. Hashing with binary autoencoders. In Proceedings of the IEEE conference computer vision and pattern recognition, pages 557-566, 2015.

---

Under review as a conference paper at ICLR 2020
7 APPENDIX
7.1 PROOF OF THEOREM 3.2
Proof of Theorem 3.2 Let := arccos and a := aTccos(T/b). Note that dP((gar) di is propor- tional to the surface area of (d 1) dimennsoonl hypersphere with radius of sin 6. Thus we have (f) & Sa-1 sin d- 2 0, where Sa-1 is the surface area of (d - -p-sher with unit radius.
Thus, X(T,)) b) can be re-written as:
Jo cos 0S sin d-2 0d00 0d0
Jo sin d-2 0d0
A(T b)
1.
Jo sin 0Sa-1 sin d-2 22200 Od0
So sin 0d0
Denote la = J0 sin 0d0,
Ia cos sin d-1 a+ (
cos² O 1) sins 2d10
cos ain d-1 + (d 1) / sin d-2 0d0 (d - //" sin 0d0 sind-20do-
cos cos a d-1 + (d 1)-2-2 (d 1)Id.
This gives recursive formula to compute I when d is positive integer:
sin
1 1a-2
Ia
(13)
d
With the base case of Io = and I = 1 - cos a, the exact value of À Ja-2 can be computed explicitly in (dd) time.
7.2 PROOF OF THEEREM
First, it easy to see that because d-n sin a, Cauchy-Sehhe Schwarz inequality for integrals, we have
Proof of Theorem
3.3
1. Next, from Ia
1e-2
(f sin d+2 xsin d-2 usind=?xdx)))
( sin sin 422 22nd S sin d- rdr.
0
Rearranging this have Jg la-2 which proves that 4/2 is monotonically non-increasing. Given that has lower bound and is monotonically non-increasing, the limit of Ta4z
Teta Ta
exists.
Dividing both sides of Equation. 13 by Ia. have
cOs a sin a (d- 1)--2
dIa
dla
cosassin sin
Thus lima- dia
(d-1)la-2
lim
1--2
exists.
And therefore lim d+000 dIa
also
Ia
exists. Furthermore,
000 sin 4-1
a
(d - 1--2]a-22
lim
did
+ lim d
d
sin 4-3 (d-2)ll-2
dIa
sin
T/b
Finally we have lim X d
and this proves Theorem 3.3
sin 2
1 (T/b)²*
12

---

Under review as a conference paper at ICLR 2020
7.3
PROOF OF THEOREM 4.1
Proof of Theorem 4.1 Indeed,
g( 2) pllr (2i, F)1 (x;, R)1
((0 2;)² xx,)²
+ |1 - xz²)
( x22) TT 24
Zi
112
|0,112
|
||::
= ( r,,²(a x.)) + (n 1) ((0 x3 xx1)
||2;11?
(x 24
2 x.))
= (i - 2r 2 + x;) + (p 1)
|
(5 xz 2 + | 1
27 2i
- -2 2n 2 2 + (μ 1)
|001|2
(
(5 2x x x.) (n 1)
||:2:|12
-25 201
||=:|12
(5 x2)
= ||l|| + (1- 1)
2u I; + μ |<; 1|
| 2
I xaat
= 5 i + (p= - 1)
2n xs + u||x;1?
|
Therefore, the derivative of g .) with respect to ã is
dg(x;, R) 2 + 1
2
T 2p
db
|
Setting >m"
dolas..)) de
O, we have
dg(x;, 2)
2T 2
T' 5
2prr
0
|2
i=1
T T
Σ
Di=1
1
|x;]
m
Σi=1 26
b = /b
11
m
|
m
13

---

Under review as a conference paper at ICLR 2020
7.4
ALGORITHM FOR VECTOR QUANTIZATION WITH THE MODIFIED OBJECTIVE
Algorithm 1 Proposed Vector Quantization Algorithm For Minimizing Weighted Quantization Errors
Input:
A set of N datapoints 21: .2............................ NN R
A scalar μ 0, the weight for quantization error components tradeoff (selection guided by desired inner product threshold T Seeß).
A positive integer k the size of the codebook.
Output:
A set of codebook C1, c Ck E Rd
Partition assignment @1, ,,,...,, aN E (1, k} for the N datapoints such that xz is quantized Ca.-
Algorithm:
Initialize the centroids c1, . Cj. by choosing k random datapoints. Set eeror +00.
do
old eπrr < new ciror.
(Partition Assignment
for each i (1,2, ................. N] do
a, < arg min (12
end for [Centroid Update]
for each i (1,2...
} do St ujjaa = i, S N}
a u 1+ 111111
F.
Enes x S
S
xES
where |S] denote the cardinality of the set S. end for
Compute new_erron < E (111) Cll + (1 Ca. 11 while old_erroo < new_error
Output the codebook C1, c2,..., Cj and the assignment a1, ....... ON.
7.5 SENSITIVITY TO CHOICE OF T
Another interesting question how the retrieval performance relates to given X(T, b). Intuitively, if T' is set too low, then the objective takes almost all pairs of query and database points into consideration, and becomes similar to the standard reconstruction loss. If is too high, then very few pairs will be considered and the quantization may be inaccurate for low value inner product pairs. Figure shows the retrieval evaluation of Glovel. 2M dataset under different T', We use T 0.2 for all of our retrieval experiments.
14

---

Under review as a conference paper at ICLR 2020
7.6 CODEBOOK OPTIMIZATION IN PRODUCT QUANTIZATION
For example, consider the first vector C1,1 in the codebook C₁ for the first subspace, and let æ; be one of the datapoints the first subspace of which is encoded as C1,1, i.., 22 C1.1. Write as
x; (x ai ). and 5. 1 (11)). Then
(1 2i)1 || (Ii, Ei)1l = 5 " T; + (u 1) Hb xx
2 Ds + u||x;|1
| |0
= Cc + x (11)²
22 و(-ي)) - (,, (10 + (-1)
x x(-11) + 10|1a:|12
_f 2 C1,1 2z -1) 2; of- 20) 0
(1) !T
C1,1 + + f x 23 x
(-1) (-1)
+ (1 -
|
Let S denote the of indices S = {ilAi,1 1}. Therefore, the partial derivative of respect to C1,1 is
12 with
201, + (n 1) 20, 2x( (1)
1 1) (1))
C1,1 + 2x,
x9
24
(14)
T3
AES
Set 14) to be zero, and we have
(1- (1 a(-1) (21))
Ex
1 12
Tī =
1
(15)
S
x 1
S
iES
7.7 NOTES ON APPLYING NEW LOSS FUNCTION ON LSQ
Local Search Quantization (LSQ) has shown strong results achieving state-of-the-ar performance on SIFTIM with fxed-bit-rates Since LSQ also uses reconstruction loss, it possible that the new loss would provide additional improvement over it. The author released the code on Github built on CUDA and Julia. However of GPU RAM), which seems to be related internals of Julia's CuArray library that causes OOM. Even though we tried our best to fix the issues, we weren's able to apply this on LSQ. We refer readers to the open issues of LSQ's 's code on pttttt:: / /gggtttn thub. com/ una dinos sauriiirraa Rayue la $1/issues/ for more context. We would resolved.
into multiple issues with julia-0.7.0 and GeForce GTX 1080 (8G
update and release the results if the issues are
15

---

Under review as a conference paper at ICLR 2020
7.8 RESULTS ON BINARY QUANTIZATION
Another popular family of quantization function is binary quantization. In such a setting, a function h(x) Rd {0, }}ah A is learned to quantize datapoints into binary codes, which
storage space and can speed up distance computation. There are many possible ways to design such a binary quantization function, and some Caareira-Perpinae and Raziperchikolaei (2015): Dai et al. (2017)
uses reconstruction loss.
is straight-forwand to apply our proposed loss function there and the details algorithm. We follow the setting of Stochastic Generative Hashing (SGH) Dai et al. (0017), which explicitly minimizes reconstruction loss and has been shown outperform earlier baselines. In their paper, binary auto-encoder is learned to quantize and dequantize binary codes:
f = g(((rr)); where h(x)) E {0,1)*
where (s(.) is the "encoder" part which binarizes original datapoint into binary space and g(-) is the "decoder" part which reconstructs the datapoints given the binary codes. The authors of the paper uses h(x) = sign(W)) x: + by.) as the encoder function and g(h) = w h as the decoder functions, respectively. The learning objective is to minimize the reconstruction error of ||x 2|I and the weights in the encoder and decoder are optimized end-to-ene using standard stochastic gradient descent. Following our discussion in Section. 3] this is an suboptimal objective in the MIPS settings, and the learning objective given in (8) should be preferred. This implies minimal changes to the algorithm of Dai al. (2017) except the loss function part, while holding everything else unchanged. We show below the results of SGH Dai et al. (2017) and SGH with the new loss function to illustrate the proposed loss function can be casily applied to binary quantization case.
SIFTIM 64 bits, SGH
1@1 1
1@10 10
10@
10@
100
0.028
0.096
0.053
0.220
64 bits, SGH-newloos
0.071
0.185
0.093
0.327
128 bits, SGH
0.073
0.195
0.105
0.376
128 bits, SGH-newloss
0.196
0.406
0.209
0.574
256 bits, SGH
0.142
0.331
0. 0.172
0.539
256 bits, SGH-newloss
0.362
0.662
0.363
0.820
16

---

Under review as a conference paper at ICLR 2020
7.9 IDIOSYNCRASY OF DATASETS FOR MIPS / NNS EVALUATION
With the increasing interest in Maximum Inner Product Search problem (MIPS) and its practical value in embedding based retrieval systems, researchers compete intensively on evaluation for publications. The widely used datasets for evaluating these include SIFTIM/18, 1B, GISTIM, Glovel 2M for NNS, as well as Movielens and Net for MIPS. However, we argue many datasets have data distribution issues and can lead to misinformed conclusions about the relative performance of algorithms. Some of these datasets suffer from (I) serve representation redundancy: (2) heterogeneous importance across dimensions. Since algorithms were often developed based on the empirical observation of these datasets, some have adapted to exploit the idiosyncrasies of particular datasets. Our suggestion is evaluate embedding vectors which show less data distribution issues, and thus methods can be compared on the merit of their effectiveness against well-formed vectors, and revisit some of comparisons.
SIFTIM, SIFTIB and GISTIM are introduced by Jegou al. 12011) to illustrate the use of product quantization. SIFT is a keypoint descriptor while GIST is image-level descriptor, which have been hand-crafter for image retrieval. These vectors have a high correlation between dimensions and has high degree of redundantly. The intrinsic dimension of SIFTIM and GIST much lower than its dimensionality.
Movielens and Netflix dataset are formed from the SVD of the rating matrix of Movielens and Netflix websites, respectively. This is introduced by [Shrivastava and Li (0014) for MIPS retrieval evaluation. Following SVD of X correspond to the eigenvalues of X. Thus the variance of dimensions are sorted by eigenvalues, and the first few dimensions are much more important than later ones. Moreover, the datasets are (11k)) in size and can hardly be called large-scale for evaluation purposes.
v22 (A12V)) the dimension of these two datasets
Glovel. 2M is a word embeddings dataset similar to word2vee, which use neural-network style training with a bottleneck layer. Similarly we also created Amazon670k which comes from feedforward network. These datasets exhibit less data distribution problem as illustrated in In fact, it our general observation that bottleneck layer lead independent dimensions with similar entropy, making them good datasets for benchmarking.
Below plot the correlation and variance by dimensions of SIFTIM, GISTIM, NetflixSVi as well as Gl Glove.. 2M and Ama Amazon6700 Is obvious that SIFTIM and GI GISTIM has strong correlations between dimensions and the intrinsic dimensions are significantly lower than its original dimension. On the hand eeiieeeeeVV and Netfli fflixxx 1SVD suffers from problem of variance numeric scales across dimensions, as shown in the graph below. With huge variance in the numeric scale, a few dimensions are dominating the results and the rest of dimension play much smaller roles and can almost be discarded. Thus we argue, despite the popular of first four datasets, has strong structure in data distribution and are not effective representation. On such datasets, is difficult to judge the performance of a MIPS NNS algorithm, because the dataset idiosynerasy may be exploited provide much gain the extend may overwhelm the effect of searching strategies.
We argue that the role of a MIPS NNS algorithm should be efficient search against well-formed data, not fixing representational deficiency of features in the dataset. On the other hand, dataset such as Glovel. 2M, Ama zon 6 0k, or empirically many neural network embedding has less distribution structures. This is perhaps because bottleneck layers encourage each dimension to encode independent information and carry similar amount of entropy. We suggest that these datasets should be used for benchmarking, under reproducible settings such http:// /www. , ann bennhharrk
17

---

Under review as a conference paper at ICLR 2020
Dataset
Size
Correlation
Variance by dimension
Conyetation matris SIFTIN
2000
Variance per dipiesioo SIFTIM
2200
-06
10
AM
--0.4
08
SIFTIM
(1000000, 128)
Oemerelo1
Varjance dimersion
048
0204
200
400
600
803
1000
GISTIM
(1000000, 960)
Dimona
Dimumioon
Varjance per dimansiop on MovielenaSVn
Correlpting migrri of jenofio
16-
230
075
000
2.10
0000
15
Movie lensSVD
(10681, 150)
Demonsion
per on, Netflievi
Correjation matpi of NettlpsvD
22-
Vatianc on
250
260
25
150
302
NetflixSVD
(17770, 300)
Denensoon
Correiption matrix of Gloye100
Varipcce per plinension on Glove100
175
Glovel.8 2M
(1183514. 100)
Dimanccion
Sprrelation matrix is Amapond7
0000
Varapce dymenston on Amaage670k
0075
0m00
XXO
6A0
6005
6.00
6015
615
0000
1300
400
400
600
1000
230
.02
000
000
3000
Amazon670k
(670091, 1024)
18


Reviews:
[{"review_id": "S1xgHrkiFB", "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": "The paper proposes a novel quantization algorithm for maximum inner product search. Instead of imposing equal weights on all possible queries, the proposed framework considers giving larger weights on queries having larger inner product values. The authors shows that this derives a loss function having different weights on parallel and orthogonal component of residual of quantization. The paper shows the performance of the algorithm mainly by using the Glove1.2M dataset.\n\nThe basic idea and the weighting approach would be reasonable. Empirical evaluation might be slightly weak.\n\nIn practice, how can the hyper-parameter (T and b) be determined? T = 0.2 shows the best performance on Fig. 2 (b), but its seems sensitive, and generality of this setting is not clear.\n\nIn (7), only <q,x> larger than T is penalized, but larger <q,\\tidel{x}> seems important as well. If the encoded \\tilde{x} has a large inner product value wrongly, it would deteriorate performance.\n\nThe tightness of the the upper bound of the inequality in the end of page 4 would be unclear. Replacing norm with its possible maximum value seemingly has large effect.\n\nMinor comment:\nFigure 1 is not referred from the main text.\n\nIn Fig. 2 (b), reconstruction and proposed have the save value at T = 0.1. Is this just a coincident?", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or 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": "Hyg_DV7DFS", "reviewer": "AnonReviewer1", "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": "Summary:\nThe authors propose a new loss function for solving large-scale inner product search that rely on quantization, based on the intuition that all pairs of (query, database vector) are not equally important for a given query. In particular, the authors weight the reconstruction error so that the pairs with a higher scalar product are more precisely quantized (as they lie among the most plausible candidates).\n\nStrengths of the paper:\n- The paper is well written and easy to follow. In particular, the intuition of the method is well explained in Figure 1 and the setup in Section 3 is well formulated.\n- The proposed method works with a variety of quantization approaches, such as binary, simple PQ or LSQ (even if the authors aren't able to report results for this last method due to technical issues as explained in Appendix 7.7)\n\nWeaknesses of the paper:\n- The related work could be more detailed, see for example: \"Spreading vectors for Similarity Search\", Sablayrolles et al. ; \"Pairwise Quantization\",  Babenko et al ; \"Unsupervised Neural Quantization for Compressed-Domain Similarity Search\", Morozov et al.\n\nJustification of rating:\nThe paper proposes a new loss function that weights the scalar products differently according to their importance than can be applied to a wide range of existing quantization methods. However, the strength of experimental results (in particular the fact that LSQ or other cited references above are missing) remains unclear. ", "extra_scores": {"experience_assessment": "I do not know much about 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 carefully checked 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": "BygEF9_ycS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "The paper proposes new loss functions for quantization when the task of interest is maximum inner product search (MIPS).\nThe paper is well written with clear descriptions, fairly comprehensive analysis and empirical exploration, and good results, and in general I agree that learning quantization so as to minimize quantization related errors on task at hand is a good strategy.  \nSpecific comments and suggestions for strengthening the paper are:\na) The proposed loss function in (2) includes a weight function that serves as a proxy for the task objective of giving more emphasis to quantization errors on samples with larger inner product.  Instead, why not use the true task objective which for the MIPS task is stated in the Introduction section?  If this was considered please comment on reasons for not including / discussing this in the paper, otherwise perhaps this’ll be good to discuss.\nb) Did the authors consider using a task dependent training data set which will capture both ‘q’ and ‘x’ distributions and potentially lead to even further improved quantization?  This has the disadvantage of making quantization dependent on query distribution, but in cases where such data is available it will be very valuable to know if incorporating data distributions in quantization process helps performance and to what extent.\nc) It will also be valuable to consider the closely related task of cosine distance based retrieval and comment on how that impacts the modifications of loss functions.\nd) The idea of learning quantization under objective of interest using observed data distribution has been studied earlier (e.g. see Marcheret et al., “Optimal quantization and bit allocation for compressing large discriminative feature space transforms,” ASRU 2009), perhaps worth citing as related work.\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 assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: While there was some support for the ideas presented, the majority of reviewers felt that this submission is not ready for publication at ICLR in its present form.

Concerns were raised as to the generality of the approach, thoroughness of experiments, and clarity of the exposition.
Decision: Reject