論文の概要: Second-order Optimization under Heavy-Tailed Noise: Hessian Clipping and Sample Complexity Limits

• arxiv url: http://arxiv.org/abs/2510.10690v1
• Date: Sun, 12 Oct 2025 16:36:54 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-14 18:06:30.067038
• Title: Second-order Optimization under Heavy-Tailed Noise: Hessian Clipping and Sample Complexity Limits
• Title（参考訳）: 重音下での2次最適化:ヘッセン・クリッピングとサンプル複雑度限界
• Authors: Abdurakhmon Sadiev, Peter Richtárik, Ilyas Fatkhullin,
• Abstract要約: 重み付き雑音下での2階最適化の理論的理解に向けて第一歩を踏み出す。 勾配とヘッセン切断に基づく新しいアルゴリズムを導入し、基本限界にほぼ一致する高い確率上の境界を証明した。
• 参考スコア（独自算出の注目度）: 53.773695219320125
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Heavy-tailed noise is pervasive in modern machine learning applications, arising from data heterogeneity, outliers, and non-stationary stochastic environments. While second-order methods can significantly accelerate convergence in light-tailed or bounded-noise settings, such algorithms are often brittle and lack guarantees under heavy-tailed noise -- precisely the regimes where robustness is most critical. In this work, we take a first step toward a theoretical understanding of second-order optimization under heavy-tailed noise. We consider a setting where stochastic gradients and Hessians have only bounded $p$-th moments, for some $p\in (1,2]$, and establish tight lower bounds on the sample complexity of any second-order method. We then develop a variant of normalized stochastic gradient descent that leverages second-order information and provably matches these lower bounds. To address the instability caused by large deviations, we introduce a novel algorithm based on gradient and Hessian clipping, and prove high-probability upper bounds that nearly match the fundamental limits. Our results provide the first comprehensive sample complexity characterization for second-order optimization under heavy-tailed noise. This positions Hessian clipping as a robust and theoretically sound strategy for second-order algorithm design in heavy-tailed regimes.
• Abstract（参考訳）: ヘビーテールノイズは、データの不均一性、外れ値、非定常確率環境から生じる、現代の機械学習アプリケーションで広く使われている。 2階法は、光尾や有界ノイズの設定における収束を著しく加速するが、そのようなアルゴリズムはしばしば脆く、重尾ノイズ下での保証が欠如している。 本研究では,重み付き雑音下での2次最適化の理論的理解に向けて第一歩を踏み出す。 確率勾配と Hessian が、ある$p\in (1,2]$ に対して、わずか$p$-th のモーメントしか持たないような場合を考える。 次に、二階情報を利用した正規化確率勾配勾配の変種を開発し、これらの下界を確実に一致させる。 大きな偏差による不安定性に対処するために,勾配とヘッセン切断に基づく新しいアルゴリズムを導入し,基本的限界にほぼ一致する高い確率上界を証明した。 その結果,重み付き雑音下での2次最適化のための包括的サンプル複雑性評価法が得られた。 このことはヘシアン・クリッピングを重み付き状態における二階アルゴリズム設計の頑健で理論的に健全な戦略として位置づけている。

関連論文リスト

• Nonconvex Decentralized Stochastic Bilevel Optimization under Heavy-Tailed Noises [27.097405340259325]
  既存の分散最適化手法では、低レベル損失関数は強い凸であり、勾配ノイズは有限分散である。 これは、重み付き雑音の下で厳密な理論的保証を持つ最初の分散二レベルアルゴリズムである。
  論文  参考訳（メタデータ） (2025-09-19T02:51:19Z)
• 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)
• From Gradient Clipping to Normalization for Heavy Tailed SGD [19.369399536643773]
  最近の実証的な証拠は、機械学習の応用が重尾ノイズを伴い、実際に有界分散の標準的な仮定に挑戦していることを示している。 本稿では, 勾配依存型雑音収束問題において, テール雑音下での厳密性を実現することができることを示す。
  論文  参考訳（メタデータ） (2024-10-17T17:59:01Z)
• Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
  本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。 本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
  論文  参考訳（メタデータ） (2024-06-28T02:56:22Z)
• Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization Problems [56.86067111855056]
  構造密度の重み付き雑音によるクリップ最適化問題を考察する。 勾配が有限の順序モーメントを持つとき、$mathcalO(K-(alpha - 1)/alpha)$よりも高速な収束率が得られることを示す。 得られた推定値が無視可能なバイアスと制御可能な分散を持つことを示す。
  論文  参考訳（メタデータ） (2023-11-07T17:39:17Z)
• 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)

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

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