論文の概要: High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise

• arxiv url: http://arxiv.org/abs/2106.05958v3
• Date: Fri, 30 Aug 2024 13:35:31 GMT
• ステータス: 処理完了
• システム内更新日: 2024-09-03 14:11:27.234784
• Title: High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise
• Title（参考訳）: 重音を用いた非滑らか確率最適化のための高確率複素境界
• Authors: Eduard Gorbunov, Marina Danilova, Innokentiy Shibaev, Pavel Dvurechensky, Alexander Gasnikov,
• Abstract要約: アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。 非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。 そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
• 参考スコア（独自算出の注目度）: 51.31435087414348
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Stochastic first-order methods are standard for training large-scale machine learning models. Random behavior may cause a particular run of an algorithm to result in a highly suboptimal objective value, whereas theoretical guarantees are usually proved for the expectation of the objective value. Thus, it is essential to theoretically guarantee that algorithms provide small objective residual with high probability. Existing methods for non-smooth stochastic convex optimization have complexity bounds with the dependence on the confidence level that is either negative-power or logarithmic but under an additional assumption of sub-Gaussian (light-tailed) noise distribution that may not hold in practice. In our paper, we resolve this issue and derive the first high-probability convergence results with logarithmic dependence on the confidence level for non-smooth convex stochastic optimization problems with non-sub-Gaussian (heavy-tailed) noise. To derive our results, we propose novel stepsize rules for two stochastic methods with gradient clipping. Moreover, our analysis works for generalized smooth objectives with H\"older-continuous gradients, and for both methods, we provide an extension for strongly convex problems. Finally, our results imply that the first (accelerated) method we consider also has optimal iteration and oracle complexity in all the regimes, and the second one is optimal in the non-smooth setting.
• Abstract（参考訳）: 確率的一階法は大規模機械学習モデルのトレーニングに標準である。 ランダムな振る舞いは、アルゴリズムの特定の実行によって、高い最適化された目標値が得られるが、理論的な保証は通常、目的値の期待に対して証明される。 したがって、アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。 既存の非滑らかな確率凸最適化の方法は、負のパワーまたは対数的な信頼度に依存するが、実際には持たない準ガウス雑音分布の仮定の下で、複雑性を持つ。 本稿では,この問題を解き,非ガウス雑音を用いた非滑らか凸確率確率最適化問題に対する信頼度に対数的依存を持つ最初の高確率収束結果を導出する。 そこで本研究では,勾配クリッピングを用いた2つの確率的手法のステップサイズルールを提案する。 さらに,H\ より古い連続勾配を用いた一般化された滑らかな対象に対して解析を行い,両手法とも強い凸問題に対する拡張を提供する。 最後に,本研究の結果から,第1の(加速された)手法は全てのレシエーションにおいて最適反復とオラクルの複雑さを持ち,第2の手法は非滑らかな設定において最適であることが示唆された。

関連論文リスト

• Dealing with unbounded gradients in stochastic saddle-point optimization [9.983014605039658]
  本研究では,凸凹関数のサドル点を求める一階法の性能について検討する。 悪名高い課題は、最適化中に勾配が任意に大きくなることだ。 本稿では,反復を安定化し,有意義な性能保証を与える,シンプルで効果的な正則化手法を提案する。
  論文  参考訳（メタデータ） (2024-02-21T16:13:49Z)
• Accelerated stochastic approximation with state-dependent noise [7.4648480208501455]
  勾配観測における2次雑音に対する一般仮定の下での滑らかな凸最適化問題を考察する。 このような問題は、統計学におけるよく知られた一般化された線形回帰問題において、様々な応用において自然に発生する。 SAGDとSGEは、適切な条件下で、最適収束率を達成することを示す。
  論文  参考訳（メタデータ） (2023-07-04T06:06:10Z)
• Learning Unnormalized Statistical Models via Compositional Optimization [73.30514599338407]
  実データと人工雑音のロジスティックな損失として目的を定式化することにより, ノイズコントラスト推定(NCE)を提案する。 本稿では,非正規化モデルの負の対数類似度を最適化するための直接的アプローチについて検討する。
  論文  参考訳（メタデータ） (2023-06-13T01:18:16Z)
• High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance [59.211456992422136]
  制約の少ない仮定の下で高確率収束結果のアルゴリズムを提案する。 これらの結果は、標準機能クラスに適合しない問題を最適化するために検討された手法の使用を正当化する。
  論文  参考訳（メタデータ） (2023-02-02T10:37:23Z)
• Nearly Optimal Robust Method for Convex Compositional Problems with Heavy-Tailed Noise [46.94819585976063]
  我々は、$f(E_xi g(cdot; xi)) + r(cdot)$という形の凸合成問題を解くための頑健なアルゴリズムを提案する。 我々の知る限りでは、これは重尾の仮定の下で構成問題に対するほぼ最適な準ガウス的自信境界を確立する最初の研究である。
  論文  参考訳（メタデータ） (2020-06-17T18:36:05Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。 我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
  論文  参考訳（メタデータ） (2020-06-11T17:43:19Z)
• The Strength of Nesterov's Extrapolation in the Individual Convergence of Nonsmooth Optimization [0.0]
  ネステロフの外挿は、非滑らかな問題に対して勾配降下法の個人収束を最適にする強さを持つことを証明している。 提案手法は,設定の非滑らかな損失を伴って正規化学習タスクを解くためのアルゴリズムの拡張である。 本手法は,大規模な1-正規化ヒンジロス学習問題の解法として有効である。
  論文  参考訳（メタデータ） (2020-06-08T03:35:41Z)
• Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clipping [69.9674326582747]
  そこで本研究では,重み付き分散雑音を用いたスムーズな凸最適化のための,クリップ付きSSTMと呼ばれる新しい1次高速化手法を提案する。 この場合、最先端の結果を上回る新たな複雑さが証明される。 本研究は,SGDにおいて,ノイズに対する光細かな仮定を伴わずにクリッピングを施した最初の非自明な高確率複雑性境界を導出した。
  論文  参考訳（メタデータ） (2020-05-21T17:05:27Z)

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

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