論文の概要: A Fast Optimization View: Reformulating Single Layer Attention in LLM Based on Tensor and SVM Trick, and Solving It in Matrix Multiplication Time

• arxiv url: http://arxiv.org/abs/2309.07418v1
• Date: Thu, 14 Sep 2023 04:23:40 GMT
• ステータス: 処理完了
• システム内更新日: 2023-09-15 16:21:45.508192
• Title: A Fast Optimization View: Reformulating Single Layer Attention in LLM Based on Tensor and SVM Trick, and Solving It in Matrix Multiplication Time
• Title（参考訳）: 高速最適化視点:テンソルとSVMトリップに基づくLLMにおける単一層アテンションの修正と行列乗算時間での解法
• Authors: Yeqi Gao, Zhao Song, Weixin Wang, Junze Yin
• Abstract要約: 我々は、一層注意ネットワーク目的関数 $L(X,Y) の証明可能な保証を提供することに注力する。 多層LCMネットワークでは、mathbbRn×d2$の行列$Bを層の出力と見なすことができる。 損失関数をトレーニングする反復アルゴリズムを$L(X,Y)$ up $epsilon$で、$widetildeO( (cal T_mathrmmat(n,d) + dで実行される。
• 参考スコア（独自算出の注目度）: 7.613259578185218
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Large language models (LLMs) have played a pivotal role in revolutionizing various facets of our daily existence. Solving attention regression is a fundamental task in optimizing LLMs. In this work, we focus on giving a provable guarantee for the one-layer attention network objective function $L(X,Y) = \sum_{j_0 = 1}^n \sum_{i_0 = 1}^d ( \langle \langle \exp( \mathsf{A}_{j_0} x ) , {\bf 1}_n \rangle^{-1} \exp( \mathsf{A}_{j_0} x ), A_{3} Y_{*,i_0} \rangle - b_{j_0,i_0} )^2$. Here $\mathsf{A} \in \mathbb{R}^{n^2 \times d^2}$ is Kronecker product between $A_1 \in \mathbb{R}^{n \times d}$ and $A_2 \in \mathbb{R}^{n \times d}$. $A_3$ is a matrix in $\mathbb{R}^{n \times d}$, $\mathsf{A}_{j_0} \in \mathbb{R}^{n \times d^2}$ is the $j_0$-th block of $\mathsf{A}$. The $X, Y \in \mathbb{R}^{d \times d}$ are variables we want to learn. $B \in \mathbb{R}^{n \times d}$ and $b_{j_0,i_0} \in \mathbb{R}$ is one entry at $j_0$-th row and $i_0$-th column of $B$, $Y_{*,i_0} \in \mathbb{R}^d$ is the $i_0$-column vector of $Y$, and $x \in \mathbb{R}^{d^2}$ is the vectorization of $X$. In a multi-layer LLM network, the matrix $B \in \mathbb{R}^{n \times d}$ can be viewed as the output of a layer, and $A_1= A_2 = A_3 \in \mathbb{R}^{n \times d}$ can be viewed as the input of a layer. The matrix version of $x$ can be viewed as $QK^\top$ and $Y$ can be viewed as $V$. We provide an iterative greedy algorithm to train loss function $L(X,Y)$ up $\epsilon$ that runs in $\widetilde{O}( ({\cal T}_{\mathrm{mat}}(n,n,d) + {\cal T}_{\mathrm{mat}}(n,d,d) + d^{2\omega}) \log(1/\epsilon) )$ time. Here ${\cal T}_{\mathrm{mat}}(a,b,c)$ denotes the time of multiplying $a \times b$ matrix another $b \times c$ matrix, and $\omega\approx 2.37$ denotes the exponent of matrix multiplication.
• Abstract（参考訳）: 大規模言語モデル(LLM)は、我々の日常生活における様々な側面に革命をもたらす重要な役割を担っている。 注意の回帰を解くことはLLMを最適化する基本的な課題である。 本研究では、一層アテンションネットワーク対象関数 $L(X,Y) = \sum_{j_0 = 1}^n \sum_{i_0 = 1}^d ( \langle \langle \exp( \mathsf{A}_{j_0} x ) , {\bf 1}_n \rangle^{-1} \exp( \mathsf{A}_{j_0} x ), A_{3} Y_{*,i_0} \rangle - b_{j_0,i_0} )^2$ に対して証明可能な保証を与えることに焦点を当てる。 ここで、$\mathsf{A} \in \mathbb{R}^{n^2 \times d^2}$は、$A_1 \in \mathbb{R}^{n \times d}$と$A_2 \in \mathbb{R}^{n \times d}$の間のクロネッカー積である。 A_3$ は $\mathbb{R}^{n \times d}$, $\mathsf{A}_{j_0} \in \mathbb{R}^{n \times d^2}$ の行列は $\mathsf{A}$ の$j_0$-番目のブロックである。 X, Y \in \mathbb{R}^{d \times d}$は私たちが学びたい変数である。 $B \in \mathbb{R}^{n \times d}$と$b_{j_0,i_0} \in \mathbb{R}$は$j_0$-th rowと$i_0$-th column of $B$, $Y_{*,i_0} \in \mathbb{R}^d$は$Y$の$i_0$-column vectorであり、$x \in \mathbb{R}^{d^2}$は$X$のベクトル化である。 多層llmネットワークでは、行列 $b \in \mathbb{r}^{n \times d}$ は層の出力と見なすことができ、$a_1= a_2 = a_3 \in \mathbb{r}^{n \times d}$ は層の入力と見なすことができる。 x$の行列版は$QK^\top$と見ることができ、$Y$は$V$と見ることができる。 損失関数 $l(x,y)$ up $\epsilon$ を訓練するための反復的グリーディアルゴリズムを提供し、$\widetilde{o}( ({\cal t}_{\mathrm{mat}}(n,n,d) + {\cal t}_{\mathrm{mat}}(n,d,d) + d^{2\omega}) \log(1/\epsilon)$ time で実行する。 ここで、${\cal T}_{\mathrm{mat}}(a,b,c)$ は $a \times b$ matrix と $b \times c$ matrix を乗算する時間を表し、$\omega\approx 2.37$ は行列乗算の指数を表す。

関連論文リスト

• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• LevAttention: Time, Space, and Streaming Efficient Algorithm for Heavy Attentions [54.54897832889028]
  任意の$K$に対して、$n$とは独立に「普遍集合」$Uサブセット[n]$が存在し、任意の$Q$と任意の行$i$に対して、大きな注目スコアが$A_i,j$ in row $i$ of $A$は全て$jin U$を持つことを示す。 我々は、視覚変換器のスキームの利点を実証的に示し、トレーニング中に我々の普遍的なセットを使用する新しいモデルのトレーニング方法を示した。
  論文  参考訳（メタデータ） (2024-10-07T19:47:13Z)
• Efficient Matrix Factorization Via Householder Reflections [2.3326951882644553]
  我々は$mathbfH$と$mathbfX$を$mathbfY$から正確に回収することが、$mathbfY$の$Omega$列で保証されていることを示す。 この研究のテクニックが、辞書学習のための代替アルゴリズムの開発に役立つことを願っている。
  論文  参考訳（メタデータ） (2024-05-13T11:13:49Z)
• Provably learning a multi-head attention layer [55.2904547651831]
  マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。 本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。 最悪の場合、$m$に対する指数的依存は避けられないことを示す。
  論文  参考訳（メタデータ） (2024-02-06T15:39:09Z)
• Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
  本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。 目標は、低ランク因子の積として$mathbfA$を近似することである。 我々の手法はBMF問題の他の一般的な変種に一般化する。
  論文  参考訳（メタデータ） (2023-06-02T18:55:27Z)
• Randomized and Deterministic Attention Sparsification Algorithms for Over-parameterized Feature Dimension [18.57735939471469]
  我々は注意問題のスパシフィケーションを考慮する。 超大規模特徴量の場合、文の長さをほぼ線形に縮めることができる。
  論文  参考訳（メタデータ） (2023-04-10T05:52:38Z)
• Fast Attention Requires Bounded Entries [19.17278873525312]
  内部製品注意計算はTransformer, GPT-1, BERT, GPT-2, GPT-3, ChatGPTなどの大規模言語モデルを訓練するための基本的なタスクである。 行列を暗黙的に$A$とすることで、より高速なアルゴリズムが可能かどうかを検討する。 このことは、入力行列がより小さいエントリを持つ場合、注意計算の方がはるかに効率的である、実際に観察された現象の理論的な説明を与える。
  論文  参考訳（メタデータ） (2023-02-26T02:42:39Z)
• A Nearly-Optimal Bound for Fast Regression with $\ell_\infty$ Guarantee [16.409210914237086]
  行列 $Ain mathbbRntimes d$ とテンソル $bin mathbbRn$ が与えられたとき、 $ell_infty$ の回帰問題を考える。 このような$ell_infty$レグレッションの保証を得るためには、濃密なスケッチ行列を使わなければならない。 我々はまた、OCE(Oblivious Coordinate-wise Embedding)特性を利用した $ell_infty$ guarantee regression のための新しい分析フレームワークを開発した。
  論文  参考訳（メタデータ） (2023-02-01T05:22:40Z)
• Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
  我々は、任意のSchatten-$p$ノルムの下で、低ランク近似のためのクリロフ部分空間に基づく反復法について研究する。 我々の主な成果は、$tildeO(k/sqrtepsilon)$ matrix-vector productのみを使用するアルゴリズムである。
  論文  参考訳（メタデータ） (2022-02-10T16:10:41Z)
• Spectral properties of sample covariance matrices arising from random matrices with independent non identically distributed columns [50.053491972003656]
  関数 $texttr(AR(z))$, for $R(z) = (frac1nXXT- zI_p)-1$ and $Ain mathcal M_p$ deterministic, have a standard deviation of order $O(|A|_* / sqrt n)$. ここでは、$|mathbb E[R(z)] - tilde R(z)|_F を示す。
  論文  参考訳（メタデータ） (2021-09-06T14:21:43Z)
• Algorithms and Hardness for Linear Algebra on Geometric Graphs [14.822517769254352]
  グリーンガードとロークリンの有名な高速多重極法における次元$dの指数的依存は改善できないことを示す。 これは高速多重極法について証明された最初の公式な制限である。
  論文  参考訳（メタデータ） (2020-11-04T18:35:02Z)

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

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