論文の概要: Exact Theory and Optimal Stepsizes for Stochastic Gradient Descent in Smooth Convex Minimization
- arxiv url: http://arxiv.org/abs/2610.42048v1
- Date: Fri, 30 Oct 2026 17:14:59 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-11-02 22:05:31.826266
- Title: Exact Theory and Optimal Stepsizes for Stochastic Gradient Descent in Smooth Convex Minimization
- Title(参考訳): Smooth Convex Minimizationにおける確率的グラディエントDescenceのエクササイズ理論と最適ステップサイズ
- Abstract要約: 本研究は,滑らかな凸最適化における勾配降下のための段差スケジュールの設計について考察する。
我々は,勾配降下の最終反復の予測下最適性について,正確な最悪のケース解析を行う。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This work considers the design of stepsize schedules for stochastic gradient descent in smooth convex optimization. Throughout, we assume that gradient noise is conditionally zero-mean with bounded variance. Among problems with dimension $d\geq N+1$, we provide an exact worst-case analysis of the expected suboptimality of stochastic gradient descent's final iterate. Our analysis applies to any (potentially nonconstant) schedule of $N$ stepsizes in $[0,1.5]^N$. Here, exact means that we provide a matching objective function and noise distributions where our guarantee is attained. Whenever the variance bound is at least $Ω(1/\sqrt{N})$, our theory provides the minimax optimal stepsize schedule for stochastic gradient descent and proves its uniqueness. These optimal stepsizes monotonically decrease, ruling out any accelerations in expected final suboptimality from fixed fractal schedules observed in the deterministic case.
- Abstract(参考訳): 本研究は,滑らかな凸最適化における確率勾配降下のための段差スケジュールの設計について考察する。
全体を通して、勾配ノイズは有界な分散を持つ条件付きゼロ平均であると仮定する。
次元が $d\geq N+1$ である問題のうち、確率勾配勾配の最終的な反復の予測準最適性の正確な最悪のケース解析を提供する。
我々の分析は、$[0,1.5]^N$の任意の(潜在的に非定常な)スケジュールに適用される。
ここでは、正確なことは、我々の保証が達成された目標関数と雑音分布が一致することを意味する。
分散境界が少なくとも$Ω(1/\sqrt{N})$であるとき、我々の理論は確率勾配勾配の最小極大ステップ化スケジュールを提供し、その特異性を証明する。
これらの最適ステップは単調に減少し、決定論的ケースで観測される固定されたフラクタルスケジュールから期待される最終最適値の加速度を除外する。
関連論文リスト
- Optimal Algorithms for Nonsmooth Nonconvex Stochastic Optimization with Constraints [8.966143663102798]
凸制約セットを対象とし,目的が滑らかでも凸でもない最適化問題に対する新しいアルゴリズムを提案する。
我々の分析は、制約のない最適化から関連する手法であるオンライン複雑性最適化への還元に基づく。
論文 参考訳(メタデータ) (2026-10-09T16:04:13Z) - Differential Private Stochastic Optimization with Heavy-tailed Data: Towards Optimal Rates [15.27596975662702]
重み付き勾配を用いたDP最適化の最適速度を達成するアルゴリズムについて検討する。
その結果,DP下での凸最適化の理論的限界が達成可能であることを示す。
論文 参考訳(メタデータ) (2024-08-19T11:07:05Z) - Provable Complexity Improvement of AdaGrad over SGD: Upper and Lower Bounds in Stochastic Non-Convex Optimization [18.47705532817026]
適応勾配法は、最も成功したニューラルネットワークトレーニングアルゴリズムの一つである。
これらの手法は凸SGD-ノルマリティよりも次元依存性が優れていることが知られている。
本稿では,構造物の滑らかさと勾配雑音の分散に関する新しい仮定を紹介する。
論文 参考訳(メタデータ) (2024-06-07T02:55:57Z) - Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization Problems [56.86067111855056]
構造密度の重み付き雑音によるクリップ最適化問題を考察する。
勾配が有限の順序モーメントを持つとき、$mathcalO(K-(alpha - 1)/alpha)$よりも高速な収束率が得られることを示す。
得られた推定値が無視可能なバイアスと制御可能な分散を持つことを示す。
論文 参考訳(メタデータ) (2023-11-07T17:39:17Z) - Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。
漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
論文 参考訳(メタデータ) (2022-06-17T06:10:20Z) - Improved Convergence Rate of Stochastic Gradient Langevin Dynamics with
Variance Reduction and its Application to Optimization [50.83356836818667]
勾配ランゲヴィン・ダイナミクスは非エプス最適化問題を解くための最も基本的なアルゴリズムの1つである。
本稿では、このタイプの2つの変種、すなわち、分散還元ランジュバンダイナミクスと再帰勾配ランジュバンダイナミクスを示す。
論文 参考訳(メタデータ) (2022-03-30T11:39:00Z) - Towards Noise-adaptive, Problem-adaptive Stochastic Gradient Descent [7.176107039687231]
雑音に対して勾配降下(SGD)を適応させるステップサイズスキームを設計する。
我々は、Nesterov反復によるSGDの$T$反復がほぼ最適であることを示す。
他のステップサイズスキームと比較して、新しい指数的なステップサイズスキームの有効性を実証する。
論文 参考訳(メタデータ) (2021-10-21T19:22:14Z) - High-probability Bounds for Non-Convex Stochastic Optimization with
Heavy Tails [55.561406656549686]
我々は、勾配推定が末尾を持つ可能性のある一階アルゴリズムを用いたヒルベルト非最適化を考える。
本研究では, 勾配, 運動量, 正規化勾配勾配の収束を高確率臨界点に収束させることと, 円滑な損失に対する最もよく知られた繰り返しを示す。
論文 参考訳(メタデータ) (2021-06-28T00:17:01Z) - Stochastic Bias-Reduced Gradient Methods [44.35885731095432]
モロー・吉田関数の任意の有界な$x_star$の低バイアスで低コストな平滑化である。
論文 参考訳(メタデータ) (2021-06-17T13:33:05Z) - Balancing Rates and Variance via Adaptive Batch-Size for Stochastic
Optimization Problems [120.21685755278509]
本研究は,ステップサイズの減衰が正確な収束に必要であるという事実と,一定のステップサイズがエラーまでの時間でより速く学習するという事実のバランスをとることを目的とする。
ステップサイズのミニバッチを最初から修正するのではなく,パラメータを適応的に進化させることを提案する。
論文 参考訳(メタデータ) (2020-07-02T16:02:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。