Gradient Descent with Identity Initialization Efficiently Learns Positive-Definite Linear Transformations by Deep Residual Networks

By Peter L. Bartlett, David P. Helmbold, Philip M. Long. 2018

125 citations recorded by the source corpus.

We analyze algorithms for approximating a function f(x)=Φx mapping ℜd to ℜd using deep linear neural networks, that is, that learn a function h parameterized by matrices Θ1,…,ΘL and defined by h(x)=ΘLΘL-1…Θ1x. We focus on algorithms that learn through gradient descent on the population quadratic loss in the case that the distribution over the inputs is isotropic. We provide polynomial bounds on the number of iterations for gradient descent to approximate the least-squares matrix Φ, in the case where the initial hypothesis Θ1=…=ΘL=I has excess loss bounded by a small enough constant. We also show that gradient descent fails to converge for Φ whose distance from the identity is a larger constant, and we show that some forms of regularization toward the identity in each layer do not help. If Φ is symmetric positive definite, we show that an algorithm that initializes Θi=I learns an ε-approximation of f using a number of updates polynomial in L, the condition number of Φ, and log(d/ε). In contrast, we show that if the least-squares matrix Φ is symmetric and has a negative eigenvalue, then all members of a class of algorithms that perform gradient descent with identity initialization, and optionally regularize toward the identity in each layer, fail to converge. We analyze an algorithm for the case that Φ satisfies u⊤Φu>0 for all u but may not be symmetric. This algorithm uses two regularizers: one that maintains the invariant u⊤ΘLΘL-1…Θ1u>0 for all u and the other that “balances” Θ1,…,ΘL so that they have the same singular values.

Subfields: Artificial Intelligence, Computational Mechanics, Computational Theory and Mathematics, 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 Computational Theory and Mathematics

In Optimization & Training

Citations in the corpus

A Convergence Theory for Deep Learning via Over-Parameterization (2018, background): “Besides the already cited references (Arora et al., 2018a; Bartlett et al., 2018; Hardt & Ma, 2017; Kawaguchi, 2016), 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.”
Architecture Matters in Continual Learning (2022, background): “…have been done to explain why skip connections are useful: Hardt and Ma (2016) show that skip connection tends to eliminate spurious local optima; Bartlett et al. (2018b) study the function expressivity of residual architectures; Bartlett et al. (2018a) show that gradient descent provably learns…”
Representing smooth functions as compositions of near-identity functions with implications for deep network optimization (2018, background): “This raised the possibility that gradient descent with each layer initialized to the identity might provably converge for this non-convex optimization problem; Bartlett et al. (2018) investigated this, identifying sets of problems where this method converges, and where it does not.”
A Convergence Analysis of Gradient Descent for Deep Linear Neural Networks (2018, methodology): “In terms of deﬁciency margin, we provide (by adapting Theorem 4 in Bartlett et al. (2018)) a different, somewhat stronger result — there exist settings where initialization violates the assumption of deﬁciency margin, and despite being perfectly balanced, leads to convergence failure, for any…”
Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks (2018, background): “Deep linear networks Beyond shallow one-hidden-layer neural networks, a series of recent work (Hardt and Ma, 2016; Kawaguchi, 2016; Bartlett et al., 2018; Arora et al., 2018a,b) focus on the optimization landscape of deep linear networks.”
On the Convergence Rate of Training Recurrent Neural Networks (2018, background): “Some study deep neural networks but assuming the activation function is linear [6, 7, 25].”
Algorithmic Regularization in Learning Deep Homogeneous Models: Layers are Automatically Balanced (2018, background): “…many studies on the optimization landscapes of neural networks [Kawaguchi, 2016, Choromanska et al., 2015, Du and Lee, 2018, Hardt and Ma, 2016, Bartlett et al., 2018, Haeffele and Vidal, 2015, Freeman and Bruna, 2016, Vidal et al., 2017, Safran and Shamir, 2016, Zhou and Feng, 2017, Nguyen…”
Width Provably Matters in Optimization for Deep Linear Neural Networks (2019, methodology): “The most related papers are (Bartlett et al., 2018) and (Arora et al., 2018a).”
Batch normalization provably avoids ranks collapse for randomly initialised deep networks (2020, background): “Since our empirical observations hold equally for both non-linear and linear networks, we here focus on improving the theoretical understanding in the linear case, which constitutes a growing area of research [26, 19, 6, 2].”
Step Size Matters in Deep Learning (2018, methodology): “Later, equivalent results were also derived for nonlinear residual networks under certain conditions (Bartlett et al., 2018a).”
Understanding self-supervised Learning Dynamics without Contrastive Pairs (2021, background): “Many previous studies of deep learning dynamics made simplifying isotropic assumptions about data (Tian, 2017; Brutzkus & Globerson, 2017; Du et al., 2019; Bartlett et al., 2018; Safran & Shamir, 2018).”
Implicit Regularization in Deep Learning May Not Be Explainable by Norms (2020, background): “[8] Peter Bartlett, Dave Helmbold, and Phil Long.”
Exponential Convergence Time of Gradient Descent for One-Dimensional Deep Linear Neural Networks (2018, methodology): “Motivated by residual networks, Hardt and Ma [2016] and Bartlett et al. [2018] consider initializing each Wi independently at I , possibly with some random perturbation.”
Implicit Regularization in Deep Matrix Factorization (2019, background): “[17, 6, 39, 18] — and more recently for linear neural networks of arbitrary depth — see [5, 3, 4, 14].”