論文の概要: Stochastic Nonsmooth Convex Optimization with Heavy-Tailed Noises:
High-Probability Bound, In-Expectation Rate and Initial Distance Adaptation
- arxiv url: http://arxiv.org/abs/2303.12277v3
- Date: Sat, 20 May 2023 04:12:11 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-24 03:43:18.251965
- Title: Stochastic Nonsmooth Convex Optimization with Heavy-Tailed Noises:
High-Probability Bound, In-Expectation Rate and Initial Distance Adaptation
- Title（参考訳）: 重音を用いた確率的非平滑凸最適化:高確率境界, 観測速度, 初期距離適応
- Authors: Zijian Liu, Zhengyuan Zhou
- Abstract要約: 重尾雑音系では、勾配と真の速度の差は有限の$p-thモーメントを持つと仮定される。
本稿では,重み付き雑音を用いた非平滑凸最適化の包括的解析を行う。
- 参考スコア（独自算出の注目度）: 22.758674468435302
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Recently, several studies consider the stochastic optimization problem but in
a heavy-tailed noise regime, i.e., the difference between the stochastic
gradient and the true gradient is assumed to have a finite $p$-th moment (say
being upper bounded by $\sigma^{p}$ for some $\sigma\geq0$) where $p\in(1,2]$,
which not only generalizes the traditional finite variance assumption ($p=2$)
but also has been observed in practice for several different tasks. Under this
challenging assumption, lots of new progress has been made for either convex or
nonconvex problems, however, most of which only consider smooth objectives. In
contrast, people have not fully explored and well understood this problem when
functions are nonsmooth. This paper aims to fill this crucial gap by providing
a comprehensive analysis of stochastic nonsmooth convex optimization with
heavy-tailed noises. We revisit a simple clipping-based algorithm, whereas,
which is only proved to converge in expectation but under the additional strong
convexity assumption. Under appropriate choices of parameters, for both convex
and strongly convex functions, we not only establish the first high-probability
rates but also give refined in-expectation bounds compared with existing works.
Remarkably, all of our results are optimal (or nearly optimal up to logarithmic
factors) with respect to the time horizon $T$ even when $T$ is unknown in
advance. Additionally, we show how to make the algorithm parameter-free with
respect to $\sigma$, in other words, the algorithm can still guarantee
convergence without any prior knowledge of $\sigma$. Furthermore, an initial
distance adaptive convergence rate is provided if $\sigma$ is assumed to be
known.
- Abstract（参考訳）: 近年、確率的最適化問題を考える研究がいくつかあるが、重み付きノイズレジーム、すなわち、確率的勾配と真の勾配の差は、(例えば、いくつかの$\sigma\geq0$ に対して$\sigma^{p}$ で上限されるような)有限の$p$-th モーメント(例えば、$p\in(1,2]$)を持つと仮定される。
この挑戦的な仮定の下では、凸問題や非凸問題に対して多くの新しい進歩がなされてきたが、そのほとんどは滑らかな目的しか考慮していない。
対照的に、関数が不眠である場合、人々はこの問題を十分に探求し、よく理解していない。
本稿では,重み付き雑音を用いた確率的非滑らか凸最適化の包括的解析により,この重要なギャップを埋めることを目的とする。
単純なクリッピングに基づくアルゴリズムを再検討するが、これは期待値に収束するだけでなく、さらに強い凸性仮定の下でも証明される。
パラメータの適切な選択の下では、凸関数と強凸関数の両方に対して、最初の高確率率を確立するだけでなく、既存の研究と比較して洗練された内部予測境界を与える。
驚くべきことに、すべての結果は、事前に$t$が不明であっても、時間軸$t$に関して最適(または対数係数までほぼ最適)である。
さらに、$\sigma$に対してアルゴリズムをパラメータフリーにする方法を示し、言い換えれば、$\sigma$の事前知識なしでも収束を保証することができる。
さらに、$\sigma$ が知られていると仮定すると、初期距離適応収束率が与えられる。
関連論文リスト
- Methods for Convex $(L_0,L_1)$-Smooth Optimization: Clipping, Acceleration, and Adaptivity [50.25258834153574]
我々は、(強に)凸 $(L0)$-smooth 関数のクラスに焦点を当て、いくつかの既存のメソッドに対する新しい収束保証を導出する。
特に,スムーズなグラディエント・クリッピングを有するグラディエント・ディフレッシュと,ポリアク・ステップサイズを有するグラディエント・ディフレッシュのコンバージェンス・レートの改善を導出した。
論文 参考訳（メタデータ） (2024-09-23T13:11:37Z) - Revisiting the Last-Iterate Convergence of Stochastic Gradient Methods [25.831462008050387]
グラディエント・Descent(SGD)アルゴリズムは、実際の性能が良く、理論的な理解が欠如していることから、人々の関心を喚起している。
有限収束がより広い合成最適化や非ユークリッドノルムに証明可能な拡張が可能かどうかはまだ不明である。
論文 参考訳（メタデータ） (2023-12-13T21:41:06Z) - An Algorithm with Optimal Dimension-Dependence for Zero-Order Nonsmooth Nonconvex Stochastic Optimization [37.300102993926046]
リプシッツの目的の滑らかな点も凸点も生成しない点の複雑さについて検討する。
私たちの分析は単純だが強力だ。
Goldstein-subdifferential set, これは最近の進歩を可能にする。
非滑らかな非最適化
論文 参考訳（メタデータ） (2023-07-10T11:56:04Z) - Gradient-free optimization of highly smooth functions: improved analysis
and a new algorithm [87.22224691317766]
この研究は、目的関数が極めて滑らかであるという仮定の下で、ゼロ次ノイズオラクル情報による問題を研究する。
ゼロオーダー射影勾配勾配アルゴリズムを2種類検討する。
論文 参考訳（メタデータ） (2023-06-03T17:05:13Z) - High-Probability Bounds for Stochastic Optimization and Variational
Inequalities: the Case of Unbounded Variance [59.211456992422136]
制約の少ない仮定の下で高確率収束結果のアルゴリズムを提案する。
これらの結果は、標準機能クラスに適合しない問題を最適化するために検討された手法の使用を正当化する。
論文 参考訳（メタデータ） (2023-02-02T10:37:23Z) - Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。
漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
論文 参考訳（メタデータ） (2022-06-17T06:10:20Z) - Mirror Descent Strikes Again: Optimal Stochastic Convex Optimization
under Infinite Noise Variance [17.199063087458907]
我々は一様凸ミラーマップのクラスを用いてミラーDescentアルゴリズムの収束率を定量化する。
このアルゴリズムは明確な勾配クリッピングや正規化を必要としない。
我々は,1次オラクルのみを用いた他のアルゴリズムでは改善率を達成できないことを示す情報理論の下界を補完する。
論文 参考訳（メタデータ） (2022-02-23T17:08:40Z) - High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。
非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。
そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
論文 参考訳（メタデータ） (2021-06-10T17:54:21Z) - Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
近年、深層ネットワークにおける非最適化アルゴリズムの解析やデータ問題への関心が高まっており、非最適化のための理論的最適化アルゴリズムの最近の結果の概要を概説する。
論文 参考訳（メタデータ） (2020-12-11T08:28:51Z) - A New Randomized Primal-Dual Algorithm for Convex Optimization with
Optimal Last Iterate Rates [16.54912614895861]
我々は,非滑らかな制約付き凸最適化問題のクラスを解くために,新しいランダム化ブロック座標原始双対アルゴリズムを開発した。
我々は,一般凸性と強い凸性という2つのケースにおいて,アルゴリズムが最適収束率を達成することを証明した。
その結果,提案手法は異なる実験における性能向上に寄与していることがわかった。
論文 参考訳（メタデータ） (2020-03-03T03:59:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。