論文の概要: High Probability Convergence of Stochastic Gradient Methods
- arxiv url: http://arxiv.org/abs/2302.14843v1
- Date: Tue, 28 Feb 2023 18:42:11 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-01 14:53:33.080308
- Title: High Probability Convergence of Stochastic Gradient Methods
- Title（参考訳）: 確率勾配法の高確率収束
- Authors: Zijian Liu, Ta Duy Nguyen, Thien Hang Nguyen, Alina Ene, Huy L\^e
Nguyen
- Abstract要約: 最適解への初期距離に依存する有界収束を示す。
AdaGrad-Normのハイバウンドが得られることを示す。
- 参考スコア（独自算出の注目度）: 15.829413808059124
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this work, we describe a generic approach to show convergence with high
probability for both stochastic convex and non-convex optimization with
sub-Gaussian noise. In previous works for convex optimization, either the
convergence is only in expectation or the bound depends on the diameter of the
domain. Instead, we show high probability convergence with bounds depending on
the initial distance to the optimal solution. The algorithms use step sizes
analogous to the standard settings and are universal to Lipschitz functions,
smooth functions, and their linear combinations. This method can be applied to
the non-convex case. We demonstrate an
$O((1+\sigma^{2}\log(1/\delta))/T+\sigma/\sqrt{T})$ convergence rate when the
number of iterations $T$ is known and an
$O((1+\sigma^{2}\log(T/\delta))/\sqrt{T})$ convergence rate when $T$ is unknown
for SGD, where $1-\delta$ is the desired success probability. These bounds
improve over existing bounds in the literature. Additionally, we demonstrate
that our techniques can be used to obtain high probability bound for
AdaGrad-Norm (Ward et al., 2019) that removes the bounded gradients assumption
from previous works. Furthermore, our technique for AdaGrad-Norm extends to the
standard per-coordinate AdaGrad algorithm (Duchi et al., 2011), providing the
first noise-adapted high probability convergence for AdaGrad.
- Abstract（参考訳）: 本研究では,ガウス雑音による確率凸と非凸最適化の両方の確率の高い収束を示す一般的な手法について述べる。
凸最適化に関する以前の研究では、収束は期待値のみであり、境界は領域の直径に依存する。
代わりに、最適解への初期距離に依存して有界な高確率収束を示す。
アルゴリズムは標準設定に類似したステップサイズを使用し、リプシッツ関数や滑らかな関数、それらの線形結合に普遍的である。
この方法は非凸の場合に適用できる。
sgdでは$t$が未知である場合には$o((1+\sigma^{2}\log(1/\delta))/t+\sigma/\sqrt{t})$収束率を示し、1-\delta$が望ましい成功確率であるsgdでは$t$が未知である場合、$o((1+\sigma^{2}\log(t/\delta))/\sqrt{t})$収束率を示す。
これらの境界は、文献の既存の境界よりも改善される。
さらに,本手法は,前の研究から境界勾配の仮定を取り除いたアダグラードノルム (ward et al., 2019) に対する高い確率バウンドが得られることを示す。
さらに、AdaGrad-Norm の手法は、標準のコーディネート AdaGrad アルゴリズム (Duchi et al., 2011) にまで拡張され、AdaGrad に対する最初の雑音適応高確率収束を提供する。
関連論文リスト
- Revisiting the Last-Iterate Convergence of Stochastic Gradient Methods [25.831462008050387]
グラディエント・Descent(SGD)アルゴリズムは、実際の性能が良く、理論的な理解が欠如していることから、人々の関心を喚起している。
有限収束がより広い合成最適化や非ユークリッドノルムに証明可能な拡張が可能かどうかはまだ不明である。
論文 参考訳（メタデータ） (2023-12-13T21:41:06Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - Convergence of a Normal Map-based Prox-SGD Method under the KL
Inequality [0.0]
我々は、$symbol$k$収束問題に対して、新しいマップベースのアルゴリズム(mathsfnorMtext-mathsfSGD$)を提案する。
論文 参考訳（メタデータ） (2023-05-10T01:12:11Z) - 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) - Beyond Uniform Smoothness: A Stopped Analysis of Adaptive SGD [38.221784575853796]
この研究は、勾配を用いて潜在的に一定の滑らかさを持つ非アトー関数の1次定常点を求める問題を考える。
我々は、ノイズに一様境界を仮定することなく$mathcalO(fracmathrmpolylog(T)sigmatT)$収束率を証明できる技術を開発した。
論文 参考訳（メタデータ） (2023-02-13T18:13:36Z) - 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) - A first-order primal-dual method with adaptivity to local smoothness [64.62056765216386]
凸凹対象 $min_x max_y f(x) + langle Ax, yrangle - g*(y)$, ここで、$f$ は局所リプシッツ勾配を持つ凸関数であり、$g$ は凸かつ非滑らかである。
主勾配ステップと2段ステップを交互に交互に行うCondat-Vuアルゴリズムの適応バージョンを提案する。
論文 参考訳（メタデータ） (2021-10-28T14:19:30Z) - Accelerating Optimization and Reinforcement Learning with
Quasi-Stochastic Approximation [2.294014185517203]
本稿では、収束理論を準確率近似に拡張することを目的とする。
強化学習のためのグラデーションフリー最適化とポリシー勾配アルゴリズムへの応用について説明する。
論文 参考訳（メタデータ） (2020-09-30T04:44:45Z) - On the Almost Sure Convergence of Stochastic Gradient Descent in
Non-Convex Problems [75.58134963501094]
本稿では,勾配降下(SGD)の軌跡を解析する。
我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
論文 参考訳（メタデータ） (2020-06-19T14:11:26Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。