論文の概要: Large Deviations and Improved Mean-squared Error Rates of Nonlinear SGD: Heavy-tailed Noise and Power of Symmetry

• arxiv url: http://arxiv.org/abs/2410.15637v1
• Date: Mon, 21 Oct 2024 04:50:57 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-22 13:15:40.225861
• Title: Large Deviations and Improved Mean-squared Error Rates of Nonlinear SGD: Heavy-tailed Noise and Power of Symmetry
• Title（参考訳）: 非線形SGDの大規模偏差と平均2乗誤差率の改善:重テールノイズと対称性のパワー
• Authors: Aleksandar Armacki, Shuhua Yu, Dragana Bajovic, Dusan Jakovetic, Soummya Kar,
• Abstract要約: 本研究では,オンライン環境における非線形凸勾配法の一般的な枠組みを,大偏差と平均二乗誤差(MSE)で保証する。 重騒音対称密度関数の存在下での広帯域ステップサイズに対する強い結果を与える。
• 参考スコア（独自算出の注目度）: 47.653744900375855
• License:
• Abstract: We study large deviations and mean-squared error (MSE) guarantees of a general framework of nonlinear stochastic gradient methods in the online setting, in the presence of heavy-tailed noise. Unlike existing works that rely on the closed form of a nonlinearity (typically clipping), our framework treats the nonlinearity in a black-box manner, allowing us to provide unified guarantees for a broad class of bounded nonlinearities, including many popular ones, like sign, quantization, normalization, as well as component-wise and joint clipping. We provide several strong results for a broad range of step-sizes in the presence of heavy-tailed noise with symmetric probability density function, positive in a neighbourhood of zero and potentially unbounded moments. In particular, for non-convex costs we provide a large deviation upper bound for the minimum norm-squared of gradients, showing an asymptotic tail decay on an exponential scale, at a rate $\sqrt{t} / \log(t)$. We establish the accompanying rate function, showing an explicit dependence on the choice of step-size, nonlinearity, noise and problem parameters. Next, for non-convex costs and the minimum norm-squared of gradients, we derive the optimal MSE rate $\widetilde{\mathcal{O}}(t^{-1/2})$. Moreover, for strongly convex costs and the last iterate, we provide an MSE rate that can be made arbitrarily close to the optimal rate $\mathcal{O}(t^{-1})$, improving on the state-of-the-art results in the presence of heavy-tailed noise. Finally, we establish almost sure convergence of the minimum norm-squared of gradients, providing an explicit rate, which can be made arbitrarily close to $o(t^{-1/4})$.
• Abstract（参考訳）: 本研究では,重み付き雑音の存在下でのオンライン環境における非線形確率勾配法の一般的な枠組みについて,大きな偏差と平均二乗誤差(MSE)の保証について検討する。 非線形性(典型的にはクリッピング)の閉形式に依存する既存の研究とは異なり、我々のフレームワークはブラックボックス方式で非線形性を扱い、符号、量子化、正規化、コンポーネントワイドおよびジョイントクリッピングといった多くの一般的な非線形性の幅広いクラスに対して統一された保証を提供することができる。 本研究は, 確率密度関数が対称な重み付き雑音の存在下では, ゼロ近傍では正であり, 潜在的に非有界なモーメントが存在する場合において, 幅広いステップサイズに対して強い結果を与える。 特に、非凸コストに対しては、最小ノルム二乗の勾配に対して大きな偏差上界を提供し、指数スケールでの漸近的テール崩壊を$\sqrt{t} / \log(t)$で示す。 本研究では, ステップサイズ, 非線形性, ノイズ, 問題パラメータの選択に明示的に依存していることを示す。 次に、非凸コストと勾配の最小ノルム二乗に対して、最適MSEレート$\widetilde{\mathcal{O}}(t^{-1/2})$を導出する。 さらに, 厳密な凸コストと最終反復率に対して, 最適値である$\mathcal{O}(t^{-1})$に任意に近づくことができるMSEレートを提供し, 重み付き雑音の存在下での最先端結果を改善する。 最後に、最小ノルム二乗の勾配の収束をほぼ確実にし、明示的な速度を与え、$o(t^{-1/4})$に任意に近づくことができる。

関連論文リスト

• 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)
• High-probability Convergence Bounds for Nonlinear Stochastic Gradient Descent Under Heavy-tailed Noise [59.25598762373543]
  重み付き雑音の存在下でのストリーミングデータにおける学習の精度保証について検討した。 解析的に、与えられた問題に対する設定の選択に$ta$を使うことができることを実証する。
  論文  参考訳（メタデータ） (2023-10-28T18:53:41Z)
• Convex and Non-convex Optimization Under Generalized Smoothness [69.69521650503431]
  凸法と非最適化法の分析は、しばしばリプシッツ勾配を必要とし、この軌道による解析を制限する。 最近の研究は、非一様滑らか性条件を通した勾配設定を一般化している。
  論文  参考訳（メタデータ） (2023-06-02T04:21:59Z)
• 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)
• High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tails [55.561406656549686]
  我々は、勾配推定が末尾を持つ可能性のある一階アルゴリズムを用いたヒルベルト非最適化を考える。 本研究では, 勾配, 運動量, 正規化勾配勾配の収束を高確率臨界点に収束させることと, 円滑な損失に対する最もよく知られた繰り返しを示す。
  論文  参考訳（メタデータ） (2021-06-28T00:17:01Z)
• 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)

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

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