Fugu-MT 論文翻訳(概要): Sign Operator for Coping with Heavy-Tailed Noise in Non-Convex Optimization: High Probability Bounds Under $(L_0, L

論文の概要: Sign Operator for Coping with Heavy-Tailed Noise in Non-Convex Optimization: High Probability Bounds Under $(L_0, L_1)$-Smoothness

arxiv url: http://arxiv.org/abs/2502.07923v2
Date: Tue, 27 May 2025 15:31:20 GMT
ステータス: 翻訳完了
システム内更新日: 2025-05-28 14:37:19.176339
Title: Sign Operator for Coping with Heavy-Tailed Noise in Non-Convex Optimization: High Probability Bounds Under $(L_0, L_1)$-Smoothness
Title（参考訳）: 非凸最適化における重音対応符号演算子:(L_0, L_1)$-Smoothnessの下での高確率境界
Authors: Nikita Kornilov, Philip Zmushko, Andrei Semenov, Mark Ikonnikov, Alexander Gasnikov, Alexander Beznosikov,
Abstract要約: SignSGD with Majority Votingは,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappaka ppakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa -1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappappapa-1right,Kappaを用いて,複雑性の全範囲で堅牢に動作することを示す。
参考スコア（独自算出の注目度）: 74.18546828528298
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: In recent years, non-convex optimization problems are more often described by generalized $(L_0, L_1)$-smoothness assumption rather than standard one. Meanwhile, severely corrupted data used in these problems has increased the demand for methods capable of handling heavy-tailed noises, i.e., noises with bounded $\kappa$-th moment. Motivated by these real-world trends and challenges, we explore sign-based methods in this setup and demonstrate their effectiveness in comparison with other popular solutions like clipping or normalization. In theory, we prove the first-known high probability convergence bounds under $(L_0, L_1)$-smoothness and heavy-tailed noises with mild parameter dependencies. In the case of standard smoothness, these bounds are novel for sign-based methods as well. In particular, SignSGD with batching achieves sample complexity $\tilde{O}\left(\left(\frac{\Delta L_0d}{\varepsilon^2} + \frac{\Delta L_1d^\frac{3}{2}}{\varepsilon}\right)\left[1 + \left(\frac{\sigma}{\varepsilon}\right)^\frac{\kappa}{\kappa-1}\right]\right), \kappa \in (1,2]$. Under the assumption of symmetric noises, SignSGD with Majority Voting can robustly work on the whole range of $\kappa \in (0,2]$ with complexity $\tilde{O}\left(\left(\frac{\Delta L_0d}{\varepsilon^2} + \frac{\Delta L_1d^\frac{3}{2}}{\varepsilon}\right)\left[\frac{1}{\kappa^2} + \frac{\sigma^2}{\varepsilon^2}\right]\right)$. We also obtain results for parameter-agnostic setups, Polyak-Lojasiewicz functions and momentum-based methods (in expectation). Our theoretical findings are supported by the superior performance of sign-based methods in training Large Language Models compared to clipping and normalization.
Abstract（参考訳）: 近年では、非凸最適化問題は標準的なものよりも一般化された$(L_0, L_1)$-smoothness仮定によって説明されることが多い。一方、これらの問題で使用されるひどい破損したデータは、重い尾のノイズを扱える方法、すなわち境界の$\kappa$-thのノイズの需要を増大させている。これらの現実のトレンドや課題に触発された我々は、このセットアップにおける手話ベースの手法を探求し、クリップや正規化といった他の一般的なソリューションと比較して、それらの効果を実証する。理論的には、最初の既知の高確率収束境界は、(L_0, L_1)$-smoothnessおよび軽度パラメータ依存の重み付き雑音の下で証明する。標準滑らか性の場合、これらの境界は手話法にも新しいものである。特に SignSGD は、サンプル複雑性 $\tilde{O}\left(\left(\frac{\Delta L_0d}{\varepsilon^2} + \frac{\Delta L_1d^\frac{3}{2}}{\varepsilon}\right)\left[1 + \left(\frac{\sigma}{\varepsilon}\right)^\frac{\kappa}{\kappa-1}\right]\right), \kappa \in (1,2]$ を達成する。対称ノイズの仮定の下で、Majority Voting の SignSGD は、$\kappa \in (0,2]$ のすべての範囲で、複雑性を持つ$\tilde{O}\left(\left(\frac{\Delta L_0d}{\varepsilon^2} + \frac{\Delta L_1d^\frac{3}{2}}{\varepsilon}\right)\left[\frac{1}{\kappa^2} + \frac{\sigma^2}{\varepsilon^2}\right]\right)$ を強く扱うことができる。また、パラメータに依存しないセットアップ、Polyak-Lojasiewicz関数および運動量に基づく手法(期待)の結果を得る。我々の理論的な知見は、クリッピングや正規化と比較して、大規模言語モデルの訓練において、手話に基づく手法の優れた性能に支えられている。

論文の概要: Sign Operator for Coping with Heavy-Tailed Noise in Non-Convex Optimization: High Probability Bounds Under $(L_0, L_1)$-Smoothness

関連論文リスト