Width Provably Matters in Optimization for Deep Linear Neural Networks

By Simon Shaolei Du, Wei Hu. 2019

104 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Optimization & Training, Statistical Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Optimization & Training

In Statistical Learning Theory

Citations in the corpus

Initialization and Regularization of Factorized Neural Layers (2021, background): “While the use of factorized neural layers for improving training has theoretical roots (Arora et al., 2018; Du & Hu, 2019), we are aware of two other works focusing on experimental practicality: ExpandNets (Guo et al., 2020) and DO-Conv (Cao et al., 2020).”
On Exact Computation with an Infinitely Wide Neural Net (2019, methodology): “This paper is inspired by a line of recent work on over-parameterized neural networks [Du et al., 2019, 2018b, Du and Hu, 2019, Li and Liang, 2018, Allen-Zhu et al., 2018b,a, Zou et al., 2018].”
Understanding self-supervised Learning Dynamics without Contrastive Pairs (2021, background): “Many previous studies of deep learning dynamics made simplifying isotropic assumptions about data (Tian, 2017; Brutzkus & Globerson, 2017; Du et al., 2019; Bartlett et al., 2018; Safran & Shamir, 2018).”
Backward Feature Correction: How Deep Learning Performs Deep Learning (2020, background): “(4)For instance, the theory for efficiently training DLNs only holds when the target linear function is wellconditioned [16, 29], and its running time bound is much worse than merely training a linear function as the learner.”
Implicit Regularization in Deep Matrix Factorization (2019, background): “These questions were studied extensively for matrix factorization — cf. [17, 6, 39, 18] — and more recently for linear neural networks of arbitrary depth — see [5, 3, 4, 14].”