A Convergence Analysis of Gradient Descent for Deep Linear Neural Networks

Abstract

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).

arXiv commentPublished as a conference paper at ICLR 2019

References in corpus (10)

• The Loss Surfaces of Multilayer Networks
• The loss surface of deep and wide neural networks
• On the Power of Over-parametrization in Neural Networks with Quadratic Activation
• No bad local minima: Data independent training error guarantees for multilayer neural networks
• Spurious Local Minima are Common in Two-Layer ReLU Neural Networks
• Globally Optimal Gradient Descent for a ConvNet with Gaussian Inputs
• Identity Matters in Deep Learning
• An Analytical Formula of Population Gradient for two-layered ReLU network and its Applications in Convergence and Critical Point Analysis
• When is a Convolutional Filter Easy To Learn?
• Algorithmic Regularization in Learning Deep Homogeneous Models: Layers are Automatically Balanced

Cited by in corpus (49)

• A Convergence Theory for Deep Learning via Over-Parameterization
• QMIX: Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learning
• Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks
• Optimization for deep learning: theory and algorithms
• The Modern Mathematics of Deep Learning
• On the Convergence Rate of Training Recurrent Neural Networks
• Deep matrix factorizations
• Deep Polynomial Neural Networks
• Overparameterized Neural Networks Implement Associative Memory
• AR-Net: A simple Auto-Regressive Neural Network for time-series
• Effect of Depth and Width on Local Minima in Deep Learning
• Stochastic AUC Maximization with Deep Neural Networks
• Provable Benefit of Orthogonal Initialization in Optimizing Deep Linear Networks
• Width Provably Matters in Optimization for Deep Linear Neural Networks
• The Impact of Neural Network Overparameterization on Gradient Confusion and Stochastic Gradient Descent
• Exponential Convergence Time of Gradient Descent for One-Dimensional Deep Linear Neural Networks
• Neural Mechanics: Symmetry and Broken Conservation Laws in Deep Learning Dynamics
• Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstruction
• Decoupling Gating from Linearity
• On Dropout and Nuclear Norm Regularization
• Over-parametrized deep neural networks do not generalize well
• Selection dynamics for deep neural networks
• On Connected Sublevel Sets in Deep Learning
• On the rate of convergence of a neural network regression estimate learned by gradient descent
• Almost Sure Convergence of Dropout Algorithms for Neural Networks
• Analytic Insights into Structure and Rank of Neural Network Hessian Maps
• A global convergence theory for deep ReLU implicit networks via over-parameterization
• Noether: The More Things Change, the More Stay the Same
• Let's Agree to Agree: Neural Networks Share Classification Order on Real Datasets
• A Deep Conditioning Treatment of Neural Networks
• Towards an Understanding of Residual Networks Using Neural Tangent Hierarchy (NTH)
• Pure and Spurious Critical Points: a Geometric Study of Linear Networks
• Speeding up Deep Model Training by Sharing Weights and Then Unsharing
• Holdout SGD: Byzantine Tolerant Federated Learning
• The loss landscape of deep linear neural networks: a second-order analysis
• Analysis of the rate of convergence of neural network regression estimates which are easy to implement
• Abide by the Law and Follow the Flow: Conservation Laws for Gradient Flows
• A Convergence Theory Towards Practical Over-parameterized Deep Neural Networks
• Deep orthogonal linear networks are shallow
• Student-Teacher Learning from Clean Inputs to Noisy Inputs
• A priori guarantees of finite-time convergence for Deep Neural Networks
• Neural Network Training Techniques Regularize Optimization Trajectory: An Empirical Study
• A Modular Analysis of Provable Acceleration via Polyak's Momentum: Training a Wide ReLU Network and a Deep Linear Network
• Understanding Modern Techniques in Optimization: Frank-Wolfe, Nesterov's Momentum, and Polyak's Momentum
• Painless step size adaptation for SGD
• Over-Parametrized Matrix Factorization in the Presence of Spurious Stationary Points
• SGD Through the Lens of Kolmogorov Complexity
• Training Linear Neural Networks: Non-Local Convergence and Complexity Results
• Adaptive Gradient Descent Methods for Computing Implied Volatility