Equivalence between algorithmic instability and transition to replica symmetry breaking in perceptron learning systems
arXiv:2111.13302 · doi:10.1103/PhysRevResearch.4.023023
Abstract
Binary perceptron is a fundamental model of supervised learning for the non-convex optimization, which is a root of the popular deep learning. Binary perceptron is able to achieve a classification of random high-dimensional data by computing the marginal probabilities of binary synapses. The relationship between the algorithmic instability and the equilibrium analysis of the model remains elusive. Here, we establish the relationship by showing that the instability condition around the algorithmic fixed point is identical to the instability for breaking the replica symmetric saddle point solution of the free energy function. Therefore, our analysis would hopefully provide insights towards other learning systems in bridging the gap between non-convex learning dynamics and statistical mechanics properties of more complex neural networks.
arXiv comment24 pages, 2 figures, revision to journal
References in corpus (19)
- Message Passing Algorithms for Compressed Sensing
- The Bethe lattice spin glass revisited
- Statistical physics of inference: Thresholds and algorithms
- Probabilistic Reconstruction in Compressed Sensing: Algorithms, Phase Diagrams, and Threshold Achieving Matrices
- 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
- Phase Diagram of Restricted Boltzmann Machines and Generalised Hopfield Networks with Arbitrary Priors
- Origin of the computational hardness for learning with binary synapses
- Local entropy as a measure for sampling solutions in Constraint Satisfaction Problems
- Entropy landscape of solutions in the binary perceptron problem
- Propagating beliefs in spin glass models
- Statistical mechanics of unsupervised feature learning in a restricted Boltzmann machine with binary synapses
- On the role of synaptic stochasticity in training low-precision neural networks
- Equivalence of replica and cavity methods for computing spectra of sparse random matrices
- Statistical physics of unsupervised learning with prior knowledge in neural networks
- Minimal model of permutation symmetry in unsupervised learning
- Learning by random walks in the weight space of the Ising perceptron
- Combined local search strategy for learning in networks of binary synapses