# Binary perceptron: efficient algorithms can find solutions in a rare well-connected cluster

arXiv: https://arxiv.org/abs/2111.03084 · HTML: https://mlsanity.com/paper/2111.03084/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 21 references that are in the map.
- First posted on arXiv 4 Nov 2021.

## Builds on (most cited first, 9 of 9)

- [Deep learning: a statistical viewpoint](https://mlsanity.com/paper/2103.09177/) (2021)
- [Unreasonable Effectiveness of Learning Neural Networks: From Accessible States and Robust Ensembles to Basic Algorithmic Schemes](https://mlsanity.com/paper/1605.06444/) (2016)
- [Subdominant Dense Clusters Allow for Simple Learning and High Computational Performance in Neural Networks with Discrete Synapses](https://mlsanity.com/paper/1509.05753/) (2015)
- [Unveiling the structure of wide flat minima in neural networks](https://mlsanity.com/paper/2107.01163/) (2021)
- [Local entropy as a measure for sampling solutions in Constraint Satisfaction Problems](https://mlsanity.com/paper/1511.05634/) (2015)
- [Proof of the Contiguity Conjecture and Lognormal Limit for the Symmetric Perceptron](https://mlsanity.com/paper/2102.13069/) (2021)
- [Discrete perceptrons](https://mlsanity.com/paper/1306.4375/) (2013)
- [Entropy landscape of solutions in the binary perceptron problem](https://mlsanity.com/paper/1304.2850/) (2013)
- [A Max-Sum algorithm for training discrete neural networks](https://mlsanity.com/paper/1505.05401/) (2015)

## Built on by (most cited first, 13 of 13)

- [Typical and atypical solutions in non-convex neural networks with discrete and continuous weights](https://mlsanity.com/paper/2304.13871/) (2023)
- [Binary perceptrons capacity via fully lifted random duality theory](https://mlsanity.com/paper/2312.00073/) (2023)
- [Fl RDT based ultimate lowering of the negative spherical perceptron capacity](https://mlsanity.com/paper/2312.16531/) (2023)
- [Rare dense solutions clusters in asymmetric binary perceptrons -- local entropy via fully lifted RDT](https://mlsanity.com/paper/2506.19276/) (2025)
- [A CLuP algorithm to practically achieve ~ 0.76 SK--model ground state free energy](https://mlsanity.com/paper/2507.09247/) (2025)
- [High-dimensional manifold of solutions in neural networks: insights from statistical physics](https://mlsanity.com/paper/2309.09240/) (2023)
- [Injectivity capacity of ReLU gates](https://mlsanity.com/paper/2410.20646/) (2024)
- [Binary perceptron computational gap -- a parametric fl RDT view](https://mlsanity.com/paper/2511.01037/) (2025)
- [Generative diffusion for perceptron problems: statistical physics analysis and efficient algorithms](https://mlsanity.com/paper/2502.16292/) (2025)
- [Parametric RDT approach to computational gap of symmetric binary perceptron](https://mlsanity.com/paper/2601.10628/) (2026)
- [Phase transition of descending phase retrieval algorithms](https://mlsanity.com/paper/2506.18275/) (2025)
- [A large deviation view of stationarized fully lifted blirp interpolation](https://mlsanity.com/paper/2506.19273/) (2025)
- [Ultrametric OGP - parametric RDT symmetric binary perceptron connection](https://mlsanity.com/paper/2604.19712/) (2026)

## Abstract (arXiv)

It was recently shown that almost all solutions in the symmetric binary perceptron are isolated, even at low constraint densities, suggesting that finding typical solutions is hard. In contrast, some algorithms have been shown empirically to succeed in finding solutions at low density. This phenomenon has been justified numerically by the existence of subdominant and dense connected regions of solutions, which are accessible by simple learning algorithms. In this paper, we establish formally such a phenomenon for both the symmetric and asymmetric binary perceptrons. We show that at low constraint density (equivalently for overparametrized perceptrons), there exists indeed a subdominant connected cluster of solutions with almost maximal diameter, and that an efficient multiscale majority algorithm can find solutions in such a cluster with high probability, settling in particular an open problem posed by Perkins-Xu '21. In addition, even close to the critical threshold, we show that there exist clusters of linear diameter for the symmetric perceptron, as well as for the asymmetric perceptron under additional assumptions.