Frozen $1$-RSB structure of the symmetric Ising perceptron

Abstract

We prove, under an assumption on the critical points of a real-valued function, that the symmetric Ising perceptron exhibits the `frozen 1-RSB' structure conjectured by Krauth and Mezard in the physics literature; that is, typical solutions of the model lie in clusters of vanishing entropy density. Moreover, we prove this in a very strong form conjectured by Huang, Wong, and Kabashima: a typical solution of the model is isolated with high probability and the Hamming distance to all other solutions is linear in the dimension. The frozen 1-RSB scenario is part of a recent and intriguing explanation of the performance of learning algorithms by Baldassi, Ingrosso, Lucibello, Saglietti, and Zecchina. We prove this structural result by comparing the symmetric Ising perceptron model to a planted model and proving a comparison result between the two models. Our main technical tool towards this comparison is an inductive argument for the concentration of the logarithm of number of solutions in the model.

References in corpus (15)

• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Statistical physics of inference: Thresholds and algorithms
• Phase Transitions in the Coloring of Random Graphs
• 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
• Hiding Quiet Solutions in Random Constraint Satisfaction Problems
• 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
• Information-theoretic thresholds from the cavity method
• Origin of the computational hardness for learning with binary synapses
• Local entropy as a measure for sampling solutions in Constraint Satisfaction Problems
• Charting the replica symmetric phase
• Entropy landscape of solutions in the binary perceptron problem
• Generalization learning in a perceptron with binary synapses
• Sharp threshold for the Ising perceptron model