SciPost Submission Page

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

by Damien Barbier

Submission summary

Authors (as registered SciPost users):

Damien Barbier

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_{\rm no-mem.\, state}$ ($\kappa_{\rm no-mem.\, state}\sim \sqrt{0.91\log(N)}$ for $\alpha=0.5$ and $N$ being the dimension of the problem). For $\kappa<\kappa_{\rm 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.

Author indications on fulfilling journal expectations

• Provide a novel and synergetic link between different research areas.
• Open a new pathway in an existing or a new research direction, with clear potential for multi-pronged follow-up work
• Detail a groundbreaking theoretical/experimental/computational discovery
• Present a breakthrough on a previously-identified and long-standing research stumbling block