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

• arxiv url: http://arxiv.org/abs/2310.18784v7
• Date: Wed, 1 May 2024 02:30:23 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-02 20:21:02.346357
• 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要約: 重み付き雑音の存在下でのストリーミングデータにおける学習の精度保証について検討した。 解析的に、与えられた問題に対する設定の選択に$ta$を使うことができることを実証する。
• 参考スコア（独自算出の注目度）: 59.25598762373543
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study high-probability convergence guarantees of learning on streaming data in the presence of heavy-tailed noise. In the proposed scenario, the model is updated in an online fashion, as new information is observed, without storing any additional data. To combat the heavy-tailed noise, we consider a general framework of nonlinear stochastic gradient descent (SGD), providing several strong results. First, for non-convex costs and component-wise nonlinearities, we establish a convergence rate arbitrarily close to $\mathcal{O}\left(t^{-\frac{1}{4}}\right)$, whose exponent is independent of noise and problem parameters. Second, for strongly convex costs and component-wise nonlinearities, we establish a rate arbitrarily close to $\mathcal{O}\left(t^{-\frac{1}{2}}\right)$ for the weighted average of iterates, with exponent again independent of noise and problem parameters. Finally, for strongly convex costs and a broader class of nonlinearities, we establish convergence of the last iterate, with a rate $\mathcal{O}\left(t^{-\zeta} \right)$, where $\zeta \in (0,1)$ depends on problem parameters, noise and nonlinearity. As we show analytically and numerically, $\zeta$ can be used to inform the preferred choice of nonlinearity for given problem settings. Compared to state-of-the-art, who only consider clipping, require bounded noise moments of order $\eta \in (1,2]$, and establish convergence rates whose exponents go to zero as $\eta \rightarrow 1$, we provide high-probability guarantees for a much broader class of nonlinearities and symmetric density noise, with convergence rates whose exponents are bounded away from zero, even when the noise has finite first moment only. Moreover, in the case of strongly convex functions, we demonstrate analytically and numerically that clipping is not always the optimal nonlinearity, further underlining the value of our general framework.
• Abstract（参考訳）: 本研究では,重み付き雑音の存在下でのストリーミングデータ学習の高確率収束保証について検討する。 提案シナリオでは,新たな情報が観測されるにつれて,追加データを保持することなく,オンライン形式でモデルが更新される。 重み付き雑音に対処するため,非線形確率勾配勾配(SGD)の一般的な枠組みを考察し,いくつかの強い結果を得た。 まず、非凸コストと成分的非線形性に対して、指数が雑音や問題パラメータに依存しない$\mathcal{O}\left(t^{-\frac{1}{4}}\right)$に任意の収束速度を確立する。 第二に、強い凸コストと成分の非線形性のために、重み付けされたイテレートの平均に対して$\mathcal{O}\left(t^{-\frac{1}{2}}\right)$に任意に近い速度を定め、指数は再びノイズと問題パラメータから独立する。 最後に、強い凸コストとより広範な非線形性のために、最後の反復の収束を確立し、$\mathcal{O}\left(t^{-\zeta} \right)$で、$\zeta \in (0,1)$は問題パラメータ、ノイズ、非線形性に依存する。 解析的および数値的に示すように、$\zeta$ は与えられた問題設定に対して好まれる非線形性の選択を知らせるのに使うことができる。 クリッピングのみを考慮し、次数$\eta \in (1,2]$の有界雑音モーメントを必要とし、指数が0となる収束率を$\eta \rightarrow 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)

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

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