OpenAlex ·

Strong freezing in binary perceptron models

Shuyang Gong and Shuangping Li

Published
Source
OpenAlex
Published in
arXiv (Cornell University)
DOI
10.48550/arxiv.2610.06275
Original
Read it at the publisher
Topics
Artificial Intelligence

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\sqrt n}$, all but an $e^{-c\sqrt 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.

The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.

Read it on ReadSearch

Each opens after you create an account, and brings you back to this paper.

Already a reader? Sign in

All new papers in Artificial Intelligence

Get the few papers worth your time in Artificial Intelligence every morning.

ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.

Papers belong to their authors and publishers; every page here links to the original. All research topics