Rare dense solutions clusters in asymmetric binary perceptrons — local entropy via fully lifted RDT
arXiv:2506.19276v1 Announce Type: new
Abstract: We study classical asymmetric binary perceptron (ABP) and associated emph{local entropy} (LE) as potential source of its algorithmic hardness. Isolation of emph{typical} ABP solutions in SAT phase seemingly suggests a universal algorithmic hardness. Paradoxically, efficient algorithms do exist even for constraint densities $alpha$ fairly close but at a finite distance (emph{computational gap}) from the capacity. In recent years, existence of rare large dense clusters and magical ability of fast algorithms to find them have been posited as the conceptual resolution of this paradox. Monotonicity or breakdown of the LEs associated with such emph{atypical} clusters are predicated to play a key role in their thinning-out or even complete defragmentation.
Invention of fully lifted random duality theory (fl RDT) [90,93,94] allows studying random structures emph{typical} features. A large deviation upgrade, sfl LD RDT [96,97], moves things further and enables emph{atypical} features characterizations as well. Utilizing the machinery of [96,97] we here develop a generic framework to study LE as an ABP’s atypical feature. Already on the second level of lifting we discover that the LE results are closely matching those obtained through replica methods. For classical zero threshold ABP, we obtain that LE breaks down for $alpha$ in $(0.77,0.78)$ interval which basically matches $alphasim 0.75-0.77$ range that currently best ABP solvers can handle and effectively indicates that LE’s behavior might indeed be among key reflections of the ABP’s computational gaps presumable existence.
Abstract: We study classical asymmetric binary perceptron (ABP) and associated emph{local entropy} (LE) as potential source of its algorithmic hardness. Isolation of emph{typical} ABP solutions in SAT phase seemingly suggests a universal algorithmic hardness. Paradoxically, efficient algorithms do exist even for constraint densities $alpha$ fairly close but at a finite distance (emph{computational gap}) from the capacity. In recent years, existence of rare large dense clusters and magical ability of fast algorithms to find them have been posited as the conceptual resolution of this paradox. Monotonicity or breakdown of the LEs associated with such emph{atypical} clusters are predicated to play a key role in their thinning-out or even complete defragmentation.
Invention of fully lifted random duality theory (fl RDT) [90,93,94] allows studying random structures emph{typical} features. A large deviation upgrade, sfl LD RDT [96,97], moves things further and enables emph{atypical} features characterizations as well. Utilizing the machinery of [96,97] we here develop a generic framework to study LE as an ABP’s atypical feature. Already on the second level of lifting we discover that the LE results are closely matching those obtained through replica methods. For classical zero threshold ABP, we obtain that LE breaks down for $alpha$ in $(0.77,0.78)$ interval which basically matches $alphasim 0.75-0.77$ range that currently best ABP solvers can handle and effectively indicates that LE’s behavior might indeed be among key reflections of the ABP’s computational gaps presumable existence.
Mihailo Stojnic
Go to original source