Algorithmic Regularization in Over-parameterized Matrix Sensing and Neural Networks with Quadratic Activations

We show that the gradient descent algorithm provides an implicit effect in the learning of over-parameterized matrix models and one-hidden-layer neural networks with quadratic. Concretely, we show that given ̃(dr²) random linear of a rank r positive semidefinite matrix X\, we can X\ by parameterizing it by UU^\ with U\∈ \× d and minimizing the squared loss, even if r \ d. We prove starting from a small initialization, gradient descent recovers\ in ̃(\√r) iterations approximately. The results the conjecture of Gunasekar et al.'17 under the restricted isometry. The technique can be applied to analyzing neural networks with-hidden-layer quadratic activations with some technical modifications.