論文の概要: Stochastic Autoregressive Learning

• arxiv url: http://arxiv.org/abs/2608.07224v1
• Date: Fri, 07 Aug 2026 13:40:17 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-10 16:21:25.521885
• Title: Stochastic Autoregressive Learning
• Title（参考訳）: 確率的自己回帰学習
• Abstract要約: 連立自己回帰学習のためのPAC学習モデルを提案する。 自己回帰学習が決定論的理論と根本的に異なることを示す。
• 参考スコア（独自算出の注目度）: 14.292982828097465
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Motivated by LLMs, which generate outputs by iteratively sampling from next-token distributions, we introduce a PAC-learning model for binary stochastic autoregressive learning. This generalizes the deterministic autoregressive learning framework of Joshi et al., COLT 2025. In our model, one fixed generator assigns a Bernoulli next-token distribution to every prompt string. Starting from an input prompt, a token is sampled and appended to the prompt; the same generator is then applied again to this expanded prompt; this procedure is repeated for $M$ steps. Three forms of supervision are considered: base one-step samples, chain-of-thought (CoT) samples that reveal full random trajectories of length $M$, and end-to-end (e2e) samples that reveal only the final token of length $M$ trajectories. For a generator class, we study the minimum number of samples $m_{base}(\varepsilon),m_{CoT}(\varepsilon), m_{e2e}(\varepsilon)$, resp., required to learn the one-step probabilities in the base model, and the final-token probability in the CoT and e2e models, under squared loss error~$\varepsilon$. We show that stochastic autoregressive learning fundamentally differs from the deterministic theory. At scale $\varepsilon$, there is no universal comparison between the three learning tasks: both $m_{CoT}/m_{base}$ and $m_{e2e}/m_{CoT}$ can be made simultaneously arbitrarily larger than $M/\varepsilon$, the natural analogue for the existing deterministic results. Nevertheless, after altering scales, for every class, CoT learning at scale $\varepsilon$ is upper-bounded by base learning at scale $\varepsilon/M^2$, whereas e2e learning at scale $\varepsilon$ is upper-bounded, up to logarithmic factors, by $(M/\varepsilon) m_{CoT}(Θ(\varepsilon))$. These dependencies and scales are essentially tight. We complement these bounds by studying dimension $d$ logistic functions in our model.
• Abstract（参考訳）: 次点分布から繰り返しサンプリングすることで出力を生成するLLMをモチベーションとして,二元確率自己回帰学習のためのPAC学習モデルを提案する。 これは、Joshi et al , COLT 2025の決定論的自己回帰学習フレームワークを一般化する。 我々のモデルでは、1つの固定生成器がすべてのプロンプト文字列にベルヌーイ次トーケン分布を割り当てる。 入力プロンプトからトークンをサンプリングし、プロンプトに付加し、同じジェネレータをこの拡張プロンプトに再度適用する。 基本的な一段階のサンプル、長さ$M$の完全なランダムな軌跡を示すチェーンオブシント(CoT)サンプル、長さ$M$の最終的なトークンのみを示すエンドツーエンド(e2e)サンプルである。 ジェネレータクラスでは、サンプルの最小値 $m_{base}(\varepsilon), m_{CoT}(\varepsilon), m_{e2e}(\varepsilon)$, resp を調べる。 ベースモデルの1ステップ確率と、CoTおよびe2eモデルの最終的な確率を2乗損失誤差~$\varepsilon$で学習する必要がある。 確率的自己回帰学習は決定論的理論と根本的に異なることを示す。 m_{CoT}/m_{base}$ と $m_{e2e}/m_{CoT}$ は、既存の決定論的結果の自然な類似である$M/\varepsilon$ よりも同時に大きい。 それにもかかわらず、スケールを変更した後、すべてのクラスにおいて、スケールでのCoT学習は、スケールでのベースラーニングによって上界に$\varepsilon/M^2$、スケールでのe2e学習は、(M/\varepsilon) m_{CoT}( )$で上界に$\varepsilon$がある。 これらの依存関係とスケールは本質的に厳密です。 モデルの次元$d$ロジスティック関数を研究することで、これらの境界を補完する。

関連論文リスト

• Efficient Sample-optimal Learning of Gaussian Tree Models via Sample-optimal Testing of Gaussian Mutual Information [1.7419682548187605]
  ガウス確率変数に対する条件付き相互情報テスタを開発した。 条件付き相互情報の連鎖ルールは、推定された(条件付き)相互情報の保持を継続することを示す。 また、基礎となるガウスモデルが木構造であることが分かっていない場合、$widetildeTheta(n2varepsilon-2)$サンプルが必要であることも示している。
  論文  参考訳（メタデータ） (2024-11-18T12:25:34Z)
• 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)
• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。 我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。 我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
  論文  参考訳（メタデータ） (2024-05-10T09:58:47Z)
• Approximation Rates and VC-Dimension Bounds for (P)ReLU MLP Mixture of Experts [17.022107735675046]
  Mixture-of-Experts(MoEs)は、従来のディープラーニングモデルを越えてスケールアップすることができる。 MoMLPモデル全体のVC次元が$tildeO(LmaxnL,JW)$であるので、MoMLPが一般化可能であることを示す。
  論文  参考訳（メタデータ） (2024-02-05T19:11:57Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。 本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。 また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
  論文  参考訳（メタデータ） (2023-09-25T17:54:19Z)
• Replicability in Reinforcement Learning [46.89386344741442]
  生成モデルにアクセス可能なディスカウント型MDPの基本設定に焦点をあてる。 ImpagliazzoらにインスパイアされたRLアルゴリズムは、高い確率で2回の実行後に全く同じポリシーを出力した場合、複製可能である。
  論文  参考訳（メタデータ） (2023-05-31T05:16:23Z)
• Efficient Sampling of Stochastic Differential Equations with Positive Semi-Definite Models [91.22420505636006]
  本稿では, ドリフト関数と拡散行列を考慮し, 微分方程式からの効率的なサンプリング問題を扱う。 1/varepsilonは$m2d log (1/varepsilon)$である。 以上の結果から,真の解がより滑らかになるにつれて,どのような凸性も必要とせず,次元の呪いを回避できることが示唆された。
  論文  参考訳（メタデータ） (2023-03-30T02:50:49Z)
• Tight Bounds on the Hardness of Learning Simple Nonparametric Mixtures [9.053430799456587]
  有限混合系における非パラメトリック分布の学習問題について検討する。 このようなモデルにおける成分分布を学習するために、サンプルの複雑さに厳密な境界を定めている。
  論文  参考訳（メタデータ） (2022-03-28T23:53:48Z)
• Reward-Free Model-Based Reinforcement Learning with Linear Function Approximation [92.99933928528797]
  エピソードマルコフ決定過程(MDP)に対する線形関数近似を用いたモデルに基づく無報酬強化学習について検討する。 計画段階では、特定の報酬関数が与えられ、探索フェーズから収集したサンプルを使用して良い政策を学ぶ。 任意の報酬関数に対して$epsilon$-optimal Policyを得るには,最大$tilde O(H4d(H + d)epsilon-2)$ episodesをサンプリングする必要がある。
  論文  参考訳（メタデータ） (2021-10-12T23:03:58Z)
• Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Model [3.749193647980305]
  本稿では,一連の状態対応機能を有するマルコフ決定プロセス(MDP)について考察する。 モデルに基づくアプローチ(resp.$Q-learning)が、高い確率で$varepsilon$-Optimalポリシーを確実に学習することを示す。
  論文  参考訳（メタデータ） (2021-05-28T17:49:39Z)
• 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)

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

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