論文の概要: Simple and Optimal Stochastic Gradient Methods for Nonsmooth Nonconvex Optimization

• arxiv url: http://arxiv.org/abs/2208.10025v1
• Date: Mon, 22 Aug 2022 02:40:35 GMT
• ステータス: 処理完了
• システム内更新日: 2022-08-23 14:47:43.863089
• Title: Simple and Optimal Stochastic Gradient Methods for Nonsmooth Nonconvex Optimization
• Title（参考訳）: 非滑らかな非凸最適化のための単純かつ最適確率勾配法
• Authors: Zhize Li, Jian Li
• Abstract要約: 非平滑正則化問題,有限サム問題,オンライン最適化問題において,定常点や局所最小値を求めるための勾配アルゴリズムを提案し,解析する。 まず,ProxSVRG+と呼ばれる減算の分散に基づく簡単な近似最適勾配アルゴリズムを提案する。 我々のアルゴリズムは、そのアルゴリズムとほぼ同等に単純であり、同様の最適率が得られることを示す。
• 参考スコア（独自算出の注目度）: 23.447011255046835
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose and analyze several stochastic gradient algorithms for finding stationary points or local minimum in nonconvex, possibly with nonsmooth regularizer, finite-sum and online optimization problems. First, we propose a simple proximal stochastic gradient algorithm based on variance reduction called ProxSVRG+. We provide a clean and tight analysis of ProxSVRG+, which shows that it outperforms the deterministic proximal gradient descent (ProxGD) for a wide range of minibatch sizes, hence solves an open problem proposed in Reddi et al. (2016b). Also, ProxSVRG+ uses much less proximal oracle calls than ProxSVRG (Reddi et al., 2016b) and extends to the online setting by avoiding full gradient computations. Then, we further propose an optimal algorithm, called SSRGD, based on SARAH (Nguyen et al., 2017) and show that SSRGD further improves the gradient complexity of ProxSVRG+ and achieves the optimal upper bound, matching the known lower bound of (Fang et al., 2018; Li et al., 2021). Moreover, we show that both ProxSVRG+ and SSRGD enjoy automatic adaptation with local structure of the objective function such as the Polyak-\L{}ojasiewicz (PL) condition for nonconvex functions in the finite-sum case, i.e., we prove that both of them can automatically switch to faster global linear convergence without any restart performed in prior work ProxSVRG (Reddi et al., 2016b). Finally, we focus on the more challenging problem of finding an $(\epsilon, \delta)$-local minimum instead of just finding an $\epsilon$-approximate (first-order) stationary point (which may be some bad unstable saddle points). We show that SSRGD can find an $(\epsilon, \delta)$-local minimum by simply adding some random perturbations. Our algorithm is almost as simple as its counterpart for finding stationary points, and achieves similar optimal rates.
• Abstract（参考訳）: 非凸における定常点や局所極小を求める確率勾配アルゴリズムを,非滑らかな正則化問題,有限サム問題,オンライン最適化問題などを用いて提案し,解析する。 まず,ProxSVRG+と呼ばれる分散還元に基づく簡単な確率勾配アルゴリズムを提案する。 我々は, ProxSVRG+ のクリーンかつ厳密な解析を行い, 決定論的近位勾配降下(ProxGD)よりも広い範囲のミニバッチサイズで優れており, Reddi et al. (2016b) で提案されたオープンな問題を解く。 また、 ProxSVRG+ は ProxSVRG (Reddi et al., 2016b) よりもはるかに少ないオラクルコールを使用し、完全な勾配計算を回避してオンライン設定に拡張する。 さらに、SARAH(Nguyen et al., 2017)に基づくSSRGDと呼ばれる最適アルゴリズムを提案し、SSRGDがProxSVRG+の勾配複雑性をさらに向上し、既知の下界(Fang et al., 2018; Li et al., 2021)と一致する最適上界を実現することを示す。 さらに、proxsvrg+ と ssrgd は、有限平均の場合の非凸関数に対する polyak-\l{}ojasiewicz (pl) 条件のような対象関数の局所構造と自動的に適応し、前回のproxsvrg (reddi et al., 2016b) で再開することなく、両者が自動的により高速な大域的線形収束に切り替えられることを証明している。 最後に、$(\epsilon, \delta)$-local minimum を見つけるよりも、$(\epsilon, \delta)$-local minimum を見つけるより難しい問題に焦点を当てる。 ランダムな摂動を加えるだけで、SSRGDは$(\epsilon, \delta)$-local minimumを見つけることができる。 我々のアルゴリズムは定常点を求めるのとほぼ同等に単純であり、同様の最適率が得られる。

関連論文リスト

• An Algorithm with Optimal Dimension-Dependence for Zero-Order Nonsmooth Nonconvex Stochastic Optimization [37.300102993926046]
  リプシッツの目的の滑らかな点も凸点も生成しない点の複雑さについて検討する。 私たちの分析は単純だが強力だ。 Goldstein-subdifferential set, これは最近の進歩を可能にする。 非滑らかな非最適化
  論文  参考訳（メタデータ） (2023-07-10T11:56:04Z)
• Decentralized Riemannian Algorithm for Nonconvex Minimax Problems [82.50374560598493]
  ニューラルネットワークのためのミニマックスアルゴリズムは、多くの問題を解決するために開発された。 本稿では,2種類のミニマックスアルゴリズムを提案する。 そこで我々は, DRSGDAを提案し, 本手法が勾配を達成することを証明した。
  論文  参考訳（メタデータ） (2023-02-08T01:42:45Z)
• ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
  本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。 我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2023-01-01T18:51:29Z)
• Efficiently Escaping Saddle Points in Bilevel Optimization [48.925688192913]
  バイレベル最適化は、機械学習における問題の1つだ。 双レベル最適化の最近の進歩は、最初の基本的非適応的多段階解析に収束する。
  論文  参考訳（メタデータ） (2022-02-08T07:10:06Z)
• Faster Single-loop Algorithms for Minimax Optimization without Strong Concavity [30.97847679999505]
  GDA(Gradient descent Ascent)は、GAN(Generative Adversarial Network)やGAN(Adversarial Network)といった実用用途で広く利用されている。 最近の研究は、一方のトレーニング結果に対する反復の理論において、GDAの収束率が劣っていることを示している。 本稿では, 1変数のpolyak-Lojasiewicz(PL)条件を満たすという軽微な仮定の下で, GDAと滑らかなGDAの交互化という2つの代替シングルループアルゴリズムを確立する。
  論文  参考訳（メタデータ） (2021-12-10T15:35:42Z)
• A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm for Bilevel Optimization [112.59170319105971]
  問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。 MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
  論文  参考訳（メタデータ） (2021-02-15T07:10:33Z)
• A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic [142.1492359556374]
  双レベル最適化は、2レベル構造を示す問題のクラスである。 このような二段階問題に対処するための2段階近似(TTSA)アルゴリズムを提案する。 本稿では,TTSAフレームワークの特殊な事例として,2段階の自然なアクター・クリティカルポリシー最適化アルゴリズムが有用であることを示す。
  論文  参考訳（メタデータ） (2020-07-10T05:20:02Z)
• Gradient Free Minimax Optimization: Variance Reduction and Faster Convergence [120.9336529957224]
  本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。 本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
  論文  参考訳（メタデータ） (2020-06-16T17:55:46Z)

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

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