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

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 α and threshold κ. 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 κ>κno-mem.\, state (κno-mem.\, state~ √0.91log(N) for α=0.5 and N being the dimension of the problem). For κ<κno-mem.\, 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.