Fugu-MT 論文翻訳(概要): A Lower Bound for the Heavy-Ball Method on Smooth Convex Functions

論文の概要: A Lower Bound for the Heavy-Ball Method on Smooth Convex Functions

arxiv url: http://arxiv.org/abs/2609.08656v1
Date: Tue, 08 Sep 2026 12:26:22 GMT
ステータス: 翻訳完了
システム内更新日: 2026-09-11 16:05:38.697778
Title: A Lower Bound for the Heavy-Ball Method on Smooth Convex Functions
Title（参考訳）: Smooth Convex関数のヘビーボール法における下界
Abstract要約: 古典的ヘビーボール法は、すべての滑らかな凸対象に対してネステロフの$O(T-2)$終点レートを達成することができるか? 完全に非定常で地平線に依存したチューニングであっても、古典的なヘヴィ・ボール法は滑らかな凸類に対するネステロフレートを保証することはできない。
参考スコア（独自算出の注目度）: 21.464888179731698
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Can the classical Heavy-Ball method, with arbitrary horizon-dependent parameters chosen in advance, achieve Nesterov's $O(T^{-2})$ last-iterate rate on every smooth convex objective? We provide a negative answer. For every horizon $T\ge2$ and every predetermined schedule with nonnegative step sizes and momenta in $[0,1)$, there exists a convex $1$-smooth objective, with initialization distance at most one and zero initial velocity, for which the last iterate of the Heavy-Ball method satisfies \[ f(x_T)-f^\star=Ω\!\left(\frac{1}{T^α\log T}\right), \qquad α=\frac{1+\sqrt5}{2}. \] Thus even fully nonstationary, horizon-dependent tuning cannot give the classical Heavy-Ball method a Nesterov-rate guarantee on the smooth convex class.
Abstract（参考訳）: 古典的ヘビーボール法は、任意の地平線依存パラメータを事前に選択して、任意の滑らかな凸対象に対してネステロフの$O(T^{-2})$終点レートを達成することができるか? 私たちは否定的な答えを与えます。あらゆる地平線$T\ge2$と、非負のステップサイズとモーメントが$[0,1)$のすべての所定のスケジュールに対して、凸の1$-smoothの目標が存在し、その初期化距離は最大1とゼロであり、ヘビーボール法の最終イテレーションは \[f(x_T)-f^\star=Ω\! \left(\frac{1}{T^α\log T}\right), \qquad α=\frac{1+\sqrt5}{2}。したがって、完全に非定常で地平線に依存したチューニングであっても、古典的なヘビーボール法は滑らかな凸クラスにおいてネステロフレートを保証することはできない。

関連論文リスト

Convergence of Stochastic Gradient Methods under Heavy-Tailed Noise and Hölder Smoothness [0.0]
我々は勾配クリッピング(G-Clip)を分析し、上述のレートをge1+s$で回収する一方、非常に重く細い体制では1+s$で回収することを示した。
論文参考訳（メタデータ） (2026-09-11T12:40:43Z)
The Exact Time-Uniform Rate Frontier for Stochastic Gradient Descent on Smooth Convex Objectives [26.189892200366895]
本研究では、非拘束な滑らかな凸対象に対する標準降下勾配(SGD)の原繰り返しの時間一様収束について検討する。標準的な雑音仮定の下では、時間一様収束速度が$sqrtlog n / n$に任意に近づくが、それに到達することはないことを証明している。
論文参考訳（メタデータ） (2026-09-08T10:24:19Z)
Constrained Online Learning with Noisy Constraint Values [55.29259818039367]
LEDGERは、非負のバランスでネット消費を観測した。 LEDGERは、$O(sqrt T/V)$期待の後悔と$O(sqrt V,T3/4+sqrt T)$期待の予算違反を$Vin[T-1/2,1]$で達成する。
論文参考訳（メタデータ） (2026-09-07T01:38:41Z)
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)
Improved high-dimensional estimation with Langevin dynamics and stochastic weight averaging [54.172416732517156]
ランゲヴィン力学は、前よりも平均的な反復を考えると、$n gtrsim d kstar/2 $サンプルで成功する。前者よりも平均的な反復を考えると、ランゲヴィン力学が$n gtrsim d kstar/2 $サンプルで成功することを示す。
論文参考訳（メタデータ） (2026-03-06T08:23:24Z)
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)
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)
Convergence Rate for the Last Iterate of Stochastic Gradient Descent Schemes [0.0]
Fdelta が凸であるときに SHB が$F_*$ で一定運動量に達することを証明した。また、Fdelta が凸であるときに SHB が$F_*$ の運動量を得ることを示す。
論文参考訳（メタデータ） (2025-07-09T20:59:23Z)
Heavy-Tailed Linear Bandits: Huber Regression with One-Pass Update [62.96781471194877]
ヘビーテール付きバンディットには、ヘビーテール付きノイズ、トランケーション、中央値の2つの基本戦略が導入されている。本稿では,オンラインミラー降下フレームワークに基づくEmphone-passアルゴリズムを提案する。
論文参考訳（メタデータ） (2025-03-01T09:41:45Z)
Sign Operator for Coping with Heavy-Tailed Noise in Non-Convex Optimization: High Probability Bounds Under $(L_0, L_1)$-Smoothness [74.18546828528298]
SignSGD with Majority Votingは,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappaka ppakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa -1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappappapa-1right,Kappaを用いて,複雑性の全範囲で堅牢に動作することを示す。
論文参考訳（メタデータ） (2025-02-11T19:54:11Z)
Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
制約付き非線形最適化問題のオンライン統計的推測を考察する。これらの問題を解決するために、逐次二次計画法(StoSQP)を適用する。
論文参考訳（メタデータ） (2022-05-27T00:34:03Z)
Accelerated Primal-Dual Gradient Method for Smooth and Convex-Concave Saddle-Point Problems with Bilinear Coupling [84.47780064014262]
線形凸凹サドル点問題 $min_xmax_y f(x) ytopmathbfA x - g(y) について検討する。
論文参考訳（メタデータ） (2021-12-30T20:31:46Z)
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)
Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。我々はCIFARに関する実験結果を示し,その理論を検証した。
論文参考訳（メタデータ） (2020-02-08T22:02:14Z)

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