  It is believed that Gradient Descent (GD) induces an implicit bias towards
good generalization in training machine learning models. This paper provides a
fine-grained analysis of the dynamics of GD for the matrix sensing problem,
whose goal is to recover a low-rank ground-truth matrix from near-isotropic
linear measurements. It is shown that GD with small initialization behaves
similarly to the greedy low-rank learning heuristics (Li et al., 2020) and
follows an incremental learning procedure (Gissin et al., 2019): GD
sequentially learns solutions with increasing ranks until it recovers the
ground truth matrix. Compared to existing works which only analyze the first
learning phase for rank-1 solutions, our result provides characterizations for
the whole learning process. Moreover, besides the over-parameterized regime
that many prior works focused on, our analysis of the incremental learning
procedure also applies to the under-parameterized regime. Finally, we conduct
numerical experiments to confirm our theoretical findings.
