論文の概要: SGD: The Role of Implicit Regularization, Batch-size and Multiple-epochs

• arxiv url: http://arxiv.org/abs/2107.05074v1
• Date: Sun, 11 Jul 2021 15:50:01 GMT
• ステータス: 処理完了
• システム内更新日: 2021-07-14 02:56:18.019038
• Title: SGD: The Role of Implicit Regularization, Batch-size and Multiple-epochs
• Title（参考訳）: SGD: 急激な正規化, バッチサイズ, マルチエポックの役割
• Authors: Satyen Kale, Ayush Sekhari, Karthik Sridharan
• Abstract要約: 本稿では,現実に一般的に用いられているグラディエント・ディファイス(SGD)のマルチエポックな変種について述べる。 最悪の場合、これはシングルパスSGDと同程度であることを示す。 SCOの特定の問題に対して、データセットに複数のパスを取ることは、シングルパスSGDを著しく上回る。
• 参考スコア（独自算出の注目度）: 30.41773138781369
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: Multi-epoch, small-batch, Stochastic Gradient Descent (SGD) has been the method of choice for learning with large over-parameterized models. A popular theory for explaining why SGD works well in practice is that the algorithm has an implicit regularization that biases its output towards a good solution. Perhaps the theoretically most well understood learning setting for SGD is that of Stochastic Convex Optimization (SCO), where it is well known that SGD learns at a rate of $O(1/\sqrt{n})$, where $n$ is the number of samples. In this paper, we consider the problem of SCO and explore the role of implicit regularization, batch size and multiple epochs for SGD. Our main contributions are threefold: (a) We show that for any regularizer, there is an SCO problem for which Regularized Empirical Risk Minimzation fails to learn. This automatically rules out any implicit regularization based explanation for the success of SGD. (b) We provide a separation between SGD and learning via Gradient Descent on empirical loss (GD) in terms of sample complexity. We show that there is an SCO problem such that GD with any step size and number of iterations can only learn at a suboptimal rate: at least $\widetilde{\Omega}(1/n^{5/12})$. (c) We present a multi-epoch variant of SGD commonly used in practice. We prove that this algorithm is at least as good as single pass SGD in the worst case. However, for certain SCO problems, taking multiple passes over the dataset can significantly outperform single pass SGD. We extend our results to the general learning setting by showing a problem which is learnable for any data distribution, and for this problem, SGD is strictly better than RERM for any regularization function. We conclude by discussing the implications of our results for deep learning, and show a separation between SGD and ERM for two layer diagonal neural networks.
• Abstract（参考訳）: SGD(Stochastic Gradient Descent)は,大規模過パラメータモデルを用いて学習する方法である。 SGDが実際にうまく機能する理由を説明する一般的な理論は、アルゴリズムが良い解に向けて出力をバイアスする暗黙の正規化を持っていることである。 おそらく理論上最もよく知られたsgdの学習設定は確率凸最適化(sco)であり、sgdはサンプル数である$o(1/\sqrt{n})$で学習することがよく知られている。 本稿ではSCOの問題点を考察し,SGDにおける暗黙の正規化,バッチサイズ,複数エポックの役割について考察する。 主な貢献は3つある: (a) 正規化者にとって、正規化実証リスク最小化が学習に失敗するSCO問題が存在することを示す。 これにより、暗黙の正規化に基づくSGDの成功の説明が自動的に除外される。 b)サンプル複雑性の観点から,経験的損失の勾配降下(gd)によるsgdと学習の分離を提供する。 任意のステップサイズと反復数を持つ GD が最適以下でしか学べないような SCO 問題が存在することを示す:少なくとも $\widetilde{\Omega}(1/n^{5/12})$。 (c) 一般的に用いられるSGDのマルチエポック版について述べる。 最悪の場合、このアルゴリズムはsingle pass sgdと同じくらい優れていることが証明される。 しかし、SCOの特定の問題に対して、データセットに複数回のパスを取ることはシングルパスSGDを著しく上回る。 我々は,任意のデータ分布に対して学習可能な問題を示すことによって,一般的な学習環境にまで拡張し,この問題に対して,SGDは正規化関数のRERMよりも厳密に優れていることを示す。 この結果が深層学習に与える影響について考察し,2層対角型ニューラルネットワークにおけるsgdとermの分離を示す。

関連論文リスト

• On the Trajectories of SGD Without Replacement [0.0]
  本稿では,グラディエントDescence(SGD)の暗黙的正則化効果について検討する。 我々は、大規模なニューラルネットワークを最適化するために一般的に使用される変種である、置換のないSGDの場合を考える。
  論文  参考訳（メタデータ） (2023-12-26T18:06:48Z)
• Implicit Regularization or Implicit Conditioning? Exact Risk Trajectories of SGD in High Dimensions [26.782342518986503]
  勾配降下(SGD)は現代の機械学習の柱であり、様々な問題に対するゴート最適化アルゴリズムとして機能している。 HSGD形式をストリーミングSGDに適合させる方法を示し、ストリーミングSGDと比較してマルチパスSGDの過大なリスクを正確に予測できることを示す。
  論文  参考訳（メタデータ） (2022-06-15T02:32:26Z)
• Risk Bounds of Multi-Pass SGD for Least Squares in the Interpolation Regime [127.21287240963859]
  勾配降下(SGD)は最適化と一般化の両方において優れた性能を持つため、大きな成功を収めている。 本稿では,マルチパスSGDの一般化を強く特徴付けることを目的とする。 我々は,SGDが同じレベルの過剰リスクを達成するためには,GD以上を必要とするが,勾配評価の回数を削減できることを示した。
  論文  参考訳（メタデータ） (2022-03-07T06:34:53Z)
• Benign Underfitting of Stochastic Gradient Descent [72.38051710389732]
  本研究では,適切な学習データを得ることで,一般化性能を実現する「従来型」学習ルールとして,勾配降下度(SGD)がどの程度理解されるかを検討する。 類似現象が起こらない近縁な交換SGDを解析し、その集団リスクが実際に最適な速度で収束することを証明する。
  論文  参考訳（メタデータ） (2022-02-27T13:25:01Z)
• The Benefits of Implicit Regularization from SGD in Least Squares Problems [116.85246178212616]
  勾配降下(SGD)はアルゴリズム正則化効果が強い。 我々は、(正規化されていない)平均SGDで得られる暗黙の正則化とリッジ回帰の明示的な正則化の比較を行う。
  論文  参考訳（メタデータ） (2021-08-10T09:56:47Z)
• Label Noise SGD Provably Prefers Flat Global Minimizers [48.883469271546076]
  過度パラメータ化モデルでは、勾配降下(SGD)のノイズは最適化軌道を暗黙的に規則化し、どの局所最小SGDが収束するかを決定する。 ラベルノイズを持つSGDが正規化損失$L(theta) +lambda R(theta)$の定常点に収束することを示す。 解析の結果,線形スケーリング法則を超越した大規模学習率の正規化効果が明らかとなった。
  論文  参考訳（メタデータ） (2021-06-11T17:59:07Z)
• SGD Generalizes Better Than GD (And Regularization Doesn't Help) [39.588906680621825]
  我々は、勾配勾配(SGD)の一般化性能と全バッチ勾配(GD)の分離結果を与える。 同じステップ数で、GD はオーバーフィットし、$Omega(1)$ generalization error で解を出力することを示した。 本稿では,GDによる経験的リスクの最小化が,基本的には上記の結果を変えるものではないことを論じ,安定性,暗黙バイアス,一般化における学習アルゴリズムの役割を再考する。
  論文  参考訳（メタデータ） (2021-02-01T19:18:40Z)
• Direction Matters: On the Implicit Bias of Stochastic Gradient Descent with Moderate Learning Rate [105.62979485062756]
  本稿では,中等度学習におけるSGDの特定の正規化効果を特徴付けることを試みる。 SGDはデータ行列の大きな固有値方向に沿って収束し、GDは小さな固有値方向に沿って収束することを示す。
  論文  参考訳（メタデータ） (2020-11-04T21:07:52Z)
• Least Squares Regression with Markovian Data: Fundamental Limits and Algorithms [69.45237691598774]
  マルコフ連鎖からデータポイントが依存しサンプリングされる最小二乗線形回帰問題について検討する。 この問題を$tau_mathsfmix$という観点から、鋭い情報理論のミニマックス下限を確立する。 本稿では,経験的リプレイに基づくアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-16T04:26:50Z)

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

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