論文の概要: Learning Deep ReLU Networks Is Fixed-Parameter Tractable
- arxiv url: http://arxiv.org/abs/2009.13512v1
- Date: Mon, 28 Sep 2020 17:58:43 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-13 21:42:28.961550
- Title: Learning Deep ReLU Networks Is Fixed-Parameter Tractable
- Title（参考訳）: ディープラーニングのReLUネットワークを学習する
- Authors: Sitan Chen, Adam R. Klivans, Raghu Meka
- Abstract要約: ガウス入力に関して未知のReLUネットワークを学習する問題を考察する。
ランニング時間が周囲次元の固定重みとなるアルゴリズムを与える。
我々の境界は、隠れた単位数、深さ、スペクトルノルムのスペクトルノルム、リプシッツ定数に依存する。
- 参考スコア（独自算出の注目度）: 21.625005195943707
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the problem of learning an unknown ReLU network with respect to
Gaussian inputs and obtain the first nontrivial results for networks of depth
more than two. We give an algorithm whose running time is a fixed polynomial in
the ambient dimension and some (exponentially large) function of only the
network's parameters.
Our bounds depend on the number of hidden units, depth, spectral norm of the
weight matrices, and Lipschitz constant of the overall network (we show that
some dependence on the Lipschitz constant is necessary). We also give a bound
that is doubly exponential in the size of the network but is independent of
spectral norm. These results provably cannot be obtained using gradient-based
methods and give the first example of a class of efficiently learnable neural
networks that gradient descent will fail to learn.
In contrast, prior work for learning networks of depth three or higher
requires exponential time in the ambient dimension, even when the above
parameters are bounded by a constant. Additionally, all prior work for the
depth-two case requires well-conditioned weights and/or positive coefficients
to obtain efficient run-times. Our algorithm does not require these
assumptions.
Our main technical tool is a type of filtered PCA that can be used to
iteratively recover an approximate basis for the subspace spanned by the hidden
units in the first layer. Our analysis leverages new structural results on
lattice polynomials from tropical geometry.
- Abstract（参考訳）: ガウス入力に関して未知のreluネットワークを学習する問題を考察し,深さ2以上のネットワークに対する最初の非自明な結果を得る。
実行時間が周囲次元の固定多項式であるアルゴリズムと、ネットワークのパラメータのみのいくつかの(指数的に大きい)関数を与える。
我々の境界は、隠れた単位数、深さ、重み行列のスペクトルノルム、および全体のネットワークのリプシッツ定数に依存する(リプシッツ定数へのいくつかの依存が必要であることを示す)。
また、ネットワークのサイズが2倍に指数関数的であるが、スペクトルノルムとは独立な境界を与える。
これらの結果は勾配に基づく手法では得られず、勾配降下が学習できない効率的な学習可能なニューラルネットワークのクラスの最初の例を与える。
対照的に、深度3以上のネットワークを学習するには、上記のパラメータが定数で有界であっても、周囲次元の指数時間を必要とする。
さらに、深度2のケースのすべての事前作業には、効率的な実行時間を得るために、十分な条件付き重みと/または正の係数が必要である。
我々のアルゴリズムはこれらの仮定を必要としない。
我々の主な技術ツールはフィルタPCAの一種であり、第1層に隠されたユニットが分散する部分空間の近似基底を反復的に復元することができる。
本解析は,熱帯幾何学による格子多項式の新たな構造的結果を活用する。
関連論文リスト
- Local Loss Optimization in the Infinite Width: Stable Parameterization of Predictive Coding Networks and Target Propagation [8.35644084613785]
局所目標の2つの代表的設計に対して、無限幅極限における最大更新パラメータ化(mu$P)を導入する。
深層線形ネットワークを解析した結果,PCの勾配は1次勾配とガウス・ニュートン様勾配の間に介在していることが判明した。
我々は、特定の標準設定において、無限幅制限のPCは、一階勾配とよりよく似た振る舞いをすることを示した。
論文 参考訳（メタデータ） (2024-11-04T11:38:27Z) - ECLipsE: Efficient Compositional Lipschitz Constant Estimation for Deep Neural Networks [0.8993153817914281]
リプシッツ定数は、入力摂動に対するニューラルネットワークの堅牢性を証明する上で重要な役割を果たす。
リプシッツ定数の厳密な上界を得る努力がなされている。
ディープフィードフォワードニューラルネットワークに対するリプシッツ定数を推定するための構成的アプローチを提案する。
論文 参考訳（メタデータ） (2024-04-05T19:36:26Z) - Asymptotics of Learning with Deep Structured (Random) Features [9.366617422860543]
機能マップの大規模なクラスでは、読み出しレイヤの学習に伴うテストエラーの厳密な特徴付けを提供しています。
いくつかのケースでは、勾配降下下で訓練された深部有限幅ニューラルネットワークによって学習された特徴写像をキャプチャできる。
論文 参考訳（メタデータ） (2024-02-21T18:35:27Z) - Depth Separations in Neural Networks: Separating the Dimension from the Accuracy [9.783697404304027]
我々は、(実入力で)深度2と深度3ニューラルネットの指数的なサイズ分離を証明した。
対象関数が深度3ネットワークを用いて効率的に表現できる場合であっても,次元の呪いは深さ2の近似で現れることを示す。
論文 参考訳（メタデータ） (2024-02-11T17:27:26Z) - Globally Optimal Training of Neural Networks with Threshold Activation
Functions [63.03759813952481]
しきい値アクティベートを伴うディープニューラルネットワークの重み劣化正規化学習問題について検討した。
ネットワークの特定の層でデータセットを破砕できる場合に、簡易な凸最適化の定式化を導出する。
論文 参考訳（メタデータ） (2023-03-06T18:59:13Z) - A Unified Algebraic Perspective on Lipschitz Neural Networks [88.14073994459586]
本稿では,様々なタイプの1-Lipschitzニューラルネットワークを統一する新しい視点を提案する。
そこで本研究では,SDP(Common semidefinite Programming)条件の解析解を求めることによって,既存の多くの手法を導出し,一般化することができることを示す。
SDPベースのLipschitz Layers (SLL) と呼ばれる我々のアプローチは、非自明で効率的な凸ポテンシャル層の一般化を設計できる。
論文 参考訳（メタデータ） (2023-03-06T14:31:09Z) - Bayesian Interpolation with Deep Linear Networks [92.1721532941863]
ニューラルネットワークの深さ、幅、データセットサイズがモデル品質にどう影響するかを特徴付けることは、ディープラーニング理論における中心的な問題である。
線形ネットワークが無限深度で証明可能な最適予測を行うことを示す。
また、データに依存しない先行法により、広い線形ネットワークにおけるベイズ模型の証拠は無限の深さで最大化されることを示す。
論文 参考訳（メタデータ） (2022-12-29T20:57:46Z) - Globally Gated Deep Linear Networks [3.04585143845864]
我々はGGDLN(Globally Gated Deep Linear Networks)を導入する。
有限幅熱力学極限におけるこれらのネットワークの一般化特性の正確な方程式を導出する。
我々の研究は、有限幅の非線形ネットワークの族における学習に関する最初の正確な理論解である。
論文 参考訳（メタデータ） (2022-10-31T16:21:56Z) - Robust Training and Verification of Implicit Neural Networks: A
Non-Euclidean Contractive Approach [64.23331120621118]
本稿では,暗黙的ニューラルネットワークのトレーニングとロバスト性検証のための理論的および計算的枠組みを提案する。
組込みネットワークを導入し、組込みネットワークを用いて、元のネットワークの到達可能な集合の超近似として$ell_infty$-normボックスを提供することを示す。
MNISTデータセット上で暗黙的なニューラルネットワークをトレーニングするためにアルゴリズムを適用し、我々のモデルの堅牢性と、文献における既存のアプローチを通じてトレーニングされたモデルを比較する。
論文 参考訳（メタデータ） (2022-08-08T03:13:24Z) - Unified Field Theory for Deep and Recurrent Neural Networks [56.735884560668985]
本稿では,再帰的ネットワークと深層ネットワークの両方に対する平均場理論の統一的,体系的な導出について述べる。
平均場理論への収束は、ディープネットワークよりもリカレントネットワークの方が典型的に遅い。
提案手法はガウス過程が1/n$の体系的展開の最下位次数であることを示す。
論文 参考訳（メタデータ） (2021-12-10T15:06:11Z) - Path Regularization: A Convexity and Sparsity Inducing Regularization
for Parallel ReLU Networks [75.33431791218302]
本稿では,ディープニューラルネットワークのトレーニング問題について検討し,最適化環境に隠された凸性を明らかにするための解析的アプローチを提案する。
我々は、標準のディープ・ネットワークとResNetを特別なケースとして含む、ディープ・パラレルなReLUネットワークアーキテクチャについて検討する。
論文 参考訳（メタデータ） (2021-10-18T18:00:36Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。