論文の概要: ReLU Neural Networks of Polynomial Size for Exact Maximum Flow Computation

• arxiv url: http://arxiv.org/abs/2102.06635v5
• Date: Wed, 17 Jul 2024 15:31:15 GMT
• ステータス: 処理完了
• システム内更新日: 2024-07-19 00:00:34.676129
• Title: ReLU Neural Networks of Polynomial Size for Exact Maximum Flow Computation
• Title（参考訳）: 実最大流計算のためのReLUニューラルネット
• Authors: Christoph Hertrich, Leon Sering,
• Abstract要約: 本稿では,線形整流ユニットを用いたニューラルネットワークのパワーについて検討する。 我々は,2つの基本最適化問題を$mathcalO(m2n2)$のニューラルネットワークで解くことができることを示した。
• 参考スコア（独自算出の注目度）: 5.35599092568615
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper studies the expressive power of artificial neural networks with rectified linear units. In order to study them as a model of real-valued computation, we introduce the concept of Max-Affine Arithmetic Programs and show equivalence between them and neural networks concerning natural complexity measures. We then use this result to show that two fundamental combinatorial optimization problems can be solved with polynomial-size neural networks. First, we show that for any undirected graph with $n$ nodes, there is a neural network (with fixed weights and biases) of size $\mathcal{O}(n^3)$ that takes the edge weights as input and computes the value of a minimum spanning tree of the graph. Second, we show that for any directed graph with $n$ nodes and $m$ arcs, there is a neural network of size $\mathcal{O}(m^2n^2)$ that takes the arc capacities as input and computes a maximum flow. Our results imply that these two problems can be solved with strongly polynomial time algorithms that solely use affine transformations and maxima computations, but no comparison-based branchings.
• Abstract（参考訳）: 本稿では,線形整流ユニットを用いたニューラルネットワークの表現力について検討する。 実数値計算のモデルとして研究するために,Max-Affine Arithmetic Programsの概念を導入し,自然複雑性測定に関するニューラルネットワークとの等価性を示す。 この結果を用いて、多項式サイズのニューラルネットワークで2つの基本組合せ最適化問題を解くことができることを示す。 まず、$n$のノードを持つ任意の非方向グラフに対して、エッジウェイトを入力として取り、グラフの最小スパンニングツリーの値を計算する大きさ$\mathcal{O}(n^3)$のニューラルネットワーク(固定重みとバイアス)が存在することを示す。 第二に、$n$ノードと$m$アークを持つ任意の有向グラフに対して、最大フローを計算し、入力としてアーク容量を取る大きさの$\mathcal{O}(m^2n^2)$のニューラルネットワークが存在することを示す。 この結果は,アフィン変換と最大計算のみを用いる強い多項式時間アルゴリズムを用いて,これらの2つの問題を解くことができるが,比較に基づく分岐は行わないことを示唆している。

関連論文リスト

• Neural Networks and (Virtual) Extended Formulations [5.762677915745415]
  ニューラルネットワークのサイズに対する低い境界を、その代表的能力を拡張複雑性(mathrmxc(P)$)の概念にリンクすることで証明する。 通常の拡張複雑性の強力な結果は、モノトーンニューラルネットワークの下位境界に変換可能であることを示す。
  論文  参考訳（メタデータ） (2024-11-05T11:12:11Z)
• On the Complexity of Neural Computation in Superposition [3.9803704378699103]
  ニューラルネットワークの理解の最近の進歩は、重畳が大規模ネットワークの計算効率の根底にある重要なメカニズムであることを示唆している。 ペアワイズのような論理演算は、$O(sqrtm' log m')$ ニューロンと$O(m' log2 m')$パラメータで計算できる。 本研究は,ニューラルネットワークの解釈可能性研究における複雑性理論手法の活用の道を開くものである。
  論文  参考訳（メタデータ） (2024-09-05T18:58:59Z)
• Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit [75.4661041626338]
  単一インデックス対象関数 $f_*(boldsymbolx) = textstylesigma_*left(langleboldsymbolx,boldsymbolthetarangleright)$ の等方的ガウスデータの下で勾配降下学習の問題を考察する。 SGDアルゴリズムで最適化された2層ニューラルネットワークは、サンプル付き任意のリンク関数の$f_*$を学習し、実行時の複雑さは$n asymp T asymp C(q) cdot dであることを示す。
  論文  参考訳（メタデータ） (2024-06-03T17:56:58Z)
• Matching the Statistical Query Lower Bound for k-sparse Parity Problems with Stochastic Gradient Descent [83.85536329832722]
  勾配勾配降下(SGD)は,$d$次元ハイパーキューブ上の$k$パリティ問題を効率的に解くことができることを示す。 次に、SGDでトレーニングされたニューラルネットワークがどのようにして、小さな統計的エラーで$k$-parityの問題を解決するかを実証する。
  論文  参考訳（メタデータ） (2024-04-18T17:57:53Z)
• Moccasin: Efficient Tensor Rematerialization for Neural Networks [21.348126106786914]
  我々はtextscMoccasin という新しい制約プログラミングの定式化を開発し,O(n)$ の整数変数しか持たない。 本稿では,特に大規模グラフにおいて,我々のアプローチが最近の研究よりも桁違いに高速であることを示す数値的研究について述べる。
  論文  参考訳（メタデータ） (2023-04-27T18:41:37Z)
• Training Fully Connected Neural Networks is $\exists\mathbb{R}$-Complete [4.170994234169557]
  InpiricalRiskmization(英語版)として知られる、与えられたデータポイントのセットに可能な限り適合する2層完全連結ニューラルネットワークの重みとバイアスを求める問題を考察する。 任意のデータポイントが有理である場合でも、いくつかのインスタンスを最適に訓練できるウェイトとして、任意の大きな次数の代数数が必要であることを証明します。 この結果、Basu, Mianjy, Mukherjee [ICLR 2018]のような検索アルゴリズムは、$mathsfNP=existsでない限り、複数の出力次元を持つネットワークでは不可能である。
  論文  参考訳（メタデータ） (2022-04-04T10:28:11Z)
• Minimax Optimal Quantization of Linear Models: Information-Theoretic Limits and Efficient Algorithms [59.724977092582535]
  測定から学習した線形モデルの定量化の問題を考える。 この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。 本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
  論文  参考訳（メタデータ） (2022-02-23T02:39:04Z)
• The Separation Capacity of Random Neural Networks [78.25060223808936]
  標準ガウス重みと一様分布バイアスを持つ十分に大きな2層ReLUネットワークは、この問題を高い確率で解くことができることを示す。 我々は、相互複雑性という新しい概念の観点から、データの関連構造を定量化する。
  論文  参考訳（メタデータ） (2021-07-31T10:25:26Z)
• Deep Polynomial Neural Networks [77.70761658507507]
  $Pi$Netsは拡張に基づいた関数近似の新しいクラスである。 $Pi$Netsは、画像生成、顔検証、および3Dメッシュ表現学習という3つの困難なタスクで、最先端の結果を生成する。
  論文  参考訳（メタデータ） (2020-06-20T16:23:32Z)
• Multipole Graph Neural Operator for Parametric Partial Differential Equations [57.90284928158383]
  物理系をシミュレーションするためのディープラーニングベースの手法を使用する際の大きな課題の1つは、物理ベースのデータの定式化である。 線形複雑度のみを用いて、あらゆる範囲の相互作用をキャプチャする、新しいマルチレベルグラフニューラルネットワークフレームワークを提案する。 実験により, 離散化不変解演算子をPDEに学習し, 線形時間で評価できることを確認した。
  論文  参考訳（メタデータ） (2020-06-16T21:56:22Z)
• A Corrective View of Neural Networks: Representation, Memorization and Learning [26.87238691716307]
  我々はニューラルネットワーク近似の補正機構を開発する。 ランダム・フィーチャー・レギュレーション(RF)における2層ニューラルネットワークは任意のラベルを記憶できることを示す。 また、3層ニューラルネットワークについても検討し、その補正機構がスムーズなラジアル関数に対する高速な表現率をもたらすことを示す。
  論文  参考訳（メタデータ） (2020-02-01T20:51:09Z)

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

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