論文の概要: Computational-Statistical Tradeoffs at the Next-Token Prediction Barrier: Autoregressive and Imitation Learning under Misspecification

• arxiv url: http://arxiv.org/abs/2502.12465v1
• Date: Tue, 18 Feb 2025 02:52:00 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-19 14:05:47.095628
• Title: Computational-Statistical Tradeoffs at the Next-Token Prediction Barrier: Autoregressive and Imitation Learning under Misspecification
• Title（参考訳）: 次世代予測障壁における計算統計的トレードオフ--ミス種別による自己回帰学習と模倣学習-
• Authors: Dhruv Rohatgi, Adam Block, Audrey Huang, Akshay Krishnamurthy, Dylan J. Foster,
• Abstract要約: 対数損失を伴う次のトーケン予測は自己回帰シーケンスモデリングの基盤となる。 次トーケン予測は、適度な誤差増幅を表す$C=tilde O(H)$を達成するために堅牢にすることができる。 C=e(log H)1-Omega(1)$。
• 参考スコア（独自算出の注目度）: 50.717692060500696
• License:
• Abstract: Next-token prediction with the logarithmic loss is a cornerstone of autoregressive sequence modeling, but, in practice, suffers from error amplification, where errors in the model compound and generation quality degrades as sequence length $H$ increases. From a theoretical perspective, this phenomenon should not appear in well-specified settings, and, indeed, a growing body of empirical work hypothesizes that misspecification, where the learner is not sufficiently expressive to represent the target distribution, may be the root cause. Under misspecification -- where the goal is to learn as well as the best-in-class model up to a multiplicative approximation factor $C\geq 1$ -- we confirm that $C$ indeed grows with $H$ for next-token prediction, lending theoretical support to this empirical hypothesis. We then ask whether this mode of error amplification is avoidable algorithmically, computationally, or information-theoretically, and uncover inherent computational-statistical tradeoffs. We show: (1) Information-theoretically, one can avoid error amplification and achieve $C=O(1)$. (2) Next-token prediction can be made robust so as to achieve $C=\tilde O(H)$, representing moderate error amplification, but this is an inherent barrier: any next-token prediction-style objective must suffer $C=\Omega(H)$. (3) For the natural testbed of autoregressive linear models, no computationally efficient algorithm can achieve sub-polynomial approximation factor $C=e^{(\log H)^{1-\Omega(1)}}$; however, at least for binary token spaces, one can smoothly trade compute for statistical power and improve on $C=\Omega(H)$ in sub-exponential time. Our results have consequences in the more general setting of imitation learning, where the widely-used behavior cloning algorithm generalizes next-token prediction.
• Abstract（参考訳）: 対数損失を伴う次のトーケン予測は自己回帰シーケンスモデリングの基盤となるが、実際には、モデル化合物の誤差と生成品質が、シーケンス長が$H$増加するにつれて低下するエラー増幅に悩まされる。 理論的な観点からは、この現象は適切に特定された環境では現れず、実際は、学習者が対象の分布を表現するのに十分な表現力を持たないような誤特定が根本原因であると仮説を立てる経験的作品が増えている。 ここでは、C$が次の予測のために$H$で成長し、この経験的仮説を理論的に支持することを確認する。 次に,この手法がアルゴリズム的に,計算的に,あるいは情報論的に回避可能かどうかを問うとともに,本質的に計算統計学的なトレードオフを明らかにする。 1)情報理論では、エラー増幅を回避し、$C=O(1)$を達成できる。 2) 次トーケン予測は、適度な誤差増幅を表す$C=\tilde O(H)$を達成するために頑健にすることができるが、これは固有の障壁である: 次トーケン予測スタイルの目的は、$C=\Omega(H)$を被らなければならない。 (3) 自己回帰線形モデルの自然なテストベッドでは、計算効率のよいアルゴリズムは、サブポリノミカル近似係数$C=e^{(\log H)^{1-\Omega(1)}}$を達成できないが、少なくとも二進トークン空間では、統計パワーの計算を円滑に交換し、サブ指数時間で$C=\Omega(H)$を改善することができる。 より一般的な模倣学習では、広く使われている行動クローニングアルゴリズムが次点予測を一般化する結果が得られます。

関連論文リスト

• Cross-validating causal discovery via Leave-One-Variable-Out [11.891940572224783]
  私たちは"Leave-One-Variable-Out (LOVO)"予測を使い、$Y$は$X$から推論されるが、$X$と$Y$は共同で観測されることはない。 Acyclic Directed Mixed Graphs (ADMGs) という形で、2つの部分集合上の因果モデルが、しばしば$X$ と $Y$ の依存関係に関する結論を導くことを示した。 この予測誤差は、$P(X, Y)$が利用可能であると仮定され、$X$と$Y$がfalの目的のために省略されているため推定できる。
  論文  参考訳（メタデータ） (2024-11-08T15:15:34Z)
• Theoretical limits of descending $\ell_0$ sparse-regression ML algorithms [0.0]
  本研究では,emphmaximum-likelihood (ML)デコーディングの性能解析プログラムを開発した。 ML性能パラメータの鍵となるのは、残留エンフェロ平均二乗誤差(textbfRMSE$)を発見し、いわゆるエンフェロ遷移(PT)現象を示す。 Fl RDTの具体的実装と実用的妥当性は、典型的には、基礎となる数値評価のサイズのセットを実行する能力に依存している。
  論文  参考訳（メタデータ） (2024-10-10T06:33:41Z)
• Scaling Laws in Linear Regression: Compute, Parameters, and Data [86.48154162485712]
  無限次元線形回帰セットアップにおけるスケーリング法則の理論について検討する。 テストエラーの再現可能な部分は$Theta(-(a-1) + N-(a-1)/a)$であることを示す。 我々の理論は経験的ニューラルスケーリング法則と一致し、数値シミュレーションによって検証される。
  論文  参考訳（メタデータ） (2024-06-12T17:53:29Z)
• Mind the Gap: A Causal Perspective on Bias Amplification in Prediction & Decision-Making [58.06306331390586]
  本稿では,閾値演算による予測値がS$変化の程度を測るマージン補数の概念を導入する。 適切な因果仮定の下では、予測スコア$S$に対する$X$の影響は、真の結果$Y$に対する$X$の影響に等しいことを示す。
  論文  参考訳（メタデータ） (2024-05-24T11:22:19Z)
• A Pseudo-Semantic Loss for Autoregressive Models with Logical Constraints [87.08677547257733]
  ニューロシンボリックAIは、純粋にシンボリックな学習とニューラルな学習のギャップを埋める。 本稿では,ニューラルネットワークの出力分布に対するシンボリック制約の可能性を最大化する方法を示す。 また,スドクと最短経路予測の手法を自己回帰世代として評価した。
  論文  参考訳（メタデータ） (2023-12-06T20:58:07Z)
• Towards Faster Non-Asymptotic Convergence for Diffusion-Based Generative Models [49.81937966106691]
  我々は拡散モデルのデータ生成過程を理解するための非漸近理論のスイートを開発する。 従来の研究とは対照的に,本理論は基本的だが多目的な非漸近的アプローチに基づいて開発されている。
  論文  参考訳（メタデータ） (2023-06-15T16:30:08Z)
• Stability and Risk Bounds of Iterative Hard Thresholding [41.082982732100696]
  アルゴリズム安定性の概念の下でIHTの新しいスパース一般化理論を導入する。 スパースレベル$k$のIHTは、スパース過剰リスクにおける収束率を$mathcaltilde O(n-1/2sqrtlog(n)log(p))$で楽しむことを示す。 理論的予測を確認するための予備的な数値的証拠が提供される。
  論文  参考訳（メタデータ） (2022-03-17T16:12:56Z)
• Exponential Error Suppression for Near-Term Quantum Devices [0.0]
  NISQ時代には、最小のQECでさえ採用するために必要な複雑さと規模は禁じられている。 観測可能な天体の期待値を推定する重要な場合において、実効的な指数的抑制を達成できることが示される。
  論文  参考訳（メタデータ） (2020-11-11T18:00:38Z)
• Estimating Stochastic Linear Combination of Non-linear Regressions Efficiently and Scalably [23.372021234032363]
  サブサンプルサイズが大きくなると、推定誤差が過度に犠牲になることを示す。 私たちの知る限りでは、線形テキスト+確率モデルが保証される最初の研究です。
  論文  参考訳（メタデータ） (2020-10-19T07:15:38Z)
• Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model [50.38446482252857]
  本稿では、生成モデル(シミュレータ)へのアクセスを想定して、強化学習のサンプル効率について検討する。 最初に$gamma$-discounted infinite-horizon Markov decision process (MDPs) with state space $mathcalS$ and action space $mathcalA$を考える。 対象の精度を考慮すれば,モデルに基づく計画アルゴリズムが最小限のサンプルの複雑さを実現するのに十分であることを示す。
  論文  参考訳（メタデータ） (2020-05-26T17:53:18Z)

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

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