論文の概要: Neural Networks and (Virtual) Extended Formulations
- arxiv url: http://arxiv.org/abs/2411.03006v1
- Date: Tue, 05 Nov 2024 11:12:11 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-11-06 14:55:01.504397
- Title: Neural Networks and (Virtual) Extended Formulations
- Title（参考訳）: ニューラルネットワークと(仮想)拡張形式
- Authors: Christoph Hertrich, Georg Loho,
- Abstract要約: ニューラルネットワークのサイズに対する低い境界を、その代表的能力を拡張複雑性(mathrmxc(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$, a well-studied quantity in combinatorial optimization and polyhedral geometry. To this end, we propose the notion of virtual extension complexity $\mathrm{vxc}(P)=\min\{\mathrm{xc}(Q)+\mathrm{xc}(R)\mid P+Q=R\}$. This 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 a neural network that optimizes over $P$. While it remains open to derive strong lower bounds on virtual extension complexity, we show that powerful results on the ordinary extension complexity can be converted into lower bounds for monotone neural networks, that is, neural networks with only nonnegative weights. Furthermore, we show that one can efficiently optimize over a polytope $P$ using a small virtual extended formulation. We therefore believe that virtual extension complexity deserves to be studied independently from neural networks, just like the ordinary extension complexity. As a first step in this direction, we derive an example showing that extension complexity can go down under Minkowski sum.
- Abstract（参考訳）: 整列線形単位(rerectified linear unit, RELU)やmaxoutのような一方向線形活性化関数を持つニューラルネットワークは、現代の機械学習において最も基本的なモデルである。
我々は、それらの代表的能力を拡張複雑性の概念に結びつけることで、そのようなニューラルネットワークの大きさの低い境界を証明するための一歩を踏み出した: $\mathrm{xc}(P)$, a polytope $P$, a well-expudied amount in combinatorial optimization and polyhedral geometry。
この目的のために、仮想拡張複雑性 $\mathrm{vxc}(P)=\min\{\mathrm{xc}(Q)+\mathrm{xc}(R)\mid P+Q=R\}$ の概念を提案する。
これは$\mathrm{xc}(P)$を一般化し、2つの線形プログラムの違いとして$P$を超える線形最適化問題を表すのに必要な不等式の数を記述する。
我々は、$\mathrm{vxc}(P)$が、$P$を最適化するニューラルネットワークのサイズの低い境界であることを証明する。
仮想拡張複雑性の強い下界を導出することは依然としてオープンであるが、通常の拡張複雑性の強力な結果は、モノトーンニューラルネットワーク、すなわち非負の重みしか持たないニューラルネットワークの下位境界に変換可能であることを示す。
さらに,仮想的に拡張された小さな定式化を用いて,ポリトープの$P$を効率よく最適化できることを示す。
したがって、通常の拡張複雑性と同じように、仮想拡張複雑性はニューラルネットワークから独立して研究されるべきである、と我々は信じている。
この方向への第一歩として、ミンコフスキー和の下で拡張複雑性が下降できることを示す例を導出する。
関連論文リスト
- 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) - Neural Network Approximation of Continuous Functions in High Dimensions
with Applications to Inverse Problems [6.84380898679299]
現在の理論では、ネットワークは問題の次元で指数関数的にスケールすべきだと予測されている。
ニューラルネットワークがH"より古い(あるいは一様)連続関数を近似するのに要する複雑性を境界付ける一般的な方法を提案する。
論文 参考訳（メタデータ） (2022-08-28T22:44:07Z) - 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) - 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) - Size and Depth Separation in Approximating Natural Functions with Neural
Networks [52.73592689730044]
本稿では,ReLUネットワークを用いた自然関数の近似におけるサイズと深さの利点を示す。
我々は、そのような結果が$O(d)$を超えることを証明するための複雑性理論上の障壁を示す。
また、サイズ$O(d)$のネットワークで近似できる明示的な自然関数も示している。
論文 参考訳（メタデータ） (2021-01-30T21:30:11Z) - On Function Approximation in Reinforcement Learning: Optimism in the
Face of Large State Spaces [208.67848059021915]
強化学習のコアにおける探索・探索トレードオフについて検討する。
特に、関数クラス $mathcalF$ の複雑さが関数の複雑さを特徴づけていることを証明する。
私たちの後悔の限界はエピソードの数とは無関係です。
論文 参考訳（メタデータ） (2020-11-09T18:32:22Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。