Training Linear Neural Networks: Non-Local Convergence and Complexity Results

Abstract

Linear networks provide valuable insights into the workings of neural networks in general. This paper identifies conditions under which the gradient flow provably trains a linear network, in spite of the non-strict saddle points present in the optimization landscape. This paper also provides the computational complexity of training linear networks with gradient flow. To achieve these results, this work develops a machinery to provably identify the stable set of gradient flow, which then enables us to improve over the state of the art in the literature of linear networks (Bah et al., 2019;Arora et al., 2018a). Crucially, our results appear to be the first to break away from the lazy training regime which has dominated the literature of neural networks. This work requires the network to have a layer with one neuron, which subsumes the networks with a scalar output, but extending the results of this theoretical work to all linear networks remains a challenging open problem.

References in corpus (32)

• Exact solutions to the nonlinear dynamics of learning in deep linear neural networks
• A Convergence Theory for Deep Learning via Over-Parameterization
• Gradient Descent Provably Optimizes Over-parameterized Neural Networks
• Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data
• Optimal detection of sparse principal components in high dimension
• Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks
• On Lazy Training in Differentiable Programming
• Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks
• Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks
• Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers
• On the Power of Over-parametrization in Neural Networks with Quadratic Activation
• On the Optimization of Deep Networks: Implicit Acceleration by Overparameterization
• Gradient Descent Converges to Minimizers
• 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
• First-order Methods Almost Always Avoid Saddle Points
• Depth Creates No Bad Local Minima
• Implicit Regularization in Deep Matrix Factorization
• Fast Convergence of Natural Gradient Descent for Overparameterized Neural Networks
• Overparameterized Nonlinear Learning: Gradient Descent Takes the Shortest Path?
• Global optimality conditions for deep neural networks
• Global Convergence of Adaptive Gradient Methods for An Over-parameterized Neural Network
• Learning Non-overlapping Convolutional Neural Networks with Multiple Kernels
• SGD Learns Over-parameterized Networks that Provably Generalize on Linearly Separable Data
• Width Provably Matters in Optimization for Deep Linear Neural Networks
• How Much Over-parameterization Is Sufficient to Learn Deep ReLU Networks?
• On Learning Over-parameterized Neural Networks: A Functional Approximation Perspective
• MOSES: A Streaming Algorithm for Linear Dimensionality Reduction
• On Connected Sublevel Sets in Deep Learning
• Pure and Spurious Critical Points: a Geometric Study of Linear Networks
• PCA by Optimisation of Symmetric Functions has no Spurious Local Optima