Clustering of solutions in the symmetric binary perceptron

Abstract

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.

References in corpus (13)

• Clustering of solutions in the random satisfiability problem
• Unreasonable Effectiveness of Learning Neural Networks: From Accessible States and Robust Ensembles to Basic Algorithmic Schemes
• Learning by message-passing in networks of discrete synapses
• Subdominant Dense Clusters Allow for Simple Learning and High Computational Performance in Neural Networks with Discrete Synapses
• Efficient supervised learning in networks with binary synapses
• Shaping the learning landscape in neural networks around wide flat minima
• Origin of the computational hardness for learning with binary synapses
• Properties of the geometry of solutions and capacity of multi-layer neural networks with Rectified Linear Units activations
• Local entropy as a measure for sampling solutions in Constraint Satisfaction Problems
• Pairs of SAT Assignment in Random Boolean Formulae
• Storage capacity in symmetric binary perceptrons
• Generalization learning in a perceptron with binary synapses
• A Max-Sum algorithm for training discrete neural networks

Cited by in corpus (6)

• The Overlap Gap Property: a Geometric Barrier to Optimizing over Random Structures
• Learning through atypical "phase transitions" in overparameterized neural networks
• On the Atypical Solutions of the Symmetric Binary Perceptron
• How to escape atypical regions in the symmetric binary perceptron: a journey through connected-solutions states
• The closest vector problem and the zero-temperature p-spin landscape for lossy compression
• The maximum-average subtensor problem: equilibrium and out-of-equilibrium properties