論文の概要: Breaking the Lower Bound with (Little) Structure: Acceleration in Non-Convex Stochastic Optimization with Heavy-Tailed Noise

• arxiv url: http://arxiv.org/abs/2302.06763v2
• Date: Tue, 5 Sep 2023 04:45:48 GMT
• ステータス: 処理完了
• システム内更新日: 2023-09-07 06:35:14.611201
• Title: Breaking the Lower Bound with (Little) Structure: Acceleration in Non-Convex Stochastic Optimization with Heavy-Tailed Noise
• Title（参考訳）: 小さい)構造で下界を破る:重み付き雑音による非凸確率最適化の高速化
• Authors: Zijian Liu, Jiawei Zhang, Zhengyuan Zhou
• Abstract要約: 重み付き雑音状態において、滑らかだが必ずしも凸な目標を持つ最適化問題を考察する。 簡単な構造しか持たない低境界の$Omega(Tfrac1-p3p-2)$よりも高速な速度が得られることを示す。 また、軽度条件下では、高い確率収束率が$O(log(T/delta)Tfrac1-p3p-2)$であることを保証する。
• 参考スコア（独自算出の注目度）: 28.780192812703948
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the stochastic optimization problem with smooth but not necessarily convex objectives in the heavy-tailed noise regime, where the stochastic gradient's noise is assumed to have bounded $p$th moment ($p\in(1,2]$). Zhang et al. (2020) is the first to prove the $\Omega(T^{\frac{1-p}{3p-2}})$ lower bound for convergence (in expectation) and provides a simple clipping algorithm that matches this optimal rate. Cutkosky and Mehta (2021) proposes another algorithm, which is shown to achieve the nearly optimal high-probability convergence guarantee $O(\log(T/\delta)T^{\frac{1-p}{3p-2}})$, where $\delta$ is the probability of failure. However, this desirable guarantee is only established under the additional assumption that the stochastic gradient itself is bounded in $p$th moment, which fails to hold even for quadratic objectives and centered Gaussian noise. In this work, we first improve the analysis of the algorithm in Cutkosky and Mehta (2021) to obtain the same nearly optimal high-probability convergence rate $O(\log(T/\delta)T^{\frac{1-p}{3p-2}})$, without the above-mentioned restrictive assumption. Next, and curiously, we show that one can achieve a faster rate than that dictated by the lower bound $\Omega(T^{\frac{1-p}{3p-2}})$ with only a tiny bit of structure, i.e., when the objective function $F(x)$ is assumed to be in the form of $\mathbb{E}_{\Xi\sim\mathcal{D}}[f(x,\Xi)]$, arguably the most widely applicable class of stochastic optimization problems. For this class of problems, we propose the first variance-reduced accelerated algorithm and establish that it guarantees a high-probability convergence rate of $O(\log(T/\delta)T^{\frac{1-p}{2p-1}})$ under a mild condition, which is faster than $\Omega(T^{\frac{1-p}{3p-2}})$. Notably, even when specialized to the finite-variance case, our result yields the (near-)optimal high-probability rate $O(\log(T/\delta)T^{-1/3})$.
• Abstract（参考訳）: 確率勾配の雑音が有界なp$thモーメント(p\in(1,2]$)と仮定される重み付き雑音系において、滑らかだが必ずしも凸な目的を持つ確率最適化問題を考察する。 Zhang et al. (2020) は$\Omega(T^{\frac{1-p}{3p-2}})$ lower bound for convergence (in expectation) を初めて証明し、この最適な速度に一致する単純なクリッピングアルゴリズムを提供する。 cutkosky と mehta (2021) は、ほぼ最適な高確率収束保証 $o(\log(t/\delta)t^{\frac{1-p}{3p-2}})$ を達成する別のアルゴリズムを提案している。 しかし、この望ましい保証は、確率的勾配自体が p$th モーメントに有界であるという追加の仮定の下でのみ確立され、二次目的や中心ガウスノイズに対しても保持されない。 本研究では,Cutkosky と Mehta (2021) におけるアルゴリズムの解析を改善し,上記の制限的仮定なしに,ほぼ最適に近い高確率収束率$O(\log(T/\delta)T^{\frac{1-p}{3p-2}})$を得る。 次に、興味深いことに、目的関数 $f(x)$ が $\mathbb{e}_{\xi\sim\mathcal{d}}[f(x,\xi)]$ の形であると仮定された場合、最小のビット構造だけで、下限の$\omega(t^{\frac{1-p}{3p-2}})$ によって指示されるよりも速い速度が得られる。 このクラスの問題に対して、最初の分散還元促進アルゴリズムを提案し、その確率収束率を$O(\log(T/\delta)T^{\frac{1-p}{2p-1}})$で保証し、$Omega(T^{\frac{1-p}{3p-2}})$より高速である。 特に、有限分散の場合に特化しても、我々の結果は(準)最適高確率率$O(\log(T/\delta)T^{-1/3})$となる。

関連論文リスト

• An Algorithm with Optimal Dimension-Dependence for Zero-Order Nonsmooth Nonconvex Stochastic Optimization [37.300102993926046]
  リプシッツの目的の滑らかな点も凸点も生成しない点の複雑さについて検討する。 私たちの分析は単純だが強力だ。 Goldstein-subdifferential set, これは最近の進歩を可能にする。 非滑らかな非最適化
  論文  参考訳（メタデータ） (2023-07-10T11:56:04Z)
• An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue Optimization Problems [76.2042837251496]
  相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。 注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。 本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
  論文  参考訳（メタデータ） (2023-06-30T08:34:29Z)
• High Probability Convergence of Stochastic Gradient Methods [15.829413808059124]
  最適解への初期距離に依存する有界収束を示す。 AdaGrad-Normのハイバウンドが得られることを示す。
  論文  参考訳（メタデータ） (2023-02-28T18:42:11Z)
• Beyond Uniform Smoothness: A Stopped Analysis of Adaptive SGD [38.221784575853796]
  この研究は、勾配を用いて潜在的に一定の滑らかさを持つ非アトー関数の1次定常点を求める問題を考える。 我々は、ノイズに一様境界を仮定することなく$mathcalO(fracmathrmpolylog(T)sigmatT)$収束率を証明できる技術を開発した。
  論文  参考訳（メタデータ） (2023-02-13T18:13:36Z)
• Near-Optimal Non-Convex Stochastic Optimization under Generalized Smoothness [21.865728815935665]
  2つの最近の研究は、$O(epsilon-3)$サンプル複雑性を確立し、$O(epsilon)$-定常点を得る。 しかし、どちらも$mathrmploy(epsilon-1)$という大きなバッチサイズを必要とする。 本研究では,STORMアルゴリズムの単純な変種を再検討することにより,従来の2つの問題を同時に解決する。
  論文  参考訳（メタデータ） (2023-02-13T00:22:28Z)
• A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [53.044526424637866]
  本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。 特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
  論文  参考訳（メタデータ） (2023-01-10T20:43:29Z)
• ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
  本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。 我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2023-01-01T18:51:29Z)
• Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
  滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。 漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
  論文  参考訳（メタデータ） (2022-06-17T06:10:20Z)
• Accelerating Optimization and Reinforcement Learning with Quasi-Stochastic Approximation [2.294014185517203]
  本稿では、収束理論を準確率近似に拡張することを目的とする。 強化学習のためのグラデーションフリー最適化とポリシー勾配アルゴリズムへの応用について説明する。
  論文  参考訳（メタデータ） (2020-09-30T04:44:45Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations [54.42518331209581]
  私たちは発見するアルゴリズムを見つけます。 epsilon$-approximate stationary point ($|nabla F(x)|le epsilon$) using $(epsilon,gamma)$surimateランダムランダムポイント。 ここでの私たちの下限は、ノイズのないケースでも新規です。
  論文  参考訳（メタデータ） (2020-06-24T04:41:43Z)

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

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