論文の概要: From Gradient Clipping to Normalization for Heavy Tailed SGD

• arxiv url: http://arxiv.org/abs/2410.13849v1
• Date: Thu, 17 Oct 2024 17:59:01 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-18 13:20:49.284739
• Title: From Gradient Clipping to Normalization for Heavy Tailed SGD
• Title（参考訳）: 重り付きSGDのグラディエントクリッピングから正規化へ
• Authors: Florian Hübler, Ilyas Fatkhullin, Niao He,
• Abstract要約: 最近の実証的な証拠は、機械学習の応用が重尾ノイズを伴い、実際に有界分散の標準的な仮定に挑戦していることを示している。 本稿では, 勾配依存型雑音収束問題において, テール雑音下での厳密性を実現することができることを示す。
• 参考スコア（独自算出の注目度）: 19.369399536643773
• License:
• Abstract: Recent empirical evidence indicates that many machine learning applications involve heavy-tailed gradient noise, which challenges the standard assumptions of bounded variance in stochastic optimization. Gradient clipping has emerged as a popular tool to handle this heavy-tailed noise, as it achieves good performance in this setting both theoretically and practically. However, our current theoretical understanding of non-convex gradient clipping has three main shortcomings. First, the theory hinges on large, increasing clipping thresholds, which are in stark contrast to the small constant clipping thresholds employed in practice. Second, clipping thresholds require knowledge of problem-dependent parameters to guarantee convergence. Lastly, even with this knowledge, current sampling complexity upper bounds for the method are sub-optimal in nearly all parameters. To address these issues, we study convergence of Normalized SGD (NSGD). First, we establish a parameter-free sample complexity for NSGD of $\mathcal{O}\left(\varepsilon^{-\frac{2p}{p-1}}\right)$ to find an $\varepsilon$-stationary point. Furthermore, we prove tightness of this result, by providing a matching algorithm-specific lower bound. In the setting where all problem parameters are known, we show this complexity is improved to $\mathcal{O}\left(\varepsilon^{-\frac{3p-2}{p-1}}\right)$, matching the previously known lower bound for all first-order methods in all problem dependent parameters. Finally, we establish high-probability convergence of NSGD with a mild logarithmic dependence on the failure probability. Our work complements the studies of gradient clipping under heavy tailed noise improving the sample complexities of existing algorithms and offering an alternative mechanism to achieve high probability convergence.
• Abstract（参考訳）: 最近の実証的な証拠は、多くの機械学習アプリケーションが重尾勾配雑音を伴っており、確率最適化における有界分散の標準仮定に挑戦していることを示している。 グラディエント・クリッピングは、理論上も実用上も優れた性能を発揮するため、この重み付きノイズに対処するための一般的なツールとして登場した。 しかしながら、非凸勾配クリッピングに関する現在の理論的理解には、主な欠点が3つある。 第一に、この理論はクリッピングしきい値の増大に基づき、実際使用される小さな一定のクリッピングしきい値とは対照的である。 第二に、クリッピング閾値は収束を保証するために問題に依存したパラメータの知識を必要とする。 最後に、この知識がなくても、この手法の現在のサンプリング複雑性上限は、ほぼ全てのパラメータにおいて準最適である。 これらの課題に対処するため,正規化SGD(NSGD)の収束について検討する。 まず、パラメータフリーなサンプル複雑性を$\mathcal{O}\left(\varepsilon^{-\frac{2p}{p-1}}\right)$に対して確立し、$\varepsilon$-定常点を求める。 さらに、マッチングアルゴリズム固有の下界を提供することにより、この結果の厳密性を証明する。 すべての問題パラメータが知られている環境では、この複雑さは$\mathcal{O}\left(\varepsilon^{-\frac{3p-2}{p-1}}\right)$に改善され、すべての問題依存パラメータにおける全ての一階メソッドに対する既知の下限と一致する。 最後に, NSGDの確率収束性を確立し, 故障確率の対数的依存性を軽度に評価する。 本研究は, 既成アルゴリズムのサンプル複素量を改善するため, 重み付き雑音下での勾配クリッピングの研究を補完し, 高確率収束を実現するための代替メカニズムを提供する。

関連論文リスト

• Convergence Analysis of Adaptive Gradient Methods under Refined Smoothness and Noise Assumptions [18.47705532817026]
  AdaGradは特定の条件下では$d$でSGDより優れていることを示す。 これを動機として、目的物の滑らかさ構造と勾配のばらつきを仮定する。
  論文  参考訳（メタデータ） (2024-06-07T02:55:57Z)
• Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization Problems [56.86067111855056]
  構造密度の重み付き雑音によるクリップ最適化問題を考察する。 勾配が有限の順序モーメントを持つとき、$mathcalO(K-(alpha - 1)/alpha)$よりも高速な収束率が得られることを示す。 得られた推定値が無視可能なバイアスと制御可能な分散を持つことを示す。
  論文  参考訳（メタデータ） (2023-11-07T17:39:17Z)
• Parameter-Agnostic Optimization under Relaxed Smoothness [25.608968462899316]
  本研究では,モメンタムを用いた正規化グラディエントDescence (NSGD-M) が,問題パラメータの事前知識を必要とせずに,速度-最適の複雑性を実現できることを示す。 決定論的設定では、指数係数は、バックトラックラインサーチによるグラディエント・ディクスト(Gradient Descent)を用いることで、中和することができる。
  論文  参考訳（メタデータ） (2023-11-06T16:39:53Z)
• SGD with AdaGrad Stepsizes: Full Adaptivity with High Probability to Unknown Parameters, Unbounded Gradients and Affine Variance [33.593203156666746]
  本稿では,AdaGradが一階最適化のための適応(自己調整)手法を段階化することを示す。 低ノイズと高レジの両方で、低ノイズと高レジの両方で急激な収束率を見出す。
  論文  参考訳（メタデータ） (2023-02-17T09:46:08Z)
• High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance [59.211456992422136]
  制約の少ない仮定の下で高確率収束結果のアルゴリズムを提案する。 これらの結果は、標準機能クラスに適合しない問題を最適化するために検討された手法の使用を正当化する。
  論文  参考訳（メタデータ） (2023-02-02T10:37:23Z)
• Clipped Stochastic Methods for Variational Inequalities with Heavy-Tailed Noise [64.85879194013407]
  単調なVIPと非単調なVIPの解法における信頼度に対数的依存を持つ最初の高確率結果が証明された。 この結果は光尾の場合で最もよく知られたものと一致し,非単調な構造問題に新鮮である。 さらに,多くの実用的な定式化の勾配雑音が重く,クリッピングによりSEG/SGDAの性能が向上することを示す。
  論文  参考訳（メタデータ） (2022-06-02T15:21:55Z)
• High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tails [55.561406656549686]
  我々は、勾配推定が末尾を持つ可能性のある一階アルゴリズムを用いたヒルベルト非最適化を考える。 本研究では, 勾配, 運動量, 正規化勾配勾配の収束を高確率臨界点に収束させることと, 円滑な損失に対する最もよく知られた繰り返しを示す。
  論文  参考訳（メタデータ） (2021-06-28T00:17:01Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。 非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。 そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
  論文  参考訳（メタデータ） (2021-06-10T17:54:21Z)
• Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clipping [69.9674326582747]
  そこで本研究では,重み付き分散雑音を用いたスムーズな凸最適化のための,クリップ付きSSTMと呼ばれる新しい1次高速化手法を提案する。 この場合、最先端の結果を上回る新たな複雑さが証明される。 本研究は,SGDにおいて,ノイズに対する光細かな仮定を伴わずにクリッピングを施した最初の非自明な高確率複雑性境界を導出した。
  論文  参考訳（メタデータ） (2020-05-21T17:05:27Z)

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

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