# Givens Coordinate Descent Methods for Rotation Matrix Learning in Trainable Embedding Indexes

arXiv: https://arxiv.org/abs/2203.05082 · HTML: https://mlsanity.com/paper/2203.05082/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 47 references that are in the map.
- First posted on arXiv 9 Mar 2022.

## Builds on (most cited first, 17 of 17)

- [Billion-scale similarity search with GPUs](https://mlsanity.com/paper/1702.08734/) (2017)
- [Estimating or Propagating Gradients Through Stochastic Neurons for Conditional Computation](https://mlsanity.com/paper/1308.3432/) (2013)
- [On the Continuity of Rotation Representations in Neural Networks](https://mlsanity.com/paper/1812.07035/) (2018)
- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [Ups and Downs: Modeling the Visual Evolution of Fashion Trends with One-Class Collaborative Filtering](https://mlsanity.com/paper/1602.01585/) (2016)
- [Embedding-based Retrieval in Facebook Search](https://mlsanity.com/paper/2006.11632/) (2020)
- [Cheap Orthogonal Constraints in Neural Networks: A Simple Parametrization of the Orthogonal and Unitary Group](https://mlsanity.com/paper/1901.08428/) (2019)
- [Multi-Interest Network with Dynamic Routing for Recommendation at Tmall](https://mlsanity.com/paper/1904.08030/) (2019)
- [Learning Tree-based Deep Model for Recommender Systems](https://mlsanity.com/paper/1801.02294/) (2018)
- [An Analysis of SVD for Deep Rotation Estimation](https://mlsanity.com/paper/2006.14616/) (2020)
- [Orthogonal Recurrent Neural Networks with Scaled Cayley Transform](https://mlsanity.com/paper/1707.09520/) (2017)
- [Joint Optimization of Tree-based Index and Deep Model for Recommender Systems](https://mlsanity.com/paper/1902.07565/) (2019)
- [Differentiable Product Quantization for End-to-End Embedding Compression](https://mlsanity.com/paper/1908.09756/) (2019)
- [Towards Personalized and Semantic Retrieval: An End-to-End Solution for E-commerce Search via Embedding Learning](https://mlsanity.com/paper/2006.02282/) (2020)
- [Learning Optimal Tree Models Under Beam Search](https://mlsanity.com/paper/2006.15408/) (2020)
- [Joint Learning of Deep Retrieval Model and Product Quantization based Embedding Index](https://mlsanity.com/paper/2105.03933/) (2021)
- [Polysemous codes](https://mlsanity.com/paper/1609.01882/) (2016)

## Built on by (most cited first, 2 of 2)

- [Beyond Two-Tower Matching: Learning Sparse Retrievable Cross-Interactions for Recommendation](https://mlsanity.com/paper/2311.18213/) (2023)
- [Riemannian coordinate descent algorithms on matrix manifolds](https://mlsanity.com/paper/2406.02225/) (2024)

## Abstract (arXiv)

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 to experimental studies. They further improve upon vanilla product quantization significantly in an end-to-end training scenario.