論文の概要: Near-Optimal Last-Iterate Convergence of SGD in the Smooth Interpolation Regime

• arxiv url: http://arxiv.org/abs/2610.25469v1
• Date: Sun, 18 Oct 2026 18:53:00 GMT
• ステータス: 情報取得中
• システム内更新日: 2026-10-20 22:44:45.803389
• Title: Near-Optimal Last-Iterate Convergence of SGD in the Smooth Interpolation Regime
• Title（参考訳）: SGDのSmooth Interpolation Regimeにおける準最適最終Iterate Convergence
• Abstract要約: 本研究では, 滑らかな凸対象に対して一定段差の勾配降下(SGD)について検討した。 我々は、SGDの$-smooth convex損失に対する$T$のステップが一定のステップサイズで$02/$になると、最後の反復が予想される過剰なリスクを達成できることを確認した。
• 参考スコア（独自算出の注目度）: 25.58905234810626
• License:
• Abstract: We study the last iterate of stochastic gradient descent (SGD) with a constant stepsize on smooth convex objectives in the low-noise and interpolation regimes, where the variance $σ_\star^2$ of the stochastic gradients at the optimum is small or zero. We establish that after $T$ steps of SGD on $β$-smooth convex losses with any constant stepsize $0<η<2/β$, the last iterate attains expected excess risk $\widetilde O\bigl(\tfrac{1}{η(2-βη)^3T}+\tfracη{(2-βη)^4}σ_\star^2\bigr)$, which gives the rate $\smash{\widetilde O(1/T)}$ for every constant stepsize in the interpolation regime ($σ_\star=0$), matching the $Ω(1/T)$ lower bound up to logarithmic factors and improving upon the $O(1/\sqrt T)$ rate of Attia et al. (2026) for $η=1/β$. Our analysis is based on a new technique, which compares the second moments of the stochastic gradients along the SGD trajectory across only logarithmically many time scales. For quadratic losses in the interpolation regime, an adaptation of this technique gives an $O(1/T)$ rate for every constant stepsize, extending the recent optimal rate for the randomized Kaczmarz method of Derezinski and Dong (2026) to stepsizes above the greedy stepsize with an arguably simpler proof.
• Abstract（参考訳）: 低雑音および補間系における滑らかな凸目標に対して一定の段差を有する確率勾配降下(SGD)の最後の繰り返しについて検討し、最適点における確率勾配の差$σ_\star^2$は小さいかゼロである。 我々は、$β$-smooth convexの損失に対して$0<η<2/β$でSGDのステップを引いた後、$0<η<2/β$で、最後の反復が期待される余剰リスクを$\widetilde O\bigl(\tfrac{1}{η(2-βη)^3T}+\tfracη{(2-βη)^4}σ_\star^2\bigr)$で達成し、$\smash {\widetilde O(1/T)} の速度を$\smash {\widetilde O(1/T)} で表す。 解析は,SGD軌道に沿った確率勾配の第2モーメントを,対数的に多くの時間スケールで比較する手法に基づく。 補間系における二次的損失に対して、この手法の適応は任意の定数のステップサイズに対して$O(1/T)$レートを与え、デレジンスキーとドン(2026年)のランダム化カッツマルツ法(英語版)の最近の最適レートを拡張して、より単純な証明でグリーディのステップサイズ以上のステップ化を行う。

関連論文リスト

• A Single-Loop, Constant-Batch First-Order Penalty Method for Stochastic Bilevel Optimization [66.48718943929202]
  非強凸二値問題の場合、既存の一階法はネストループに依存するのが一般的である。 2つの相補成分を組み合わせたSingle-loop Constant-1次ペナルティ法(ICOS)を提案する。
  論文  参考訳（メタデータ） (2026-10-05T19:26:20Z)
• Fast Last-Iterate Convergence of SGD in the Smooth Interpolation Regime [26.711510824243803]
  本研究では, 最適騒音が0または0に近い政権において, 円滑な凸目標に対する勾配降下(SGD)の集団収束保証について検討した。 十分に調整されたステップサイズでは、最後の繰り返しに対してほぼ最適な$widetildeO (1/T + sigma_star/sqrtT)$レートを得る。
  論文  参考訳（メタデータ） (2025-07-15T12:52:47Z)
• Rapid Overfitting of Multi-Pass Stochastic Gradient Descent in Stochastic Convex Optimization [34.451177321785146]
  基本凸最適化(SCO)モデルにおけるマルチパス勾配勾配勾配(SGD)のアウトオブサンプル性能について検討した。 SCOの非平滑なケースでは、SGDのごく一部のエポックが既にそのアウト・オブ・サンプルを著しく損なっており、オーバーフィッティングにつながることが示されている。
  論文  参考訳（メタデータ） (2025-05-13T07:32:48Z)
• 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)
• Optimal and instance-dependent guarantees for Markovian linear stochastic approximation [47.912511426974376]
  標準スキームの最後の繰り返しの2乗誤差に対して、$t_mathrmmix tfracdn$の非漸近境界を示す。 マルコフ雑音による政策評価について,これらの結果のまとめを導出する。
  論文  参考訳（メタデータ） (2021-12-23T18:47:50Z)
• On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems [75.58134963501094]
  本稿では,勾配降下(SGD)の軌跡を解析する。 我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
  論文  参考訳（メタデータ） (2020-06-19T14:11:26Z)

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

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