論文の概要: SGD in the Large: Average-case Analysis, Asymptotics, and Stepsize Criticality

• arxiv url: http://arxiv.org/abs/2102.04396v1
• Date: Mon, 8 Feb 2021 18:00:13 GMT
• ステータス: 処理完了
• システム内更新日: 2021-02-09 15:49:32.837768
• Title: SGD in the Large: Average-case Analysis, Asymptotics, and Stepsize Criticality
• Title（参考訳）: SGD in the Large: Average-case Analysis, Asymptotics, and Stepsize criticality
• Authors: Courtney Paquette, Kiwon Lee, Fabian Pedregosa and Elliot Paquette
• Abstract要約: 本稿では,サンプル数と寸法がともに大きい場合の勾配降下(SGD)のダイナミクスを解析するための新しい枠組みを提案する。 この新たな枠組みを用いて, ランダムデータを用いた最小二乗問題におけるSGDの力学が, 標本および次元限界において決定論的になることを示す。
• 参考スコア（独自算出の注目度）: 15.640534097470923
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose a new framework, inspired by random matrix theory, for analyzing the dynamics of stochastic gradient descent (SGD) when both number of samples and dimensions are large. This framework applies to any fixed stepsize and the finite sum setting. Using this new framework, we show that the dynamics of SGD on a least squares problem with random data become deterministic in the large sample and dimensional limit. Furthermore, the limiting dynamics are governed by a Volterra integral equation. This model predicts that SGD undergoes a phase transition at an explicitly given critical stepsize that ultimately affects its convergence rate, which we also verify experimentally. Finally, when input data is isotropic, we provide explicit expressions for the dynamics and average-case convergence rates (i.e., the complexity of an algorithm averaged over all possible inputs). These rates show significant improvement over the worst-case complexities.
• Abstract（参考訳）: 本稿では,ランダム行列理論に着想を得た新しいフレームワークを提案し,サンプル数と寸法がともに大きい場合の確率勾配勾配(SGD)のダイナミクスを解析する。 このフレームワークは任意の固定ステップと有限和設定に適用できる。 この新しいフレームワークを用いて、ランダムなデータを持つ最小二乗問題におけるSGDのダイナミクスが、大きなサンプルと次元の限界において決定論的になることを示す。 さらに、制限ダイナミクスはヴォルテラ積分方程式によって支配される。 このモデルでは, sgd が相転移を受けると予測し, その収束速度に最終的に影響し, 実験的に検証する。 最後に、入力データが等方性であるとき、我々は、ダイナミクスと平均ケース収束率(すなわち、可能なすべての入力で平均されるアルゴリズムの複雑さ)の明示的な表現を提供する。 これらの率は最悪のケースの複雑さよりも有意な改善を示しています。

関連論文リスト

• Hitting the High-Dimensional Notes: An ODE for SGD learning dynamics on GLMs and multi-index models [10.781866671930857]
  高次元限界におけるストリーミング勾配降下(SGD)のダイナミクスを解析する。 我々は、通常の微分方程式の体系の形で、SGDの決定論的等価性を実証する。 決定論的等価性に加えて、単純化された拡散係数を持つSDEを導入する。
  論文  参考訳（メタデータ） (2023-08-17T13:33:02Z)
• High-dimensional limit theorems for SGD: Effective dynamics and critical scaling [6.950316788263433]
  我々は、勾配降下(SGD)の要約統計の軌跡に対する極限定理を証明する。 下記の有効弾道力学が人口減少の勾配流と一致するステップサイズにおける重要なスケーリング体制を示す。 この実効力学の固定点について、対応する拡散極限は極めて複雑であり、さらに退化することもある。
  論文  参考訳（メタデータ） (2022-06-08T17:42:18Z)
• Homogenization of SGD in high-dimensions: Exact dynamics and generalization properties [26.782342518986503]
  我々は、勾配降下ベクトル(SGD)のダイナミクスを解析するための等質化SGDと呼ばれる微分方程式を開発する。 均質化されたSGDは、任意の二次統計量(例えば、二次的損失を伴う人口リスク)に対して、SGDの高次元同値であることを示す。
  論文  参考訳（メタデータ） (2022-05-14T14:10:08Z)
• On the Double Descent of Random Features Models Trained with SGD [78.0918823643911]
  勾配降下(SGD)により最適化された高次元におけるランダム特徴(RF)回帰特性について検討する。 本研究では, RF回帰の高精度な非漸近誤差境界を, 定常および適応的なステップサイズSGD設定の下で導出する。 理論的にも経験的にも二重降下現象を観察する。
  論文  参考訳（メタデータ） (2021-10-13T17:47:39Z)
• Last Iterate Risk Bounds of SGD with Decaying Stepsize for Overparameterized Linear Regression [122.70478935214128]
  勾配降下(SGD)は、多くのディープラーニングアプリケーションでよく一般化されている。 本稿では, 崩壊段階のSGDの最終反復リスク境界に関する問題依存解析を行う。
  論文  参考訳（メタデータ） (2021-10-12T17:49:54Z)
• Heavy-tailed Streaming Statistical Estimation [58.70341336199497]
  ストリーミング$p$のサンプルから重み付き統計推定の課題を考察する。 そこで我々は,傾きの雑音に対して,よりニュアンスな条件下での傾きの傾きの低下を設計し,より詳細な解析を行う。
  論文  参考訳（メタデータ） (2021-08-25T21:30:27Z)
• The Benefits of Implicit Regularization from SGD in Least Squares Problems [116.85246178212616]
  勾配降下(SGD)はアルゴリズム正則化効果が強い。 我々は、(正規化されていない)平均SGDで得られる暗黙の正則化とリッジ回帰の明示的な正則化の比較を行う。
  論文  参考訳（メタデータ） (2021-08-10T09:56:47Z)
• Dynamics of Stochastic Momentum Methods on Large-scale, Quadratic Models [0.2741266294612776]
  我々は高次元ランダム最小二乗問題に対して運動量を持つ勾配アルゴリズムのクラスを解析する。 固定運動量パラメータを持つ(小バッチ)運動量では,ステップサイズを正確に調整した場合,SGDよりも実際の性能向上は得られないことを示す。 非強凸条件では、運動量を用いてSGDよりも大きな改善が得られる。
  論文  参考訳（メタデータ） (2021-06-07T15:08:24Z)
• Benign Overfitting of Constant-Stepsize SGD for Linear Regression [122.70478935214128]
  帰納バイアスは 経験的に過剰フィットを防げる中心的存在です この研究は、この問題を最も基本的な設定として考慮している: 線形回帰に対する定数ステップサイズ SGD。 我々は、(正規化されていない)SGDで得られるアルゴリズム正則化と、通常の最小二乗よりも多くの顕著な違いを反映する。
  論文  参考訳（メタデータ） (2021-03-23T17:15:53Z)
• Balancing Rates and Variance via Adaptive Batch-Size for Stochastic Optimization Problems [120.21685755278509]
  本研究は,ステップサイズの減衰が正確な収束に必要であるという事実と,一定のステップサイズがエラーまでの時間でより速く学習するという事実のバランスをとることを目的とする。 ステップサイズのミニバッチを最初から修正するのではなく,パラメータを適応的に進化させることを提案する。
  論文  参考訳（メタデータ） (2020-07-02T16:02:02Z)
• The Heavy-Tail Phenomenon in SGD [7.366405857677226]
  最小損失のHessianの構造に依存すると、SGDの反復はエンフェビーテールの定常分布に収束する。 深層学習におけるSGDの行動に関する知見に分析結果を変換する。
  論文  参考訳（メタデータ） (2020-06-08T16:43:56Z)

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

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