論文の概要: Near-Optimal Non-Convex Stochastic Optimization under Generalized
Smoothness
- arxiv url: http://arxiv.org/abs/2302.06032v2
- Date: Sat, 28 Oct 2023 03:26:32 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-31 23:15:20.733991
- Title: Near-Optimal Non-Convex Stochastic Optimization under Generalized
Smoothness
- Title（参考訳）: 一般化平滑性下における近似最適非凸確率最適化
- Authors: Zijian Liu, Srikanth Jagabathula, Zhengyuan Zhou
- Abstract要約: 2つの最近の研究は、$O(epsilon-3)$サンプル複雑性を確立し、$O(epsilon)$-定常点を得る。
しかし、どちらも$mathrmploy(epsilon-1)$という大きなバッチサイズを必要とする。
本研究では,STORMアルゴリズムの単純な変種を再検討することにより,従来の2つの問題を同時に解決する。
- 参考スコア（独自算出の注目度）: 21.865728815935665
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The generalized smooth condition, $(L_{0},L_{1})$-smoothness, has triggered
people's interest since it is more realistic in many optimization problems
shown by both empirical and theoretical evidence. Two recent works established
the $O(\epsilon^{-3})$ sample complexity to obtain an $O(\epsilon)$-stationary
point. However, both require a large batch size on the order of
$\mathrm{ploy}(\epsilon^{-1})$, which is not only computationally burdensome
but also unsuitable for streaming applications. Additionally, these existing
convergence bounds are established only for the expected rate, which is
inadequate as they do not supply a useful performance guarantee on a single
run. In this work, we solve the prior two problems simultaneously by revisiting
a simple variant of the STORM algorithm. Specifically, under the
$(L_{0},L_{1})$-smoothness and affine-type noises, we establish the first
near-optimal $O(\log(1/(\delta\epsilon))\epsilon^{-3})$ high-probability sample
complexity where $\delta\in(0,1)$ is the failure probability. Besides, for the
same algorithm, we also recover the optimal $O(\epsilon^{-3})$ sample
complexity for the expected convergence with improved dependence on the
problem-dependent parameter. More importantly, our convergence results only
require a constant batch size in contrast to the previous works.
- Abstract（参考訳）: 一般化された滑らかな条件である$(l_{0},l_{1})$-smoothness は、経験的および理論的証拠の両方によって示される多くの最適化問題においてより現実的であるため、人々の関心を引き起こしている。
2つの最近の研究は、$O(\epsilon^{-3})$サンプル複雑性を確立し、$O(\epsilon)$-定常点を得る。
しかし、どちらも$\mathrm{ploy}(\epsilon^{-1})$という順序で大きなバッチサイズを必要とする。
さらに、これらの既存の収束限界は、期待値に対してのみ確立されるが、1回のランで有用な性能保証が提供されないため、不十分である。
本研究では,STORMアルゴリズムの単純な変種を再検討することにより,従来の2つの問題を同時に解決する。
具体的には、$(L_{0},L_{1})$-smoothness と affine-type noises の下で、最初の準最適 $O(\log(1/(\delta\epsilon))\epsilon^{-3})$ 高確率サンプル複雑性を確立し、$\delta\in(0,1)$ は失敗確率である。
また、同じアルゴリズムでは、問題依存パラメータへの依存性を改善した期待収束のために最適な$o(\epsilon^{-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) - Breaking the Lower Bound with (Little) Structure: Acceleration in
Non-Convex Stochastic Optimization with Heavy-Tailed Noise [28.780192812703948]
重み付き雑音状態において、滑らかだが必ずしも凸な目標を持つ最適化問題を考察する。
簡単な構造しか持たない低境界の$Omega(Tfrac1-p3p-2)$よりも高速な速度が得られることを示す。
また、軽度条件下では、高い確率収束率が$O(log(T/delta)Tfrac1-p3p-2)$であることを保証する。
論文 参考訳（メタデータ） (2023-02-14T00:23:42Z) - Beyond Uniform Smoothness: A Stopped Analysis of Adaptive SGD [38.221784575853796]
この研究は、勾配を用いて潜在的に一定の滑らかさを持つ非アトー関数の1次定常点を求める問題を考える。
我々は、ノイズに一様境界を仮定することなく$mathcalO(fracmathrmpolylog(T)sigmatT)$収束率を証明できる技術を開発した。
論文 参考訳（メタデータ） (2023-02-13T18:13:36Z) - ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。
我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-01-01T18:51:29Z) - An Optimal Stochastic Algorithm for Decentralized Nonconvex Finite-sum
Optimization [25.21457349137344]
私たちは、DEARESTが少なくとも$mathcal O(+sqrtmnLvarepsilon-2)$ 1次オラクル(IFO)コールと$mathcal O(Lvarepsilon-2/sqrt1-lambda_W)$通信ラウンドを必要とすることを示す証拠を示します。
論文 参考訳（メタデータ） (2022-10-25T11:37:11Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Optimal Gradient Sliding and its Application to Distributed Optimization
Under Similarity [121.83085611327654]
積 $r:=p + q$, ここで$r$は$mu$-strong convex類似性である。
エージェントの通信やローカルコールにマスターされた問題を解決する方法を提案する。
提案手法は$mathcalO(sqrtL_q/mu)$法よりもはるかにシャープである。
論文 参考訳（メタデータ） (2022-05-30T14:28:02Z) - Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$
Geometry [69.24618367447101]
対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。
損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
論文 参考訳（メタデータ） (2021-03-02T06:53:44Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。