論文の概要: Fast global convergence of gradient descent for low-rank matrix
approximation
- arxiv url: http://arxiv.org/abs/2305.19206v1
- Date: Tue, 30 May 2023 16:55:34 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-31 14:56:55.736123
- Title: Fast global convergence of gradient descent for low-rank matrix
approximation
- Title(参考訳): 低ランク行列近似に対する勾配降下の高速大域収束
- Authors: Hengchao Chen, Xin Chen, Mohamad Elmasri, Qiang Sun
- Abstract要約: 我々は、特に小さなランダム値で達成された場合、勾配降下の急速な大域収束を証明した。
我々は,非対称行列近似問題に対処するために解析を拡張し,リトラクションフリーな固有空間計算法の有効性について検討する。
- 参考スコア(独自算出の注目度): 3.8725717612267774
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper investigates gradient descent for solving low-rank matrix
approximation problems. We begin by establishing the local linear convergence
of gradient descent for symmetric matrix approximation. Building on this
result, we prove the rapid global convergence of gradient descent, particularly
when initialized with small random values. Remarkably, we show that even with
moderate random initialization, which includes small random initialization as a
special case, gradient descent achieves fast global convergence in scenarios
where the top eigenvalues are identical. Furthermore, we extend our analysis to
address asymmetric matrix approximation problems and investigate the
effectiveness of a retraction-free eigenspace computation method. Numerical
experiments strongly support our theory. In particular, the retraction-free
algorithm outperforms the corresponding Riemannian gradient descent method,
resulting in a significant 29\% reduction in runtime.
- Abstract(参考訳): 本稿では,低ランク行列近似問題の解法における勾配勾配について検討する。
まず、対称行列近似に対する勾配降下の局所線型収束を確立することから始める。
この結果に基づき, 勾配降下の急速大域収束を, 特に小さなランダム値で初期化した場合に証明する。
特例として小さなランダム初期化を含む適度なランダム初期化であっても、勾配降下は、最上位固有値が同一のシナリオにおいて高速な大域収束を達成する。
さらに,非対称行列近似問題に対する解析を拡張し,レトラクションフリー固有空間計算法の有効性について検討する。
数値実験は我々の理論を強く支持する。
特に、retraction-freeアルゴリズムは対応するリーマン勾配降下法を上回り、その結果、実行時間の29\%減少する。
関連論文リスト
- Asymmetric matrix sensing by gradient descent with small random
initialization [0.8611782340880084]
いくつかの線形測定値から低ランク行列を再構成する問題について検討する。
私たちの重要な貢献は、$texted gradient flow$と呼ぶ連続的な勾配流方程式の導入です。
論文 参考訳(メタデータ) (2023-09-04T20:23:35Z) - Curvature-Independent Last-Iterate Convergence for Games on Riemannian
Manifolds [77.4346324549323]
本研究では, 多様体の曲率に依存しないステップサイズが, 曲率非依存かつ直線的最終点収束率を達成することを示す。
我々の知る限りでは、曲率非依存率や/または最終点収束の可能性はこれまでに検討されていない。
論文 参考訳(メタデータ) (2023-06-29T01:20:44Z) - Asymptotically efficient one-step stochastic gradient descent [62.997667081978825]
これはフィッシャースコアリングアルゴリズムの単一ステップで補正された対数型関数の勾配勾配に基づいている。
理論的およびシミュレーションにより、これは平均勾配あるいは適応勾配勾配の通常の勾配勾配の代替として興味深いものであることをi.d設定で示す。
論文 参考訳(メタデータ) (2023-06-09T13:43:07Z) - Min-Max Optimization Made Simple: Approximating the Proximal Point
Method via Contraction Maps [77.8999425439444]
本稿では,凸/凹凸 min-max 問題に対して,ほぼ最適収束率を許容する一階法を提案する。
我々の研究は、近点法の更新規則を精度良く近似できるという事実に基づいている。
論文 参考訳(メタデータ) (2023-01-10T12:18:47Z) - Algorithmic Regularization in Model-free Overparametrized Asymmetric
Matrix Factorization [16.325663190517773]
我々は、任意の過パラメータ化を持つ自然な非定式化の下で、非対称な分解問題を考察する。
観測された行列に対して最高の低ランク近似を生成する。
論文 参考訳(メタデータ) (2022-03-06T00:07:53Z) - 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) - Small random initialization is akin to spectral learning: Optimization
and generalization guarantees for overparameterized low-rank matrix
reconstruction [35.585697639325105]
本稿では,小さなランダム初期化が完全には理解されていないことを示す。
我々は、小さな乱数行列から勾配を再構成し、低い乱数行列から最適勾配に類似した解を求める。
論文 参考訳(メタデータ) (2021-06-28T22:52:39Z) - Exact Linear Convergence Rate Analysis for Low-Rank Symmetric Matrix
Completion via Gradient Descent [22.851500417035947]
因数分解に基づく勾配降下は、因数分解行列の完備化を解くためのスケーラブルで効率的なアルゴリズムである。
勾配勾配降下は, 地球自然問題の解を推定するために, 高速収束を楽しむことを示す。
論文 参考訳(メタデータ) (2021-02-04T03:41:54Z) - Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box
Optimization Framework [100.36569795440889]
この作業は、一階情報を必要としない零次最適化(ZO)の反復である。
座標重要度サンプリングにおける優雅な設計により,ZO最適化法は複雑度と関数クエリコストの両面において効率的であることを示す。
論文 参考訳(メタデータ) (2020-12-21T17:29:58Z) - Understanding Implicit Regularization in Over-Parameterized Single Index
Model [55.41685740015095]
我々は高次元単一インデックスモデルのための正規化自由アルゴリズムを設計する。
暗黙正則化現象の理論的保証を提供する。
論文 参考訳(メタデータ) (2020-07-16T13:27:47Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。