論文の概要: Convergence and complexity of block majorization-minimization for
constrained block-Riemannian optimization
- arxiv url: http://arxiv.org/abs/2312.10330v1
- Date: Sat, 16 Dec 2023 05:40:19 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-19 17:17:40.483777
- Title: Convergence and complexity of block majorization-minimization for
constrained block-Riemannian optimization
- Title(参考訳): 制約付きブロック-リーマン最適化におけるブロック偏極最小化の収束と複雑性
- Authors: Yuchen Li, Laura Balzano, Deanna Needell, Hanbaek Lyu
- Abstract要約: ブロック化最小化(BMM)は、非排他的部分空間推定のための単純な反復勾配である。
我々の分析はユークリッドの制約を明示的に用いている。
- 参考スコア(独自算出の注目度): 20.128697661112618
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Block majorization-minimization (BMM) is a simple iterative algorithm for
nonconvex optimization that sequentially minimizes a majorizing surrogate of
the objective function in each block coordinate while the other block
coordinates are held fixed. We consider a family of BMM algorithms for
minimizing smooth nonconvex objectives, where each parameter block is
constrained within a subset of a Riemannian manifold. We establish that this
algorithm converges asymptotically to the set of stationary points, and attains
an $\epsilon$-stationary point within $\widetilde{O}(\epsilon^{-2})$
iterations. In particular, the assumptions for our complexity results are
completely Euclidean when the underlying manifold is a product of Euclidean or
Stiefel manifolds, although our analysis makes explicit use of the Riemannian
geometry. Our general analysis applies to a wide range of algorithms with
Riemannian constraints: Riemannian MM, block projected gradient descent,
optimistic likelihood estimation, geodesically constrained subspace tracking,
robust PCA, and Riemannian CP-dictionary-learning. We experimentally validate
that our algorithm converges faster than standard Euclidean algorithms applied
to the Riemannian setting.
- Abstract(参考訳): bmm (block majorization-minimization) は非凸最適化のための単純な反復アルゴリズムで、各ブロック座標における目的関数のメジャー化サーロゲートを順次最小化し、他のブロック座標を固定する。
我々は、各パラメータブロックがリーマン多様体の部分集合内で制約される滑らかな非凸対象を最小化するbmmアルゴリズムの族を考える。
このアルゴリズムは定常点の集合に漸近的に収束し、$\widetilde{O}(\epsilon^{-2})$ iterations 内で $\epsilon$-stationary point を得る。
特に、我々の複雑性の仮定は、基礎となる多様体がユークリッド多様体またはスティーフェル多様体の積であるとき、完全にユークリッドである。
一般解析はリーマン制約のある広い範囲のアルゴリズムに適用できる:リーマンmm,ブロック投影勾配降下,楽観的確率推定,測地制約付き部分空間追跡,ロバストpca,リーマンcp-ディクショナリー学習。
我々は,我々のアルゴリズムがリーマン設定に適用された標準ユークリッドアルゴリズムよりも早く収束することを実験的に検証した。
関連論文リスト
- Riemannian Bilevel Optimization [35.42472057648458]
特に,2次情報を回避することを目的とした,バッチおよび勾配に基づく手法に着目する。
本稿では,一階勾配情報を活用する手法である$mathrmRF2SA$を提案し,分析する。
様々な設定の下で、$epsilon$-stationary 点に達するための明示的な収束率を提供する。
論文 参考訳(メタデータ) (2024-05-22T20:49:01Z) - Convergence and Complexity Guarantee for Inexact First-order Riemannian Optimization Algorithms [18.425648833592312]
tBMM は $O(epsilon-2)$ 内の $ilon$-定常点に収束することを示す。
軽度反復の下では、全最適性ギャップが有界である場合、各反復においてサブプロブレムが解かれるときの結果は依然として保たれる。
論文 参考訳(メタデータ) (2024-05-05T22:53:14Z) - Riemannian stochastic optimization methods avoid strict saddle points [68.80251170757647]
研究中のポリシーは、確率 1 の厳密なサドル点/部分多様体を避けていることを示す。
この結果は、アルゴリズムの極限状態が局所最小値にしかならないことを示すため、重要な正当性チェックを提供する。
論文 参考訳(メタデータ) (2023-11-04T11:12:24Z) - Zeroth-order Riemannian Averaging Stochastic Approximation Algorithms [19.99781875916751]
textttZo-RASAは$epsilon$-approximation 1次定常解を生成するのに最適なサンプル複雑性を実現する。
指数写像や並列輸送の代わりに幾何とベクトル輸送を用いることで,アルゴリズムの実用性を向上させる。
論文 参考訳(メタデータ) (2023-09-25T20:13:36Z) - Complexity of Block Coordinate Descent with Proximal Regularization and
Applications to Wasserstein CP-dictionary Learning [1.4010916616909743]
正規化(BCD-PR)によるGauss-Sdel型ブロック座標の導出について検討する。
W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W) W(W) W(W) W) W(W) W(W) W) W(W) W(W) W(W)
論文 参考訳(メタデータ) (2023-06-04T17:52:49Z) - Decentralized Riemannian Algorithm for Nonconvex Minimax Problems [82.50374560598493]
ニューラルネットワークのためのミニマックスアルゴリズムは、多くの問題を解決するために開発された。
本稿では,2種類のミニマックスアルゴリズムを提案する。
そこで我々は, DRSGDAを提案し, 本手法が勾配を達成することを証明した。
論文 参考訳(メタデータ) (2023-02-08T01:42:45Z) - On a class of geodesically convex optimization problems solved via
Euclidean MM methods [50.428784381385164]
ユークリッド凸化関数の違いは、統計学と機械学習の異なるタイプの問題の違いとして記述できることを示す。
最終的に、より広い範囲、より広い範囲の作業を支援するのです。
論文 参考訳(メタデータ) (2022-06-22T23:57:40Z) - 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) - 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) - Stochastic Zeroth-order Riemannian Derivative Estimation and
Optimization [15.78743548731191]
多様体非線型性の非線型性の難しさを克服するために、ガウス滑らか化関数のオラクル版を提案する。
ニューラルネットワークに対するロボティクスとブラックボックス攻撃に対するブラックボックス剛性制御における,結果によるアルゴリズムの適用性と実世界の応用を実証する。
論文 参考訳(メタデータ) (2020-03-25T06:58:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。