論文の概要: Size and Depth Separation in Approximating Natural Functions with Neural
Networks
- arxiv url: http://arxiv.org/abs/2102.00314v2
- Date: Wed, 3 Feb 2021 01:51:12 GMT
- ステータス: 処理完了
- システム内更新日: 2021-02-04 12:53:33.852106
- Title: Size and Depth Separation in Approximating Natural Functions with Neural
Networks
- Title（参考訳）: ニューラルネットワークによる自然関数の近似におけるサイズと深さの分離
- Authors: Gal Vardi, Daniel Reichman, Toniann Pitassi, Ohad Shamir
- Abstract要約: 本稿では,ReLUネットワークを用いた自然関数の近似におけるサイズと深さの利点を示す。
我々は、そのような結果が$O(d)$を超えることを証明するための複雑性理論上の障壁を示す。
また、サイズ$O(d)$のネットワークで近似できる明示的な自然関数も示している。
- 参考スコア（独自算出の注目度）: 52.73592689730044
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: When studying the expressive power of neural networks, a main challenge is to
understand how the size and depth of the network affect its ability to
approximate real functions. However, not all functions are interesting from a
practical viewpoint: functions of interest usually have a polynomially-bounded
Lipschitz constant, and can be computed efficiently. We call functions that
satisfy these conditions "natural", and explore the benefits of size and depth
for approximation of natural functions with ReLU networks. As we show, this
problem is more challenging than the corresponding problem for non-natural
functions. We give barriers to showing depth-lower-bounds: Proving existence of
a natural function that cannot be approximated by polynomial-size networks of
depth $4$ would settle longstanding open problems in computational complexity.
It implies that beyond depth $4$ there is a barrier to showing depth-separation
for natural functions, even between networks of constant depth and networks of
nonconstant depth. We also study size-separation, namely, whether there are
natural functions that can be approximated with networks of size $O(s(d))$, but
not with networks of size $O(s'(d))$. We show a complexity-theoretic barrier to
proving such results beyond size $O(d\log^2(d))$, but also show an explicit
natural function, that can be approximated with networks of size $O(d)$ and not
with networks of size $o(d/\log d)$. For approximation in $L_\infty$ we achieve
such separation already between size $O(d)$ and size $o(d)$. Moreover, we show
superpolynomial size lower bounds and barriers to such lower bounds, depending
on the assumptions on the function. Our size-separation results rely on an
analysis of size lower bounds for Boolean functions, which is of independent
interest: We show linear size lower bounds for computing explicit Boolean
functions with neural networks and threshold circuits.
- Abstract（参考訳）: ニューラルネットワークの表現力を調べるとき、ネットワークのサイズと深さが実際の関数を近似する能力にどのように影響するかを理解することが主な課題です。
しかし、すべての函数は実際的な観点から興味深いわけではない: 興味のある函数は通常多項式有界リプシッツ定数を持ち、効率的に計算できる。
これらの条件を満たす関数を「自然」と呼び、ReLUネットワークによる自然関数の近似のためのサイズと深さの利点を探ります。
私たちが示すように、この問題は非自然関数の対応する問題よりも困難です。
深さ4$の多項式サイズのネットワークでは近似できない自然関数の存在を証明すれば、計算の複雑さにおける長年のオープンな問題を解決できる。
深さ4ドルを超えると、一定の深さのネットワークと非定数深さのネットワークの間でも、自然関数の深さ分離を示すための障壁がある。
また、サイズ分離、すなわち、サイズ $o(s(d))$ のネットワークで近似できるが、サイズ $o(s'(d))$ のネットワークで近似できる自然関数が存在するかどうかについても研究した。
このような結果がサイズ $o(d\log^2(d))$ を超えることを証明するための複雑性理論上の障壁を示すとともに、サイズ $o(d)$ で近似でき、サイズ $o(d/\log d)$ のネットワークで近似できる明示的な自然関数も示す。
L_\infty$ の近似に対して、既に$O(d)$ と $o(d)$ の分離が達成されている。
さらに、関数の仮定に応じて、超多項式サイズの下限とそのような下限への障壁を示す。
サイズ分離の結果は,boolean関数のサイズ下限の解析に依存するが,それとは独立に,ニューラルネットワークとしきい値回路を用いた明示的なboolean関数の線形サイズ下限を示す。
関連論文リスト
- Neural Networks and (Virtual) Extended Formulations [5.762677915745415]
ニューラルネットワークのサイズに対する低い境界を、その代表的能力を拡張複雑性(mathrmxc(P)$)の概念にリンクすることで証明する。
通常の拡張複雑性の強力な結果は、モノトーンニューラルネットワークの下位境界に変換可能であることを示す。
論文 参考訳（メタデータ） (2024-11-05T11:12:11Z) - Expressivity and Approximation Properties of Deep Neural Networks with
ReLU$^k$ Activation [2.3020018305241337]
本稿では、ReLU$k$Activation Function for $k geq 2$を用いたディープネットワークの表現性と近似特性について検討する。
ディープ ReLU$k$ ネットワークは効率的に近似できるが、ディープ ReLU$k$ ネットワークは高次を正確に表現することができる。
論文 参考訳（メタデータ） (2023-12-27T09:11:14Z) - Universal approximation with complex-valued deep narrow neural networks [0.0]
境界幅と任意の深さを持つ複素数値ニューラルネットワークの普遍性について検討する。
より狭い複素数値ネットワークは、その活性化関数が正則でもなく、反正則でもなく、$mathbbR$-affineでもない場合に限り普遍であることを示す。
論文 参考訳（メタデータ） (2023-05-26T13:22:14Z) - Understanding Deep Neural Function Approximation in Reinforcement
Learning via $\epsilon$-Greedy Exploration [53.90873926758026]
本稿では、強化学習(RL)における深部神経機能近似の理論的研究について述べる。
我々は、Besov(およびBarron)関数空間によって与えられるディープ(および2層)ニューラルネットワークによる$epsilon$-greedy探索により、バリューベースのアルゴリズムに焦点を当てる。
我々の解析は、ある平均測度$mu$の上の$L2(mathrmdmu)$-integrable空間における時間差誤差を再構成し、非イド設定の下で一般化問題に変換する。
論文 参考訳（メタデータ） (2022-09-15T15:42:47Z) - Deep neural network approximation of analytic functions [91.3755431537592]
ニューラルネットワークの空間に エントロピーバウンド 片方向の線形活性化関数を持つ
我々は、ペナル化深部ニューラルネットワーク推定器の予測誤差に対するオラクルの不等式を導出する。
論文 参考訳（メタデータ） (2021-04-05T18:02:04Z) - A deep network construction that adapts to intrinsic dimensionality
beyond the domain [79.23797234241471]
本稿では,ReLUを活性化したディープネットワークを用いて,2層合成の近似を$f(x) = g(phi(x))$で検討する。
例えば、低次元埋め込み部分多様体への射影と、低次元集合の集合への距離である。
論文 参考訳（メタデータ） (2020-08-06T09:50:29Z) - Interval Universal Approximation for Neural Networks [47.767793120249095]
区間普遍近似(IUA)定理を導入する。
IUAは、ニューラルネットワークが何十年にもわたって知られているような、あらゆる連続関数の$f$を近似できることを示している。
本稿では,精度の高い区間解析が可能なニューラルネットワークを構築する際の計算複雑性について検討する。
論文 参考訳（メタデータ） (2020-07-12T20:43:56Z) - Neural Networks with Small Weights and Depth-Separation Barriers [40.66211670342284]
一定の深さでは、既存の結果が2ドルと3ドルに制限され、より深い深さで結果を達成することが重要な問題となっている。
我々はフィードフォワードのReLUネットワークに注力し、その効果を4ドル以上の金額で証明する上での基本的な障壁を証明している。
論文 参考訳（メタデータ） (2020-05-31T21:56:17Z) - On the Modularity of Hypernetworks [103.1147622394852]
構造化対象関数の場合、ハイパーネットワークにおけるトレーニング可能なパラメータの総数は、標準ニューラルネットワークのトレーニング可能なパラメータの数や埋め込み法よりも桁違いに小さいことを示す。
論文 参考訳（メタデータ） (2020-02-23T22:51:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。