論文の概要: Fast Global Convergence for Low-rank Matrix Recovery via Riemannian
Gradient Descent with Random Initialization
- arxiv url: http://arxiv.org/abs/2012.15467v1
- Date: Thu, 31 Dec 2020 06:40:43 GMT
- ステータス: 処理完了
- システム内更新日: 2021-04-18 02:57:13.502434
- Title: Fast Global Convergence for Low-rank Matrix Recovery via Riemannian
Gradient Descent with Random Initialization
- Title（参考訳）: ランダム初期化を伴うリーマン勾配降下による低ランク行列回復のための高速大域収束
- Authors: Thomas Y. Hou, Zhenzhen Li, Ziyun Zhang
- Abstract要約: リーマン多様体上の低ランク行列回復問題のクラスに対するグローバルな挙動を分析する。
より単純な最小二乗函数に対して急激な臨界点が存在するという、低ランク行列多様体の既知の幾何学的性質を明らかにする。
我々の収束保証は、ほぼ最適でほぼ次元のないものであり、数値的な観察を完全に説明できる。
- 参考スコア（独自算出の注目度）: 3.0263650731957275
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this paper, we propose a new global analysis framework for a class of
low-rank matrix recovery problems on the Riemannian manifold. We analyze the
global behavior for the Riemannian optimization with random initialization. We
use the Riemannian gradient descent algorithm to minimize a least squares loss
function, and study the asymptotic behavior as well as the exact convergence
rate. We reveal a previously unknown geometric property of the low-rank matrix
manifold, which is the existence of spurious critical points for the simple
least squares function on the manifold. We show that under some assumptions,
the Riemannian gradient descent starting from a random initialization with high
probability avoids these spurious critical points and only converges to the
ground truth in nearly linear convergence rate, i.e.
$\mathcal{O}(\text{log}(\frac{1}{\epsilon})+ \text{log}(n))$ iterations to
reach an $\epsilon$-accurate solution. We use two applications as examples for
our global analysis. The first one is a rank-1 matrix recovery problem. The
second one is the Gaussian phase retrieval problem. The second example only
satisfies the weak isometry property, but has behavior similar to that of the
first one except for an extra saddle set. Our convergence guarantee is nearly
optimal and almost dimension-free, which fully explains the numerical
observations. The global analysis can be potentially extended to other data
problems with random measurement structures and empirical least squares loss
functions.
- Abstract（参考訳）: 本稿では,リーマン多様体上の低ランク行列回復問題のクラスに対する新しい大域的解析フレームワークを提案する。
ランダム初期化を用いたリーマン最適化の大域的挙動を解析する。
最小二乗損失関数を最小化するためにリーマン勾配降下アルゴリズムを使用し、漸近的挙動と正確な収束率について研究する。
低ランク行列多様体の以前は未知の幾何学的性質を明らかにし、これは多様体上の単純最小二乗函数に対する急激な臨界点の存在である。
いくつかの仮定の下では、確率の高い確率のランダムな初期化から始まるリーマン勾配降下はこれらの急激な臨界点を回避し、ほとんど線形収束率で基底真理に収束する。
$\mathcal{o}(\text{log}(\frac{1}{\epsilon})+ \text{log}(n))$ で$\epsilon$-accurate 解に到達する。
グローバル分析の例として2つのアプリケーションを使用します。
1つ目は rank-1 matrix recovery problem である。
2つ目はガウス位相探索問題である。
第二の例は弱等長性のみを満たすが、余分な鞍集合を除いて第一のものと類似した挙動を持つ。
我々の収束保証は、ほぼ最適であり、ほぼ次元のないものである。
大域解析は、ランダムな測定構造と経験的最小二乗損失関数を持つ他のデータ問題にも拡張できる。
関連論文リスト
- ADMM for Structured Fractional Minimization [7.9047096855236125]
我々は、数値化器が微分可能な関数を含むような、構造化された分数問題のクラスを考える。
本稿では,このクラスの問題に対して,最初の乗算器の交換法であるsf FADMMを紹介する。
論文 参考訳（メタデータ） (2024-11-12T02:50:12Z) - Riemannian Optimization for Non-convex Euclidean Distance Geometry with Global Recovery Guarantees [6.422262171968397]
ユークリッド距離幾何学問題を解くために2つのアルゴリズムが提案されている。
第一のアルゴリズムは真の解に線形に収束する。
第2のアルゴリズムは、合成データと実データの両方で強い数値性能を示す。
論文 参考訳（メタデータ） (2024-10-08T21:19:22Z) - 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) - Rank-1 Matrix Completion with Gradient Descent and Small Random
Initialization [15.127728811011245]
我々は,GDの暗黙的正規化が分析において重要な役割を担っていることを示す。
我々は、手頃な分析において暗黙の正規化GDが重要な役割を担っていることを観察する。
論文 参考訳（メタデータ） (2022-12-19T12:05:37Z) - Randomized Coordinate Subgradient Method for Nonsmooth Composite
Optimization [11.017632675093628]
非滑らかな問題に対処するコーディネート型劣階法は、リプシッツ型仮定の性質のセットのため、比較的過小評価されている。
論文 参考訳（メタデータ） (2022-06-30T02:17:11Z) - Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix
Factorization [49.090785356633695]
非対称な低ランク分解問題: [mathbbRm min d , mathbfU$ および MathV$ について検討する。
論文 参考訳（メタデータ） (2021-06-27T17:25:24Z) - Proximal Gradient Descent-Ascent: Variable Convergence under K{\L}
Geometry [49.65455534654459]
有限降下指数パラメータ (GDA) はミニマックス最適化問題の解法として広く応用されている。
本稿では、KL-L型幾何学の収束を研究することにより、そのようなギャップを埋める。
論文 参考訳（メタデータ） (2021-02-09T05:35:53Z) - ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。
我々は,過去の勾配を平均化し,実装が容易な小説「Recursive One-Over-T SGD」を考案した。
有限サンプル, 漸近感覚, 感覚の両面において, 最先端の性能を同時に達成できることを実証する。
論文 参考訳（メタデータ） (2020-08-28T14:46:56Z) - Convergence Analysis of Riemannian Stochastic Approximation Schemes [39.32179384256228]
本稿では,最適化問題に取り組むための相関近似 (SA) スキームのクラスを解析する。
得られた条件は, 従来よりかなり軽度であることを示す。
第3に、平均場関数を小さなバイアスにしか推定できない場合、および/または、サンプルが鎖から引き出される場合を考える。
論文 参考訳（メタデータ） (2020-05-27T11:24:58Z) - Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。
特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
論文 参考訳（メタデータ） (2020-02-10T23:23:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。