無限幅トランスフォーマーのアルゴリズム的キャプチャ、計算複雑性、および帰納的バイアス
arXiv cs.LG / 2026/3/13
📰 ニュースIdeas & Deep AnalysisModels & Research
要点
- この論文は、アルゴリズムのグロッキング（アルゴリズムの理解）を、誤差を制御可能で最小限のサンプル適応とともに任意の問題サイズへ一般化するニューラルネットワークの能力として正式に定義し、真のアルゴリズム学習と統計的補間を区別する。
- 無限幅トランスフォーマーを遅延レジームとリッチレジームの両方で分析し、これらのネットワークが学習できる関数の推論時計算複雑性の上界を導出する。
- 著者らは、普遍的な表現力を持つにもかかわらず、Efficient Polynomial Time Heuristic Scheme（EPTHS）クラス内の低複雑度アルゴリズムへの帰納的バイアスを持つことを示す。このバイアスは高複雑度アルゴリズムを捉えることを妨げる一方、検索、コピー、ソートのようなより単純なタスクには成功を収める。
- この知見は、トランスフォーマーを用いたアルゴリズム一般化の限界を照らし、帰納的バイアスがネットワークが効果的に獲得できるアルゴリズムを制約することを強調する。
本文: arXiv:2603.11161v1 アナウンス種別: new
Abstract: アルゴリズムのグロッキング（すなわちアルゴリズムの理解）を、ニューラルネットワークが任意の問題サイズ（$T$）へ、制御可能な誤差と最小限のサンプル適応とともに一般化する能力として正式に定義し、真のアルゴリズム学習と統計的補間を区別します。無限幅トランスフォーマーを遅延（lazy）およびリッチ（rich）レジームの両方で分析することにより、これらのネットワークが学習できる関数の推論時計算複雑性の上界を導出します。普遍的な表現力を持つにもかかわらず、トランスフォーマーは Efficient Polynomial Time Heuristic Scheme（EPTHS）クラス内の低複雑度アルゴリズムへの帰納的バイアスを有することを示します。このバイアスは高複雑度アルゴリズムを捉えることを実質的に妨げる一方、検索、コピー、ソートのようなより単純なタスクには成功を許します。
