論文の概要: High Probability Bounds for a Class of Nonconvex Algorithms with AdaGrad Stepsize

• arxiv url: http://arxiv.org/abs/2204.02833v1
• Date: Wed, 6 Apr 2022 13:50:33 GMT
• ステータス: 処理完了
• システム内更新日: 2022-04-07 15:31:18.273830
• Title: High Probability Bounds for a Class of Nonconvex Algorithms with AdaGrad Stepsize
• Title（参考訳）: AdaGrad ステップサイズをもつ非凸アルゴリズムの高確率境界
• Authors: Ali Kavis, Kfir Yehuda Levy, Volkan Cevher
• Abstract要約: 本研究では,AdaGradのスムーズな非確率問題に対する簡易な高確率解析法を提案する。 我々はモジュラーな方法で解析を行い、決定論的設定において相補的な$mathcal O (1 / TT)$収束率を得る。 我々の知る限りでは、これは真に適応的なスキームを持つAdaGradにとって初めての高い確率である。
• 参考スコア（独自算出の注目度）: 55.0090961425708
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we propose a new, simplified high probability analysis of AdaGrad for smooth, non-convex problems. More specifically, we focus on a particular accelerated gradient (AGD) template (Lan, 2020), through which we recover the original AdaGrad and its variant with averaging, and prove a convergence rate of $\mathcal O (1/ \sqrt{T})$ with high probability without the knowledge of smoothness and variance. We use a particular version of Freedman's concentration bound for martingale difference sequences (Kakade & Tewari, 2008) which enables us to achieve the best-known dependence of $\log (1 / \delta )$ on the probability margin $\delta$. We present our analysis in a modular way and obtain a complementary $\mathcal O (1 / T)$ convergence rate in the deterministic setting. To the best of our knowledge, this is the first high probability result for AdaGrad with a truly adaptive scheme, i.e., completely oblivious to the knowledge of smoothness and uniform variance bound, which simultaneously has best-known dependence of $\log( 1/ \delta)$. We further prove noise adaptation property of AdaGrad under additional noise assumptions.
• Abstract（参考訳）: 本稿では,AdaGradのスムーズな非凸問題に対する簡易な高確率解析法を提案する。 より具体的には、AdaGradとその変種を平均化して復元し、滑らかさと分散の知識のない高い確率で$\mathcal O (1/ \sqrt{T})$の収束率を証明する、特定の加速勾配(AGD)テンプレート(Lan, 2020)に焦点を当てる。 我々は、マーチンゲール差分列(Kakade & Tewari, 2008)に有界なフリードマン濃度の特定のバージョンを使用し、確率マージン$\delta$で$\log (1 / \delta )$の最もよく知られた依存を達成できる。 我々はモジュラーな方法で解析を行い、決定論的設定における補的な$\mathcal O (1 / T)$収束率を得る。 私たちの知る限りでは、これは真に適応的なスキームを持つアダグラードにとって最初の高い確率結果であり、すなわち、滑らかさと均一な分散境界の知識に完全に従わず、同時に最もよく知られた$\log(1/\delta)$の依存を持つ。 さらに,アダグラードの雑音適応特性を付加雑音条件下で証明する。

関連論文リスト

• Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization Problems [56.86067111855056]
  構造密度の重み付き雑音によるクリップ最適化問題を考察する。 勾配が有限の順序モーメントを持つとき、$mathcalO(K-(alpha - 1)/alpha)$よりも高速な収束率が得られることを示す。 得られた推定値が無視可能なバイアスと制御可能な分散を持つことを示す。
  論文  参考訳（メタデータ） (2023-11-07T17:39:17Z)
• High-probability Convergence Bounds for Nonlinear Stochastic Gradient Descent Under Heavy-tailed Noise [59.25598762373543]
  重み付き雑音の存在下でのストリーミングデータにおける学習の精度保証について検討した。 解析的に、与えられた問題に対する設定の選択に$ta$を使うことができることを実証する。
  論文  参考訳（メタデータ） (2023-10-28T18:53:41Z)
• Convergence of AdaGrad for Non-convex Objectives: Simple Proofs and Relaxed Assumptions [33.49807210207286]
  新しい補助関数$xi$は、AdaGradsイテレーションの数値と分母の間の相関を扱う複雑さを取り除くのに役立つ。 AdaGradは,学習率がしきい値より低い限り,$(L_0)$smooth条件下での収束に成功していることを示す。
  論文  参考訳（メタデータ） (2023-05-29T09:33:04Z)
• High Probability Convergence of Stochastic Gradient Methods [15.829413808059124]
  最適解への初期距離に依存する有界収束を示す。 AdaGrad-Normのハイバウンドが得られることを示す。
  論文  参考訳（メタデータ） (2023-02-28T18:42:11Z)
• SGD with AdaGrad Stepsizes: Full Adaptivity with High Probability to Unknown Parameters, Unbounded Gradients and Affine Variance [33.593203156666746]
  本稿では,AdaGradが一階最適化のための適応(自己調整)手法を段階化することを示す。 低ノイズと高レジの両方で、低ノイズと高レジの両方で急激な収束率を見出す。
  論文  参考訳（メタデータ） (2023-02-17T09:46:08Z)
• Adaptive Stochastic Variance Reduction for Non-convex Finite-Sum Minimization [52.25843977506935]
  有限サム構造をもつ$L$-smooth, non-deuction関数に対して, AdaSpider と呼ばれる適応分散法を提案する。 そうすることで、$tildeOleft + st/epsilonコールで$epsilon-stationaryポイントを計算することができます。
  論文  参考訳（メタデータ） (2022-11-03T14:41:46Z)
• Convergence Rates of Stochastic Gradient Descent under Infinite Noise Variance [14.06947898164194]
  ヘビーテールは様々なシナリオで勾配降下 (sgd) で現れる。 SGDの収束保証は、潜在的に無限のばらつきを持つ状態依存性および重尾ノイズ下で提供します。 その結果,SGDは無限に分散した重尾雑音下であっても,地球最適値に収束できることが示された。
  論文  参考訳（メタデータ） (2021-02-20T13:45:11Z)
• 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)

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

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