# Equivalence between algorithmic instability and transition to replica symmetry breaking in perceptron learning systems

arXiv: https://arxiv.org/abs/2111.13302 · HTML: https://mlsanity.com/paper/2111.13302/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 43 references that are in the map.
- First posted on arXiv 26 Nov 2021.

## Builds on (most cited first, 13 of 13)

- [Statistical physics of inference: Thresholds and algorithms](https://mlsanity.com/paper/1511.02476/) (2015)
- [Unreasonable Effectiveness of Learning Neural Networks: From Accessible States and Robust Ensembles to Basic Algorithmic Schemes](https://mlsanity.com/paper/1605.06444/) (2016)
- [Subdominant Dense Clusters Allow for Simple Learning and High Computational Performance in Neural Networks with Discrete Synapses](https://mlsanity.com/paper/1509.05753/) (2015)
- [Phase Diagram of Restricted Boltzmann Machines and Generalised Hopfield Networks with Arbitrary Priors](https://mlsanity.com/paper/1702.05882/) (2017)
- [Learning through atypical "phase transitions" in overparameterized neural networks](https://mlsanity.com/paper/2110.00683/) (2021)
- [Local entropy as a measure for sampling solutions in Constraint Satisfaction Problems](https://mlsanity.com/paper/1511.05634/) (2015)
- [Proof of the Contiguity Conjecture and Lognormal Limit for the Symmetric Perceptron](https://mlsanity.com/paper/2102.13069/) (2021)
- [Origin of the computational hardness for learning with binary synapses](https://mlsanity.com/paper/1408.1784/) (2014)
- [Minimal model of permutation symmetry in unsupervised learning](https://mlsanity.com/paper/1904.13052/) (2019)
- [Entropy landscape of solutions in the binary perceptron problem](https://mlsanity.com/paper/1304.2850/) (2013)
- [Statistical mechanics of unsupervised feature learning in a restricted Boltzmann machine with binary synapses](https://mlsanity.com/paper/1612.01717/) (2016)
- [Statistical physics of unsupervised learning with prior knowledge in neural networks](https://mlsanity.com/paper/1911.02344/) (2019)
- [On the role of synaptic stochasticity in training low-precision neural networks](https://mlsanity.com/paper/1710.09825/) (2017)

## Built on by (most cited first, 1 of 1)

- [A short review on the maximum clique problem algorithms with classical, AI, and quantum methods](https://mlsanity.com/paper/2403.09742/) (2024)

## Abstract (arXiv)

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.