The analysis of nonconvex matrix completion has recently attracted much
attention in the community of machine learning thanks to its computational
convenience. Existing analysis on this problem, however, usually relies on
$\ell_{2,\infty}$ projection or regularization that involves unknown model
parameters, although they are observed to be unnecessary in numerical
simulations, see, e.g., Zheng and Lafferty [2016]. In this paper, we extend the
analysis of the vanilla gradient descent for positive semidefinite matrix
completion proposed in Ma et al. [2017] to the rectangular case, and more
significantly, improve the required sampling rate from
$O(\operatorname{poly}(\kappa)\mu^3 r^3 \log^3 n/n )$ to $O(\mu^2 r^2
\kappa^{14} \log n/n )$. Our technical ideas and contributions are potentially
useful in improving the leave-one-out analysis in other related problems.

本文介绍了如何通过改进梯度下降的技术和方法，将矩阵填充的采样率由 O (poly (条件数)*mu^3*r^3*log^3n/n) 降低至 O (mu^2*r^2 * 条件数 ^14*log (n)/n)，并且这些技术和方法在改善其他相关问题的分析方面也具有潜在的用处。