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

2021/11/04 by Emmanuel Abbé, Shuangping Li, Abbe, Emmanuel +3 · 9 citations
Computer Science · #FOS: Computer and information sciences #FOS: Mathematics #FOS: Physical sciences #Machine Learning (stat.ML) #Mathematical Physics (math-ph) #Neural Networks and Applications #Probability (math.PR) #Rough Sets and Fuzzy Logic #Topological and Geometric Data Analysis

paper · pdf · doi:10.48550/arxiv.2111.03084

openalex publication_date 2021/11/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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.

Cited by

• Binary perceptron computational gap -- a parametric fl RDT view
• A threshold for online balancing of sparse i.i.d. vectors
• Polynomial-time sampling despite disorder chaos
• A CLuP algorithm to practically achieve ∼ 0.76 SK--model ground state free energy
• Rare dense solutions clusters in asymmetric binary perceptrons -- local entropy via fully lifted RDT
• A large deviation view of stationarized fully lifted blirp interpolation
• Phase transition of descending phase retrieval algorithms
• The maximum-average subtensor problem: equilibrium and out-of-equilibrium properties
• Overlap Gap and Computational Thresholds in the Square Wave Perceptron

Related

• Algorithms and Barriers in the Symmetric Binary Perceptron Model
• Hardness of sampling solutions from the Symmetric Binary Perceptron
• Rare dense solutions clusters in asymmetric binary perceptrons -- local entropy via fully lifted RDT
• Proof of the Contiguity Conjecture and Lognormal Limit for the Symmetric Perceptron
• Typical and atypical solutions in non-convex neural networks with discrete and continuous weights