論文の概要: Givens Coordinate Descent Methods for Rotation Matrix Learning in Trainable Embedding Indexes

• arxiv url: http://arxiv.org/abs/2203.05082v1
• Date: Wed, 9 Mar 2022 22:58:56 GMT
• ステータス: 処理完了
• システム内更新日: 2022-03-11 15:41:08.271319
• Title: Givens Coordinate Descent Methods for Rotation Matrix Learning in Trainable Embedding Indexes
• Title（参考訳）: 学習可能な埋め込み指標における回転行列学習のためのDescent法
• Authors: Yunjiang Jiang, Han Zhang, Yiming Qiu, Yun Xiao, Bo Long, Wen-Yun Yang
• Abstract要約: 回転行列を学習するためのブロックアジェンダ座標降下アルゴリズムのファミリーを提案する。 最先端のSVD法と比較して、Givensアルゴリズムははるかに並列化可能である。
• 参考スコア（独自算出の注目度）: 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.
• Abstract（参考訳）: 製品量子化(PQ)と空間回転が組み合わされ、現代の近接近接探索システム(ANN)において、埋め込み用のディスクストレージを著しく圧縮し、内部積計算を高速化するために広く使われている。 しかし、既存の回転学習法は固定埋め込みの量子化歪みを最小限に抑えており、常に埋め込みが更新されるエンドツーエンドのトレーニングシナリオには適用できない。 本稿では,リー群理論の幾何学的直観,特に特殊直交群 $SO(n)$ に基づいて,任意の凸対象に対して有意収束する回転行列を学習するために,ブロックガジン座標降下アルゴリズム群を提案する。 最先端のSVD法と比較して、Givensアルゴリズムはより並列化可能であり、現代のGPUの桁違いのランタイムを削減し、実験結果により安定に収束する。 エンドツーエンドのトレーニングシナリオでは、バニラ製品の量子化が大幅に改善される。

関連論文リスト

• A Mirror Descent-Based Algorithm for Corruption-Tolerant Distributed Gradient Descent [57.64826450787237]
  本研究では, 分散勾配降下アルゴリズムの挙動を, 敵対的腐敗の有無で解析する方法を示す。 汚職耐性の分散最適化アルゴリズムを設計するために、(怠慢な)ミラー降下からアイデアをどう使うかを示す。 MNISTデータセットの線形回帰、サポートベクトル分類、ソフトマックス分類に基づく実験は、我々の理論的知見を裏付けるものである。
  論文  参考訳（メタデータ） (2024-07-19T08:29:12Z)
• An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
  クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。 このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。 本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-09-30T15:57:14Z)
• Ordering for Non-Replacement SGD [7.11967773739707]
  我々は,アルゴリズムの非置換形式に対する収束率を改善する順序付けを求める。 我々は,強い凸関数と凸関数のステップサイズを一定かつ小さくするための最適順序付けを開発する。 さらに、注文とミニバッチを組み合わせることで、より複雑なニューラルネットワークにも適用できます。
  論文  参考訳（メタデータ） (2023-06-28T00:46:58Z)
• Faster One-Sample Stochastic Conditional Gradient Method for Composite Convex Minimization [61.26619639722804]
  滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。 提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
  論文  参考訳（メタデータ） (2022-02-26T19:10:48Z)
• High-Dimensional Sparse Bayesian Learning without Covariance Matrices [66.60078365202867]
  共分散行列の明示的な構成を避ける新しい推論手法を提案する。 本手法では, 数値線形代数と共役勾配アルゴリズムの対角線推定結果とを結合する。 いくつかのシミュレーションにおいて,本手法は計算時間とメモリにおける既存手法よりも拡張性が高い。
  論文  参考訳（メタデータ） (2022-02-25T16:35:26Z)
• Parallelized Computation and Backpropagation Under Angle-Parametrized Orthogonal Matrices [0.0]
  そこで本研究では, 連続した初等回転パラメトリゼーションを可換演算ブロックに再構成する方法を示す。 本稿では、生成モデルに対する関心のパラメトリックな制限について論じ、GPUのプロトタイプ実装による有望な性能結果を示す。
  論文  参考訳（メタデータ） (2021-05-30T00:47:03Z)
• CWY Parametrization: a Solution for Parallelized Optimization of Orthogonal and Stiefel Matrices [41.57234424773276]
  本稿では,GPUやTPUなどの並列計算ユニット上での直交群に対する効率的な最適化手法を提案する。 さらに、Stiefel多様体のパラメトリゼーションのための新しいTruncated CWY(またはT-CWY)アプローチを開発する。 我々は,ニューラルマシンビデオ予測のタスクにおいて,リカレントニューラルネットワークアーキテクチャのトレーニングに本手法を適用した。
  論文  参考訳（メタデータ） (2020-04-18T17:58:43Z)
• Efficient Alternating Least Squares Algorithms for Low Multilinear Rank Approximation of Tensors [6.308492837096872]
  テンソルの低次階数近似を効率的に計算するための最小二乗(ALS)に基づく新しいクラスHOSVDアルゴリズムを提案する。 ALSに基づくアプローチは、中間行列の特異ベクトルの冗長な計算を排除し、したがってデータの爆発をなくすことができる。 合成および実世界の双方の大規模テンソルを用いた数値実験により、ALSベースの手法が原材料全体のコストを大幅に削減し、並列計算に非常にスケーラブルであることを示す。
  論文  参考訳（メタデータ） (2020-04-06T11:58:04Z)
• Stochastic Flows and Geometric Optimization on the Orthogonal Group [52.50121190744979]
  直交群 $O(d)$ 上の幾何駆動最適化アルゴリズムの新しいクラスを示す。 提案手法は,深層,畳み込み,反復的なニューラルネットワーク,強化学習,フロー,メトリック学習など,機械学習のさまざまな分野に適用可能であることを示す。
  論文  参考訳（メタデータ） (2020-03-30T15:37:50Z)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。 我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。 得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
  論文  参考訳（メタデータ） (2020-02-21T17:45:32Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。