# Training Linear Neural Networks: Non-Local Convergence and Complexity Results

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Feb 2020.

## Built on by (most cited first, 19 of 19)

- [Saddle-to-Saddle Dynamics in Deep Linear Networks: Small Initialization Training, Symmetry, and Sparsity](https://mlsanity.com/paper/2106.15933/) (2021)
- [Differentiation and Specialization of Attention Heads via the Refined Local Learning Coefficient](https://mlsanity.com/paper/2410.02984/) (2024)
- [Continuous vs. Discrete Optimization of Deep Neural Networks](https://mlsanity.com/paper/2107.06608/) (2021)
- [Dynamical versus Bayesian Phase Transitions in a Toy Model of Superposition](https://mlsanity.com/paper/2310.06301/) (2023)
- [Subquadratic Overparameterization for Shallow Neural Networks](https://mlsanity.com/paper/2111.01875/) (2021)
- [The loss landscape of deep linear neural networks: a second-order analysis](https://mlsanity.com/paper/2107.13289/) (2021)
- [Infinite-width limit of deep linear neural networks](https://mlsanity.com/paper/2211.16980/) (2022)
- [The Law of Parsimony in Gradient Descent for Learning Deep Linear Networks](https://mlsanity.com/paper/2306.01154/) (2023)
- [On the Omnipresence of Spurious Local Minima in Certain Neural Network Training Problems](https://mlsanity.com/paper/2202.12262/) (2022)
- [Neural Hilbert Ladders: Multi-Layer Neural Networks in Function Space](https://mlsanity.com/paper/2307.01177/) (2023)
- [Efficient Compression of Overparameterized Deep Models through Low-Dimensional Learning Dynamics](https://mlsanity.com/paper/2311.05061/) (2023)
- [Over-Parametrized Matrix Factorization in the Presence of Spurious Stationary Points](https://mlsanity.com/paper/2112.13269/) (2021)
- [On the ISS Property of the Gradient Flow for Single Hidden-Layer Neural Networks with Linear Activations](https://mlsanity.com/paper/2305.09904/) (2023)
- [Lecture Notes on Linear Neural Networks: A Tale of Optimization and Generalization in Deep Learning](https://mlsanity.com/paper/2408.13767/) (2024)
- [Remarks on the Polyak-Lojasiewicz inequality and the convergence of gradient systems](https://mlsanity.com/paper/2503.23641/) (2025)
- [Does SGD Seek Flatness or Sharpness? An Exactly Solvable Model](https://mlsanity.com/paper/2602.05065/) (2026)
- [The critical slowing down in training diffusion models](https://mlsanity.com/paper/2605.12597/) (2026)
- [Global Convergence Analysis of Deep Linear Networks with A One-neuron Layer](https://mlsanity.com/paper/2201.02761/) (2022)
- [On the Convergence of Overparameterized Problems: Inherent Properties of the Compositional Structure of Neural Networks](https://mlsanity.com/paper/2511.09810/) (2025)

## Abstract (arXiv)

Linear networks provide valuable insights into the workings of neural networks in general. This paper identifies conditions under which the gradient flow provably trains a linear network, in spite of the non-strict saddle points present in the optimization landscape. This paper also provides the computational complexity of training linear networks with gradient flow. To achieve these results, this work develops a machinery to provably identify the stable set of gradient flow, which then enables us to improve over the state of the art in the literature of linear networks (Bah et al., 2019;Arora et al., 2018a). Crucially, our results appear to be the first to break away from the lazy training regime which has dominated the literature of neural networks. This work requires the network to have a layer with one neuron, which subsumes the networks with a scalar output, but extending the results of this theoretical work to all linear networks remains a challenging open problem.