Learning One-hidden-layer ReLU Networks via Gradient Descent

Abstract

We study the problem of learning one-hidden-layer neural networks with Rectified Linear Unit (ReLU) activation function, where the inputs are sampled from standard Gaussian distribution and the outputs are generated from a noisy teacher network. We analyze the performance of gradient descent for training such kind of neural networks based on empirical risk minimization, and provide algorithm-dependent guarantees. In particular, we prove that tensor initialization followed by gradient descent can converge to the ground-truth parameters at a linear rate up to some statistical error. To the best of our knowledge, this is the first work characterizing the recovery guarantee for practical learning of one-hidden-layer ReLU networks with multiple neurons. Numerical experiments verify our theoretical findings.

arXiv comment26 pages, 2 figures

Cited by in corpus (20)

• Learning ReLU Networks on Linearly Separable Data: Algorithm, Optimality, and Generalization
• ReduNet: A White-box Deep Network from the Principle of Maximizing Rate Reduction
• Generalization Error Bounds of Gradient Descent for Learning Over-parameterized Deep ReLU Networks
• A Generalized Neural Tangent Kernel Analysis for Two-layer Neural Networks
• Agnostic Learning of a Single Neuron with Gradient Descent
• Directional Pruning of Deep Neural Networks
• On the Global Convergence of Training Deep Linear ResNets
• A Local Convergence Theory for Mildly Over-Parameterized Two-Layer Neural Network
• Learning Over-Parametrized Two-Layer ReLU Neural Networks beyond NTK
• Guaranteed Recovery of One-Hidden-Layer Neural Networks via Cross Entropy
• Tune smarter not harder: A principled approach to tuning learning rates for shallow nets
• Forward Super-Resolution: How Can GANs Learn Hierarchical Generative Models for Real-World Distributions
• Agnostic Learning of Halfspaces with Gradient Descent via Soft Margins
• Self-Regularity of Non-Negative Output Weights for Overparameterized Two-Layer Neural Networks
• A Convergence Theory Towards Practical Over-parameterized Deep Neural Networks
• Making Method of Moments Great Again? -- How can GANs learn distributions
• Structured Directional Pruning via Perturbation Orthogonal Projection
• Coordinate Descent Methods for DC Minimization: Optimality Conditions and Global Convergence
• Neural Network Training Techniques Regularize Optimization Trajectory: An Empirical Study
• Estimating Stochastic Linear Combination of Non-linear Regressions Efficiently and Scalably