論文の概要: Non-Asymptotic Length Generalization

• arxiv url: http://arxiv.org/abs/2506.03085v2
• Date: Fri, 06 Jun 2025 07:47:10 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-09 17:28:43.060168
• Title: Non-Asymptotic Length Generalization
• Title（参考訳）: 非漸近長一般化
• Authors: Thomas Chen, Tengyu Ma, Zhiyuan Li,
• Abstract要約: 理想化された設定において、様々な関数のクラスに対する長さ一般化の証明可能な保証を提供する。 本稿では,最小複雑度補間器学習アルゴリズムが最適長複雑性を実現することを示す。
• 参考スコア（独自算出の注目度）: 26.982645261213847
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Length generalization is the ability of a learning algorithm to learn a hypothesis which generalizes to longer inputs than the inputs in the training set. In this paper, we provide provable guarantees of length generalization for various classes of functions in an idealized setting. First, we formalize the framework of non-asymptotic length generalization, which requires a computable upper bound for the minimum input length that guarantees length generalization, as a function of the complexity of ground-truth function under some given complexity measure. We refer to this minimum input length to length generalize as length complexity. We show the Minimum-Complexity Interpolator learning algorithm achieves optimal length complexity. We further show that whether a function class admits non-asymptotic length generalization is equivalent to the decidability of its language equivalence problem, which implies that there is no computable upper bound for the length complexity of Context-Free Grammars. On the positive side, we show that the length complexity of Deterministic Finite Automata is $2n - 2$ where $n$ is the number of states of the ground-truth automaton. Our main results are upper bounds of length complexity for a subset of a transformer-related function class called C-RASP (Yang & Chiang, 2024). We show that the length complexity of 1-layer C-RASP functions is $O(T^2)$ when the ground-truth function has precision $T$, and that the length complexity of 2-layer C-RASP functions is $O(T^{O(K)})$ when the ground-truth function has precision $T$ and $K$ heads.
• Abstract（参考訳）: 長さ一般化は、学習アルゴリズムが学習セットの入力よりも長い入力に一般化する仮説を学習する能力である。 本稿では,様々な関数のクラスに対して,理想化された設定で長さ一般化の証明可能な保証を提供する。 まず、与えられた複雑性尺度の下での接地構造関数の複雑性の関数として、長さの一般化を保証する最小入力長に対して計算可能な上限を必要とする非漸近長一般化の枠組みを定式化する。 この最小入力長を、長さ複雑性として一般化する。 本稿では,最小複雑度補間器学習アルゴリズムが最適長複雑性を実現することを示す。 さらに,非漸近長一般化を許容する関数クラスが言語同値問題の決定可能性と同値であることを示す。 正の面では、決定論的有限オートマトンの長さの複雑さが2n - 2$であることを示す。 我々の主な結果は、C-RASP(Yang & Chiang, 2024)と呼ばれる変圧器関連関数クラスの部分集合に対する長さ複雑性の上限である。 1層C-RASP関数の長さ複雑性が$O(T^2)$,2層C-RASP関数の長さ複雑性が$O(T^{O(K)}$,2層C-RASP関数の長さ複雑性が$O(T^{O(K)}$であることを示す。

関連論文リスト

• Ehrenfeucht-Haussler Rank and Chain of Thought [51.33559894954108]
  関数の階数$f$は、単層トランスフォーマーデコーダで要求される思考の連鎖の最小値に対応することを示す。 また、ブール列における1の$k$-thの発生位置を同定する問題を解析し、$k$CoTステップが必要であることを証明した。
  論文  参考訳（メタデータ） (2025-01-22T16:30:58Z)
• Quantum computational complexity of matrix functions [2.7488316163114823]
  2つの原始問題の計算複雑性について検討する。 単項関数、チェビシェフ関数、時間発展関数、逆関数の4つの関数を考える。 各関数に対する両問題のBQP完全形式を同定する。
  論文  参考訳（メタデータ） (2024-10-17T18:00:03Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• Best of Both Worlds: Practical and Theoretically Optimal Submodular Maximization in Parallel [17.462968952951883]
  主アルゴリズムは、独立した関心を持つ可能性のある2つのコンポーネントから組み立てられる。 LINEARSEQの変種は、文献のどのアルゴリズムよりも小さい$O(log(n))$の適応複雑性を持つ。
  論文  参考訳（メタデータ） (2021-11-15T17:10:40Z)
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces [208.67848059021915]
  強化学習のコアにおける探索・探索トレードオフについて検討する。 特に、関数クラス $mathcalF$ の複雑さが関数の複雑さを特徴づけていることを証明する。 私たちの後悔の限界はエピソードの数とは無関係です。
  論文  参考訳（メタデータ） (2020-11-09T18:32:22Z)
• Hybrid Stochastic-Deterministic Minibatch Proximal Gradient: Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
  HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。 損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
  論文  参考訳（メタデータ） (2020-09-18T02:18:44Z)
• Refined bounds for algorithm configuration: The knife-edge of dual class approximability [94.83809668933021]
  トレーニングセットが、トレーニングセット上でのパラメータの平均メトリックのパフォーマンスが、予想される将来的なパフォーマンスに最も近いことを保証するために、どの程度の規模が必要かを調査する。 この近似が L-無限ノルムの下で成り立つなら、強いサンプル複雑性境界を与えることができる。 我々は、コンピュータ科学において最も強力なツールの一つである整数プログラミングの文脈において、我々の限界を実証的に評価する。
  論文  参考訳（メタデータ） (2020-06-21T15:32:21Z)

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

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