論文の概要: Optimality and NP-Hardness of Transformers in Learning Markovian Dynamical Functions

• arxiv url: http://arxiv.org/abs/2510.18638v1
• Date: Tue, 21 Oct 2025 13:42:48 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-25 03:08:13.634803
• Title: Optimality and NP-Hardness of Transformers in Learning Markovian Dynamical Functions
• Title（参考訳）: マルコフ力学関数学習における変圧器の最適性とNP-Hardness
• Authors: Yanna Ding, Songtao Lu, Yingdong Lu, Tomasz Nowicki, Jianxi Gao,
• Abstract要約: トランスフォーマーアーキテクチャは、インコンテキスト学習(ICL)による所定のプロンプトにおける入出力ペアに基づいて、目に見えないタスクを解決できる マルコフ関数学習の基盤となる最適化動作を明らかにするため,構造化ICL設定によるマルコフ関数学習について検討する。
• 参考スコア（独自算出の注目度）: 32.71332125930795
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Transformer architectures can solve unseen tasks based on input-output pairs in a given prompt due to in-context learning (ICL). Existing theoretical studies on ICL have mainly focused on linear regression tasks, often with i.i.d. inputs. To understand how transformers express ICL when modeling dynamics-driven functions, we investigate Markovian function learning through a structured ICL setup, where we characterize the loss landscape to reveal underlying optimization behaviors. Specifically, we (1) provide the closed-form expression of the global minimizer (in an enlarged parameter space) for a single-layer linear self-attention (LSA) model; (2) prove that recovering transformer parameters that realize the optimal solution is NP-hard in general, revealing a fundamental limitation of one-layer LSA in representing structured dynamical functions; and (3) supply a novel interpretation of a multilayer LSA as performing preconditioned gradient descent to optimize multiple objectives beyond the square loss. These theoretical results are numerically validated using simplified transformers.
• Abstract（参考訳）: トランスフォーマーアーキテクチャは、インコンテキスト学習(ICL)によって与えられたプロンプトで入力と出力のペアに基づいて見えないタスクを解くことができる。 ICLに関する既存の理論的研究は、主に線形回帰タスクに焦点を合わせており、しばしば入出力に焦点が当てられている。 動的関数のモデル化における変換器の表現方法を理解するため,構造化ICL設定によるマルコフ関数の学習について検討し,損失景観を特徴付けることにより,基礎となる最適化動作を明らかにする。 具体的には,(1) 単一層線形自己アテンション(LSA)モデルに対する大域最小化器(拡張パラメータ空間)の閉形式表現,(2) 最適解を実現するトランスフォーマーパラメータの復元がNPハードであることの証明,(3) 構造的力学関数を表す1層LSAの基本的な制限,(3) 複数層LSAの新たな解釈を提供することにより,平方損失を超えて複数の目的を最適化する。 これらの理論結果は、単純化された変圧器を用いて数値的に検証される。

関連論文リスト

• Graded Transformers [0.0]
  そこで我々は,ベクトル空間上のグレーディングを通じて帰納バイアスを埋め込む新しいシーケンスモデルである Graded Transformer フレームワークを紹介した。 このフレームワークは、以前のモデルの固定グレードの制限を克服し、適応的な特徴優先順位付けを可能にする。 Graded Transformerは、階層的学習とニューロシンボリック推論に対する数学的に原則化されたアプローチを提供する。
  論文  参考訳（メタデータ） (2025-07-27T02:34:08Z)
• Exact Learning Dynamics of In-Context Learning in Linear Transformers and Its Application to Non-Linear Transformers [1.7034813545878589]
  トランスフォーマーモデルは、顕著なインコンテキスト学習(ICL)を示す 我々の研究は、ICLの正確な動的モデルを提供し、複雑なトランスフォーマートレーニングを解析するための理論的基盤ツールを提供する。
  論文  参考訳（メタデータ） (2025-04-17T13:05:33Z)
• How Do Nonlinear Transformers Learn and Generalize in In-Context Learning? [82.51626700527837]
  トランスフォーマーベースの大規模言語モデルでは、トレーニング済みのモデルが微調整なしで新しいタスクを処理できるような、コンテキスト内学習機能が印象的だった。 我々は、TransformerがICLを実現する方法の仕組みが、Transformerにおけるトレーニング問題の技術的課題にどのように貢献するかを分析する。
  論文  参考訳（メタデータ） (2024-02-23T21:07:20Z)
• How Do Transformers Learn In-Context Beyond Simple Functions? A Case Study on Learning with Representations [98.7450564309923]
  本稿では、より複雑なシナリオにおける文脈内学習(ICL)の理解を、表現を用いた学習で研究する。 合成文内学習問題を合成構造を用いて構築し、ラベルは複雑なが固定された表現関数によって入力に依存する。 理論的には、そのようなアルゴリズムを軽度な深さと大きさでほぼ実装するトランスフォーマーの存在を示す。
  論文  参考訳（メタデータ） (2023-10-16T17:40:49Z)
• Transformers as Statisticians: Provable In-Context Learning with In-Context Algorithm Selection [88.23337313766353]
  この研究はまず、変換器がICLを実行するための包括的な統計理論を提供する。 コンテクストにおいて、トランスフォーマーは、幅広い種類の標準機械学習アルゴリズムを実装可能であることを示す。 エンフィングル変換器は、異なるベースICLアルゴリズムを適応的に選択することができる。
  論文  参考訳（メタデータ） (2023-06-07T17:59:31Z)

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

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