論文の概要: Rank-1 Matrix Completion with Gradient Descent and Small Random
Initialization
- arxiv url: http://arxiv.org/abs/2212.09396v1
- Date: Mon, 19 Dec 2022 12:05:37 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-20 15:43:24.813927
- Title: Rank-1 Matrix Completion with Gradient Descent and Small Random
Initialization
- Title(参考訳): 勾配降下と小乱数初期化を伴うrank-1行列補完
- Authors: Daesung Kim and Hye Won Chung
- Abstract要約: 我々は,GDの暗黙的正規化が分析において重要な役割を担っていることを示す。
我々は、手頃な分析において暗黙の正規化GDが重要な役割を担っていることを観察する。
- 参考スコア(独自算出の注目度): 15.127728811011245
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The nonconvex formulation of matrix completion problem has received
significant attention in recent years due to its affordable complexity compared
to the convex formulation. Gradient descent (GD) is the simplest yet efficient
baseline algorithm for solving nonconvex optimization problems. The success of
GD has been witnessed in many different problems in both theory and practice
when it is combined with random initialization. However, previous works on
matrix completion require either careful initialization or regularizers to
prove the convergence of GD. In this work, we study the rank-1 symmetric matrix
completion and prove that GD converges to the ground truth when small random
initialization is used. We show that in logarithmic amount of iterations, the
trajectory enters the region where local convergence occurs. We provide an
upper bound on the initialization size that is sufficient to guarantee the
convergence and show that a larger initialization can be used as more samples
are available. We observe that implicit regularization effect of GD plays a
critical role in the analysis, and for the entire trajectory, it prevents each
entry from becoming much larger than the others.
- Abstract(参考訳): 行列完備化問題の非凸定式化は,近年,凸定式化と比較して手頃な複雑さのため,大きな注目を集めている。
勾配降下(GD)は非凸最適化問題の解法として最も単純だが効率的なベースラインアルゴリズムである。
GDの成功は、ランダム初期化と組み合わせることで、理論と実践の両方において多くの異なる問題で見られた。
しかしながら、行列完全性に関する以前の研究では、gd の収束を証明するために注意深い初期化または正規化が必要である。
本研究では,rank-1対称行列の完全性を研究し,小さなランダム初期化を用いた場合,gd が基底真理に収束することを示す。
対数的な反復量では、軌道は局所収束が起こる領域に入る。
我々は、収束を保証するのに十分な初期化サイズの上界を提供し、より多くのサンプルが利用できるので、より大きな初期化が使用できることを示す。
gdの暗黙的正規化効果は解析において重要な役割を担っており、軌道全体において、各エントリが他よりも大きくなることを防ぐ。
関連論文リスト
- Fast global convergence of gradient descent for low-rank matrix
approximation [3.8725717612267774]
我々は、特に小さなランダム値で達成された場合、勾配降下の急速な大域収束を証明した。
我々は,非対称行列近似問題に対処するために解析を拡張し,リトラクションフリーな固有空間計算法の有効性について検討する。
論文 参考訳(メタデータ) (2023-05-30T16:55:34Z) - Alternating minimization for generalized rank one matrix sensing: Sharp
predictions from a random initialization [10.516962652888989]
ランクランダム行列の特性をdで推定する手法を示す。
鋭い収束は、単一のステップで正確な回復を保証する。
我々の分析は、この問題の他のいくつかの特性も明らかにしている。
論文 参考訳(メタデータ) (2022-07-20T05:31:05Z) - Randomly Initialized Alternating Least Squares: Fast Convergence for
Matrix Sensing [9.264464791978362]
Alternating Least Squares (ALS) は $O(log n + log (1/varepsilon)) $ iterations において $varepsilon$-accuracy で真の解に収束することを示す。
我々の証明の鍵となるのは、ALSの軌道が反復する観察は、ランダムな測定行列の特定のエントリのみに非常に軽度に依存することである。
論文 参考訳(メタデータ) (2022-04-25T08:55:38Z) - Distributed stochastic optimization with large delays [59.95552973784946]
大規模最適化問題を解決する最も広く使われている手法の1つは、分散非同期勾配勾配(DASGD)である。
DASGDは同じ遅延仮定の下で大域的最適実装モデルに収束することを示す。
論文 参考訳(メタデータ) (2021-07-06T21:59:49Z) - Benign Overfitting of Constant-Stepsize SGD for Linear Regression [122.70478935214128]
帰納バイアスは 経験的に過剰フィットを防げる中心的存在です
この研究は、この問題を最も基本的な設定として考慮している: 線形回帰に対する定数ステップサイズ SGD。
我々は、(正規化されていない)SGDで得られるアルゴリズム正則化と、通常の最小二乗よりも多くの顕著な違いを反映する。
論文 参考訳(メタデータ) (2021-03-23T17:15:53Z) - Fast Global Convergence for Low-rank Matrix Recovery via Riemannian
Gradient Descent with Random Initialization [3.0263650731957275]
リーマン多様体上の低ランク行列回復問題のクラスに対するグローバルな挙動を分析する。
より単純な最小二乗函数に対して急激な臨界点が存在するという、低ランク行列多様体の既知の幾何学的性質を明らかにする。
我々の収束保証は、ほぼ最適でほぼ次元のないものであり、数値的な観察を完全に説明できる。
論文 参考訳(メタデータ) (2020-12-31T06:40:43Z) - ROOT-SGD: Sharp Nonasymptotics and Asymptotic Efficiency in a Single
Algorithm [77.71051081132912]
第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。
emphRecursive One-Over-T Root (ROOTSGD) と呼ばれる小説を考案する。
有限サンプル勾配, 漸近感覚, 感覚を同時に達成することを証明する。
論文 参考訳(メタデータ) (2020-08-28T14:46:56Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳(メタデータ) (2020-08-23T20:36:49Z) - Provably Convergent Working Set Algorithm for Non-Convex Regularized
Regression [0.0]
本稿では、収束保証付き非正則正規化器のためのワーキングセットアルゴリズムを提案する。
その結果,ブロックコーディネートや勾配ソルバの完全解法と比較して高い利得を示した。
論文 参考訳(メタデータ) (2020-06-24T07:40:31Z) - Effective Dimension Adaptive Sketching Methods for Faster Regularized
Least-Squares Optimization [56.05635751529922]
スケッチに基づくL2正規化最小二乗問題の解法を提案する。
我々は、最も人気のあるランダム埋め込みの2つ、すなわちガウス埋め込みとサブサンプリングランダム化アダマール変換(SRHT)を考える。
論文 参考訳(メタデータ) (2020-06-10T15:00:09Z) - Optimal Iterative Sketching with the Subsampled Randomized Hadamard
Transform [64.90148466525754]
最小二乗問題に対する反復スケッチの性能について検討する。
本研究では、Haar行列とランダム化されたHadamard行列の収束速度が同一であることを示し、ランダムなプロジェクションを経時的に改善することを示した。
これらの手法は、ランダム化次元還元を用いた他のアルゴリズムにも適用することができる。
論文 参考訳(メタデータ) (2020-02-03T16:17:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。