論文の概要: A lower bound for stepsize-based acceleration of gradient descent

• arxiv url: http://arxiv.org/abs/2608.10418v1
• Date: Tue, 11 Aug 2026 03:06:59 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-12 19:14:45.885695
• Title: A lower bound for stepsize-based acceleration of gradient descent
• Title（参考訳）: 勾配勾配勾配の段階的加速度に対する下界
• Abstract要約: 非負のステップサイズスケジュールを持つ勾配降下の最終点収束率に対して、新しい下限の$(T-1.9319)を提示する。 この結果は、段階化スケジュールだけでは最適な$O(T-2)$収束速度まで原GDを加速できないという厳密な証拠を与える。
• 参考スコア（独自算出の注目度）: 18.733838876040537
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Recent work has shown that, for smooth convex optimization, plain gradient descent can be accelerated from its textbook convergence rate of $O(T^{-1})$ (where $T$ denotes the number of iterations) to $O\big(T^{-\log_2(1+\sqrt{2})}\big)$ using carefully designed stepsize schedules alone, without resorting to momentum or other algorithmic modifications. Despite this progress, however, little was known about lower bounds for such methods beyond the classical $Ω(T^{-2})$ benchmark for general first-order methods. In this work, we present a new lower bound of $Ω(T^{-1.9319})$ for the last-iterate convergence rate of gradient descent with predetermined nonnegative stepsize schedules. This result provides rigorous evidence that stepsize schedules alone cannot accelerate plain GD to the optimal $O(T^{-2})$ convergence rate. The proof was developed by GPT-5.6 Sol Pro under the authors' guidance.
• Abstract（参考訳）: 最近の研究によると、滑らかな凸最適化のために、平ら勾配降下は教科書収束率$O(T^{-1})$(ここで$T$は反復数を表す)から$O\big(T^{-\log_2(1+\sqrt{2})}\big)$に加速できる。 しかし、この進歩にもかかわらず、一般的な一階法に対する古典的な$Ω(T^{-2})$ベンチマークを超えて、そのような方法の下位境界についてはほとんど知られていない。 本研究では, 所定の非負のステップサイズスケジュールを持つ勾配降下の最終点収束率に対して, Ω(T^{-1.9319})$の新たな下界を提示する。 この結果は、段階化スケジュールだけでは、最適な$O(T^{-2})$収束速度まで原GDを加速できないという厳密な証拠を与える。 この証明は著者の指導の下で GPT-5.6 Sol Pro によって開発された。

関連論文リスト

• Accelerating Min-Max Optimization via Power-Law Stepsizes [46.20699762747848]
  本稿では,非拘束的ビファインmin-max最適化に対するEG法(Extragradient)の収束保証を再検討する。 決定論的動的段階化スケジュールは、任意の$varepsilon > 0$に対して、EGの収束速度を$mathcalO(T-2/3+varepsilon)$に加速させることを示す。 次に、外挿と更新の異なるステップ化を許すことで、ほぼ最適の$mathcalO(T-1+varepsilon)$への収束率がさらに向上することを示す。
  論文  参考訳（メタデータ） (2026-06-01T06:45:16Z)
• Complexity Bounds for Smooth Convex Multiobjective Optimization [0.0]
  目的値$m$の滑らかな多目的最適化において,$varepsilon$-Pareto定常点を求める際のオラクルの複雑さについて検討する。 強い凸目的に対して、任意の一階法は、$exp(-Theta(T/sqrtkappa)$ after $T$ oracle call よりも早く線形収束を示す。 適応スカラー化を伴う凸問題や一般スパン法に対して、最終イテレートの勾配ノルムに1/T2$の普遍的下界を確立する。
  論文  参考訳（メタデータ） (2025-09-16T21:33:11Z)
• Anytime Acceleration of Gradient Descent [92.02082223856479]
  エム収束保証による勾配勾配勾配の段階的加速度について検討する。 滑らかな(強くない)凸最適化のために、任意の停止時間に対して、勾配降下が$O(T-1.119)$の収束保証を達成できる段階的なスケジュールを提案する。
  論文  参考訳（メタデータ） (2024-11-26T18:29:44Z)
• Methods for Convex $(L_0,L_1)$-Smooth Optimization: Clipping, Acceleration, and Adaptivity [50.25258834153574]
  我々は、(強に)凸 $(L0)$-smooth 関数のクラスに焦点を当て、いくつかの既存のメソッドに対する新しい収束保証を導出する。 特に,スムーズなグラディエント・クリッピングを有するグラディエント・ディフレッシュと,ポリアク・ステップサイズを有するグラディエント・ディフレッシュのコンバージェンス・レートの改善を導出した。
  論文  参考訳（メタデータ） (2024-09-23T13:11:37Z)
• 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)
• Accelerated Quasi-Newton Proximal Extragradient: Faster Rate for Smooth Convex Optimization [26.328847475942894]
  我々は,本手法が$Obigl(minfrac1k2, fracsqrtdlog kk2.5bigr)$の収束率を達成できることを証明した。 我々の知る限りでは、この結果はネステロフの加速勾配に対する準ニュートン型法の証明可能な利得を示す最初のものである。
  論文  参考訳（メタデータ） (2023-06-03T23:31:27Z)
• Non-stationary Delayed Online Convex Optimization: From Full-information to Bandit Setting [71.82716109461967]
  遅延勾配が利用できる全情報ケースに対して Mild-OGD というアルゴリズムを提案する。 ミルド-OGDのダイナミックな後悔は、順番の仮定の下で$O(sqrtbardT(P_T+1))$で自動的に束縛されることを示す。 Mild-OGDのバンディット版も開発し,損失値の遅れのみを考慮に入れた,より困難なケースについて検討した。
  論文  参考訳（メタデータ） (2023-05-20T07:54:07Z)
• A first-order primal-dual method with adaptivity to local smoothness [64.62056765216386]
  凸凹対象 $min_x max_y f(x) + langle Ax, yrangle - g*(y)$, ここで、$f$ は局所リプシッツ勾配を持つ凸関数であり、$g$ は凸かつ非滑らかである。 主勾配ステップと2段ステップを交互に交互に行うCondat-Vuアルゴリズムの適応バージョンを提案する。
  論文  参考訳（メタデータ） (2021-10-28T14:19:30Z)
• On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems [75.58134963501094]
  本稿では,勾配降下(SGD)の軌跡を解析する。 我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
  論文  参考訳（メタデータ） (2020-06-19T14:11:26Z)
• 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)

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

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