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

2020/07/09 by Li, Yuanzhi, Ma, Tengyu, Zhang, Hongyang R. · 1 citation
#FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2007.04596

Abstract

We consider the dynamic of gradient descent for learning a two-layer neural network. We assume the input x∈ℝ^d is drawn from a Gaussian distribution and the label of x satisfies f^⋆(x) = a^\top|W^⋆x|, where a∈ℝ^d is a nonnegative vector and W^⋆ ∈ℝ^{d× 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 Ω(1 / d).

Cited by

• Feature learning is decoupled from generalization in high capacity neural networks

Related

• On Learning Over-parameterized Neural Networks: A Functional Approximation Perspective
• Learning One-hidden-layer ReLU Networks via Gradient Descent
• Gradient Descent Provably Optimizes Over-parameterized Neural Networks
• Over-parametrized neural networks as under-determined linear systems
• Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks