Towards Resolving the Implicit Bias of Gradient Descent for Matrix
  Factorization: Greedy Low-Rank Learning
  Matrix factorization is a simple and natural test-bed to investigate the
implicit regularization of gradient descent. Gunasekar et al. (2017)
conjectured that Gradient Flow with infinitesimal initialization converges to
the solution that minimizes the nuclear norm, but a series of recent papers
argued that the language of norm minimization is not sufficient to give a full
characterization for the implicit regularization. In this work, we provide
theoretical and empirical evidence that for depth-2 matrix factorization,
gradient flow with infinitesimal initialization is mathematically equivalent to
a simple heuristic rank minimization algorithm, Greedy Low-Rank Learning, under
some reasonable assumptions. This generalizes the rank minimization view from
previous works to a much broader setting and enables us to construct
counter-examples to refute the conjecture from Gunasekar et al. (2017). We also
extend the results to the case where depth $\ge 3$, and we show that the
benefit of being deeper is that the above convergence has a much weaker
dependence over initialization magnitude so that this rank minimization is more
likely to take effect for initialization with practical scale.
