Width Provably Matters in Optimization for Deep Linear Neural Networks

We prove that for an $L$-layer fully-connected linear neural network, if the width of every hidden layer is $\tilde\Omega (L \cdot r \cdot d_{$\mathrm{o}\mathrm{u}\mathrm{t}$} \cdot \kappa^3 )$,where$r$and$\kappa$ are the rank and the condition number of the input data, and $d_{\mathrm{o}\mathrm{u}\mathrm{t}}$ is the output dimension, then gradient descent with Gaussian random initialization converges to a global minimum at a linear rate. The number of iterations to find an $ϵ$-suboptimal solution is $O(\kappa \log (\frac{1}{ϵ}))$. Our polynomial upper bound on the total running time for wide deep linear networks and the $\exp \left(\mathrm{\Omega }\left(L\right)\right)$ lower bound for narrow deep linear neural networks [Shamir, 2018] together demonstrate that wide layers are necessary for optimizing deep models.