論文の概要: Optimal Lottery Tickets via SubsetSum: Logarithmic Over-Parameterization is Sufficient

• arxiv url: http://arxiv.org/abs/2006.07990v2
• Date: Thu, 11 Mar 2021 18:40:46 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-21 12:37:14.591358
• Title: Optimal Lottery Tickets via SubsetSum: Logarithmic Over-Parameterization is Sufficient
• Title（参考訳）: subsetsum経由の最適抽選チケット:対数過剰パラメータ化で十分
• Authors: Ankit Pensia, Shashank Rajput, Alliot Nagle, Harit Vishwakarma and Dimitris Papailiopoulos
• Abstract要約: 幅$d$と深さ$l$の任意のターゲットネットワークは、幅$O(log(dl))$の2倍、幅$O(log(dl))$のランダムネットワークを切断することで近似できることを示す。 解析は、プルーニングランダムなReLUネットワークをtextscSubset問題のランダムなインスタンスに接続することに依存する。
• 参考スコア（独自算出の注目度）: 9.309655246559094
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The strong {\it lottery ticket hypothesis} (LTH) postulates that one can approximate any target neural network by only pruning the weights of a sufficiently over-parameterized random network. A recent work by Malach et al. \cite{MalachEtAl20} establishes the first theoretical analysis for the strong LTH: one can provably approximate a neural network of width $d$ and depth $l$, by pruning a random one that is a factor $O(d^4l^2)$ wider and twice as deep. This polynomial over-parameterization requirement is at odds with recent experimental research that achieves good approximation with networks that are a small factor wider than the target. In this work, we close the gap and offer an exponential improvement to the over-parameterization requirement for the existence of lottery tickets. We show that any target network of width $d$ and depth $l$ can be approximated by pruning a random network that is a factor $O(\log(dl))$ wider and twice as deep. Our analysis heavily relies on connecting pruning random ReLU networks to random instances of the \textsc{SubsetSum} problem. We then show that this logarithmic over-parameterization is essentially optimal for constant depth networks. Finally, we verify several of our theoretical insights with experiments.
• Abstract（参考訳）: strong {\it lottery ticket hypothesis} (lth) は、十分な過パラメータのランダムネットワークの重みを刈り取るだけで、任意のターゲットニューラルネットワークを近似できると仮定している。 Malachらによる最近の作品。 \cite{MalachEtAl20} は強い LTH に対する最初の理論的解析を確立している: 幅$d$ と深さ $l$ のニューラルネットワークを、幅$O(d^4l^2)$ の確率で2倍の深さの確率的に近似することができる。 この多項式の過剰パラメータ要件は、ターゲットよりも小さな因子を持つネットワークとの良好な近似を実現する最近の実験的研究と相反する。 本研究では,このギャップを解消し,抽選券の存在に対する過剰パラメータ要件を指数関数的に改善する。 幅$d$ と深さ$l$ の任意のターゲットネットワークは、値$o(\log(dl))$のランダムネットワークを、幅が2倍、深さが2倍の幅で刈り取ることで近似できることを示す。 我々の分析は、プルーニングランダムなReLUネットワークと \textsc{SubsetSum} 問題のランダムなインスタンスとの接続に大きく依存している。 次に、この対数的過パラメータ化は、定数深度ネットワークに本質的に最適であることを示す。 最後に,実験による理論的知見のいくつかを検証する。

関連論文リスト

• On the Sparsity of the Strong Lottery Ticket Hypothesis [8.47014750905382]
  最近の研究で、任意のニューラルネットワークを正確に近似できるランダムニューラルネットワークの$N$ containsworksが示されている。 古典的セッティングにおけるStrong Lottery Ticket仮説の最初の証明を提供する。
  論文  参考訳（メタデータ） (2024-10-18T06:57:37Z)
• 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)
• 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)
• Bounding the Width of Neural Networks via Coupled Initialization -- A Worst Case Analysis [121.9821494461427]
  2層ReLUネットワークに必要なニューロン数を著しく削減する方法を示す。 また、事前の作業を改善するための新しい下位境界を証明し、ある仮定の下では、最善を尽くすことができることを証明します。
  論文  参考訳（メタデータ） (2022-06-26T06:51:31Z)
• Most Activation Functions Can Win the Lottery Without Excessive Depth [6.68999512375737]
  宝くじの仮説は、プルーニングによってディープニューラルネットワークをトレーニングする可能性を強調している。 ReLUアクティベーション関数を持つネットワークの場合、深さ$L$のターゲットネットワークは、ターゲットの深さが2L$で対数係数がより広いランダムニューラルネットワークのサブネットワークによって近似できることが証明されている。
  論文  参考訳（メタデータ） (2022-05-04T20:51:30Z)
• A Law of Robustness beyond Isoperimetry [84.33752026418045]
  我々は、任意の分布上でニューラルネットワークパラメータを補間する頑健性の低い$Omega(sqrtn/p)$を証明した。 次に、$n=mathrmpoly(d)$のとき、スムーズなデータに対する過度なパラメータ化の利点を示す。 我々は、$n=exp(omega(d))$ のとき、$O(1)$-Lipschitz の頑健な補間関数の存在を否定する。
  論文  参考訳（メタデータ） (2022-02-23T16:10:23Z)
• Minimax Optimal Quantization of Linear Models: Information-Theoretic Limits and Efficient Algorithms [59.724977092582535]
  測定から学習した線形モデルの定量化の問題を考える。 この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。 本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
  論文  参考訳（メタデータ） (2022-02-23T02:39:04Z)
• Towards an Understanding of Benign Overfitting in Neural Networks [104.2956323934544]
  現代の機械学習モデルは、しばしば膨大な数のパラメータを使用し、通常、トレーニング損失がゼロになるように最適化されている。 ニューラルネットワークの2層構成において、これらの良質な過適合現象がどのように起こるかを検討する。 本稿では,2層型ReLUネットワーク補間器を極小最適学習率で実現可能であることを示す。
  論文  参考訳（メタデータ） (2021-06-06T19:08:53Z)
• An $L^2$ Analysis of Reinforcement Learning in High Dimensions with Kernel and Neural Network Approximation [9.088303226909277]
  本稿では,カーネル法や2層ニューラルネットワークモデルを用いて関数近似を行う状況について考察する。 私たちは$tildeO(H3|mathcal A|frac14n-frac14)$を$Hn$サンプルで最適なポリシーにバインドします。 この結果はまだ有限次元の作用空間を必要とするが、誤差境界は状態空間の次元とは独立である。
  論文  参考訳（メタデータ） (2021-04-15T21:59:03Z)
• A Universal Approximation Theorem of Deep Neural Networks for Expressing Probability Distributions [12.100913944042972]
  ReLU 活性化を伴う深層ニューラルネットワーク $g:mathbbRdrightarrow mathbbR$ が存在することを示す。 ニューラルネットワークのサイズは、1ドルのワッサーシュタイン距離が相違点として使用される場合、$d$で指数関数的に成長することができる。
  論文  参考訳（メタデータ） (2020-04-19T14:45:47Z)

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

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