論文の概要: Fast Gradient Computation for RoPE Attention in Almost Linear Time

• arxiv url: http://arxiv.org/abs/2412.17316v1
• Date: Mon, 23 Dec 2024 06:20:22 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-24 16:01:42.476184
• Title: Fast Gradient Computation for RoPE Attention in Almost Linear Time
• Title（参考訳）: ほぼ線形時間におけるRoPEアテンションの高速勾配計算
• Authors: Yifang Chen, Jiayan Huo, Xiaoyu Li, Yingyu Liang, Zhenmei Shi, Zhao Song,
• Abstract要約: 我々は,RoPEに基づく有界エントリ下での逆方向の計算のための,最初のニアリニア時間アルゴリズムを開発した。 我々のアプローチは、高速なRoPEアテンション計算の最近の進歩に基づいている。
• 参考スコア（独自算出の注目度）: 27.28314860714307
• License:
• Abstract: The Rotary Position Embedding (RoPE) mechanism has become a powerful enhancement to the Transformer architecture, which enables models to capture token relationships when encoding positional information. However, the RoPE mechanisms make the computations of attention mechanisms more complicated, which makes efficient algorithms challenging. Earlier research introduced almost linear time, i.e., $n^{1+o(1)}$ where $n$ is the number of input tokens, algorithms for the forward computation under specific parameter settings. However, achieving a subquadratic time algorithm for other parameter regimes remains impossible unless the widely accepted Strong Exponential Time Hypothesis (SETH) is disproven. In this work, we develop the first almost linear time algorithm for backward computations in the RoPE-based attention under bounded entries. Our approach builds on recent advancements in fast RoPE attention computations, utilizing a novel combination of the polynomial method and the Fast Fourier Transform. Furthermore, we show that with lower bounds derived from the SETH, the bounded entry condition is necessary for subquadratic performance.
• Abstract（参考訳）: RoPE(Rotary Position Embedding)メカニズムはTransformerアーキテクチャの強力な拡張であり、位置情報をエンコードする際のトークン関係をモデルでキャプチャすることができる。 しかし、RoPE機構は注意機構の計算をより複雑にし、効率的なアルゴリズムを困難にしている。 初期の研究は、ほぼ線形時間、すなわち$n^{1+o(1)}$を導入しており、$n$は入力トークンの数、特定のパラメータ設定の下での前方計算のアルゴリズムである。 しかし、広く受け入れられているStrong Exponential Time hypothesis (SETH)が証明されない限り、他のパラメータ規則に対するサブクワッド・タイム・アルゴリズムを達成することは不可能である。 本研究では,制約付きエントリ下でのRoPEに基づくアテンションにおける逆方向の計算のための,最初のニアリニア時間アルゴリズムを開発する。 提案手法は,多項式法と高速フーリエ変換を組み合わせた高速RoPEアテンション計算の最近の進歩に基づいている。 さらに,SETHから導出される境界が低い場合には,サブクワッドラティックな性能を実現するためには,境界付きエントリー条件が必要であることを示す。

関連論文リスト

• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。 TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
  論文  参考訳（メタデータ） (2023-10-18T10:29:58Z)
• Tractable Bounding of Counterfactual Queries by Knowledge Compilation [51.47174989680976]
  本稿では, パール構造因果モデルにおいて, 因果関係などの部分的特定可能なクエリのバウンダリングの問題について議論する。 最近提案された反復EMスキームは初期化パラメータをサンプリングしてそれらの境界を内部近似する。 シンボルパラメータを実際の値に置き換えた回路構造を,単一のシンボル知識コンパイルによって得られることを示す。
  論文  参考訳（メタデータ） (2023-10-05T07:10:40Z)
• Approximative lookup-tables and arbitrary function rotations for facilitating NISQ-implementations of the HHL and beyond [6.1003703380200545]
  本稿では,HHLにおける算術サブルーチンを強化する回路近似手法を提案する。 単純かつ強力な近似手法を提供することにより,これらの回路の深さを小さくすることができることを示す。
  論文  参考訳（メタデータ） (2023-06-08T08:22:41Z)
• Higher-order Derivatives of Weighted Finite-state Machines [68.43084108204741]
  本研究では、重み付き有限状態機械の正規化定数に関する高次微分の計算について検討する。 文献に記載されていないすべての順序の導関数を評価するための一般アルゴリズムを提案する。 我々のアルゴリズムは以前のアルゴリズムよりもはるかに高速である。
  論文  参考訳（メタデータ） (2021-06-01T19:51:55Z)
• Sublinear Least-Squares Value Iteration via Locality Sensitive Hashing [49.73889315176884]
  本稿では、実行時の複雑さをアクション数にサブリニアに持つ最初の証明可能なLeast-Squares Value Iteration(LSVI)アルゴリズムを提示する。 我々は, 近似最大内積探索理論と強化学習の後悔分析との関係を構築する。
  論文  参考訳（メタデータ） (2021-05-18T05:23:53Z)
• Quantum-Inspired Classical Algorithm for Principal Component Regression [1.9105479266011323]
  本研究では,データ点数に対して時間的多元対数で動作する主成分回帰のアルゴリズムを開発する。 この指数的なスピードアップは、より大きなデータセットにおける潜在的な応用を可能にする。
  論文  参考訳（メタデータ） (2020-10-16T20:50:48Z)
• Rapid Robust Principal Component Analysis: CUR Accelerated Inexact Low Rank Estimation [8.169365031508885]
  我々は、Iterated Robust CUR(IRCUR)という新しい非RPCアルゴリズムを提案する。 IRCURは小さなサブマトリクスのみを処理でき、アルゴリズム全体を通して全行列上の高価な計算を避けることができる。 数値実験は、IRCURの合成と実世界の両方のデータセットに対する計算上の優位性を確立する。
  論文  参考訳（メタデータ） (2020-10-14T22:30:20Z)
• Approximation Algorithms for Sparse Principal Component Analysis [57.5357874512594]
  主成分分析(PCA)は、機械学習と統計学において広く使われている次元削減手法である。 スパース主成分分析(Sparse principal Component Analysis)と呼ばれる,スパース主成分負荷を求める様々な手法が提案されている。 本研究では,SPCA問題に対するしきい値の精度,時間,近似アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-23T04:25:36Z)
• Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
  ニューラルネットワーク検証の基本的なコンポーネントは、出力が取ることのできる値のバウンダリの計算である。 ラグランジアン分解に基づく新しい手法を提案する。 ランニングタイムのごく一部で、既成の解法に匹敵するバウンダリが得られることを示す。
  論文  参考訳（メタデータ） (2020-02-24T17:55:10Z)

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

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