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 \alpha <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline"> <mml:mi>α</mml:mi> </mml:math> and threshold \kappa <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline"> <mml:mi>κ</mml:mi> </mml:math> . 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&amp;gt;\kappa_{no-mem. state} <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline"> <mml:mrow> <mml:mi>κ</mml:mi> <mml:mo>&gt;</mml:mo> <mml:msub> <mml:mi>κ</mml:mi> <mml:mrow> <mml:mi>n</mml:mi> <mml:mi>o</mml:mi> <mml:mo>−</mml:mo> <mml:mi>m</mml:mi> <mml:mi>e</mml:mi> <mml:mi>m</mml:mi> <mml:mi>.</mml:mi> <mml:mi>s</mml:mi> <mml:mi>t</mml:mi> <mml:mi>a</mml:mi> <mml:mi>t</mml:mi> <mml:mi>e</mml:mi> </mml:mrow> </mml:msub> </mml:mrow> </mml:math> ( \kappa_{no-mem. state}\sim \sqrt{0.91\log(N)} <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline"> <mml:mrow> <mml:msub> <mml:mi>κ</mml:mi> <mml:mrow> <mml:mi>n</mml:mi> <mml:mi>o</mml:mi> <mml:mo>−</mml:mo> <mml:mi>m</mml:mi> <mml:mi>e</mml:mi> <mml:mi>m</mml:mi> <mml:mi>.</mml:mi> <mml:mi>s</mml:mi> <mml:mi>t</mml:mi> <mml:mi>a</mml:mi> <mml:mi>t</mml:mi> <mml:mi>e</mml:mi> </mml:mrow> </mml:msub> <mml:mo>∼</mml:mo> <mml:msqrt> <mml:mrow> <mml:mn>0.91</mml:mn> <mml:mo>log</mml:mo> <mml:mo stretchy="false" form="prefix">(</mml:mo> <mml:mi>N</mml:mi> <mml:mo stretchy="false" form="postfix">)</mml:mo> </mml:mrow> </mml:msqrt> </mml:mrow> </mml:math> for \alpha=0.5 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline"> <mml:mrow> <mml:mi>α</mml:mi> <mml:mo>=</mml:mo> <mml:mn>0.5</mml:mn> </mml:mrow> </mml:math> and N <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline"> <mml:mi>N</mml:mi> </mml:math> being the dimension of the problem). For \kappa&lt;\kappa_{no-mem. state} <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline"> <mml:mrow> <mml:mi>κ</mml:mi> <mml:mo>&lt;</mml:mo> <mml:msub> <mml:mi>κ</mml:mi> <mml:mrow> <mml:mi>n</mml:mi> <mml:mi>o</mml:mi> <mml:mo>−</mml:mo> <mml:mi>m</mml:mi> <mml:mi>e</mml:mi> <mml:mi>m</mml:mi> <mml:mi>.</mml:mi> <mml:mi>s</mml:mi> <mml:mi>t</mml:mi> <mml:mi>a</mml:mi> <mml:mi>t</mml:mi> <mml:mi>e</mml:mi> </mml:mrow> </mml:msub> </mml:mrow> </mml:math> , 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.