論文の概要: New Complexity-Theoretic Frontiers of Tractability for Neural Network Training

• arxiv url: http://arxiv.org/abs/2607.20811v1
• Date: Thu, 23 Jul 2026 00:44:44 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-24 18:26:25.25295
• Title: New Complexity-Theoretic Frontiers of Tractability for Neural Network Training
• Title（参考訳）: ニューラルネットトレーニングのためのトラクタビリティの新しい複雑性理論フロンティア
• Abstract要約: 機械学習研究におけるニューラルネットワークの基本的な役割にもかかわらず、ニューラルネットワークを最適に訓練することの理解はいまだ不完全である。 本稿では、トレーニングのための新しいアルゴリズム上界と、最適性のためのReLU活性化ニューラルネットワークを得る。
• 参考スコア（独自算出の注目度）: 17.54018378847318
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In spite of the fundamental role of neural networks in contemporary machine learning research, our understanding of the computational complexity of optimally training neural networks remains incomplete even when dealing with the simplest kinds of activation functions. Indeed, while there has been a number of very recent results that establish ever-tighter lower bounds for the problem under linear and ReLU activation functions, less progress has been made towards the identification of novel polynomial-time tractable network architectures. In this article we obtain novel algorithmic upper bounds for training linear- and ReLU-activated neural networks to optimality which push the boundaries of tractability for these problems beyond the previous state of the art. In particular, for ReLU networks we establish the polynomial-time tractability of all architectures where hidden neurons have an out-degree of $1$, improving upon the previous algorithm of Arora, Basu, Mianjy and Mukherjee. On the other hand, for networks with linear activation functions we identify the first non-trivial polynomial-time solvable class of networks by obtaining an algorithm that can optimally train network architectures satisfying a novel data throughput condition.
• Abstract（参考訳）: 現代の機械学習研究におけるニューラルネットワークの基本的な役割にもかかわらず、ニューラルネットワークを最適に訓練する際の計算複雑性の理解は、最も単純な種類のアクティベーション関数を扱う場合でも不完全である。 実際、線形およびReLUアクティベーション関数の下で問題に対するより高次の下限を確立する非常に最近の成果はいくつかあるが、新しい多項式時間トラクタブルネットワークアーキテクチャの同定に向けた進歩は少ない。 本稿では、線形およびReLU活性化ニューラルネットワークを最適に訓練するための新しいアルゴリズム上界を得る。 特に、ReLUネットワークでは、隠れたニューロンが1ドルを超える全てのアーキテクチャの多項式時間トラクタビリティを確立し、以前のアルゴリズムであるArora、Basu、Mianjy、Mukherjeeを改良する。 一方、線形アクティベーション関数を持つネットワークに対しては、新しいスループット条件を満たすネットワークアーキテクチャを最適に訓練できるアルゴリズムを探索することにより、最初の非自明な多項式時間解決可能なネットワークのクラスを同定する。

関連論文リスト

• Unveiling Hidden Convexity in Deep Learning: a Sparse Signal Processing Perspective [51.908606610432194]
  ディープニューラルネットワーク(DNN)は、さまざまな機械学習タスクで大きな成功を収めています。 近年の研究では、特定のNNアーキテクチャが失われる際のいくつかの凸性を明らかにしている。
  論文  参考訳（メタデータ） (2026-03-25T01:34:04Z)
• NeuralFastLAS: Fast Logic-Based Learning from Raw Data [54.938128496934695]
  シンボリック・ルール学習者は解釈可能な解を生成するが、入力を記号的に符号化する必要がある。 ニューロシンボリックアプローチは、ニューラルネットワークを使用して生データを潜在シンボリック概念にマッピングすることで、この問題を克服する。 我々は,ニューラルネットワークを記号学習者と共同でトレーニングする,スケーラブルで高速なエンドツーエンドアプローチであるNeuralFastLASを紹介する。
  論文  参考訳（メタデータ） (2023-10-08T12:33:42Z)
• When Deep Learning Meets Polyhedral Theory: A Survey [5.59187625600025]
  過去10年間で、ディープ・ニューラル・ラーニングの顕著な精度のおかげで、ディープは予測モデリングの一般的な方法論となった。 一方、ニューラルネットワークの構造はより単純で線形な関数に収束した。
  論文  参考訳（メタデータ） (2023-04-29T11:46:53Z)
• Globally Optimal Training of Neural Networks with Threshold Activation Functions [63.03759813952481]
  しきい値アクティベートを伴うディープニューラルネットワークの重み劣化正規化学習問題について検討した。 ネットワークの特定の層でデータセットを破砕できる場合に、簡易な凸最適化の定式化を導出する。
  論文  参考訳（メタデータ） (2023-03-06T18:59:13Z)
• Spiking neural network for nonlinear regression [68.8204255655161]
  スパイクニューラルネットワークは、メモリとエネルギー消費を大幅に削減する可能性を持っている。 彼らは、次世代のニューロモルフィックハードウェアによって活用できる時間的および神経的疎結合を導入する。 スパイキングニューラルネットワークを用いた回帰フレームワークを提案する。
  論文  参考訳（メタデータ） (2022-10-06T13:04:45Z)
• Neural networks with linear threshold activations: structure and algorithms [1.795561427808824]
  クラス内で表現可能な関数を表現するのに、2つの隠れたレイヤが必要であることを示す。 また、クラス内の任意の関数を表すのに必要なニューラルネットワークのサイズについて、正確な境界を与える。 我々は,線形しきい値ネットワークと呼ばれるニューラルネットワークの新たなクラスを提案する。
  論文  参考訳（メタデータ） (2021-11-15T22:33:52Z)
• A Weight Initialization Based on the Linear Product Structure for Neural Networks [0.0]
  非線形的な観点からニューラルネットワークを研究し、ニューラルネットワークの線形積構造(LPS)に基づく新しいウェイト初期化戦略を提案する。 提案手法は, 数値代数学の理論を用いて, すべての局所最小値を求めることを保証することにより, 活性化関数の近似から導かれる。
  論文  参考訳（メタデータ） (2021-09-01T00:18:59Z)
• Validation of RELU nets with tropical polyhedra [7.087237546722617]
  本稿では,熱帯ポリヘドラを用いてReLUフィードフォワードニューラルネットワークを抽象化する手法を提案する。 本稿では、ReLUネットワークと熱帯有理関数の接続が、ReLUニューラルネットワークのレンジ解析にどのように役立つかを示す。
  論文  参考訳（メタデータ） (2021-07-30T06:22:59Z)
• Implicit recurrent networks: A novel approach to stationary input processing with recurrent neural networks in deep learning [0.0]
  本研究では,ニューラルネットの新たな実装を深層学習に導入し,検証する。 繰り返しネットワークの暗黙的な実装にバックプロパゲーションアルゴリズムを実装するアルゴリズムを提案する。 シングルレイヤの暗黙的リカレントネットワークはXOR問題を解くことができ、一方、単調に活性化関数が増加するフィードフォワードネットワークは、このタスクで失敗する。
  論文  参考訳（メタデータ） (2020-10-20T18:55:32Z)
• Learning Connectivity of Neural Networks from a Topological Perspective [80.35103711638548]
  本稿では,ネットワークを解析のための完全なグラフに表現するためのトポロジ的視点を提案する。 接続の規模を反映したエッジに学習可能なパラメータを割り当てることにより、学習プロセスを異なる方法で行うことができる。 この学習プロセスは既存のネットワークと互換性があり、より大きな検索空間と異なるタスクへの適応性を持っている。
  論文  参考訳（メタデータ） (2020-08-19T04:53:31Z)
• 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)

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

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