論文の概要: On the Hardness of Training Deep Neural Networks Discretely

• arxiv url: http://arxiv.org/abs/2412.13057v1
• Date: Tue, 17 Dec 2024 16:20:29 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-18 13:57:45.545279
• Title: On the Hardness of Training Deep Neural Networks Discretely
• Title（参考訳）: 深部ニューラルネットワークの学習困難性について
• Authors: Ilan Doron-Arad,
• Abstract要約: ニューラルネットワークトレーニング(NNT)の硬さは,ネットワーク深度に大きく影響している。 具体的には、標準仮定の下では、D-NNTは、固定次元とデータセットサイズを持つインスタンスであってもクラスNPに含まれていないことを示す。 これらの結果を2層ネットワーク上でのD-NNTのNP硬度下界の包括的リストで補完する。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: We study neural network training (NNT): optimizing a neural network's parameters to minimize the training loss over a given dataset. NNT has been studied extensively under theoretic lenses, mainly on two-layer networks with linear or ReLU activation functions where the parameters can take any real value (here referred to as continuous NNT (C-NNT)). However, less is known about deeper neural networks, which exhibit substantially stronger capabilities in practice. In addition, the complexity of the discrete variant of the problem (D-NNT in short), in which the parameters are taken from a given finite set of options, has remained less explored despite its theoretical and practical significance. In this work, we show that the hardness of NNT is dramatically affected by the network depth. Specifically, we show that, under standard complexity assumptions, D-NNT is not in the complexity class NP even for instances with fixed dimensions and dataset size, having a deep architecture. This separates D-NNT from any NP-complete problem. Furthermore, using a polynomial reduction we show that the above result also holds for C-NNT, albeit with more structured instances. We complement these results with a comprehensive list of NP-hardness lower bounds for D-NNT on two-layer networks, showing that fixing the number of dimensions, the dataset size, or the number of neurons in the hidden layer leaves the problem challenging. Finally, we obtain a pseudo-polynomial algorithm for D-NNT on a two-layer network with a fixed dataset size.
• Abstract（参考訳）: ニューラルネットワークトレーニング(NNT): ニューラルネットワークのパラメータを最適化して、与えられたデータセットに対するトレーニング損失を最小限にする。 NNTは理論レンズの下で広く研究されており、主に線形またはReLU活性化関数を持つ2層ネットワークで、パラメータは任意の実値を取ることができる(以下、連続NNT (Continuous NNT: C-NNT) と呼ぶ)。 しかし、より深いニューラルネットワークについてはあまり知られていない。 さらに、パラメータが与えられた有限個の選択肢から取られる問題(D-NNT)の離散的変種(略してD-NNT)の複雑さは、その理論的および実践的重要性にもかかわらず、まだ研究が進んでいない。 本研究では,NNTの硬さがネットワーク深度に大きく影響されていることを示す。 具体的には、D-NNTは、標準的な複雑性仮定の下では、固定次元とデータセットサイズを持つインスタンスであっても、複雑性クラスNPには含まれておらず、より深いアーキテクチャを持つことを示す。 これは、D-NNT を任意のNP完全問題から分離する。 さらに、多項式還元を用いて、より構造化されたインスタンスを持つにもかかわらず、上記の結果がC-NNTにも成り立つことを示す。 これらの結果を2層ネットワーク上でのD-NNTのNP硬度下界の包括的リストで補完し、次元数、データセットサイズ、隠れた層内のニューロン数を固定することが問題となることを示す。 最後に,データセットサイズが固定された2層ネットワーク上でD-NNTの擬似ポリノミカルアルゴリズムを得る。

関連論文リスト

• Deep Neural Networks via Complex Network Theory: a Perspective [3.1023851130450684]
  ディープニューラルネットワーク(DNN)は、リンクと頂点が反復的にデータを処理し、タスクを亜最適に解くグラフとして表現することができる。複雑なネットワーク理論(CNT)は、統計物理学とグラフ理論を融合させ、その重みとニューロン構造を分析してニューラルネットワークを解釈する方法を提供する。 本研究では,DNNのトレーニング分布から抽出した測定値を用いて既存のCNTメトリクスを拡張し,純粋なトポロジカル解析からディープラーニングの解釈可能性へ移行する。
  論文  参考訳（メタデータ） (2024-04-17T08:42:42Z)
• Deeper or Wider: A Perspective from Optimal Generalization Error with Sobolev Loss [2.07180164747172]
  より深いニューラルネットワーク(DeNN)と、柔軟な数のレイヤと、限られた隠れたレイヤを持つより広いニューラルネットワーク(WeNN)を比較します。 より多くのパラメータがWeNNを好む傾向にあるのに対し、サンプルポイントの増加と損失関数の規則性の向上は、DeNNの採用に傾いている。
  論文  参考訳（メタデータ） (2024-01-31T20:10:10Z)
• Variational Inference for Infinitely Deep Neural Networks [0.4061135251278187]
  非有界深度ニューラルネットワーク(UDN) 我々は、無限に深い確率モデルである非有界深度ニューラルネットワーク(UDN)を導入し、その複雑さをトレーニングデータに適用する。 我々はUDNを実データと合成データに基づいて研究する。
  論文  参考訳（メタデータ） (2022-09-21T03:54:34Z)
• Extrapolation and Spectral Bias of Neural Nets with Hadamard Product: a Polynomial Net Study [55.12108376616355]
  NTKの研究は典型的なニューラルネットワークアーキテクチャに特化しているが、アダマール製品(NNs-Hp)を用いたニューラルネットワークには不完全である。 本研究では,ニューラルネットワークの特別なクラスであるNNs-Hpに対する有限幅Kの定式化を導出する。 我々は,カーネル回帰予測器と関連するNTKとの等価性を証明し,NTKの適用範囲を拡大する。
  論文  参考訳（メタデータ） (2022-09-16T06:36:06Z)
• Deep Neural Networks as Complex Networks [1.704936863091649]
  我々は、重み付きグラフとしてディープニューラルネットワーク(DNN)を表現するために複雑ネットワーク理論を用いる。 我々は、DNNを動的システムとして研究するためのメトリクスを導入し、その粒度は、重みから神経細胞を含む層まで様々である。 我々の測定値が低性能ネットワークと高パフォーマンスネットワークを区別していることが示される。
  論文  参考訳（メタデータ） (2022-09-12T16:26:04Z)
• Deep Architecture Connectivity Matters for Its Convergence: A Fine-Grained Analysis [94.64007376939735]
  我々は、勾配降下訓練におけるディープニューラルネットワーク(DNN)の収束に対する接続パターンの影響を理論的に特徴づける。 接続パターンの単純なフィルタリングによって、評価対象のモデルの数を削減できることが示される。
  論文  参考訳（メタデータ） (2022-05-11T17:43:54Z)
• On Feature Learning in Neural Networks with Global Convergence Guarantees [49.870593940818715]
  勾配流(GF)を用いた広帯域ニューラルネットワーク(NN)の最適化について検討する。 入力次元がトレーニングセットのサイズ以下である場合、トレーニング損失はGFの下での線形速度で0に収束することを示す。 また、ニューラル・タンジェント・カーネル(NTK)システムとは異なり、我々の多層モデルは特徴学習を示し、NTKモデルよりも優れた一般化性能が得られることを実証的に示す。
  論文  参考訳（メタデータ） (2022-04-22T15:56:43Z)
• Block-term Tensor Neural Networks [29.442026567710435]
  ブロック終端テンソル層(BT層)は,CNNやRNNなどのニューラルネットワークモデルに容易に適用可能であることを示す。 CNNとRNNのBT層は、元のDNNの表現力を維持したり改善したりしながら、パラメータ数に対して非常に大きな圧縮比を達成することができる。
  論文  参考訳（メタデータ） (2020-10-10T09:58:43Z)
• Finite Versus Infinite Neural Networks: an Empirical Study [69.07049353209463]
  カーネルメソッドは、完全に接続された有限幅ネットワークより優れている。 中心とアンサンブルの有限ネットワークは後続のばらつきを減らした。 重みの減衰と大きな学習率の使用は、有限ネットワークと無限ネットワークの対応を破る。
  論文  参考訳（メタデータ） (2020-07-31T01:57:47Z)
• Modeling from Features: a Mean-field Framework for Over-parameterized Deep Neural Networks [54.27962244835622]
  本稿では、オーバーパラメータ化ディープニューラルネットワーク(DNN)のための新しい平均場フレームワークを提案する。 このフレームワークでは、DNNは連続的な極限におけるその特徴に対する確率測度と関数によって表現される。 本稿では、標準DNNとResidual Network(Res-Net)アーキテクチャを通してフレームワークを説明する。
  論文  参考訳（メタデータ） (2020-07-03T01:37:16Z)
• Widening and Squeezing: Towards Accurate and Efficient QNNs [125.172220129257]
  量子化ニューラルネットワーク(QNN)は、非常に安価な計算とストレージオーバーヘッドのため、業界にとって非常に魅力的なものだが、その性能は、完全な精度パラメータを持つネットワークよりも悪い。 既存の手法の多くは、より効果的なトレーニング技術を利用して、特にバイナリニューラルネットワークの性能を高めることを目的としている。 本稿では,従来の完全精度ネットワークで高次元量子化機能に特徴を投影することで,この問題に対処する。
  論文  参考訳（メタデータ） (2020-02-03T04:11:13Z)

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

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