論文の概要: Escape saddle points faster on manifolds via perturbed Riemannian
stochastic recursive gradient
- arxiv url: http://arxiv.org/abs/2010.12191v2
- Date: Wed, 28 Oct 2020 23:41:00 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-04 00:04:58.843139
- Title: Escape saddle points faster on manifolds via perturbed Riemannian
stochastic recursive gradient
- Title（参考訳）: 摂動リーマン確率再帰勾配による多様体上のエスケープサドル点の高速化
- Authors: Andi Han, Junbin Gao
- Abstract要約: 我々のアルゴリズムは、勾配を求めるために$widetildemathcalObig( frac sqrtnepsilon2 + fracsqrtn delta4 + fracndelta3big)$グラデーションクエリを必要とする。
さらに$widetildemathcalObig( frac1epsilon3 +)の複雑さも提供します。
- 参考スコア（独自算出の注目度）: 36.79189106909088
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we propose a variant of Riemannian stochastic recursive
gradient method that can achieve second-order convergence guarantee and escape
saddle points using simple perturbation. The idea is to perturb the iterates
when gradient is small and carry out stochastic recursive gradient updates over
tangent space. This avoids the complication of exploiting Riemannian geometry.
We show that under finite-sum setting, our algorithm requires
$\widetilde{\mathcal{O}}\big( \frac{ \sqrt{n}}{\epsilon^2} + \frac{\sqrt{n}
}{\delta^4} + \frac{n}{\delta^3}\big)$ stochastic gradient queries to find a
$(\epsilon, \delta)$-second-order critical point. This strictly improves the
complexity of perturbed Riemannian gradient descent and is superior to
perturbed Riemannian accelerated gradient descent under large-sample settings.
We also provide a complexity of $\widetilde{\mathcal{O}} \big(
\frac{1}{\epsilon^3} + \frac{1}{\delta^3 \epsilon^2} + \frac{1}{\delta^4
\epsilon} \big)$ for online optimization, which is novel on Riemannian manifold
in terms of second-order convergence using only first-order information.
- Abstract（参考訳）: 本稿では,単純摂動を用いて二次収束保証と脱出サドル点を実現するリーマン確率的再帰的勾配手法の変種を提案する。
この考え方は、勾配が小さいときに反復を摂動させ、接空間上で確率的再帰的な勾配更新を行う。
これはリーマン幾何学の複雑さを避ける。
有限サム設定下では、アルゴリズムは$(\epsilon, \delta)$-second-order 臨界点を求めるために$\widetilde{\mathcal{o}}\big( \frac{ \sqrt{n}}{\epsilon^2} + \frac{\sqrt{n} }{\delta^4} + \frac{n}{\delta^3}\big)$ 確率的勾配クエリを要求する。
これは摂動リーマン勾配降下の複雑さを厳密に改善し、大きなサンプル設定下で摂動リーマン加速度勾配降下よりも優れている。
また、オンライン最適化のために、$\widetilde{\mathcal{O}} \big( \frac{1}{\epsilon^3} + \frac{1}{\delta^3 \epsilon^2} + \frac{1}{\delta^4 \epsilon} \big)$の複雑さも提供する。
関連論文リスト
- Improved Complexity for Smooth Nonconvex Optimization: A Two-Level Online Learning Approach with Quasi-Newton Methods [18.47705532817026]
本研究では,スムーズな関数を持つ$epsilon$firstorder stationary point (FOSP) を求める問題について検討する。
本稿では,このオンライン学習問題を解決するために,新しい楽観的な準勾配近似法を提案する。
論文 参考訳（メタデータ） (2024-12-03T05:20:05Z) - Riemannian Bilevel Optimization [35.42472057648458]
特に,2次情報を回避することを目的とした,バッチおよび勾配に基づく手法に着目する。
本稿では,一階勾配情報を活用する手法である$mathrmRF2SA$を提案し,分析する。
様々な設定の下で、$epsilon$-stationary 点に達するための明示的な収束率を提供する。
論文 参考訳（メタデータ） (2024-05-22T20:49:01Z) - Decentralized Riemannian Conjugate Gradient Method on the Stiefel
Manifold [59.73080197971106]
本稿では,最急降下法よりも高速に収束する一階共役最適化法を提案する。
これはスティーフェル多様体上の大域収束を達成することを目的としている。
論文 参考訳（メタデータ） (2023-08-21T08:02:16Z) - Curvature-Independent Last-Iterate Convergence for Games on Riemannian
Manifolds [77.4346324549323]
本研究では, 多様体の曲率に依存しないステップサイズが, 曲率非依存かつ直線的最終点収束率を達成することを示す。
我々の知る限りでは、曲率非依存率や/または最終点収束の可能性はこれまでに検討されていない。
論文 参考訳（メタデータ） (2023-06-29T01:20:44Z) - Revisiting Subgradient Method: Complexity and Convergence Beyond Lipschitz Continuity [24.45688490844496]
次進法は非滑らかな最適化のための最も基本的なアルゴリズムスキームの1つである。
本研究では、まず、非Lipschitz凸と弱凸最小化をカバーするために、下次法の典型的な反復複雑性結果を拡張する。
論文 参考訳（メタデータ） (2023-05-23T15:26:36Z) - Convergence of Alternating Gradient Descent for Matrix Factorization [5.439020425819001]
非対称行列分解対象に一定のステップサイズを施した交互勾配降下(AGD)について検討した。
階数-r$行列 $mathbfA in mathbbRm times n$, smoothness $C$ in the complexity $T$ to be a absolute constant。
論文 参考訳（メタデータ） (2023-05-11T16:07:47Z) - 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) - Fast Global Convergence for Low-rank Matrix Recovery via Riemannian
Gradient Descent with Random Initialization [3.0263650731957275]
リーマン多様体上の低ランク行列回復問題のクラスに対するグローバルな挙動を分析する。
より単純な最小二乗函数に対して急激な臨界点が存在するという、低ランク行列多様体の既知の幾何学的性質を明らかにする。
我々の収束保証は、ほぼ最適でほぼ次元のないものであり、数値的な観察を完全に説明できる。
論文 参考訳（メタデータ） (2020-12-31T06:40:43Z) - Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。
特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
論文 参考訳（メタデータ） (2020-02-10T23:23:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。