Over-Parameterization Exponentially Slows Down Gradient Descent for Learning a Single Neuron

Understand

We revisit the problem of learning a single neuron with ReLU activation under Gaussian input with square loss.

• We particularly focus on the over-parameterization setting where the student network has $n\ge 2$ neurons.
• We prove the global convergence of randomly initialized gradient descent with a $O\left(T^{-3}\right)$ rate.
• This is the first global convergence result for this problem beyond the exact-parameterization setting ($n=1$) in which the gradient descent enjoys an $\exp(-\Omega(T))$ rate.