Givens Coordinate Descent Methods for Rotation Matrix Learning in Trainable Embedding Indexes
Authors: Yunjiang Jiang
Han Zhang
Yiming Qiu
Yun Xiao
Bo Long
Wen-Yun Yang
Venue: ICLR 2022 Poster (2022)
Keywords: Search index
Product quantization
Block coordinate descent

Abstract: Product quantization (PQ) coupled with a space rotation, is widely used in modern approximate nearest neighbor (ANN) search systems to significantly compress the disk storage for embeddings and speed up the inner product computation. Existing rotation learning methods, however, minimize quantization distortion for fixed embeddings, which are not applicable to an end-to-end training scenario where embeddings are updated constantly. In this paper, based on geometric intuitions from Lie group theory,  in particular the special orthogonal groupSO(n),  we propose a family of block Givens coordinate descent algorithms to learn rotation matrix that are provably convergent on any convex objectives. Compared to the state-of-the-art SVD method, the Givens algorithms are much more parallelizable, reducing runtime by orders of magnitude on modern GPUs, and converge more stably  according  to  experimental  studies.   They  further  improve  upon  vanilla product quantization significantly in an end-to-end training scenario.

Published as a conference paper at ICLR 2022
GIVENS COORDINATE DESCENT METHODS FOR ROTA- TION MATRIX LEARNING IN TRAINABLE EMBEDDING INDEXES
Yunjiang Jiang", Han Zhang, Yiming Qiu, Yun Xiao, Bo Long, Wen-Yun Yang* JD.com, Mountain View, CA, United States & Beijing, China
jinggsan,,,,r, wenyun. yang) 8 @gmail ii com (zhanghan33, wigpghannnnnnnuiiiiiiii.. qiuyiming3, xiaoyunl, bo. Long @jd. com com
ABSTRACT
Product quantization (PQ) coupled with a space rotation, is widely used in modern approximate nearest neighbor (ANN) search systems to significantly compress the disk storage for embeddings and speed up the inner product computation. Existing rotation learning methods, however, minimize quantization distortion for fixed embeddings, which are not applicable to an end-to-end training scenario where embeddings are updated constantly. In this paper, based on geometric intuitions from Lie group theory, in particular the special orthogonal group SO(n), we propose a family of block Givens coordinate descent algorithms to learn rotation matrix that are provably convergent on any convex objectives. Compared to the state-of-the-art SVD method, the Givens algorithms are much more parallelizable, reducing runtime by orders of magnitude on modern GPUs, and converge more stably according experimental studies. They further improve upon vanilla product quantization significantly in an end-to-end training scenario.
INTRODUCTION
Search index is the core technology to enable fast information retrieval in various modern compu- tational systems, such as web search, e-commerce search, recommendation and advertising in the past few decades. As a traditional type of search index, inverted index (Dean) 2009), which maps terms to documents in order to retrieve documents by term matching, have been mainstream type of search index for decades, thanks to its efficiency and straightforward interpretability. Recently, with the advent of deep learning era, embedding indexes coupled with approximate nearest neighbor promising alternative to search index (Zhang et al.) 2020) and recommendation index (Covington et al. 2016 Huang et al. 2020 Li ct al. 2019). in part due to its learnable representations and efficient ANN algorithms.
(ANN) search algorithms, have established
The main idea of embedding indexes is to encode users (or queries) and items in a latent vector space, and represent their semantic proximity in terms of inner product cosine similarity. Embedding indexes enjoy a few appealing characteristies: a) the embeddings can be learned to optimize down- stream retrieval task of interests, and b) items can be efficiently retrieved within tens of milliseconds. The latter leverages decades of algorithmic innovations, including a) maximum inner product search (MIPS) or approximate nearest neighbors (ANN), such as locality sensitive hashing (LSH) (Datar
et al. 2004). hierarchical navigable small world graphs (HNSW) (Malkov & Yashunin 2020). space
indexing by trees (Bentley 1975 Dasgupta & Freund 2008 Muja Lowel 2014 Bernhardsson
2018) or graphs (Harwood & Drummond, 2016 Iwasaki] 2015). and b) ofate-of-the-e product
quantization (PQ) based approaches (Jegou et al. 2010, Johnson et al., 2019) Guo et al. 2020
Wu et al., 2017). In particular, PQ based indexes and its variants have regularly claimed top spots on public benchmarks such as GISTIM, SIFTIB (Jegou et al. 2010) and DEEPIOM (Yandex & Lempitsky 2016). Morcover, along with the open-sourced libraries Faiss (Johnson et al., 2019) and ScaNN (Guo et al. 2020), PQ based embedding indexes are widely adopted in many industrial
systems (Huang et al. 2020 Zhang et al. 2020).
"Corresponding author

---

Published as a conference paper at ICLR 2022
1.1 PRODUCT QUANTIZATION (PQ) BASED INDEXES
SinceJJegon et al. (2010) first introduced PQ and Asymmetric Distance Computation (ADC) from signal processing to ANN search problem, there have been multiple lines of research focused on improving PQ based indexes. We briefly summarize the main directions below.
Coarse Quantization, also referred to as inverted file (IVF), is introduced in the original work of Jegou et al. (0100) to first learn a full vector quantization (referred to as coarse quantization) by K-means clustering and then perform product quantization over the residual of the coarse quantization. This enables non exhausstee search of only a subsets of the clusters, which allows ANN retrieve billions of embeddings in tens of milliseconds. More work has been done in this direction, including Inverted Multi-Index (IMI) (Lempitsky 2012);
Implementation Optimization efforts have mainly been spent on the computation of ADC, including using Hamming distance for fast pruning (Douze et al.] 2016), efficient GPU implementation of ADC lookup (Johnson et al., 2201), and SIMD-based computation for lower bounds of ADC (André) 2.15). Our proposed method fully compatible with all these implementation optimizations, since we are solely focused on the rotation matrix learning algorithms.
al.
Rotation Matrix Learning is introduced to reduce the dependencies between PQ subspaces, since PQ works best when the different subspaces are statistically independent, which may not be true in practice. As early as 2013, Optimized PQ (OPQ) (Ge et al., 2013), ITQ (Gong et al., 2013) and Cartesian k-means (Norouzi & Fleet, 2013) all propose the idea of alternating between learning (product) vector quantization and that of the rotation matrix; the latter can be formulated as the classic Orthogonal Procrustes problem (Schönemann) 1966) that has closed form solution in terms of singular value decomposition (SVD), which is also widely used in CV (Levinson et al. 2020).
Cayley Transform (Cayley (846) recently inspires researcher to develop end-to-end algorithm
to learn rotation matrix in various neural networks, especially unitary RNN (Helfrich et al., 2018
Casado & Martínez-Rube
2019) and PQ indexes (Wu et al. (017). Formally, Cayley transform parameterizes a d x d rotation matrix R by R= AI- A)- wwhere A is a skew-symmetrie matrix (i.e., A = =AA)) Note that the above parameterization of R is differentiable w.r.t. the (9) parameters of A. Thus, it allows for end-to-end training of rotation matrix R, as long as the gradient of R can be obtained. However, as we will discuss in Section 2.4 these Cayley transform based methods are not easily parallelizable to modern GPUs thus inefficient compared to our proposed method, Another drawback of Cayley transforms is numerical instability near orthogonal matrices with 11 eigenvalues. This has been partially addressed in (Lezcano- using approximate matrix exponential methods. However the latter incurs higher computation cost per step, due to the higher order rational functions involved. The question of minimal Euclidean dimension to embed SO(n) has been shown in (Zhou et al. 2019 to be of order O By contrast, our proposed GCD methods only require (n) dimension of local parameterization.
Martínez-Rubig (019)
1.2 TRAINABLE INDEXES
Despite its various advantages, notable drawhack of embedding indexes is the separation between model training and index building, which results in extra index building time and reduced retrieval accuracy. Typically, for large industrial dataset with hundreds of millions of examples, it takes hours to build the index, and recall rates drop by at least 10% (Zhang et al., 2021). This spurred a new trend of replacing embedding indexes with jointly learnable structural indexes. Researchers argue that product quantization based embedding indexes are suboptimal, as it can not be learned jointly with retrieval model. To overcome this drawback, researchers propose a few learnable index structures, such as tree-based ones (Zhu et al. 2018 2019). a K-D matrix one (Gao et al. (2200) and an improved tree-based one (Zhuo et al. 2020). Though these alternative approaches have also shown improved performance, they often require highly specialized approximate training techniques, whose complexities unfortunately hinder their wide adoptions.
On the other hand, learning PQ based indexes and retrieval model in end-to-end scenario is also challenging, in large part due to the presence of non- con-differential operators in PQ, e.g., arg min. Recently, however, ZZhang et al. (2021) proposes end-to-end training method which tackles the non-differentiability problem by leveraging gradient straight-through estimator (Bengio et al.) (013). and it shows improved performance over the separately trained embedding indexes. However, learning
2

---

Published as a conference paper at ICLR 2022
rotation matrix in end-to-end training scenario remains unaddressed. As alluded to earlier, all existing methods of learning rotation matrix are based on alternative minimization procedure with an expensive paralllelizable SVD step in each iteration. Thus it is not applicable to various pack-propagation based techniques in neural network learning.
Note that the orthonormality constraint the rotation matrix is critical to ensure pairwise distances are preserved between query and item embeddings. In end to end training, however, one could relax this condition by using L2 regularization loss of the form | 1 We have not explored this latter approach here, since we aim for applicability of the method even for standalone PQ.
1.3 OUR CONTRIBUTIONS
In this paper, we overcome the last hurdle to fully enable end-to-end training of PQ based embedding index with retrieval models, by leveraging mathematical studies of decomposition of orthogonal group by Hurwitz (1963) as early as 1963. Based on intuitions about maximal tori in compact Lie groups (Hall 2015), we propose an efficient Givens coordinate gradient descent algorithm to iteratively learn the rotation matrix starting from an identity matrix and applying a set of maximally independent (mutually commuting) Givens block rotations each iteration. We open sourced the proposed algorithm, which can be easily integrated with standard neural network training algorithms,, such as Adagrad and Adam.
Our contribution can be summarized as follows.
Methodologicallyy, we change the landscape of learning rotation matrix in approximate nearest neighbor (ANN) search from SVD based to iterative Givens rotation based, in order to be applicable to end-to-end neural network training.
Algorithmically, we propose family of Givens coordinate block descent algorithms with complexity analysis and convergence proof of the least effective variant, GCD-R
Empirically, we prove that for fixed embeddings the proposed algorithm is able to converge similarly as the existing rotation matrix learning algorithms, and for end-to-end training the proposed algorithm is able to learn the rotation matrix more effectively.
2 METHOD
2.1 REVISIT TRAINABLE PQ INDEX
Figure illustrates an overview an embedding indexing layer inside typical deep retrieval two- tower model. Formally, the indexing layer defines a full quantization function T R mx that maps a batch of m input embedding X in n--imensional space to output embeddings T(X). which can be decomposed into two functions: product quantization function ó p IR m and a rotation function with an orthonormal matrix R. The indexing layer multiplies the input embedding X by rotation matrix R and the product quantized embedding ((XR) by its inverse matrix R which is equal to its transpose R for orthonormal rotation matrix. Formally,
T(X) ((XR)R
We omit the definition of product quantization function & here, since it is not the focus of this paper. Interested readers can find the full definitions in (Jegou et al. 2010) or (Zhang et al.) (02T).
The final loss function includes two parts, retrieval loss and quantization distortion loss, formally,
((X) = Lred (T(X)) + (I/m)]|XX XR 2(121
where Lret denotes any retrieval loss typically by softmax cross entropy loss or hinge loss (Cov lington et al. 2016 Zhang et al. 2020 Huang et al., 2020). Note that straight- optimization of L is intractable, since the quantization function is not differentiable, which, however, can still be tackled by gradient straight- arrighh-thrrough estimator (Bengio et al., 2013). Then the only remaining unaddressed problem is how to iteratively learn the rotation matrix R, since existing methods only solve the case where the input vectors are fixed (Ge et al. 2013 Jegou et al. 2010). We will present our approach in the following sections.
3

---

Published as a conference paper at ICLR 2022
Rotation
Inner Prodact Cosine Similarity
Marrix
Product
Indexing Layer
Quanization
Layer
Query
Input Item Embedding
Rotated
Product
Ourput
Quzntized
Item
Emnheding
Embbdding
EisbodMing
Query Featirrss
Hiem Fealirrss
(XRR)
7(X)
MXRRR
Figure I: Illustration of end-to-end trainable two-tower retrieval model. The indexing layer located at the top of item tower is composed of a rotation matrix and a product quantization layer.
2.2 GIVENS ROTATION
Before we present the algorithm of learning a rotation matrix, let us first present a few mathematical preliminaries that serve foundations our algorithm. For simplicity of exposition, the embedding dimension = 2m will always be an even number.
Definition 1. TRxx denote the set of n n matrices. An orthogonal group O(n) (A TRxx. AAT In} is the group of all special orthogonal group, denoted SO(n), consists of all orthogonal matrices with determinant
transformations of the Euclidean space TR. The
It is forrar to check that axioms of group theory are satisfied by O(n) and SO(n) (see any introductory text on Lie groups, e.g., (Hall 2015)). In fact they form Lie sub- sub-groups groups the group of n x n invertible matrices GL(n), both of which are manifolds embedded naturally in RT
Definition 2. A Givens rotation, denoted as (0), defines rotational linear transformation around axes and j. by an angle of f E [0, 2x). Formally,
4-1
cos 9
sin 0 Iz-i
R2y(0)
sin 0
cos 0
In
where I denotes the k identity matrix. other words, the Givens rotation matrix Riy can be regarded as an identity matrix with four elements at (i, i), (f,j), (i,)), (j.j) replaced.
Hurwitz 1963) showed the following important result as early as in 1963. The essential idea is similar to Gram- Schmidt process, but specialized to rotational matrices.
Lemma 1. Every element in SO(n) can be written as a product Hisiiss (0.() though the decomposition is not unique.
In our case, to iteratively learn the rotation, we want to take to be small, such as uniformly in (-c, c), at each step. While most existing work considers single Givens rotation each step, to our best knowledge published work has considered multiple rotations in one steps, namely with step rotation composed n/2 independent rotations:
R = (2 (o (63,4) ... ()(
where is randomly chosen permutation, (i)) is the value at position i, and 0 's are again independent and uniform in (-c, c).
The fact that these rotation axes mutually disjoint ensures that their product be computed in parallel fashion. Also the convergence proof of the coordinate descent algorithm relies on estimating the amount of descent in the tangent space, which in turns requires that the rotations commute with one another. This is naturally satisfied by the choice of rotations above.
Lemma 2.
The n/2 families of Givens rotations (91.2)) Ra(o- (Bn- (.n-1,n) gener- maximally commating subgroup within S0(n).
4

---

Published as a conference paper at ICLR 2022
This follows from the observation that maximal torus of (O is precisely given by simultaneous rotations along n/2 pairs of mutually orthogonal 2d 2d-planes (see (Bröcker & Tom Dieck 2013) Chapter 5). For odd 2m + 1, simply replace n/2 by (n 1)/2.
Note that both groups SO(n) and GL(n) are non-commutative for all n > 2, just as matrix multi- plication is in general non-commutative. Unlike GL(,), however, S0(2) is commutative, since consists of the 1-parameter family planar rotations.
2.3 BLOCK COORDINATE DESCENT ALGORITHM
The overall objective function, as shown in Eq. ① needs to optimized with respect R and other parameters in T, formally,
minimize RESO(n).T
= Lree +
((XRI)
(2)
where we omit other parameters in since they are not the focus of this paper, though clearly opti- mizing those parameters needs special techniques such gradient straight-through estimator (Bengio
et al. 2013). Note that, in earlier PQ work, It is either fixed to be Zn, the identity matrix (Chen et al.
2020), separately optimized in non-differentiable manner, e-g., using singular value decomposi- tion (Ge et al. 2013), which is equivalent to optimizing only the second term in Eq. (2) with respect
to only R and hxing all other parameters.
These earlier approaches do not apply to our case, since we would like to optimize the rotation matrix iteratively and jointly with other parameters. The naive update rule f- R a nt, however, does not preserve the requirement that R E SO(n). A straight-forward remedy is to project the update back to SO(n), such as with SVD or the tangent space exponential map, both of which however require essentially diagonalization procedure, which is prohibitively expensive. Instead we take direct approach to ensure that R stays on SO(n) after every iteration.
Consider the Hurwitz parameterization in Lemma D since Oig E I., optimization, thus step gradient descent looks like + -III -lissejss (0, + V C). How-
treat it as Euclidean
ever, full Hurwitz product requires (2n²)) sparse matrix multiplications, which is too expensive. Furthermore the various ii are non-trivially correlated. To address both, we consider selecting subset of Givens rotation Rij at each step, according to the directional derivative as follows.
Proposition 1. Given an objective function C, the (un-normalized) directional derivative 0=0 C(X R,, 1sis n, given by
(R, x Trace(X VV(X)) -V"X)
where (.)ss denotes the element i-th row and j-th column, and (---) is the Frobenius inner product.
(.) By linearity, h'(0) X (0) Thus, Proof. Consider the map h:R. R h(0)
the chain rule gives
(0)= = ())
===
We would like group V((X) and X together. Using the fact that (u, v) uTo the right hand side can be written as
VL(X) X (0) (X" VL(X)) R, (X (0)
(3)
From Definition 2 of Givens rotation Roy(O), we see that
j
i j
0,-1
cos' (0)
sin (0)
0
-1
(4,(0)
sin' (0)
cos' (0)
j
5

---

Published as a conference paper at ICLR 2022
Algorithm 1 Bipartiie matching in greedy Givens coordinate descent (GCD-G).
n. 2: Output: n/2 disjoint coordinate pairs {(ie. je) : S 8 n/2).
1: Input: (2) directional derivatives 9zj :=
3: Let S : (1....,m be the set of all coordinate axes.
4: for n do
5: Among indices in S, pick (ie, ig < <je,, that maximizes ||
6: Remove ig and je from S: S + S {ie.je)-
7:
end for
It follows that (R),(0) (0) (YT Y) for any square matrix Y, which completes the proof by plugging Eq. 33 Finally to normalize the directional derivative, needs to be divided by
(0) = 22.
Given the above directional derivatives for each Ryy (0). we have a few options to select subset of n/2 disjoint (i pairs for Ray. listed below in order of increasing computational complexities, where GCD stands for Givens coordinate descent.
GCD-R randomly chooses a bipartite matching and descents along the n/2 2 Givens coordi- nates, similar to stochastic block coordinate gradient descent (Beck & Tetruashvili 2013).
This can be done efficiently by first shuffling the set of coordinates {1, .1...
GCD-G sorts the ij pairs according the absolute value of its directional derivatives in a decreasing order, and greedily picks pairs one by one if they forms a bipartite matching. Since this our main proposed algorithm, we list the details in Algorithm
GCD-S finds bipartite matching with maximum sum of edge weights, giving the steepest descent. The fastest exact algorithm (Kolmogorov 2009) for maximal matching in general weighted graph, has Onn)) 3) running time, which is impractical for first-order optimization.
With any of the above options to pick n/2 disjoint ii pairs, we can present the full algorithm in Algorithm 2 Moreover, it is worth mentioning that picking non-disjoint ij pairs neither guarantees theoretical convergence as shown Section 2.5] nor works well in practice (see Section 3.1
2.4 COMPLEXITY ANALYSIS
One iteration of Givens coordinate descent, as shown Algorithm 2 consists of three major steps: a) computing directional derivatives A in On²²) but parallelizable to O(n); b) selecting n/2 disjoint pairs in (n) by random, On log n) by greedy, or (n3) by the exact non-parallnn con-parallelizable blossom algorithm (Kolmogorov) 2009); y; c) applying rotation in ((2m²) FLOPs by a matrix multiplication between and an incremental rotation, which is sparse matrix with 2n nonzero elements. Thus, the sequential computational complexities of iteration for the three proposed algorithms Onn + n 2n²) 2) = O for GCD-R, On + n² log + n² + 2n?) = ( for GCD-G, and O(n3 + 2n O(n)) for GCD-S.
Though the time complexity for SVD and Cayley transform's 's gradient computation also O(n²), the derivative computation in the proposed GCD algorithms can be fully parallelized under modern GPUs. Thus GCD-R and GCD-G have parallel runtimes of O and O(n log n)) respectively. In contrast, the SVD computation can not be easily parallelized for general dense matrices (Berry et al., 2005), due to its internal QR factorization step (Golub & Van Loan 1996). So is the Cayley transform gradient computation, since matrix inversion by solving linear system can be parallelized.
2.5 CONVERGENCE ANALYSIS
In this section we consider gradient descent of loss function L: SO(n) + F. Note that SO(n) (n) is not a convex subset of its natural embedding space "R² because convex combinations two distinct orthogonal matrices never orthogonal.

---

Published as a conference paper at ICLR 2022
Algorithm 2 One iteration of Givens coordinate descent algorithm for rotation matrix learning.
1: Input: current
rotation matrix R. loss function L : R IR, learning rate X.
2: Get a batch of imput X E R=*x and run forward pass using X' = X R.
Run backward pass to get the gradient G V & (xXX R) and compute A R
4: for < < S do
5: Gather Aij as the directional derivative Pij == v2 de |= (RRo( (see Proposition !
6: end for
7: Select n1/ disjoint pairs {(ét, je) : 1 by random, greedy (see Algo. I steepest options.
8:
R t RII-1 ( -Agiedde)
As usual, convergence results require some assumptions about the domain and the function. Before stating them, first we introduce some definitions, specialized to the space SO(n) of orthogonal matrices with determinant 1.
For all below lemmas, theorem and corollary, see Appendix for complete proof.
The tangent space of SO(n) C RT at the identity In is given by the space of anti- symmetric matrices so sn) := (g E Rax", :g + =0. That of GL(n) is simply gl(n) == R²² Definition 4. A geodesic on SO(n)
Definition 3.
curve of the form E(t) G exp(tg) for a starting point G E (O(n) and a direction given by some E so(n); exp is the matrix exponential.
Definition 5. A function L (O) - is called geodesically convex if for any geodesic L [0, 1] + R is a convex function.
We make two assumptions on L in order prove global convergence results for the random Givens coordinate descent method (GCD-R) on (O(n). The convergence GCD-G and GCD-S follows by simple comparison with GCD-R at each step.
Assumption 1. The objective function C is geodesically convex on the level set of the manifold S(Gn) = {G (O(n) L() < [(Go)} and has unique global minimum at G Assumption 2. (Global Lipschitz) For some > and all G E S(Go), E so(n):
[(Gexp(g)) S ((G) + (VL(G). 1991.
(4)
Assumption Dlaaossnnlleassss to the following Lemma Lemma 3. For learning rate a = ,, the descent is sufficiently large for each step:
1
E[C(G+) [(Gx+1)|GGL) (n 1)m VZ(G&))
Lemma 3.4-3.6 of (Beck & Tetruashvili 2013) combined with the above lemma and Assumption ! finally yield the following Theorem:
Theorem 1. Lei | be the sequence generated by the GCD-R method, and let Dn == N&w be the diameter of 8O(n). With the assumptions above,
((Gx) - L(G)) I
k(Da(n 1 -CIG)) L(G+))-I
In particular, the value of ((G+) approaches that of the minimum, L(G*), at a sub-linear rate.
By verifying Assumptions and for individual functions F, have Corollary 1. Let the joint rotational product quantization learning objective be of form
F(R,C) =
Ui S.L. Us C.CC C Ra/D and ||C,|| =K
1=1
where D un = (uj...., up) stands for vector concatenation. Consider the specialization to
convex F, such F(x) (w, xx) (dot product) F(x) value of Rn as well the choice of quantization components wi gradient descent applied the map L R F(R,C) converges the global minimum, provided the latter is unique.
(w... T (cosine similarity). If we fix the
7

---

Published as a conference paper at ICLR 2022
3.00
3.00
3.00
Overlaping OCDN
10%
3.75
Ovarlaginng OCIN
3.75
50%
3.75
3.20
GCD-
GUD-X
1.70
100%
3.70
100%6
Disorrion
GCDS
Distortion
Distortion
3.65
Cirley
3.65
3.65
GPQ
3.60
3.00
3:55
3:55
3.50
3.50
1.00
200
200
400
500
130
200
300
400
500
100
200
300
4.00
500
Number of Iterations
Number of Iterations
Number of lierations
(a) Convergence comparative results.
(b) OPQ various datasets.
(c) GCD-G various datasets.
Figure 2: Performance of the proposed GCD algorithms in the SIFT M dataset (Lowe 2004
EXPERIMENTS
We evaluate the convergence performance fixed embeddings in Section 3.1 and the overall embedding retrieval performance on end-to-end trainable embedding indexes in Section [3.2 We implement the proposed GCD algorithm in Tensorflow 1.15, and perform all experiments single machine with Nvidia 16G V100 GPU cards.
3.1 FIXED EMBEDDINGS
Dataset and Setup. To make sure the proposed GCD algorithms practically converge, we first evaluate, for a given set of embeddings from SIFTIM (Lwwe 2004), whether the GCD algorithms can converge similarly as the original OPQ algorithm (Ge et al. 2013), which alternates between k-means for PQ centroid learning and SVD projection for optimal rotation. Our GCD algorithms simply replace the latter SVD step by a number (5 in this experiment) of Givens coordinate descent iterations with learning rate ==0.0001 as shown in Algorithm Similarly, Cayley method (Helfrich) 2019) also replaces the SVD steps by number of Cayley
ctt al. 2018 Casado & Martinez-Rubin parameter updates. All methods are evaluated by quantization distortion, which is the square of 1.2 distance between the original embedding and quantized embedding, averaged over all examples.
Figure 2a shows the comparative results between OPQ, Cayley method and the proposed GCD algorithms. Specifically, the proposed GCD-G and GCD-S can converge as well as the original OPQ algorithm, as the convergence curves are similar. The previously widely used method, Cayley transform, does not converge as fast as the proposed GCD algorithms, potentially due to the varying scales of the transformed gradient. It also shows the results of two other alternatives: overlapping GCD-G and overlapping GCD-R, which do not enforce the (i.j) pairs to be disjoint we discussed in Section 2.2 The comparison shows the necessity of enforcing the disjoint selection, since otherwise GCD-G does not converge well, though it does not affect GCD-R much. But GCD-R in general does not work as well as GCD-G, which indicates the necessity of picking the steeper descent directions. Moreover, can observe that GCD-G converges similarly as GCD-S, which indicates that greedy bipartite matching algorithm as given in Algorithm [ may be good enough in practice.
2b and 2c further compare the convergence performance between GCD-G and OPQ, by averaging over TO runs and varying the size of data. We can make two important observations: a) GCD-G converges much more stably than OPQ, as the curves show significantly lower variances; b) GCD-G converges better for smaller size of data, e.g., for 10% of the data. It indicates that GCD-G potentially works better in the stochastic descent scenario where the batch size is usually small.
Figures
3.2 END-TO-END TRAINABLE EMBEDDING INDEXES
Dataset and Setup. In this section, we evaluate GCD-S and GCD-R performances in an industrial search click log data where a user input query is used to retrieve items, and two public datasets of MovieLens (Harper & Konstan 2015) and Amazon Books (He & McAuley) 2016) where user historical behaviors are used to retrieve next behavior. The industrial dataset contains 9,989,13 135 training examples with 1,031,583 unique queries and 1,541,673 unique items, which is subsampled about 2% from our full dataset, but enough for training a reasonably well search retrieval model. We evaluate the effectiveness of the learned rotation matrix by quantization distortion, precision @
8

---

Published as a conference paper at ICLR 2022
2.1
Ciylky GUTNR
1.20
Cuylyy
Distonioe
2.0
GCD-G
OCDS
Distoriion
6.0
6.1
Distortie
1.18
GCD-G
GID-2
OLD-5
1.8
1.14
1.7
Roseline
1.12
1.6
1.10
5.7
18.0
0.5
1.0
1.5
2,0
5.6
1.00
1.25
1.50
1.75
2,00
1.0.0
0.5
1.0
1.5
2,0
Training steps
Training steps
Training stegs
(a) Industrial Dataset
(b) MovieLens
(c) Amazon Books
Figure Comparison of quantization distortion reduction on end-to-end trainable embedding indexes.
Table 1: Comparison of retrieval quality metrics on end-to-end trainable embedding indexes.
Industrial Dataset r@ 100
MovieLens
Amazon Books
p@ 100
p@ 100
r@ 100
p@ 100
r@ 100
Baseline
2.43%
51.29%
7.78%
35.53%
0.74%
5.91%
Cayley
2.44%
51.37%
7.73%
35.59%
0.74%
5.88%
GCD-R
2.43%
51.28%
7.82%
35.78%
0.73%
5.88%
GCD-G
2.43%
51.37%
7.83%
35.89%
0.73%
5.81%
GCD-S
2.44%
51.43%
7.94%
36.35%
0.74%
5.91%
GCD-S p-value baseline
0.054
0.012
0.145
0.024
0.702
0.925
(p@A k) and recall@ k (r@k) metries, which standard retrieval quality metrics. In experiments, we choose 10000. Specifically, for each query, we retrieve from embedding indexes a set top items, which then compared with the ground truth of items calculate the precision and recall. We perform ANOVA test to evaluate the p-value for all comparisons. We implement two-tower retrieval model (Zhang al. 202I with cosine scoring. hinge loss of margin 0.1 and embedding size 512. At the beginning, number of 10,000 warmup steps are performed before applying the indexing layer as shown in Figure I Then a number of 8,192 examples are collected warm start the PQ centroids and rotation matrix with 200 iterations of OPQ algorithm. The baseline method uses this initial rotation matrix and stops updating it, while the other methods continue updating it.
As shown in Figure 3 in all three datasets, the proposed GCD algorithms and Cayley method clearly outperform the baseline in terms of quantization distortion, which consequentially translates into the improvement in retrieval quality metrics, measured by precision@ @ 100 and recall @ 100 as shown in Table However, the Amazon Book dataset is an exception. We suspect the dataset may have subtle distribution, thus the small quantization distortion reduction does not result in improvements on retrieval quality metrics. Finally, we observe that the three proposed GCD algorithms consistently with theoretical analysis GCD-R and GCD-S can be regarded the lower bound and upper bound of GCD methods, with GCD-G in between. The GCD-S with steepest Givens rotations picked at each step, generally shows the best performance in both quantization distortion and retrieval metrics, especially better than the widely known Cayley method in literature.
4 CONCLUSION
In this paper, we have proposed a novel method called Givens coordinate descent (GCD) to iteratively learn rotation matrix, in the context end-to-end trainable PQ based embedding indexes. Based on a well studied mathematical result that any orthogonal matrix can be written as product of Givens rotations, the proposed GCD algorithm pieks n/2 maximally commuting Givens rotations to update the learning rotation matrix by their directional derivatives. We also provide complexity analysis and prove convergence of the proposed algorithm under convexity and other mild assumptions. Experimental results show that the proposed method converges more stably than previous SVD based and Cayley transform method, and significantly improves retrieval metrics in the end-to-end training of embedding indexes. Our algorithm is also applicable to other scenarios in any neural network training where learning a rotation matrix is potentially helpful.

---

Published as a conference paper at ICLR 2022
REFERENCES
Fabien André, Anne-Marie Kermarrec, and Nicolas Le Scouarnec. Cache locality is not enough: High-performance nearest neighbor search with product quantization fast scan. Proc. VLDB Endow. (4):288 299, December 2015.
Amir Beck and Luba Tetruashvili. the convergence of block coordinate descent type methods. SIAM journal on Optimization, 2344)2037--000, 2013.
Yoshua Bengio, Nicholas Léonard, and Aaron Courville. Estimating propagating gradients through stochastic neurons for conditional computation. In arXiv, pp. 1308.3432, 2013.
Jon Louis Bently. Multidimensional binary search trees used for associative searching. Commun. ACM, 1899):509-517, September 1975.
Erik Bernhardsson. Annoy: Approximate Nearest Neighhors in C++/Python, 2018. URL https
//pypi. wtwppioorg/prooectco /anooooyy//////////oo
Michael W Berry, Dani Mezher, Bernard Philippe, and Ahmed Sameh. Parallel algorithms for the singular value decomposition. In Handbook of parallel computing and statistics, pp. 133-180. Chapman and Hal//CRC, 2005.
Theodor Bröcker and Tammo Tom Dieck. Representations of compact Lie groups, volume 98. Springer Science & Business Media, 2013.
Mario Lezcano Casado and David Martínez-Rube Rubio. Cheap orthogonal constraints neural networks: A simple parametrization of the orthogonal and unitary group. In ICML., pp. 3794-3803, 2019.
Arthur Cayley. Sur quelques propriétés des déterminants gauches. Journal für die reine und
angewandte Mathematik, 32:1 32:119-123, 1846.
Ting Chen, Lala Li, and Yizhou Sun. Differentiable product quantization for end-to-end embedding compression. In ICML, pp. 1617-1626, 2020.
Paul Covington, Jay Adams, and Emre Sargin. Deep neural networks for youtube recommendations. In RecSys, pp. 191-198, 2016.
Sanjoy Dasgupta and Yoav Freund. Random projection trees and low dimensional manifolds. In STOC, pp. 537-546, 2008.
Mayur Datar, Nicole Immorlica, Piotr Indyk, and Vahab S Mirrokni. Locality-sensittve sensitive hashing scheme based on p-stable distributions. In Proceedings of the twentieth annual symposium on Computational geometry, pp. 253-262. 2004.
Jeffrey Dean. Challenges in building large-scale information retrieval systems. In WSDM, volume 10, 2009.
Matthijs Douze, Hervé Jégou, and Florent Perronnin. Polysemous codes. Bastian Leibe, Jiri Matas, Nicu Sebe. and Max Welling (eds.), ECCV. pp. 785-801, 2016.
Weihao Gao, Xiangjun Fan, Jiankai Sun, Kai Jia, Wenzhi Xiao, Chong Wang, and Xiaobing Liu. Deep retrieval: An end-to-end learnable structure model for large-scale recommendations, arXiv preprint arXiv:2007.07203. 2020.
Tiezheng Ge, Kaiming He, Qifa Ke, and Jian Sun. Optimized product quantization for approximate nearest neighbor search. In CVPR, pp. 2946-2953, 2013.
Gene H. Golub and Charles F. Van Loan. Matrix Computations (3rd Ed.). Johns Hopkins University Press, USA, 1996. ISBN 0801854148.
Yunchao Gong, Svetlana Lazebnik, Albert Gordo, and Florent Perronnin. Iterative quantization: A procrustean approach to learning binary codes for large-scale image retrieval. PAMI, 35(12): 2916 2916-2929, 2013.
10

---

Published as a conference paper at ICLR 2022
Ruiqi Guo, Philip Sun, Erik Lindgren, Quan Geng, David Simcha, Felix Chern, and Sanjiv Kumar. Accelerating large-scale inference with anisotropic vector quantization. ICML, pp. 3887-3896, 2020.
Brian Hall. Lie groups, Lie algebras, and representations: an elementary introduction, volume 222. Springer, 2015.
Maxwell Harper and Joseph Konstan. The movielens datasets: History and context. Acm Iransactions on interactive intelligent systems (liss, 5(4):1-19, 2015.
Ben Harwood and Tom Drummond. Fanng: Fast approximate nearest neighbour graphs. CVPR. pp. 5713-5722, 2016.
Ruining He and Julian McAuley. Ups and downs: Modeling the visual evolution of fashion trends with one-class collaborative filtering. In www, pp. 507-517, 2016.
Kyle Helfrich, Devin Willmott, and Qiang Ye. Orthogonal recurrent neural networks with scaled
Cayley transform. In ICML, pp. 1969-1978, 2018.
Jui-Ting Huang, Ashish Sharma, Shuying Sun, Li Xia, David Zhang, Philip Pronin, Janani Padman- abhan, Giuseppe Ottaviano, and Linjun Yang. Embedding based retrieval in facebook search. In SIGKDD, pp. 2553-2561, 2020.
Adolf Hurwitz. Ueber die erzeugung der invarianten durch integration. In Mathematische Werke, pp. 546-564. Springer, 1963.
Masajiro Iwasaki. NGT Neighborhood Graph and Tree for Indexing, 2015. URL https: ://
github. httpb//co///ooooaaaaaa.ao
Herve Jegou, Matthijs Douze, and Cordelia Schmid. Product quantization for nearest neighbor search.
IEEE transactions on pattern analysis and machine intelligence, 33(1):117-128, 2010.
Jeff Johnson, Matthijs Douze, and Hervé Jégou. Billion-scale similarity search with gpus. IEEE Transactions Big Data, 2019.
Vladimir Kolmogorov. Blossom
implementation of minimum cost perfect matching algorithm. Mathematical Programming Computation, 1(1):43-67, 2009.
Victor Lempitsky. The inverted multi-index. In CVPR, pp. 3069-3076, USA, 2012.
Jake Levinson, Carlos Esteves, Kefan Chen, Noah Snavely, Angjoo Kanazawa, Afshin Ros- tamizadeh, and Ameesh Makadia. An analysis of svd for deep rotation estimation. arXiv preprint wwXi:22066.16666 2020.
Mario Lezcano-Casado and David Martínez-Rubio Cheap orthogonal constraints in neural networks: A simple parametrization the orthogonal and unitary group. arXiv preprint arXiv:1901, 08428. 2019.
Chao Li, Zhiyuan Liu, Mengmeng Wu, Yuchi Xu, Huan Zhao, Pipei Huang, Guoliang Kang, Qiwei Chen, Wei Li, and Dik Lun Lee. Multi-interest network with dynamic routing for recommendation at tmall. In CIKM, pp. 2621, 2019.
David G. Lowe. Distinctive image features from scale-invariant keypoints. International Journal of Computer Vision, 60(2):91-100, November 2004. ISSN 0990--561..
Y. A. Malkov and D. A. Yashunin. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence, 42(4):824-88) 836, 2020.
Marius Muja and David G. Lowe. Scalable nearest neighbor algorithms for high dimensional data. IEEE Transactions on Pattern Analysis and Machine Intelligence, 36(1 36(11):2227-2240, 2014,
Mohammad Norouzi and David J. Fleet. Cartesian k-means. In CVPR, pp. 3017-3024, 2013.

---

Published as a conference paper at ICLR 2022
Peter Schönemann. A generalized solution of the orthogonal procrustes problem. Psychometrika, 31 (1):1-10, 1966.
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 NIPS, volume 30, 2017.
Artem Babenko Yandex and Victor Lempitsky. Efficient indexing of billion-scale datasets of deep descriptors. In CVPR, pp. 2055-2063, 2016.
Han Zhang, Songlin Wang, Kang Zhang, Zhiling Tang, Yunjiang Jiang, Yun Xiao, Weipeng Yan, and Wen- Yun Yang. Towards personalized and semantic retrieval: An end-to-end solution for e-commerce search via embedding learning. In SIGIR, pp. 2407-2416, 2020.
Han Zhang, Hongwei Shen, Yiming Qiu, Yunjiang Jiang, Songlin Wang, Sulong Xu, Yun Xiao, Bo Long, and Wen-Yun Yun Yang. Joint learning deep retrieval model and product quantization based embedding index. In SIGIR, 2021.
Yi Zhou, Connelly Barnes, Jingwan Lu, Jimei Yang, and Hao Li. On the continuity of rotation representations neural networks. Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 5745-5753, 2019.
Han Zhu, Xiang Li, Pengye Zhang, Guozheng Li, Jie He, Han Li, and Kun Gai. Learning tree-based deep model for recommender systems. In SIGKDD, pp. 1079-1088, 2018.
Han Zhu, Daqing Chang, Ziru Xu, Pengye Zhang, Xiang Li, Jie He, Han Li, Jian Xu, and Kun Gai. Joint optimization of tree-based index and deep model for recommender systems. In NIPS, pp- 3971-3980, 2019.
Jingwei Zhuo, Ziru Xu, Wei Dai, Han Zhu Han Li, Jian Xu, and Kun Gai. Learning optimal tree models under beam search. In /CML, volume 1 119, pp. 11650-11659, 2020.
12

---

Published as a conference paper at ICLR 2022
A CONVERGENCE RESULTS
In this section we prove the results stated Section 2.5
Lemma 1. For learning rate 1. the descent is sufficiently large for each step:
- F(Ex+1))=R) 2(n 1)L [VF(()))1
[[F(< -
Proof. Recall that each step of RGCGD is given by Tk+1 3x G where G Ih -0(22- (2,2)) (ft), where
Sn is uniformly random permutation. Furthermore since the (n(2i-1).o(2)) s in the product are along disjoint axes, they commute with one another:
(0(2i-1) (0)))
(0(2)-1). (000)))0221))00200(00)
(5)
we can write them as (0) exp( P2 (e: A e₁)), where the v2 factor accounts for the fact that |le, A e,ll² under Euclidean norm.
Thus let's define E so(n) = (n) by
n/2
0
12) A (o()))
Vn
n/2
0,
1k+1 = Rs (as) = In explas) = x4. exp(a
10(21-1) A C0(2)))
i=1 v2
In fact, the 0,'s 's are projections of the full gradient (F()), for F(x) := F( x),
0, - (VF(I), e A Aey), for 1 < < j S
So from 4 and orthogonality of + (2(r-)) A Co(2)), we have
F( s Fxx) - a||s|| + La
2 ||s||.
(6)
Now choose a -- We easily get
F(x++1) F(xx) S 2T
||
(7)
Finally recall that E so(n) is random vector with randomness given by the uniform a E S,, By orthogonality and the definition of 0; above, we have
B s
Σ dES
n/2
2
72: 1),
1
|VF(0)]12
|VF
(8)
n!!
n
n-1
ISicjsn
Taking expectation of both sides of 7
B[F [un] < F(xx)
VF(xx))1
(9)
2(n 1)T.
Next we recall Lemma 3.5 from Beck & Tetruashvili (0013)
Lemma 2. Let (Ak Jzzo be a non non-negative sequence of real numbers satisfying A A&t1 2 743. k = 0, 1,.,,, and Ao I mnn for positive y and m. Then
1
A S
(1c + m)² for 0, 1....
(10)
1
A - n/. for k = 2,.... for
(11)
13

---

Published as a conference paper at ICLR 2022
This along with Assumption leads to global convergence result below (combining Lemma 3.4 and Theorem 3.6 of Beck & Tetruashvili )2013)):
Theorem 1. Let {ax (22 be the sequence generated by the RGCGD method. With the two assump- tions above,
F(IR) - F(x))) & 2kH - + (F(zo) F(x)))-
(12)
In particular, the value of F(rg)) approaches that of the minimum, F(x*) ). at a sub-linear rate.
Proof. We can write 24 Rg---66 (s). where s = 70) and y [0,1] S(0)) SO(n) a constant speed geodesic path from x² to Tk. This means that (t)]l is constant for all t.
By geodesic convexity, F For: [0, 1] + convex, therefore
F(zx) - F(=*) - (For) (F/
Since 7(0)) d(rx, 2²), the geodesic distance between T& and x², by the constant speed parametriza- tion of y, Cauchy- Sahuhy-Schwwrz inequality then implies
F(xx) F(x*) [[VF(=)) x*) S ((Fx))
This combined with Lemma] gives
E (xF(2x) F F(r+41/2d)
( 1)L (F((x) - F(
Now consider the Taylor expansion around the global minimum x². Since the gradient vanishes, the Lipschitz condition
4 simplifies to
F(*x) - F(x*) - |||
2 Rx())
For the last inequality, we again use 7())) = d(Ik, x²) < R(zo) by definition of the latter.
So letting A& (xF(Fx) F(x*) )1 (2 and m (F(oo)-F(a-)) Lemma 2
implies that
1 (k + m)n
F(ax) - F(x")
2kR (2o) 1)L (F(oo)
Corollary 1. Let the joint rotational product quantization learning objective be given by
Lww, = (R
+ wi) 1=1
s.t. E.E.. CR/D and ||C,]| = K.
(13)
Consider the specialization of w E Th and F(w)(x)== = (w, x) (dot product) or F(w)(x)= (w.z)
Th [|=l|
(cosine similarity). If we fix the value of w E W as well as the choice of quantization components Un gradient descent applied to the map provided the latter is unique.
+ L(w, R, C*) converges to the global minimum,
Proof. In the dot product case, F(R) (w, Ro). If there is unique global minimizer, it can be given by UVL from the following singular value decomposition:
w. USV+
First we verify Assumption namely that the following function is convex:
t FGu exp(t.)) (w, Go exp(tA)a)).
Indeed this follows immediately from diagonalizing A, which yiclds linear combination convex functions of t.
14

---

Published as a conference paper at ICLR 2022
For assumption? 2 recall need to show F exp( <
A) 11A41 , for
some L 0. By differentiating (w, Go exp(tA)r) at = 0, we see that
t= FGo ((F))))))(F((o......
F(Go F(Go) = (we, Go(exp(A) - D)a) (w, Go +
122 + +...aa)
(VF(Go), A) + (VF A
(w, A²x).
k!
k=2
For |||]| small, the last term can be bounded by ellAll - ||A||, which O(1 For larger ||-|||, say > C, we can choose L large enough so that LC 2 > sup F.
The cosine similarity case follows immediately from the dot product case since the denominator is constant for fixed w and 4 D u, thanks to the fact that || ||||||
Corollary 2. Under the assumptions [and 2 the steepest Givens coordinate gradient descent (SGCGD) method also converges to its unique global minimum.
Proof. By the choice coordinates, each step of SGCGD dominated by the corresponding step of RGCGD based at the same point E SO(n), in other words, the estimate (22 continues to hold. D
B EMPIRICAL RUNNING TIME
Figure shows the comparison of per step runtime cost between GCD methods and Cayley transform for standalone QP training, with batch size chosen to be In Figure 4a for a fair comparison, we only compare the GCD-R method with Cayley transform, since we have not implemented GCD-G and GCD-S fully GPU operators yet. Note that the GCD-G method needs sorting operator implemented in GPU (see step in Algorithm TD. which is possible but needs customized GPU operator implemented in addition to the original TensorFlow release. On the other hand for Cayley transform, while the gradient propagation and matrix multiplication matrix inversion operation unfortunately cannot be parallelized, thus effectively runs on CPU. As expected from the complexity analysis in Section 2.4 GCD-R slows down quadratically in the embedding dimension n. whereas Cayley incurs an asymptotic O(n") cost per step. To further explore the empirical computation cost in a completely fair setup, we compare the methods all in CPU. As shown in Figure 4b GCD-G and GCD-R run much faster than the Cayley method, with about 5 times and 50 times faster running speed, respectively, which roughly reflect the total number of floating point computations in each method.
all computed GPU, the
2.5
0.10
Cayley GCD-R
Soconds per per Stop
Cayley
2.0
GCD-G
GCD-R
0.06
Seconds
0.02
0.00
0.0
1024
512
2048
Embedding Dimension
Embedding Dimension
(a) on GPU.
(b) CPU.
Figure 4: Empirical runtime comparison between GCD methods and Cayley transform method.
15


Reviews:
[{"review_id": "qPtplhyoCiI", "reviewer": "Reviewer_HiTR", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "strengths:\n\nA new method to learn rotation matrix in approximate nearest neighbor search in proposed to replace the SVD based solution. The proposed iterative Givens rotation based method is applicable to end-to-end neural network training.\n\nA family of Givens coordinate block descent algorithm are proposed to learn the rotation matrix.\n\nExperimental results on both fixed embeddings and learnable embeddings validate the effectiveness of the proposed Givens rotation based method.\n\nThe paper is clearly organized and easy to follow.\n\nweaknesses:\n\nSince the authors claim that the Cayley transform based methods are inefficient compared to the proposed method. Evidence of complexity analysis and/or experimental running time should be shown to support the claim.\n\nWhile the authors provide complexity analysis, the running time of each part can help the reader to understand and compare different components of the proposed method and also different methods.\n\nComparison with other baselines besides OPQ, e.g. ITQ, is expected in the fixed embedding experiment. It would be great if the authors can find other baselines beside the Cayley for Section 3.2.\n\nHow much is the contribution of the quantization distortion loss to the final loss in (1). Can you provide an ablation study of the weight besides 1/m?\n\nminor:\n\nthe notation of a product quantization function is expected to be R^{mxn} to R^{mxk}", "summary_of_the_paper": "This paper proposes to learn rotation matrix by Givens coordinate descent algorithms in the context of minimizing the quantization distortion for efficient storage. The proposed family of Givens coordinate descent algorithms are based on geometric intuitions of the special orthogonal group and are provably convergent on any convex objectives. The experiments show that the proposed algorithms are much time efficient and lead to performance improvement in an end-to-end training of embedding indexes.", "summary_of_the_review": "This paper is overall well written and the contributions can be clearly recognized. The method part is clear but the experimental part is not solid as expected. I tend to accept this paper at this stage and am looking forward to the authors' feedback.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "hKdHfkPbV-k", "reviewer": "Reviewer_kyJu", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "Although I could read the paper and understand it, I think the representation can benefit from some improvements. In particular, the authors avoided adding some definitions that could have helped a wider range of audiences to understand the paper. \n\n-  In the \"REVISIT TRAINABLE PQ INDEX\" subsection, the author mentioned the loss function is intractable. Hence, they try to solve that by fixing X (input) and iteratively learning R (rotation matrix). But they don't explain why the loss function is intractable. \n\n- The preliminaries notation has been introduced in the 2.2 section but it would be better if it was at the beginning of the method section. \n\n-  It is interesting that authors tried to use the lesser noticed approach in geometry to address one of the current problems in the applied world. But they didn't develop a new technique. Although, the context that they used this method seems novel the method itself is not considered novel. \n\n", "summary_of_the_paper": "Current rotation learning methods are trying to minimize quantization distortion for fixed embeddings, which are not applicable to an end-to-end training scenario where embeddings are getting updated constantly. Therefore, this paper tries to address this issue to fully enable end-to-end training of Product Quantization (PQ) based embedding index with retrieval models, by using mathematical studies of the decomposition of orthogonal group. They proposed a family of block Givens coordinate descent algorithms to learn rotation matrices that are provably convergent on any convex objectives by leveraging geometric intuitions from Lie group theory. Authors claimed that their algorithms are much more parallelizable, reducing runtime by orders of magnitude on modern GPUs, and converge more stably according to experimental studies in comparison to the state-of-the-art SVD method. \n\nTheir main contributions can be summarized as follows: \n- Changing the landscape of learning rotation matrix in approximate nearest neighbor (ANN) search from SVD based to iterative Givens rotation-based, to be applicable to end-to-end neural network training.\n\n- Proposing a family of Givens coordinate block descent algorithm with complexity analysis and convergence proof.\n\n- Proves that for the fixed embedding, their algorithm shows similar convergence result as the existing rotation matrix learning algorithms. Therefore, their proposed algorithm is able to learn the rotation matrix more effectively for the end-to-end training.", "summary_of_the_review": "It was an interesting paper because of the way that authors bridged from geometry to solve an applied problem with neural networks. But it has some room for improvement as I mentioned in the detailed review. Although the approach is interesting the technique is not that novel. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "h1k0j7IjV3", "reviewer": "Reviewer_Qvs3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "There is a mistake in Lemma 1 and 2. There must be n(n-1)/2 components instead of n/2 as claimed in the Lemmas. Take SO(3) for example, any minimal representation of SO(3) needs 3 numbers. But n/2=1.5. The value $n/2$ appears wrongly in a few places thereafter.\n\nWhile I think there is no major issue with mathematics in the paper apart from the mistake in Lemma 1 and 2, I think the authors may have overlooked the power of the Lie algebra so(n) of rotation matrices that can give them a few benefits. One can view their representation (or let us call it the Givens representation) of a small rotation matrix $R$ as $R = \\prod_{i<j} expm( \\theta_{i,j} B_{i,j} )$ (ignoring the sigma terms for ease of discussion) where each $B_{i,j}$ is a matrix of zeros everywhere except that $B_{i,j} = 1$ and $B_{j,i} = -1$, and $expm(X) = \\sum_{k>=0} (1/k!) X^k$ is the matrix exponential function. Here, $B_{i,j}$ is equivalent to a bivector such that the set of the $n(n-1)/2$ bivectors forms so(n). Their representation is similar to, but not the same as, the common Lie algebra representation of a small rotation matrix $R = expm(\\sum_{i<j} \\theta_{i,j} B_{i,j})$.\n\nWith the Lie algebra representation, given that R is small, the computation of expm() can be approximated by using the definition above but restricting to a first few terms, e.g. k <= 2 or 3. There is no need to do an expensive diagonalisation (I think the authors should elaborate the need of diagonalisation - it is not clear from the paper).\n\nSecondly, in doing so, line 8 of Algorithm 2 can be replaced by a simpler and faster to compute formula $R \\leftarrow R expm(\\sum_{i<j} \\theta_{i,j} B_{i,j})$, again taking the advantage of approximating $expm()$, eliminating the need to restrict to selected coordinates for gradient descent. There is a concern of whether doing this way would make updated rotation matrices falling off SO(n). However, one can argue that many standard functions implemented on modern machines have already incurred some level of approximation. Hence, the question is not about whether the updated matrices fall off SO(n), but about when they fall off. I would argue that if done right, adding a loss term for penalizing when the rotation is off the manifold for example, you may not have to correct the rotation matrix (via SVD to project it down to SO(n)) in every training step.\n\nThirdly, in the Givens representation I would not be too sure if bounding each element $\\theta_{i<j}$ with $-\\epsilon < \\theta_{i<j} < \\epsilon$ is good enough for small $\\epsilon$. Each Givens rotation can incur a small error. The product of all the Givens rotations can make the error on R rather large in a non-linear way. With the Lie algebra representation, we know $R$ is a function of a linear sum. Hence, how large R can be compared to $\\epsilon$ is much more predictable.\n\nFinally, the main challenge of the Lie algebra representation compared to the Givens representation is, in my view, computing the partial derivatives efficiently. But here we can take advantage of our small rotation assumption as well. According to:\n\nRossmann, Wulf (2002), Lie Groups – An Introduction Through Linear Groups, Oxford Graduate Texts in Mathematics, Oxford Science Publications, ISBN 0-19-859683-9\n\nin theorem 5, section 1.2, one can mathematically compute:\n\n$(d/dt) expm(X(t)) = expm(X(t)) \\sum_{k>=0} (-1)^k/((k+1)!) (ad_X)^k (d(X(t))/dt)$,\n\nwhere $ad_X(Y) = XY-YX$ is the adjoint operator. Applying this formula to the Lie algebra representation above, restricting to k <= 2 or 3, making use of the fact that $B_{i<j}$ are constant and very sparse, one may end up with a rather efficient approximation of $dR/d_{\\theta_{i<j}}$ for all pairs $i<j$.\n\nThe experiments are sufficient to me. However, the improvement gains when switching to the proposed approaches are rather small (i.e. distortion after 500 iterations reduced from about 3.55e-4 to about 3.50e-4 (Fig 2a), and less than 1% p-value improvements in Tab. 1) that sparks a question of statistical significance.", "summary_of_the_paper": "The paper address rotation matrix learning during product quantization in modern ANN embedding search systems. The main contribution is addressing rotation matrix learning via gradient descent of small rotation updates. The approach relies on the decomposition of any small rotation matrix into a product of Given rotations, so that partial derivatives can be obtained in parallel, but the product causes the computation of the rotation matrix itself to be slow, in O(n^2) matrix multiplications, hence the need to select a subset of coordinates and do coordinate descent. Experiments on product quantization show a marginal improvement in results over existing approaches OPQ and Cayley.", "summary_of_the_review": "I do not know much about product quantization but I know a bit about rotation matrices. For me, necessary experiments to prove the point of the paper in product quantization are presented, but the gain seems marginal. \n\nRegarding rotation matrix learning, I think the authors may have overlooked the standard approach of projecting rotations to a tangent space/Lie algebra. In this particular problem when the rotations are small, Lie algebra can be very helpful. The paper would be a lot more interesting if there were deeper treatment on this front.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "K3X2qnSbT6o", "reviewer": "Reviewer_rUSS", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "This paper proposes a block coordinate descent algorithm for rotation learning. The algorithm is based on Lemma 1 and Theorem 1. The rotation matrix on SO(n) is decomposed into diverse simple Givens rotation matrices. Then the optimized variable is converted into these Givens rotation matrices so that the rotation matrix is always on SO(3) and the projection is not required anymore. The authors also discuss how to select the coordinate, including random strategy, greedy strategy, and steepest strategy. Different from the existing work, it considers multiple Given rotations matrices in one step. \n\n## Pros\n\n1) It seems novel to consider multiple Givens rotations in one step. The motivation is clear due to proper lemmas. \n2) This paper is well-organized and easy to follow. \n\n## Cons\n1)  As the authors claim that this paper firstly considers multiple Givens rotations in one step, why does it have to use $n/2$ rotations? Could the number of rotations change? Or equivalently, is $n/2$ theoretically supported? Related discussions may be needed. Furthermore, if $n$ can be regarded as a hyper-parameter, it would be better to conduct ablation experiments of it. \n2) The experimental results about time are necessary since Cayley works well on Industrial Dataset, MovieLens, and Amazon Books. It is also important to empirically show the different efficiencies of GCD-R, GCD-G, and GCD-S. By the way, why is GCD-G missed in Table 1? Since the major improvement compared with Cayley is achieved by GCD-S, the experimental results may be dissatisfactory. There should be some competitive methods with one Givens rotation in each step. \n3) As the authors claim that '*Since this is our main proposed algorithm*', it would be better to provide some convergence analysis about GCD-G rather than GCD-R. \n\n(Minor)\n\n1)  In the 3D vision, there are also some works to estimate the rotation matrix, which are listed below. It would be better to mention the related methods as well.  \n    -  On the continuity of rotation representations in neural networks \n    - An analysis of SVD for deep rotation estimation\n2)  There are some inappropriate formulations:\n    - In Theorem 1, $:=$ may be inappropriate as it is not the formal *definition* of $\\langle R, X^T \\nabla\\mathcal L(X) \\rangle$ but a derivation. Meanwhile, it may be improper to call it a *theorem*. It is more like a proposition. \n    - In Algorithm 1, it would be better to use \"*Output*\" instead of \"*Ensure*\" as \"*Input*\" is used in the first line. \n\n", "summary_of_the_paper": "This paper proposes a block coordinate descent algorithm for rotation learning. The algorithm is based on Lemma 1 and Theorem 1. The rotation matrix on SO(n) is decomposed into diverse simple Givens rotation matrices. Then the optimized variable is converted into these Givens rotation matrices so that the rotation matrix is always on SO(3) and the projection is not required anymore. The authors also discuss how to select the coordinate, including random strategy, greedy strategy, and steepest strategy. Different from the existing work, it considers multiple Given rotations matrices in one step. ", "summary_of_the_review": "The paper is well-organized and easy to follow. The idea to use multiple Givens rotations seems novel. \n\nHowever, there are some flaws in the technical and experimental parts. One is the lack of discussion of the number of rotations in one step. It seems the authors fail to provide convincing explanations. Another problem is the missing comparison of consuming time. The method that uses only one Givens rotation is also necessary in Section 3. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper introduces a method to learn rotations of a quantized embedding end-to-end. The proposed technique seems novel, although the technical/algorithm novelty seems to be somewhat marginal. 
The empirical results are promising, although do not quite match some of the claims by the authors. 
Hopefully the reviewer feedback would help in producing an even more influential paper.
Decision: Accept (Poster)