How to escape atypical regions in the symmetric binary perceptron: a journey through connected-solutions states

Abstract

We study the binary symmetric perceptron model, and in particular its atypical solutions. While the solution-space of this problem is dominated by isolated configurations, it is also solvable for a certain range of constraint density $\alpha$ and threshold $\kappa$. We provide in this paper a statistical measure probing sequences of solutions, where two consecutive elements shares a strong overlap. After simplifications, we test its predictions by comparing it to Monte-Carlo simulations. We obtain good agreement and show that connected states with a Markovian correlation profile can fully decorrelate from their initialization only for $\kappa >{\kappa }_{\mathrm{no}-mem.\mathrm{state}}$ (${\kappa }_{\mathrm{no}-mem.\mathrm{state}}\sim \sqrt{0.91\log (N)}$ for $\alpha =0.5$ and $N$ being the dimension of the problem). For $\kappa <{\kappa }_{\mathrm{no}-mem.\mathrm{state}}$, we show that decorrelated sequences still exist but have a non-trivial correlations profile. To study this regime we introduce an $Ansatz$ for the correlations that we label as the nested Markov chain.

References in corpus (21)

• Analytical Solution of the Off-Equilibrium Dynamics of a Long Range Spin-Glass Model
• 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
• 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
• The Overlap Gap Property: a Geometric Barrier to Optimizing over Random Structures
• 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
• Constraint satisfaction problems with isolated solutions are hard
• Storage capacity in symmetric binary perceptrons
• Entropy landscape of solutions in the binary perceptron problem
• A frozen glass phase in the multi-index matching problem
• Quasi-equilibrium in glassy dynamics: an algebraic view
• A Max-Sum algorithm for training discrete neural networks
• Clustering of solutions in the symmetric binary perceptron
• On the Atypical Solutions of the Symmetric Binary Perceptron
• The asymptotics of the clustering transition for random constraint satisfaction problems
• Statistical mechanics of the maximum-average submatrix problem
• Quasi equilibrium construction for the long time limit of glassy dynamics

Cited by in corpus (1)

• The maximum-average subtensor problem: equilibrium and out-of-equilibrium properties