Abstract
Recent efforts to unravel the mystery of implicit regularization in deeplearning have led to a theoretical focus on matrix factorization -- matrixcompletion via linear neural network. As a step further towards practical deeplearning, we provide the first theoretical analysis of implicit regularizationin tensor factorization -- tensor completion via certain type of non-linearneural network. We circumvent the notorious difficulty of tensor problems byadopting a dynamical systems perspective, and characterizing the evolutioninduced by gradient descent. The characterization suggests a form of greedy lowtensor rank search, which we rigorously prove under certain conditions, andempirically demonstrate under others. Motivated by tensor rank capturing theimplicit regularization of a non-linear neural network, we empirically exploreit as a measure of complexity, and find that it captures the essence ofdatasets on which neural networks generalize. This leads us to believe thattensor rank may pave way to explaining both implicit regularization in deeplearning, and the properties of real-world data translating this implicitregularization to generalization.