A Max-Sum algorithm for training discrete neural networks

Abstract

We present an efficient learning algorithm for the problem of training neural networks with discrete synapses, a well-known hard (NP-complete) discrete optimization problem. The algorithm is a variant of the so-called Max-Sum (MS) algorithm. In particular, we show how, for bounded integer weights with $q$ distinct states and independent concave a priori distribution (e.g. $l_1$ regularization), the algorithm's time complexity can be made to scale as $O\left(N\log N\right)$ per node update, thus putting it on par with alternative schemes, such as Belief Propagation (BP), without resorting to approximations. Two special cases are of particular interest: binary synapses $W\in \{-1,1\}$ and ternary synapses $W\in \{-1,0,1\}$ with $l_0$ regularization. The algorithm we present performs as well as BP on binary perceptron learning problems, and may be better suited to address the problem on fully-connected two-layer networks, since inherent symmetries in two layer networks are naturally broken using the MS approach.

References in corpus (5)

• Containing epidemic outbreaks by message-passing techniques
• Finding undetected protein associations in cell signaling by belief propagation
• Efficient supervised learning in networks with binary synapses
• Origin of the computational hardness for learning with binary synapses
• Generalization learning in a perceptron with binary synapses

Cited by in corpus (10)

• Subdominant Dense Clusters Allow for Simple Learning and High Computational Performance in Neural Networks with Discrete Synapses
• Mean-field message-passing equations in the Hopfield model and its generalizations
• Efficiency of quantum versus classical annealing in non-convex learning problems
• Local entropy as a measure for sampling solutions in Constraint Satisfaction Problems
• Learning may need only a few bits of synaptic precision
• On the role of synaptic stochasticity in training low-precision neural networks
• Clustering of solutions in the symmetric binary perceptron
• On the Atypical Solutions of the Symmetric Binary Perceptron
• How to escape atypical regions in the symmetric binary perceptron: a journey through connected-solutions states
• Understanding the computational difficulty of a binary-weight perceptron and the advantage of input sparseness