# A Max-Sum algorithm for training discrete neural networks

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 May 2015.

## Built on by (most cited first, 5 of 5)

- [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)
- [BOLD: Boolean Logic Deep Learning](https://mlsanity.com/paper/2405.16339/) (2024)
- [Boolean Variation and Boolean Logic BackPropagation](https://mlsanity.com/paper/2311.07427/) (2023)
- [Generative diffusion for perceptron problems: statistical physics analysis and efficient algorithms](https://mlsanity.com/paper/2502.16292/) (2025)

## Abstract (arXiv)

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. l1 regularization), the algorithm's time complexity can be made to scale as Oleft(Nlog Nright) 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∈-1,1 and ternary synapses W∈-1,0,1 with l0 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.