論文の概要: An Exponential Improvement on the Memorization Capacity of Deep
Threshold Networks
- arxiv url: http://arxiv.org/abs/2106.07724v1
- Date: Mon, 14 Jun 2021 19:42:32 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-16 15:21:51.692603
- Title: An Exponential Improvement on the Memorization Capacity of Deep
Threshold Networks
- Title(参考訳): ディープしきい値ネットワークの記憶容量の指数関数的改善
- Authors: Shashank Rajput, Kartik Sreenivasan, Dimitris Papailiopoulos, Amin
Karbasi
- Abstract要約: 我々は$widetildemathcalO(e1/delta2+sqrtn)$ニューロンと$widetildemathcalO(fracddelta+n)$ウェイトが十分であることを証明した。
また、超平面を用いて球面上の$n$の点を分離する純粋に幾何学的な問題にニューラルネットワークを接続することで、新しい下界を証明した。
- 参考スコア(独自算出の注目度): 40.489350374378645
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: It is well known that modern deep neural networks are powerful enough to
memorize datasets even when the labels have been randomized. Recently,
Vershynin (2020) settled a long standing question by Baum (1988), proving that
\emph{deep threshold} networks can memorize $n$ points in $d$ dimensions using
$\widetilde{\mathcal{O}}(e^{1/\delta^2}+\sqrt{n})$ neurons and
$\widetilde{\mathcal{O}}(e^{1/\delta^2}(d+\sqrt{n})+n)$ weights, where $\delta$
is the minimum distance between the points. In this work, we improve the
dependence on $\delta$ from exponential to almost linear, proving that
$\widetilde{\mathcal{O}}(\frac{1}{\delta}+\sqrt{n})$ neurons and
$\widetilde{\mathcal{O}}(\frac{d}{\delta}+n)$ weights are sufficient. Our
construction uses Gaussian random weights only in the first layer, while all
the subsequent layers use binary or integer weights. We also prove new lower
bounds by connecting memorization in neural networks to the purely geometric
problem of separating $n$ points on a sphere using hyperplanes.
- Abstract(参考訳): 現代のディープニューラルネットワークは、ラベルがランダム化されてもデータセットを記憶できるほど強力なことはよく知られている。
最近、vershynin (2020) は baum (1988) による長い疑問を解決し、\emph{deep threshold} ネットワークは$\widetilde{\mathcal{o}}(e^{1/\delta^2}+\sqrt{n})$ニューロンと$\widetilde{\mathcal{o}}(e^{1/\delta^2}(d+\sqrt{n})+n)$(ここで $\delta$ は点間の最小距離である。
本研究では、指数関数からほぼ線型への$\delta$依存を改善し、$\widetilde{\mathcal{O}}(\frac{1}{\delta}+\sqrt{n})$ニューロンと$\widetilde{\mathcal{O}}(\frac{d}{\delta}+n)$ウェイトが十分であることを証明した。
我々の構成では最初の層でのみガウスのランダム重みを使い、それに続く全ての層はバイナリまたは整数重みを使います。
また,超平面を用いて球面上の点を分離する純粋幾何問題とニューラルネットワークの記憶化を結びつけることで,新たな下界を証明した。
関連論文リスト
- Bayesian Inference with Deep Weakly Nonlinear Networks [57.95116787699412]
我々は,完全連結ニューラルネットワークによるベイズ推定が解けることを示す物理レベルの厳密さを示す。
我々はモデルエビデンスを計算し、任意の温度で1/N$で任意の順序に後続する手法を提供する。
論文 参考訳(メタデータ) (2024-05-26T17:08:04Z) - Learning Hierarchical Polynomials with Three-Layer Neural Networks [56.71223169861528]
3層ニューラルネットワークを用いた標準ガウス分布における階層関数の学習問題について検討する。
次数$k$s$p$の大規模なサブクラスの場合、正方形損失における階層的勾配によるトレーニングを受けた3層ニューラルネットワークは、テストエラーを消すためにターゲット$h$を学習する。
この研究は、3層ニューラルネットワークが複雑な特徴を学習し、その結果、幅広い階層関数のクラスを学ぶ能力を示す。
論文 参考訳(メタデータ) (2023-11-23T02:19:32Z) - Rates of Approximation by ReLU Shallow Neural Networks [8.22379888383833]
隠れたニューロンが$m$のReLU浅部ニューラルネットワークは、H"古い空間からの関数を均一に近似できることを示す。
そのようなレートは$O(m-fracrd)$に非常に近いが、$fracd+2d+4d+4$は、$d$が大きければ1ドルに近いという意味では$O(m-fracrd)$である。
論文 参考訳(メタデータ) (2023-07-24T00:16:50Z) - Neural Networks Efficiently Learn Low-Dimensional Representations with
SGD [22.703825902761405]
SGDで訓練されたReLU NNは、主方向を回復することで、$y=f(langleboldsymbolu,boldsymbolxrangle) + epsilon$という形の単一インデックスターゲットを学習できることを示す。
また、SGDによる近似低ランク構造を用いて、NNに対して圧縮保証を提供する。
論文 参考訳(メタデータ) (2022-09-29T15:29:10Z) - On the Multidimensional Random Subset Sum Problem [0.9007371440329465]
確率変数 $X_1, ..., X_n$ が与えられたランダム部分集合 Sum 問題では、任意の点 $z in [-1,1]$ を部分集合 $X_i_1(z), ..., X_i_s(z)$ の和として近似したい。
我々は、$d$次元において、$n = O(d3log frac 1varepsilon cdot
論文 参考訳(メタデータ) (2022-07-28T08:10:43Z) - Learning (Very) Simple Generative Models Is Hard [45.13248517769758]
我々は,$mathbbRdtobbRd'$の出力座標が$mathrmpoly(d)$ニューロンを持つ一層ReLUネットワークである場合でも,リアルタイムアルゴリズムが問題を解決可能であることを示す。
我々の証明の鍵となる要素は、コンパクトに支持されたピースワイズ線形関数$f$をニューラルネットワークで束ねたスロープで構築することであり、$mathcalN(0,1)$のプッシュフォワードは$mathcalのすべての低度モーメントと一致する。
論文 参考訳(メタデータ) (2022-05-31T17:59:09Z) - On the Optimal Memorization Power of ReLU Neural Networks [53.15475693468925]
フィードフォワードReLUニューラルネットワークは、軽度の分離可能性仮定を満たす任意のN$ポイントを記憶することができることを示す。
このような大きなビットの複雑性を持つことは、サブ線形数のパラメータを記憶するのに必要であり、十分であることを示す。
論文 参考訳(メタデータ) (2021-10-07T05:25:23Z) - Distributed Saddle-Point Problems Under Similarity [173.19083235638104]
与えられたサブ最適度$epsilon0$は、$Omegabigのマスター/ワーカーネットワークで達成されることを示す。
次に,ネットワークの下位の型(ログオーバまで)に適合するアルゴリズムを提案する。
頑健なロジスティック回帰問題に対して提案アルゴリズムの有効性を評価する。
論文 参考訳(メタデータ) (2021-07-22T14:25:16Z) - Learning Over-Parametrized Two-Layer ReLU Neural Networks beyond NTK [58.5766737343951]
2層ニューラルネットワークを学習する際の降下のダイナミクスについて考察する。
過度にパラメータ化された2層ニューラルネットワークは、タンジェントサンプルを用いて、ほとんどの地上で勾配損失を許容的に学習できることを示す。
論文 参考訳(メタデータ) (2020-07-09T07:09:28Z) - Network size and weights size for memorization with two-layers neural
networks [15.333300054767726]
本稿では,ニューロンの複雑な再結合をベースとしたReLUネットワークの新しいトレーニング手順を提案する。
Oleft(fracnd cdot fraclog(1/epsilon)epsilonright)$のニューロンと、体重のほぼ最適サイズの両方で近似記憶を示す。
論文 参考訳(メタデータ) (2020-06-04T13:44:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。