Learning ReLUs via Gradient Descent

Abstract

In this paper we study the problem of learning Rectified Linear Units (ReLUs) which are functions of the form $max(0,<w,x>)$ with $w$ denoting the weight vector. We study this problem in the high-dimensional regime where the number of observations are fewer than the dimension of the weight vector. We assume that the weight vector belongs to some closed set (convex or nonconvex) which captures known side-information about its structure. We focus on the realizable model where the inputs are chosen i.i.d.~from a Gaussian distribution and the labels are generated according to a planted weight vector. We show that projected gradient descent, when initialization at 0, converges at a linear rate to the planted model with a number of samples that is optimal up to numerical constants. Our results on the dynamics of convergence of these very shallow neural nets may provide some insights towards understanding the dynamics of deeper architectures.

arXiv admin note: text overlap with arXiv:1702.06175

Cited by in corpus (28)

• A Convergence Theory for Deep Learning via Over-Parameterization
• Gradient Descent Provably Optimizes Over-parameterized Neural Networks
• Gradient Descent Finds Global Minima of Deep Neural Networks
• On the Convergence Rate of Training Recurrent Neural Networks
• Depth with Nonlinearity Creates No Bad Local Minima in ResNets
• On the loss landscape of a class of deep neural networks with no bad local valleys
• Generalization Error Bounds of Gradient Descent for Learning Over-parameterized Deep ReLU Networks
• Quadratic Suffices for Over-parametrization via Matrix Chernoff Bound
• Understanding the Loss Surface of Neural Networks for Binary Classification
• Adding One Neuron Can Eliminate All Bad Local Minima
• Learning One Convolutional Layer with Overlapping Patches
• Elimination of All Bad Local Minima in Deep Learning
• On the Benefit of Width for Neural Networks: Disappearance of Bad Basins
• A Generalized Neural Tangent Kernel Analysis for Two-layer Neural Networks
• On the Power and Limitations of Random Features for Understanding Neural Networks
• Gradient Descent can Learn Less Over-parameterized Two-layer Neural Networks on Classification Problems
• Learning Two Layer Rectified Neural Networks in Polynomial Time
• Learning a Single Neuron with Gradient Methods
• The Multilinear Structure of ReLU Networks
• Learning ReLU Networks via Alternating Minimization
• End-to-end Learning of a Convolutional Neural Network via Deep Tensor Decomposition
• GradSign: Model Performance Inference with Theoretical Insights
• An Approximation Algorithm for training One-Node ReLU Neural Network
• Improved Learning of One-hidden-layer Convolutional Neural Networks with Overlaps
• Guaranteed Recovery of One-Hidden-Layer Neural Networks via Cross Entropy
• Solving Equations of Random Convex Functions via Anchored Regression
• The Effects of Mild Over-parameterization on the Optimization Landscape of Shallow ReLU Neural Networks
• Representation Learning and Recovery in the ReLU Model