論文の概要: Training Fully Connected Neural Networks is $\exists\mathbb{R}$-Complete
- arxiv url: http://arxiv.org/abs/2204.01368v3
- Date: Fri, 22 Mar 2024 09:42:26 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-26 00:08:10.452503
- Title: Training Fully Connected Neural Networks is $\exists\mathbb{R}$-Complete
- Title（参考訳）: フル接続ニューラルネットワークのトレーニングは$\exists\mathbb{R}$-Complete
- Authors: Daniel Bertschinger, Christoph Hertrich, Paul Jungeblut, Tillmann Miltzow, Simon Weber,
- Abstract要約: InpiricalRiskmization(英語版)として知られる、与えられたデータポイントのセットに可能な限り適合する2層完全連結ニューラルネットワークの重みとバイアスを求める問題を考察する。
任意のデータポイントが有理である場合でも、いくつかのインスタンスを最適に訓練できるウェイトとして、任意の大きな次数の代数数が必要であることを証明します。
この結果、Basu, Mianjy, Mukherjee [ICLR 2018]のような検索アルゴリズムは、$mathsfNP=existsでない限り、複数の出力次元を持つネットワークでは不可能である。
- 参考スコア（独自算出の注目度）: 4.170994234169557
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the problem of finding weights and biases for a two-layer fully connected neural network to fit a given set of data points as well as possible, also known as EmpiricalRiskMinimization. Our main result is that the associated decision problem is $\exists\mathbb{R}$-complete, that is, polynomial-time equivalent to determining whether a multivariate polynomial with integer coefficients has any real roots. Furthermore, we prove that algebraic numbers of arbitrarily large degree are required as weights to be able to train some instances to optimality, even if all data points are rational. Our result already applies to fully connected instances with two inputs, two outputs, and one hidden layer of ReLU neurons. Thereby, we strengthen a result by Abrahamsen, Kleist and Miltzow [NeurIPS 2021]. A consequence of this is that a combinatorial search algorithm like the one by Arora, Basu, Mianjy and Mukherjee [ICLR 2018] is impossible for networks with more than one output dimension, unless $\mathsf{NP}=\exists\mathbb{R}$.
- Abstract（参考訳）: InpiricalRiskMinimization (EmpiricalRiskMinimization) として知られる,2層完全連結ニューラルネットワークの重みとバイアスを求める問題について考察する。
我々の主な結果は、関連する決定問題は$\exists\mathbb{R}$-complete、すなわち、整数係数を持つ多変量多項式が実根を持つかどうかを決定する多項式時間である。
さらに、任意のデータポイントが有理である場合でも、いくつかのインスタンスを最適に訓練できるウェイトとして、任意の大きな代数的数の代数的数が必要であることを証明している。
この結果は、ReLUニューロンの2つの入力、2つの出力と1つの隠れた層を持つ完全に接続されたインスタンスに適用できる。
これにより、Abrahamsen, Kleist and Miltzow [NeurIPS 2021]による結果が強化される。
その結果、Arora, Basu, Mianjy, Mukherjee (ICLR 2018) のような組合せ探索アルゴリズムは、$\mathsf{NP}=\exists\mathbb{R}$でない限り、複数の出力次元を持つネットワークでは不可能である。
関連論文リスト
- Deep Neural Networks: Multi-Classification and Universal Approximation [0.0]
我々は,幅2ドル,深さ2N+4M-1$のReLUディープニューラルネットワークが,$N$要素からなる任意のデータセットに対して有限標本記憶を達成できることを実証した。
また、$W1,p$関数を近似するための深さ推定と$Lp(Omega;mathbbRm)$ for $mgeq1$を近似するための幅推定も提供する。
論文 参考訳（メタデータ） (2024-09-10T14:31:21Z) - Learning sum of diverse features: computational hardness and efficient gradient-based training for ridge combinations [40.77319247558742]
目的関数 $f_*:mathbbRdtomathbbR$ を加法構造で学習する際の計算複雑性について検討する。
2層ニューラルネットワークの勾配学習により,$f_*$の大規模なサブセットを効率的に学習できることを実証した。
論文 参考訳（メタデータ） (2024-06-17T17:59:17Z) - Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit [75.4661041626338]
単一インデックス対象関数 $f_*(boldsymbolx) = textstylesigma_*left(langleboldsymbolx,boldsymbolthetarangleright)$ の等方的ガウスデータの下で勾配降下学習の問題を考察する。
SGDアルゴリズムで最適化された2層ニューラルネットワークは、サンプル付き任意のリンク関数の$f_*$を学習し、実行時の複雑さは$n asymp T asymp C(q) cdot dであることを示す。
論文 参考訳（メタデータ） (2024-06-03T17:56:58Z) - Learning Hierarchical Polynomials with Three-Layer Neural Networks [56.71223169861528]
3層ニューラルネットワークを用いた標準ガウス分布における階層関数の学習問題について検討する。
次数$k$s$p$の大規模なサブクラスの場合、正方形損失における階層的勾配によるトレーニングを受けた3層ニューラルネットワークは、テストエラーを消すためにターゲット$h$を学習する。
この研究は、3層ニューラルネットワークが複雑な特徴を学習し、その結果、幅広い階層関数のクラスを学ぶ能力を示す。
論文 参考訳（メタデータ） (2023-11-23T02:19:32Z) - Bounding the Width of Neural Networks via Coupled Initialization -- A
Worst Case Analysis [121.9821494461427]
2層ReLUネットワークに必要なニューロン数を著しく削減する方法を示す。
また、事前の作業を改善するための新しい下位境界を証明し、ある仮定の下では、最善を尽くすことができることを証明します。
論文 参考訳（メタデータ） (2022-06-26T06:51:31Z) - A Law of Robustness beyond Isoperimetry [84.33752026418045]
我々は、任意の分布上でニューラルネットワークパラメータを補間する頑健性の低い$Omega(sqrtn/p)$を証明した。
次に、$n=mathrmpoly(d)$のとき、スムーズなデータに対する過度なパラメータ化の利点を示す。
我々は、$n=exp(omega(d))$ のとき、$O(1)$-Lipschitz の頑健な補間関数の存在を否定する。
論文 参考訳（メタデータ） (2022-02-23T16:10:23Z) - The Separation Capacity of Random Neural Networks [78.25060223808936]
標準ガウス重みと一様分布バイアスを持つ十分に大きな2層ReLUネットワークは、この問題を高い確率で解くことができることを示す。
我々は、相互複雑性という新しい概念の観点から、データの関連構造を定量化する。
論文 参考訳（メタデータ） (2021-07-31T10:25:26Z) - ReLU Neural Networks of Polynomial Size for Exact Maximum Flow Computation [5.35599092568615]
本稿では,線形整流ユニットを用いたニューラルネットワークのパワーについて検討する。
我々は,2つの基本最適化問題を$mathcalO(m2n2)$のニューラルネットワークで解くことができることを示した。
論文 参考訳（メタデータ） (2021-02-12T17:23:34Z) - Learning Over-Parametrized Two-Layer ReLU Neural Networks beyond NTK [58.5766737343951]
2層ニューラルネットワークを学習する際の降下のダイナミクスについて考察する。
過度にパラメータ化された2層ニューラルネットワークは、タンジェントサンプルを用いて、ほとんどの地上で勾配損失を許容的に学習できることを示す。
論文 参考訳（メタデータ） (2020-07-09T07:09:28Z) - A Corrective View of Neural Networks: Representation, Memorization and
Learning [26.87238691716307]
我々はニューラルネットワーク近似の補正機構を開発する。
ランダム・フィーチャー・レギュレーション(RF)における2層ニューラルネットワークは任意のラベルを記憶できることを示す。
また、3層ニューラルネットワークについても検討し、その補正機構がスムーズなラジアル関数に対する高速な表現率をもたらすことを示す。
論文 参考訳（メタデータ） (2020-02-01T20:51:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。