Gradient descent aligns the layers of deep linear networks

By Ziwei Ji, Matus Telgarsky. 2018

304 citations recorded by the source corpus.

This paper establishes risk convergence and asymptotic weight matrix alignment --- a form of implicit regularization --- of gradient flow and gradient descent when applied to deep linear networks on linearly separable data. In more detail, for gradient flow applied to strictly decreasing loss functions (with similar results for gradient descent with particular decreasing step sizes): (i) the risk converges to 0; (ii) the normalized i-th weight matrix asymptotically equals its rank-1 approximation $u_iv_i^{\top}$; (iii) these rank-1 matrices are aligned across layers, meaning $|v_{i+1}^{\top}u_i|\to1$. In the case of the logistic loss (binary cross entropy), more can be said: the linear function induced by the network --- the product of its weight matrices --- converges to the same direction as the maximum margin solution. This last property was identified in prior work, but only under assumptions on gradient descent which here are implied by the alignment phenomenon.

Subfields: Artificial Intelligence, Computational Mechanics, Radiology, Nuclear Medicine and Imaging, Optimization & Training

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 Computational Mechanics

In Radiology, Nuclear Medicine and Imaging

In Optimization & Training

Citations in the corpus

The Surprising Simplicity of the Early-Time Learning Dynamics of Neural Networks (2020, background): “…has also been studied in various settings, suggesting a bias towards large-margin, low-norm, or low-rank solutions [Gunasekar et al., 2017, 2018, Soudry et al., 2018, Li et al., 2018, Ji and Telgarsky, 2019a,b, Arora et al., 2019a, Lyu and Li, 2019, Chizat and Bach, 2020, Razin and Cohen, 2020].”
Generalization Guarantees for Neural Networks via Harnessing the Low-rank Structure of the Jacobian (2019, background): “For linearly separable datasets, [55, 27, 14, 32, 33] show that first-order methods find solutions that generalize well without an explicit regularization for logistic regression.”
Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks (2019, methodology): “…established that ﬁrst-order methods can automatically ﬁnd minimum-norm/maximum-margin solutions that ﬁt the data in the settings of logistic regression, deep linear networks, and symmetric matrix factorization (Soudry et al., 2018; Gunasekar et al., 2018a,b; Ji & Telgarsky, 2018; Li et al., 2018b).”
Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks (2018, background): “Assumption 3.1 has been widely made in the studies of training binary classiﬁers (Soudry et al., 2017; Nacson et al., 2018; Ji and Telgarsky, 2018).”
Implicit Regularization in Deep Matrix Factorization (2019, unknown): “[4, 28]) later supported this match theoretically.”
The Convergence Rate of Neural Networks for Learned Functions of Different Frequencies (2019, background): “[14] studies the effect of gradient descent on the alignment of the weight matrices for linear neural networks.”
Toward Moderate Overparameterization: Global Convergence Guarantees for Training Shallow Neural Networks (2019, background): “Several works [1–3,10,23–33] study the benefits of overparameterization for training neural networks and related optimization problems.”
Truth or Backpropaganda? An Empirical Investigation of Deep Learning Theory (2019, methodology): “The ﬁndings in Ji & Telgarsky (2018) are corroborated here as the black dots in Figures 2 show that ini-tializations are higher in rank than the trained models.”
Gradient Descent Maximizes the Margin of Homogeneous Neural Networks (2019, background): “[Ji and Telgarsky, 2019] shows that the product of weights in a deep linear network with strictly decreasing loss converges in the direction of the max L 2 -margin solution.”
Exponential Convergence Time of Gradient Descent for One-Dimensional Deep Linear Neural Networks (2018, background): “In another recent related work, Ji and Telgarsky [2018] show that for certain classiﬁcation problems on linearly separable data (corresponding to a suitable choice of f in Eq.”
Kernel and Deep Regimes in Overparametrized Models (2019, background): “But in many cases, the speciﬁc solution reached by gradient ﬂow (or some other optimization procedure) has special structure, or minimizes some implicit regularizer, and this structure or regularizer provides the needed inductive bias [13, 12, 22, 15].”
Implicit Bias of Gradient Descent for Wide Two-layer Neural Networks Trained with the Logistic Loss (2020, unknown): “Fine analyses of convergence rates have been carried out by Nacson et al. (2019b); Ji and Telgarsky (2019b, 2018), and extensions to other gradient-based algorithms and to factored parameterizations are considered by Gunasekar et al. (2018a).”
Generalization of Two-layer Neural Networks: An Asymptotic Viewpoint (2020, result): “Existing works have analyzed the implicit regularization of gradient descent (Gunasekar et al., 2018; Ji and Telgarsky, 2018), and provided generalization guarantees (Arora et al., 2018; Bartlett et al., 2017; Dziugaite and Roy, 2017) that align with the empirical observations.”