論文の概要: Nonconvex Stochastic Optimization under Heavy-Tailed Noises: Optimal Convergence without Gradient Clipping

• arxiv url: http://arxiv.org/abs/2412.19529v1
• Date: Fri, 27 Dec 2024 08:46:46 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-30 17:28:13.059931
• Title: Nonconvex Stochastic Optimization under Heavy-Tailed Noises: Optimal Convergence without Gradient Clipping
• Title（参考訳）: 重音下での非凸確率最適化:勾配クリップを伴わない最適収束
• Authors: Zijian Liu, Zhengyuan Zhou,
• Abstract要約: 重み付き雑音下での最初の収束を提供するが、切断はしない。 また、テールインデックス$mathfrakp$が事前に不明な場合には、最初の$mathcalO(Tfrac1-mathfrakp3mathfrakp-2)$収束率も設定する。
• 参考スコア（独自算出の注目度）: 21.865728815935665
• License:
• Abstract: Recently, the study of heavy-tailed noises in first-order nonconvex stochastic optimization has gotten a lot of attention since it was recognized as a more realistic condition as suggested by many empirical observations. Specifically, the stochastic noise (the difference between the stochastic and true gradient) is considered only to have a finite $\mathfrak{p}$-th moment where $\mathfrak{p}\in\left(1,2\right]$ instead of assuming it always satisfies the classical finite variance assumption. To deal with this more challenging setting, people have proposed different algorithms and proved them to converge at an optimal $\mathcal{O}(T^{\frac{1-\mathfrak{p}}{3\mathfrak{p}-2}})$ rate for smooth objectives after $T$ iterations. Notably, all these new-designed algorithms are based on the same technique - gradient clipping. Naturally, one may want to know whether the clipping method is a necessary ingredient and the only way to guarantee convergence under heavy-tailed noises. In this work, by revisiting the existing Batched Normalized Stochastic Gradient Descent with Momentum (Batched NSGDM) algorithm, we provide the first convergence result under heavy-tailed noises but without gradient clipping. Concretely, we prove that Batched NSGDM can achieve the optimal $\mathcal{O}(T^{\frac{1-\mathfrak{p}}{3\mathfrak{p}-2}})$ rate even under the relaxed smooth condition. More interestingly, we also establish the first $\mathcal{O}(T^{\frac{1-\mathfrak{p}}{2\mathfrak{p}}})$ convergence rate in the case where the tail index $\mathfrak{p}$ is unknown in advance, which is arguably the common scenario in practice.
• Abstract（参考訳）: 近年, 1次非凸確率最適化における重み付き雑音の研究は, 多くの経験的観測から示唆されるより現実的な条件として認識され, 注目されている。 具体的には、確率ノイズ(確率的勾配と真の勾配の差)は、古典的な有限偏差仮定を常に満たすのではなく、$\mathfrak{p}$-第モーメントしか持たないと考えられる。 このより困難な設定に対処するために、人々は異なるアルゴリズムを提案し、それらを最適な$\mathcal{O}(T^{\frac{1-\mathfrak{p}}{3\mathfrak{p}-2}})$T$反復後の滑らかな目的に対して収束することを証明した。 特に、これらの新しく設計されたアルゴリズムはすべて、勾配クリッピングという同じ手法に基づいている。 当然、切り抜き法が必須成分であり、重音下での収束を保証する唯一の方法であるかどうかを知る必要がある。 本研究は,既存のBatched Normalized Stochastic Gradient Descent with Momentum (Batched NSGDM) アルゴリズムを再検討することにより,重み付き雑音下での1次収束結果を提供する。 具体的には、Batched NSGDMが緩和された滑らかな条件下であっても最適な$\mathcal{O}(T^{\frac{1-\mathfrak{p}}{3\mathfrak{p}-2}})$レートを達成できることを示す。 さらに興味深いことに、テール指数 $\mathfrak{p}$ が前もって未知の場合には、最初の $\mathcal{O}(T^{\frac{1-\mathfrak{p}}{2\mathfrak{p}}})$収束率も成立する。

関連論文リスト

• An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue Optimization Problems [76.2042837251496]
  相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。 注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。 本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
  論文  参考訳（メタデータ） (2023-06-30T08:34:29Z)
• Gradient-free optimization of highly smooth functions: improved analysis and a new algorithm [87.22224691317766]
  この研究は、目的関数が極めて滑らかであるという仮定の下で、ゼロ次ノイズオラクル情報による問題を研究する。 ゼロオーダー射影勾配勾配アルゴリズムを2種類検討する。
  論文  参考訳（メタデータ） (2023-06-03T17:05:13Z)
• Stochastic Nonsmooth Convex Optimization with Heavy-Tailed Noises: High-Probability Bound, In-Expectation Rate and Initial Distance Adaptation [22.758674468435302]
  重尾雑音系では、勾配と真の速度の差は有限の$p-thモーメントを持つと仮定される。 本稿では,重み付き雑音を用いた非平滑凸最適化の包括的解析を行う。
  論文  参考訳（メタデータ） (2023-03-22T03:05:28Z)
• High Probability Convergence of Stochastic Gradient Methods [15.829413808059124]
  最適解への初期距離に依存する有界収束を示す。 AdaGrad-Normのハイバウンドが得られることを示す。
  論文  参考訳（メタデータ） (2023-02-28T18:42:11Z)
• Breaking the Lower Bound with (Little) Structure: Acceleration in Non-Convex Stochastic Optimization with Heavy-Tailed Noise [28.780192812703948]
  重み付き雑音状態において、滑らかだが必ずしも凸な目標を持つ最適化問題を考察する。 簡単な構造しか持たない低境界の$Omega(Tfrac1-p3p-2)$よりも高速な速度が得られることを示す。 また、軽度条件下では、高い確率収束率が$O(log(T/delta)Tfrac1-p3p-2)$であることを保証する。
  論文  参考訳（メタデータ） (2023-02-14T00:23:42Z)
• Beyond Uniform Smoothness: A Stopped Analysis of Adaptive SGD [38.221784575853796]
  この研究は、勾配を用いて潜在的に一定の滑らかさを持つ非アトー関数の1次定常点を求める問題を考える。 我々は、ノイズに一様境界を仮定することなく$mathcalO(fracmathrmpolylog(T)sigmatT)$収束率を証明できる技術を開発した。
  論文  参考訳（メタデータ） (2023-02-13T18:13:36Z)
• A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [53.044526424637866]
  本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。 特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
  論文  参考訳（メタデータ） (2023-01-10T20:43:29Z)
• ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
  本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。 我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2023-01-01T18:51:29Z)
• Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
  滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。 漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
  論文  参考訳（メタデータ） (2022-06-17T06:10:20Z)
• A first-order primal-dual method with adaptivity to local smoothness [64.62056765216386]
  凸凹対象 $min_x max_y f(x) + langle Ax, yrangle - g*(y)$, ここで、$f$ は局所リプシッツ勾配を持つ凸関数であり、$g$ は凸かつ非滑らかである。 主勾配ステップと2段ステップを交互に交互に行うCondat-Vuアルゴリズムの適応バージョンを提案する。
  論文  参考訳（メタデータ） (2021-10-28T14:19:30Z)

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

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