Learning Over-Parametrized Two-Layer ReLU Neural Networks beyond NTK

Abstract

We consider the dynamic of gradient descent for learning a two-layer neural network. We assume the input $x\in {\mathbb{R}}^d$ is drawn from a Gaussian distribution and the label of $x$ satisfies $f^{\star }(x)=a^{\top }|W^{\star }x|$, where $a\in {\mathbb{R}}^d$ is a nonnegative vector and $W^{\star }\in {\mathbb{R}}^{d\times d}$ is an orthonormal matrix. We show that an over-parametrized two-layer neural network with ReLU activation, trained by gradient descent from random initialization, can provably learn the ground truth network with population loss at most $o(1/d)$ in polynomial time with polynomial samples. On the other hand, we prove that any kernel method, including Neural Tangent Kernel, with a polynomial number of samples in $d$, has population loss at least $\Omega (1/d)$.

Conference on Learning Theory (COLT) 2020

References in corpus (22)

• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• A Convergence Theory for Deep Learning via Over-Parameterization
• Regularizing and Optimizing LSTM Language Models
• Gradient Descent Provably Optimizes Over-parameterized Neural Networks
• Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data
• Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks
• Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks
• Toward Deeper Understanding of Neural Networks: The Power of Initialization and a Dual View on Expressivity
• Scaling Limits of Wide Neural Networks with Weight Sharing: Gaussian Process Behavior, Gradient Independence, and Neural Tangent Kernel Derivation
• No bad local minima: Data independent training error guarantees for multilayer neural networks
• Optimization for deep learning: theory and algorithms
• Recovery Guarantees for One-hidden-layer Neural Networks
• Towards Explaining the Regularization Effect of Initial Large Learning Rate in Training Neural Networks
• Learning One-hidden-layer Neural Networks with Landscape Design
• When Are Nonconvex Problems Not Scary?
• Enhanced Convolutional Neural Tangent Kernels
• First-order Methods Almost Always Avoid Saddle Points
• An Analytical Formula of Population Gradient for two-layered ReLU network and its Applications in Convergence and Critical Point Analysis
• Learning One-hidden-layer ReLU Networks via Gradient Descent
• Analyzing Tensor Power Method Dynamics in Overcomplete Regime
• Theoretical properties of the global optimizer of two layer neural network
• Shape Matters: Understanding the Implicit Bias of the Noise Covariance

Cited by in corpus (17)

• Towards Understanding Ensemble, Knowledge Distillation and Self-Distillation in Deep Learning
• Feature Learning in Infinite-Width Neural Networks
• Optimal Rates for Averaged Stochastic Gradient Descent under Neural Tangent Kernel Regime
• Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstruction
• A Local Convergence Theory for Mildly Over-Parameterized Two-Layer Neural Network
• The Effects of Mild Over-parameterization on the Optimization Landscape of Shallow ReLU Neural Networks
• Forward Super-Resolution: How Can GANs Learn Hierarchical Generative Models for Real-World Distributions
• Proxy Convexity: A Unified Framework for the Analysis of Neural Networks Trained by Gradient Descent
• Particle Dual Averaging: Optimization of Mean Field Neural Networks with Global Convergence Rate Analysis
• Making Method of Moments Great Again? -- How can GANs learn distributions
• On the Provable Generalization of Recurrent Neural Networks
• On the Power of Differentiable Learning versus PAC and SQ Learning
• Properties of the After Kernel
• Deep Networks Provably Classify Data on Curves
• Towards Understanding Learning in Neural Networks with Linear Teachers
• Unintended Effects on Adaptive Learning Rate for Training Neural Network with Output Scale Change
• A Modular Analysis of Provable Acceleration via Polyak's Momentum: Training a Wide ReLU Network and a Deep Linear Network