論文の概要: Algorithmic Foundations of Deep Learning: Complexity-Theoretic Rates and a Characterization of Universal Approximation

• arxiv url: http://arxiv.org/abs/2606.26705v1
• Date: Thu, 25 Jun 2026 07:34:20 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-26 18:46:32.193545
• Title: Algorithmic Foundations of Deep Learning: Complexity-Theoretic Rates and a Characterization of Universal Approximation
• Title（参考訳）: 深層学習のアルゴリズム基礎:複雑度理論速度と普遍近似のキャラクタリゼーション
• Abstract要約: ニューラルネットワークはフレキシブルな基底関数として、また計算のモデルとして見なされるべきであることを示す。 自然並列化条件を満たす任意の定義可能なNNモデルは、非アフィン非線形性を含む場合に限り、普遍近似であることを示す。 提案理論の範囲は,連続関数に対する普遍近似保証,ベソフ類に対する最小最適近似保証,正則関数に対する対数誤差複雑性,およびニュートン・ラフソン根探索や電力計算のような数値アルゴリズムをエミュレートできることを示す。
• 参考スコア（独自算出の注目度）: 15.78691543310587
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Feedforward neural network (NN) expressivity is typically studied by emulating optimal basis-expansion schemes. While powerful, this perspective is incomplete: it primarily captures complexity through regularity, and therefore does not distinguish intuitively simple and complicated objects with comparable regularity, such as the square-root function and a typical Brownian path. The guiding message is that neural networks should be viewed not only as flexible basis functions, but also as models of computation. If a function is computable by a real-valued circuit over a prescribed elementary gate language, then it can be computed to comparable accuracy by an NN with explicit depth, width, and non-zero-parameter bounds controlled by the depth, width, gate count, and gate structure. Thus, neural-network complexity is not governed by regularity alone, but also by algorithmic complexity. We then show that any definable NN model satisfying a natural parallelization condition, allowing possibly multivariate non-linearities such as attention or layer normalization, is a universal approximator if and only if it contains a non-affine nonlinearity. The scope of our theory is illustrated by deducing universal approximation guarantees for continuous functions, minimax-optimal approximation guarantees for Besov classes, logarithmic-error complexity for holomorphic functions, and by showing that NNs can emulate numerical algorithms such as Newton-Raphson root finding and power iteration without architecture-specific arguments. Its precision is illustrated by shortest-path computation on $k$-vertex graphs: compiling the tropical dynamic-programming circuit yields NNs with O(log(1/ε)) non-zero parameters, exponentially improving in 1/ε over the generic $O(ε^{-c k^2})$ Lipschitz-approximation scale, for a constant c>0.
• Abstract（参考訳）: フィードフォワードニューラルネットワーク(NN)の表現性は、通常最適な基底展開スキームをエミュレートすることによって研究される。 強いが、この観点は不完全であり、主に正則性を通して複雑性を捉え、従って直観的に単純で複雑な対象を区別しない。 ニューラルネットワークはフレキシブルな基底関数としてだけでなく、計算のモデルとしても見なされるべきである。 関数が所定の基本ゲート言語上の実数値回路で計算可能であれば、その深さ、幅、ゲート数、ゲート構造によって制御される非零パラメータ境界を持つNNにより、同等の精度で計算することができる。 したがって、ニューラルネットワークの複雑さは正規性だけでなく、アルゴリズムの複雑さによっても支配される。 そして、自然並列化条件を満たす任意の定義可能なNNモデルは、注意や層正規化のような多変量非線型性を許容し、非アフィン非線形性を含む場合に限り、普遍近似であることを示す。 この理論の範囲は、連続関数に対する普遍近似保証の導出、ベソフ類に対する最小最適近似保証、正則関数に対する対数誤差の複雑さ、およびNNがアーキテクチャ固有の議論なしにニュートン・ラフソン根探索やパワーイテレーションなどの数値アルゴリズムをエミュレートできることを示せば説明できる。 その精度は、$k$-頂点グラフ上の最短パス計算によって示される: 熱帯の動的プログラミング回路は、O(log(1/ε))非ゼロパラメータでNNを出力し、通常の$O(ε^{-c k^2})$ Lipschitz-approximationスケールよりも指数関数的に1/εを改善する。

関連論文リスト

• The Descriptive Complexity of Graph Neural Networks [2.6728900378310514]
  グラフクエリはグラフニューラルネットワーク(GNN)の有界サイズファミリによって計算可能であることを示す。 GNNは、カウントとビルトインの関係を持つ一階述語論理のガードされた断片で定義できる。 GFO+Cでは1つのGNNで1つの線形アクティベーションと有理重みを持つクエリが組込み関係なく定義可能であることを示す。
  論文  参考訳（メタデータ） (2023-03-08T14:32:59Z)
• Gauss-Newton Temporal Difference Learning with Nonlinear Function Approximation [11.925232472331494]
  非線形関数近似を用いたQラーニング問題を解くため,ガウスニュートン時間差分法(GNTD)学習法を提案する。 各イテレーションにおいて、我々の手法は1つのガウスニュートン(GN)ステップを踏んで平均二乗ベルマン誤差(MSBE)の変種を最適化する。 いくつかのRLベンチマークにおいて、GNTDはTD型よりも高い報酬と高速な収束を示す。
  論文  参考訳（メタデータ） (2023-02-25T14:14:01Z)
• The Separation Capacity of Random Neural Networks [78.25060223808936]
  標準ガウス重みと一様分布バイアスを持つ十分に大きな2層ReLUネットワークは、この問題を高い確率で解くことができることを示す。 我々は、相互複雑性という新しい概念の観点から、データの関連構造を定量化する。
  論文  参考訳（メタデータ） (2021-07-31T10:25:26Z)
• Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers [50.85524803885483]
  本研究は,統計的学習性を示すために近似ネットワークを必要とする統計有意(SM)近似の形式的定義を提案する。 回路とチューリングマシンの2つの機能クラスに対するSM近似について検討する。
  論文  参考訳（メタデータ） (2021-07-28T04:28:55Z)
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces [208.67848059021915]
  強化学習のコアにおける探索・探索トレードオフについて検討する。 特に、関数クラス $mathcalF$ の複雑さが関数の複雑さを特徴づけていることを証明する。 私たちの後悔の限界はエピソードの数とは無関係です。
  論文  参考訳（メタデータ） (2020-11-09T18:32:22Z)
• Multipole Graph Neural Operator for Parametric Partial Differential Equations [57.90284928158383]
  物理系をシミュレーションするためのディープラーニングベースの手法を使用する際の大きな課題の1つは、物理ベースのデータの定式化である。 線形複雑度のみを用いて、あらゆる範囲の相互作用をキャプチャする、新しいマルチレベルグラフニューラルネットワークフレームワークを提案する。 実験により, 離散化不変解演算子をPDEに学習し, 線形時間で評価できることを確認した。
  論文  参考訳（メタデータ） (2020-06-16T21:56:22Z)
• Measuring Model Complexity of Neural Networks with Curve Activation Functions [100.98319505253797]
  本稿では,線形近似ニューラルネットワーク(LANN)を提案する。 ニューラルネットワークのトレーニングプロセスを実験的に検討し、オーバーフィッティングを検出する。 我々は、$L1$と$L2$正規化がモデルの複雑さの増加を抑制することを発見した。
  論文  参考訳（メタデータ） (2020-06-16T07:38:06Z)

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

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