論文の概要: Benign Underfitting of Stochastic Gradient Descent

• arxiv url: http://arxiv.org/abs/2202.13361v1
• Date: Sun, 27 Feb 2022 13:25:01 GMT
• ステータス: 処理完了
• システム内更新日: 2022-03-01 15:47:49.975332
• Title: Benign Underfitting of Stochastic Gradient Descent
• Title（参考訳）: 確率的勾配降下の良性不適合
• Authors: Tomer Koren, Roi Livni, Yishay Mansour, Uri Sherman
• Abstract要約: 本研究では,SGD(グラデーション降下法)が,学習データに適合して一般化性能を得る「従来型」学習規則として理解される可能性について検討する。 我々は、類似現象が起こらないことを示し、その集団リスクが実際に最適な速度で収束することを証明した、密接な関係のあるエンフィスリプレースメントSGDを分析した。
• 参考スコア（独自算出の注目度）: 72.38051710389732
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study to what extent may stochastic gradient descent (SGD) be understood as a "conventional" learning rule that achieves generalization performance by obtaining a good fit to training data. We consider the fundamental stochastic convex optimization framework, where (one pass, \emph{without}-replacement) SGD is classically known to minimize the population risk at rate $O(1/\sqrt n)$, and prove that, surprisingly, there exist problem instances where the SGD solution exhibits both empirical risk and generalization gap of $\Omega(1)$. Consequently, it turns out that SGD is not algorithmically stable in \emph{any} sense, and its generalization ability cannot be explained by uniform convergence or any other currently known generalization bound technique for that matter (other than that of its classical analysis). We then continue to analyze the closely related \emph{with}-replacement SGD, for which we show that an analogous phenomenon does not occur and prove that its population risk does in fact converge at the optimal rate. Finally, we interpret our main results in the context of without-replacement SGD for finite-sum convex optimization problems, and derive upper and lower bounds for the multi-epoch regime that significantly improve upon previously known results.
• Abstract（参考訳）: 本研究では,確率勾配降下(SGD)を「従来型」学習規則として理解し,学習データに適合して一般化性能が得られるかを検討した。 基本的な確率的凸最適化の枠組みを考えると、SGDは古典的には、O(1/\sqrt n)$で人口リスクを最小化することが知られており、驚くべきことに、SGDが$\Omega(1)$の経験的リスクと一般化ギャップの両方を示す問題が存在することを証明している。 その結果、SGDはアルゴリズム的に安定ではないことが判明し、その一般化能力は、一様収束法や、その物質について(古典解析以外の)現在知られている一般化バウンド技術によって説明できないことが判明した。 次に,類似現象が発生しないことを示し,その個体群リスクが実際に最適速度で収束することを示す,近縁の \emph{with}-replacement sgd の解析を継続する。 最後に, 有限サム凸最適化問題に対する非置換 SGD の文脈において, 本研究の主な成果を解釈し, 既知結果よりも大幅に向上するマルチエポック方式の上下境界を導出する。

関連論文リスト

• Improving Implicit Regularization of SGD with Preconditioning for Least Square Problems [19.995877680083105]
  最小二乗問題に対する事前条件付き勾配降下(SGD)の一般化性能について検討した。 提案したプレコンディショニング行列は有限標本からのロバストな推定が可能なほど単純であることを示す。
  論文  参考訳（メタデータ） (2024-03-13T14:42:06Z)
• Empirical Risk Minimization with Shuffled SGD: A Primal-Dual Perspective and Improved Bounds [12.699376765058137]
  勾配降下法(SGD)は、おそらく現代の機械学習において最も一般的な最適化法である。 SGDを交換せずにサンプリングするSGDが分析されたのはごく最近のことだ。 データマトリックスに依存し、既存の境界によって予測されるものよりも決して悪くない、きめ細かい複雑性境界を証明します。
  論文  参考訳（メタデータ） (2023-06-21T18:14:44Z)
• From Gradient Flow on Population Loss to Learning with Stochastic Gradient Descent [50.4531316289086]
  SGD(Gradient Descent)は、大規模非ルートモデルの学習方法である。 集団損失のGFが収束すると仮定して、総合的な条件 SGD が収束する。 我々は、凸損失のような古典的な設定だけでなく、Retrieval Matrix sq-rootのようなより複雑な問題に対してもGD/SGDを統一的に解析する。
  論文  参考訳（メタデータ） (2022-10-13T03:55:04Z)
• 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)
• The Benefits of Implicit Regularization from SGD in Least Squares Problems [116.85246178212616]
  勾配降下(SGD)はアルゴリズム正則化効果が強い。 我々は、(正規化されていない)平均SGDで得られる暗黙の正則化とリッジ回帰の明示的な正則化の比較を行う。
  論文  参考訳（メタデータ） (2021-08-10T09:56:47Z)
• A general sample complexity analysis of vanilla policy gradient [101.16957584135767]
  政策勾配(PG)は、最も一般的な強化学習(RL)問題の1つである。 PG軌道の「バニラ」理論的理解は、RL問題を解く最も一般的な方法の1つである。
  論文  参考訳（メタデータ） (2021-07-23T19:38:17Z)
• Benign Overfitting of Constant-Stepsize SGD for Linear Regression [122.70478935214128]
  帰納バイアスは 経験的に過剰フィットを防げる中心的存在です この研究は、この問題を最も基本的な設定として考慮している: 線形回帰に対する定数ステップサイズ SGD。 我々は、(正規化されていない)SGDで得られるアルゴリズム正則化と、通常の最小二乗よりも多くの顕著な違いを反映する。
  論文  参考訳（メタデータ） (2021-03-23T17:15:53Z)
• 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)

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

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