Nonconvex Rectangular Matrix Completion via Gradient Descent Without <i>ℓ</i>₂,<sub>∞</sub> Regularization
Chen Ji, Dekai Liu, Xiaodong Li
Abstract
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 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\ell _{2,\infty }$ </tex-math></inline-formula> projection or regularization that involves unknown model parameters, although they are observed to be unnecessary in numerical simulations. In this paper, we extend the analysis of the vanilla gradient descent for positive semidefinite matrix completion in the literature to the rectangular case, and more significantly, improve the required sampling rate from <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$O(\mathrm {poly}(\kappa )\mu ^{3}~r^{3} \log ^{3}~n/n )$ </tex-math></inline-formula> to <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$O(\mu ^{2}~r^{2} \kappa ^{14} \log n/n )$ </tex-math></inline-formula> . Our technical ideas and contributions are potentially useful in improving the leave-one-out analysis in other related problems.