論文の概要: Riemannian stochastic optimization methods avoid strict saddle points

• arxiv url: http://arxiv.org/abs/2311.02374v1
• Date: Sat, 4 Nov 2023 11:12:24 GMT
• ステータス: 処理完了
• システム内更新日: 2023-11-07 17:55:31.625598
• Title: Riemannian stochastic optimization methods avoid strict saddle points
• Title（参考訳）: 厳密な鞍点を避けるリーマン確率最適化法
• Authors: Ya-Ping Hsieh and Mohammad Reza Karimi and Andreas Krause and Panayotis Mertikopoulos
• Abstract要約: 研究中のポリシーは、確率 1 の厳密なサドル点/部分多様体を避けていることを示す。 この結果は、アルゴリズムの極限状態が局所最小値にしかならないことを示すため、重要な正当性チェックを提供する。
• 参考スコア（独自算出の注目度）: 68.80251170757647
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Many modern machine learning applications - from online principal component analysis to covariance matrix identification and dictionary learning - can be formulated as minimization problems on Riemannian manifolds, and are typically solved with a Riemannian stochastic gradient method (or some variant thereof). However, in many cases of interest, the resulting minimization problem is not geodesically convex, so the convergence of the chosen solver to a desirable solution - i.e., a local minimizer - is by no means guaranteed. In this paper, we study precisely this question, that is, whether stochastic Riemannian optimization algorithms are guaranteed to avoid saddle points with probability 1. For generality, we study a family of retraction-based methods which, in addition to having a potentially much lower per-iteration cost relative to Riemannian gradient descent, include other widely used algorithms, such as natural policy gradient methods and mirror descent in ordinary convex spaces. In this general setting, we show that, under mild assumptions for the ambient manifold and the oracle providing gradient information, the policies under study avoid strict saddle points / submanifolds with probability 1, from any initial condition. This result provides an important sanity check for the use of gradient methods on manifolds as it shows that, almost always, the limit state of a stochastic Riemannian algorithm can only be a local minimizer.
• Abstract（参考訳）: オンライン主成分分析から共分散行列同定や辞書学習に至るまで、現代の機械学習アプリケーションの多くはリーマン多様体上の最小化問題として定式化され、リーマンの確率的勾配法(あるいはその変種)で解かれる。 しかし、多くの場合において、結果の最小化問題は測地的に凸ではないので、選択された解の望ましい解(すなわち局所最小化)への収束は決して保証されない。 本稿では,確率 1 の鞍点を避けるために,確率リーマン最適化アルゴリズムが保証されているか,という問題を正確に研究する。 一般性については, リーマン勾配降下と比較して, シナリオ毎のコストがはるかに低い可能性に加えて, 自然政策勾配法や通常の凸空間におけるミラー降下法など, 広く用いられている他のアルゴリズムを含む, 引き込みに基づく手法の族について検討する。 この一般的な設定では、環境多様体と勾配情報を提供するオラクルの穏やかな仮定の下で、研究中のポリシーは、任意の初期条件から、確率 1 の厳密な saddle point / submanifolds を避ける。 この結果は、ほぼ常に、確率リーマンアルゴリズムの極限状態が局所的最小値のみであることを示すため、多様体上の勾配法の使用に対する重要な健全性チェックを提供する。

関連論文リスト

• Trust-Region Sequential Quadratic Programming for Stochastic Optimization with Random Models [57.52124921268249]
  本稿では,1次と2次の両方の定常点を見つけるための信頼逐次準計画法を提案する。 本手法は, 1次定常点に収束するため, 対象対象の近似を最小化して定義された各イテレーションの勾配ステップを計算する。 2階定常点に収束するため,本手法は負曲率を減少するヘッセン行列を探索する固有ステップも計算する。
  論文  参考訳（メタデータ） (2024-09-24T04:39:47Z)
• Curvature-Independent Last-Iterate Convergence for Games on Riemannian Manifolds [77.4346324549323]
  本研究では, 多様体の曲率に依存しないステップサイズが, 曲率非依存かつ直線的最終点収束率を達成することを示す。 我々の知る限りでは、曲率非依存率や/または最終点収束の可能性はこれまでに検討されていない。
  論文  参考訳（メタデータ） (2023-06-29T01:20:44Z)
• Manifold Free Riemannian Optimization [4.484251538832438]
  滑らかな多様体 $mathcalM$ を用いて最適化問題を解くための原理的枠組みを提案する。 代数学M におけるコスト関数 $(x_i, y_i) の雑音のないサンプル集合 mathbbR$ と多様体 $mathcalM$ の固有次元を用いる。
  論文  参考訳（メタデータ） (2022-09-07T16:19:06Z)
• Riemannian Natural Gradient Methods [21.14740680011498]
  本稿では, 自然勾配法の自然な拡張と見なすことができる, 多様体設定におけるフィッシャー情報行列の概念を紹介する。 提案手法のほぼ完全な大域収束を標準仮定の下で確立する。 機械学習による応用に関する数値実験は、最先端の手法よりも提案手法の利点を実証している。
  論文  参考訳（メタデータ） (2022-07-15T04:33:10Z)
• The Dynamics of Riemannian Robbins-Monro Algorithms [101.29301565229265]
  本稿では,Robins と Monro のセミナル近似フレームワークを一般化し拡張するリーマンアルゴリズムの族を提案する。 ユークリッドのそれと比較すると、リーマンのアルゴリズムは多様体上の大域線型構造が欠如しているため、はるかに理解されていない。 ユークリッド・ロビンス=モンロスキームの既存の理論を反映し拡張するほぼ確実な収束結果の一般的なテンプレートを提供する。
  論文  参考訳（メタデータ） (2022-06-14T12:30:11Z)
• Faster One-Sample Stochastic Conditional Gradient Method for Composite Convex Minimization [61.26619639722804]
  滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。 提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
  論文  参考訳（メタデータ） (2022-02-26T19:10:48Z)
• A Riemannian smoothing steepest descent method for non-Lipschitz optimization on submanifolds [15.994495285950293]
  部分多様体上の非Lipschitz関数を最小化するスムースな急降下法を提案する。 滑らか化関数によって生成される列の任意の点が元の非リプシッツ問題の極限点であることを証明する。 提案手法の効率性を示すために, 数値実験を行った。
  論文  参考訳（メタデータ） (2021-04-09T05:38:28Z)
• Gradient-Free Methods for Saddle-Point Problem [125.99533416395765]
  我々はGasnikov et al., 2017のアプローチを一般化し、不正確な勾配のないオラクルで(確率的な)凸最適化問題を解けるようにした。 我々のアプローチは、$fracnlog n$ の要求するオラクル呼び出しの回数を削減します。 論文の後半では、そのような仮定ができない場合を分析し、この問題を解決する方法の近代化方法に関する一般的なアプローチを提案する。
  論文  参考訳（メタデータ） (2020-05-12T16:44:27Z)
• Stochastic Zeroth-order Riemannian Derivative Estimation and Optimization [15.78743548731191]
  多様体非線型性の非線型性の難しさを克服するために、ガウス滑らか化関数のオラクル版を提案する。 ニューラルネットワークに対するロボティクスとブラックボックス攻撃に対するブラックボックス剛性制御における,結果によるアルゴリズムの適用性と実世界の応用を実証する。
  論文  参考訳（メタデータ） (2020-03-25T06:58:19Z)

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

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