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

Abstract

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.

11 pages, 4 figures (main text: 5 pages, 3 figures; Supplemental Material: 6 pages, 1 figure)

References in corpus (7)

• Subdominant Dense Clusters Allow for Simple Learning and High Computational Performance in Neural Networks with Discrete Synapses
• Efficient supervised learning in networks with binary synapses
• Entropy landscape and non-Gibbs solutions in constraint satisfaction problems
• Origin of the computational hardness for learning with binary synapses
• Entropy landscape of solutions in the binary perceptron problem
• Generalization learning in a perceptron with binary synapses
• A Max-Sum algorithm for training discrete neural networks

Cited by in corpus (65)

• Machine learning and the physical sciences
• Binarized Neural Networks: Training Deep Neural Networks with Weights and Activations Constrained to +1 or -1
• Quantized Neural Networks: Training Neural Networks with Low Precision Weights and Activations
• XNOR-Net: ImageNet Classification Using Binary Convolutional Neural Networks
• Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data
• Unreasonable Effectiveness of Learning Neural Networks: From Accessible States and Robust Ensembles to Basic Algorithmic Schemes
• Neural Quantum States of frustrated magnets: generalization and sign structure
• Subdominant Dense Clusters Allow for Simple Learning and High Computational Performance in Neural Networks with Discrete Synapses
• Towards Understanding Generalization of Deep Learning: Perspective of Loss Landscapes
• Entropy-SGD: Biasing Gradient Descent Into Wide Valleys
• Shaping the learning landscape in neural networks around wide flat minima
• Non-Vacuous Generalization Bounds at the ImageNet Scale: A PAC-Bayesian Compression Approach
• Efficiency of quantum versus classical annealing in non-convex learning problems
• Properties of the geometry of solutions and capacity of multi-layer neural networks with Rectified Linear Units activations
• Local entropy as a measure for sampling solutions in Constraint Satisfaction Problems
• An Optimal Control Approach to Deep Learning and Applications to Discrete-Weight Neural Networks
• Storage capacity in symmetric binary perceptrons
• Mean-field inference methods for neural networks
• Unveiling the structure of wide flat minima in neural networks
• Sparsely-Connected Neural Networks: Towards Efficient VLSI Implementation of Deep Neural Networks
• Learning through atypical "phase transitions" in overparameterized neural networks
• Entropic gradient descent algorithms and wide flat minima
• Convergent Block Coordinate Descent for Training Tikhonov Regularized Deep Neural Networks
• Learning may need only a few bits of synaptic precision
• Spin glass theory and its new challenge: structured disorder
• On the role of synaptic stochasticity in training low-precision neural networks
• The large deviations of the whitening process in random constraint satisfaction problems
• Clustering of solutions in the symmetric binary perceptron
• Teacher-student learning for a binary perceptron with quantum fluctuations
• Deep learning via message passing algorithms based on belief propagation
• Dual time scales in simulated annealing of a two-dimensional Ising spin glass
• Wide flat minima and optimal generalization in classifying high-dimensional Gaussian mixtures
• Exact full-RSB SAT/UNSAT transition in infinitely wide two-layer neural networks
• Generalization from correlated sets of patterns in the perceptron
• On the Atypical Solutions of the Symmetric Binary Perceptron
• Iterative Low-Rank Approximation for CNN Compression
• SALR: Sharpness-aware Learning Rate Scheduler for Improved Generalization
• The Copycat Perceptron: Smashing Barriers Through Collective Learning
• Perturbated Gradients Updating within Unit Space for Deep Learning
• Maximally flexible solutions of a random $K$-satisfiability formula
• Partial local entropy and anisotropy in deep weight spaces
• Optimization of the dynamic transition in the continuous coloring problem
• Statistical mechanics of the maximum-average submatrix problem
• Counting and Hardness-of-Finding Fixed Points in Cellular Automata on Random Graphs
• How to escape atypical regions in the symmetric binary perceptron: a journey through connected-solutions states
• Equivalence between algorithmic instability and transition to replica symmetry breaking in perceptron learning systems
• Data-driven effective model shows a liquid-like deep learning
• Reinforced stochastic gradient descent for deep neural network learning
• Understanding the computational difficulty of a binary-weight perceptron and the advantage of input sparseness
• EasyConvPooling: Random Pooling with Easy Convolution for Accelerating Training and Testing
• Active online learning in the binary perceptron problem
• Variational Characterizations of Local Entropy and Heat Regularization in Deep Learning
• MUSCO: Multi-Stage Compression of neural networks
• Biased thermodynamics can explain the behaviour of smart optimization algorithms that work above the dynamical threshold
• Bilinear Sequence Regression: A Model for Learning from Long Sequences of High-dimensional Tokens
• Algorithmic thresholds in combinatorial optimization depend on the time scaling
• Frozen $1$-RSB structure of the symmetric Ising perceptron
• Entropy-SGD optimizes the prior of a PAC-Bayes bound: Generalization properties of Entropy-SGD and data-dependent priors
• Stochastic Backward Euler: An Implicit Gradient Descent Algorithm for $k$-means Clustering
• Optimization of neural networks via finite-value quantum fluctuations
• Deep Networks on Toroids: Removing Symmetries Reveals the Structure of Flat Regions in the Landscape Geometry
• The maximum-average subtensor problem: equilibrium and out-of-equilibrium properties
• SGB: Stochastic Gradient Bound Method for Optimizing Partition Functions
• Training Multi-Layer Binary Neural Networks With Local Binary Error Signals
• Native state of natural proteins optimises local entropy