論文の概要: Escaping Saddle Points with Stochastically Controlled Stochastic Gradient Methods

• arxiv url: http://arxiv.org/abs/2103.04413v1
• Date: Sun, 7 Mar 2021 18:09:43 GMT
• ステータス: 処理完了
• システム内更新日: 2021-03-09 15:24:46.742623
• Title: Escaping Saddle Points with Stochastically Controlled Stochastic Gradient Methods
• Title（参考訳）: 確率制御確率勾配法によるサドル点のエスケープ
• Authors: Guannan Liang, Qianqian Tong, Chunjiang Zhu, Jinbo bi
• Abstract要約: 騒音やステップによって1次サドル勾配降下法(SCSG)が摂動可能であることを示す。 この問題を解決するために、別のステップが提案される。 提案手法は,サドル点に対するCNC-SCSGD法をさらに取り入れることを目的としている。
• 参考スコア（独自算出の注目度）: 12.173568611144626
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Stochastically controlled stochastic gradient (SCSG) methods have been proved to converge efficiently to first-order stationary points which, however, can be saddle points in nonconvex optimization. It has been observed that a stochastic gradient descent (SGD) step introduces anistropic noise around saddle points for deep learning and non-convex half space learning problems, which indicates that SGD satisfies the correlated negative curvature (CNC) condition for these problems. Therefore, we propose to use a separate SGD step to help the SCSG method escape from strict saddle points, resulting in the CNC-SCSG method. The SGD step plays a role similar to noise injection but is more stable. We prove that the resultant algorithm converges to a second-order stationary point with a convergence rate of $\tilde{O}( \epsilon^{-2} log( 1/\epsilon))$ where $\epsilon$ is the pre-specified error tolerance. This convergence rate is independent of the problem dimension, and is faster than that of CNC-SGD. A more general framework is further designed to incorporate the proposed CNC-SCSG into any first-order method for the method to escape saddle points. Simulation studies illustrate that the proposed algorithm can escape saddle points in much fewer epochs than the gradient descent methods perturbed by either noise injection or a SGD step.
• Abstract（参考訳）: 確率的に制御された確率勾配(SCSG)法は1次定常点に効率よく収束することが証明されているが、非凸最適化ではサドル点となる。 確率勾配降下 (SGD) ステップは, 深層学習と非凸空間学習問題に対するサドル点周辺の異方性雑音を生じさせ, これらの問題に対してSGDが相関負曲率 (CNC) 条件を満たすことを示す。 そこで我々は,SCSG法が厳密なサドル点から脱出するのを助けるためにSGDステップを別々に使用し,CNC-SCSG法を提案する。 SGDステップはノイズ注入と同じような役割を果たすが、より安定している。 結果のアルゴリズムは、$\tilde{O}( \epsilon^{-2} log( 1/\epsilon)$の収束率を持つ2次定常点に収束することを証明している。 この収束率は問題次元とは独立であり、cnc-sgdよりも高速である。 より一般的なフレームワークは、提案する cnc-scsg を任意の一階法に組み込むように設計されている。 シミュレーション研究により、提案アルゴリズムはノイズ注入またはSGDステップによって摂動される勾配降下法よりもはるかに少ないエポックでサドル点を回避できることを示した。

関連論文リスト

• Convergence Analysis of Adaptive Gradient Methods under Refined Smoothness and Noise Assumptions [18.47705532817026]
  AdaGradは特定の条件下では$d$でSGDより優れていることを示す。 これを動機として、目的物の滑らかさ構造と勾配のばらつきを仮定する。
  論文  参考訳（メタデータ） (2024-06-07T02:55:57Z)
• Switch and Conquer: Efficient Algorithms By Switching Stochastic Gradient Oracles For Decentralized Saddle Point Problems [1.2277343096128712]
  そこで本研究では, 一次変数と双対変数の更新を可能にする非接触な原始的ハイブリッド勾配(非接触PDHG)法を開発した。 GSGとSVRGの最適収束位相を利用することで、C-DPSSGが低-ナトリウム精度の解を得るのに適していることを示す。
  論文  参考訳（メタデータ） (2023-09-02T17:48:42Z)
• Utilising the CLT Structure in Stochastic Gradient based Sampling : Improved Analysis and Faster Algorithms [14.174806471635403]
  粒子ダイナミック(IPD)に対するグラディエント・ランゲヴィン・ダイナミクス(SGLD)やランダムバッチ法(RBM)などのサンプリングアルゴリズムの近似を考察する。 近似によって生じる雑音は中央極限定理(CLT)によりほぼガウス的であるが、ブラウン運動はまさにガウス的である。 この構造を利用して拡散過程内の近似誤差を吸収し、これらのアルゴリズムの収束保証を改善する。
  論文  参考訳（メタデータ） (2022-06-08T10:17:40Z)
• Towards Noise-adaptive, Problem-adaptive Stochastic Gradient Descent [7.176107039687231]
  雑音に対して勾配降下(SGD)を適応させるステップサイズスキームを設計する。 我々は、Nesterov反復によるSGDの$T$反復がほぼ最適であることを示す。 他のステップサイズスキームと比較して、新しい指数的なステップサイズスキームの有効性を実証する。
  論文  参考訳（メタデータ） (2021-10-21T19:22:14Z)
• Differentiable Annealed Importance Sampling and the Perils of Gradient Noise [68.44523807580438]
  Annealed importance sample (AIS) と関連するアルゴリズムは、限界推定のための非常に効果的なツールである。 差別性は、目的として限界確率を最適化する可能性を認めるため、望ましい性質である。 我々はメトロポリス・ハスティングスのステップを放棄して微分可能アルゴリズムを提案し、ミニバッチ計算をさらに解き放つ。
  論文  参考訳（メタデータ） (2021-07-21T17:10:14Z)
• Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity [49.66890309455787]
  本稿では,SGDA と SCO の最終的な収束保証として,期待されるコヒーレンシティ条件を導入し,その利点を説明する。 定常的なステップサイズを用いた場合、両手法の線形収束性を解の近傍に証明する。 我々の収束保証は任意のサンプリングパラダイムの下で保たれ、ミニバッチの複雑さに関する洞察を与える。
  論文  参考訳（メタデータ） (2021-06-30T18:32:46Z)
• On the Convergence of Stochastic Extragradient for Bilinear Games with Restarted Iteration Averaging [96.13485146617322]
  本稿では, ステップサイズが一定であるSEG法の解析を行い, 良好な収束をもたらす手法のバリエーションを示す。 平均化で拡張した場合、SEGはナッシュ平衡に確実に収束し、スケジュールされた再起動手順を組み込むことで、その速度が確実に加速されることを証明した。
  論文  参考訳（メタデータ） (2021-06-30T17:51:36Z)
• Faster Convergence of Stochastic Gradient Langevin Dynamics for Non-Log-Concave Sampling [110.88857917726276]
  我々は,非log-concaveとなる分布のクラスからサンプリングするために,勾配ランゲヴィンダイナミクス(SGLD)の新たな収束解析を行う。 我々のアプローチの核心は、補助的時間反転型マルコフ連鎖を用いたSGLDのコンダクタンス解析である。
  論文  参考訳（メタデータ） (2020-10-19T15:23:18Z)
• On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems [75.58134963501094]
  本稿では,勾配降下(SGD)の軌跡を解析する。 我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
  論文  参考訳（メタデータ） (2020-06-19T14:11:26Z)
• Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses [52.039438701530905]
  任意のリプシッツ非平滑凸損失に対して,数種類の勾配勾配降下(SGD)に対して,鋭い上下境界を与える。 我々の限界は、極端に過剰な集団リスクを伴う、微分的にプライベートな非平滑凸最適化のための新しいアルゴリズムを導出することを可能にする。
  論文  参考訳（メタデータ） (2020-06-12T02:45:21Z)

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

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