  It has been empirically observed that, in deep neural networks, the solutions
found by stochastic gradient descent from different random initializations can
be often connected by a path with low loss. Recent works have shed light on
this intriguing phenomenon by assuming either the over-parameterization of the
network or the dropout stability of the solutions. In this paper, we reconcile
these two views and present a novel condition for ensuring the connectivity of
two arbitrary points in parameter space. This condition is provably milder than
dropout stability, and it provides a connection between the problem of finding
low-loss paths and the memorization capacity of neural nets. This last point
brings about a trade-off between the quality of features at each layer and the
over-parameterization of the network. As an extreme example of this trade-off,
we show that (i) if subsets of features at each layer are linearly separable,
then almost no over-parameterization is needed, and (ii) under generic
assumptions on the features at each layer, it suffices that the last two hidden
layers have $\Omega(\sqrt{N})$ neurons, $N$ being the number of samples.
Finally, we provide experimental evidence demonstrating that the presented
condition is satisfied in practical settings even when dropout stability does
not hold.
