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.

对称矩阵完成问题的研究表明，使用小初始化的梯度下降算法可以无需显式正则化地收敛到真实解，即使在过参数优化情况下也成立；同时，初始点越小，解的精确度越高。针对该问题的全局收敛性分析借助了一种新颖的弱耦合一致性评估方法，拓展了经典的留一法分析范畴。