Givens Coordinate Descent Methods for Rotation Matrix Learning in Trainable Embedding Indexes
Yunjiang Jiang, Han Zhang, Yiming Qiu, Yun Xiao, Bo Long, Wen-Yun Yang
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 , 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.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
3 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- Knowledge Distillation for High Dimensional Search Index cites Differentiable Product Quantization for End-to-End Embedding Compression
- Knowledge Distillation for High Dimensional Search Index cites Accelerating Large-Scale Inference with Anisotropic Vector Quantization
Cited by top-tier papers3
- Beyond Two-Tower Matching: Learning Sparse Retrievable Cross-Interactions for RecommendationLiangcai Su, Fan Yan, Jieming Zhu, Xi Xiao et al.SIGIR 2023 · 11 citations
- Knowledge Distillation for High Dimensional Search IndexZepu Lu, Jin Chen, Defu Lian, Zaixi Zhang et al.NeurIPS 2023 · 10 citations
- Riemannian coordinate descent algorithms on matrix manifoldsAndi Han, Pratik Jawanpuria, Bamdev MishraICML 2024 · 10 citations
Builds on3
- Accelerating Large-Scale Inference with Anisotropic Vector QuantizationRuiqi Guo, Philip Sun, Erik Lindgren, Quan Geng et al.ICML 2020 · 539 citations
- Differentiable Product Quantization for End-to-End Embedding CompressionTing Chen, Lala Li, Yizhou SunICML 2020 · 81 citations
- Learning Optimal Tree Models under Beam SearchJingwei Zhuo, Ziru Xu, Wei Dai, Han Zhu et al.ICML 2020 · 72 citations
Related papers
- Routing-Guided Learned Product Quantization for Graph-Based Approximate Nearest Neighbor SearchQiang Yue, Xiaoliang Xu, Yuxiang Wang, Yikun Tao et al.ICDE 2024 · 5 citations
- Differentiable Optimized Product Quantization and BeyondZepu Lu, Defu Lian, Jin Zhang, Zaixi Zhang et al.WWW 2023 · 11 citations
- An Analysis of SVD for Deep Rotation EstimationJake Levinson, Carlos Esteves, Kefan Chen, Noah Snavely et al.NeurIPS 2020 · 131 citations
- Anisotropic Additive Quantization for Fast Inner Product SearchJin Zhang, Qi Liu, Defu Lian, Zheng Liu et al.AAAI 2022 · 12 citations
- Product Quantizer Aware Inverted Index for Scalable Nearest Neighbor SearchHae-Chan Noh, Taeho Kim, Jae-Pil HeoICCV 2021 · 9 citations
