論文の概要: Tight Hardness Results for Training Depth-2 ReLU Networks

• arxiv url: http://arxiv.org/abs/2011.13550v1
• Date: Fri, 27 Nov 2020 04:18:00 GMT
• ステータス: 処理完了
• システム内更新日: 2022-09-20 02:56:01.153445
• Title: Tight Hardness Results for Training Depth-2 ReLU Networks
• Title（参考訳）: 深さ2 reluネットワークのタイトな硬さ評価
• Authors: Surbhi Goel, Adam Klivans, Pasin Manurangsi, Daniel Reichman
• Abstract要約: ReLUアクティベーション関数を用いた深度2ニューラルネットのトレーニングにおいて,いくつかの硬度結果が得られた。 私たちのゴールは、与えられたトレーニングセットに対する平方損失を最小限に抑えるディープ2ニューラルネットワークを出力することです。
• 参考スコア（独自算出の注目度）: 38.60407125604287
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We prove several hardness results for training depth-2 neural networks with the ReLU activation function; these networks are simply weighted sums (that may include negative coefficients) of ReLUs. Our goal is to output a depth-2 neural network that minimizes the square loss with respect to a given training set. We prove that this problem is NP-hard already for a network with a single ReLU. We also prove NP-hardness for outputting a weighted sum of $k$ ReLUs minimizing the squared error (for $k>1$) even in the realizable setting (i.e., when the labels are consistent with an unknown depth-2 ReLU network). We are also able to obtain lower bounds on the running time in terms of the desired additive error $\epsilon$. To obtain our lower bounds, we use the Gap Exponential Time Hypothesis (Gap-ETH) as well as a new hypothesis regarding the hardness of approximating the well known Densest $\kappa$-Subgraph problem in subexponential time (these hypotheses are used separately in proving different lower bounds). For example, we prove that under reasonable hardness assumptions, any proper learning algorithm for finding the best fitting ReLU must run in time exponential in $1/\epsilon^2$. Together with a previous work regarding improperly learning a ReLU (Goel et al., COLT'17), this implies the first separation between proper and improper algorithms for learning a ReLU. We also study the problem of properly learning a depth-2 network of ReLUs with bounded weights giving new (worst-case) upper bounds on the running time needed to learn such networks both in the realizable and agnostic settings. Our upper bounds on the running time essentially matches our lower bounds in terms of the dependency on $\epsilon$.
• Abstract（参考訳）: ReLU活性化関数を用いた深度2ニューラルネットのトレーニングにおいて,これらのネットワークは単にReLUの重み付き和(負の係数を含むかもしれない)であることを示す。 我々の目標は、与えられたトレーニングセットに対する平方損失を最小限に抑えるディープ2ニューラルネットワークを出力することです。 この問題は1つのReLUを持つネットワークに対して既にNPハードであることが証明されている。 また、2乗誤差を最小化($k>1$)する重み付き和$k$ReLUを、実現可能な設定(ラベルが未知の深さ-2 ReLUネットワークと整合である場合)で出力するNP硬度も証明する。 また、所望の加算誤差$\epsilon$という観点で、実行時の下限を得ることができる。 下界を得るには、Gap Exponential Time hypothesis (Gap-ETH) を用いるとともに、既知のDensest $\kappa$-Subgraph 問題を半周期時間で近似する難しさに関する新たな仮説を用いる(これらの仮説は異なる下界の証明に別々に使用される)。 例えば、妥当な硬さ仮定の下では、最適なReLUを見つけるための適切な学習アルゴリズムは、1/\epsilon^2$で指数関数的に実行しなければならない。 ReLUを不適切に学習する以前の研究(Goel et al., COLT'17)とともに、これはReLUを学習するための適切なアルゴリズムと不適切なアルゴリズムを最初に分離することを意味する。 また,有界重みを持つrelusの深さ2ネットワークを適切に学習することで,実現可能かつ不可知な環境での学習に必要な実行時間(worst-case)の上限を新たに与える問題についても検討した。 ランニングタイム上の上限は、基本的に$\epsilon$への依存性の観点から下限と一致する。

関連論文リスト

• Fixing the NTK: From Neural Network Linearizations to Exact Convex Programs [63.768739279562105]
  学習目標に依存しない特定のマスクウェイトを選択する場合、このカーネルはトレーニングデータ上のゲートReLUネットワークのNTKと等価であることを示す。 この目標への依存の欠如の結果として、NTKはトレーニングセット上の最適MKLカーネルよりもパフォーマンスが良くない。
  論文  参考訳（メタデータ） (2023-09-26T17:42:52Z)
• The Implicit Bias of Minima Stability in Multivariate Shallow ReLU Networks [53.95175206863992]
  本研究では,2次損失を持つ1層多変量ReLUネットワークをトレーニングする際に,勾配勾配勾配が収束する解のタイプについて検討する。 我々は、浅いReLUネットワークが普遍近似器であるにもかかわらず、安定した浅層ネットワークは存在しないことを証明した。
  論文  参考訳（メタデータ） (2023-06-30T09:17:39Z)
• A Framework for Provably Stable and Consistent Training of Deep Feedforward Networks [4.21061712600981]
  本稿では、教師付き(分類と回帰)および教師なし(強化学習)シナリオにおいて、ディープニューラルネットワークを訓練するための新しいアルゴリズムを提案する。 このアルゴリズムは、標準降下勾配と勾配クリッピング法を組み合わせたものである。 理論的および実験を通して、我々のアルゴリズム更新はばらつきが低く、トレーニング損失はスムーズな方法で減少することを示す。
  論文  参考訳（メタデータ） (2023-05-20T07:18:06Z)
• Hardness of Noise-Free Learning for Two-Hidden-Layer Neural Networks [21.687992445577226]
  標準(ノイズフリー)モデルにおけるガウス入力に対する2層ReLUネットワークを学習するために,指数関数的統計的クエリ(SQ)の下界を与える。 従来のSQの下限は、逆ノイズモデル(認識学習)や相関SQのような制限されたモデルに限られていた。 これらの手法を他の学習モデルに拡張する方法を示し、多くのよく研究されたケースにおいて、より効率的な還元が得られることを示す。
  論文  参考訳（メタデータ） (2022-02-10T18:59:14Z)
• Implicit Regularization Towards Rank Minimization in ReLU Networks [34.41953136999683]
  ニューラルネットワークにおける暗黙の正規化とランク最小化の関係について検討する。 我々は非線形ReLUネットワークに焦点をあて、いくつかの新しい正および負の結果を提供する。
  論文  参考訳（メタデータ） (2022-01-30T09:15:44Z)
• Efficient Algorithms for Learning Depth-2 Neural Networks with General ReLU Activations [27.244958998196623]
  一般のReLUアクティベーションを用いた未知の深度2フィードフォワードニューラルネットワークを学習するための時間とサンプル効率のアルゴリズムを提案する。 特に、f(x) = amathsfTsigma(WmathsfTx+b)$, ここで$x$はガウス分布から引き出され、$sigma(t) := max(t,0)$はReLU活性化である。
  論文  参考訳（メタデータ） (2021-07-21T17:06:03Z)
• Towards an Understanding of Benign Overfitting in Neural Networks [104.2956323934544]
  現代の機械学習モデルは、しばしば膨大な数のパラメータを使用し、通常、トレーニング損失がゼロになるように最適化されている。 ニューラルネットワークの2層構成において、これらの良質な過適合現象がどのように起こるかを検討する。 本稿では,2層型ReLUネットワーク補間器を極小最適学習率で実現可能であることを示す。
  論文  参考訳（メタデータ） (2021-06-06T19:08:53Z)
• Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks [48.32532049640782]
  ガウス境界の下で, 1層ReLUネットワークを$k$の隠れ単位で学習する問題をmathbbRd$で研究する。 正の係数の場合、この学習問題の初回アルゴリズムを$k$から$tildeOOmega(sqrtlog d)$まで与える。
  論文  参考訳（メタデータ） (2020-06-22T17:53:54Z)
• Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
  ニューラルネットワーク検証の基本的なコンポーネントは、出力が取ることのできる値のバウンダリの計算である。 ラグランジアン分解に基づく新しい手法を提案する。 ランニングタイムのごく一部で、既成の解法に匹敵するバウンダリが得られることを示す。
  論文  参考訳（メタデータ） (2020-02-24T17:55:10Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。