%0 Journal Article %1 li2017algorithmic %A Li, Yuanzhi %A Ma, Tengyu %A Zhang, Hongyang %D 2017 %K deep-learning foundations machine-learning optimization readings stable theory %T Algorithmic Regularization in Over-parameterized Matrix Sensing and Neural Networks with Quadratic Activations %U http://arxiv.org/abs/1712.09203 %X We show that the gradient descent algorithm provides an implicit regularization effect in the learning of over-parameterized matrix factorization models and one-hidden-layer neural networks with quadratic activations. Concretely, we show that given $O(dr^2)$ random linear measurements of a rank $r$ positive semidefinite matrix $X^\star$, we can recover $X^\star$ by parameterizing it by $UU^\top$ with $U\mathbb R^dd$ and minimizing the squared loss, even if $r d$. We prove that starting from a small initialization, gradient descent recovers $X^\star$ in $O(r)$ iterations approximately. The results solve the conjecture of Gunasekar et al.'17 under the restricted isometry property. The technique can be applied to analyzing neural networks with one-hidden-layer quadratic activations with some technical modifications.

@article{li2017algorithmic, abstract = {We show that the gradient descent algorithm provides an implicit regularization effect in the learning of over-parameterized matrix factorization models and one-hidden-layer neural networks with quadratic activations. Concretely, we show that given $\tilde{O}(dr^{2})$ random linear measurements of a rank $r$ positive semidefinite matrix $X^{\star}$, we can recover $X^{\star}$ by parameterizing it by $UU^\top$ with $U\in \mathbb R^{d\times d}$ and minimizing the squared loss, even if $r \ll d$. We prove that starting from a small initialization, gradient descent recovers $X^{\star}$ in $\tilde{O}(\sqrt{r})$ iterations approximately. The results solve the conjecture of Gunasekar et al.'17 under the restricted isometry property. The technique can be applied to analyzing neural networks with one-hidden-layer quadratic activations with some technical modifications.}, added-at = {2019-06-10T12:02:35.000+0200}, author = {Li, Yuanzhi and Ma, Tengyu and Zhang, Hongyang}, biburl = {https://www.bibsonomy.org/bibtex/2be5bb2cffa8860eb83c3d58b14efbd9b/kirk86}, description = {[1712.09203] Algorithmic Regularization in Over-parameterized Matrix Sensing and Neural Networks with Quadratic Activations}, interhash = {fd2930733f331409377bf1a5a62ba46e}, intrahash = {be5bb2cffa8860eb83c3d58b14efbd9b}, keywords = {deep-learning foundations machine-learning optimization readings stable theory}, note = {cite arxiv:1712.09203Comment: COLT 2018 best paper; fixed minor missing steps in the previous version}, timestamp = {2019-11-14T20:39:46.000+0100}, title = {Algorithmic Regularization in Over-parameterized Matrix Sensing and Neural Networks with Quadratic Activations}, url = {http://arxiv.org/abs/1712.09203}, year = 2017 }