論文の概要: Learnable Low-Rank Polynomial Sketch for Effective Linear Attention
- arxiv url: http://arxiv.org/abs/2610.14219v1
- Date: Fri, 09 Oct 2026 18:30:52 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-15 21:06:15.022715
- Title: Learnable Low-Rank Polynomial Sketch for Effective Linear Attention
- Title（参考訳）: 線形注意のための学習可能な低ランクポリノミアルスケッチ
- Abstract要約: トランスフォーマーにおけるソフトマックスの注意は、シーケンス長の2次計算の複雑さに悩まされており、長文のアプリケーションでは実用的ではない。
本稿では,カーネル近似の観点からも,既存の線形アテンション法が依然として最適であることを示す。
textbfLearnable textbfLow-Rank textbfPonomial bfSketch (LLoPS)を提案する。
- 参考スコア（独自算出の注目度）: 46.63417149494
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Softmax attention in Transformers suffers from quadratic complexity in sequence length, making it impractical for long-context applications. Linear attention alleviates this issue by replacing the exponential kernel with alternative functions that enable linear-time computation. Among existing linear attention approaches, recent studies have shown that polynomial kernels are particularly effective, as they exhibit sparse and spiky behavior similar to softmax attention, which emphasizes large dot products while suppressing irrelevant interactions. However, the exact computation of high-degree polynomial kernels is infeasible for high-dimensional representations. As a result, prior work relies on approximate polynomial kernels. This introduces a non-negligible approximation error. In this paper, we show that, from the perspective of polynomial kernel approximation, existing linear attention methods are still suboptimal. We propose \textbf{L}earnable \textbf{Lo}w-Rank \textbf{P}olynomial \textbf{S}ketch (LLoPS), a principled and flexible framework for approximating polynomial kernels with linear attention. Our method learns a low-rank polynomial sketch that provably achieves a strictly smaller approximation error than existing approaches. Experiment results show that LLoPS achieves the highest performance across extensive benchmarks, comparing with various linear attention baselines.
- Abstract（参考訳）: トランスフォーマーにおけるソフトマックスの注意は、シーケンス長の2次複雑さに悩まされており、長文の応用には実用的ではない。
線形注意(Linear attention)は、指数カーネルを線形時間計算を可能にする代替関数に置き換えることでこの問題を軽減する。
既存の線形アテンションアプローチの中で、多項式カーネルはソフトマックスアテンションに似たスパースでスパイクな振る舞いを示し、不適切な相互作用を抑えながら大きなドット積を強調するため、特に有効であることが最近の研究で示されている。
しかし、高次多項式カーネルの正確な計算は高次元表現では不可能である。
結果として、先行研究は近似多項式核に依存している。
これは無視できない近似誤差を導入する。
本稿では,多項式カーネル近似の観点からも,既存の線形アテンション法が依然として最適であることを示す。
本稿では,多項式カーネルを線形注意で近似する原理的かつ柔軟なフレームワークであるtextbf{L}earnable \textbf{Lo}w-Rank \textbf{P}olynomial \textbf{S}ketch (LLoPS)を提案する。
提案手法は,既存の手法よりも精度の低い近似誤差を確実に達成する低ランク多項式スケッチを学習する。
実験の結果,LLoPSは様々な線形アテンションベースラインと比較して,広範囲なベンチマークで最高の性能を発揮することがわかった。
関連論文リスト
- Sandwiching Polynomials for Geometric Concepts with Low Intrinsic Dimension [23.43080600040766]
そこで本研究では,いくつかの基本関数クラスと限界分布に対して,大幅に改良された次数境界が得られる低次サンドイッチ構築法を提案する。
我々の証明は比較的単純であり、ターゲット関数の境界の滑らかさを直接利用してサンドイッチング・リプシッツ関数を構築する。
論文 参考訳（メタデータ） (2026-02-27T16:59:18Z) - HLA: Hadamard Linear Attention [23.409131174857666]
注意機構は変圧器の成功の重要な理由である。
トークン間のペア関係の計算に依存する。
効率的な近似法として 線形注意法が提案されています
論文 参考訳（メタデータ） (2026-02-12T16:16:47Z) - Numerical Schemes for Signature Kernels [0.5461938536945723]
署名カーネルは、シーケンシャルデータのためのカーネルメソッドの強力なツールとして登場した。
近似法と境界法のいずれかを用いて境界条件の表現を利用する2つの高度な数値スキームを導入する。
我々のアルゴリズムはGPU並列化が可能であり、入力シーケンスの長さの2次から線形への計算複雑性を低減できる。
論文 参考訳（メタデータ） (2025-02-12T15:04:23Z) - Sparse Cholesky Factorization for Solving Nonlinear PDEs via Gaussian
Processes [3.750429354590631]
本稿では、高密度カーネル行列に対するスパースColesky分解アルゴリズムを提案する。
我々は, 幅広い非線形PDEのクラスに対して, アルゴリズムのニア線形空間/時間複雑性を数値的に説明する。
論文 参考訳（メタデータ） (2023-04-03T18:35:28Z) - Fast Sketching of Polynomial Kernels of Polynomial Degree [61.83993156683605]
他のカーネルはしばしばテイラー級数展開を通じてカーネルによって近似されるので、カーネルは特に重要である。
スケッチの最近の技術は、カーネルの$q$という難解な程度に実行時間に依存することを減らしている。
我々は、この実行時間を大幅に改善する新しいスケッチを、先頭の注文項で$q$への依存を取り除くことで提供します。
論文 参考訳（メタデータ） (2021-08-21T02:14:55Z) - Hybrid Trilinear and Bilinear Programming for Aligning Partially
Overlapping Point Sets [85.71360365315128]
多くの応用において、部分重なり合う点集合が対応するRPMアルゴリズムに不変であるようなアルゴリズムが必要である。
まず、目的が立方体有界関数であることを示し、次に、三線型および双線型単相変換の凸エンベロープを用いて、その下界を導出する。
次に、変換変数上の分岐のみを効率よく実行するブランチ・アンド・バウンド(BnB)アルゴリズムを開発する。
論文 参考訳（メタデータ） (2021-01-19T04:24:23Z) - Optimal oracle inequalities for solving projected fixed-point equations [53.31620399640334]
ヒルベルト空間の既知の低次元部分空間を探索することにより、確率観測の集合を用いて近似解を計算する手法を検討する。
本稿では,線形関数近似を用いた政策評価問題に対する時間差分学習手法の誤差を正確に評価する方法について述べる。
論文 参考訳（メタデータ） (2020-12-09T20:19:32Z) - Multipole Graph Neural Operator for Parametric Partial Differential
Equations [57.90284928158383]
物理系をシミュレーションするためのディープラーニングベースの手法を使用する際の大きな課題の1つは、物理ベースのデータの定式化である。
線形複雑度のみを用いて、あらゆる範囲の相互作用をキャプチャする、新しいマルチレベルグラフニューラルネットワークフレームワークを提案する。
実験により, 離散化不変解演算子をPDEに学習し, 線形時間で評価できることを確認した。
論文 参考訳（メタデータ） (2020-06-16T21:56:22Z) - Efficient Alternating Least Squares Algorithms for Low Multilinear Rank
Approximation of Tensors [6.308492837096872]
テンソルの低次階数近似を効率的に計算するための最小二乗(ALS)に基づく新しいクラスHOSVDアルゴリズムを提案する。
ALSに基づくアプローチは、中間行列の特異ベクトルの冗長な計算を排除し、したがってデータの爆発をなくすことができる。
合成および実世界の双方の大規模テンソルを用いた数値実験により、ALSベースの手法が原材料全体のコストを大幅に削減し、並列計算に非常にスケーラブルであることを示す。
論文 参考訳（メタデータ） (2020-04-06T11:58:04Z) - Improved guarantees and a multiple-descent curve for Column Subset
Selection and the Nystr\"om method [76.73096213472897]
我々は,データ行列のスペクトル特性を利用して近似保証を改良する手法を開発した。
我々のアプローチは、特異値減衰の既知の速度を持つデータセットのバウンダリが大幅に向上する。
RBFパラメータを変更すれば,改良された境界線と多重発振曲線の両方を実データセット上で観測できることが示される。
論文 参考訳（メタデータ） (2020-02-21T00:43:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。