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

• URL: http://arxiv.org/abs/2203.05082v1
• Date: Wed, 9 Mar 2022 22:58:56 GMT
• Title: 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
• Abstract summary: We propose a family of block Givens coordinate descent algorithms to learn rotation matrix. Compared to the state-of-the-art SVD method, the Givens algorithms are much more parallelizable.
• Score: 19.716527782586788
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• 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 to experimental studies. They further improve upon vanilla product quantization significantly in an end-to-end training scenario.

Related papers

• A Mirror Descent-Based Algorithm for Corruption-Tolerant Distributed Gradient Descent [57.64826450787237]
  We show how to analyze the behavior of distributed gradient descent algorithms in the presence of adversarial corruptions. We show how to use ideas from (lazy) mirror descent to design a corruption-tolerant distributed optimization algorithm. Experiments based on linear regression, support vector classification, and softmax classification on the MNIST dataset corroborate our theoretical findings.
  arXiv  Detail & Related papers  (2024-07-19T08:29:12Z)
• An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
  Clustered multi-task compressive sensing is a hierarchical model that solves multiple compressive sensing tasks. The existing inference algorithm for this model is computationally expensive and does not scale well in high dimensions. We propose a new algorithm that substantially accelerates model inference by avoiding the need to explicitly compute these covariance matrices.
  arXiv  Detail & Related papers  (2023-09-30T15:57:14Z)
• Ordering for Non-Replacement SGD [7.11967773739707]
  We seek to find an ordering that can improve the convergence rates for the non-replacement form of the algorithm. We develop optimal orderings for constant and decreasing step sizes for strongly convex and convex functions. In addition, we are able to combine the ordering with mini-batch and further apply it to more complex neural networks.
  arXiv  Detail & Related papers  (2023-06-28T00:46:58Z)
• Faster One-Sample Stochastic Conditional Gradient Method for Composite Convex Minimization [61.26619639722804]
  We propose a conditional gradient method (CGM) for minimizing convex finite-sum objectives formed as a sum of smooth and non-smooth terms. The proposed method, equipped with an average gradient (SAG) estimator, requires only one sample per iteration. Nevertheless, it guarantees fast convergence rates on par with more sophisticated variance reduction techniques.
  arXiv  Detail & Related papers  (2022-02-26T19:10:48Z)
• High-Dimensional Sparse Bayesian Learning without Covariance Matrices [66.60078365202867]
  We introduce a new inference scheme that avoids explicit construction of the covariance matrix. Our approach couples a little-known diagonal estimation result from numerical linear algebra with the conjugate gradient algorithm. On several simulations, our method scales better than existing approaches in computation time and memory.
  arXiv  Detail & Related papers  (2022-02-25T16:35:26Z)
• Parallelized Computation and Backpropagation Under Angle-Parametrized Orthogonal Matrices [0.0]
  We show how an apparently sequential elementary rotation parametrization can be restructured into blocks of commutative operations. We discuss parametric restrictions of interest to generative modeling and present promising performance results with a prototype GPU implementation.
  arXiv  Detail & Related papers  (2021-05-30T00:47:03Z)
• CWY Parametrization: a Solution for Parallelized Optimization of Orthogonal and Stiefel Matrices [41.57234424773276]
  We introduce an efficient approach for optimization over orthogonal groups on highly parallel computation units such as GPUs or TPUs. We further develop a novel Truncated CWY (or T-CWY) approach for Stiefel manifold parametrization. We apply our methods to train recurrent neural network architectures in the tasks of neural machine video prediction.
  arXiv  Detail & Related papers  (2020-04-18T17:58:43Z)
• Efficient Alternating Least Squares Algorithms for Low Multilinear Rank Approximation of Tensors [6.308492837096872]
  We propose a new class of truncated HOSVD algorithms based on alternating least squares (ALS) for efficiently computing the low multilinear rank approximation of tensors. ALS-based approaches are able to eliminate the redundant computations of the singular vectors of intermediate matrices and are therefore free of data explosion. Numerical experiments with large-scale tensors from both synthetic and real-world applications demonstrate that ALS-based methods can substantially reduce the total cost of the original ones and are highly scalable for parallel computing.
  arXiv  Detail & Related papers  (2020-04-06T11:58:04Z)
• Stochastic Flows and Geometric Optimization on the Orthogonal Group [52.50121190744979]
  We present a new class of geometrically-driven optimization algorithms on the orthogonal group $O(d)$. We show that our methods can be applied in various fields of machine learning including deep, convolutional and recurrent neural networks, reinforcement learning, flows and metric learning.
  arXiv  Detail & Related papers  (2020-03-30T15:37:50Z)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  This class of algorithms encompasses several randomized methods among the fastest solvers for least-squares problems. We focus on two classical embeddings, namely, Gaussian projections and subsampled Hadamard transforms. Our resulting algorithm yields the best complexity known for solving least-squares problems with no condition number dependence.
  arXiv  Detail & Related papers  (2020-02-21T17:45:32Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.