論文の概要: Ordinary Nonconvex SGD under Distance-Dependent Moments: Finite-Horizon Stationarity and Nagaev Bounds
- arxiv url: http://arxiv.org/abs/2609.30499v1
- Date: Thu, 24 Sep 2026 19:37:07 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-28 18:27:51.122411
- Title: Ordinary Nonconvex SGD under Distance-Dependent Moments: Finite-Horizon Stationarity and Nagaev Bounds
- Title（参考訳）: 距離依存モーメント下における通常の非凸SGD:有限-水平定常および長エフ境界
- Abstract要約: 一様雑音-モーメンタリティ境界は、距離によって変動が増加する勾配を除外する。
直接降下すると、スムーズな転位引数が3エプシロン6$を回復する。
局所化半径は、非レート仮定、クリッピング正規化、運動量、バッチサイズの増加といった境界から導かれる。
- 参考スコア（独自算出の注目度）: 1.6582968942719265
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Uniform noise-moment bounds exclude stochastic gradients whose variability increases with the iterate. We study ordinary, single-sample stochastic gradient descent for smooth, lower-bounded, possibly nonconvex objectives under distance-dependent conditional moments. Under second moments alone, a direct descent--displacement argument yields $T^{-1/3}$ expected average squared-gradient stationarity with a horizon-dependent stepsize. An explicit oracle-complexity corollary matches the known smooth Blum--Gladyshev (BG-0) lower bound, including the $Lb_2Δ^3\varepsilon^{-6}$ and $LΔσ^2\varepsilon^{-4}$ stochastic terms, where $Δ$ is the initial objective gap and $σ^2+b_2\|x-x_1\|^2$ bounds the variance. Thus unchanged SGD attains the minimax stochastic complexity in this second-moment class. For $p>2$, predictable localization and a Hilbert-space Fuk--Nagaev inequality yield a high-probability bound separating logarithmic variance and polynomial rare-shock contributions. The localization radius is derived from the recursion: no bounded-iterate assumption, clipping, normalization, momentum, or increasing batch size is needed. We also give increasing-confidence rates, an objective-gap-growth refinement recovering root-$T$ stationarity, and stochastic $L^p$-Lipschitz examples. The broad BG-0 optimality statement is distinguished from the smaller mean-square-smooth class, in which additional oracle structure permits faster algorithms.
- Abstract（参考訳）: 一様ノイズモーメント境界は、反復によって変動が増加する確率勾配を除外する。
距離依存的条件付モーメント下で, 平滑で低境界, 非凸な目的に対して, 通常の, 単サンプル確率勾配勾配について検討した。
第2の瞬間だけで、直接降下変位論は、地平線依存のステップサイズを持つ平均2次定常性(英語版)を期待して$T^{-1/3} を得る。
Lb_2Δ^3\varepsilon^{-6}$と$LΔσ^2\varepsilon^{-4}$の確率項、$Δ$は初期目的ギャップ、$σ^2+b_2\|x-x_1\|^2$は分散を有界とする。
したがって、SGD は第二モーメントクラスにおいてミニマックス確率複雑性を得る。
p>2$ の場合、予測可能なローカライゼーションとヒルベルト空間のフク=ナガエフ不等式は、対数分散と多項式レアショックの寄与を分離する高確率有界な有界な値を与える。
局所化半径は再帰から導かれる: 有界イテレート仮定、クリッピング、正規化、運動量、バッチサイズの増加は不要である。
また,信頼度の増加,ルート=T$固定率の回復,および確率$L^p$-Lipschitz例を示す。
広義のBG-0最適性ステートメントは、より高速なアルゴリズムを許容する、より小さな平均2乗スムースクラスと区別される。
関連論文リスト
- Is Spurious Correlation Removal Always Learnable? [56.28155520961125]
不変学習は、構造が統計的に識別可能であっても失敗することがある。
ブラックボックスサンプリング可能な教師付きスパースリカバリプリミティブの下では、実証可能な多次元環境が存在する。
合成および実際のデータセットは、予測されたギャップと遷移を示し、単純な多様性診断を動機付ける。
論文 参考訳（メタデータ） (2026-06-11T05:49:43Z) - Optimal Dimension-Free Sampling for Regularized Classification [56.72526267755301]
我々は、リプシッツ連続分類損失関数の幅広いクラスに対して、$(1pmvarepsilon)$-relativeエラーを達成する最適サンプリング境界を証明した。
これにはロジスティックやシグモイドの損失、ヒンジの損失、ReLUの損失といった重要な機能が含まれており、顕著で一般的な例である。
論文 参考訳（メタデータ） (2026-05-22T15:05:33Z) - Beyond Bounded Variance: Variance-Reduced Normalized Methods for Nonconvex Optimization under Blum-Gladyshev Noise [7.692336118507715]
我々は,Blum-Gladyshev(mathsfBG$-0)ノイズモデルの下での非線形最適化について検討した。
モーメント付き正規化勾配降下は、勾配毎のパラメータを1つだけ使い、複雑さが$O(varepsilon-6)$で$mathsfBG$-0ノイズの下に収束することを示す。
論文 参考訳（メタデータ） (2026-05-14T18:27:49Z) - Towards Scalable Persistence-Based Topological Optimization [44.16669776030478]
永続性に基づく位相最適化は、点クラウド $X の部分集合 mathbbRd$ を $L(X) = ell(mathrmDgm(X))$ という形の目的を最小化することによって変形する。
実際、最適化は2つの結合した問題によって制限される: 永続ホモロジーは典型的にはサブサンプル上で計算され、結果として生じる位相勾配は非常にスパースであり、非ゼロ更新を受けるアンカーポイントはわずかである。
論文 参考訳（メタデータ） (2026-05-09T15:47:20Z) - When Does $\ell_2$-Boosting Overfit Benignly? High-Dimensional Risk Asymptotics and the $\ell_1$ Implicit Bias [15.113649527486276]
良性オーバーフィッティングが線形レートで失敗することを示します。
この局所化機構は信号の存在下で持続するべきであるが、正確な信号-雑音分解は未解決の問題である。
論文 参考訳（メタデータ） (2026-05-07T14:14:09Z) - Can SGD Handle Heavy-Tailed Noise? [6.111519084375339]
Gradient Descent (SGD) は大規模最適化のための機械学習プロジェクトであるが、重尾雑音下での理論的挙動は理解されていない。
このような悪条件下でSGDが確実に成功できるかどうかを精査する。
論文 参考訳（メタデータ） (2025-08-06T20:09:41Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。
漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
論文 参考訳（メタデータ） (2022-06-17T06:10:20Z) - Faster Convergence of Stochastic Gradient Langevin Dynamics for
Non-Log-Concave Sampling [110.88857917726276]
我々は,非log-concaveとなる分布のクラスからサンプリングするために,勾配ランゲヴィンダイナミクス(SGLD)の新たな収束解析を行う。
我々のアプローチの核心は、補助的時間反転型マルコフ連鎖を用いたSGLDのコンダクタンス解析である。
論文 参考訳（メタデータ） (2020-10-19T15:23:18Z) - A Simple Convergence Proof of Adam and Adagrad [74.24716715922759]
我々はAdam Adagradと$O(d(N)/st)$アルゴリズムの収束の証明を示す。
Adamはデフォルトパラメータで使用する場合と同じ収束$O(d(N)/st)$で収束する。
論文 参考訳（メタデータ） (2020-03-05T01:56:17Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。