Strong freezing in binary perceptron models
Abstract
The binary perceptron model concerns the set of solutions obtained by intersecting random half-spaces. One of the most striking physics predictions for this model, going back to Krauth and Mézard [KM89] and sharpened in [HWK13, HK14], is strong freezing: typical solutions are at Hamming distance of order n from every other solution. This phenomenon has attracted a lot of attention over the years, partly because of its intricate connections to statistical physics and computational complexity. We prove strong freezing at every positive constraint density for a general class of perceptron models and for any disorder with independent entries of mean zero and unit variance. More precisely, with probability at least 1−e−c√n, all but an e−c√n fraction of the solutions have no other solution within Hamming distance δn. In particular, our result includes the asymmetric binary perceptron at every margin, for which strong freezing has been a long-standing open problem [KM89,HWK13,HK14], and the symmetric binary perceptron, for which we recover the strong freezing results of Perkins and Xu [PX24] and of Abbe, Li and Sly [ALS21]. Our proof crucially relies on replacing the number of constraints by a Poisson variable, which makes the numbers of constraints cutting out different subsets of the hypercube independent. Since each constraint can only remove solutions, the FKG inequality then decouples the partition function from the event that two nearby configurations are both solutions.
Related
- State Evolution and Universality of Iterated Linear Programs for the Binary Perceptron
- Finite-Sample Binary Hypothesis Testing via Rényi Divergences: Strong Converse and Local Privacy
- Free energy fluctuations of symmetric perceptron models up to and including criticality
- A Robust Perceptron Cycling Theorem and Applications
- Generalization properties of the token perceptron: the role of embedding and vocabulary
BibTeX
@misc{gong2026strong,
title = {{Strong freezing in binary perceptron models}},
author = {Shuyang Gong and Shuangping Li},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.06275},
eprint = {2610.06275},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.06275},
}
RIS
TY - UNPB
TI - Strong freezing in binary perceptron models
AU - Shuyang Gong
AU - Shuangping Li
PY - 2026
DA - 2026/10/21
PB - arXiv
DO - 10.48550/arxiv.2610.06275
UR - https://arxiv.org/abs/2610.06275
AB - The binary perceptron model concerns the set of solutions obtained by intersecting random half-spaces. One of the most striking physics predictions for this model, going back to Krauth and Mézard [KM89] and sharpened in [HWK13, HK14], is strong freezing: typical solutions are at Hamming distance of order n from every other solution. This phenomenon has attracted a lot of attention over the years, partly because of its intricate connections to statistical physics and computational complexity. We prove strong freezing at every positive constraint density for a general class of perceptron models and for any disorder with independent entries of mean zero and unit variance. More precisely, with probability at least 1−e^−c√n, all but an e^−c√n fraction of the solutions have no other solution within Hamming distance δn. In particular, our result includes the asymmetric binary perceptron at every margin, for which strong freezing has been a long-standing open problem [KM89,HWK13,HK14], and the symmetric binary perceptron, for which we recover the strong freezing results of Perkins and Xu [PX24] and of Abbe, Li and Sly [ALS21]. Our proof crucially relies on replacing the number of constraints by a Poisson variable, which makes the numbers of constraints cutting out different subsets of the hypercube independent. Since each constraint can only remove solutions, the FKG inequality then decouples the partition function from the event that two nearby configurations are both solutions.
ER -