# Subdominant Dense Clusters Allow for Simple Learning and High Computational Performance in Neural Networks with Discrete Synapses

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

## Key facts

- Cited by 39 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Sep 2015.

## Built on by (most cited first, 30 of 39)

- [Low-Pass Filtering SGD for Recovering Flat Optima in the Deep Learning Optimization Landscape](https://mlsanity.com/paper/2201.08025/) (2022)
- [Deep Networks on Toroids: Removing Symmetries Reveals the Structure of Flat Regions in the Landscape Geometry](https://mlsanity.com/paper/2202.03038/) (2022)
- [Learning through atypical "phase transitions" in overparameterized neural networks](https://mlsanity.com/paper/2110.00683/) (2021)
- [Proof of the Contiguity Conjecture and Lognormal Limit for the Symmetric Perceptron](https://mlsanity.com/paper/2102.13069/) (2021)
- [Binary perceptron: efficient algorithms can find solutions in a rare well-connected cluster](https://mlsanity.com/paper/2111.03084/) (2021)
- [Typical and atypical solutions in non-convex neural networks with discrete and continuous weights](https://mlsanity.com/paper/2304.13871/) (2023)
- [Deep learning via message passing algorithms based on belief propagation](https://mlsanity.com/paper/2110.14583/) (2021)
- [High-dimensional learning of narrow neural networks](https://mlsanity.com/paper/2409.13904/) (2024)
- [Entropy-MCMC: Sampling from Flat Basins with Ease](https://mlsanity.com/paper/2310.05401/) (2023)
- [Exact full-RSB SAT/UNSAT transition in infinitely wide two-layer neural networks](https://mlsanity.com/paper/2410.06717/) (2024)
- [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)
- [Learning Capacity: A Measure of the Effective Dimensionality of a Model](https://mlsanity.com/paper/2305.17332/) (2023)
- [High-dimensional manifold of solutions in neural networks: insights from statistical physics](https://mlsanity.com/paper/2309.09240/) (2023)
- [PAC Bayesian Performance Guarantees for Deep (Stochastic) Networks in Medical Imaging](https://mlsanity.com/paper/2104.05600/) (2021)
- [Perturbated Gradients Updating within Unit Space for Deep Learning](https://mlsanity.com/paper/2110.00199/) (2021)
- [BOLD: Boolean Logic Deep Learning](https://mlsanity.com/paper/2405.16339/) (2024)
- [Bilinear Sequence Regression: A Model for Learning from Long Sequences of High-dimensional Tokens](https://mlsanity.com/paper/2410.18858/) (2024)
- [Transfer Learning in Infinite Width Feature Learning Networks](https://mlsanity.com/paper/2507.04448/) (2025)
- [CLuP practically achieves ~ 1.77 positive and ~ 0.33 negative Hopfield model ground state free energy](https://mlsanity.com/paper/2507.22396/) (2025)
- [Binary perceptron computational gap -- a parametric fl RDT view](https://mlsanity.com/paper/2511.01037/) (2025)
- [Boolean Variation and Boolean Logic BackPropagation](https://mlsanity.com/paper/2311.07427/) (2023)
- [Equivalence between algorithmic instability and transition to replica symmetry breaking in perceptron learning systems](https://mlsanity.com/paper/2111.13302/) (2021)
- [Bayes Complexity of Learners vs Overfitting](https://mlsanity.com/paper/2303.07874/) (2023)
- [Flat Posterior Does Matter For Bayesian Model Averaging](https://mlsanity.com/paper/2406.15664/) (2024)
- [Training Multi-Layer Binary Neural Networks With Local Binary Error Signals](https://mlsanity.com/paper/2412.00119/) (2024)
- [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)
- [Entropic alternatives to initialization](https://mlsanity.com/paper/2107.07757/) (2021)
- [Low-power multi-mode fiber projector overcomes shallow neural networks classifiers](https://mlsanity.com/paper/2210.04745/) (2022)

## Abstract (arXiv)

We show that discrete synaptic weights can be efficiently used for learning in large scale neural systems, and lead to unanticipated computational performance. We focus on the representative case of learning random patterns with binary synapses in single layer networks. The standard statistical analysis shows that this problem is exponentially dominated by isolated solutions that are extremely hard to find algorithmically. Here, we introduce a novel method that allows us to find analytical evidence for the existence of subdominant and extremely dense regions of solutions. Numerical experiments confirm these findings. We also show that the dense regions are surprisingly accessible by simple learning protocols, and that these synaptic configurations are robust to perturbations and generalize better than typical solutions. These outcomes extend to synapses with multiple states and to deeper neural architectures. The large deviation measure also suggests how to design novel algorithmic schemes for optimization based on local entropy maximization.