論文の概要: High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance

• arxiv url: http://arxiv.org/abs/2302.00999v2
• Date: Tue, 18 Jul 2023 14:19:07 GMT
• ステータス: 処理完了
• システム内更新日: 2023-07-19 19:17:10.839527
• Title: High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance
• Title（参考訳）: 確率的最適化と変分不等式に対する高確率境界:非有界分散の場合
• Authors: Abdurakhmon Sadiev, Marina Danilova, Eduard Gorbunov, Samuel Horv\'ath, Gauthier Gidel, Pavel Dvurechensky, Alexander Gasnikov, Peter Richt\'arik
• Abstract要約: 制約の少ない仮定の下で高確率収束結果のアルゴリズムを提案する。 これらの結果は、標準機能クラスに適合しない問題を最適化するために検討された手法の使用を正当化する。
• 参考スコア（独自算出の注目度）: 59.211456992422136
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: During recent years the interest of optimization and machine learning communities in high-probability convergence of stochastic optimization methods has been growing. One of the main reasons for this is that high-probability complexity bounds are more accurate and less studied than in-expectation ones. However, SOTA high-probability non-asymptotic convergence results are derived under strong assumptions such as the boundedness of the gradient noise variance or of the objective's gradient itself. In this paper, we propose several algorithms with high-probability convergence results under less restrictive assumptions. In particular, we derive new high-probability convergence results under the assumption that the gradient/operator noise has bounded central $\alpha$-th moment for $\alpha \in (1,2]$ in the following setups: (i) smooth non-convex / Polyak-Lojasiewicz / convex / strongly convex / quasi-strongly convex minimization problems, (ii) Lipschitz / star-cocoercive and monotone / quasi-strongly monotone variational inequalities. These results justify the usage of the considered methods for solving problems that do not fit standard functional classes studied in stochastic optimization.
• Abstract（参考訳）: 近年,確率的最適化手法の高確率収束に対する最適化と機械学習コミュニティの関心が高まっている。 この主な理由の1つは、高確率の複雑性境界が観測値よりも正確で研究の少ないことである。 しかし、SOTA高確率非漸近収束結果は、勾配雑音分散の有界性や目的の勾配自体の有界性といった強い仮定の下で導出される。 本稿では,制約の少ない仮定下で高い確率収束結果を持つアルゴリズムを提案する。 特に、勾配/演算ノイズが、次の設定で$\alpha \in (1,2]$の中央$\alpha$-thのモーメントを有界とする仮定の下で、新しい高確率収束結果を得る。 (i)滑らかな非凸/ポリak-ロヤシーヴィチ/凸/強凸/準強凸最小化問題 (II)リプシッツ / スターコヒールシブ, モノトン / 準強いモノトン変分不等式。 これらの結果は、確率最適化で研究されている標準関数クラスに適合しない問題を解くための考慮された方法の使用を正当化する。

関連論文リスト

• Methods for Convex $(L_0,L_1)$-Smooth Optimization: Clipping, Acceleration, and Adaptivity [50.25258834153574]
  我々は、(強に)凸 $(L0)$-smooth 関数のクラスに焦点を当て、いくつかの既存のメソッドに対する新しい収束保証を導出する。 特に,スムーズなグラディエント・クリッピングを有するグラディエント・ディフレッシュと,ポリアク・ステップサイズを有するグラディエント・ディフレッシュのコンバージェンス・レートの改善を導出した。
  論文  参考訳（メタデータ） (2024-09-23T13:11:37Z)
• High-Probability Convergence for Composite and Distributed Stochastic Minimization and Variational Inequalities with Heavy-Tailed Noise [96.80184504268593]
  グラデーション、クリッピングは、優れた高確率保証を導き出すアルゴリズムの鍵となる要素の1つである。 クリッピングは、合成および分散最適化の一般的な方法の収束を損なう可能性がある。
  論文  参考訳（メタデータ） (2023-10-03T07:49:17Z)
• Convex and Non-convex Optimization Under Generalized Smoothness [69.69521650503431]
  凸法と非最適化法の分析は、しばしばリプシッツ勾配を必要とし、この軌道による解析を制限する。 最近の研究は、非一様滑らか性条件を通した勾配設定を一般化している。
  論文  参考訳（メタデータ） (2023-06-02T04:21:59Z)
• 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)
• Clipped Stochastic Methods for Variational Inequalities with Heavy-Tailed Noise [64.85879194013407]
  単調なVIPと非単調なVIPの解法における信頼度に対数的依存を持つ最初の高確率結果が証明された。 この結果は光尾の場合で最もよく知られたものと一致し,非単調な構造問題に新鮮である。 さらに,多くの実用的な定式化の勾配雑音が重く,クリッピングによりSEG/SGDAの性能が向上することを示す。
  論文  参考訳（メタデータ） (2022-06-02T15:21:55Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。 非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。 そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
  論文  参考訳（メタデータ） (2021-06-10T17:54:21Z)
• Halpern Iteration for Near-Optimal and Parameter-Free Monotone Inclusion and Strong Solutions to Variational Inequalities [14.848525762485872]
  非拡張写像、単調リプシッツ作用素、近位写像の間の接続を利用して、単調包含問題に対する準最適解を得る。 これらの結果は、変分不等式問題に対する強い解の近似、凸凸凹 min-max 最適化問題の近似、および min-max 最適化問題における勾配のノルムの最小化について、ほぼ最適に保証される。
  論文  参考訳（メタデータ） (2020-02-20T17:12:49Z)

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

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