論文の概要: Training Fully Connected Neural Networks is $\exists\mathbb{R}$-Complete
- arxiv url: http://arxiv.org/abs/2204.01368v1
- Date: Mon, 4 Apr 2022 10:28:11 GMT
- ステータス: 処理完了
- システム内更新日: 2022-04-05 17:28:00.001696
- 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要約: 問題は$existsmathbbR$completeであることが示される。
我々は、Abrahamsen, Kleist and Miltzow [NeurIPS]による最近の結果を一般化する。
この結果は、一連の中央アルゴリズムの問題が$existsmathbbR$completeであることを明らかにする最近の研究の行に該当する。
- 参考スコア（独自算出の注目度）: 2.362412515574206
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the algorithmic problem of finding the optimal weights and biases
for a two-layer fully connected neural network to fit a given set of data
points. This problem is known as empirical risk minimization in the machine
learning community. We show that the problem is $\exists\mathbb{R}$-complete.
This complexity class can be defined as the set of algorithmic problems that
are polynomial-time equivalent to finding real roots of a polynomial with
integer coefficients. Our results hold even if the following restrictions are
all added simultaneously.
$\bullet$ There are exactly two output neurons.
$\bullet$ There are exactly two input neurons.
$\bullet$ The data has only 13 different labels.
$\bullet$ The number of hidden neurons is a constant fraction of the number
of data points.
$\bullet$ The target training error is zero.
$\bullet$ The ReLU activation function is used.
This shows that even very simple networks are difficult to train. The result
offers an explanation (though far from a complete understanding) on why only
gradient descent is widely successful in training neural networks in practice.
We generalize a recent result by Abrahamsen, Kleist and Miltzow [NeurIPS 2021].
This result falls into a recent line of research that tries to unveil that a
series of central algorithmic problems from widely different areas of computer
science and mathematics are $\exists\mathbb{R}$-complete: This includes the art
gallery problem [JACM/STOC 2018], geometric packing [FOCS 2020], covering
polygons with convex polygons [FOCS 2021], and continuous constraint
satisfaction problems [FOCS 2021].
- Abstract（参考訳）: 与えられたデータ点の集合に適合する2層完全連結ニューラルネットワークの最適重みとバイアスを求めるアルゴリズム問題を考える。
この問題は、機械学習コミュニティにおける経験的リスク最小化として知られている。
問題は$\exists\mathbb{R}$-completeである。
この複雑性クラスは、整数係数を持つ多項式の実根を見つけることと同値な多項式時間問題の集合として定義することができる。
以下の制約が同時に加えられても結果が得られます。
$\bullet$ ちょうど2つの出力ニューロンがあります。
$\bullet$ちょうど2つの入力ニューロンがあります。
$\bullet$ データには13のラベルしかありません。
$\bullet$ 隠れたニューロンの数は、データポイントの数の一定割合である。
$\bullet$ ターゲットのトレーニングエラーはゼロです。
$\bullet$ ReLUアクティベーション関数が使用される。
これは非常に単純なネットワークでさえ訓練が難しいことを示している。
その結果、なぜ勾配降下だけが実際にニューラルネットワークのトレーニングに広く成功したのか(完全には理解できないが)が説明できる。
我々は、Abrahamsen, Kleist and Miltzow [NeurIPS 2021] による最近の結果を一般化する。
この結果は、コンピュータ科学と数学の幅広い分野における一連の中央的アルゴリズム問題は、$\exists\mathbb{r}$-completeであることを示す最近の研究に当てはまる: アートギャラリー問題[jacm/stoc 2018]、幾何学的パッキング[focs 2020]、凸多角形による多角形被覆問題[focs 2021]、連続的制約満足問題[focs 2021]を含む。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。