論文の概要: Improved Gradient Descent Lower Bounds Beyond Nesterov

• arxiv url: http://arxiv.org/abs/2609.02855v1
• Date: Wed, 02 Sep 2026 17:39:52 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-03 17:53:18.482808
• Title: Improved Gradient Descent Lower Bounds Beyond Nesterov
• Title（参考訳）: ネステロフを超えるグラディエントな未熟な下界の改善
• Authors: Yuhan Ye, Kaizhao Liu,
• Abstract要約: 本研究では, 滑らかな凸最適化において, 所定の段差によってどれだけの降下を加速できるかを考察する。 我々は、$(n-1.6342)$ non-anytime lower bound と $(n-1.2408)$ anytime lower bound を証明している。
• 参考スコア（独自算出の注目度）: 2.506624215459612
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study how far gradient descent (GD) can be accelerated by predetermined stepsizes in smooth convex optimization. Going beyond the classical $Ω(n^{-2})$ first-order oracle lower bound of Nemirovsky and Yudin, we prove an $Ω(n^{-1.6342})$ non-anytime lower bound and an $Ω(n^{-1.2408})$ anytime lower bound. These improve the recent $Ω(n^{-1.932})$ non-anytime lower bound of Ma and Chen and the $Ω(n^{-4/3})$ anytime lower bound of Tsai et al., respectively. Together with the non-anytime $O(n^{-\log_2(1+\sqrt{2})})$ rate achieved by silver schedules, our anytime lower bound establishes a strict separation between the achievable convergence exponents in the two settings.
• Abstract（参考訳）: 本研究では, 滑らかな凸最適化において, 所定の段差による勾配勾配勾配(GD)の加速について検討した。 古典的な$Ω(n^{-2})$ Nemirovsky と Yudin の1次オラクル下界を超えると、$Ω(n^{-1.6342})$非随時下界と$Ω(n^{-1.2408})$任意の時下界を証明できる。 これは、最近の$Ω(n^{-1.932})$ Ma と Chen の非随時下界と $Ω(n^{-4/3})$ Tsai と al の随時下界を改善する。 銀のスケジュールによって達成される非随時$O(n^{-\log_2(1+\sqrt{2})})$レートとともに、我々の任意の下限は、2つの設定における達成可能な収束指数の間の厳密な分離を確立する。

関連論文リスト

• A lower bound for stepsize-based acceleration of gradient descent [18.733838876040537]
  非負のステップサイズスケジュールを持つ勾配降下の最終点収束率に対して、新しい下限の$(T-1.9319)を提示する。 この結果は、段階化スケジュールだけでは最適な$O(T-2)$収束速度まで原GDを加速できないという厳密な証拠を与える。
  論文  参考訳（メタデータ） (2026-08-11T03:06:59Z)
• Entropy-Smooth Convex Optimization Cannot Be Accelerated [0.0]
  負のエントロピーに対する凸函数のクラスにおける最小化の収束率に対して、$(L/T)$低い境界を証明します。 このことは、ミラー降下がこのクラスの対数係数に最適であることを示している。
  論文  参考訳（メタデータ） (2026-07-29T21:34:12Z)
• Asymptotically Optimal Regret for Reinforcement Learning without Horizon Dependence [54.59847568544922]
  有限水平時間同質なマルコフ決定過程に対して、$A$状態、$A$アクション、hoighty $H$、および1ドルで有界なトラジェクティブ当たりの合計報酬について、地平自由な後悔について検討する。 失敗確率$$K$はエピソード数で$tilde O(sqrtSAK+S3K)$ hides $mathsfpolyである。
  論文  参考訳（メタデータ） (2026-07-22T07:42:19Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。 どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
  論文  参考訳（メタデータ） (2026-03-19T15:53:41Z)
• On the Condition Number Dependency in Bilevel Optimization [23.985835962136793]
  実現可能な領域が下層問題の解である上層問題によって定義される目的関数間の双レベル最適化。 2次および超滑らかな問題に対して、それぞれ$(_y13/4 )$と$(4-4)$を示す。
  論文  参考訳（メタデータ） (2025-11-27T11:03:24Z)
• On the Gradient Complexity of Private Optimization with Private Oracles [51.044364532408345]
  我々は,リプシッツ損失の個人的経験的/人口的リスクの1次オラクルクエリーの観点から,ランニング時間について検討した。 予測ランニングタイム$(minfracsqrtd2, fracdlog(1/))$は、$dgeq 1/2$のときの次元の問題に対して$$$過剰なリスクを達成するために必要であることを示す。
  論文  参考訳（メタデータ） (2025-11-17T23:58:11Z)
• Convergence Rate Analysis of LION [54.28350823319057]
  LION は、勾配カルシュ=クーン=T (sqrtdK-)$で測定された $cal(sqrtdK-)$ の反復を収束する。 従来のSGDと比較して,LIONは損失が小さく,性能も高いことを示す。
  論文  参考訳（メタデータ） (2024-11-12T11:30:53Z)
• Sharper Convergence Guarantees for Asynchronous SGD for Distributed and Federated Learning [77.22019100456595]
  通信周波数の異なる分散計算作業者のトレーニングアルゴリズムを示す。 本研究では,より厳密な収束率を$mathcalO!!(sigma2-2_avg!)とする。 また,不均一性の項は,作業者の平均遅延によっても影響されることを示した。
  論文  参考訳（メタデータ） (2022-06-16T17:10:57Z)
• Complexity Lower Bounds for Nonconvex-Strongly-Concave Min-Max Optimization [31.0295459253155]
  min-max最適化問題の定常点を求めるための1次オラクル下界を提供する。 私たちの分析は、上限が$epsilon$依存性最大$kappa$で最適であることを示しています。 この結果から, 上の$mathcalOkappa3 epsilon-4)$ in (Lin et al., 2020a) と, 近似数依存性の下位境界との間には, 有意な差があることが示唆された。
  論文  参考訳（メタデータ） (2021-04-18T04:30:01Z)
• Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$ Geometry [69.24618367447101]
  対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。 損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
  論文  参考訳（メタデータ） (2021-03-02T06:53:44Z)

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

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