論文の概要: Nonconvex Matrix Factorization is Geodesically Convex: Global Landscape
Analysis for Fixed-rank Matrix Optimization From a Riemannian Perspective
- arxiv url: http://arxiv.org/abs/2209.15130v1
- Date: Thu, 29 Sep 2022 23:08:41 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-03 17:05:57.436734
- Title: Nonconvex Matrix Factorization is Geodesically Convex: Global Landscape
Analysis for Fixed-rank Matrix Optimization From a Riemannian Perspective
- Title（参考訳）: 非凸行列分解は測地学的凸である:リーマン的視点による固定ランク行列最適化のための大域的ランドスケープ解析
- Authors: Yuetian Luo and Nicolas Garcia Trillos
- Abstract要約: 固定ランク正半定値(PSD)制約を用いた一般行列最適化問題について検討する。
探索空間全体は、(R1)対象パラメータの近傍の領域、(R2)厳密なサドル点の近傍を含む領域、(R3)残りの領域の3つの領域に分けられることを示す。
以上の結果から, ブラー・モンテイロの分解条件下でのバニラ勾配降下の優れた性能について, 完全に説明できる。
- 参考スコア（独自算出の注目度）: 2.28438857884398
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study a general matrix optimization problem with a fixed-rank positive
semidefinite (PSD) constraint. We perform the Burer-Monteiro factorization and
consider a particular Riemannian quotient geometry in a search space that has a
total space equipped with the Euclidean metric. When the original objective f
satisfies standard restricted strong convexity and smoothness properties, we
characterize the global landscape of the factorized objective under the
Riemannian quotient geometry. We show the entire search space can be divided
into three regions: (R1) the region near the target parameter of interest,
where the factorized objective is geodesically strongly convex and smooth; (R2)
the region containing neighborhoods of all strict saddle points; (R3) the
remaining regions, where the factorized objective has a large gradient. To our
best knowledge, this is the first global landscape analysis of the
Burer-Monteiro factorized objective under the Riemannian quotient geometry. Our
results provide a fully geometric explanation for the superior performance of
vanilla gradient descent under the Burer-Monteiro factorization. When f
satisfies a weaker restricted strict convexity property, we show there exists a
neighborhood near local minimizers such that the factorized objective is
geodesically convex. To prove our results we provide a comprehensive landscape
analysis of a matrix factorization problem with a least squares objective,
which serves as a critical bridge. Our conclusions are also based on a result
of independent interest stating that the geodesic ball centered at Y with a
radius 1/3 of the least singular value of Y is a geodesically convex set under
the Riemannian quotient geometry, which as a corollary, also implies a
quantitative bound of the convexity radius in the Bures-Wasserstein space. The
convexity radius obtained is sharp up to constants.
- Abstract（参考訳）: 固定ランク正半定値(PSD)制約を用いた一般行列最適化問題について検討する。
ブラー・モンティロ分解を行い、ユークリッド計量を備えた全空間を持つ探索空間において特定のリーマン商幾何学を考える。
原目的 f が標準の強い凸性と滑らか性を満たすとき、リーマン商幾何学の下での分解対象の大域的な風景を特徴づける。
探索空間全体を3つの領域に分けることができることを示す: (R1) 対象パラメータの近傍の領域、(R) 分解対象が地理的に凸で滑らかな領域、(R2) 厳密なサドル点の近傍を含む領域、(R3) 残りの領域、(R3) 因子化対象が大きな勾配を持つ領域。
我々の知る限りでは、これはリーマン商幾何の下でのバーラー・モンテイロ分解対象の最初の世界的ランドスケープ解析である。
以上の結果から,バニラ勾配降下がバニラ-モンティロ因子分解下で優れた性能を示す完全な幾何学的説明が得られた。
f がより制限された厳密な凸性を満たすとき、分解対象が測地的に凸であるような局所最小化近傍が存在することを示す。
この結果を証明するために,最小二乗目的の行列分解問題の包括的ランドスケープ解析を行い,重要な橋梁として機能する。
我々の結論はまた、 Y の最小特異値の半径 1/3 の Y 中心の測地球はリーマン商幾何の下で設定された測地凸であり、これは圏として、バーレス=ヴァッサーシュタイン空間における凸半径の定量的な境界をも意味している、という独立な関心の結果に基づいている。
得られる凸半径は定数までシャープである。
関連論文リスト
- Intrinsic Bayesian Cramér-Rao Bound with an Application to Covariance Matrix Estimation [49.67011673289242]
本稿では, 推定パラメータが滑らかな多様体内にある推定問題に対して, 新たな性能境界を提案する。
これはパラメータ多様体の幾何学と推定誤差測度の本質的な概念を誘導する。
論文 参考訳（メタデータ） (2023-11-08T15:17:13Z) - Curvature-Independent Last-Iterate Convergence for Games on Riemannian
Manifolds [77.4346324549323]
本研究では, 多様体の曲率に依存しないステップサイズが, 曲率非依存かつ直線的最終点収束率を達成することを示す。
我々の知る限りでは、曲率非依存率や/または最終点収束の可能性はこれまでに検討されていない。
論文 参考訳（メタデータ） (2023-06-29T01:20:44Z) - Symmetry & Critical Points for Symmetric Tensor Decomposition Problems [6.650108973968032]
実対称テンソルをランク1項の和に分解する非最適化問題を考える。
使用法は、問題次元においてプーズ級数で表される臨界点の無限の族を構成するためのリッチ対称性構造から成り立っている。
すべての臨界点に対して生じる望ましくない現象は、対象関数の値によって増加する負のヘッセン固有値の数を懸念する。
論文 参考訳（メタデータ） (2023-06-13T16:25:30Z) - First-Order Algorithms for Min-Max Optimization in Geodesic Metric
Spaces [93.35384756718868]
min-maxアルゴリズムはユークリッド設定で解析されている。
指数関数法 (RCEG) が線形速度で最終収束を補正したことを証明した。
論文 参考訳（メタデータ） (2022-06-04T18:53:44Z) - Square Root Marginalization for Sliding-Window Bundle Adjustment [53.34552451834707]
実時間オドメトリーに適合する新しい正方形根のすべり窓束の調整法を提案する。
提案した平方根辺化は、ヘシアン上でのシュール補数(SC)の従来の使用と代数的に等価であることを示す。
実世界のデータセットにおける視覚的および視覚的慣性オドメトリーの評価は,提案した推定器がベースラインよりも36%高速であることを示す。
論文 参考訳（メタデータ） (2021-09-05T23:22:38Z) - Unified Representation of Geometric Primitives for Graph-SLAM
Optimization Using Decomposed Quadrics [12.096145632383418]
この研究は、高レベルの幾何学的プリミティブのパラメータ化問題に焦点を当てている。
まず、これらの幾何学的プリミティブの統一表現を、一貫した簡潔な定式化をもたらすエンフカドリックを用いて提示する。
シミュレーション実験では, 分解された定式化は, 基本パラメータ化よりも高い効率とロバスト性を有することが示された。
論文 参考訳（メタデータ） (2021-08-20T01:06:51Z) - Bayesian Quadrature on Riemannian Data Manifolds [79.71142807798284]
データに固有の非線形幾何学構造をモデル化する原則的な方法が提供される。
しかし、これらの演算は通常計算的に要求される。
特に、正規法則上の積分を数値計算するためにベイズ二次(bq)に焦点を当てる。
先行知識と活発な探索手法を両立させることで,BQは必要な評価回数を大幅に削減できることを示す。
論文 参考訳（メタデータ） (2021-02-12T17:38:04Z) - Riemannian Perspective on Matrix Factorization [6.85316573653194]
部分空間の間には主角の批判的概念が存在することを示す。
完全に観察された場合、測地線が凸状であり、その外にあるすべてのサドルが存在する。
論文 参考訳（メタデータ） (2021-02-01T16:12:07Z) - Global Riemannian Acceleration in Hyperbolic and Spherical Spaces [0.0]
第1次大域一階法によるユークリッド曲率の加速現象の研究
第一次方法は、加速勾配降下と同じ速度をユークリッド勾配で達成する。
論文 参考訳（メタデータ） (2020-12-07T12:09:30Z) - Convex Geometry and Duality of Over-parameterized Neural Networks [70.15611146583068]
有限幅2層ReLUネットワークの解析のための凸解析手法を開発した。
正規化学習問題に対する最適解が凸集合の極点として特徴づけられることを示す。
高次元では、トレーニング問題は無限に多くの制約を持つ有限次元凸問題としてキャストできることが示される。
論文 参考訳（メタデータ） (2020-02-25T23:05:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。