Fugu-MT 論文翻訳(概要): A Tighter Complexity Analysis of SparseGPT

論文の概要: A Tighter Complexity Analysis of SparseGPT

arxiv url: http://arxiv.org/abs/2408.12151v1
Date: Thu, 22 Aug 2024 06:40:32 GMT
ステータス: 処理完了
システム内更新日: 2024-08-23 15:03:23.094219
Title: A Tighter Complexity Analysis of SparseGPT
Title（参考訳）: スパースGPTの高次複雑度解析
Authors: Xiaoyu Li, Yingyu Liang, Zhenmei Shi, Zhao Song,
Abstract要約: SparseGPT[Frantar, Alistarh ICML 2023]のランニングタイムを$O(d3)$から$O(domega + d2+a+o)$に改善する。この実行時間は、反復的なメンテナンス問題における遅延更新動作の分析によるものである。
参考スコア（独自算出の注目度）: 25.73901707554868
License: http://creativecommons.org/licenses/by/4.0/
Abstract: In this work, we improved the analysis of the running time of SparseGPT [Frantar, Alistarh ICML 2023] from $O(d^{3})$ to $O(d^{\omega} + d^{2+a+o(1)} + d^{1+\omega(1,1,a)-a})$ for any $a \in [0, 1]$, where $\omega$ is the exponent of matrix multiplication. In particular, for the current $\omega \approx 2.371$ [Alman, Duan, Williams, Xu, Xu, Zhou 2024], our running times boil down to $O(d^{2.53})$. This running time is due to the analysis of the lazy update behavior in iterative maintenance problems, such as [Deng, Song, Weinstein 2022, Brand, Song, Zhou ICML 2024].
Abstract（参考訳）: 本研究では, SparseGPT [Frantar, Alistarh ICML 2023] を$O(d^{3})$から$O(d^{\omega} + d^{2+a+o(1)} + d^{1+\omega(1,1,a)-a})$ の任意の $a \in [0,1]$ に対して, $\omega$ は行列乗算の指数である。特に、現在の$\omega \approx 2.371$ [Alman, Duan, Williams, Xu, Xu, Zhou 2024] の場合、実行時間は$O(d^{2.53})$に沸騰する。この実行時間は,[Deng, Song, Weinstein 2022, Brand, Song, Zhou ICML 2024] のような反復メンテナンス問題における遅延更新動作の分析によるものだ。

関連論文リスト

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)
Optimal bounds for $\ell_p$ sensitivity sampling via $\ell_2$ augmentation [56.403488578703865]
我々は$ell$ Sensitivities を $ell$ Sensitivities で拡張することにより、最適な線形 $tilde O(varepsilon-2mu2 d)$ サンプリング複雑性のより良い境界が得られることを示した。また、ロジスティック回帰のために、$tilde O(varepsilon-2mu2 d)$ sensitivity sample bound を得る。
論文参考訳（メタデータ） (2024-06-01T07:03:40Z)
$\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
コーディネータモデルにおける分散$ell_p$-regression問題のランダム化通信複雑性について考察する。 p = 2$、すなわち最小二乗回帰の場合、$tildeTheta(sd2 + sd/epsilon)$ bitsの最初の最適境界を与える。 p in (1,2)$ に対して、$tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound を得る。
論文参考訳（メタデータ） (2023-07-11T08:51:53Z)
Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces [2.687607197645453]
次元$Theta(log n)$ が $(sqrt3/2-o(1))$hard である場合でさえ、FPTアルゴリズムを近似する。また、次元 $Theta(log n)$ が $(sqrt3/2-o(1))$hard であるような特別な場合でさえ、FPTアルゴリズムを近似することを示す。
論文参考訳（メタデータ） (2023-05-12T08:43:28Z)
How the Move Acceptance Hyper-Heuristic Copes With Local Optima: Drastic Differences Between Jumps and Cliffs [6.793248433673384]
我々は, マルチモーダル崖ベンチマークの局所的最適度を, 高い効率で保ち, モブアクセプタンスハイパーヒューリスティック (MAHH) が最適であることを示す。また、局所的な1ビット演算子の代わりにグローバルビットワイズ演算子を持つMAHHがジャンプ関数を時間内に最適化することを示した。これは、いくつかの方法で局所最適に対処する方法を組み合わせることは、実りあるアプローチであることを示している。
論文参考訳（メタデータ） (2023-04-20T15:57:33Z)
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)
Reward-Mixing MDPs with a Few Latent Contexts are Learnable [75.17357040707347]
報酬混合マルコフ決定過程(RMMDP)におけるエピソード強化学習の検討我々のゴールは、そのようなモデルにおける時間段階の累積報酬をほぼ最大化する、ほぼ最適に近いポリシーを学ぶことである。
論文参考訳（メタデータ） (2022-10-05T22:52:00Z)
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)
An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文参考訳（メタデータ） (2020-08-24T06:50:57Z)
An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games and its Applications [28.54236118020831]
本稿では,最適な$O(n log (kappa))$オアラーク評価を用いた新しい切削平面アルゴリズムを提案する。また、評価毎に$n2$の時間を改善できないため、実行時間が最適であることを示す。
論文参考訳（メタデータ） (2020-04-08T20:56:40Z)

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