論文の概要: Training Neural Networks is ER-complete

• arxiv url: http://arxiv.org/abs/2102.09798v1
• Date: Fri, 19 Feb 2021 08:28:37 GMT
• ステータス: 処理完了
• システム内更新日: 2021-02-22 13:29:23.916747
• Title: Training Neural Networks is ER-complete
• Title（参考訳）: ニューラルネットワークのトレーニングはER完全
• Authors: Mikkel Abrahamsen, Linda Kleist, Tillmann Miltzow
• Abstract要約: ニューラルネットワーク、トレーニングデータ、およびしきい値を考えると、総誤差がしきい値以下であるようにニューラルネットワークにとってNPハードであることが知られていました。 ER完全であることを示すことにより、この根本的な問題を的確に決定する。 これは、ER方程式の系と整数係数と実未知のの不等式が解を持つかどうかを決定することと同値であることを意味する。
• 参考スコア（独自算出の注目度）: 0.7251305766151019
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Given a neural network, training data, and a threshold, it was known that it is NP-hard to find weights for the neural network such that the total error is below the threshold. We determine the algorithmic complexity of this fundamental problem precisely, by showing that it is ER-complete. This means that the problem is equivalent, up to polynomial-time reductions, to deciding whether a system of polynomial equations and inequalities with integer coefficients and real unknowns has a solution. If, as widely expected, ER is strictly larger than NP, our work implies that the problem of training neural networks is not even in NP.
• Abstract（参考訳）: ニューラルネットワーク、トレーニングデータ、およびしきい値を考えると、総誤差がしきい値以下であるようにニューラルネットワークの重みを見つけることはNPハードであることが知られていました。 この基本問題のアルゴリズム的複雑性を正確に決定し、ER完全であることを示した。 これは、多項式方程式の系と整数係数と実未知数の不等式が解を持つかどうかを決定できる多項式時間還元まで同値であることを意味する。 広く予想されているように、ER が NP よりも厳密に大きい場合、我々の研究は、ニューラルネットワークのトレーニングの問題は NP にも及ばないことを意味している。

関連論文リスト

• Verified Neural Compressed Sensing [58.98637799432153]
  精度の高い計算タスクのために、初めて(私たちの知識を最大限に活用するために)証明可能なニューラルネットワークを開発します。 極小問題次元(最大50)では、線形および双項線形測定からスパースベクトルを確実に回復するニューラルネットワークを訓練できることを示す。 ネットワークの複雑さは問題の難易度に適応できることを示し、従来の圧縮センシング手法が証明不可能な問題を解く。
  論文  参考訳（メタデータ） (2024-05-07T12:20:12Z)
• SPFQ: A Stochastic Algorithm and Its Error Analysis for Neural Network Quantization [5.982922468400901]
  ニューラルネットワークの重みの順に得られる誤差境界を達成可能であることを示す。 我々は、無限アルファベットと入力データに対する最小の仮定の下で、完全なネットワーク境界を達成できることを証明した。
  論文  参考訳（メタデータ） (2023-09-20T00:35:16Z)
• 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)
• The (Un)Scalability of Heuristic Approximators for NP-Hard Search Problems [25.641418039598587]
  A*アルゴリズムはNP-ハード最適化問題の解法として一般的に用いられる。 このような問題の多くに対する正確な近似もNPハードであることを示す。
  論文  参考訳（メタデータ） (2022-09-07T18:02:02Z)
• Reachability In Simple Neural Networks [2.7195102129095003]
  NP-hardnessは、単純な仕様とニューラルネットワークの制限されたクラスをすでに保持していることを示す。 我々は、ニューラルネットワーク検証研究のこの方向の展開の可能性について、徹底的な議論と展望を行う。
  論文  参考訳（メタデータ） (2022-03-15T14:25:44Z)
• Reachability Is NP-Complete Even for the Simplest Neural Networks [0.0]
  この問題は、一般的なニューラルネットワークと共役入力/出力仕様に対してNP完全である、と最近主張された。 NP-hardnessは1層のみの単純な仕様とニューラルネットワークの制限されたクラスをすでに保持していることを示す。
  論文  参考訳（メタデータ） (2021-08-30T12:38:57Z)
• The Separation Capacity of Random Neural Networks [78.25060223808936]
  標準ガウス重みと一様分布バイアスを持つ十分に大きな2層ReLUネットワークは、この問題を高い確率で解くことができることを示す。 我々は、相互複雑性という新しい概念の観点から、データの関連構造を定量化する。
  論文  参考訳（メタデータ） (2021-07-31T10:25:26Z)
• Redundant representations help generalization in wide neural networks [71.38860635025907]
  様々な最先端の畳み込みニューラルネットワークの最後に隠された層表現について検討する。 最後に隠された表現が十分に広ければ、そのニューロンは同一の情報を持つグループに分裂し、統計的に独立したノイズによってのみ異なる傾向にある。
  論文  参考訳（メタデータ） (2021-06-07T10:18:54Z)
• Conditional physics informed neural networks [85.48030573849712]
  固有値問題のクラス解を推定するための条件付きPINN(物理情報ニューラルネットワーク)を紹介します。 一つのディープニューラルネットワークが、問題全体に対する偏微分方程式の解を学習できることが示される。
  論文  参考訳（メタデータ） (2021-04-06T18:29:14Z)
• Abstraction based Output Range Analysis for Neural Networks [10.051309746913512]
  本稿では,ReLUアクティベーション機能を備えたフィードフォワードニューラルネットワークにおける出力範囲解析の問題点について考察する。 既存の手法は、出力範囲解析問題を満足度と最適化の解決に還元する。 より少ないニューロンで単純なニューラルネットワークを構築する新しい抽象化手法を提案する。
  論文  参考訳（メタデータ） (2020-07-18T22:24:54Z)
• Self-Organized Operational Neural Networks with Generative Neurons [87.32169414230822]
  ONNは、任意の非線型作用素をカプセル化できる一般化されたニューロンモデルを持つ異種ネットワークである。 我々は,各接続の結節演算子を適応(最適化)できる生成ニューロンを有する自己組織型ONN(Self-ONNs)を提案する。
  論文  参考訳（メタデータ） (2020-04-24T14:37:56Z)

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

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