論文の概要: High-probability Convergence Bounds for Nonlinear Stochastic Gradient Descent Under Heavy-tailed Noise

• arxiv url: http://arxiv.org/abs/2310.18784v3
• Date: Mon, 4 Dec 2023 20:45:39 GMT
• ステータス: 処理完了
• システム内更新日: 2023-12-06 19:09:22.369527
• Title: High-probability Convergence Bounds for Nonlinear Stochastic Gradient Descent Under Heavy-tailed Noise
• Title（参考訳）: 重み付き雑音下での非線形確率勾配の高確率収束境界
• Authors: Aleksandar Armacki, Pranay Sharma, Gauri Joshi, Dragana Bajovic, Dusan Jakovetic, Soummya Kar
• Abstract要約: 本研究では, 広帯域非線形SGD法における収束境界テクスタイチン高確率について検討する。 リプシッツ連続勾配の強い凸損失関数に対して、ノイズが重く抑えられた場合でも、故障確率に対数依存があることを証明する。
• 参考スコア（独自算出の注目度）: 62.227421825689895
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Several recent works have studied the convergence \textit{in high probability} of stochastic gradient descent (SGD) and its clipped variant. Compared to vanilla SGD, clipped SGD is practically more stable and has the additional theoretical benefit of logarithmic dependence on the failure probability. However, the convergence of other practical nonlinear variants of SGD, e.g., sign SGD, quantized SGD and normalized SGD, that achieve improved communication efficiency or accelerated convergence is much less understood. In this work, we study the convergence bounds \textit{in high probability} of a broad class of nonlinear SGD methods. For strongly convex loss functions with Lipschitz continuous gradients, we prove a logarithmic dependence on the failure probability, even when the noise is heavy-tailed. Strictly more general than the results for clipped SGD, our results hold for any nonlinearity with bounded (component-wise or joint) outputs, such as clipping, normalization, and quantization. Further, existing results with heavy-tailed noise assume bounded $\eta$-th central moments, with $\eta \in (1,2]$. In contrast, our refined analysis works even for $\eta=1$, strictly relaxing the noise moment assumptions in the literature.
• Abstract（参考訳）: 最近のいくつかの研究は、確率勾配降下 (sgd) の収束 \textit{in high probability} とそのクリップ付き変種を研究している。 バニラSGDと比較して、切断されたSGDは事実上安定しており、失敗確率に対する対数依存のさらなる理論的利点がある。 しかし、SGDの他の実用的な非線形変種、例えば符号 SGD、量子化 SGD および正規化 SGD の収束は、通信効率の向上や加速収束の達成をはるかに少なくする。 本研究では、非線形SGD法の幅広いクラスにおける収束境界 \textit{in high probability} について検討する。 リプシッツ連続勾配を持つ強凸損失関数に対して, 雑音が重み付きであっても, 故障確率に対する対数依存性が証明される。 クリッピングされたSGDの結果よりも厳密に一般的な結果として, クリッピング, 正規化, 量子化など, 有界(成分方向, 関節)の出力を持つ非線形性を示す。 さらに、重み付きノイズによる既存の結果は、$\eta$-th central moments, with $\eta \in (1,2]$である。 対照的に、洗練された分析は$\eta=1$でも機能し、文学におけるノイズモーメントの仮定を厳密に緩和する。

関連論文リスト

• Large Deviations and Improved Mean-squared Error Rates of Nonlinear SGD: Heavy-tailed Noise and Power of Symmetry [47.653744900375855]
  本研究では,オンライン環境における非線形凸勾配法の一般的な枠組みを,大偏差と平均二乗誤差(MSE)で保証する。 重騒音対称密度関数の存在下での広帯域ステップサイズに対する強い結果を与える。
  論文  参考訳（メタデータ） (2024-10-21T04:50:57Z)
• Nonlinear Stochastic Gradient Descent and Heavy-tailed Noise: A Unified Framework and High-probability Guarantees [56.80920351680438]
  本研究では,重音の存在下でのオンライン学習における高確率収束について検討する。 切断のみを考慮し、有界な$p$-thモーメントでノイズを必要とする最先端技術と比較して、幅広い非線形性の保証を提供する。
  論文  参考訳（メタデータ） (2024-10-17T18:25:28Z)
• Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization Problems [56.86067111855056]
  構造密度の重み付き雑音によるクリップ最適化問題を考察する。 勾配が有限の順序モーメントを持つとき、$mathcalO(K-(alpha - 1)/alpha)$よりも高速な収束率が得られることを示す。 得られた推定値が無視可能なバイアスと制御可能な分散を持つことを示す。
  論文  参考訳（メタデータ） (2023-11-07T17:39:17Z)
• Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
  滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。 漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
  論文  参考訳（メタデータ） (2022-06-17T06:10:20Z)
• High Probability Bounds for a Class of Nonconvex Algorithms with AdaGrad Stepsize [55.0090961425708]
  本研究では,AdaGradのスムーズな非確率問題に対する簡易な高確率解析法を提案する。 我々はモジュラーな方法で解析を行い、決定論的設定において相補的な$mathcal O (1 / TT)$収束率を得る。 我々の知る限りでは、これは真に適応的なスキームを持つAdaGradにとって初めての高い確率である。
  論文  参考訳（メタデータ） (2022-04-06T13:50:33Z)
• Nonlinear gradient mappings and stochastic optimization: A general framework with applications to heavy-tail noise [11.768495184175052]
  本稿では,勾配雑音が重みを示す場合の非線形勾配降下シナリオに関する一般的な枠組みを紹介する。 有界出力を持つ非線形性や1より大きい順序の有限モーメントを持たない勾配雑音に対して、非線形SGDは速度$O(/tzeta)$, $zeta in (0, 1)$でゼロに収束することを示す。 実験により、我々のフレームワークは、ヘビーテールノイズ下でのSGDの既存研究よりも汎用的であるが、我々のフレームワークから実装が容易ないくつかの非線形性は、実際のデータセット上のアート代替品の状況と競合することを示した。
  論文  参考訳（メタデータ） (2022-04-06T06:05:52Z)
• Convergence Rates of Stochastic Gradient Descent under Infinite Noise Variance [14.06947898164194]
  ヘビーテールは様々なシナリオで勾配降下 (sgd) で現れる。 SGDの収束保証は、潜在的に無限のばらつきを持つ状態依存性および重尾ノイズ下で提供します。 その結果,SGDは無限に分散した重尾雑音下であっても,地球最適値に収束できることが示された。
  論文  参考訳（メタデータ） (2021-02-20T13:45:11Z)
• Last iterate convergence of SGD for Least-Squares in the Interpolation regime [19.05750582096579]
  基本最小二乗構成におけるノイズレスモデルについて検討する。 最適予測器が完全に入力に適合すると仮定し、$langletheta_*, phi(X) rangle = Y$, ここで$phi(X)$は無限次元の非線型特徴写像を表す。
  論文  参考訳（メタデータ） (2021-02-05T14:02:20Z)

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

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