Clustering of solutions in the symmetric binary perceptron
This work addresses a foundational problem in machine learning theory by rigorously exploring the conditions for flat minimizers, which are crucial for generalization, though it is incremental as it focuses on a toy model.
The paper tackles the problem of understanding the existence of flat minimizers in neural networks by analyzing the symmetric binary perceptron as a constraint satisfaction problem, where flat minimizers correspond to large, dense clusters of solutions, and it provides rigorous first and second moment bounds for the existence of such clusters in certain parameter regimes.
The geometrical features of the (non-convex) loss landscape of neural network models are crucial in ensuring successful optimization and, most importantly, the capability to generalize well. While minimizers' flatness consistently correlates with good generalization, there has been little rigorous work in exploring the condition of existence of such minimizers, even in toy models. Here we consider a simple neural network model, the symmetric perceptron, with binary weights. Phrasing the learning problem as a constraint satisfaction problem, the analogous of a flat minimizer becomes a large and dense cluster of solutions, while the narrowest minimizers are isolated solutions. We perform the first steps toward the rigorous proof of the existence of a dense cluster in certain regimes of the parameters, by computing the first and second moment upper bounds for the existence of pairs of arbitrarily close solutions. Moreover, we present a non rigorous derivation of the same bounds for sets of $y$ solutions at fixed pairwise distances.