Source-linked AI summary
Subdominant Dense Clusters Allow for Simple Learning and High Computational Performance in Neural Networks with Discrete Synapses
Carlo Baldassi, Alessandro Ingrosso, Carlo Lucibello, Luca Saglietti, Riccardo Zecchina
TL;DR
The paper analyzes dense solution regions in discrete-synapse learning and develops methods for identifying them. Large-deviation analysis, learning extensions, and numerical experiments show accessible solution structures, efficient search behavior, and scope beyond the single-layer perceptron.
Problem
The analysis concerns the structure and accessibility of solution regions in discrete-synapse classification, including when standard methods are inadequate.
Method
The paper uses large-deviation analysis, extends CP+R to multilayer classifiers, and applies entropy-driven Monte Carlo to search for solutions.
Results
Entropy-driven Monte Carlo reached zero-energy solutions with time scaling almost linearly with N, while simulated annealing often became trapped in local minima.
Takeaways & Limitations
The analysis and algorithms extend beyond the single-layer perceptron to multilayer classifiers and random K-satisfiability settings.
Takeaways & Limitations
The reported analysis relies on the replica-symmetric assumption, whose stability requires further replica-symmetry-breaking calculations that are computationally too heavy.
Abstract
from arXiv · showhide
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.
SUPPLEMENTAL MATERIAL
The supplemental material lists the authors and their affiliations with Politecnico di Torino, Human Genetics Foundation-Torino, and Collegio Carlo Alberto.
- Carlo Baldassi, Alessandro Ingrosso, Carlo Lucibello, and Luca Saglietti are affiliated with Politecnico di Torino and Human Genetics Foundation-Torino.
- Riccardo Zecchina is affiliated with Politecnico di Torino and Human Genetics Foundation-Torino.
- Riccardo Zecchina is also affiliated with Collegio Carlo Alberto in Moncalieri, Italy.
A. Brief description of the heuristic algorithms
The supplemental material describes four heuristic algorithms for large-N classification: R-BP, R-MS, SBPI, and CP+R. They range from reinforced message-passing methods to simpler online synaptic-update rules using local information.
- Four algorithms are identified for solving the large-N classification problem in sub-exponential time: R-BP, R-MS, SBPI, and CP+R.
- R-BP reinforces Belief Propagation with a time-dependent field that progressively polarizes marginals toward one configuration.
- R-MS parallels R-BP but uses Max-Sum instead of Belief Propagation, producing similar characteristics.
- SBPI simplifies R-BP into an online algorithm using locally available synaptic information and finitely many discrete internal states.
- CP+R further simplifies SBPI by replacing near-threshold updates with generalized stochastic unsupervised synaptic reinforcement.
B. Large deviation analysis
The analysis uses a replica-symmetric large-deviation framework to characterize solution density around reference configurations, with overlap and entropy constraints defining physically meaningful regions. It finds that reference solutions are generally non-unique and that the resulting picture agrees well with numerical evidence except in specific high-α regions where the approximation breaks down.
- Large deviation analysis: Constraining the distance is essential for revealing dense subdominant regions, which do not appear in the corresponding unconstrained standard 1-RSB equations.The replica-symmetric construction is structurally reminiscent of 1-RSB, but the distance constraint is what exposes the dense regions.
- Large deviation analysis: The external entropy is set to zero to determine y⋆, the largest reweighting value for which the replica-symmetric results remain physically consistent.For larger y, the external entropy becomes negative, which signals a problem with the replica-symmetric assumption.
- Large deviation analysis: In all analyzed cases, q̃<1 implies that the reference solutions are not unique, while the typical number of reference solutions remains sub-exponential in N.This establishes that the analysis selects families of reference solutions rather than a single reference configuration.
- Large deviation analysis: The analytical picture agrees well with numerical evidence outside problematic high-α regions, although those regions are inadequately described by the replica-symmetric ansatz.The problematic intervals occur at high α, while further replica-symmetry-breaking calculations are computationally too heavy; reported internal entropies are probably lower bounds.
C. Multi-layer network with binary synapses
The paper extends CP+R to multilayer classifiers with binary synapses and trains them using simple error back-propagation alongside the unchanged unsupervised process.
- C. Multi-layer network with binary synapses: The multilayer architecture uses K2 committee machines, each containing K1 hidden units, feeding L summation nodes and an argmax readout.The synaptic weights and output weights are binary.
- C. Multi-layer network with binary synapses: When a pattern is misclassified, error signals are sent to committee machines that contributed to the error, and selected hidden units update by the CP+R supervised rule.The hidden unit chosen among those with wrong outputs is the one whose relevant contribution is easiest to fix.
- C. Multi-layer network with binary synapses: A robustness setting also emits an error signal for correct classifications when the top two penultimate-layer outputs differ by less than threshold r.
- C. Multi-layer network with binary synapses: The network was evaluated on MNIST with 10 labels, using 7 · 10^4 grayscale images and 10^4 held-out examples for generalization assessment.Inputs were preprocessed with a Restricted Boltzmann Machine producing N = 501 output nodes, though simpler preprocessing had only minor performance effects.
Perceptron
Entropy-driven Monte Carlo reaches zero-energy perceptron solutions efficiently, whereas simulated annealing can remain trapped in local minima.
- Perceptron: EdMC reaches zero-energy solutions in a time scaling almost linearly with N, while simulated annealing often gets stuck even at low loading.
- Perceptron: At α = 0.3, EdMC required approximately N^1.2 iterations across 100 random classification instances for N ∈ {201, 401, 801, 1601}.
Random K-satisfiability
Entropy-driven Monte Carlo is faster than simulated annealing on both 3-SAT in the replica-symmetric phase and 4-SAT in the replica-symmetry-breaking regime.
- Random K-satisfiability: EdMC has a much faster running time than simulated annealing in both the 3-SAT RS phase and the 4-SAT RSB regime.The 4-SAT regime is one where simulated annealing is known to fail.
- Random K-satisfiability: For α = 3.0 in 3-SAT, the reported scaling is N^1.23, while for α = 8.0 in 4-SAT it is N^1.18.The estimates use N values from 100 to 10,000 and sample counts from 1000 to 20.