論文の概要: 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$でも機能し、文学におけるノイズモーメントの仮定を厳密に緩和する。
関連論文リスト
- Differential Privacy of Noisy (S)GD under Heavy-Tailed Perturbations [6.220757855114254]
降下反復音(SGD)に重尾ノイズを注入することは,ここ数年で注目されている。
重み付き摂動を持つSGDは、(0, tildemathcalO (1/n)$ DP保証が得られることを示す。
重み付きノイズ発生機構はガウスの場合と同じようなDP保証を実現し,軽み付きノイズの代替となる可能性が示唆された。
論文 参考訳(メタデータ) (2024-03-04T13:53:41Z) - Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization
Problems [61.002740957716156]
構造密度の重み付き雑音によるクリップ最適化問題を考察する。
勾配が有限の順序モーメントを持つとき、$mathcalO(K-(alpha - 1)/alpha)$よりも高速な収束率が得られることを示す。
得られた推定値が無視可能なバイアスと制御可能な分散を持つことを示す。
論文 参考訳(メタデータ) (2023-11-07T17:39:17Z) - Two Sides of One Coin: the Limits of Untuned SGD and the Power of
Adaptive Methods [22.052459124774504]
本研究では,未調整のSGDに対する適応的手法により,スムーズさと情報優位性で問題を緩和することを示す。
この結果から, 指数関数依存性が欠如している場合, 未修正SGDに対する適応手法の理論的正当性について検討した。
論文 参考訳(メタデータ) (2023-05-21T14:40:43Z) - Clipped Stochastic Methods for Variational Inequalities with
Heavy-Tailed Noise [64.85879194013407]
単調なVIPと非単調なVIPの解法における信頼度に対数的依存を持つ最初の高確率結果が証明された。
この結果は光尾の場合で最もよく知られたものと一致し,非単調な構造問題に新鮮である。
さらに,多くの実用的な定式化の勾配雑音が重く,クリッピングによりSEG/SGDAの性能が向上することを示す。
論文 参考訳(メタデータ) (2022-06-02T15:21:55Z) - 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) - Benign Underfitting of Stochastic Gradient Descent [72.38051710389732]
本研究では,適切な学習データを得ることで,一般化性能を実現する「従来型」学習ルールとして,勾配降下度(SGD)がどの程度理解されるかを検討する。
類似現象が起こらない近縁な交換SGDを解析し、その集団リスクが実際に最適な速度で収束することを証明する。
論文 参考訳(メタデータ) (2022-02-27T13:25:01Z) - On the Double Descent of Random Features Models Trained with SGD [78.0918823643911]
勾配降下(SGD)により最適化された高次元におけるランダム特徴(RF)回帰特性について検討する。
本研究では, RF回帰の高精度な非漸近誤差境界を, 定常および適応的なステップサイズSGD設定の下で導出する。
理論的にも経験的にも二重降下現象を観察する。
論文 参考訳(メタデータ) (2021-10-13T17:47:39Z) - Global Convergence and Stability of Stochastic Gradient Descent [0.0]
我々は,SGDがほぼ任意の非特異性および雑音モデルの下で定常点に収束することを示す。
我々は,SGDがグローバルな信頼の収束に関する様々な問題に適用可能であることを示す。
論文 参考訳(メタデータ) (2021-10-04T19:00:50Z) - Convergence Rates of Stochastic Gradient Descent under Infinite Noise
Variance [14.06947898164194]
ヘビーテールは様々なシナリオで勾配降下 (sgd) で現れる。
SGDの収束保証は、潜在的に無限のばらつきを持つ状態依存性および重尾ノイズ下で提供します。
その結果,SGDは無限に分散した重尾雑音下であっても,地球最適値に収束できることが示された。
論文 参考訳(メタデータ) (2021-02-20T13:45:11Z) - Faster Convergence of Stochastic Gradient Langevin Dynamics for
Non-Log-Concave Sampling [110.88857917726276]
我々は,非log-concaveとなる分布のクラスからサンプリングするために,勾配ランゲヴィンダイナミクス(SGLD)の新たな収束解析を行う。
我々のアプローチの核心は、補助的時間反転型マルコフ連鎖を用いたSGLDのコンダクタンス解析である。
論文 参考訳(メタデータ) (2020-10-19T15:23:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。