論文の概要: Fast Last-Iterate Convergence of SGD in the Smooth Interpolation Regime
- arxiv url: http://arxiv.org/abs/2507.11274v2
- Date: Mon, 28 Jul 2025 11:03:24 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-07-29 14:15:46.964858
- Title: Fast Last-Iterate Convergence of SGD in the Smooth Interpolation Regime
- Title(参考訳): SGDのSmooth Interpolation RegimeにおけるFast-Iterate Convergence
- Authors: Amit Attia, Matan Schliserman, Uri Sherman, Tomer Koren,
- Abstract要約: 本研究では, 最適騒音が0または0に近い政権において, 円滑な凸目標に対する勾配降下(SGD)の集団収束保証について検討した。
十分に調整されたステップサイズでは、最後の繰り返しに対してほぼ最適な$widetildeO (1/T + sigma_star/sqrtT)$レートを得る。
- 参考スコア(独自算出の注目度): 26.711510824243803
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study population convergence guarantees of stochastic gradient descent (SGD) for smooth convex objectives in the interpolation regime, where the noise at optimum is zero or near zero. The behavior of the last iterate of SGD in this setting -- particularly with large (constant) stepsizes -- has received growing attention in recent years due to implications for the training of over-parameterized models, as well as to analyzing forgetting in continual learning and to understanding the convergence of the randomized Kaczmarz method for solving linear systems. We establish that after $T$ steps of SGD on $\beta$-smooth convex loss functions with stepsize $0 < \eta < 2/\beta$, the last iterate exhibits expected excess risk $\widetilde{O}(\frac{1}{\eta (2-\beta \eta) T^{1-\beta\eta/2}} + \frac{\eta}{(2-\beta\eta)^2} T^{\beta\eta/2} \sigma_\star^2)$, where $\sigma_\star^2$ denotes the variance of the stochastic gradients at the optimum. In particular, for a well-tuned stepsize we obtain a near optimal $\widetilde{O}(1/T + \sigma_\star/\sqrt{T})$ rate for the last iterate, extending the results of Varre et al. (2021) beyond least squares regression; and when $\sigma_\star=0$ we obtain a rate of $\smash{O(1/\sqrt T)}$ with $\eta=1/\beta$, improving upon the best-known $\smash{O(T^{-1/4})}$ rate recently established by Evron et al. (2025) in the special case of realizable linear regression.
- Abstract(参考訳): 補間系における円滑な凸目標に対する確率勾配降下(SGD)の集団収束保証について検討した。
この環境でのSGDの最後の反復の振る舞い(特に大きな(定数)ステップサイズ)は、過パラメータ化モデルのトレーニングの影響や連続学習における忘れを解析し、線形系を解くためのランダム化Kaczmarz法(英語版)の収束を理解するために近年注目されている。
SGD on $\beta$-smooth convex loss function with stepsize $0 < \eta < 2/\beta$, the last iterate exhibits expected excess risk $\widetilde{O}(\frac{1}{\eta (2-\beta \eta) T^{1-\beta\eta/2}} + \frac{\eta}{(2-\beta\eta)^2} T^{\beta\eta/2} \sigma_\star^2$。
特に、よく調整されたステップサイズに対して、最終イテレートに対して、最も最適な $\widetilde{O}(1/T + \sigma_\star/\sqrt{T})$ rate を得ることができ、最小二乗回帰を超えて Varre et al (2021) の結果を拡張することができ、そして$\sigma_\star=0$ が$\smash{O(1/\sqrt T)}$$$\eta=1/\beta$ となると、最もよく知られた $\smash{O(T^{-1/4})}$ rate が高くなる。
関連論文リスト
- Rapid Overfitting of Multi-Pass Stochastic Gradient Descent in Stochastic Convex Optimization [34.451177321785146]
基本凸最適化(SCO)モデルにおけるマルチパス勾配勾配勾配(SGD)のアウトオブサンプル性能について検討した。
SCOの非平滑なケースでは、SGDのごく一部のエポックが既にそのアウト・オブ・サンプルを著しく損なっており、オーバーフィッティングにつながることが示されている。
論文 参考訳(メタデータ) (2025-05-13T07:32:48Z) - From Continual Learning to SGD and Back: Better Rates for Continual Linear Models [50.11453013647086]
以前見られたタスクの損失を、$k$の繰り返しの後、忘れること、すなわち、分析する。
実現可能な最小二乗の設定において、新しい最上界を創出する。
我々は、タスクを繰り返しないランダム化だけで、十分に長いタスクシーケンスで破滅的な事態を防げることを初めて証明した。
論文 参考訳(メタデータ) (2025-04-06T18:39:45Z) - Nonasymptotic Analysis of Stochastic Gradient Descent with the Richardson-Romberg Extrapolation [22.652143194356864]
本研究では, 勾配勾配勾配(SGD)を一定のステップサイズで解くことで, 密接な凸と滑らかな問題を解く問題に対処する。
得られた推定子の平均二乗誤差を、反復数$n$に対して拡張する。
我々の分析は、時相マルコフ連鎖と見なされるSGDの特性に依存している。
論文 参考訳(メタデータ) (2024-10-07T15:02:48Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳(メタデータ) (2024-02-14T07:52:00Z) - Optimal and instance-dependent guarantees for Markovian linear stochastic approximation [47.912511426974376]
標準スキームの最後の繰り返しの2乗誤差に対して、$t_mathrmmix tfracdn$の非漸近境界を示す。
マルコフ雑音による政策評価について,これらの結果のまとめを導出する。
論文 参考訳(メタデータ) (2021-12-23T18:47:50Z) - Last iterate convergence of SGD for Least-Squares in the Interpolation
regime [19.05750582096579]
基本最小二乗構成におけるノイズレスモデルについて検討する。
最適予測器が完全に入力に適合すると仮定し、$langletheta_*, phi(X) rangle = Y$, ここで$phi(X)$は無限次元の非線型特徴写像を表す。
論文 参考訳(メタデータ) (2021-02-05T14:02:20Z) - Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。
i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
論文 参考訳(メタデータ) (2020-07-16T06:44:44Z) - Almost sure convergence rates for Stochastic Gradient Descent and
Stochastic Heavy Ball [17.33867778750777]
一般近似問題に対する勾配降下法(SGD)と重球法(SHB)について検討した。
SGD の場合、凸と滑らかな設定において、イテレートの重み付き平均に対して、最初の最も確実な収束式を提供する。
論文 参考訳(メタデータ) (2020-06-14T11:12:05Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。