論文の概要: The Dynamics of Riemannian Robbins-Monro Algorithms
- arxiv url: http://arxiv.org/abs/2206.06795v2
- Date: Thu, 16 Jun 2022 12:07:47 GMT
- ステータス: 処理完了
- システム内更新日: 2022-06-19 05:06:07.652684
- Title: The Dynamics of Riemannian Robbins-Monro Algorithms
- Title（参考訳）: Riemannian Robbins-Monroアルゴリズムのダイナミクス
- Authors: Mohammad Reza Karimi, Ya-Ping Hsieh, Panayotis Mertikopoulos, Andreas
Krause
- Abstract要約: 本稿では,Robins と Monro のセミナル近似フレームワークを一般化し拡張するリーマンアルゴリズムの族を提案する。
ユークリッドのそれと比較すると、リーマンのアルゴリズムは多様体上の大域線型構造が欠如しているため、はるかに理解されていない。
ユークリッド・ロビンス=モンロスキームの既存の理論を反映し拡張するほぼ確実な収束結果の一般的なテンプレートを提供する。
- 参考スコア（独自算出の注目度）: 101.29301565229265
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Many important learning algorithms, such as stochastic gradient methods, are
often deployed to solve nonlinear problems on Riemannian manifolds. Motivated
by these applications, we propose a family of Riemannian algorithms
generalizing and extending the seminal stochastic approximation framework of
Robbins and Monro. Compared to their Euclidean counterparts, Riemannian
iterative algorithms are much less understood due to the lack of a global
linear structure on the manifold. We overcome this difficulty by introducing an
extended Fermi coordinate frame which allows us to map the asymptotic behavior
of the proposed Riemannian Robbins-Monro (RRM) class of algorithms to that of
an associated deterministic dynamical system under very mild assumptions on the
underlying manifold. In so doing, we provide a general template of almost sure
convergence results that mirrors and extends the existing theory for Euclidean
Robbins-Monro schemes, albeit with a significantly more involved analysis that
requires a number of new geometric ingredients. We showcase the flexibility of
the proposed RRM framework by using it to establish the convergence of a
retraction-based analogue of the popular optimistic / extra-gradient methods
for solving minimization problems and games, and we provide a unified treatment
for their convergence.
- Abstract（参考訳）: 確率勾配法のような多くの重要な学習アルゴリズムは、リーマン多様体上の非線形問題を解くためにしばしば展開される。
これらの応用により、Robins と Monro の半連続確率近似フレームワークを一般化し拡張するリーマンアルゴリズムの族を提案する。
ユークリッドアルゴリズムと比較すると、リーマンの反復アルゴリズムは多様体上の大域線型構造が欠如しているため、理解されていない。
我々は、提案するリーマン型ロビンズ・モンロ(rrm)クラスのアルゴリズムの漸近的挙動を、基礎多様体上の非常に穏やかな仮定の下で関連する決定論的力学系にマッピングできる拡張フェルミ座標フレームを導入することで、この困難を克服した。
このようにして、我々は、ユークリッドロビンス・モンロスキームの既存の理論を反映し拡張するほぼ確実に収束する結果の一般的なテンプレートを提供する。
提案手法の柔軟性を実証するために,提案手法を用いて,最小化問題やゲームを解くための楽観的・外段階的な手法の帰納的類似の収束を確立し,それらの収束を統一的に処理する手法を提案する。
関連論文リスト
- RMLR: Extending Multinomial Logistic Regression into General Geometries [64.16104856124029]
我々のフレームワークは、最小限の幾何学的性質しか必要とせず、広い適用性を示す。
SPD MLRの5つのファミリーを5種類のパワー変形測定値に基づいて開発する。
回転行列上では、人気のある双不変計量に基づいてリー MLR を提案する。
論文 参考訳（メタデータ） (2024-09-28T18:38:21Z) - Convergence and Complexity Guarantee for Inexact First-order Riemannian Optimization Algorithms [18.425648833592312]
tBMM は $O(epsilon-2)$ 内の $ilon$-定常点に収束することを示す。
軽度反復の下では、全最適性ギャップが有界である場合、各反復においてサブプロブレムが解かれるときの結果は依然として保たれる。
論文 参考訳（メタデータ） (2024-05-05T22:53:14Z) - Convergence and complexity of block majorization-minimization for constrained block-Riemannian optimization [18.425648833592312]
ブロック化最小化(BMM)は、非排他的部分空間推定のための単純な反復勾配である。
我々の分析はユークリッドの制約を明示的に用いている。
論文 参考訳（メタデータ） (2023-12-16T05:40:19Z) - Riemannian stochastic optimization methods avoid strict saddle points [68.80251170757647]
研究中のポリシーは、確率 1 の厳密なサドル点/部分多様体を避けていることを示す。
この結果は、アルゴリズムの極限状態が局所最小値にしかならないことを示すため、重要な正当性チェックを提供する。
論文 参考訳（メタデータ） (2023-11-04T11:12:24Z) - Curvature-Independent Last-Iterate Convergence for Games on Riemannian
Manifolds [77.4346324549323]
本研究では, 多様体の曲率に依存しないステップサイズが, 曲率非依存かつ直線的最終点収束率を達成することを示す。
我々の知る限りでは、曲率非依存率や/または最終点収束の可能性はこれまでに検討されていない。
論文 参考訳（メタデータ） (2023-06-29T01:20:44Z) - On Riemannian Approach for Constrained Optimization Model in Extreme
Classification Problems [2.7436792484073638]
制約付き最適化問題は行列多様体上の最適化問題として定式化される。
提案手法は,複数の実世界の大規模マルチラベルデータセットで検証される。
論文 参考訳（メタデータ） (2021-09-30T11:28:35Z) - Nonlinear matrix recovery using optimization on the Grassmann manifold [18.655422834567577]
本研究では,列が部分空間の結合などの非線形構造に従う部分観測された高階クラスタリング行列の復元問題について検討する。
交代極限はクルディカ・ロジャシ性質を用いて一意点に収束することを示す。
論文 参考訳（メタデータ） (2021-09-13T16:13:13Z) - Optimization on manifolds: A symplectic approach [127.54402681305629]
本稿では、最適化問題を解くための一般的な枠組みとして、ディラックの制約付きハミルトン系理論の散逸拡張を提案する。
我々の(加速された)アルゴリズムのクラスは単純で効率的なだけでなく、幅広い文脈にも適用できる。
論文 参考訳（メタデータ） (2021-07-23T13:43:34Z) - Bayesian Quadrature on Riemannian Data Manifolds [79.71142807798284]
データに固有の非線形幾何学構造をモデル化する原則的な方法が提供される。
しかし、これらの演算は通常計算的に要求される。
特に、正規法則上の積分を数値計算するためにベイズ二次(bq)に焦点を当てる。
先行知識と活発な探索手法を両立させることで,BQは必要な評価回数を大幅に削減できることを示す。
論文 参考訳（メタデータ） (2021-02-12T17:38:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。