  A candidate explanation of the good empirical performance of deep neural
networks is the implicit regularization effect of first order optimization
methods. Inspired by this, we prove a convergence theorem for nonconvex
composite optimization, and apply it to a general learning problem covering
many machine learning applications, including supervised learning. We then
present a deep multilayer perceptron model and prove that, when sufficiently
wide, it $(i)$ leads to the convergence of gradient descent to a global optimum
with a linear rate, $(ii)$ benefits from the implicit regularization effect of
gradient descent, $(iii)$ is subject to novel bounds on the generalization
error, $(iv)$ exhibits the lazy training phenomenon and $(v)$ enjoys learning
rate transfer across different widths. The corresponding coefficients, such as
the convergence rate, improve as width is further increased, and depend on the
even order moments of the data generating distribution up to an order depending
on the number of layers. The only non-mild assumption we make is the
concentration of the smallest eigenvalue of the neural tangent kernel at
initialization away from zero, which has been shown to hold for a number of
less general models in contemporary works. We present empirical evidence
supporting this assumption as well as our theoretical claims.
