論文の概要: Training Neural Networks is NP-Hard in Fixed Dimension

• arxiv url: http://arxiv.org/abs/2303.17045v2
• Date: Thu, 18 Jan 2024 12:10:03 GMT
• ステータス: 処理完了
• システム内更新日: 2024-01-19 20:56:57.603574
• Title: Training Neural Networks is NP-Hard in Fixed Dimension
• Title（参考訳）: ニューラルネットワークのトレーニングは固定次元におけるNPハードである
• Authors: Vincent Froese, Christoph Hertrich
• Abstract要約: 本稿では,入力データの次元と隠れニューロンの数に関して,2層ニューラルネットワークをトレーニングする際のパラメータ化複雑性について検討する。 その結果、これらのパラメータに関する複雑さの状態をほぼ完全に解決した。
• 参考スコア（独自算出の注目度）: 8.774952953654655
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the parameterized complexity of training two-layer neural networks with respect to the dimension of the input data and the number of hidden neurons, considering ReLU and linear threshold activation functions. Albeit the computational complexity of these problems has been studied numerous times in recent years, several questions are still open. We answer questions by Arora et al. [ICLR '18] and Khalife and Basu [IPCO '22] showing that both problems are NP-hard for two dimensions, which excludes any polynomial-time algorithm for constant dimension. We also answer a question by Froese et al. [JAIR '22] proving W[1]-hardness for four ReLUs (or two linear threshold neurons) with zero training error. Finally, in the ReLU case, we show fixed-parameter tractability for the combined parameter number of dimensions and number of ReLUs if the network is assumed to compute a convex map. Our results settle the complexity status regarding these parameters almost completely.
• Abstract（参考訳）: 本稿では,ReLUと線形しきい値活性化関数を考慮し,入力データの次元と隠れニューロン数に関する2層ニューラルネットワークのトレーニングのパラメータ化複雑性について検討する。 これらの問題の計算複雑性は近年何度も研究されているが、いくつかの疑問がまだ残っている。 Aroraらによる質問に答える。 [ICLR '18] と Khalife と Basu [IPCO '22] は、どちらの問題も2次元のNPハードであることを示し、定数次元の多項式時間アルゴリズムを除外している。 また、Froeseらによる質問にも答える。 [jair '22] 4つのrelus(または2つの線形しきい値ニューロン)のw[1]硬さをトレーニングエラーゼロで証明する。 最後に、ReLUの場合、ネットワークが凸写像を計算すると仮定された場合、ReLUの次元と次元の合計パラメータ数に対する固定パラメータのトラクタビリティを示す。 以上より,これらのパラメータの複雑さをほぼ完全に解決した。

関連論文リスト

• Convex Formulations for Training Two-Layer ReLU Neural Networks [21.88871868680998]
  非層NPハード最適化問題は、機械学習モデルにとって不可欠である。 有限幅2つのニューラルネットワークで解ける半定緩和を導入する。
  論文  参考訳（メタデータ） (2024-10-29T17:53:15Z)
• Complexity of Deciding Injectivity and Surjectivity of ReLU Neural Networks [5.482420806459269]
  ReLU層の単射率を決定するためのcoNP完全性を証明する。 1次元出力を持つ2層ReLUネットワークのサージェクティビティも特徴付ける。
  論文  参考訳（メタデータ） (2024-05-30T08:14:34Z)
• Polynomial-Time Solutions for ReLU Network Training: A Complexity Classification via Max-Cut and Zonotopes [70.52097560486683]
  我々は、ReLUネットワークの近似の難しさがマックス・カッツ問題の複雑さを反映しているだけでなく、特定の場合において、それと完全に一致することを証明した。 特に、$epsilonleqsqrt84/83-1approx 0.006$とすると、目的値に関して相対誤差$epsilon$でReLUネットワーク対象の近似グローバルデータセットを見つけることはNPハードであることが示される。
  論文  参考訳（メタデータ） (2023-11-18T04:41:07Z)
• A Recursively Recurrent Neural Network (R2N2) Architecture for Learning Iterative Algorithms [64.3064050603721]
  本研究では,リカレントニューラルネットワーク (R2N2) にランゲ・クッタニューラルネットワークを一般化し,リカレントニューラルネットワークを最適化した反復アルゴリズムの設計を行う。 本稿では, 線形方程式系に対するクリロフ解法, 非線形方程式系に対するニュートン・クリロフ解法, 常微分方程式に対するルンゲ・クッタ解法と類似の繰り返しを計算問題クラスの入力・出力データに対して提案した超構造内における重みパラメータの正規化について述べる。
  論文  参考訳（メタデータ） (2022-11-22T16:30:33Z)
• Accelerating the training of single-layer binary neural networks using the HHL quantum algorithm [58.720142291102135]
  Harrow-Hassidim-Lloyd (HHL) の量子力学的実装から有用な情報が抽出可能であることを示す。 しかし,本論文では,HHLの量子力学的実装から有用な情報を抽出し,古典的側面における解を見つける際の複雑性を低減することを目的としている。
  論文  参考訳（メタデータ） (2022-10-23T11:58:05Z)
• What Can Be Learnt With Wide Convolutional Neural Networks? [69.55323565255631]
  カーネルシステムにおける無限大の深層CNNについて検討する。 我々は,深部CNNが対象関数の空間スケールに適応していることを証明する。 我々は、別の深部CNNの出力に基づいて訓練された深部CNNの一般化誤差を計算して結論付ける。
  論文  参考訳（メタデータ） (2022-08-01T17:19:32Z)
• The Separation Capacity of Random Neural Networks [78.25060223808936]
  標準ガウス重みと一様分布バイアスを持つ十分に大きな2層ReLUネットワークは、この問題を高い確率で解くことができることを示す。 我々は、相互複雑性という新しい概念の観点から、データの関連構造を定量化する。
  論文  参考訳（メタデータ） (2021-07-31T10:25:26Z)
• The Computational Complexity of ReLU Network Training Parameterized by Data Dimensionality [8.940054309023525]
  トレーニングデータの寸法$d$が計算の複雑さに与える影響を分析します。 既知のブルートフォース戦略が本質的に最適であることを示す。 特に、一定の$d$ と凸損失関数に対する既知の時間アルゴリズムを、より一般的な損失関数のクラスに拡張する。
  論文  参考訳（メタデータ） (2021-05-18T17:05:26Z)
• Achieving Small Test Error in Mildly Overparameterized Neural Networks [30.664282759625948]
  時間内にこれらの点の1つを見つけるアルゴリズムを示す。 さらに、我々は、完全に接続されたニューラルネットワークのために、データ分布に追加の仮定で、時間アルゴリズムがあることを証明します。
  論文  参考訳（メタデータ） (2021-04-24T06:47:20Z)
• Vector-output ReLU Neural Network Problems are Copositive Programs: Convex Analysis of Two Layer Networks and Polynomial-time Algorithms [29.975118690758126]
  2層ベクトル無限ReLUニューラルネットワークトレーニング問題の半出力グローバル双対について述べる。 特定の問題のクラスに対して正確であることが保証されるソリューションを提供する。
  論文  参考訳（メタデータ） (2020-12-24T17:03:30Z)
• Measuring Model Complexity of Neural Networks with Curve Activation Functions [100.98319505253797]
  本稿では,線形近似ニューラルネットワーク(LANN)を提案する。 ニューラルネットワークのトレーニングプロセスを実験的に検討し、オーバーフィッティングを検出する。 我々は、$L1$と$L2$正規化がモデルの複雑さの増加を抑制することを発見した。
  論文  参考訳（メタデータ） (2020-06-16T07:38:06Z)

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

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