A Convergence Analysis of Gradient Descent for Deep Linear Neural Networks

By Sanjeev Arora, Nadav Cohen, Noah Golowich, Wei Hu. 2018

350 citations recorded by the source corpus.

We analyze speed of convergence to global optimum for gradient descent training a deep linear neural network (parameterized as $x \mapsto W_N W_{N-1} \cdots W_1 x$) by minimizing the $\ell_2$ loss over whitened data. Convergence at a linear rate is guaranteed when the following hold: (i) dimensions of hidden layers are at least the minimum of the input and output dimensions; (ii) weight matrices at initialization are approximately balanced; and (iii) the initial loss is smaller than the loss of any rank-deficient solution. The assumptions on initialization (conditions (ii) and (iii)) are necessary, in the sense that violating any one of them may lead to convergence failure. Moreover, in the important case of output dimension 1, i.e. scalar regression, they are met, and thus convergence to global optimum holds, with constant probability under a random initialization scheme. Our results significantly extend previous analyses, e.g., of deep linear residual networks (Bartlett et al., 2018).

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

A Convergence Theory for Deep Learning via Over-Parameterization (2018, background): “Besides the already cited references [7, 9, 26, 31], there are a number of works that study linear dynamical systems , which can be viewed as the linear version of recurrent neural networks or reinforcement learning.”
Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learning (2020, background): “Having an extra layer is a better parametrisation in this scenario because it allows for gradient descent to optimise the loss faster (Arora et al., 2018).”
Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks (2018, background): “…Anthony and Bartlett, 2009), a vast literature have recently studied the connection between the generalization performance of deep neural networks and their architectures (Neyshabur et al., 2015, 2017a,b; Bartlett et al., 2017; Golowich et al., 2017; Arora et al., 2018c; Allen-Zhu et al., 2018a).”
On the Convergence Rate of Training Recurrent Neural Networks (2018, background): “Some study deep neural networks but assuming the activation function is linear [5, 6, 22].”
Fast Convergence of Natural Gradient Descent for Overparameterized Neural Networks (2019, methodology): “Bartlett et al., Arora et al. [2019a] studied the optimization trajectory of deep linear networks and showed that gradient descent can ﬁnd global minima under some assumptions.”
Exponential Convergence Time of Gradient Descent for One-Dimensional Deep Linear Neural Networks (2018, background): “More recently, Arora et al. [2018a] considered gradient descent on a similar objective, and managed to prove strong polynomial-time convergence guarantees under certain assumptions about the initialization.”
Collapse of Deep and Narrow Neural Nets (2018, background): “However, these assumptions do not always hold and are provably false for deep neural networks (Safran and Shamir, 2018; Kawaguchi, 2016; Arora et al., 2018).”
A Generalization Theory of Gradient Descent for Learning Over-parameterized Deep ReLU Networks (2019, background): “Arora et al. (2018b) interpreted over-parametrization as a way of implicit acceleration during optimization.”
Implicit Regularization in Deep Matrix Factorization (2019, neutral): “[4, 28]) later supported this match theoretically.”
The Break-Even Point on Optimization Trajectories of Deep Neural Networks (2020, background): “Arora et al. (2019) suggest it is necessary to study the optimization trajectory to understand optimization and generalization of deep networks.”
Gradient descent optimizes over-parameterized deep ReLU networks (2019, methodology): “Very recently, there emerges a large body of work that study the global convergence of gradient descent (GD) for training neural networks (Li andLiang2018;Du et al. 2018b;AllenZhu et al. 2018a; Du et al. 2018a). In particular, Li and Liang (2018) showed that for a onehidden-layer networkwithReLUacti”
Implicit Regularization in Deep Learning May Not Be Explainable by Norms (2020, background): “[7, 45]) have supported this match theoretically, and we provide additional support in Appendix D by extending our theory to the case of unbalanced initialization (Equation (5) holding approximately).”
Why do Larger Models Generalize Better? A Theoretical Perspective via the XOR Problem (2018, background): “Several works (Ji & Telgarsky, 2019; Gunasekar et al., 2018; Arora et al., 2019) provide guarantees for gradient descent on linear networks.”
Towards Understanding Knowledge Distillation (2019, background): “Finally, condition (13) is called balanced-ness (Arora et al., 2018) and discussed in-depth in (Arora et al., 2019)).”
Width Provably Matters in Optimization for Deep Linear Neural Networks (2019, methodology): “Arora et al. (2018a) showed that if the initialization is balanced and the initial loss is smaller than the loss of any low-rank solution by a margin, then gradient descent converges to global minimum at a linear rate.”