論文の概要: A Tight Lower Bound for Smooth Nonconvex Stochastic Optimization with Bounded Gradient Noise
- arxiv url: http://arxiv.org/abs/2608.09004v1
- Date: Mon, 10 Aug 2026 01:45:56 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-11 19:16:37.033647
- Title: A Tight Lower Bound for Smooth Nonconvex Stochastic Optimization with Bounded Gradient Noise
- Title（参考訳）: 境界勾配雑音を用いた平滑な非凸確率最適化のための高次下界
- Authors: Jikai Jin,
- Abstract要約: 勾配雑音を考慮したスムーズな非適応最適化のためのシャープな下界を証明した。
これは標準上界と一致し、[Arvani et al.] によって提起された、ほぼ確実に有界なオラクル誤差が有界な分散よりも優れているかどうかの問題を解く。
- 参考スコア（独自算出の注目度）: 7.7753818665096945
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: We prove a sharp lower bound for smooth nonconvex stochastic optimization with uniformly bounded gradient noise. In the \(K=1\) fresh-sample model, every randomized adaptive algorithm requires $$Ω\left( \frac{ΔL}{ε^2} + \frac{ΔLσ^2}{ε^4} \right)$$ queries to find a point with expected gradient norm at most \(ε\). This matches the standard upper bound and, to the best of our knowledge, resolves the question raised by [Arjevani et al. 2023] of whether almost-surely bounded oracle error permits a better rate than bounded variance. The proof was independently generated with GPT-5.6 Sol in Codex's Ultra mode during a two-hour session. The human author supplied the prompt and was responsible only forchecking the proof and revising and polishing the manuscript.
- Abstract（参考訳）: 均一な勾配雑音を持つ滑らかな非凸確率最適化のためのシャープな下界を証明した。
K=1\) 新サンプルモデルでは、任意のランダム化適応アルゴリズムは$$$Ω\left( \frac{ΔL}{ε^2} + \frac{ΔLσ^2}{ε^4} \right)$$クエリを必要とする。
これは標準上界と一致し、我々の知る限りでは、[Arjevani et al 2023] によって提起された、ほぼ確実に有界なオラクル誤差が有界な分散よりも良いレートを許すかどうかという問題を解決する。
この証明は、2時間のセッションでコーデックスのウルトラモードの GPT-5.6 Sol で独立に生成された。
人間の著者はプロンプトを供給し、証明の確認と改訂と原稿の研磨のみを担当した。
関連論文リスト
- Noise-Adaptive High-Probability Regret Bounds for Online Convex Optimization [12.903796669387809]
オンライン凸最適化 (OCO) における高い確率的後悔境界について, 強い凸損失を伴って検討した。
雑音適応性, フィードバック構造, 制約満足度の交点において, オープンな質問を解決するための3つの結果を確立する。
論文 参考訳（メタデータ） (2026-06-06T07:40:55Z) - 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) - Lower Bounds and Proximally Anchored SGD for Non-Convex Minimization Under Unbounded Variance [7.788141970705731]
勾配解析とその変種におけるBlum-Glady Oracle (Amax-0) 条件の弱さに対処する。
これらの下界に合わせるために、スムーズな勾配に対する統一的なアルゴリズムフレームワークであるProllyxima Anchor (ASTA) を考える。
論文 参考訳（メタデータ） (2026-04-17T18:15:51Z) - High-accuracy log-concave sampling with stochastic queries [70.90863485771405]
サブエクスフォデンシャルテールの繰り返し勾配を用いて,ログコンケーブサンプリングの精度保証が達成可能であることを示す。
また、このフレームワークは、0番目の順序(値)クエリの下でも、同様の高精度な保証を提供する。
論文 参考訳（メタデータ） (2026-02-15T23:19:07Z) - Revisiting the Last-Iterate Convergence of Stochastic Gradient Methods [25.831462008050387]
グラディエント・Descent(SGD)アルゴリズムは、実際の性能が良く、理論的な理解が欠如していることから、人々の関心を喚起している。
有限収束がより広い合成最適化や非ユークリッドノルムに証明可能な拡張が可能かどうかはまだ不明である。
論文 参考訳（メタデータ） (2023-12-13T21:41:06Z) - Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization Problems [56.86067111855056]
構造密度の重み付き雑音によるクリップ最適化問題を考察する。
勾配が有限の順序モーメントを持つとき、$mathcalO(K-(alpha - 1)/alpha)$よりも高速な収束率が得られることを示す。
得られた推定値が無視可能なバイアスと制御可能な分散を持つことを示す。
論文 参考訳（メタデータ） (2023-11-07T17:39:17Z) - Closing the Gap Between the Upper Bound and the Lower Bound of Adam's
Iteration Complexity [51.96093077151991]
我々はAdamの新しい収束保証を導出し、$L$-smooth条件と有界雑音分散仮定のみを導出する。
本証明は,運動量と適応学習率の絡み合いを扱うために,新しい手法を利用する。
論文 参考訳（メタデータ） (2023-10-27T09:16:58Z) - 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 Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization [112.59170319105971]
問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。
MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
論文 参考訳（メタデータ） (2021-02-15T07:10:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。