  We study the asymmetric matrix factorization problem under a natural
nonconvex formulation with arbitrary overparametrization. The model-free
setting is considered, with minimal assumption on the rank or singular values
of the observed matrix, where the global optima provably overfit. We show that
vanilla gradient descent with small random initialization sequentially recovers
the principal components of the observed matrix. Consequently, when equipped
with proper early stopping, gradient descent produces the best low-rank
approximation of the observed matrix without explicit regularization. We
provide a sharp characterization of the relationship between the approximation
error, iteration complexity, initialization size and stepsize. Our complexity
bound is almost dimension-free and depends logarithmically on the approximation
error, with significantly more lenient requirements on the stepsize and
initialization compared to prior work. Our theoretical results provide accurate
prediction for the behavior gradient descent, showing good agreement with
numerical experiments.
