論文の概要: Tight Long-Term Tail Decay of (Clipped) SGD in Non-Convex Optimization

• arxiv url: http://arxiv.org/abs/2602.05657v1
• Date: Thu, 05 Feb 2026 13:41:13 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-06 18:49:08.952017
• Title: Tight Long-Term Tail Decay of (Clipped) SGD in Non-Convex Optimization
• Title（参考訳）: 非凸最適化における(クラッピング)SGDの長期劣化
• Authors: Aleksandar Armacki, Dragana Bajović, Dušan Jakovetić, Soummya Kar, Ali H. Sayed,
• Abstract要約: 大規模偏差理論のレンズによるSGD法における長期のテール崩壊について検討する。 我々は、テールが以前よりもはるかに早く崩壊する体制を発見し、個々のランニングに対してより強力な長期保証を提供する。
• 参考スコア（独自算出の注目度）: 62.48819955422706
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The study of tail behaviour of SGD-induced processes has been attracting a lot of interest, due to offering strong guarantees with respect to individual runs of an algorithm. While many works provide high-probability guarantees, quantifying the error rate for a fixed probability threshold, there is a lack of work directly studying the probability of failure, i.e., quantifying the tail decay rate for a fixed error threshold. Moreover, existing results are of finite-time nature, limiting their ability to capture the true long-term tail decay which is more informative for modern learning models, typically trained for millions of iterations. Our work closes these gaps, by studying the long-term tail decay of SGD-based methods through the lens of large deviations theory, establishing several strong results in the process. First, we provide an upper bound on the tails of the gradient norm-squared of the best iterate produced by (vanilla) SGD, for non-convex costs and bounded noise, with long-term decay at rate $e^{-t/\log(t)}$. Next, we relax the noise assumption by considering clipped SGD (c-SGD) under heavy-tailed noise with bounded moment of order $p \in (1,2]$, showing an upper bound with long-term decay at rate $e^{-t^{β_p}/\log(t)}$, where $β_p = \frac{4(p-1)}{3p-2}$ for $p \in (1,2)$ and $e^{-t/\log^2(t)}$ for $p = 2$. Finally, we provide lower bounds on the tail decay, at rate $e^{-t}$, showing that our rates for both SGD and c-SGD are tight, up to poly-logarithmic factors. Notably, our results demonstrate an order of magnitude faster long-term tail decay compared to existing work based on finite-time bounds, which show rates $e^{-\sqrt{t}}$ and $e^{-t^{β_p/2}}$, $p \in (1,2]$, for SGD and c-SGD, respectively. As such, we uncover regimes where the tails decay much faster than previously known, providing stronger long-term guarantees for individual runs.
• Abstract（参考訳）: SGDによって引き起こされるプロセスの尾の挙動の研究は、アルゴリズムの個々の実行に関して強い保証を提供するため、多くの関心を集めている。 多くの研究が高い確率保証を提供し、固定された確率閾値の誤差率を定量化しているが、失敗の確率を直接研究する仕事、すなわち固定された誤差閾値のテール崩壊率を定量化する仕事がない。 さらに、既存の結果は有限時間の性質であり、数百万回の反復で訓練された現代の学習モデルにとってより有益な、真の長期的な尾の崩壊を捉える能力を制限する。 我々の研究はこれらのギャップを埋め、大きな偏差理論のレンズを通してSGD法による長期の尾の崩壊を研究し、その過程でいくつかの強い結果が得られた。 まず、(バニラ) SGD が生成する最適イテレートの勾配ノルム二乗の尾辺について、非凸コストと有界雑音に対して、長期減衰率 $e^{-t/\log(t)}$ で表す。 次に、次数$p \in (1,2]$の有界なモーメントを持つ重み付き雑音の下でクリップされたSGD (c-SGD) を考えることにより、ノイズ仮定を緩和し、$β_p = \frac{4(p-1)}{3p-2}$ for $p \in (1,2)$と$e^{-t/\log^2(t)}$ for $p = 2$で長期減衰を持つ上限を示す。 最後に、テール崩壊の低い境界を$e^{-t}$で示し、SGD と c-SGD の両者の速度が、多対数因子まで厳密であることを示す。 特に、この結果は、SGD と c-SGD に対して、それぞれ $e^{-\sqrt{t}}$ と $e^{-t^{β_p/2}}$ と $p \in (1,2]$ の値を示すような、有限時間境界に基づく既存の研究に比べて、桁違いに高速な長期テール崩壊を示す。 このようにして、テールが従来よりもはるかに早く崩壊する体制を明らかにし、個々のランニングに対してより強力な長期保証を提供する。

関連論文リスト

• SGD with Dependent Data: Optimal Estimation, Regret, and Inference [3.038061705362137]
  勾配降下 (SGD) は, 広範囲の段階的スケジュールと探索率スキームの下で, 独立情報と依存情報の両方に対応できることが示されている。 SGDは統計的に最適な推定誤差と後悔を同時に達成し,既存の結果を拡張し,改善することを示す。 オンラインのスパースレグレッションのために、我々はSGDベースの新しいアルゴリズムを開発し、ストレージの$d$のみを使用し、1イテレーションあたり$O(d)$フロップを必要とする。
  論文  参考訳（メタデータ） (2026-01-04T04:52:11Z)
• Rapid Overfitting of Multi-Pass Stochastic Gradient Descent in Stochastic Convex Optimization [34.451177321785146]
  基本凸最適化(SCO)モデルにおけるマルチパス勾配勾配勾配(SGD)のアウトオブサンプル性能について検討した。 SCOの非平滑なケースでは、SGDのごく一部のエポックが既にそのアウト・オブ・サンプルを著しく損なっており、オーバーフィッティングにつながることが示されている。
  論文  参考訳（メタデータ） (2025-05-13T07:32:48Z)
• Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization Problems [56.86067111855056]
  構造密度の重み付き雑音によるクリップ最適化問題を考察する。 勾配が有限の順序モーメントを持つとき、$mathcalO(K-(alpha - 1)/alpha)$よりも高速な収束率が得られることを示す。 得られた推定値が無視可能なバイアスと制御可能な分散を持つことを示す。
  論文  参考訳（メタデータ） (2023-11-07T17:39:17Z)
• High-probability Convergence Bounds for Nonlinear Stochastic Gradient Descent Under Heavy-tailed Noise [59.25598762373543]
  重み付き雑音の存在下でのストリーミングデータにおける学習の精度保証について検討した。 解析的に、与えられた問題に対する設定の選択に$ta$を使うことができることを実証する。
  論文  参考訳（メタデータ） (2023-10-28T18:53:41Z)
• Fast Rates for the Regret of Offline Reinforcement Learning [69.23654172273085]
  無限水平割引決定プロセス(MDP)における固定行動ポリシーによって生成されたオフラインデータからの強化学習の後悔について検討する。 最適品質関数 $Q*$ に対する任意の推定が与えられたとき、定義するポリシーの後悔は、$Q*$-estimate の点収束率の指数によって与えられる速度で収束することを示す。
  論文  参考訳（メタデータ） (2021-01-31T16:17:56Z)

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

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