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

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.

24 pages, 2 figures, revision to journal

References in corpus (4)

• Probabilistic Reconstruction in Compressed Sensing: Algorithms, Phase Diagrams, and Threshold Achieving Matrices
• Origin of the computational hardness for learning with binary synapses
• Equivalence of replica and cavity methods for computing spectra of sparse random matrices
• Learning by random walks in the weight space of the Ising perceptron

Cited by in corpus (2)

• A short review on the maximum clique problem algorithms with classical, AI, and quantum methods
• Replica analysis of the lattice-gas Restricted Boltzmann Machine partition function