論文の概要: Lower Bounds and Proximally Anchored SGD for Non-Convex Minimization Under Unbounded Variance

• arxiv url: http://arxiv.org/abs/2604.16620v1
• Date: Fri, 17 Apr 2026 18:15:51 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-21 21:52:52.108505
• Title: Lower Bounds and Proximally Anchored SGD for Non-Convex Minimization Under Unbounded Variance
• Title（参考訳）: 非有界変動下における非凸最小化のための下界および近近距離SGD
• Authors: Arda Fazla, Ege C. Kaya, Antesh Upadhyay, Abolfazl Hashemi,
• Abstract要約: 勾配解析とその変種におけるBlum-Glady Oracle (Amax-0) 条件の弱さに対処する。 これらの下界に合わせるために、スムーズな勾配に対する統一的なアルゴリズムフレームワークであるProllyxima Anchor (ASTA) を考える。
• 参考スコア（独自算出の注目度）: 7.788141970705731
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Analysis of Stochastic Gradient Descent (SGD) and its variants typically relies on the assumption of uniformly bounded variance, a condition that frequently fails in practical non-convex settings, such as neural network training, as well as in several elementary optimization settings. While several relaxations are explored in the literature, the Blum-Gladyshev (BG-0) condition, which permits the variance to grow quadratically with distance has recently been shown to be the weakest condition. However, the study of the oracle complexity of stochastic first-order non-convex optimization under BG-0 has remained underexplored. In this paper, we address this gap and establish information-theoretic lower bounds, proving that finding an $ε$-stationary point requires $Ω(ε^{-6})$ stochastic BG-0 oracle queries for smooth functions and $Ω(ε^{-4})$ queries under mean-square smoothness. These limits demonstrate an unavoidable degradation from classical bounded-variance complexities, i.e., $Ω(ε^{-4})$ and $Ω(ε^{-3})$ for smooth and mean-square smooth cases, respectively. To match these lower bounds, we consider Proximally Anchored STochastic Approximation (PASTA), a unified algorithmic framework that couples Halpern anchoring with Tikhonov regularization to dynamically mitigate the extra variance explosion term permitted by the BG-0 oracle. We prove that PASTA achieves minimax optimal complexities across numerous non-convex regimes, including standard smooth, mean-square smooth, weakly convex, star-convex, and Polyak-Lojasiewicz functions, entirely under an unbounded domain and unbounded stochastic gradients.
• Abstract（参考訳）: Stochastic Gradient Descent (SGD) とその変種の解析は、通常、一様有界分散(英語版)という仮定に依存している。 文献中ではいくつかの緩和が検討されているが、近距離で四角形に成長するBlum-Gladyshev (BG-0) 条件は、最近最も弱い状態であることが示されている。 しかし、BG-0の下での確率的一階非凸最適化のオラクル複雑性の研究はいまだ未解明のままである。 本稿では,このギャップに対処し,ε$-定常点を見つけるためには,滑らかな関数に対する確率的BG-0オラクルクエリと平均2乗滑らかさの下での$Ω(ε^{-4})$クエリが必要であることを証明し,情報理論の下界を確立する。 これらの極限は古典的有界分散複素数、すなわち、滑らかかつ平均二乗の滑らかなケースに対して、$Ω(ε^{-4})$と$Ω(ε^{-3})$から避けられない分解を示す。 これらの下限を満たすために、我々は、BG-0オラクルが許容する余剰分散爆発項を動的に緩和するために、ハルペルンをチコノフ正規化に固定する統一アルゴリズムフレームワークであるPASTA(Proximally Anchored STochastic Approximation)を検討する。 PASTA は、標準滑らか、平均二乗滑らか、弱凸、星凸、ポリャク・ロジャシエヴィチ関数を含む多くの非凸系において、非有界領域と非有界確率勾配の下で極小最大複素数を達成することを証明した。

関連論文リスト

• Can SGD Handle Heavy-Tailed Noise? [6.111519084375339]
  Gradient Descent (SGD) は大規模最適化のための機械学習プロジェクトであるが、重尾雑音下での理論的挙動は理解されていない。 このような悪条件下でSGDが確実に成功できるかどうかを精査する。
  論文  参考訳（メタデータ） (2025-08-06T20:09:41Z)
• Provable Complexity Improvement of AdaGrad over SGD: Upper and Lower Bounds in Stochastic Non-Convex Optimization [18.47705532817026]
  適応勾配法は、最も成功したニューラルネットワークトレーニングアルゴリズムの一つである。 これらの手法は凸SGD-ノルマリティよりも次元依存性が優れていることが知られている。 本稿では,構造物の滑らかさと勾配雑音の分散に関する新しい仮定を紹介する。
  論文  参考訳（メタデータ） (2024-06-07T02:55:57Z)
• A Unified Analysis on the Subgradient Upper Bounds for the Subgradient Methods Minimizing Composite Nonconvex, Nonsmooth and Non-Lipschitz Functions [7.972544890243396]
  本稿では, 近位降下法(Prox-SubGrad) 型アプローチの統一解析について述べる。 我々は, 誤差有界条件, 対象の下位次数の成長条件, および主次次次次次次数反復の挙動を, 極めて広い目的関数のクラスに関連付けることができる。
  論文  参考訳（メタデータ） (2023-08-30T23:34:11Z)
• Convex and Non-convex Optimization Under Generalized Smoothness [69.69521650503431]
  凸法と非最適化法の分析は、しばしばリプシッツ勾配を必要とし、この軌道による解析を制限する。 最近の研究は、非一様滑らか性条件を通した勾配設定を一般化している。
  論文  参考訳（メタデータ） (2023-06-02T04:21:59Z)
• Projective Proximal Gradient Descent for A Class of Nonconvex Nonsmooth Optimization Problems: Fast Convergence Without Kurdyka-Lojasiewicz (KL) Property [19.988762532185884]
  非滑らかな最適化問題は、学習にとって重要かつ困難である。 本稿では,PSGDの高速収束を示す新しい解析法について述べる。
  論文  参考訳（メタデータ） (2023-04-20T17:39:24Z)
• High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance [59.211456992422136]
  制約の少ない仮定の下で高確率収束結果のアルゴリズムを提案する。 これらの結果は、標準機能クラスに適合しない問題を最適化するために検討された手法の使用を正当化する。
  論文  参考訳（メタデータ） (2023-02-02T10:37:23Z)
• Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation Constrained Optimization [88.0031283949404]
  多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。 提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
  論文  参考訳（メタデータ） (2022-12-19T14:48:54Z)
• Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyond [63.59034509960994]
  シャッフルに基づく変種(ミニバッチと局所ランダムリシャッフル)について検討する。 ポリアック・ロジャシエヴィチ条件を満たす滑らかな函数に対して、これらのシャッフル型不変量(英語版)(shuffling-based variants)がそれらの置換式よりも早く収束することを示す収束境界を得る。 我々は, 同期シャッフル法と呼ばれるアルゴリズムの修正を提案し, ほぼ均一な条件下では, 下界よりも収束速度が速くなった。
  論文  参考訳（メタデータ） (2021-10-20T02:25:25Z)
• Unified Convergence Analysis for Adaptive Optimization with Moving Average Estimator [75.05106948314956]
  1次モーメントに対する大きな運動量パラメータの増大は適応的スケーリングに十分であることを示す。 また,段階的に減少するステップサイズに応じて,段階的に運動量を増加させるための洞察を与える。
  論文  参考訳（メタデータ） (2021-04-30T08:50:24Z)
• SGD for Structured Nonconvex Functions: Learning Rates, Minibatching and Interpolation [17.199023009789308]
  予想されるSGD(SGD)の仮定は、非アーティザン関数に対して日常的に使われている。 本稿では,スムーズな非線形設定への収束のパラダイムを示す。 また,異なるステップサイズ条件の理論的保証も提供する。
  論文  参考訳（メタデータ） (2020-06-18T07:05:56Z)

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

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