論文の概要: Is Stochastic Gradient Descent Near Optimal?

• arxiv url: http://arxiv.org/abs/2209.08627v1
• Date: Sun, 18 Sep 2022 18:26:43 GMT
• ステータス: 処理完了
• システム内更新日: 2022-09-20 19:05:21.821491
• Title: Is Stochastic Gradient Descent Near Optimal?
• Title（参考訳）: 確率勾配は最適に近いか?
• Authors: Yifan Zhu (1), Hong Jun Jeon (1), Benjamin Van Roy (1) ((1) Stanford University Department of Electrical Engineering)
• Abstract要約: 本研究では,多数のサンプルとクエリの総数を用いて,勾配勾配勾配の誤差が小さいことを示す。 このことは、SGDがJoen & Van Roy (arXiv:2203.00246) の情報理論的なサンプル複雑性境界を計算的に効率よく達成していることを示唆している。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The success of neural networks over the past decade has established them as effective models for many relevant data generating processes. Statistical theory on neural networks indicates graceful scaling of sample complexity. For example, Joen & Van Roy (arXiv:2203.00246) demonstrate that, when data is generated by a ReLU teacher network with $W$ parameters, an optimal learner needs only $\tilde{O}(W/\epsilon)$ samples to attain expected error $\epsilon$. However, existing computational theory suggests that, even for single-hidden-layer teacher networks, to attain small error for all such teacher networks, the computation required to achieve this sample complexity is intractable. In this work, we fit single-hidden-layer neural networks to data generated by single-hidden-layer ReLU teacher networks with parameters drawn from a natural distribution. We demonstrate that stochastic gradient descent (SGD) with automated width selection attains small expected error with a number of samples and total number of queries both nearly linear in the input dimension and width. This suggests that SGD nearly achieves the information-theoretic sample complexity bounds of Joen & Van Roy (arXiv:2203.00246) in a computationally efficient manner. An important difference between our positive empirical results and the negative theoretical results is that the latter address worst-case error of deterministic algorithms, while our analysis centers on expected error of a stochastic algorithm.
• Abstract（参考訳）: 過去10年間のニューラルネットワークの成功により、多くの関連するデータ生成プロセスの効果的なモデルとして確立された。 ニューラルネットワークの統計理論は、サンプル複雑性の優雅なスケーリングを示している。 例えば、Joen & Van Roy (arXiv:2203.00246) は、データが$W$パラメータを持つReLUの教師ネットワークによって生成される場合、最適な学習者は、期待されるエラー$\epsilon$を達成するために$\tilde{O}(W/\epsilon)$サンプルだけを必要とすることを示した。 しかし、既存の計算理論では、一階層の教師ネットワークであっても、そのような教師ネットワークに対して小さな誤差を犯すためには、この複雑さを実現するのに必要な計算は難解であることが示唆されている。 本研究では,自然分布から引き出されたパラメータを持つ単層ReLU教師ネットワークから生成されるデータに,単層ニューラルネットワークを適合させる。 自動幅選択による確率勾配降下(SGD)は,多数のサンプルと,入力次元と幅のほぼ線形なクエリの総数で,予測誤差が小さいことを実証した。 このことは、SGDがJoen & Van Roy (arXiv:2203.00246) の情報理論的なサンプル複雑性境界を計算的に効率よく達成していることを示唆している。 我々の正の実証結果と負の理論的結果との間に重要な違いは、後者が決定論的アルゴリズムの最悪の場合の誤りに対処し、一方、我々の分析は確率的アルゴリズムの予測誤差に焦点を合わせていることである。

関連論文リスト

• Sharper Guarantees for Learning Neural Network Classifiers with Gradient Methods [43.32546195968771]
  本研究では,スムーズなアクティベーションを有するニューラルネットワークに対する勾配法におけるデータ依存収束と一般化挙動について検討する。 我々の結果は、よく確立されたRadecher複雑性に基づく境界の欠点を改善した。 XOR分布の分類において、NTK体制の結果に対して大きなステップサイズが大幅に改善されることが示されている。
  論文  参考訳（メタデータ） (2024-10-13T21:49:29Z)
• 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)
• Sampling weights of deep neural networks [1.2370077627846041]
  完全に接続されたニューラルネットワークの重みとバイアスに対して,効率的なサンプリングアルゴリズムと組み合わせた確率分布を導入する。 教師付き学習環境では、内部ネットワークパラメータの反復最適化や勾配計算は不要である。 サンプルネットワークが普遍近似器であることを証明する。
  論文  参考訳（メタデータ） (2023-06-29T10:13:36Z)
• Joint Edge-Model Sparse Learning is Provably Efficient for Graph Neural Networks [89.28881869440433]
  本稿では,グラフニューラルネットワーク(GNN)における結合エッジモデルスパース学習の理論的特徴について述べる。 解析学的には、重要なノードをサンプリングし、最小のマグニチュードでプルーニングニューロンをサンプリングすることで、サンプルの複雑さを減らし、テスト精度を損なうことなく収束を改善することができる。
  論文  参考訳（メタデータ） (2023-02-06T16:54:20Z)
• Finite Sample Identification of Wide Shallow Neural Networks with Biases [12.622813055808411]
  入力-出力対の有限標本からネットワークのパラメータを同定することは、しばしばエンプテラー-学生モデル(enmphteacher-student model)と呼ばれる。 本稿では,このような幅の広い浅層ネットワークに対して,構成的手法と有限標本同定の理論的保証を提供することにより,そのギャップを埋める。
  論文  参考訳（メタデータ） (2022-11-08T22:10:32Z)
• Why Lottery Ticket Wins? A Theoretical Perspective of Sample Complexity on Pruned Neural Networks [79.74580058178594]
  目的関数の幾何学的構造を解析することにより、刈り取られたニューラルネットワークを訓練する性能を解析する。 本稿では,ニューラルネットワークモデルがプルーニングされるにつれて,一般化が保証された望ましいモデル近傍の凸領域が大きくなることを示す。
  論文  参考訳（メタデータ） (2021-10-12T01:11:07Z)
• The Separation Capacity of Random Neural Networks [78.25060223808936]
  標準ガウス重みと一様分布バイアスを持つ十分に大きな2層ReLUネットワークは、この問題を高い確率で解くことができることを示す。 我々は、相互複雑性という新しい概念の観点から、データの関連構造を定量化する。
  論文  参考訳（メタデータ） (2021-07-31T10:25:26Z)
• Towards an Understanding of Benign Overfitting in Neural Networks [104.2956323934544]
  現代の機械学習モデルは、しばしば膨大な数のパラメータを使用し、通常、トレーニング損失がゼロになるように最適化されている。 ニューラルネットワークの2層構成において、これらの良質な過適合現象がどのように起こるかを検討する。 本稿では,2層型ReLUネットワーク補間器を極小最適学習率で実現可能であることを示す。
  論文  参考訳（メタデータ） (2021-06-06T19:08:53Z)
• Self-Regularity of Non-Negative Output Weights for Overparameterized Two-Layer Neural Networks [16.64116123743938]
  我々は、Sigmoid, rectified linear unit (ReLU) を用いた2層ニューラルネットワークの探索問題を考える。 そして、その境界を利用して、Emphfat-shattering dimensionを通じてそのようなネットワークの保証を確立する。 特に、我々の境界はサンプルの複雑さも良い(低次数$$d$のポリノミアル)。
  論文  参考訳（メタデータ） (2021-03-02T17:36:03Z)
• Random Vector Functional Link Networks for Function Approximation on Manifolds [8.535815777849786]
  ランダムな入力-隠蔽層重みとバイアスを持つ単一層ニューラルネットが実際に成功していることを示す。 さらに、このランダム化されたニューラルネットワークアーキテクチャをユークリッド空間の滑らかでコンパクトな部分多様体上の近似関数に適用する。
  論文  参考訳（メタデータ） (2020-07-30T23:50:44Z)
• OSLNet: Deep Small-Sample Classification with an Orthogonal Softmax Layer [77.90012156266324]
  本稿では,ニューラルネットワークのサブスペースを見つけることを目的としている。 そこで本研究では,Orthogonal Softmax Layer (OSL) を提案する。 実験結果から,提案OSLは4つの小サンプルベンチマークデータセットとの比較に用いた手法よりも優れた性能を示した。
  論文  参考訳（メタデータ） (2020-04-20T02:41:01Z)

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

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