Learning by message-passing in networks of discrete synapses

Abstract

We show that a message-passing process allows to store in binary "material" synapses a number of random patterns which almost saturates the information theoretic bounds. We apply the learning algorithm to networks characterized by a wide range of different connection topologies and of size comparable with that of biological systems (e.g. $n\simeq 10^5-10^6$). The algorithm can be turned into an on-line --fault tolerant-- learning protocol of potential interest in modeling aspects of synaptic plasticity and in building neuromorphic devices.

4 pages, 3 figures; references updated and minor corrections; accepted in PRL

References in corpus (1)

• Survey-propagation decimation through distributed local computations

Cited by in corpus (90)

• Improved contact prediction in proteins: Using pseudolikelihoods to infer Potts models
• Statistical physics of inference: Thresholds and algorithms
• Perturbation Biology: inferring signaling networks in cellular systems
• Unreasonable Effectiveness of Learning Neural Networks: From Accessible States and Robust Ensembles to Basic Algorithmic Schemes
• Clustering by soft-constraint affinity propagation: Applications to gene-expression data
• 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
• The Overlap Gap Property: a Geometric Barrier to Optimizing over Random Structures
• Mean-field message-passing equations in the Hopfield model and its generalizations
• Shaping the learning landscape in neural networks around wide flat minima
• Statistical mechanics of complex neural systems and high dimensional data
• Entropy landscape and non-Gibbs solutions in constraint satisfaction problems
• Origin of the computational hardness for learning with binary synapses
• Efficiency of quantum versus classical annealing in non-convex learning problems
• Local entropy as a measure for sampling solutions in Constraint Satisfaction Problems
• Constraint satisfaction problems with isolated solutions are hard
• Statistical Mechanics of Steiner trees
• Storage capacity in symmetric binary perceptrons
• Inference from correlated patterns: a unified theory for perceptron learning and linear vector channels
• Region graph partition function expansion and approximate free energy landscapes: Theory and some numerical results
• Unveiling the structure of wide flat minima in neural networks
• Collaboration in Social Networks
• Entropy landscape of solutions in the binary perceptron problem
• Aligning graphs and finding substructures by a cavity approach
• Relaxed Survey Propagation for The Weighted Maximum Satisfiability Problem
• Inference algorithms for gene networks: a statistical mechanics analysis
• The stochastic matching problem
• Generalization learning in a perceptron with binary synapses
• Message Passing for Optimization and Control of Power Grid: Model of Distribution System with Redundancy
• A rigorous analysis of the cavity equations for the minimum spanning tree
• Learning may need only a few bits of synaptic precision
• Encoding for the Blackwell Channel with Reinforced Belief Propagation
• On the role of synaptic stochasticity in training low-precision neural networks
• Unsupervised feature learning from finite data by message passing: discontinuous versus continuous phase transition
• The large deviations of the whitening process in random constraint satisfaction problems
• A Max-Sum algorithm for training discrete neural networks
• On the performance of a cavity method based algorithm for the Prize-Collecting Steiner Tree Problem on graphs
• Clustering of solutions in the symmetric binary perceptron
• Stochastic optimization by message passing
• Weight space structure and analysis using a finite replica number in the Ising perceptron
• The edge-disjoint path problem on random graphs by message-passing
• Learning of correlated patterns by simple perceptrons
• Monte Carlo algorithms are very effective in finding the largest independent set in sparse random graphs
• Deep learning via message passing algorithms based on belief propagation
• Solution space structure of random constraint satisfaction problems with growing domains
• Optimization by a quantum reinforcement algorithm
• Clustering with shallow trees
• Statistical physics approach to graphical games: local and global interactions
• On the Atypical Solutions of the Symmetric Binary Perceptron
• Efficient data compression from statistical physics of codes over finite fields
• Statistical mechanics of budget-constrained auctions
• Gene-network inference by message passing
• Enhancing the efficiency of quantum annealing via reinforcement: A path-integral Monte Carlo simulation of the quantum reinforcement algorithm
• Learning by random walks in the weight space of the Ising perceptron
• Combined local search strategy for learning in networks of binary synapses
• Constraint optimization and landscapes
• Optimal segmentation of directed graph and the minimum number of feedback arcs
• Classification and sparse-signature extraction from gene-expression data
• Theory and learning protocols for the material tempotron model
• Maximally flexible solutions of a random $K$-satisfiability formula
• Counting solutions from finite samplings
• How to escape atypical regions in the symmetric binary perceptron: a journey through connected-solutions states
• Palette-colouring: a belief-propagation approach
• Message passing algorithms for the Hopfield network reconstruction: threshold behavior and limitation
• Reinforced stochastic gradient descent for deep neural network learning
• Understanding the computational difficulty of a binary-weight perceptron and the advantage of input sparseness
• Equivalence between algorithmic instability and transition to replica symmetry breaking in perceptron learning systems
• Statics and dynamics of selfish interactions in distributed service systems
• Mean Field Bayes Backpropagation: scalable training of multilayer neural networks with binary weights
• A residual-based message passing algorithm for constraint satisfaction problems
• Susceptibility Propagation for Constraint Satisfaction Problems
• The Random Fractional Matching Problem
• Cavity approach to sphere packing in Hamming space
• Circumventing spin glass traps by microcanonical spontaneous symmetry breaking
• The solution space structure of planted constraint satisfaction problems with growing domains
• Inference by replication in densely connected systems
• Replication-based Inference Algorithms for Hard Computational Problems
• Quantum walk in a reinforced free-energy landscape: Quantum annealing with reinforcement
• Active online learning in the binary perceptron problem
• Stability of the replica symmetric solution in diluted perceptron learning
• Algorithmic thresholds in combinatorial optimization depend on the time scaling
• Noise tolerance via reinforcement: Learning a reinforced quantum dynamics
• Frozen $1$-RSB structure of the symmetric Ising perceptron
• Multi-Level Error-Resilient Neural Networks with Learning
• Improved Algorithm for the Network Alignment Problem with Application to Binary Diffing
• Biased thermodynamics can explain the behaviour of smart optimization algorithms that work above the dynamical threshold
• Statistical physics of principal minors: Cavity approach
• Training Multi-Layer Binary Neural Networks With Local Binary Error Signals
• A cavity approach to optimization and inverse dynamical problems
• The closest vector problem and the zero-temperature p-spin landscape for lossy compression