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

By Yuanzhi Li, Tengyu Ma, Hongyang Zhang. 2020

29 citations recorded by the source corpus.

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)$.

Subfields: Artificial Intelligence, Statistical Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistical Learning Theory

Citations in the corpus

Feature Purification: How Adversarial Training Performs Robust Deep Learning (2020, background): “Most of existing works (1) only focus on the case when the training data is spherical Gaussian [28–43], and some of them require heavy initialization using tensor decomposition, which might fail to capture the specific structure of the input and the property of a random initialization; or (2) only c”
Making Method of Moments Great Again? -- How can GANs learn the target distribution (2020, background): “Moreover, given the recent advance in training neural network using gradient descent [51], such generator could potentially be found by simply doing gradient descent starting from random initialization as well.”