# Width Provably Matters in Optimization for Deep Linear Neural Networks

arXiv: https://arxiv.org/abs/1901.08572 · HTML: https://mlsanity.com/paper/1901.08572/

## Key facts

- Cited by 52 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Jan 2019.

## Built on by (most cited first, 30 of 52)

- [Understanding self-supervised Learning Dynamics without Contrastive Pairs](https://mlsanity.com/paper/2102.06810/) (2021)
- [Score-based Generative Neural Networks for Large-Scale Optimal Transport](https://mlsanity.com/paper/2110.03237/) (2021)
- [Initialization and Regularization of Factorized Neural Layers](https://mlsanity.com/paper/2105.01029/) (2021)
- [Optimization of Graph Neural Networks: Implicit Acceleration by Skip Connections and More Depth](https://mlsanity.com/paper/2105.04550/) (2021)
- [A Non-Asymptotic Analysis of Oversmoothing in Graph Neural Networks](https://mlsanity.com/paper/2212.10701/) (2022)
- [From Lazy to Rich: Exact Learning Dynamics in Deep Linear Networks](https://mlsanity.com/paper/2409.14623/) (2024)
- [The Neural Race Reduction: Dynamics of Abstraction in Gated Networks](https://mlsanity.com/paper/2207.10430/) (2022)
- [On the Theory of Implicit Deep Learning: Global Convergence with Implicit Layers](https://mlsanity.com/paper/2102.07346/) (2021)
- [Continuous vs. Discrete Optimization of Deep Neural Networks](https://mlsanity.com/paper/2107.06608/) (2021)
- [Compressible Dynamics in Deep Overparameterized Low-Rank Learning & Adaptation](https://mlsanity.com/paper/2406.04112/) (2024)
- [The loss landscape of deep linear neural networks: a second-order analysis](https://mlsanity.com/paper/2107.13289/) (2021)
- [Towards Demystifying Representation Learning with Non-contrastive Self-supervision](https://mlsanity.com/paper/2110.04947/) (2021)
- [Convergence of gradient descent for learning linear neural networks](https://mlsanity.com/paper/2108.02040/) (2021)
- [Bayesian Interpolation with Deep Linear Networks](https://mlsanity.com/paper/2212.14457/) (2022)
- [Infinite-width limit of deep linear neural networks](https://mlsanity.com/paper/2211.16980/) (2022)
- [The Connection Between Approximation, Depth Separation and Learnability in Neural Networks](https://mlsanity.com/paper/2102.00434/) (2021)
- [On Feature Learning in Neural Networks with Global Convergence Guarantees](https://mlsanity.com/paper/2204.10782/) (2022)
- [On a continuous time model of gradient descent dynamics and instability in deep learning](https://mlsanity.com/paper/2302.01952/) (2023)
- [Principal Components Bias in Over-parameterized Linear Models, and its Manifestation in Deep Neural Networks](https://mlsanity.com/paper/2105.05553/) (2021)
- [Deep Residual Networks Learn the Geodesic Curve in the Wasserstein Space](https://mlsanity.com/paper/2102.09235/) (2021)
- [Imitating Deep Learning Dynamics via Locally Elastic Stochastic Differential Equations](https://mlsanity.com/paper/2110.05960/) (2021)
- [Deep Linear Networks can Benignly Overfit when Shallow Ones Do](https://mlsanity.com/paper/2209.09315/) (2022)
- [Towards Training Without Depth Limits: Batch Normalization Without Gradient Explosion](https://mlsanity.com/paper/2310.02012/) (2023)
- [Ghosts in Neural Networks: Existence, Structure and Role of Infinite-Dimensional Null Space](https://mlsanity.com/paper/2106.04770/) (2021)
- [NTK-Guided Few-Shot Class Incremental Learning](https://mlsanity.com/paper/2403.12486/) (2024)
- [Convergence and Implicit Bias of Gradient Flow on Overparametrized Linear Networks](https://mlsanity.com/paper/2105.06351/) (2021)
- [Muddling Label Regularization: Deep Learning for Tabular Datasets](https://mlsanity.com/paper/2106.04462/) (2021)
- [Neural Hilbert Ladders: Multi-Layer Neural Networks in Function Space](https://mlsanity.com/paper/2307.01177/) (2023)
- [Swing-by Dynamics in Concept Learning and Compositional Generalization](https://mlsanity.com/paper/2410.08309/) (2024)
- [ANCRe: Adaptive Neural Connection Reassignment for Efficient Depth Scaling](https://mlsanity.com/paper/2602.09009/) (2026)

## Abstract (arXiv)

We prove that for an L-layer fully-connected linear neural network, if the width of every hidden layer is tildeOmega (L · r · dout · kappa3 ), where r and kappa are the rank and the condition number of the input data, and dout 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(frac1ε)). Our polynomial upper bound on the total running time for wide deep linear networks and the expleft(Omegaleft(Lright)right) lower bound for narrow deep linear neural networks [Shamir, 2018] together demonstrate that wide layers are necessary for optimizing deep models.