  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{out}}
\cdot \kappa^3 )$, where $r$ and $\kappa$ are the rank and the condition number
of the input data, and $d_{\mathrm{out}}$ 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
$\epsilon$-suboptimal solution is $O(\kappa \log(\frac{1}{\epsilon}))$. Our
polynomial upper bound on the total running time for wide deep linear networks
and the $\exp\left(\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.
