  A recent line of work has shown that an overparametrized neural network can
perfectly fit the training data, an otherwise often intractable nonconvex
optimization problem. For (fully-connected) shallow networks, in the best case
scenario, the existing theory requires quadratic over-parametrization as a
function of the number of training samples. This paper establishes that linear
overparametrization is sufficient to fit the training data, using a simple
variant of the (stochastic) gradient descent. Crucially, unlike several related
works, the training considered in this paper is not limited to the lazy regime
in the sense cautioned against in [1, 2]. Beyond shallow networks, the
framework developed in this work for over-parametrization is applicable to a
variety of learning problems.
