論文の概要: Convergence and Complexity Guarantee for Inexact First-order Riemannian Optimization Algorithms

• arxiv url: http://arxiv.org/abs/2405.03073v2
• Date: Thu, 9 May 2024 06:09:31 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-10 15:21:52.173302
• Title: Convergence and Complexity Guarantee for Inexact First-order Riemannian Optimization Algorithms
• Title（参考訳）: 不正確な一階リーマン最適化アルゴリズムの収束と複雑度保証
• Authors: Yuchen Li, Laura Balzano, Deanna Needell, Hanbaek Lyu,
• Abstract要約: tBMM は $O(epsilon-2)$ 内の $ilon$-定常点に収束することを示す。 軽度反復の下では、全最適性ギャップが有界である場合、各反復においてサブプロブレムが解かれるときの結果は依然として保たれる。
• 参考スコア（独自算出の注目度）: 18.425648833592312
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We analyze inexact Riemannian gradient descent (RGD) where Riemannian gradients and retractions are inexactly (and cheaply) computed. Our focus is on understanding when inexact RGD converges and what is the complexity in the general nonconvex and constrained setting. We answer these questions in a general framework of tangential Block Majorization-Minimization (tBMM). We establish that tBMM converges to an $\epsilon$-stationary point within $O(\epsilon^{-2})$ iterations. Under a mild assumption, the results still hold when the subproblem is solved inexactly in each iteration provided the total optimality gap is bounded. Our general analysis applies to a wide range of classical algorithms with Riemannian constraints including inexact RGD and proximal gradient method on Stiefel manifolds. We numerically validate that tBMM shows improved performance over existing methods when applied to various problems, including nonnegative tensor decomposition with Riemannian constraints, regularized nonnegative matrix factorization, and low-rank matrix recovery problems.
• Abstract（参考訳）: 我々は、リーマン勾配とリトラクションが不正確に(かつ安価に)計算される不正確なリーマン勾配降下(RGD)を分析する。 我々の焦点は、不正確なRGDが収束したときの理解と、一般の非凸および制約された設定における複雑さについてである。 我々はこれらの疑問に,TBMM(Tangential Block Majorization-Minimization)の一般的な枠組みで答える。 tBMM が $O(\epsilon^{-2})$イテレーション内の $\epsilon$-定常点に収束することを確立する。 微妙な仮定の下では、全最適性ギャップが有界であれば、各イテレーションにおいてサブプロブレムが不正確に解かれるとき、結果は依然として保たれる。 我々の一般解析は、スティーフェル多様体上の不正確な RGD や近位勾配法を含むリーマン的制約を持つ幅広い古典的アルゴリズムに適用できる。 tBMMは、リーマン制約付き非負のテンソル分解、正規化非負行列分解、低ランク行列回復問題など、様々な問題に適用した場合に、既存の手法よりも優れた性能を示すことを数値的に検証する。

関連論文リスト

• 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)
• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。 TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
  論文  参考訳（メタデータ） (2023-10-18T10:29:58Z)
• Curvature-Independent Last-Iterate Convergence for Games on Riemannian Manifolds [77.4346324549323]
  本研究では, 多様体の曲率に依存しないステップサイズが, 曲率非依存かつ直線的最終点収束率を達成することを示す。 我々の知る限りでは、曲率非依存率や/または最終点収束の可能性はこれまでに検討されていない。
  論文  参考訳（メタデータ） (2023-06-29T01:20:44Z)
• The Dynamics of Riemannian Robbins-Monro Algorithms [101.29301565229265]
  本稿では,Robins と Monro のセミナル近似フレームワークを一般化し拡張するリーマンアルゴリズムの族を提案する。 ユークリッドのそれと比較すると、リーマンのアルゴリズムは多様体上の大域線型構造が欠如しているため、はるかに理解されていない。 ユークリッド・ロビンス=モンロスキームの既存の理論を反映し拡張するほぼ確実な収束結果の一般的なテンプレートを提供する。
  論文  参考訳（メタデータ） (2022-06-14T12:30:11Z)
• First-Order Algorithms for Min-Max Optimization in Geodesic Metric Spaces [93.35384756718868]
  min-maxアルゴリズムはユークリッド設定で解析されている。 指数関数法 (RCEG) が線形速度で最終収束を補正したことを証明した。
  論文  参考訳（メタデータ） (2022-06-04T18:53:44Z)
• Nonlinear matrix recovery using optimization on the Grassmann manifold [18.655422834567577]
  本研究では,列が部分空間の結合などの非線形構造に従う部分観測された高階クラスタリング行列の復元問題について検討する。 交代極限はクルディカ・ロジャシ性質を用いて一意点に収束することを示す。
  論文  参考訳（メタデータ） (2021-09-13T16:13:13Z)
• Provably Convergent Working Set Algorithm for Non-Convex Regularized Regression [0.0]
  本稿では、収束保証付き非正則正規化器のためのワーキングセットアルゴリズムを提案する。 その結果,ブロックコーディネートや勾配ソルバの完全解法と比較して高い利得を示した。
  論文  参考訳（メタデータ） (2020-06-24T07:40:31Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。 我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
  論文  参考訳（メタデータ） (2020-06-11T17:43:19Z)

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

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