  A main puzzle of deep neural networks (DNNs) revolves around the apparent
absence of "overfitting", defined in this paper as follows: the expected error
does not get worse when increasing the number of neurons or of iterations of
gradient descent. This is surprising because of the large capacity demonstrated
by DNNs to fit randomly labeled data and the absence of explicit
regularization. Recent results by Srebro et al. provide a satisfying solution
of the puzzle for linear networks used in binary classification. They prove
that minimization of loss functions such as the logistic, the cross-entropy and
the exp-loss yields asymptotic, "slow" convergence to the maximum margin
solution for linearly separable datasets, independently of the initial
conditions. Here we prove a similar result for nonlinear multilayer DNNs near
zero minima of the empirical loss. The result holds for exponential-type losses
but not for the square loss. In particular, we prove that the weight matrix at
each layer of a deep network converges to a minimum norm solution up to a scale
factor (in the separable case). Our analysis of the dynamical system
corresponding to gradient descent of a multilayer network suggests a simple
criterion for ranking the generalization performance of different zero
minimizers of the empirical loss.
