論文の概要: Homogenization of SGD in high-dimensions: Exact dynamics and generalization properties

• arxiv url: http://arxiv.org/abs/2205.07069v1
• Date: Sat, 14 May 2022 14:10:08 GMT
• ステータス: 処理完了
• システム内更新日: 2022-05-17 18:03:29.638965
• Title: Homogenization of SGD in high-dimensions: Exact dynamics and generalization properties
• Title（参考訳）: 高次元におけるSGDの均質化:特殊力学と一般化特性
• Authors: Courtney Paquette, Elliot Paquette, Ben Adlam, Jeffrey Pennington
• Abstract要約: 我々は、勾配降下ベクトル(SGD)のダイナミクスを解析するための等質化SGDと呼ばれる微分方程式を開発する。 均質化されたSGDは、任意の二次統計量(例えば、二次的損失を伴う人口リスク)に対して、SGDの高次元同値であることを示す。
• 参考スコア（独自算出の注目度）: 26.782342518986503
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We develop a stochastic differential equation, called homogenized SGD, for analyzing the dynamics of stochastic gradient descent (SGD) on a high-dimensional random least squares problem with $\ell^2$-regularization. We show that homogenized SGD is the high-dimensional equivalence of SGD -- for any quadratic statistic (e.g., population risk with quadratic loss), the statistic under the iterates of SGD converges to the statistic under homogenized SGD when the number of samples $n$ and number of features $d$ are polynomially related ($d^c < n < d^{1/c}$ for some $c > 0$). By analyzing homogenized SGD, we provide exact non-asymptotic high-dimensional expressions for the generalization performance of SGD in terms of a solution of a Volterra integral equation. Further we provide the exact value of the limiting excess risk in the case of quadratic losses when trained by SGD. The analysis is formulated for data matrices and target vectors that satisfy a family of resolvent conditions, which can roughly be viewed as a weak (non-quantitative) form of delocalization of sample-side singular vectors of the data. Several motivating applications are provided including sample covariance matrices with independent samples and random features with non-generative model targets.
• Abstract（参考訳）: 我々は,$\ell^2$-regularizationを持つ高次元ランダム最小二乗問題に対する確率勾配降下(sgd)のダイナミクスを分析するために,ホモゲン化sgdと呼ばれる確率微分方程式を開発した。 均質化された SGD は SGD の高次元同値であり、任意の二次統計量(例えば、二次的損失を伴う人口リスク)に対して、SGD の反復による統計量は、サンプル数 $n$ と特徴数 $d$ が多項式関係($d^c < n < d^{1/c}$ for some $c > 0$)であるときに同質化された SGD の統計量に収束する。 均質化されたSGDを解析することにより、ボルテラ積分方程式の解を用いて、SGDの一般化性能に対して正確な非漸近的な高次元表現を提供する。 さらに、sgdにより訓練された場合の二次損失の場合の限界余剰リスクの正確な値を提供する。 この分析は、データのサンプル側特異ベクトルの非局在化の弱い(非定量的)形式として概ね見なせる、分解条件の族を満たすデータ行列とターゲットベクトルに対して定式化される。 いくつかのモチベーションアプリケーションは、独立したサンプルを持つサンプル共分散行列と、生成しないモデルターゲットを持つランダムな特徴を含む。

関連論文リスト

• Stochastic Differential Equations models for Least-Squares Stochastic Gradient Descent [6.3151583550712065]
  グラディエントDescent(SGD)の連続時間モデルのダイナミクスについて検討する。 我々は,SGDをモデル化する退化微分方程式(squareSDEs)を,トレーニング損失(有限サンプル)と集団1(オンライン設定)のいずれにおいても解析する。
  論文  参考訳（メタデータ） (2024-07-02T14:52:21Z)
• Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
  単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。 我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
  論文  参考訳（メタデータ） (2024-03-08T18:50:19Z)
• Demystifying the Myths and Legends of Nonconvex Convergence of SGD [17.445810977264067]
  勾配勾配勾配(SGD)とその変種は、大規模最適化問題の解法の主要な仕事場である。 分析として,勾配の非収束に関連する神話や伝説について考察した。
  論文  参考訳（メタデータ） (2023-10-19T17:58:59Z)
• 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)
• 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)
• Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector Problems [98.34292831923335]
  オンライン相関解析の問題から,emphStochastic Scaled-Gradient Descent (SSD)アルゴリズムを提案する。 我々はこれらのアイデアをオンライン相関解析に適用し、局所収束率を正規性に比例した最適な1時間スケールのアルゴリズムを初めて導いた。
  論文  参考訳（メタデータ） (2021-12-29T18:46:52Z)
• On the Double Descent of Random Features Models Trained with SGD [78.0918823643911]
  勾配降下(SGD)により最適化された高次元におけるランダム特徴(RF)回帰特性について検討する。 本研究では, RF回帰の高精度な非漸近誤差境界を, 定常および適応的なステップサイズSGD設定の下で導出する。 理論的にも経験的にも二重降下現象を観察する。
  論文  参考訳（メタデータ） (2021-10-13T17:47:39Z)
• The Benefits of Implicit Regularization from SGD in Least Squares Problems [116.85246178212616]
  勾配降下(SGD)はアルゴリズム正則化効果が強い。 我々は、(正規化されていない)平均SGDで得られる暗黙の正則化とリッジ回帰の明示的な正則化の比較を行う。
  論文  参考訳（メタデータ） (2021-08-10T09:56:47Z)
• Benign Overfitting of Constant-Stepsize SGD for Linear Regression [122.70478935214128]
  帰納バイアスは 経験的に過剰フィットを防げる中心的存在です この研究は、この問題を最も基本的な設定として考慮している: 線形回帰に対する定数ステップサイズ SGD。 我々は、(正規化されていない)SGDで得られるアルゴリズム正則化と、通常の最小二乗よりも多くの顕著な違いを反映する。
  論文  参考訳（メタデータ） (2021-03-23T17:15:53Z)
• SGD in the Large: Average-case Analysis, Asymptotics, and Stepsize Criticality [15.640534097470923]
  本稿では,サンプル数と寸法がともに大きい場合の勾配降下(SGD)のダイナミクスを解析するための新しい枠組みを提案する。 この新たな枠組みを用いて, ランダムデータを用いた最小二乗問題におけるSGDの力学が, 標本および次元限界において決定論的になることを示す。
  論文  参考訳（メタデータ） (2021-02-08T18:00:13Z)

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

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