論文の概要: Rapid Overfitting of Multi-Pass Stochastic Gradient Descent in Stochastic Convex Optimization

• arxiv url: http://arxiv.org/abs/2505.08306v1
• Date: Tue, 13 May 2025 07:32:48 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-14 20:57:54.475051
• Title: Rapid Overfitting of Multi-Pass Stochastic Gradient Descent in Stochastic Convex Optimization
• Title（参考訳）: 確率凸最適化におけるマルチパス確率勾配の高速オーバーフィッティング
• Authors: Shira Vansover-Hager, Tomer Koren, Roi Livni,
• Abstract要約: 基本凸最適化(SCO)モデルにおけるマルチパス勾配勾配勾配(SGD)のアウトオブサンプル性能について検討した。 SCOの非平滑なケースでは、SGDのごく一部のエポックが既にそのアウト・オブ・サンプルを著しく損なっており、オーバーフィッティングにつながることが示されている。
• 参考スコア（独自算出の注目度）: 34.451177321785146
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the out-of-sample performance of multi-pass stochastic gradient descent (SGD) in the fundamental stochastic convex optimization (SCO) model. While one-pass SGD is known to achieve an optimal $\Theta(1/\sqrt{n})$ excess population loss given a sample of size $n$, much less is understood about the multi-pass version of the algorithm which is widely used in practice. Somewhat surprisingly, we show that in the general non-smooth case of SCO, just a few epochs of SGD can already hurt its out-of-sample performance significantly and lead to overfitting. In particular, using a step size $\eta = \Theta(1/\sqrt{n})$, which gives the optimal rate after one pass, can lead to population loss as large as $\Omega(1)$ after just one additional pass. More generally, we show that the population loss from the second pass onward is of the order $\Theta(1/(\eta T) + \eta \sqrt{T})$, where $T$ is the total number of steps. These results reveal a certain phase-transition in the out-of-sample behavior of SGD after the first epoch, as well as a sharp separation between the rates of overfitting in the smooth and non-smooth cases of SCO. Additionally, we extend our results to with-replacement SGD, proving that the same asymptotic bounds hold after $O(n \log n)$ steps. Finally, we also prove a lower bound of $\Omega(\eta \sqrt{n})$ on the generalization gap of one-pass SGD in dimension $d = \smash{\widetilde O}(n)$, improving on recent results of Koren et al.(2022) and Schliserman et al.(2024).
• Abstract（参考訳）: 基本確率凸最適化(SCO)モデルにおけるマルチパス確率勾配勾配勾配(SGD)のサンプル外性能について検討した。 1パスのSGDは、$n$のサンプルが与えられた場合、最適な$\Theta(1/\sqrt{n})$過剰な人口損失を達成することが知られているが、実際に広く使われているアルゴリズムのマルチパスバージョンについてはあまり理解されていない。 意外なことに、SCOの一般的な非平滑なケースでは、SGDのごく一部のエポックが、そのアウト・オブ・サンプルのパフォーマンスを著しく損なうことがあり、オーバーフィッティングにつながることが示されています。 特に、ステップサイズ$\eta = \Theta(1/\sqrt{n})$を使用することで、1回の通過後に最適なレートを与えることができ、さらに1回の通過後に$\Omega(1)$の人口減少につながる。 より一般的に、第2のパスからの人口減少は$\Theta(1/(\eta T) + \eta \sqrt{T})$である。 これらの結果から,SGDの初生以降のアウト・オブ・サンプル挙動の相転移や,SCOのスムーズおよび非スムーズケースにおけるオーバーフィット率の急激な分離が明らかとなった。 さらに、我々は結果を非置換 SGD に拡張し、同じ漸近的境界が$O(n \log n)$ ステップの後に成り立つことを証明した。 最後に、次元 $d = \smash{\widetilde O}(n)$ の 1-パス SGD の一般化ギャップに対して $\Omega(\eta \sqrt{n})$ の低い境界を証明し、Koren et al (2022) と Schliserman et al (2024) の最近の結果を改善する。

関連論文リスト

• Large Stepsize Gradient Descent for Logistic Loss: Non-Monotonicity of the Loss Improves Optimization Efficiency [47.8739414267201]
  線形分離可能なデータを用いたロジスティック回帰に一定の段差を持つ勾配降下(GD)を考える。 GD はこの初期振動位相を急速に終了し、$mathcalO(eta)$ steps となり、その後$tildemathcalO (1 / (eta t) )$ convergence rate が得られることを示す。 我々の結果は、予算が$T$ ステップであれば、GD は攻撃的なステップサイズで $tildemathcalO (1/T2)$ の加速損失を達成できることを示している。
  論文  参考訳（メタデータ） (2024-02-24T23:10:28Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Lower Generalization Bounds for GD and SGD in Smooth Stochastic Convex Optimization [9.019243171993553]
  トレーニングステップ$T$とStep-size$eta$は、滑らかな凸最適化(SCO)問題の認定に影響を与える可能性がある。 まず、グラディエントDescent(GD)とグラディエントDescent(SGD)の厳密な過剰リスク低境界を提供する。 近年の作業は、より良い速度で達成できるが、トレーニング時間が長い場合には改善が減少する。
  論文  参考訳（メタデータ） (2023-03-19T20:24:33Z)
• Towards Noise-adaptive, Problem-adaptive Stochastic Gradient Descent [7.176107039687231]
  雑音に対して勾配降下(SGD)を適応させるステップサイズスキームを設計する。 我々は、Nesterov反復によるSGDの$T$反復がほぼ最適であることを示す。 他のステップサイズスキームと比較して、新しい指数的なステップサイズスキームの有効性を実証する。
  論文  参考訳（メタデータ） (2021-10-21T19:22:14Z)
• What Happens after SGD Reaches Zero Loss? --A Mathematical Framework [35.31946061894308]
  SGD(Gradient Descent)の暗黙のバイアスを理解することは、ディープラーニングにおける重要な課題の1つである。 本稿では、Katzenberger (1991) のアイデアを適応させることにより、そのような分析の一般的な枠組みを提供する。 1) a global analysis of the implicit bias for $eta-2$ steps, not to the local analysis of Blanc et al. (2020) that is only for $eta-1.6$ steps and (2) allowing any noise covariance。
  論文  参考訳（メタデータ） (2021-10-13T17:50:46Z)
• The Convergence Rate of SGD's Final Iterate: Analysis on Dimension Dependence [2.512827436728378]
  Gradient Descent (SGD) は最適化において最も単純で一般的な手法の一つである。 定次元設定におけるSGDの最終点収束を特徴付ける方法を示す。
  論文  参考訳（メタデータ） (2021-06-28T11:51:04Z)
• On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems [75.58134963501094]
  本稿では,勾配降下(SGD)の軌跡を解析する。 我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
  論文  参考訳（メタデータ） (2020-06-19T14:11:26Z)
• Almost sure convergence rates for Stochastic Gradient Descent and Stochastic Heavy Ball [17.33867778750777]
  一般近似問題に対する勾配降下法(SGD)と重球法(SHB)について検討した。 SGD の場合、凸と滑らかな設定において、イテレートの重み付き平均に対して、最初の最も確実な収束式を提供する。
  論文  参考訳（メタデータ） (2020-06-14T11:12:05Z)
• On Tight Convergence Rates of Without-replacement SGD [52.99237600875452]
  有限サム最適化問題を解くために、置換サンプリングのないSGDは、SGDより優れていることを実証的に示している。 本研究では, 時代によって異なるステップサイズを解析することによって, これらの制約を克服する。
  論文  参考訳（メタデータ） (2020-04-18T16:14:11Z)
• A Simple Convergence Proof of Adam and Adagrad [74.24716715922759]
  我々はAdam Adagradと$O(d(N)/st)$アルゴリズムの収束の証明を示す。 Adamはデフォルトパラメータで使用する場合と同じ収束$O(d(N)/st)$で収束する。
  論文  参考訳（メタデータ） (2020-03-05T01:56:17Z)

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

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