Fugu-MT 論文翻訳(概要): ReLU Neural Networks for Exact Maximum Flow Computation

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

arxiv url: http://arxiv.org/abs/2102.06635v1
Date: Fri, 12 Feb 2021 17:23:34 GMT
ステータス: 処理完了
システム内更新日: 2021-02-15 13:11:39.309481
Title: ReLU Neural Networks for Exact Maximum Flow Computation
Title（参考訳）: 完全最大流量計算のためのreluニューラルネットワーク
Authors: Christoph Hertrich and Leon Sering
Abstract要約: n$のノードと$m$のarcを持つ有向グラフが与えられたとき、任意の実アーク容量から最大フローを入力として計算する表現的大きさのnnが存在することを示す。次に、最大フロー問題を正確に解くためにMAAPを設計し、$mathcalO(m2 n2)$のNNに変換する。
参考スコア（独自算出の注目度）: 0.30458514384586405
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Understanding the great empirical success of artificial neural networks (NNs) from a theoretical point of view is currently one of the hottest research topics in computer science. In this paper we study the expressive power of NNs with rectified linear units from a combinatorial optimization perspective. In particular, we show that, given a directed graph with $n$ nodes and $m$ arcs, there exists an NN of polynomial size that computes a maximum flow from any possible real-valued arc capacities as input. To prove this, we develop the pseudo-code language Max-Affine Arithmetic Programs (MAAPs) and show equivalence between MAAPs and NNs concerning natural complexity measures. We then design a MAAP to exactly solve the Maximum Flow Problem, which translates to an NN of size $\mathcal{O}(m^2 n^2)$.
Abstract（参考訳）: 理論的な観点からのニューラルネットワーク(nns)の偉大な実証的成功を理解することは、現在コンピュータ科学で最もホットな研究トピックの1つです。本稿では, 線形整列単位を用いたNNの表現力について, 組合せ最適化の観点から検討する。特に、$n$ノードと$m$アークを持つ有向グラフを考えると、入力として可能な実値アーク容量から最大フローを計算する多項式サイズのNNが存在することを示しています。これを証明するために、擬似符号言語Max-Affine Arithmetic Programs(MAAP)を開発し、自然複雑性対策に関するMAAPとNNの等価性を示す。次に、最大フロー問題を正確に解くためにMAAPを設計し、サイズが$\mathcal{O}(m^2 n^2)$のNNに変換する。

関連論文リスト

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)

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