Lune

ICLR2022Top-tier venue

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 SO(n)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.

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.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

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
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers3

  1. Beyond Two-Tower Matching: Learning Sparse Retrievable Cross-Interactions for RecommendationLiangcai Su, Fan Yan, Jieming Zhu, Xi Xiao et al.SIGIR 2023 · 11 citations
  2. Knowledge Distillation for High Dimensional Search IndexZepu Lu, Jin Chen, Defu Lian, Zaixi Zhang et al.NeurIPS 2023 · 10 citations
  3. Riemannian coordinate descent algorithms on matrix manifoldsAndi Han, Pratik Jawanpuria, Bamdev MishraICML 2024 · 10 citations

Builds on3

  1. Accelerating Large-Scale Inference with Anisotropic Vector QuantizationRuiqi Guo, Philip Sun, Erik Lindgren, Quan Geng et al.ICML 2020 · 539 citations
  2. Differentiable Product Quantization for End-to-End Embedding CompressionTing Chen, Lala Li, Yizhou SunICML 2020 · 81 citations
  3. Learning Optimal Tree Models under Beam SearchJingwei Zhuo, Ziru Xu, Wei Dai, Han Zhu et al.ICML 2020 · 72 citations

Related papers

  1. 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
  2. Differentiable Optimized Product Quantization and BeyondZepu Lu, Defu Lian, Jin Zhang, Zaixi Zhang et al.WWW 2023 · 11 citations
  3. An Analysis of SVD for Deep Rotation EstimationJake Levinson, Carlos Esteves, Kefan Chen, Noah Snavely et al.NeurIPS 2020 · 131 citations
  4. Anisotropic Additive Quantization for Fast Inner Product SearchJin Zhang, Qi Liu, Defu Lian, Zheng Liu et al.AAAI 2022 · 12 citations
  5. Product Quantizer Aware Inverted Index for Scalable Nearest Neighbor SearchHae-Chan Noh, Taeho Kim, Jae-Pil HeoICCV 2021 · 9 citations
Dusk over the sea between two cliffs drawn in fine vertical lines