論文の概要: The Cost of an Unknown Horizon for the Last Iterate of Clipped SGD under Heavy-Tailed Noise
- arxiv url: http://arxiv.org/abs/2610.33381v2
- Date: Tue, 27 Oct 2026 02:19:08 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-29 04:15:49.160809
- Title: The Cost of an Unknown Horizon for the Last Iterate of Clipped SGD under Heavy-Tailed Noise
- Title（参考訳）: 重音下でのクラッピングSGDの最終繰り返しにおける未知水平のコスト
- Abstract要約: 重み付き雑音下での滑らかな凸面上で, 切断したSGDの最後の繰り返し時間に対する最適一様速度を決定する。
水平線入力や信頼入力のないスケジュールは、常に$tilde O(t-_p)$に達する。
- 参考スコア（独自算出の注目度）: 8.428362872515416
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Training is often stopped at a data-dependent time, so guarantees for the last iterate must hold at all times simultaneously. We determine the optimal time-uniform rate for the last iterate of clipped SGD on smooth convex objectives under heavy-tailed noise with a bounded central $p$th moment, $1<p\le2$. A schedule without horizon or confidence inputs attains $\tilde O(t^{-β_p})$ at all times, with $β_p=2(p-1)/(3p-1)$, also almost surely, and no rule that steps along the stochastic gradient at its current iterate attains $\tilde O(t^{-r})$ for any $r>β_p$, even with adaptive step sizes and thresholds. This rate lies between the optimal rate $O(T^{-α_p})$ for a known horizon $T$, $α_p=(p-1)/p$, and the previous time-uniform rate $\tilde O(t^{-2(p-1)/(3p)})$ (Chezhegov et al., ICLR 2026); under finite variance, the exponents are $1/2$, $2/5$, and $1/3$. Their conjecture that a better schedule reaches the optimal rate thus holds with a known horizon (Liu; Jiang et al.) but fails without one. Querying gradients at the running average attains $\tilde O(t^{-α_p})$ at all times, whereas heavy-ball momentum with geometric forgetting and polynomially bounded steps cannot improve on $β_p$.
- Abstract（参考訳）: トレーニングはデータ依存の時間で停止されることが多いため、最後のイテレーションの保証は常に同時に保持されなければならない。
重み付き雑音下でのスムーズな凸目標に対して, 切断したSGDの最後の繰り返しに対する最適時間均一率を1<p\le2$, 1<p\le2$で決定する。
地平線や信頼度を持たないスケジュールは、常に$\tilde O(t^{-β_p})$に達し、ほぼ確実に$β_p=2(p-1)/(3p-1)$であり、現在のイテレートでの確率勾配に沿ったステップは、任意の$r>β_p$に対して$\tilde O(t^{-r})$となる。
この値は、既知の地平線$T$, $α_p=(p-1)/p$に対する最適レート$O(T^{-α_p})$と、以前のタイムユニフォームレート$\tilde O(t^{-2(p-1)/(3p)})$(Chezhegov et al , ICLR 2026)との間にある。
より良いスケジュールが最適値に達するという彼らの予想は、既知の地平線(Liu, Jiang et al )で成り立つが、それなしでは失敗する。
ランニング平均でのクエリ勾配は、常に$\tilde O(t^{-α_p})$に達するが、幾何的な忘れ物と多項式的に有界なステップを持つ重い球運動量は、$β_p$では改善されない。
関連論文リスト
- Near-Optimal Last-Iterate Convergence of SGD in the Smooth Interpolation Regime [25.58905234810626]
本研究では, 滑らかな凸対象に対して一定段差の勾配降下(SGD)について検討した。
我々は、SGDの$-smooth convex損失に対する$T$のステップが一定のステップサイズで$02/$になると、最後の反復が予想される過剰なリスクを達成できることを確認した。
論文 参考訳（メタデータ） (2026-10-18T18:53:00Z) - Parameter-Free Interval-Dynamic Regret under Heavy-Tailed Noise [55.29259818039367]
オンライン凸最適化を1ラウンドに1つの偏りのない下位段階と、未知の有限条件の雑音モーメントであるp$th, $1ple2$で検討する。
長さ$n$の固定区間$I$に対して、学習者は最適な全水平静的レートを含む1+log(T/n)$を達成する。
論文 参考訳（メタデータ） (2026-09-30T21:03:03Z) - 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) - Constrained Online Learning with Noisy Constraint Values [55.29259818039367]
一般的な実現可能性の下では、我々のLEDGERアルゴリズムは、期待される損失$O(sqrt T)と期待される予算違反$O(sqrtTlog(eT))を達成します。
スレーター条件、フィードバックチャネル間の独立性、絶対的制約値境界は不要である。
論文 参考訳（メタデータ） (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) - 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) - Anytime Acceleration of Gradient Descent [92.02082223856479]
エム収束保証による勾配勾配勾配の段階的加速度について検討する。
滑らかな(強くない)凸最適化のために、任意の停止時間に対して、勾配降下が$O(T-1.119)$の収束保証を達成できる段階的なスケジュールを提案する。
論文 参考訳（メタデータ） (2024-11-26T18:29:44Z) - Breaking the Lower Bound with (Little) Structure: Acceleration in
Non-Convex Stochastic Optimization with Heavy-Tailed Noise [28.780192812703948]
重み付き雑音状態において、滑らかだが必ずしも凸な目標を持つ最適化問題を考察する。
簡単な構造しか持たない低境界の$Omega(Tfrac1-p3p-2)$よりも高速な速度が得られることを示す。
また、軽度条件下では、高い確率収束率が$O(log(T/delta)Tfrac1-p3p-2)$であることを保証する。
論文 参考訳（メタデータ） (2023-02-14T00:23:42Z) - Nearly Horizon-Free Offline Reinforcement Learning [97.36751930393245]
S$状態、$A$アクション、計画的地平$H$で、エピソードな時間同質なMarkov決定プロセスに関するオフライン強化学習を再考する。
経験的MDPを用いた評価と計画のための,約$H$自由なサンプル複雑性境界の最初の集合を得る。
論文 参考訳（メタデータ） (2021-03-25T18:52:17Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。