Exponential Convergence Time of Gradient Descent for One-Dimensional Deep Linear Neural Networks
By Ohad Shamir. 2018
52 citations recorded by the source corpus.
We study the dynamics of gradient descent on objective functions of the form $f(\prod_{i=1}^{k} w_i)$ (with respect to scalar parameters $w_1,\ldots,w_k$), which arise in the context of training depth-$k$ linear neural networks. We prove that for standard random initializations, and under mild assumptions on $f$, the number of iterations required for convergence scales exponentially with the depth $k$. We also show empirically that this phenomenon can occur in higher dimensions, where each $w_i$ is a matrix. This highlights a potential obstacle in understanding the convergence of gradient-based methods for deep linear neural networks, where $k$ is large.
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
- Wei Hu
- Simon Shaolei Du
- Sanjeev Arora
- Yuanzhi Li
- Zeyuan Allen-Zhu
- Nadav Cohen
- Colin Wei
- Jason D. Lee
Citations in the corpus
- A Convergence Analysis of Gradient Descent for Deep Linear Neural Networks (2018, background): “While condition (i) does not always hold ( cf. Safran and Shamir (2018)), it has been established for various simple settings ( e.g. Soudry and Carmon (2016); Kawaguchi (2016)).”
- Width Provably Matters in Optimization for Deep Linear Neural Networks (2019, background): “Unfortunately, these properties do not hold even for simple non-linear shallow neural networks (Yun et al., 2019; Safran & Shamir, 2018).”