論文の概要: Sign Operator for Coping with Heavy-Tailed Noise: High Probability Convergence Bounds with Extensions to Distributed Optimization and Comparison Oracle
- arxiv url: http://arxiv.org/abs/2502.07923v1
- Date: Tue, 11 Feb 2025 19:54:11 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-02-13 18:10:00.759671
- Title: Sign Operator for Coping with Heavy-Tailed Noise: High Probability Convergence Bounds with Extensions to Distributed Optimization and Comparison Oracle
- Title（参考訳）: 重音による符号化のための符号演算子:分散最適化の拡張とOracleの比較による高確率収束境界
- Authors: Nikita Kornilov, Philip Zmushko, Andrei Semenov, Alexander Gasnikov, Alexander Beznosikov,
- Abstract要約: SignSGDは, 高い精度で, 最適な試料量$tildeO(varepsilon-frac3kappa - 2kappa 1right)を達成できることを示す。
また、2つの異なる点における関数値を比較することしかできないオラクルを用いて、符号演算子のゼロ階最適化への応用についても検討する。
- 参考スコア（独自算出の注目度）: 77.3806516979843
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The growing popularity of AI optimization problems involving severely corrupted data has increased the demand for methods capable of handling heavy-tailed noise, i.e., noise with bounded $\kappa$-th moment, $\kappa \in (1,2]$. For the widely used clipping technique, effectiveness heavily depends on the careful tuning of clipping levels throughout training. In this paper, we demonstrate that using only the sign of the input, without introducing additional hyperparameters, is sufficient to cope with heavy-tailed noise effectively. For smooth non-convex functions, we prove that SignSGD achieves optimal sample complexity $\tilde{O}\left(\varepsilon^{-\frac{3\kappa - 2}{\kappa - 1}}\right)$ with high probability for attaining an average gradient norm accuracy of $\varepsilon$. Under the assumption of symmetric noise, we use SignSGD with Majority Voting to extend this bound to the distributed optimization or reduce the sample complexity to $\tilde{O}(\varepsilon^{-4})$ in the case of a single worker with arbitrary parameters. Furthermore, we explore the application of the sign operator in zeroth-order optimization with an oracle that can only compare function values at two different points. We propose a novel method, MajorityVote-CompsSGD, and provide the first-known high-probability bound $\tilde{O}(\varepsilon^{-6})$ for the number of comparisons under symmetric noise assumption. Our theoretical findings are supported by the superior performance of sign-based methods in training Large Language Models.
- Abstract（参考訳）: ひどく破損したデータを含むAI最適化問題の人気が高まっているため、重い尾のノイズを扱うことのできるメソッド、すなわち境界付き$\kappa$-th moment, $\kappa \in (1,2]$のノイズに対する需要が高まっている。
広く使われているクリッピング技術では, クリッピングレベルの注意深い調整が有効である。
本稿では,入力の符号のみを用いることで,重み付き雑音を効果的に扱えることを示す。
滑らかな非凸関数に対しては、SignSGD が最適なサンプル複雑性 $\tilde{O}\left(\varepsilon^{-\frac{3\kappa - 2}{\kappa - 1}}\right)$ を達成することを証明する。
対称ノイズの仮定の下で、我々はSignSGDとMajority Votingを使ってこの境界を分散最適化に拡張し、任意のパラメータを持つ単一ワーカーの場合、サンプルの複雑さを$\tilde{O}(\varepsilon^{-4})$に削減する。
さらに、2つの異なる点における関数値を比較することしかできないオラクルを用いて、符号演算子のゼロ階最適化への応用について検討する。
そこで我々はMajorityVote-CompsSGDという新しい手法を提案し、対称雑音仮定による比較数に対して、最初の高確率境界$\tilde{O}(\varepsilon^{-6})$を提供する。
我々の理論的な知見は,大規模言語モデルの訓練における手話に基づく手法の優れた性能に支えられている。
関連論文リスト
- High Probability Complexity Bounds of Trust-Region Stochastic Sequential Quadratic Programming with Heavy-Tailed Noise [23.663813244183984]
本稿では,TR-SSQP(Trust-Region Sequential Quadratic Programming)法を提案する。
一階および二階の$epsilon$-stationary点を特定するための高確率複雑性境界を確立する。
提案手法は,光尾雑音設定と同一の高確率1次複雑性を実現する。
論文 参考訳（メタデータ） (2025-03-24T19:23:13Z) - Stochastic Halpern iteration in normed spaces and applications to reinforcement learning [0.30693357740321775]
基礎となるオラクルが一様有界であれば,本手法は全体のオラクル複雑性が$tildeO(varepsilon-5)$であることを示す。
平均報酬と割引報酬を決定するための新しい同期アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-03-19T01:07:35Z) - On Partial Optimal Transport: Revising the Infeasibility of Sinkhorn and
Efficient Gradient Methods [17.14725907264431]
本稿では,少なくとも$n$の支持を持つ2つの不均衡測度間の部分最適輸送(POT)問題について検討する。
我々はPOTの新しいラウンドリングアルゴリズムを提案し、次に、$mathcalwidetilde O(n2/varepsilon4)$の複雑さを補正した実行可能なシンクホーン手順を提供する。
論文 参考訳（メタデータ） (2023-12-21T15:56:09Z) - Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization Problems [56.86067111855056]
構造密度の重み付き雑音によるクリップ最適化問題を考察する。
勾配が有限の順序モーメントを持つとき、$mathcalO(K-(alpha - 1)/alpha)$よりも高速な収束率が得られることを示す。
得られた推定値が無視可能なバイアスと制御可能な分散を持つことを示す。
論文 参考訳（メタデータ） (2023-11-07T17:39:17Z) - A Specialized Semismooth Newton Method for Kernel-Based Optimal
Transport [92.96250725599958]
カーネルベース最適輸送(OT)推定器は、サンプルからOT問題に対処するための代替的機能的推定手順を提供する。
SSN法は, 標準正規性条件下でのグローバル収束率$O (1/sqrtk)$, 局所二次収束率を達成できることを示す。
論文 参考訳（メタデータ） (2023-10-21T18:48:45Z) - Accelerating Inexact HyperGradient Descent for Bilevel Optimization [84.00488779515206]
本稿では,一般的な非コンケーブ二段階最適化問題の解法を提案する。
また,非コンケーブ問題における2次定常点を求める際の既存の複雑性も改善した。
論文 参考訳（メタデータ） (2023-06-30T20:36:44Z) - A Fully First-Order Method for Stochastic Bilevel Optimization [8.663726907303303]
一階勾配オラクルのみが利用できる場合、制約のない二段階最適化問題を考える。
完全一階近似法(F2SA)を提案し,その非漸近収束特性について検討する。
MNISTデータハイパクリーニング実験において,既存の2次手法よりも提案手法の実用性能が優れていることを示す。
論文 参考訳（メタデータ） (2023-01-26T05:34:21Z) - An Efficient Stochastic Algorithm for Decentralized Nonconvex-Strongly-Concave Minimax Optimization [25.00475462213752]
Decentralized Recursive Dec. Method (DREAM)
具体的には、$mathcalO(minminappaappa3eps-3,kappa2N)$ one-order oracle (SFO)コールと$tildemathcalO(kappa2 epsilon-2)通信ラウンドが必要です。
我々の数値実験は,従来の手法の優越性を検証した。
論文 参考訳（メタデータ） (2022-12-05T16:09:39Z) - Second-Order Information in Non-Convex Stochastic Optimization: Power
and Limitations [54.42518331209581]
私たちは発見するアルゴリズムを見つけます。
epsilon$-approximate stationary point ($|nabla F(x)|le epsilon$) using
$(epsilon,gamma)$surimateランダムランダムポイント。
ここでの私たちの下限は、ノイズのないケースでも新規です。
論文 参考訳（メタデータ） (2020-06-24T04:41:43Z) - Learning Halfspaces with Tsybakov Noise [50.659479930171585]
テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。
真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
論文 参考訳（メタデータ） (2020-06-11T14:25:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。