SciPost Submission Page
How to escape atypical regions in the symmetric binary perceptron: a journey through connected-solutions states
by Damien Barbier
This Submission thread is now published as
Submission summary
| Authors (as registered SciPost users): | Damien Barbier |
| Submission information | |
|---|---|
| Preprint Link: | https://arxiv.org/abs/2408.04479v3 (pdf) |
| Date accepted: | 2025-03-18 |
| Date submitted: | 2025-01-31 10:55 |
| Submitted by: | Barbier, Damien |
| Submitted to: | SciPost Physics |
| Ontological classification | |
|---|---|
| Academic field: | Physics |
| Specialties: |
|
| Approaches: | Theoretical, Computational |
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
List of changes
-In Sec. 1.2, when mentioning the replica computation being annealed, we redirected explicitely the reader to App B.2.
-In Sec 3, we added a few comments about time-ordered versus non time-ordered optimization of the chain potential.
-In Sec 4.2, we rephrased part of the discussion about sending the chain overlap 'm' to one. In particular, we insisted on the fact that it cannot be an adjustable order parameter since we want to describe connected solutions.
-In Sec 4.3, we added details about the overlap-gap appearing in the chain formalism. We also added a sketch of the chain potential to make the discussion clearer.
-In Sec 5.1, we added comments about the function rescaling time. In particular, we insisted on the fact that the slowing down of the dynamics makes this function convex.
-In Sec 5.2, we added the analytical form of the stable interactions distribution for the no-memory chain.
-In Sec 5.3, we mentioned that the simple planted computation (without connectivity criteria) has already been studied. However, it fails to describe the Monte-Carlo dynamics. Again in this section, we added a comment explaining why the correlation drops in Fig. 5 as the system size is increased.
-In Sec 5.4, we mentioned that the phase diagram does not change qualitatively as the value of alpha is changed.
-In Sec 6, the computation steps for the nested Markovian chain have been moved to App D.1. We also added a table summarizing the order parameters obtained after optimization for the presented memory kernels.
-We increased the font size in most of the figures included in the manuscript.
Published as SciPost Phys. 18, 115 (2025)
Reports on this Submission
Report
The author has made significant efforts to present some part of the article more clearly, and answered my questions satisfactorily. I recommend this article for publication.
Recommendation
Publish (surpasses expectations and criteria for this Journal; among top 10%)
Report
The author has made several changes to explain better the points I found unclear.
I believe the manuscript is worth publishing in its present form.
Recommendation
Publish (easily meets expectations and criteria for this Journal; among top 50%)