Fugu-MT 論文翻訳(概要): Tight Sample Complexity of Transformers

論文の概要: Tight Sample Complexity of Transformers

arxiv url: http://arxiv.org/abs/2606.09731v1
Date: Mon, 08 Jun 2026 16:56:24 GMT
ステータス: 翻訳完了
システム内更新日: 2026-06-09 14:42:07.574462
Title: Tight Sample Complexity of Transformers
Title（参考訳）: 変圧器の厚み試料複雑度
Abstract要約: We map a input sequence of length $T$ to a single output, established a upper bound of $O(L W log (T W))$ and a nearly matching lower bound of $(L W log (T W / L))$。さらに,教師の強制力を示すトランスフォーマーを用いたチェーン・オブ・シークレット学習の複雑さを強く特徴付ける。
参考スコア（独自算出の注目度）: 28.82044197167549
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We tightly characterize the VC dimension of depth-$L$ Transformers with a total of $W$ parameters, mapping an input sequence of length $T$ to a single output, establishing an upper bound of $O(L W \log (T W))$ and a nearly matching lower bound of $Ω(L W \log (T W / L))$. We further tightly characterize the sample complexity of chain-of-thought learning using such a Transformer, showing teacher forcing (i.e. selecting a predictor consistent with the entire chain-of-thought on training data) learns with sample complexity $O\left(L W \log \left(\left(T+T^{\prime}\right) W\right)\right)$ and that any learning rule that uses chain-of-thought data requires at least $Ω\left(L W \log \left(\left(T+T^{\prime}\right) W / L\right)\right)$ examples, where $T$ is the input length and $T^{\prime}$ is the number of autoregressive steps.
Abstract（参考訳）: We tightly characterize the VC dimension of depth-L$ Transformers with a total $W$ parameters, map a input sequence of length $T$ to a single output, established a upper bound of $O(L W \log (T W))$ and a almost matching lower bound of $Ω(L W \log (T W / L))$。さらに、このようなトランスフォーマーを用いたチェーン・オブ・シークレット学習のサンプル複雑性を強く特徴付け、教師の強制(すなわち、トレーニングデータ上でチェーン・オブ・シークレット全体と整合した予測子を選択する)がサンプルの複雑さで学習する$O\left(L W \log \left(\left(T+T^{\prime}\right) W\right)\right)$と、チェーン・オブ・シークレットデータを使用する学習ルールには少なくとも$Ω\left(L W \log \left(\left(T+T^{\prime}\right) W / L\right)\right)$$例を挙げる。

関連論文リスト

Gate-Efficient Implementation of the Query-Optimal Time-Dependent Hamiltonian Simulation [17.156227790252526]
q = Oleft(T + fraclog (1/varepsilon)logleft(e + log (1/varepsilon)/(T) right) 最適なクエリ複雑性を保ち、$Oleft[q left(a + logleft (1 + fracT(+ T)varepsilonを使用する同じアルゴリズムの実装を提供する。
論文参考訳（メタデータ） (2026-08-31T11:39:55Z)
Sharp Minimax Regret for Infinite-Memory Logistic Prediction [55.29259818039367]
Lag $j$はスケール$r_j$の予測に影響を与え、$n_T,j=T-j+1$の予測ラウンドに入る。すべての要約可能なエンベロープに対して、局所化された混合は$cR_T(r)leq C_T(r)$を証明する。指数関数やエンベロープの場合、有限サンプル条件の下では、トープリッツ・デサインの逆は$cR_T(r)geq c_T(r)$である。
論文参考訳（メタデータ） (2026-08-27T01:31:46Z)
On the Optimal Sample Complexity of Offline Multi-Armed Bandits with KL Regularization [54.77408659142336]
Kullback-Leibler (KL) の正規化は、オフラインの意思決定で広く使われている。大規模な正規化の下では$tildeO(SAC*/)$のサンプル複雑性を実現する。また、よりシャープなサンプル複雑性の下界も提供し、これは正規化強度の全範囲にわたる上界と一致する。
論文参考訳（メタデータ） (2026-05-04T01:46:35Z)
High-accuracy sampling for diffusion models and log-concave distributions [70.90863485771405]
本稿では,$mathrmpolylog (1/)$のステップで$$-errorを求める拡散モデルサンプリングアルゴリズムを提案する。我々の手法は、一般的なログ凹凸分布に対する最初の$mathrmpolylog (1/)$ complexity samplerをもたらす。
論文参考訳（メタデータ） (2026-02-01T17:05:31Z)
Provably Overwhelming Transformer Models with Designed Inputs [0.0]
この文字列で評価されたモデルの出力と任意の追加文字列$t$, $mathcalM(s + t)$が、長さ($t$)$leq n_free$のたびに$t$の値に完全に無関心である場合、$mathcalM$は$s$で圧倒される。我々は、モデルの振る舞いを束縛するために使う、特に強力な「オーバースカッシング」の最悪の形態を証明します。
論文参考訳（メタデータ） (2025-02-09T21:21:57Z)
Learning Orthogonal Multi-Index Models: A Fine-Grained Information Exponent Analysis [54.57279006229212]
情報指数は、オンライン勾配降下のサンプルの複雑さを予測する上で重要な役割を担っている。本研究では,2次項と高次項の両方を考慮することで,まず2次項を用いて関連する空間を学習できることを示す。オンラインSGDの全体サンプルと複雑さは$tildeO(d PL-1 )$である。
論文参考訳（メタデータ） (2024-10-13T00:14:08Z)
Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit [75.4661041626338]
単一インデックス対象関数 $f_*(boldsymbolx) = textstylesigma_*left(langleboldsymbolx,boldsymbolthetarangleright)$ の勾配勾配勾配学習問題について検討する。 SGDに基づくアルゴリズムにより最適化された2層ニューラルネットワークは、情報指数に支配されない複雑さで$f_*$を学習する。
論文参考訳（メタデータ） (2024-06-03T17:56:58Z)
On the Sample Complexity of Two-Layer Networks: Lipschitz vs. Element-Wise Lipschitz Activation [20.70453775428433]
本研究では,異なるアクティベーション関数を用いた有界二層ニューラルネットワークのサンプル複雑性について検討する。我々は、$sigma$ が要素ワイドであれば、$mathcalH$ のサンプルの複雑さは、幅の対数依存しか持たないことを証明する。
論文参考訳（メタデータ） (2022-11-17T16:27:15Z)
Optimal algorithms for learning quantum phase states [8.736370689844682]
未知の次数$d$相状態を学ぶ際のサンプルの複雑さは、分離可能な測定を許せば$Theta(nd)$であることを示す。また、f$がsparsity-$s$, degree-$d$を持つ場合の学習フェーズ状態も検討する。
論文参考訳（メタデータ） (2022-08-16T17:15:06Z)
Understanding and Compressing Music with Maximal Transformable Patterns [0.0]
点集合の最大パターンを探索するアルゴリズム、$DinmathbbRk$を提案する。また、これらの最大パターンのそれぞれに対して発生の集合を探索する第2のアルゴリズムを提案する。民謡旋律を調律語族に分類する作業において,3種類の異なる複雑性のクラスで新しい圧縮アルゴリズムを評価する。
論文参考訳（メタデータ） (2022-01-26T17:47:26Z)
$Q$-learning with Logarithmic Regret [60.24952657636464]
楽観的な$Q$は$mathcalOleft(fracSAcdot mathrmpolyleft(Hright)Delta_minlogleft(SATright)right)$ cumulative regret bound, where $S$ is the number of state, $A$ is the number of action, $H$ is the planning horizon, $T$ is the total number of steps, $Delta_min$ is the least sub-Optitimality gap。
論文参考訳（メタデータ） (2020-06-16T13:01:33Z)
Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
論文参考訳（メタデータ） (2020-06-06T13:34:41Z)
On the Modularity of Hypernetworks [103.1147622394852]
構造化対象関数の場合、ハイパーネットワークにおけるトレーニング可能なパラメータの総数は、標準ニューラルネットワークのトレーニング可能なパラメータの数や埋め込み法よりも桁違いに小さいことを示す。
論文参考訳（メタデータ） (2020-02-23T22:51:52Z)
Few-Shot Learning via Learning the Representation, Provably [115.7367053639605]
本稿では,表現学習による少数ショット学習について検討する。 1つのタスクは、ターゲットタスクのサンプルの複雑さを減らすために、$T$ソースタスクと$n_1$データを使用して表現を学習する。
論文参考訳（メタデータ） (2020-02-21T17:30:00Z)

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