論文の概要: Gradient Descent's Last Iterate is Often (slightly) Suboptimal

• arxiv url: http://arxiv.org/abs/2604.13870v1
• Date: Wed, 15 Apr 2026 13:33:08 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-16 20:38:32.560098
• Title: Gradient Descent's Last Iterate is Often (slightly) Suboptimal
• Title（参考訳）: グラディエント・Descentのラスト・イテレートは(わずかに)最適
• Authors: Guy Kornowski, Ohad Shamir,
• Abstract要約: 我々は、勾配降下(GD)または最適変量(SGD)を用いて凸リプシッツ関数を最小化する設定を考える。 GDのノイズレスの場合においても、常に繰り返し保証を考えると、$T$の過剰なポリログ係数を避けることは不可能である。
• 参考スコア（独自算出の注目度）: 30.492009313545257
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the well-studied setting of minimizing a convex Lipschitz function using either gradient descent (GD) or its stochastic variant (SGD), and examine the last iterate convergence. By now, it is known that standard stepsize choices lead to a last iterate convergence rate of $\log T/\sqrt{T}$ after $T$ steps. A breakthrough result of Jain et al. [2019] recovered the optimal $1/\sqrt{T}$ rate by constructing a non-standard stepsize sequence. However, this sequence requires choosing $T$ in advance, as opposed to common stepsize schedules which apply for any time horizon. Moreover, Jain et al. conjectured that without prior knowledge of $T$, no stepsize sequence can ensure the optimal error for SGD's last iterate, a claim which so far remained unproven. We prove this conjecture, and in fact show that even in the noiseless case of GD, it is impossible to avoid an excess poly-log factor in $T$ when considering an anytime last iterate guarantee. Our proof further suggests that such (slightly) suboptimal stopping times are unavoidably common.
• Abstract（参考訳）: 我々は、勾配降下(GD)または確率変動(SGD)を用いて凸リプシッツ関数を最小化するためのよく研究された設定を考察し、最後の反復収束について検討する。 現在までに、標準段数選択は、$T$ステップの後の最後の反復収束率$\log T/\sqrt{T}$となることが知られている。 Jain et al [2019] によるブレークスルーの結果は、非標準のステップサイズシーケンスを構築することで、最適な 1/\sqrt{T}$ レートを回復した。 しかし、このシーケンスは、任意の時間軸に適用される一般的なステップサイズスケジュールとは対照的に、事前に$T$を選択する必要がある。 さらに、Jain et al は、$T$の事前の知識がなければ、SGD の最後の反復の最適誤差を保証する段階列は存在しないと推測した。 我々は、この予想を証明し、実際、GD のノイズレスの場合においても、常に繰り返し保証を考えるとき、$T$ の余剰ポリログ因子を避けることは不可能であることを示す。 我々の証明は、そのような(わずかに)最適下停止時間が避けられないほど多いことを示唆している。

関連論文リスト

• 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)
• From Continual Learning to SGD and Back: Better Rates for Continual Linear Models [50.11453013647086]
  以前見られたタスクの損失を、$k$の繰り返しの後、忘れること、すなわち、分析する。 実現可能な最小二乗の設定において、新しい最上界を創出する。 我々は、タスクを繰り返しないランダム化だけで、十分に長いタスクシーケンスで破滅的な事態を防げることを初めて証明した。
  論文  参考訳（メタデータ） (2025-04-06T18:39:45Z)
• Anytime Acceleration of Gradient Descent [92.02082223856479]
  エム収束保証による勾配勾配勾配の段階的加速度について検討する。 滑らかな(強くない)凸最適化のために、任意の停止時間に対して、勾配降下が$O(T-1.119)$の収束保証を達成できる段階的なスケジュールを提案する。
  論文  参考訳（メタデータ） (2024-11-26T18:29:44Z)
• Revisiting the Last-Iterate Convergence of Stochastic Gradient Methods [25.831462008050387]
  グラディエント・Descent(SGD)アルゴリズムは、実際の性能が良く、理論的な理解が欠如していることから、人々の関心を喚起している。 有限収束がより広い合成最適化や非ユークリッドノルムに証明可能な拡張が可能かどうかはまだ不明である。
  論文  参考訳（メタデータ） (2023-12-13T21:41:06Z)
• Optimal and instance-dependent guarantees for Markovian linear stochastic approximation [47.912511426974376]
  標準スキームの最後の繰り返しの2乗誤差に対して、$t_mathrmmix tfracdn$の非漸近境界を示す。 マルコフ雑音による政策評価について,これらの結果のまとめを導出する。
  論文  参考訳（メタデータ） (2021-12-23T18:47:50Z)
• 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)

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

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