論文の概要: Near-Optimal High Probability Complexity Bounds for Non-Smooth
Stochastic Optimization with Heavy-Tailed Noise
- arxiv url: http://arxiv.org/abs/2106.05958v1
- Date: Thu, 10 Jun 2021 17:54:21 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-11 14:03:48.340949
- Title: Near-Optimal 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つの勾配法に対して, 新たなステップサイズルールを提案する。
- 参考スコア(独自算出の注目度): 63.304196997102494
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Thanks to their practical efficiency and random nature of the data,
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, e.g., in several NLP tasks. 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(参考訳): データの実用的効率性とランダム性により、確率的一階法は大規模機械学習モデルのトレーニングに標準となっている。
ランダムな振る舞いはアルゴリズムの特定の実行を非常に最適でない目的値にさせるが、理論的な保証は通常目的値の期待に対して証明される。
したがって、アルゴリズムが小さな目標残差を高い確率で提供することを理論的に保証することが不可欠である。
既存の非滑らかな確率凸最適化の方法は、負のパワーまたは対数的な信頼度に依存するが、いくつかのNLPタスクのように実際には保持されない準ガウス雑音分布の仮定の下で、複雑性を持つ。
本稿では,この問題を解き,非ガウス雑音を用いた非滑らか凸確率確率最適化問題に対する信頼度に対数的依存を持つ最初の高確率収束結果を得る。
そこで本研究では,勾配クリッピングを用いた2つの確率的手法のステップサイズルールを提案する。
さらに,H\ より古い連続勾配を用いた一般化された滑らかな対象に対して解析を行い,両手法とも強い凸問題に対する拡張を提供する。
最後に,本研究では,第1の(加速)手法が,すべてのレジームにおいて最適な反復とoracleの複雑さを持ち,第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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。