Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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. 

Their main contributions can be summarized as follows: 
- 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.

- Proposing a family of Givens coordinate block descent algorithm with complexity analysis and convergence proof.

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

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

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

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


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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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. 
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. 

## Pros

1) It seems novel to consider multiple Givens rotations in one step. The motivation is clear due to proper lemmas. 
2) This paper is well-organized and easy to follow. 

## Cons
1)  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. 
2) 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. 
3) 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. 

(Minor)

1)  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.  
    -  On the continuity of rotation representations in neural networks 
    - An analysis of SVD for deep rotation estimation
2)  There are some inappropriate formulations:
    - 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. 
    - In Algorithm 1, it would be better to use "*Output*" instead of "*Ensure*" as "*Input*" is used in the first line. 


summary_of_the_review: The paper is well-organized and easy to follow. The idea to use multiple Givens rotations seems novel. 

However, 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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.
main_review: strengths:

A 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.

A family of Givens coordinate block descent algorithm are proposed to learn the rotation matrix.

Experimental results on both fixed embeddings and learnable embeddings validate the effectiveness of the proposed Givens rotation based method.

The paper is clearly organized and easy to follow.

weaknesses:

Since 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.

While 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.

Comparison 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.

How 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?

minor:

the notation of a product quantization function is expected to be R^{mxn} to R^{mxk}
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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.
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.

While 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})$.

With 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).

Secondly, 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.

Thirdly, 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.

Finally, 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:

Rossmann, Wulf (2002), Lie Groups – An Introduction Through Linear Groups, Oxford Graduate Texts in Mathematics, Oxford Science Publications, ISBN 0-19-859683-9

in theorem 5, section 1.2, one can mathematically compute:

$(d/dt) expm(X(t)) = expm(X(t)) \sum_{k>=0} (-1)^k/((k+1)!) (ad_X)^k (d(X(t))/dt)$,

where $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$.

The 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_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. 

Regarding 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.
review_title: null

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)