論文の概要: A case where a spindly two-layer linear network whips any neural network
with a fully connected input layer
- arxiv url: http://arxiv.org/abs/2010.08625v1
- Date: Fri, 16 Oct 2020 20:49:58 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-06 20:31:13.414527
- Title: A case where a spindly two-layer linear network whips any neural network
with a fully connected input layer
- Title(参考訳): スピン型2層線形ネットワークが完全に接続された入力層でニューラルネットワークをホイップする一例
- Authors: Manfred K. Warmuth, Wojciech Kot{\l}owski, Ehsan Amid
- Abstract要約: 勾配降下によるスパース目標を効率的に学習するために,スパース入力層が必要であることを示す。
驚くべきことに、同じタイプの問題は、単純な2層線形ニューラルネットワークによって大幅に効率良く解決できる。
- 参考スコア(独自算出の注目度): 24.132345589750592
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: It was conjectured that any neural network of any structure and arbitrary
differentiable transfer functions at the nodes cannot learn the following
problem sample efficiently when trained with gradient descent: The instances
are the rows of a $d$-dimensional Hadamard matrix and the target is one of the
features, i.e. very sparse. We essentially prove this conjecture: We show that
after receiving a random training set of size $k < d$, the expected square loss
is still $1-\frac{k}{(d-1)}$. The only requirement needed is that the input
layer is fully connected and the initial weight vectors of the input nodes are
chosen from a rotation invariant distribution.
Surprisingly the same type of problem can be solved drastically more
efficient by a simple 2-layer linear neural network in which the $d$ inputs are
connected to the output node by chains of length 2 (Now the input layer has
only one edge per input). When such a network is trained by gradient descent,
then it has been shown that its expected square loss is $\frac{\log d}{k}$.
Our lower bounds essentially show that a sparse input layer is needed to
sample efficiently learn sparse targets with gradient descent when the number
of examples is less than the number of input features.
- Abstract(参考訳): 任意の構造のニューラルネットワークとノードの任意の微分可能な転送関数は、勾配降下でトレーニングされた場合、次の問題サンプルを効率的に学習できないと推測された: インスタンスは$d$-dimensional hadamard行列の行であり、ターゲットは特徴の1つである、すなわち非常にスパースである。
この予想を本質的に証明する:我々は、サイズ$k < d$のランダムなトレーニングセットを受け取った後、期待の平方損失は1-\frac{k}{(d-1)}$である。
必要な唯一の要件は、入力層が完全に接続され、入力ノードの初期重みベクトルが回転不変分布から選択されることである。
驚くべきことに、同じタイプの問題は、$d$入力が出力ノードに長さ2のチェーンで接続される単純な2層線形ニューラルネットワークにより、大幅に効率良く解決できる(入力層は入力毎に1つのエッジしか持たない)。
そのようなネットワークが勾配降下によって訓練された場合、その期待平方損失は$\frac{\log d}{k}$であることが示されている。
我々の下限は、サンプル数が入力特徴数より少ない場合、スパース目標を勾配降下で効率的に学習するためにスパース入力層が必要であることを示している。
関連論文リスト
- Implicit Bias of Gradient Descent for Two-layer ReLU and Leaky ReLU
Networks on Nearly-orthogonal Data [66.1211659120882]
好ましい性質を持つ解に対する暗黙の偏見は、勾配に基づく最適化によって訓練されたニューラルネットワークがうまく一般化できる重要な理由であると考えられている。
勾配流の暗黙バイアスは、均質ニューラルネットワーク(ReLUやリークReLUネットワークを含む)に対して広く研究されているが、勾配降下の暗黙バイアスは現在、滑らかなニューラルネットワークに対してのみ理解されている。
論文 参考訳(メタデータ) (2023-10-29T08:47:48Z) - SGD Finds then Tunes Features in Two-Layer Neural Networks with
near-Optimal Sample Complexity: A Case Study in the XOR problem [1.3597551064547502]
本研究では,2層ニューラルネットワーク上でのミニバッチ降下勾配(SGD)の最適化過程について考察する。
二次 XOR' 関数 $y = -x_ix_j$ でラベル付けされた $d$-dimensional Boolean hypercube から得られるデータから、人口誤差 $o(1)$ と $d :textpolylog(d)$ のサンプルをトレーニングすることが可能であることを証明した。
論文 参考訳(メタデータ) (2023-09-26T17:57:44Z) - Beyond NTK with Vanilla Gradient Descent: A Mean-Field Analysis of
Neural Networks with Polynomial Width, Samples, and Time [37.73689342377357]
不自然な変更を伴わないネットワーク上の勾配勾配勾配が、カーネル法よりも優れたサンプリング複雑性を達成できるかどうかは、まだ明らかな問題である。
正の学習数を持つ射影勾配降下は同じサンプルで低誤差に収束することを示す。
論文 参考訳(メタデータ) (2023-06-28T16:45:38Z) - Generalization and Stability of Interpolating Neural Networks with
Minimal Width [37.908159361149835]
補間系における勾配によって訓練された浅層ニューラルネットワークの一般化と最適化について検討する。
トレーニング損失数は$m=Omega(log4 (n))$ニューロンとニューロンを最小化する。
m=Omega(log4 (n))$のニューロンと$Tapprox n$で、テスト損失のトレーニングを$tildeO (1/)$に制限します。
論文 参考訳(メタデータ) (2023-02-18T05:06:15Z) - Implicit Bias in Leaky ReLU Networks Trained on High-Dimensional Data [63.34506218832164]
本研究では,ReLUを活性化した2層完全連結ニューラルネットワークにおける勾配流と勾配降下の暗黙的バイアスについて検討する。
勾配流には、均一なニューラルネットワークに対する暗黙のバイアスに関する最近の研究を活用し、リーク的に勾配流が2つ以上のランクを持つニューラルネットワークを生成することを示す。
勾配降下は, ランダムな分散が十分小さい場合, 勾配降下の1ステップでネットワークのランクが劇的に低下し, トレーニング中もランクが小さくなることを示す。
論文 参考訳(メタデータ) (2022-10-13T15:09:54Z) - Bounding the Width of Neural Networks via Coupled Initialization -- A
Worst Case Analysis [121.9821494461427]
2層ReLUネットワークに必要なニューロン数を著しく削減する方法を示す。
また、事前の作業を改善するための新しい下位境界を証明し、ある仮定の下では、最善を尽くすことができることを証明します。
論文 参考訳(メタデータ) (2022-06-26T06:51:31Z) - On the Effective Number of Linear Regions in Shallow Univariate ReLU
Networks: Convergence Guarantees and Implicit Bias [50.84569563188485]
我々は、ラベルが$r$のニューロンを持つターゲットネットワークの符号によって決定されるとき、勾配流が方向収束することを示す。
我々の結果は、標本サイズによらず、幅が$tildemathcalO(r)$である、緩やかなオーバーパラメータ化をすでに維持しているかもしれない。
論文 参考訳(メタデータ) (2022-05-18T16:57:10Z) - Algorithms for Efficiently Learning Low-Rank Neural Networks [12.916132936159713]
低ランクニューラルネットワークの学習アルゴリズムについて検討する。
単層ReLUネットワークに最適な低ランク近似を学習するアルゴリズムを提案する。
低ランク$textitdeep$ネットワークをトレーニングするための新しい低ランクフレームワークを提案する。
論文 参考訳(メタデータ) (2022-02-02T01:08:29Z) - Learning Over-Parametrized Two-Layer ReLU Neural Networks beyond NTK [58.5766737343951]
2層ニューラルネットワークを学習する際の降下のダイナミクスについて考察する。
過度にパラメータ化された2層ニューラルネットワークは、タンジェントサンプルを用いて、ほとんどの地上で勾配損失を許容的に学習できることを示す。
論文 参考訳(メタデータ) (2020-07-09T07:09:28Z) - Towards Understanding Hierarchical Learning: Benefits of Neural
Representations [160.33479656108926]
この研究で、中間的神経表現がニューラルネットワークにさらなる柔軟性をもたらすことを実証する。
提案手法は, 生の入力と比較して, サンプルの複雑度を向上できることを示す。
この結果から, 深度が深層学習においてなぜ重要かという新たな視点が得られた。
論文 参考訳(メタデータ) (2020-06-24T02:44:54Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。