論文の概要: 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}$でない限り、複数の出力次元を持つネットワークでは不可能である。
関連論文リスト
- Learning Hierarchical Polynomials with Three-Layer Neural Networks [56.71223169861528]
3層ニューラルネットワークを用いた標準ガウス分布における階層関数の学習問題について検討する。
次数$k$s$p$の大規模なサブクラスの場合、正方形損失における階層的勾配によるトレーニングを受けた3層ニューラルネットワークは、テストエラーを消すためにターゲット$h$を学習する。
この研究は、3層ニューラルネットワークが複雑な特徴を学習し、その結果、幅広い階層関数のクラスを学ぶ能力を示す。
論文 参考訳(メタデータ) (2023-11-23T02:19:32Z) - Polynomial-Time Solutions for ReLU Network Training: A Complexity
Classification via Max-Cut and Zonotopes [70.52097560486683]
我々は、ReLUネットワークの近似の難しさがマックス・カッツ問題の複雑さを反映しているだけでなく、特定の場合において、それと完全に一致することを証明した。
特に、$epsilonleqsqrt84/83-1approx 0.006$とすると、目的値に関して相対誤差$epsilon$でReLUネットワーク対象の近似グローバルデータセットを見つけることはNPハードであることが示される。
論文 参考訳(メタデータ) (2023-11-18T04:41:07Z) - Bounding the Width of Neural Networks via Coupled Initialization -- A
Worst Case Analysis [121.9821494461427]
2層ReLUネットワークに必要なニューロン数を著しく削減する方法を示す。
また、事前の作業を改善するための新しい下位境界を証明し、ある仮定の下では、最善を尽くすことができることを証明します。
論文 参考訳(メタデータ) (2022-06-26T06:51:31Z) - Correlation Functions in Random Fully Connected Neural Networks at
Finite Width [17.51364577113718]
この記事では、ガウスのランダムな重みとバイアスと$L$の隠蔽層を持つ完全に接続されたニューラルネットワークについて考察する。
有界非線形性に対しては、ネットワーク出力とその導関数の共役相関関数に対して1/n$の急激な再帰推定を与える。
いずれの場合も、深さと幅の比$L/n$は、個々のニューロンのゆらぎのスケールとニューロン間相関の大きさの両方を制御し、有効なネットワーク深さの役割を担っている。
論文 参考訳(メタデータ) (2022-04-03T11:57:18Z) - 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 for Exact Maximum Flow Computation [0.30458514384586405]
n$のノードと$m$のarcを持つ有向グラフが与えられたとき、任意の実アーク容量から最大フローを入力として計算する表現的大きさのnnが存在することを示す。
次に、最大フロー問題を正確に解くためにMAAPを設計し、$mathcalO(m2 n2)$のNNに変換する。
論文 参考訳(メタデータ) (2021-02-12T17:23:34Z) - Learning Over-Parametrized Two-Layer ReLU Neural Networks beyond NTK [58.5766737343951]
2層ニューラルネットワークを学習する際の降下のダイナミクスについて考察する。
過度にパラメータ化された2層ニューラルネットワークは、タンジェントサンプルを用いて、ほとんどの地上で勾配損失を許容的に学習できることを示す。
論文 参考訳(メタデータ) (2020-07-09T07:09:28Z) - AlgebraNets [35.311476442807766]
本研究では, enwiki8 と WikiText-103 データセットを用いて代用代数学を数値表現として研究する。
我々は$mathbbC$, $mathbbH$, $M_2(mathbbR)$, $M_3(mathbbR)$, $M_4(mathbbR)$を考える。
これらの代数の乗法は実乗法よりも計算密度が高い。
論文 参考訳(メタデータ) (2020-06-12T17:51:20Z) - A Corrective View of Neural Networks: Representation, Memorization and
Learning [26.87238691716307]
我々はニューラルネットワーク近似の補正機構を開発する。
ランダム・フィーチャー・レギュレーション(RF)における2層ニューラルネットワークは任意のラベルを記憶できることを示す。
また、3層ニューラルネットワークについても検討し、その補正機構がスムーズなラジアル関数に対する高速な表現率をもたらすことを示す。
論文 参考訳(メタデータ) (2020-02-01T20:51:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。