論文の概要: Nonlinear Stochastic Gradient Descent and Heavy-tailed Noise: A Unified Framework and High-probability Guarantees

• arxiv url: http://arxiv.org/abs/2410.13954v1
• Date: Thu, 17 Oct 2024 18:25:28 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-21 14:24:12.770298
• Title: Nonlinear Stochastic Gradient Descent and Heavy-tailed Noise: A Unified Framework and High-probability Guarantees
• Title（参考訳）: 非線形確率勾配の老化と重み付き雑音:統一された枠組みと高確率保証
• Authors: Aleksandar Armacki, Shuhua Yu, Pranay Sharma, Gauri Joshi, Dragana Bajovic, Dusan Jakovetic, Soummya Kar,
• Abstract要約: 本研究では,重音の存在下でのオンライン学習における高確率収束について検討する。 切断のみを考慮し、有界な$p$-thモーメントでノイズを必要とする最先端技術と比較して、幅広い非線形性の保証を提供する。
• 参考スコア（独自算出の注目度）: 56.80920351680438
• License:
• Abstract: We study high-probability convergence in online learning, in the presence of heavy-tailed noise. To combat the heavy tails, a general framework of nonlinear SGD methods is considered, subsuming several popular nonlinearities like sign, quantization, component-wise and joint clipping. In our work the nonlinearity is treated in a black-box manner, allowing us to establish unified guarantees for a broad range of nonlinear methods. For symmetric noise and non-convex costs we establish convergence of gradient norm-squared, at a rate $\widetilde{\mathcal{O}}(t^{-1/4})$, while for the last iterate of strongly convex costs we establish convergence to the population optima, at a rate $\mathcal{O}(t^{-\zeta})$, where $\zeta \in (0,1)$ depends on noise and problem parameters. Further, if the noise is a (biased) mixture of symmetric and non-symmetric components, we show convergence to a neighbourhood of stationarity, whose size depends on the mixture coefficient, nonlinearity and noise. Compared to state-of-the-art, who only consider clipping and require unbiased noise with bounded $p$-th moments, $p \in (1,2]$, we provide guarantees for a broad class of nonlinearities, without any assumptions on noise moments. While the rate exponents in state-of-the-art depend on noise moments and vanish as $p \rightarrow 1$, our exponents are constant and strictly better whenever $p < 6/5$ for non-convex and $p < 8/7$ for strongly convex costs. Experiments validate our theory, demonstrating noise symmetry in real-life settings and showing that clipping is not always the optimal nonlinearity, further underlining the value of a general framework.
• Abstract（参考訳）: 本研究では,重音の存在下でのオンライン学習における高確率収束について検討する。 重みに対処するため, 符号, 量子化, コンポーネントワイド, ジョイントクリッピングなどの一般的な非線形性を仮定し, 非線形SGD法の一般的な枠組みを検討する。 本研究では, 非線形性をブラックボックス方式で扱うことにより, 幅広い非線形手法の統一保証を確立することができる。 対称ノイズと非凸コストに対して、勾配ノルム二乗の収束を$\widetilde{\mathcal{O}}(t^{-1/4})$で確立する一方、強い凸コストの最後の反復は、最適な集団への収束を$\mathcal{O}(t^{-\zeta})$で確立する。 さらに、ノイズが対称成分と非対称成分の(バイアス)混合である場合、その大きさは混合係数、非線形成分、雑音に依存する定常成分の近傍に収束することを示す。 最先端技術と比較して、クリップングのみを考慮し、有界な$p$-thモーメント、$p \in (1,2]$でバイアスのないノイズを要求する場合、ノイズモーメントの仮定なしに幅広い非線形性の保証を提供する。 最先端の指数はノイズモーメントに依存し、$p \rightarrow 1$として消えるが、当社の指数は、非凸が$p < 6/5$、凸コストが$p < 8/7$であれば、常に、厳格に良い。 実験は我々の理論を検証し、実生活環境でノイズ対称性を示し、クリッピングが必ずしも最適非線形性であるとは限らないことを示す。

関連論文リスト

• 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)
• 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)
• Distributed Extra-gradient with Optimal Complexity and Communication Guarantees [60.571030754252824]
  複数のプロセッサ/ワーカー/クライアントがローカルなデュアルベクトルにアクセス可能なマルチGPU設定において、モノトン変分不等式(VI)問題を考察する。 モノトーンVI問題に対するデファクトアルゴリズムであるExtra-gradientは、通信効率が良くないように設計されている。 そこで本稿では,VI の解法に適した非バイアスで適応的な圧縮手法である量子化一般化外部勾配 (Q-GenX) を提案する。
  論文  参考訳（メタデータ） (2023-08-17T21:15:04Z)
• 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)

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

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