RECORD
Proof of the Contiguity Conjecture and Lognormal Limit for the Symmetric Perceptron
Probability · Submitted 25 Feb 2021
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim We establish that the partition function of this model, normalized by its expected value, converges to a lognormal distribution.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
We consider the symmetric binary perceptron model, a simple model of neural networks that has gathered significant attention in the statistical physics, information theory and probability theory communities, with recent connections made to the performance of learning algorithms in Baldassi et al. '15. We establish that the partition function of this model, normalized by its expected value, converges to a lognormal distribution. As a consequence, this allows us to establish several conjectures for this model: (i) it proves the contiguity conjecture of Aubin et al. '19 between the planted and unplanted models in the satisfiable regime; (ii) it establishes the sharp threshold conjecture; (iii) it proves the frozen 1-RSB conjecture in the symmetric case, conjectured first by Krauth-M\'ezard '89 in the asymmetric case. In a recent work of Perkins-Xu '21, the last two conjectures were also established by proving that the partition function concentrates on an exponential scale, under an analytical assumption on a real-valued function. This left open the contiguity conjecture and the lognormal limit characterization, which are established here unconditionally, with the analytical assumption verified. In particular, our proof technique relies on a dense counter-part of the small graph conditioning method, which was developed for sparse models in the celebrated work of Robinson and Wormald.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | We consider the symmetric binary perceptron model, a simple model of neural networks that has gathered significant attention in the statistical physics, information theory and probability theory communities, with recent connections made to the performance of learning algorithms in Baldassi et al. '15. | background 1.00 | 0.08 | 0.03 | asserted 0.93 |
| s1 | We establish that the partition function of this model, normalized by its expected value, converges to a lognormal distribution. | result 0.98 | 0.96 | 0.78 | asserted 1.00 |
| s2 | As a consequence, this allows us to establish several conjectures for this model: (i) it proves the contiguity conjecture of Aubin et al. '19 between the planted and unplanted models in the satisfiable regime; (ii) it establishes the sharp threshold conjecture; (iii) it proves the frozen 1-RSB conjecture in the symmetric case, conjectured first by Krauth-M\'ezard '89 in the asymmetric case. | result 0.56 | 0.89 | 0.26 | asserted 1.00 |
| s3 | In a recent work of Perkins-Xu '21, the last two conjectures were also established by proving that the partition function concentrates on an exponential scale, under an analytical assumption on a real-valued function. | background 0.84 | 0.03 | 0.04 | asserted 1.00 |
| s4 | This left open the contiguity conjecture and the lognormal limit characterization, which are established here unconditionally, with the analytical assumption verified. | gap 0.53 | 0.92 | 0.33 | asserted 1.00 |
| s5 | In particular, our proof technique relies on a dense counter-part of the small graph conditioning method, which was developed for sparse models in the celebrated work of Robinson and Wormald. | method 0.99 | 0.56 | 0.03 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v2
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
We consider the symmetric binary perceptron model, a simple model of neural networks that has gathered significant attention in the statistical physics, information theory and probability theory communities, with recent connections made to the performance of learning algorithms in Baldassi et al. '15. We establish that the partition function of this model, normalized by its expected value, converges to a lognormal distribution. As a consequence, this allows us to establish several conjectures for this model: (i) it proves the contiguity conjecture of Aubin et al. '19 between the planted and unplanted models in the satisfiable regime; (ii) it establishes the sharp threshold conjecture; (iii) it proves the frozen 1-RSB conjecture in the symmetric case, conjectured first by Krauth-M\'ezard '89 in the asymmetric case. In a recent work of Perkins-Xu '21, the last two conjectures were also established by proving that the partition function concentrates on an exponential scale, under an analytical assumption on a real-valued function. This left open the contiguity conjecture and the lognormal limit characterization, which are established here unconditionally, with the analytical assumption verified. In particular, our proof technique relies on a dense counter-part of the small graph conditioning method, which was developed for sparse models in the celebrated work of Robinson and Wormald.
Human review
How the literature uses it
18 arXiv papers cite this in 27 sentences
Papers citing it · 19 sentences without a confident label
Uses its method or tool 1 paper
-
In [ref] , the authors used similar cycle counting techniques in ALR87,Ban20 to derive a log-normal limit theorem for $Z_M,N(G)$.
Mean Field Spin Glass Models under Weak External Field · Ising Perceptron Model · 0.89
Cites it as support 2 papers
-
One of the most emblematic cases supporting this line of thought is represented by the binary perceptron, for which has been recently proved [ref] that typical (i.e. almost all) solutions are completely frozen (isolated) in the clustered phase, and hence inaccessible to any known algorithm.
Biased thermodynamics can explain the behaviour of smart optimization algorithms that work above the dynamical threshold · Introduction · 0.98
-
This scenario was also recently confirmed in simple one-hidden layer neural networks with generic activation functions [ref] and also rigorously for the symmetric perceptron [ref] .
Unveiling the structure of wide flat minima in neural networks · Introduction · 0.96
Cites it as background 4 papers
-
Recent works including [ref] have studied these structural predictions.
Geometric Barriers for Stable and Online Algorithms for Discrepancy Minimization · Symmetric Binary Perceptron () · 0.93
-
Each constraint rules out certain solutions in the space $ℬ_n$ of all possible solutions; and the parameter $α$ plays a role akin to the constraint density in the literature on random $k-$SAT, see e.g. [ref] for more discussion.
Algorithms and Barriers in the Symmetric Binary Perceptron Model · Asymmetric Binary Perceptron · 0.96
-
In a different direction, numerous recent works have studied symmetric perceptron models, which are significantly more tractable than the half-space models and can be analyzed for much finer properties [ref] .
Sharp threshold sequence and universality for Ising perceptron models · Introduction · 0.95
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.