Width Provably Matters in Optimization for Deep Linear Neural Networks

Abstract

We prove that for an $L$-layer fully-connected linear neural network, if the width of every hidden layer is $\tilde{\Omega }(L\cdot r\cdot d_{\mathrm{out}}\cdot {\kappa }^3)$, where $r$ and $\kappa$ are the rank and the condition number of the input data, and $d_{\mathrm{out}}$ is the output dimension, then gradient descent with Gaussian random initialization converges to a global minimum at a linear rate. The number of iterations to find an $\epsilon$-suboptimal solution is $O(\kappa \log (\frac{1}{\epsilon }))$. Our polynomial upper bound on the total running time for wide deep linear networks and the $\exp \left(\Omega \left(L\right)\right)$ lower bound for narrow deep linear neural networks [Shamir, 2018] together demonstrate that wide layers are necessary for optimizing deep models.

In ICML 2019

References in corpus (17)

• Adam: A Method for Stochastic Optimization
• A Convergence Theory for Deep Learning via Over-Parameterization
• Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data
• Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks
• No bad local minima: Data independent training error guarantees for multilayer neural networks
• Spurious Local Minima are Common in Two-Layer ReLU Neural Networks
• On the Optimization of Deep Networks: Implicit Acceleration by Overparameterization
• A Convergence Analysis of Gradient Descent for Deep Linear Neural Networks
• Gradient descent aligns the layers of deep linear networks
• Globally Optimal Gradient Descent for a ConvNet with Gaussian Inputs
• Depth Creates No Bad Local Minima
• 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?
• Global optimality conditions for deep neural networks
• Small nonlinearities in activation functions create bad local minima in neural networks
• Algorithmic Regularization in Learning Deep Homogeneous Models: Layers are Automatically Balanced

Cited by in corpus (28)

• On Exact Computation with an Infinitely Wide Neural Net
• Deep matrix factorizations
• Implicit Regularization in Deep Matrix Factorization
• Quadratic Suffices for Over-parametrization via Matrix Chernoff Bound
• Elimination of All Bad Local Minima in Deep Learning
• Understanding self-supervised Learning Dynamics without Contrastive Pairs
• Analysis of the Gradient Descent Algorithm for a Deep Neural Network Model with Skip-connections
• Revealing the Structure of Deep Neural Networks via Convex Duality
• Neural Mechanics: Symmetry and Broken Conservation Laws in Deep Learning Dynamics
• A Unifying View on Implicit Bias in Training Linear Neural Networks
• Score-based Generative Neural Networks for Large-Scale Optimal Transport
• Continuous vs. Discrete Optimization of Deep Neural Networks
• The Connection Between Approximation, Depth Separation and Learnability in Neural Networks
• Global Convergence of Gradient Descent for Deep Linear Residual Networks
• Analysis of Knowledge Transfer in Kernel Regime
• Towards Demystifying Representation Learning with Non-contrastive Self-supervision
• Which Minimizer Does My Neural Network Converge To?
• Initialization and Regularization of Factorized Neural Layers
• The loss landscape of deep linear neural networks: a second-order analysis
• Enhance Diffusion to Improve Robust Generalization
• Deep Residual Networks Learn the Geodesic Curve in the Wasserstein Space
• Neural Path Features and Neural Path Kernel : Understanding the role of gates in deep learning
• A Modular Analysis of Provable Acceleration via Polyak's Momentum: Training a Wide ReLU Network and a Deep Linear Network
• Training Linear Neural Networks: Non-Local Convergence and Complexity Results
• Understanding Modern Techniques in Optimization: Frank-Wolfe, Nesterov's Momentum, and Polyak's Momentum
• Learning with Neural Tangent Kernels in Near Input Sparsity Time
• Ghosts in Neural Networks: Existence, Structure and Role of Infinite-Dimensional Null Space
• Deep Gated Networks: A framework to understand training and generalisation in deep learning