  Matrix factorization models have been extensively studied as a valuable
test-bed for understanding the implicit biases of overparameterized models.
Although both low nuclear norm and low rank regularization have been studied
for these models, a unified understanding of when, how, and why they achieve
different implicit regularization effects remains elusive. In this work, we
systematically investigate the implicit regularization of matrix factorization
for solving matrix completion problems. We empirically discover that the
connectivity of observed data plays a crucial role in the implicit bias, with a
transition from low nuclear norm to low rank as data shifts from disconnected
to connected with increased observations. We identify a hierarchy of intrinsic
invariant manifolds in the loss landscape that guide the training trajectory to
evolve from low-rank to higher-rank solutions. Based on this finding, we
theoretically characterize the training trajectory as following the
hierarchical invariant manifold traversal process, generalizing the
characterization of Li et al. (2020) to include the disconnected case.
Furthermore, we establish conditions that guarantee minimum nuclear norm,
closely aligning with our experimental findings, and we provide a dynamics
characterization condition for ensuring minimum rank. Our work reveals the
intricate interplay between data connectivity, training dynamics, and implicit
regularization in matrix factorization models.
