TY - GEN

T1 - Proof of the Contiguity Conjecture and Lognormal Limit for the Symmetric Perceptron

AU - Abbe, Emmanuel

AU - Li, Shuangning

AU - Sly, Allan

N1 - Publisher Copyright:
© 2022 IEEE.

PY - 2022

Y1 - 2022

N2 - 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 log-normal 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ézard '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 lognor-mal 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.

AB - 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 log-normal 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ézard '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 lognor-mal 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.

KW - freezing

KW - interpo-lation

KW - neural networks

KW - partition function

KW - perceptron model

KW - sharp thresholds

KW - solution space

UR - http://www.scopus.com/inward/record.url?scp=85127115705&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85127115705&partnerID=8YFLogxK

U2 - 10.1109/FOCS52979.2021.00041

DO - 10.1109/FOCS52979.2021.00041

M3 - Conference contribution

AN - SCOPUS:85127115705

T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

SP - 327

EP - 338

BT - Proceedings - 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science, FOCS 2021

PB - IEEE Computer Society

T2 - 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021

Y2 - 7 February 2022 through 10 February 2022

ER -