  The success of deep learning has revealed the application potential of neural
networks across the sciences and opened up fundamental theoretical problems. In
particular, the fact that learning algorithms based on simple variants of
gradient methods are able to find near-optimal minima of highly nonconvex loss
functions is an unexpected feature of neural networks. Moreover, such
algorithms are able to fit the data even in the presence of noise, and yet they
have excellent predictive capabilities. Several empirical results have shown a
reproducible correlation between the so-called flatness of the minima achieved
by the algorithms and the generalization performance. At the same time,
statistical physics results have shown that in nonconvex networks a multitude
of narrow minima may coexist with a much smaller number of wide flat minima,
which generalize well. Here we show that wide flat minima arise as complex
extensive structures, from the coalescence of minima around "high-margin"
(i.e., locally robust) configurations. Despite being exponentially rare
compared to zero-margin ones, high-margin minima tend to concentrate in
particular regions. These minima are in turn surrounded by other solutions of
smaller and smaller margin, leading to dense regions of solutions over long
distances. Our analysis also provides an alternative analytical method for
estimating when flat minima appear and when algorithms begin to find solutions,
as the number of model parameters varies.
