  Current deep neural networks are highly overparameterized (up to billions of
connection weights) and nonlinear. Yet they can fit data almost perfectly
through variants of gradient descent algorithms and achieve unexpected levels
of prediction accuracy without overfitting. These are formidable results that
defy predictions of statistical learning and pose conceptual challenges for
non-convex optimization. In this paper, we use methods from statistical physics
of disordered systems to analytically study the computational fallout of
overparameterization in non-convex binary neural network models, trained on
data generated from a structurally simpler but "hidden" network. As the number
of connection weights increases, we follow the changes of the geometrical
structure of different minima of the error loss function and relate them to
learning and generalization performance. A first transition happens at the
so-called interpolation point, when solutions begin to exist (perfect fitting
becomes possible). This transition reflects the properties of typical
solutions, which however are in sharp minima and hard to sample. After a gap, a
second transition occurs, with the discontinuous appearance of a different kind
of "atypical" structures: wide regions of the weight space that are
particularly solution-dense and have good generalization properties. The two
kinds of solutions coexist, with the typical ones being exponentially more
numerous, but empirically we find that efficient algorithms sample the
atypical, rare ones. This suggests that the atypical phase transition is the
relevant one for learning. The results of numerical tests with realistic
networks on observables suggested by the theory are consistent with this
scenario.
