Fugu-MT 論文翻訳(概要): The Exact Time-Uniform Rate Frontier for Stochastic Gradient Descent on Smooth Convex Objectives

論文の概要: The Exact Time-Uniform Rate Frontier for Stochastic Gradient Descent on Smooth Convex Objectives

arxiv url: http://arxiv.org/abs/2609.08537v1
Date: Tue, 08 Sep 2026 10:24:19 GMT
ステータス: 翻訳完了
システム内更新日: 2026-09-10 19:44:08.628968
Title: The Exact Time-Uniform Rate Frontier for Stochastic Gradient Descent on Smooth Convex Objectives
Title（参考訳）: Smooth Convex Objectivesにおける確率勾配の時間的不均一速度フロンティア
Abstract要約: 本研究では、非拘束な滑らかな凸対象に対する標準降下勾配(SGD)の原繰り返しの時間一様収束について検討する。標準的な雑音仮定の下では、時間一様収束速度が$sqrtlog n / n$に任意に近づくが、それに到達することはないことを証明している。
参考スコア（独自算出の注目度）: 26.189892200366895
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We study the time-uniform convergence of the raw iterate of standard stochastic gradient descent (SGD) for unconstrained smooth convex objectives. We prove that, under standard noise assumptions, the time-uniform convergence rate gets arbitrarily close to $\sqrt{\log n / n}$ but never reaches it. More specifically, we prove that for every positive, eventually nondecreasing sequence $h$ satisfying $h(n) = o(\sqrt{n})$, a bound of order $h(n)/\sqrt{n}$, holding simultaneously for all $n$ with probability at least $1-α$ and uniformly over the problem class, is achievable if and only if \[ \sum_{j = 1}^{\infty} \frac{1}{h(2^j)^2} < \infty. \] The constructive sufficiency result follows from a dyadic horizon-free schedule together with an additive conditional-restart inequality. The necessity counterpart applies to every deterministic nonnegative schedule and holds even for a one-dimensional analytic smooth convex objective with Gaussian noise.
Abstract（参考訳）: 本研究では、非拘束な滑らかな凸対象に対する標準確率勾配勾配勾配(SGD)の原繰り返しの時間一様収束について検討する。標準的な雑音仮定の下では、時間一様収束率は$\sqrt{\log n / n}$に任意に近づくが、到達しない。より具体的には、すべての正の非増分列 $h$ が $h(n) = o(\sqrt{n})$ を満たすことを証明し、少なくとも 1-α$ の確率を持つすべての $n$ に対して同時に保持し、問題クラス上で一様となるようなすべての $h(n)/\sqrt{n}$ は、 \[ \sum_{j = 1}^{\infty} \frac{1}{h(2^j)^2} < \infty が達成可能であることを証明する。 \] 構成的十分性の結果は、追加条件の再起動不等式とともに、ダイアディックな水平自由スケジュールから従う。必要条件はすべての決定論的非負のスケジュールに適用され、ガウス雑音を伴う一次元解析的滑らかな凸対象に対しても成り立つ。

関連論文リスト

Clipped Gradient Methods for Nonsmooth Convex Optimization under Heavy-Tailed Noise: A Refined Analysis [3.8357180714081327]
単純だが効果的な操作である勾配クリッピングは、この新しい課題をうまく処理することが知られている。我々の研究は2つの面で既存のアプローチを改善している: 重尾雑音下でのクリップ誤りに対するフリードマンの不等式とより微細な境界のより良い利用である。この研究を補完するために、我々は高確率と非観測収束の両方のための新しい下界を確立する。
論文参考訳（メタデータ） (2025-12-29T03:35:53Z)
Fast Last-Iterate Convergence of SGD in the Smooth Interpolation Regime [26.711510824243803]
本研究では, 最適騒音が0または0に近い政権において, 円滑な凸目標に対する勾配降下(SGD)の集団収束保証について検討した。十分に調整されたステップサイズでは、最後の繰り返しに対してほぼ最適な$widetildeO (1/T + sigma_star/sqrtT)$レートを得る。
論文参考訳（メタデータ） (2025-07-15T12:52:47Z)
Nonconvex Stochastic Optimization under Heavy-Tailed Noises: Optimal Convergence without Gradient Clipping [21.865728815935665]
重み付き雑音下での最初の収束を提供するが、切断はしない。また、テールインデックス$mathfrakp$が事前に不明な場合には、最初の$mathcalO(Tfrac1-mathfrakp3mathfrakp-2)$収束率も設定する。
論文参考訳（メタデータ） (2024-12-27T08:46:46Z)
Anytime Acceleration of Gradient Descent [92.02082223856479]
エム収束保証による勾配勾配勾配の段階的加速度について検討する。滑らかな(強くない)凸最適化のために、任意の停止時間に対して、勾配降下が$O(T-1.119)$の収束保証を達成できる段階的なスケジュールを提案する。
論文参考訳（メタデータ） (2024-11-26T18:29:44Z)
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)
Breaking the Lower Bound with (Little) Structure: Acceleration in Non-Convex Stochastic Optimization with Heavy-Tailed Noise [28.780192812703948]
重み付き雑音状態において、滑らかだが必ずしも凸な目標を持つ最適化問題を考察する。簡単な構造しか持たない低境界の$Omega(Tfrac1-p3p-2)$よりも高速な速度が得られることを示す。また、軽度条件下では、高い確率収束率が$O(log(T/delta)Tfrac1-p3p-2)$であることを保証する。
論文参考訳（メタデータ） (2023-02-14T00:23:42Z)
Randomized Coordinate Subgradient Method for Nonsmooth Composite Optimization [11.017632675093628]
非滑らかな問題に対処するコーディネート型劣階法は、リプシッツ型仮定の性質のセットのため、比較的過小評価されている。
論文参考訳（メタデータ） (2022-06-30T02:17:11Z)
Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
論文参考訳（メタデータ） (2022-06-17T06:10:20Z)
High Probability Bounds for a Class of Nonconvex Algorithms with AdaGrad Stepsize [55.0090961425708]
本研究では,AdaGradのスムーズな非確率問題に対する簡易な高確率解析法を提案する。我々はモジュラーな方法で解析を行い、決定論的設定において相補的な$mathcal O (1 / TT)$収束率を得る。我々の知る限りでは、これは真に適応的なスキームを持つAdaGradにとって初めての高い確率である。
論文参考訳（メタデータ） (2022-04-06T13:50:33Z)
High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tails [55.561406656549686]
我々は、勾配推定が末尾を持つ可能性のある一階アルゴリズムを用いたヒルベルト非最適化を考える。本研究では, 勾配, 運動量, 正規化勾配勾配の収束を高確率臨界点に収束させることと, 円滑な損失に対する最もよく知られた繰り返しを示す。
論文参考訳（メタデータ） (2021-06-28T00:17:01Z)
Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction [63.41789556777387]
非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。 Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
論文参考訳（メタデータ） (2020-06-04T17:51:00Z)

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

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