Unveiling the Structure of Wide Flat Minima in Neural Networks

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.

Figure 1

Representation of a portion of the space of network configurations. The dots represent solutions (zero-error configurations) with different $\kappa$ margins. Red arrows indicate four examples of typical solutions. Yellow arrows indicate three examples of the type of atypical solutions found around the typical ones with a larger margin. Low-margin solutions are more numerous than high-margin solutions. Typical low-margin solutions are isolated and distant from each other. Typical high-margin solutions are also distant from each other, but less so, and tend to be surrounded by (atypical) low-margin solutions. Thus, the higher-margin solutions are rare, but they lie within dense, extended regions that result from the coalescence of the low-margin solutions.

Figure 2

Normalized Hamming distance between typical solutions as a function of their margin, for $\alpha =0.2$, 0.3, 0.4, 0.6, and 0.8 (top to bottom). The lines become dashed when the entropy of solutions becomes negative, i.e., when $\kappa >{\kappa }_{\max }$ (see text).

Figure 3

Local entropy profiles (with $\kappa =0$) of typical solutions at $\alpha =0.5$ as a function of the distance, for various values of $\tilde{\kappa }$. The dashed line is the geometric upper bound obtained by counting all the configurations. The inset shows a detail of the three curves for $\tilde{\kappa }=0.02$, 0.03, and 0.04 in the small-$d$ range. We observe that for $\tilde{\kappa }=0$ the solutions are isolated (the curve is missing for small distances due to numerical issues, but see [28]). For $0<\tilde{\kappa }<{\tilde{\kappa }}_{\min }\simeq 0.03$ the entropy has a small positive dense region at small $d$ and there is an interval where it is negative (see the $\tilde{\kappa }=0.02$ curve). For ${\tilde{\kappa }}_{\min }\le \tilde{\kappa }<{\tilde{\kappa }}_u\simeq 0.04$ the profiles are all positive, but there is a local maximum (see the $\tilde{\kappa }=0.03$ curve). For larger $\tilde{\kappa }$, they grow monotonically up to the global maximum located at a large distance $d^{*}(\tilde{\kappa })$ (not visible). The entropy is a monotonic function of $\tilde{\kappa }$ for all distances up to $d^{*}({\tilde{\kappa }}_{\max })\simeq 0.285$, and the highest curve is the one for ${\tilde{\kappa }}_{\max }\simeq 0.418$. The points with error bars show the results of numerical experiments (ten samples at $N=2001$ obtained with the focusing-BP (FBP) algorithm, which by design seeks high-local-entropy solutions; local entropy estimated by belief propagation, see SM [23]).

Figure 4

Local entropy profiles (with $\kappa =0$) of typical maximum margin solutions (left panel) and its derivative (right panel) as a function of the distance, for different values of $\alpha$. For $\alpha =0.71$ and 0.727 the entropy is monotonic, i.e., it has a unique maximum at large distances (not visible). For $\alpha ={\alpha }_u^{\prime }\simeq 0.729$ the local entropy starts to be nonmonotonic (its derivative with respect to the distance develops a new zero). The entropy becomes negative at larger $\alpha$ [i.e., ${\tilde{\kappa }}_{\max }(\alpha )<{\tilde{\kappa }}_{\min }(\alpha )$] in a given range of distances.