Star-Shaped Space of Solutions of the Spherical Negative Perceptron

Empirical studies on the landscape of neural networks have shown that low-energy configurations are often found in complex connected structures, where zero-energy paths between pairs of distant solutions can be constructed. Here, we consider the spherical negative perceptron, a prototypical nonconvex neural network model framed as a continuous constraint satisfaction problem. We introduce a general analytical method for computing energy barriers in the simplex with vertex configurations sampled from the equilibrium. We find that in the overparametrized regime the solution manifold displays simple connectivity properties. There exists a large geodesically convex component that is attractive for a wide range of optimization dynamics. Inside this region we identify a subset of atypical high-margin solutions that are geodesically connected with most other solutions, giving rise to a star-shaped geometry. We analytically characterize the organization of the connected space of solutions and show numerical evidence of a transition, at larger constraint densities, where the aforementioned simple geodesic connectivity breaks down.

Figure 1

Sketch of the solution space of the negative perceptron in the RS phase. The red dotted line represents the border of the connected manifold of solutions for a given margin ${\kappa }_E$ (white-blue region). In the orange regions, the configurations have nonzero energy. The solutions that satisfy margins larger than the one of the problem, ${\kappa }_E<k_1<k_2$, are organized in a nested structure (darker shades of blue). When a typical solution with margin ${\kappa }_E$ is geodesically connected with a solution with margin $k_1$, an energy barrier (a crossing of the orange region) is observed. However, the $k_1$ solutions belong to a geodesically convex submanifold (the geodesic path falls within the white-blue region). Solutions with an even higher margin $k_2$, located in the kernel, are connected to almost any other solution. Definitions are provided in Appendix A.

Figure 2

Interpolating manifold between triplets of solutions for ${\kappa }_E=-0.5$, $\alpha =1$. (a) Solutions with the same margin $k={\kappa }_E$. (b) Solutions with different margins. The two bottom vertices are two typical solutions to the problem, i.e., $k_1={\kappa }_E$; the top vertex is sampled with $k_2=-0.1>{\kappa }_{\mathrm{krn}}({\kappa }_E,\alpha )\simeq -0.171$. The red level curve separates the zero from the nonzero energy region on the simplex. (c-top) Energy along the geodesic connecting two solutions sampled with margin $k$ for $k={\kappa }_E,-0.49,-0.48,-0.47$. (c-bottom) Same as the top panel but with the left endpoint margin fixed to $k_1={\kappa }_E$ and the one on the right having margin $k_2=-0.4,-0.35,-0.3$. Lines are the theoretical predictions, dots are large-$N$ extrapolations of the numerical simulations.

Figure 3

(a) Coalescence threshold lines at ${\kappa }_E=-0.5$ (blue and cyan), and the ${\kappa }_{\mathrm{krn}}$ threshold (green line) as a function of $\alpha$. In orange the dAT transition line, delimiting the RS-stable region; in red the RS estimate of the ${\kappa }_{\max }$. Above the dAT line, dashed lines indicate the continuation of the (unstable) RS predictions. Points are numerical extrapolations from SA samples (see SM for details). (b) Maximum error along the geodesic path ($y=2$) connecting numerical solutions found with different algorithms (PA, SA, and Xent) with the fBP max-margin solutions. Nonzero energies along the path indicate disconnection in the solution space. The vertical dashed lines denote the values of ${\alpha }_{dAT}$ and ${\alpha }_{LE}$ at ${\kappa }_E=-0.5$. The inset shows stability distributions for PA, SA, and Xent at $\alpha =2$ compared with the theoretical stability distribution of typical solutions (red dashed line).

Figure 4

Left: illustrative example of the projection of a straight path (blue) onto the geodesic (red) in the case of a one-dimensional path, i.e., $y=2$. All points along the geodesic (or that can be connected by a geodesic) are said to be geodesically connected. Right: simple 2-dimensional visualization of the shape of the manifold of solutions. The large geodesically convex component, (darker blue) and its kernel (purple) are also shown.

Figure 5

Top: maximum barrier height along the geodesic path connecting two SGD solutions obtained with the cross-entropy loss in function of $\alpha$. The training dynamics is stopped as soon as a solution is found. Inset: maximum barrier height along the geodesic path connecting SGD solutions with SA solutions. Bottom: maximum barrier height between two configurations initialized on typical solutions (obtained with SA) as a function of the number of SGD epochs on the cross-entropy loss. After a few epochs, the gradient drives the solutions toward the convex core.