Fugu-MT 論文翻訳(概要): The Optimal Sample Complexity of Learning Autoregressive Chain-of-Thought

論文の概要: The Optimal Sample Complexity of Learning Autoregressive Chain-of-Thought

arxiv url: http://arxiv.org/abs/2607.07423v1
Date: Wed, 08 Jul 2026 13:49:54 GMT
ステータス: 翻訳完了
システム内更新日: 2026-07-09 22:50:30.399648
Title: The Optimal Sample Complexity of Learning Autoregressive Chain-of-Thought
Title（参考訳）: 自己回帰的連鎖学習における最適サンプル複雑度
Abstract要約: 完全自己回帰的チェイン・オブ・サートトレースに対する完全トレース学習のサンプルの複雑さは、局所的な次トーケンクラスの標準マルチクラスレートによって上限づけられていることを証明する。しかし、停止ルールの$mathtthalt$とすべてのポイントワイズ$mathtthalt$-haltingローカルクラスに対して。 $operatornameDSdim(mathrmH)$への依存は最悪のケース最適である。
参考スコア（独自算出の注目度）: 8.076068840853512
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We prove that, in the realizable PAC setting, the sample complexity of exact-trace learning for full autoregressive Chain-of-Thought traces is upper bounded by the standard multiclass rate of the local next-token class, where this rate is governed by the Daniely--Shalev-Shwartz dimension. Under exact-trace loss, one wrong action makes the whole trace incorrect; nevertheless, for every stopping rule $\mathtt{halt}$ and every pointwise $\mathtt{halt}$-halting local class $\mathrm{H}$, $n_{\mathrm{PAC}}^{\varepsilon,δ}(\operatorname{Roll}_{\mathtt{halt}}(\mathrm{H}))=O((\operatorname{DSdim}(\mathrm{H})+\log(1/δ))/\varepsilon)$, with no dependence on rollout length. The dependence on $\operatorname{DSdim}(\mathrm{H})$ is worst-case optimal, since one-step stopping recovers ordinary multiclass learning of $\mathrm{H}$. The proof introduces parity dimension, a rollout-stable refinement of DS dimension based on even pseudo-cubes. It controls one-inclusion density via a low-coordinate spanning theorem on finite restrictions and, unlike DS dimension itself, does not increase under autoregressive rollout. We also show why this detour is necessary: DS dimension can increase under rollout.
Abstract（参考訳）: 実化可能なPAC設定では、完全自己回帰的連鎖-フォールトトレースに対する完全トレース学習のサンプル複雑性は、局所次トーケンクラスの標準マルチクラスレートによって上界化され、このレートはダニー-シャレフ-シュワルツ次元によって支配される。しかし、すべての停止規則に対して$\mathtt{halt}$とすべての点に対して$\mathtt{halt}$-halting local class $\mathrm{H}$, $n_{\mathrm{PAC}}^{\varepsilon,δ}(\operatorname{Roll}_{\matht{halt}}(\mathrm{H}))=O(\operatorname{DSdim}(\mathrm{H})+\log(1/δ))/\varepsilon$はロールアウト長に依存しない。 $\operatorname{DSdim}(\mathrm{H})$への依存は最悪のケース最適であり、一段階停止すると$\mathrm{H}$の通常のマルチクラス学習が回復する。この証明は、たとえ疑似キューブにもとづくDS次元のロールアウト安定改良であるパリティ次元を導入している。有限制限上の低座標スパンニング定理(英語版)を通して一包含密度を制御し、DS次元自身とは異なり、自己回帰的なロールアウトでは増加しない。 DS次元はロールアウト時に増大する可能性がある。

関連論文リスト

Gradient-Free Warm-Start Library Recovery: an Amortized-Regret Separation [0.0]
勾配のない継続的学習、ローカル、オンライン、追加のみの学習は、エッジとストリーミングデプロイメントにとって魅力的なものだ。繰り返し再生するストリームについて、証明可能な説明をします。
論文参考訳（メタデータ） (2026-06-19T09:30:55Z)
Online Realizable Regression and Applications for ReLU Networks [14.292982828097465]
近似三角形の不等式を満たす損失(擬似測度)下での対向モデルにおける実現可能なオンライン回帰について検討する。我々の主な貢献は、具体的なダドリー型エントロピー積分により、$mathbbD_mathrmonl$を上界とする一般ポテンシャル法である。
論文参考訳（メタデータ） (2026-02-22T13:02:25Z)
The Hidden Width of Deep ResNets: Tight Error Bounds and Phase Diagrams [15.246178589173523]
大深度残差ネットワーク(ResNets)の勾配に基づくトレーニングについて検討する。可変深さ$L$,固定埋め込み寸法$D$,任意の隠れ幅$M$で、トレーニングダイナミクスはニューラル平均ODEトレーニングダイナミクスに収束することを示す。
論文参考訳（メタデータ） (2025-09-12T11:51:44Z)
Provably Adaptive Average Reward Reinforcement Learning for Metric Spaces [2.2984209387877628]
本稿では, 適応アルゴリズム $textZoRL$ を $mathcalObig に限定して開発する。 $textZoRL$ は状態アクション空間を適応的に離散化し、状態アクション空間の 'promising region'' に拡大することでこれを達成します。ズーム次元と$textZoRL$は真に適応的であり、すなわち、現在の研究は、無限水平平均逆 RL に対する適応性ゲインを捉える方法を示している。
論文参考訳（メタデータ） (2024-10-25T18:14:42Z)
Monge-Kantorovich Fitting With Sobolev Budgets [6.748324975906262]
我々は、$rho$が$mtext-d$集合の近くに集中しているとき、これをノイズのあるデータを持つ多様体学習問題と解釈できることを示した。 Monge-Kantorovich $p$-cost $mathbbW_pp(rho, nu)$を介して$rho$を近似する際の$nu$のパフォーマンスを定量化し、$mathrmsupp nu$を$f : mathbbRmでカバーできるようにすることで複雑さを制限します。
論文参考訳（メタデータ） (2024-09-25T01:30:16Z)
Policy Zooming: Adaptive Discretization-based Infinite-Horizon Average-Reward Reinforcement Learning [2.2984209387877628]
無限水平平均逆強化学習(RL)におけるリプシッツ MDP について検討した。 for $d_texteff. = dPhi_z+2$ for model-free algorithmtextitPZRL-MF and $d_texteff. = 2d_mathcalS + dPhi_z + 3$ for
論文参考訳（メタデータ） (2024-05-29T06:18:09Z)
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)
Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPs [72.40181882916089]
我々のアルゴリズムが $tildeObig((d+log (|mathcalS|2 |mathcalA|))sqrtKbig)$ regret with full-information feedback, where $d$ is the dimension of a known feature mapping is linearly parametrizing the unknown transition kernel of the MDP, $K$ is the number of episodes, $|mathcalS|$ and $|mathcalA|$ is the standardities of the state and action space。
論文参考訳（メタデータ） (2023-05-15T05:37:32Z)
Differentially Private Stochastic Gradient Descent with Low-Noise [49.981789906200035]
現代の機械学習アルゴリズムは、データからきめ細かい情報を抽出して正確な予測を提供することを目的としており、プライバシー保護の目標と矛盾することが多い。本稿では、プライバシを保ちながら優れたパフォーマンスを確保するために、プライバシを保存する機械学習アルゴリズムを開発することの実践的および理論的重要性について論じる。
論文参考訳（メタデータ） (2022-09-09T08:54:13Z)
Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文参考訳（メタデータ） (2022-06-17T17:55:43Z)
The Curse of Passive Data Collection in Batch Reinforcement Learning [82.6026077420886]
高い利害関係のアプリケーションでは、アクティブな実験は危険すぎると考えられ、データはしばしば受動的に収集される。バンディットやパッシブ、アクティブなデータ収集などの単純な場合も同様に効果的であるが、制御された状態のシステムからデータを集める場合、パッシブサンプリングの価格ははるかに高い。
論文参考訳（メタデータ） (2021-06-18T07:54:23Z)
Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
我々は,バンディットフィードバックを用いてオンライン学習を学習する。 learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
論文参考訳（メタデータ） (2021-02-15T08:16:51Z)
Agnostic Learning of a Single Neuron with Gradient Descent [92.7662890047311]
期待される正方形損失から、最も適合した単一ニューロンを学習することの問題点を考察する。 ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。 ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
論文参考訳（メタデータ） (2020-05-29T07:20:35Z)
Naive Exploration is Optimal for Online LQR [49.681825576239355]
最適後悔尺度は$widetildeTheta(sqrtd_mathbfu2 d_mathbfx T)$で、$T$は時間ステップの数、$d_mathbfu$は入力空間の次元、$d_mathbfx$はシステム状態の次元である。我々の下界は、かつての$mathrmpoly(logT)$-regretアルゴリズムの可能性を排除する。
論文参考訳（メタデータ） (2020-01-27T03:44:54Z)

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

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