論文の概要: Revisiting AdaGrad in Stochastic Convex Optimization: Last Iterates, High Probability, and Lower Bounds

• arxiv url: http://arxiv.org/abs/2609.32729v1
• Date: Sat, 26 Sep 2026 15:48:40 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-06 20:56:25.72287
• Title: Revisiting AdaGrad in Stochastic Convex Optimization: Last Iterates, High Probability, and Lower Bounds
• Title（参考訳）: 確率凸最適化におけるAdaGradの再検討:最後のイテレーション、高い確率、低い境界
• Abstract要約: AdaGrad-Norm と AdaGrad はガウス以下の雑音や有界反復の下でも、普遍的テクスブフラスト定位率を認めないことを示す。 また、この$log T$損失は、有界条件が課されると消えることを示す。
• 参考スコア（独自算出の注目度）: 5.603202398374589
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: AdaGrad and AdaGrad-Norm are widely used adaptive methods, but their precise behavior in stochastic convex optimization remains less understood. We first show that AdaGrad-Norm and AdaGrad do not admit any universal \textbf{last-iterate} rate, even under sub-Gaussian noise and bounded iterates. We then prove that bounded variance alone is too weak: even with bounded iterates, it cannot yield \textbf{high-probability average-iterate} rates, and without bounded iterates it may not even guarantee convergence in expectation. Besides, we construct tight $Ω(\log T/\sqrt T)$ lower bounds for both AdaGrad-Norm and AdaGrad under sub-Gaussian noise, showing that $\log T$ in existing average-iterate upper bounds is unavoidable. Finally, we show that this $\log T$ loss disappears once bounded-iterate condition is imposed: under a general ABC condition, both methods achieve rates ${O}(1/\sqrt{T})$.
• Abstract（参考訳）: AdaGrad と AdaGrad-Norm は適応法として広く使われているが、確率凸最適化における正確な挙動はいまだ理解されていない。 最初に、AdaGrad-Norm と AdaGrad は、ガウス以下の雑音や有界反復の下でも、普遍的な \textbf{last-iterate} レートを認めないことを示す。 そして、有界な分散だけでは弱すぎることを証明する: 有界なイテレートであっても、それは \textbf{high-probability average-iterate} レートを得ることができず、有界なイテレートなしでは期待される収束を保証できない。 さらに、ガウス雑音下では、AdaGrad-Norm と AdaGrad の双方に対する厳密な$Ω(\log T/\sqrt T)$下界を構築し、既存の平均的上界における$\log T$は避けられないことを示す。 最後に、この$\log T$損失は、有界イテレート条件が課されると消滅することを示す:一般的なABC条件の下では、どちらの手法も${O}(1/\sqrt{T})$を達成する。

関連論文リスト

• Constrained Online Learning with Noisy Constraint Values [55.29259818039367]
  一般的な実現可能性の下では、我々のLEDGERアルゴリズムは、期待される損失$O(sqrt T)と期待される予算違反$O(sqrtTlog(eT))を達成します。 スレーター条件、フィードバックチャネル間の独立性、絶対的制約値境界は不要である。
  論文  参考訳（メタデータ） (2026-09-07T01:38:41Z)
• New Bounds for the Last Iterate of the Stochastic subGradient Method [11.179752660122281]
  本稿では,1次元凸リプシッツ目標に対する下段法の最後の繰り返しについて検討する。 最後の繰り返しは1/sqrt n$の順序の最適化誤差を特徴とする。 i.d.仮定がなければ、最適化誤差は位数 $(log n)/sqrt n$ となる。
  論文  参考訳（メタデータ） (2026-06-23T17:55:18Z)
• Optimal Dimension-Free Sampling for Regularized Classification [56.72526267755301]
  我々は、リプシッツ連続分類損失関数の幅広いクラスに対して、$(1pmvarepsilon)$-relativeエラーを達成する最適サンプリング境界を証明した。 これにはロジスティックやシグモイドの損失、ヒンジの損失、ReLUの損失といった重要な機能が含まれており、顕著で一般的な例である。
  論文  参考訳（メタデータ） (2026-05-22T15:05:33Z)
• Clipped Gradient Methods for Nonsmooth Convex Optimization under Heavy-Tailed Noise: A Refined Analysis [3.8357180714081327]
  単純だが効果的な操作である勾配クリッピングは、この新しい課題をうまく処理することが知られている。 我々の研究は2つの面で既存のアプローチを改善している: 重尾雑音下でのクリップ誤りに対するフリードマンの不等式とより微細な境界のより良い利用である。 この研究を補完するために、我々は高確率と非観測収束の両方のための新しい下界を確立する。
  論文  参考訳（メタデータ） (2025-12-29T03:35:53Z)
• Sign Operator for Coping with Heavy-Tailed Noise in Non-Convex Optimization: High Probability Bounds Under $(L_0, L_1)$-Smoothness [74.18546828528298]
  SignSGD with Majority Votingは,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappaka ppakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa -1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappappapa-1right,Kappaを用いて,複雑性の全範囲で堅牢に動作することを示す。
  論文  参考訳（メタデータ） (2025-02-11T19:54:11Z)
• Revisiting the Last-Iterate Convergence of Stochastic Gradient Methods [25.831462008050387]
  グラディエント・Descent(SGD)アルゴリズムは、実際の性能が良く、理論的な理解が欠如していることから、人々の関心を喚起している。 有限収束がより広い合成最適化や非ユークリッドノルムに証明可能な拡張が可能かどうかはまだ不明である。
  論文  参考訳（メタデータ） (2023-12-13T21:41:06Z)
• High Probability Convergence of Stochastic Gradient Methods [15.829413808059124]
  最適解への初期距離に依存する有界収束を示す。 AdaGrad-Normのハイバウンドが得られることを示す。
  論文  参考訳（メタデータ） (2023-02-28T18:42:11Z)
• 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)
• 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)
• Tight Regret Bounds for Noisy Optimization of a Brownian Motion [118.65407541895851]
  本稿では,1次元ブラウン運動のベイズ最適化の問題点について考察する。 Omega(sigmasqrtT cdot log T)$.sigmasqrtT cdot log T)$.sigmasqrtT.sigmasqrtT.sigmasqrtT cdot log T)$.sigmasqrtT.sigmasqrtT.sigmasqrtT.sigmasqrtT.sigmasqrtT.sigmasqrtT.sigmasqrtT.sigmasqrtT.
  論文  参考訳（メタデータ） (2020-01-25T14:44:53Z)

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

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