Fugu-MT 論文翻訳(概要): Neural Networks and (Virtual) Extended Formulations

論文の概要: Neural Networks and (Virtual) Extended Formulations

arxiv url: http://arxiv.org/abs/2411.03006v2
Date: Tue, 11 Feb 2025 14:19:32 GMT
ステータス: 翻訳完了
システム内更新日: 2025-02-12 14:02:59.711989
Title: Neural Networks and (Virtual) Extended Formulations
Title（参考訳）: ニューラルネットワークと(仮想)拡張形式
Authors: Christoph Hertrich, Georg Loho,
Abstract要約: 私たちは、$P$を最適化するニューラルネットワークのサイズに対して、より低い境界を証明します。我々は、$mathrmxc(P)$が任意のモノトーンや入力ニューラルネットワークのサイズの低い境界であることを示し、$P$を超える線形最適化問題を解く。
参考スコア（独自算出の注目度）: 5.762677915745415
License:
Abstract: Neural networks with piecewise linear activation functions, such as rectified linear units (ReLU) or maxout, are among the most fundamental models in modern machine learning. We make a step towards proving lower bounds on the size of such neural networks by linking their representative capabilities to the notion of the extension complexity $\mathrm{xc}(P)$ of a polytope $P$. This is a well-studied quantity in combinatorial optimization and polyhedral geometry describing the number of inequalities needed to model $P$ as a linear program. We show that $\mathrm{xc}(P)$ is a lower bound on the size of any monotone or input-convex neural network that solves the linear optimization problem over $P$. This implies exponential lower bounds on such neural networks for a variety of problems, including the polynomially solvable maximum weight matching problem. In an attempt to prove similar bounds also for general neural networks, we introduce the notion of virtual extension complexity $\mathrm{vxc}(P)$, which generalizes $\mathrm{xc}(P)$ and describes the number of inequalities needed to represent the linear optimization problem over $P$ as a difference of two linear programs. We prove that $\mathrm{vxc}(P)$ is a lower bound on the size of any neural network that optimizes over $P$. While it remains an open question to derive useful lower bounds on $\mathrm{vxc}(P)$, we argue that this quantity deserves to be studied independently from neural networks by proving that one can efficiently optimize over a polytope $P$ using a small virtual extended formulation.
Abstract（参考訳）: 整列線形単位(rerectified linear unit, RELU)やmaxoutのような一方向線形活性化関数を持つニューラルネットワークは、現代の機械学習において最も基本的なモデルである。このようなニューラルネットワークの大きさの低い境界を、その代表的能力と拡張複雑性の概念を結びつけることで証明する。これは組合せ最適化と多面的幾何学においてよく研究された量であり、$P$を線形プログラムとしてモデル化するのに必要な不等式の数を記述する。我々は、$\mathrm{xc}(P)$が任意のモノトーンまたは入力凸ニューラルネットワークのサイズの低い境界であることを示し、$P$を超える線形最適化問題を解く。これは、多項式的に解ける最大重み付け問題を含む様々な問題に対する、そのようなニューラルネットワーク上の指数的な下界を意味する。一般のニューラルネットワークにも同様の境界を証明しようとすると、仮想拡張複雑性$\mathrm{vxc}(P)$の概念を導入し、$\mathrm{xc}(P)$を一般化し、2つの線形プログラムの差分として$P$を超える線形最適化問題を表現するのに必要な不等式の数を記述する。我々は、$\mathrm{vxc}(P)$が、$P$を最適化する任意のニューラルネットワークのサイズの低い境界であることを証明する。この値は、$\mathrm{vxc}(P)$の有用な下限を導出するには、未解決の問題であるが、小さな仮想拡張式を用いて、ポリトープ$P$を効率的に最適化できることを証明することによって、ニューラルネットワークから独立して研究すべきである、と我々は主張する。

関連論文リスト

Deep Neural Networks: Multi-Classification and Universal Approximation [0.0]
我々は,幅2ドル,深さ2N+4M-1$のReLUディープニューラルネットワークが,$N$要素からなる任意のデータセットに対して有限標本記憶を達成できることを実証した。また、$W1,p$関数を近似するための深さ推定と$Lp(Omega;mathbbRm)$ for $mgeq1$を近似するための幅推定も提供する。
論文参考訳（メタデータ） (2024-09-10T14:31:21Z)
Learning sum of diverse features: computational hardness and efficient gradient-based training for ridge combinations [40.77319247558742]
目的関数 $f_*:mathbbRdtomathbbR$ を加法構造で学習する際の計算複雑性について検討する。 2層ニューラルネットワークの勾配学習により,$f_*$の大規模なサブセットを効率的に学習できることを実証した。
論文参考訳（メタデータ） (2024-06-17T17:59:17Z)
Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文参考訳（メタデータ） (2023-07-24T14:37:22Z)
Shallow neural network representation of polynomials [91.3755431537592]
d+1+sum_r=2Rbinomr+d-1d-1[binomr+d-1d-1d-1[binomr+d-1d-1d-1]binomr+d-1d-1d-1[binomr+d-1d-1d-1]binomr+d-1d-1d-1]
論文参考訳（メタデータ） (2022-08-17T08:14:52Z)
Minimax Optimal Quantization of Linear Models: Information-Theoretic Limits and Efficient Algorithms [59.724977092582535]
測定から学習した線形モデルの定量化の問題を考える。この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
論文参考訳（メタデータ） (2022-02-23T02:39:04Z)
On the Provable Generalization of Recurrent Neural Networks [7.115768009778412]
リカレントニューラルネットワーク(RNN)のトレーニングと一般化の分析正規化条件を使わずに関数を学習する一般化誤差を証明した。また、入力シーケンスのN-変数関数を学習するための新しい結果も証明する。
論文参考訳（メタデータ） (2021-09-29T02:06:33Z)
The Separation Capacity of Random Neural Networks [78.25060223808936]
標準ガウス重みと一様分布バイアスを持つ十分に大きな2層ReLUネットワークは、この問題を高い確率で解くことができることを示す。我々は、相互複雑性という新しい概念の観点から、データの関連構造を定量化する。
論文参考訳（メタデータ） (2021-07-31T10:25:26Z)
ReLU Neural Networks of Polynomial Size for Exact Maximum Flow Computation [5.35599092568615]
本稿では,線形整流ユニットを用いたニューラルネットワークのパワーについて検討する。我々は,2つの基本最適化問題を$mathcalO(m2n2)$のニューラルネットワークで解くことができることを示した。
論文参考訳（メタデータ） (2021-02-12T17:23:34Z)
Learning Over-Parametrized Two-Layer ReLU Neural Networks beyond NTK [58.5766737343951]
2層ニューラルネットワークを学習する際の降下のダイナミクスについて考察する。過度にパラメータ化された2層ニューラルネットワークは、タンジェントサンプルを用いて、ほとんどの地上で勾配損失を許容的に学習できることを示す。
論文参考訳（メタデータ） (2020-07-09T07:09:28Z)
On the Modularity of Hypernetworks [103.1147622394852]
構造化対象関数の場合、ハイパーネットワークにおけるトレーニング可能なパラメータの総数は、標準ニューラルネットワークのトレーニング可能なパラメータの数や埋め込み法よりも桁違いに小さいことを示す。
論文参考訳（メタデータ） (2020-02-23T22:51:52Z)
A Corrective View of Neural Networks: Representation, Memorization and Learning [26.87238691716307]
我々はニューラルネットワーク近似の補正機構を開発する。ランダム・フィーチャー・レギュレーション(RF)における2層ニューラルネットワークは任意のラベルを記憶できることを示す。また、3層ニューラルネットワークについても検討し、その補正機構がスムーズなラジアル関数に対する高速な表現率をもたらすことを示す。
論文参考訳（メタデータ） (2020-02-01T20:51:09Z)

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

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