論文の概要: Exact Linear Convergence Rate Analysis for Low-Rank Symmetric Matrix
Completion via Gradient Descent
- arxiv url: http://arxiv.org/abs/2102.02396v2
- Date: Sat, 6 Feb 2021 03:55:14 GMT
- ステータス: 処理完了
- システム内更新日: 2021-02-09 10:11:40.346152
- Title: Exact Linear Convergence Rate Analysis for Low-Rank Symmetric Matrix
Completion via Gradient Descent
- Title（参考訳）: 勾配降下による低ランク対称行列の完全線形収束速度解析
- Authors: Trung Vu and Raviv Raich
- Abstract要約: 因数分解に基づく勾配降下は、因数分解行列の完備化を解くためのスケーラブルで効率的なアルゴリズムである。
勾配勾配降下は, 地球自然問題の解を推定するために, 高速収束を楽しむことを示す。
- 参考スコア（独自算出の注目度）: 22.851500417035947
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Factorization-based gradient descent is a scalable and efficient algorithm
for solving low-rank matrix completion. Recent progress in structured
non-convex optimization has offered global convergence guarantees for gradient
descent under certain statistical assumptions on the low-rank matrix and the
sampling set. However, while the theory suggests gradient descent enjoys fast
linear convergence to a global solution of the problem, the universal nature of
the bounding technique prevents it from obtaining an accurate estimate of the
rate of convergence. In this paper, we perform a local analysis of the exact
linear convergence rate of gradient descent for factorization-based matrix
completion for symmetric matrices. Without any additional assumptions on the
underlying model, we identify the deterministic condition for local convergence
of gradient descent, which only depends on the solution matrix and the sampling
set. More crucially, our analysis provides a closed-form expression of the
asymptotic rate of convergence that matches exactly with the linear convergence
observed in practice. To the best of our knowledge, our result is the first one
that offers the exact rate of convergence of gradient descent for matrix
factorization in Euclidean space for matrix completion.
- Abstract（参考訳）: ファクタリゼーションベースの勾配降下は、低ランクマトリックスの完了を解決するためのスケーラブルで効率的なアルゴリズムです。
構造的非凸最適化の最近の進歩は、低ランク行列とサンプリングセットの特定の統計的仮定の下で、勾配降下のグローバル収束を保証する。
しかし、この理論は、勾配降下が問題の大域的な解に対する高速線型収束を楽しむことを示唆する一方で、境界技術の普遍性は収束率の正確な推定値を得るのを妨げている。
本稿では,対称行列に対する因子分解に基づく行列完成のための勾配降下の完全線形収束率を局所的に解析する。
基礎となるモデルに関する追加の仮定がなければ、解行列とサンプリングセットのみに依存する勾配降下の局所収束の決定論的条件を特定することができる。
さらに重要なことに、我々の分析は、実際に観測された線形収束と正確に一致する漸近収束率の閉形式表現を提供する。
我々の知る限りでは、行列完備化のためにユークリッド空間における行列分解に対する勾配降下の正確な収束率を与える最初の結果である。
関連論文リスト
- Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
本稿では,ニューラルネットワークトレーニングを安定化(大規模)するための原理的手法として,線形アヘッドの理論解析を提案する。
最適化過程の不安定性は、しばしば損失ランドスケープの非単調性によって引き起こされるものであり、非拡張作用素の理論を活用することによって線型性がいかに役立つかを示す。
論文 参考訳（メタデータ） (2023-10-20T12:45:12Z) - Asymmetric matrix sensing by gradient descent with small random
initialization [0.8611782340880084]
いくつかの線形測定値から低ランク行列を再構成する問題について検討する。
私たちの重要な貢献は、$texted gradient flow$と呼ぶ連続的な勾配流方程式の導入です。
論文 参考訳（メタデータ） (2023-09-04T20:23:35Z) - Convex and Non-convex Optimization Under Generalized Smoothness [69.69521650503431]
凸法と非最適化法の分析は、しばしばリプシッツ勾配を必要とし、この軌道による解析を制限する。
最近の研究は、非一様滑らか性条件を通した勾配設定を一般化している。
論文 参考訳（メタデータ） (2023-06-02T04:21:59Z) - Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector
Problems [98.34292831923335]
オンライン相関解析の問題から,emphStochastic Scaled-Gradient Descent (SSD)アルゴリズムを提案する。
我々はこれらのアイデアをオンライン相関解析に適用し、局所収束率を正規性に比例した最適な1時間スケールのアルゴリズムを初めて導いた。
論文 参考訳（メタデータ） (2021-12-29T18:46:52Z) - On Asymptotic Linear Convergence of Projected Gradient Descent for
Constrained Least Squares [22.851500417035947]
この写本は、制約最小二乗の文脈における射影勾配降下の解析のための統一的な枠組みを提示する。
本稿では,PGDの収束解析のレシピを提示し,このレシピを4つの基本的な問題に応用して実証する。
論文 参考訳（メタデータ） (2021-12-22T09:49:51Z) - Beyond Procrustes: Balancing-Free Gradient Descent for Asymmetric
Low-Rank Matrix Sensing [36.96922859748537]
低ランク行列推定は、科学と工学のさまざまなアプリケーションで中心的な役割を果たします。
既存のアプローチは、2つの行列因子のスケールのバランスをとるために計量正規化項を加えることに頼っている。
本論文では,低ランク行列の線形測定値の少ない値から回復する性能の理論的正当化について述べる。
論文 参考訳（メタデータ） (2021-01-13T15:03:52Z) - Understanding Implicit Regularization in Over-Parameterized Single Index
Model [55.41685740015095]
我々は高次元単一インデックスモデルのための正規化自由アルゴリズムを設計する。
暗黙正則化現象の理論的保証を提供する。
論文 参考訳（メタデータ） (2020-07-16T13:27:47Z) - Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled
Gradient Descent [34.0533596121548]
低ランク行列推定は凸問題を収束させ、信号処理、機械学習、画像科学に多くの応用を見出す。
低ランク行列の個数の観点から,ScaledGDが最良となることを示す。
我々の分析は、低ランク勾配降下に類似した一般損失にも適用できる。
論文 参考訳（メタデータ） (2020-05-18T17:17:16Z) - Nonconvex Matrix Completion with Linearly Parameterized Factors [10.163102766021373]
パラメトリック因子化は、部分空間や完了シミュレーションを含む重要な例を示す。
また, 統一的非制約行列最適化法の有効性について述べる。
論文 参考訳（メタデータ） (2020-03-29T22:40:47Z) - On the Convergence of Adaptive Gradient Methods for Nonconvex Optimization [80.03647903934723]
我々は、勾配収束法を期待する適応勾配法を証明した。
解析では、非理解勾配境界の最適化において、より適応的な勾配法に光を当てた。
論文 参考訳（メタデータ） (2018-08-16T20:25:28Z) - Relative Error Bound Analysis for Nuclear Norm Regularized Matrix Completion [101.83262280224729]
我々は、原子核ノルム正規化行列補完に対する相対誤差を開発する。
未知行列の最適低ランク近似を回復するための相対上界を導出する。
論文 参考訳（メタデータ） (2015-04-26T13:12:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。