論文の概要: 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（参考訳）: 変圧器の厚み試料複雑度
• Authors: Chenxiao Yang, Nathan Srebro, Zhiyuan Li,
• 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)$$例を挙げる。

関連論文リスト

• 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)
• 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)
• 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)
• Few-Shot Learning via Learning the Representation, Provably [115.7367053639605]
  本稿では,表現学習による少数ショット学習について検討する。 1つのタスクは、ターゲットタスクのサンプルの複雑さを減らすために、$T$ソースタスクと$n_1$データを使用して表現を学習する。
  論文  参考訳（メタデータ） (2020-02-21T17:30:00Z)

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

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