論文の概要: 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]を含む。
関連論文リスト
- Learning Hierarchical Polynomials with Three-Layer Neural Networks [56.71223169861528]
3層ニューラルネットワークを用いた標準ガウス分布における階層関数の学習問題について検討する。
次数$k$s$p$の大規模なサブクラスの場合、正方形損失における階層的勾配によるトレーニングを受けた3層ニューラルネットワークは、テストエラーを消すためにターゲット$h$を学習する。
この研究は、3層ニューラルネットワークが複雑な特徴を学習し、その結果、幅広い階層関数のクラスを学ぶ能力を示す。
論文 参考訳(メタデータ) (2023-11-23T02:19:32Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳(メタデータ) (2023-07-24T14:37:22Z) - Most Neural Networks Are Almost Learnable [52.40331776572531]
固定された$epsilon>0$とdeep $i$に対して、深さ$i$のランダムなXavierネットワークを学習するポリ時間アルゴリズムが存在することを示す。
このアルゴリズムは時間とサンプルの複雑さが$(bard)mathrmpoly(epsilon-1)$であり、$bar d$はネットワークのサイズである。
シグモイドやReLU様の活性化の場合、境界は$(bard)mathrmpolylog(eps)に改善できる。
論文 参考訳(メタデータ) (2023-05-25T22:27:42Z) - Learning (Very) Simple Generative Models Is Hard [45.13248517769758]
我々は,$mathbbRdtobbRd'$の出力座標が$mathrmpoly(d)$ニューロンを持つ一層ReLUネットワークである場合でも,リアルタイムアルゴリズムが問題を解決可能であることを示す。
我々の証明の鍵となる要素は、コンパクトに支持されたピースワイズ線形関数$f$をニューラルネットワークで束ねたスロープで構築することであり、$mathcalN(0,1)$のプッシュフォワードは$mathcalのすべての低度モーメントと一致する。
論文 参考訳(メタデータ) (2022-05-31T17:59:09Z) - Hardness of Learning Halfspaces with Massart Noise [56.98280399449707]
我々は、マッサート(有界)ノイズの存在下でPAC学習のハーフスペースの複雑さを研究します。
情報理論上最適なエラーとSQアルゴリズムで達成できる最高のエラーとの間に指数関数的なギャップがあることを示した。
論文 参考訳(メタデータ) (2020-12-17T16:43:11Z) - Small Covers for Near-Zero Sets of Polynomials and Learning Latent
Variable Models [56.98280399449707]
我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。
構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
論文 参考訳(メタデータ) (2020-12-14T18:14:08Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。