論文の概要: Do Neural Networks Really Beat the Curse of Dimensionality? A Bit-Complexity View
- arxiv url: http://arxiv.org/abs/2608.01357v1
- Date: Sun, 02 Aug 2026 16:20:19 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-04 15:07:25.174479
- Title: Do Neural Networks Really Beat the Curse of Dimensionality? A Bit-Complexity View
- Title（参考訳）: ニューラルネットワークは次元の曲線を本当に上回るか? ビット複雑視
- Abstract要約: バイナリエンコーディングとメートル法エントロピーに基づく統一近似フレームワークを開発した。
パラメータではなくビット単位で複雑性を測定する場合、古典的アプローチによって達成された近似順序を根本的に上回る手法は存在しないことを示す。
- 参考スコア（独自算出の注目度）: 3.8969433233965205
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Traditional approximation theory measures convergence rates in terms of the number of parameters or degrees of freedom. However, practical computation operates under finite precision: parameters must be encoded using a finite number of bits. Therefore, approximation efficiency should be evaluated in terms of computational bit complexity, which is intrinsically connected to the metric entropy of the underlying function class. In this work, we develop a unified approximation framework based on binary encoding and metric entropy. We analyze classical methods (including polynomial approximation, sparse grids, and finite elements) as well as shallow and deep neural networks, and compare their approximation rates for function classes with comparable metric entropy. We observe that, when evaluated in terms of bits, most classical methods are in general suboptimal relative to the intrinsic limits dictated by metric entropy, while neural network methods may exhibit different behaviors. We show that when complexity is measured in bits rather than parameters, no method fundamentally exceeds the approximation order achieved by classical approaches. Our results also indicate that many seeming advantages of neural networks, including dimension-independent rates and superconvergence phenomena, stem from differences in function class complexity rather than intrinsic architectural superiority. In this sense, the traditional curse of dimensionality can be misleading; the fundamental limitation is instead a curse of bit complexity, governed by metric entropy.
- Abstract（参考訳）: 従来の近似理論は、パラメータの数や自由度の観点から収束率を測定する。
しかし、実用的な計算は有限の精度で動作し、パラメータは有限ビットでエンコードされなければならない。
したがって、近似効率は、基礎となる関数クラスの計量エントロピーと本質的に結びついている計算ビットの複雑さの観点から評価されるべきである。
本研究では,バイナリエンコーディングと計量エントロピーに基づく統一近似フレームワークを開発する。
我々は,古典的手法(多項式近似,スパースグリッド,有限要素を含む)と浅層および深部ニューラルネットワークを解析し,それらの近似率を,同等の計量エントロピーを持つ関数クラスと比較する。
我々は、ビットの観点から評価すると、ほとんどの古典的手法は、計量エントロピーによって決定される内在的限界に対して概ね最適であるのに対し、ニューラルネットワーク手法は異なる振る舞いを示す可能性があることを観察する。
パラメータではなくビット単位で複雑性を測定する場合、古典的アプローチによって達成された近似順序を根本的に上回る手法は存在しないことを示す。
また,本研究の結果から,次元非依存率や超収束現象などのニューラルネットワークの利点の多くは,本質的なアーキテクチャ上の優位性よりも関数クラスの複雑性の違いが原因であることが示唆された。
この意味では、伝統的な次元の呪いは誤解を招く可能性があり、基本的な制限は代わりに、計量エントロピーによって支配される、ビットの複雑さの呪いである。
関連論文リスト
- Algorithmic Foundations of Deep Learning: Complexity-Theoretic Rates and a Characterization of Universal Approximation [15.78691543310587]
ニューラルネットワークはフレキシブルな基底関数として、また計算のモデルとして見なされるべきであることを示す。
自然並列化条件を満たす任意の定義可能なNNモデルは、非アフィン非線形性を含む場合に限り、普遍近似であることを示す。
提案理論の範囲は,連続関数に対する普遍近似保証,ベソフ類に対する最小最適近似保証,正則関数に対する対数誤差複雑性,およびニュートン・ラフソン根探索や電力計算のような数値アルゴリズムをエミュレートできることを示す。
論文 参考訳（メタデータ） (2026-06-25T07:34:20Z) - The Error of Deep Operator Networks Is the Sum of Its Parts: Branch-Trunk and Mode Error Decompositions [45.88028371034407]
演算子学習は、微分方程式の解演算子を学習することによって、科学計算に強い影響を与える可能性がある。
普遍近似特性が証明されているにもかかわらず、ディープ作用素ネットワーク(DeepONets)は、実際は限られた精度と一般化を示すことが多い。
この研究は、古典的なDeepONetアーキテクチャのパフォーマンス制限を分析する。
論文 参考訳（メタデータ） (2026-02-25T13:38:08Z) - A Scalable Quantum Neural Network for Approximate SRBB-Based Unitary Synthesis [1.3108652488669736]
拡張性のある量子ニューラルネットワークは、任意のユニタリ進化を近似する手段として導入された。
SRBBベースの合成アルゴリズムは、実際のハードウェア上でもテストされる。
論文 参考訳（メタデータ） (2024-12-04T07:21:23Z) - Approximate Contraction of Arbitrary Tensor Networks with a Flexible and Efficient Density Matrix Algorithm [8.329034093208826]
低ランク近似を用いてテンソルネットワークの収縮を効率的に近似する手法を提案する。
提案アルゴリズムは,低ランク近似を行う場合,環境の大部分を組み込む柔軟性を有する。
論文 参考訳（メタデータ） (2024-06-14T07:13:52Z) - Structure-preserving neural networks for the regularized entropy-based closure of the Boltzmann moment system [3.437372707846067]
放射線輸送の大規模数値シミュレーションの主な課題は、高いメモリと計算時間要件である。
本研究では,エントロピー閉包法に対するニューラルネットワークに基づく近似を導出し,検討する。
本手法のメモリフットプリントは,競合時間とシミュレーション精度で従来の手法よりもはるかに少ないことを示す。
論文 参考訳（メタデータ） (2024-04-22T16:16:06Z) - Guaranteed Approximation Bounds for Mixed-Precision Neural Operators [83.64404557466528]
我々は、ニューラル演算子学習が本質的に近似誤差を誘導する直感の上に構築する。
提案手法では,GPUメモリ使用量を最大50%削減し,スループットを58%向上する。
論文 参考訳（メタデータ） (2023-07-27T17:42:06Z) - A comparison of rational and neural network based approximations [0.0]
有理近似,ニューラルネットワークおよびそれらの組み合わせを用いた関数近似の効率を比較する。
その結果、有理近似は、同じ数の決定変数を持つニューラルネットワークベースのアプローチよりも優れていることがわかった。
論文 参考訳（メタデータ） (2023-03-08T08:31:06Z) - Kernel-based off-policy estimation without overlap: Instance optimality
beyond semiparametric efficiency [53.90687548731265]
本研究では,観測データに基づいて線形関数を推定するための最適手順について検討する。
任意の凸および対称函数クラス $mathcalF$ に対して、平均二乗誤差で有界な非漸近局所ミニマックスを導出する。
論文 参考訳（メタデータ） (2023-01-16T02:57:37Z) - Statistically Meaningful Approximation: a Case Study on Approximating
Turing Machines with Transformers [50.85524803885483]
本研究は,統計的学習性を示すために近似ネットワークを必要とする統計有意(SM)近似の形式的定義を提案する。
回路とチューリングマシンの2つの機能クラスに対するSM近似について検討する。
論文 参考訳（メタデータ） (2021-07-28T04:28:55Z) - A Functional Perspective on Learning Symmetric Functions with Neural
Networks [48.80300074254758]
本研究では,測定値に基づいて定義されたニューラルネットワークの学習と表現について検討する。
正規化の異なる選択の下で近似と一般化境界を確立する。
得られたモデルは効率よく学習でき、入力サイズにまたがる一般化保証を享受できる。
論文 参考訳（メタデータ） (2020-08-16T16:34:33Z) - Refined bounds for algorithm configuration: The knife-edge of dual class
approximability [94.83809668933021]
トレーニングセットが、トレーニングセット上でのパラメータの平均メトリックのパフォーマンスが、予想される将来的なパフォーマンスに最も近いことを保証するために、どの程度の規模が必要かを調査する。
この近似が L-無限ノルムの下で成り立つなら、強いサンプル複雑性境界を与えることができる。
我々は、コンピュータ科学において最も強力なツールの一つである整数プログラミングの文脈において、我々の限界を実証的に評価する。
論文 参考訳（メタデータ） (2020-06-21T15:32:21Z) - Multipole Graph Neural Operator for Parametric Partial Differential
Equations [57.90284928158383]
物理系をシミュレーションするためのディープラーニングベースの手法を使用する際の大きな課題の1つは、物理ベースのデータの定式化である。
線形複雑度のみを用いて、あらゆる範囲の相互作用をキャプチャする、新しいマルチレベルグラフニューラルネットワークフレームワークを提案する。
実験により, 離散化不変解演算子をPDEに学習し, 線形時間で評価できることを確認した。
論文 参考訳（メタデータ） (2020-06-16T21:56:22Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。