On the Atypical Solutions of the Symmetric Binary Perceptron

Abstract

We study the random binary symmetric perceptron problem, focusing on the behavior of rare high-margin solutions. While most solutions are isolated, we demonstrate that these rare solutions are part of clusters of extensive entropy, heuristically corresponding to non-trivial fixed points of an approximate message-passing algorithm. We enumerate these clusters via a local entropy, defined as a Franz-Parisi potential, which we rigorously evaluate using the first and second moment methods in the limit of a small constraint density $\alpha$ (corresponding to vanishing margin $\kappa$) under a certain assumption on the concentration of the entropy. This examination unveils several intriguing phenomena: i) We demonstrate that these clusters have an entropic barrier in the sense that the entropy as a function of the distance from the reference high-margin solution is non-monotone when $\kappa \le 1.429\sqrt{-\alpha /\log \alpha }$, while it is monotone otherwise, and that they have an energetic barrier in the sense that there are no solutions at an intermediate distance from the reference solution when $\kappa \le 1.239\sqrt{-\alpha /\log \alpha }$. The critical scaling of the margin $\kappa$ in $\sqrt{-\alpha /\log \alpha }$ corresponds to the one obtained from the earlier work of Gamarnik et al. (2022) for the overlap-gap property, a phenomenon known to present a barrier to certain efficient algorithms. ii) We establish using the replica method that the complexity (the logarithm of the number of clusters of such solutions) versus entropy (the logarithm of the number of solutions in the clusters) curves are partly non-concave and correspond to very large values of the Parisi parameter, with the equilibrium being reached when the Parisi parameter diverges.

26 pages, 6 figures

References in corpus (22)

• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• The structural glass transition and the entropy of the metastable states
• Phase Transitions in the Coloring of Random Graphs
• Recipes for metastable states in Spin Glasses
• 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
• Survey Propagation as local equilibrium equations
• 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
• Polynomial iterative algorithms for coloring and analyzing random graphs
• Origin of the computational hardness for learning with binary synapses
• Local entropy as a measure for sampling solutions in Constraint Satisfaction Problems
• Locked constraint satisfaction problems
• Royen's proof of the Gaussian correlation inequality
• Constraint satisfaction problems with isolated solutions are hard
• Storage capacity in symmetric binary perceptrons
• Unveiling the structure of wide flat minima in neural networks
• Entropy landscape of solutions in the binary perceptron problem
• A frozen glass phase in the multi-index matching problem
• A Max-Sum algorithm for training discrete neural networks
• Clustering of solutions in the symmetric binary perceptron
• The asymptotics of the clustering transition for random constraint satisfaction problems

Cited by in corpus (2)

• How to escape atypical regions in the symmetric binary perceptron: a journey through connected-solutions states
• The maximum-average subtensor problem: equilibrium and out-of-equilibrium properties