論文の概要: Convergence of Gradient Descent with Small Initialization for
Unregularized Matrix Completion
- arxiv url: http://arxiv.org/abs/2402.06756v1
- Date: Fri, 9 Feb 2024 19:39:23 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-13 19:35:25.267128
- Title: Convergence of Gradient Descent with Small Initialization for
Unregularized Matrix Completion
- Title（参考訳）: 非正規化行列完了のための小初期化による勾配降下の収束
- Authors: Jianhao Ma, Salar Fattahi
- Abstract要約: バニラ勾配降下は、明示的な正則化を必要とせず、必ず基底真理$rmXstar$に収束することを示す。
驚くべきことに、収束率も最終的な精度もオーバーパラメータ化された検索ランク$r'$に依存しておらず、それらは真のランク$r$によってのみ支配される。
- 参考スコア（独自算出の注目度）: 21.846732043706318
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the problem of symmetric matrix completion, where the goal is to
reconstruct a positive semidefinite matrix $\rm{X}^\star \in
\mathbb{R}^{d\times d}$ of rank-$r$, parameterized by $\rm{U}\rm{U}^{\top}$,
from only a subset of its observed entries. We show that the vanilla gradient
descent (GD) with small initialization provably converges to the ground truth
$\rm{X}^\star$ without requiring any explicit regularization. This convergence
result holds true even in the over-parameterized scenario, where the true rank
$r$ is unknown and conservatively over-estimated by a search rank $r'\gg r$.
The existing results for this problem either require explicit regularization, a
sufficiently accurate initial point, or exact knowledge of the true rank $r$.
In the over-parameterized regime where $r'\geq r$, we show that, with
$\widetilde\Omega(dr^9)$ observations, GD with an initial point $\|\rm{U}_0\|
\leq \epsilon$ converges near-linearly to an $\epsilon$-neighborhood of
$\rm{X}^\star$. Consequently, smaller initial points result in increasingly
accurate solutions. Surprisingly, neither the convergence rate nor the final
accuracy depends on the over-parameterized search rank $r'$, and they are only
governed by the true rank $r$. In the exactly-parameterized regime where
$r'=r$, we further enhance this result by proving that GD converges at a faster
rate to achieve an arbitrarily small accuracy $\epsilon>0$, provided the
initial point satisfies $\|\rm{U}_0\| = O(1/d)$. At the crux of our method lies
a novel weakly-coupled leave-one-out analysis, which allows us to establish the
global convergence of GD, extending beyond what was previously possible using
the classical leave-one-out analysis.
- Abstract（参考訳）: 対称行列完全化の問題を考察し, 正の半定義行列 $\rm{x}^\star \in \mathbb{r}^{d\times d}$ of rank-$r$, $\rm{u}\rm{u}^{\top}$ でパラメータ化され, 観測されたエントリのサブセットのみから正の半定義行列 $\rm{x}^\star \in \mathbb{r}^{d\times d}$ を再構成する。
小さい初期化を持つバニラ勾配降下(GD)は、明示的な正則化を必要とせず、必ず基底真理$\rm{X}^\star$に収束することを示す。
この収束の結果は、真のランク $r$ が未知であり、検索ランク $r'\gg r$ によって保守的に過大評価される過パラメータなシナリオにおいても真である。
この問題の既存の結果は、明示的な正則化、十分正確な初期点、あるいは真階数$r$の正確な知識を必要とする。
r'\geq r$ の超パラメータ状態において、$\widetilde\omega(dr^9)$ の観測では、初期点 $\|\rm{u}_0\| \leq \epsilon$ が近似的に $\epsilon$-neighborhood of $\rm{x}^\star$ に収束する。
その結果、より小さな初期点がより正確な解をもたらす。
驚くべきことに、収束率や最終的な精度は、過剰にパラメータ化された検索ランク $r'$ に依存しておらず、真のランク $r$ によってのみ制御される。
r'=r$ の正確なパラメータ化では、初期点が $\|\rm{u}_0\| = o(1/d)$ を満たす場合、gd がより速い速度で収束し、任意に小さい精度の $\epsilon>0$ を達成することを証明し、この結果をさらに強化する。
提案手法の要点は,GDのグローバルコンバージェンスを確立するために,従来のLeft-one-out解析で可能であった範囲を超えて,新たなLeft-one-out解析が導入されたことである。
関連論文リスト
- How Over-Parameterization Slows Down Gradient Descent in Matrix Sensing:
The Curses of Symmetry and Initialization [46.55524654398093]
過パラメータ化が降下の収束挙動をどのように変化させるかを示す。
目的は、ほぼ等方的線形測定から未知の低ランクの地上構造行列を復元することである。
本稿では,GDの一段階だけを修飾し,$alpha$に依存しない収束率を求める手法を提案する。
論文 参考訳（メタデータ） (2023-10-03T03:34:22Z) - A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳（メタデータ） (2023-09-25T17:54:19Z) - Convergence of a Normal Map-based Prox-SGD Method under the KL
Inequality [0.0]
我々は、$symbol$k$収束問題に対して、新しいマップベースのアルゴリズム(mathsfnorMtext-mathsfSGD$)を提案する。
論文 参考訳（メタデータ） (2023-05-10T01:12:11Z) - Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
我々は,行列がゆっくりと変化している動的環境において,正確なトレース推定に必要な行列ベクトルクエリ数を最小化する問題を考える。
我々は、$delta$失敗確率で$epsilon$エラーまで、すべての$m$トレースを同時に推定する新しいバイナリツリー要約手順を提供する。
我々の下界(1)は、静的な設定においてもフロベニウスノルム誤差を持つ行列ベクトル積モデルにおけるハッチンソン推定子の第一の厳密な境界を与え、(2)動的トレース推定のための最初の無条件下界を与える。
論文 参考訳（メタデータ） (2022-09-30T04:15:44Z) - Improved Global Guarantees for the Nonconvex Burer--Monteiro Factorization via Rank Overparameterization [10.787390511207683]
二つの微分可能な$L$-smooth, $mu$-strongly convex objective $phimph over a $ntimes n$frac14(L/mu-1)2rstar$を考える。
非局所性にもかかわらず、局所最適化は、任意の初期点から大域的最適点へグローバルに収束することが保証される。
論文 参考訳（メタデータ） (2022-07-05T03:18:17Z) - Preconditioned Gradient Descent for Overparameterized Nonconvex
Burer--Monteiro Factorization with Global Optimality Certification [14.674494335647841]
非函数 $f(X)=phi(XXT)$ を$ntimes r$ factor matrix $X$ で最小化するために勾配降下を考える。
本稿では,勾配降下の収束率を線形に戻すための安価なプレコンディショナーを提案する。
論文 参考訳（メタデータ） (2022-06-07T14:26:49Z) - Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
我々は、任意のSchatten-$p$ノルムの下で、低ランク近似のためのクリロフ部分空間に基づく反復法について研究する。
我々の主な成果は、$tildeO(k/sqrtepsilon)$ matrix-vector productのみを使用するアルゴリズムである。
論文 参考訳（メタデータ） (2022-02-10T16:10:41Z) - Improved Sample Complexity for Incremental Autonomous Exploration in
MDPs [132.88757893161699]
我々は $epsilon$-optimal 目標条件付きポリシーのセットを学び、$ L$ ステップ内で段階的に到達可能なすべての状態を達成します。
DisCoは、コストに敏感な最短経路問題に対して$epsilon/c_min$-optimalポリシーを返すことができる最初のアルゴリズムです。
論文 参考訳（メタデータ） (2020-12-29T14:06:09Z) - Sparse sketches with small inversion bias [79.77110958547695]
逆バイアスは、逆の共分散に依存する量の推定を平均化するときに生じる。
本研究では、確率行列に対する$(epsilon,delta)$-unbiased estimatorという概念に基づいて、逆バイアスを解析するためのフレームワークを開発する。
スケッチ行列 $S$ が密度が高く、すなわちサブガウスのエントリを持つとき、$(epsilon,delta)$-unbiased for $(Atop A)-1$ は $m=O(d+sqrt d/ のスケッチを持つ。
論文 参考訳（メタデータ） (2020-11-21T01:33:15Z) - Accelerating Optimization and Reinforcement Learning with
Quasi-Stochastic Approximation [2.294014185517203]
本稿では、収束理論を準確率近似に拡張することを目的とする。
強化学習のためのグラデーションフリー最適化とポリシー勾配アルゴリズムへの応用について説明する。
論文 参考訳（メタデータ） (2020-09-30T04:44:45Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。