Deep learning via message passing algorithms based on belief propagation
Authors: Fabrizio Pittorino
Carlo Lucibello
Gabriele Perugini
Riccardo Zecchina
Venue: ICLR 2022 Submitted (2022)
Keywords: belief propagation
neural networks
graphical models
gradient-free algorithms
discrete neural networks

Abstract: Message-passing algorithms based on the Belief Propagation (BP) equations constitute a well-known distributed computational scheme. It is exact on tree-like graphical models and has also proven to be effective in many problems defined on graphs with loops (from inference to optimization, from signal processing to clustering). 
The BP-based scheme is fundamentally different from stochastic gradient descent (SGD), on which the current success of deep networks is based. In this paper, we present and adapt to mini-batch training on GPUs a family of BP-based message-passing algorithms with a reinforcement field that biases distributions towards locally entropic solutions.
These algorithms are capable of training multi-layer neural networks with discrete weights and activations with performance comparable to SGD-inspired heuristics (BinaryNet) and are naturally well-adapted to continual learning. Furthermore, using these algorithms to estimate the marginals of the weights allows us to make approximate Bayesian predictions that have higher accuracy than point-wise solutions.

Under review as a conference paper at ICLR 2022
DEEP LEARNING VIA MESSAGE PASSING ALGORITHM BASED ON BELIEF PROPAGATION
Anonymous authors Paper under double-blind review
ABSTRACT
Message- Message-passing algorithms based on the Belief Propagation (BP) equations con- stitute well-known distributed computational scheme. They yield exact marginals on tree-like graphical models and have also proven to be effective in many problems defined on loopy graphs, from inference to optimization, from signal processing to clustering. The BP-based schemes are fundamentally different from stochastic gradient descent (SGD), on which the current success of deep networks is based. In this paper, we present and adapt to mini-batch training on GPUs a family of BP-based message- message-passing algorithms with a reinforcement term that biases dis- tributions towards locally entropic solutions. These algorithms are capable of training multi-layer neural networks with performance comparable to SGD heuris- ties in diverse of experiments natural datasets including multi-class image classification and continual learning, while being capable of yielding improved performances on sparse networks. Furthermore, they allow make approximate Bayesian predictions that have higher accuracy than point-wise ones.
INTRODUCTION
Belief Propagation is a method for computing marginals and entropies in probabilistic inference problems (Bethe 1935 Peierls 1936 Gallager 1962 Pearl 1982). These include optimization problems as well once they are written as zero temperature limit of a Gibbs distribution that uses the cost function as energy. Learning is one particular case, which one wants to minimize cost which is data dependent loss function. These problems are generally intractable and message-passingg techniques have been particularly successful providing principled approximations through efficient distributed computations.
particularly compact representation of inference/oppimizztion problems that is used to build massage-passingg algorithms is provided by factor graphs. A factor graph is bipartite graph composed of variables nodes and factor nodes expressing the interactions among variables. Belief Propagation is exact for tree-like factor graphs (eddidia al. (003)), where the Gibbs distribution is naturally factorized, whereas it is approximate for graphs with loops. Still, loopy BP is routinely used with success in many real world applications ranging from error correcting codes, vision, clustering, just to mention a few. In all these problems, loops are indeed present in the factor graph and yet the variables are weakly correlated long range and BP gives good results. A field in which BP has a long history is the statistical physics of disordered systems where it is known as Cavity Method (Mézard et al.) 1987). It has been used study the typical properties of spin glass models which represent binary variables interacting through random interactions over a given graph. It is very well known that in spin glass models defined on complete graphs and in locally tree-like random graphs, which are both loopy, the weak correlation conditions between variables may hold and BP give asymptotic exact results (Mézadd & Montanari 2009). Here we will mostly focus on neural networks +11 binary weights and sign activation functions, for which the messages and the marginals can be described simply by the difference between the probabilities associated with the +1 and states, the so called magnetizations. The effectiveness of BP for deep learning has never been numerically tested in systematic way, however there is clear evidence that the weak correlation decay condition does not hold and thus BP convergence and approximation quality is unpredictable.
In this paper we explore the effectiveness of a variant of BP that has shown excellent convergence properties in hard optimization problems and in non-convex shallow networks. It goes under the

---

Under review as a conference paper at ICLR 2022
name of focusing BP (fBP) and is based on probability distribution, likelihood, that focuses on highly entropic wide minima, neglecting the contribution to marginals from narrow minima even when they the majority (and hence dominate the Gibbs distribution). This version of BP is thus expected to give good results only in models that have such wide entropic minima as part of their energy landscape. As discussed in (Baldassi et al. 20T6a), simple way to define fBP is to add "reinforcement" term to the BP equations: an iteration-eependett local field is introduced for each variable, with an intensity proportional to its marginal probability computed in the previous iteration step. This field is gradually increased until the entire system becomes fully biased on a configuration.
The first version of reinforced BP was introduced in (Braunstein & Zecchina 2006) as heuristic algorithm to solve the learning problem in shallow binary networks. [Bllaasii et al. (2016a) showed that this version of BP is a limiting case of fBP, i.e. BP equations written for a likelihood that uses the local entropy function instead of the error (energy) loss function. As discussed in depth in that study, one way to introduce a likelihood that focuses on highly entropic regions is to create y coupled replicas of the original system. IBP equations are obtained as BP equations for the replicated system. It turns out that the fBP equations are identical to the BP equations for the original system with the only addition of self-reinforcing term in the message passing scheme. The fBP algorithm can be used as solver by gradually increasing the effect of the reinforcement: one can control the size of the regions over which the fBP equations estimate the marginals by tuning the parameters that appear in the expression of the reinforcement, until the high entropy regions reduce to single configuration. Interestingly, by keeping the size of the high entropy region fixed, the fBP fixed point allows one to estimate the marginals and entropy relative to the region.
In this work, we present and adapt to GPU computation a family of IBP inspired message passing algorithms that are capable of training multi-layer laaei- neural networks with generalization performance and computational speed comparable to SGD. This is the first work that shows that learning by message passing in deep neural networks 1) is possible and 2) is viable alternative to SGD, Our version of fBP adds the reinforcement term at each mini-batch step in what we call the Posterior- as as-Prior (PasP) rule. Furthermore, using the message- puessage-assingg passing algorithm not as a solver but as an estimator of marginals allows us to make locally Bayesian predictions, averaging the predictions over the approximate posterior. The resulting generalization error is significantly better than those of the solver, showing that, although approximate, the marginals of the weights estimated by message- passing retain useful information. Consistently with the assumptions underlying fBP, we find that the solutions provided by the message passing algorithms belong to flat entropic regions of the loss landscape and have good performance in continual learning tasks and on sparse networks as well.
We also remark that our PasP update scheme is of independent interest and can be combined with different posterior approximation techniques.
The paper is structured as follows: in Sec. we give a brief review of some related works. In Sec. 3 we provide detailed description of the wesssge-passing equations and of the high level structure of the algorithms. In Sec. [ we compare the performance of the message passing algorithms versus SGD based approaches in different learning settings.
2 RELATED WORKS
The literature on message passing algorithms is extensive, we refer Mézard & Montanari (209)) and Zdeborová & Krzakala (2016) for a general overview. More related to our work, multilayer
message-passing algorithms have been developed in inference contexts (Manoel al. 2017 Fletcher et al. 2018), where they have been shown to produce exact marginals under certain statistical assumptions on (unleamed) weight matrices.
The properties of message-paat -aasiinggaaiinggggg for learning shallow neural networks have been extensively studied (see (allassi et al. (2020) and reference therein). |Barbier al. (2019) rigorously show that message passing algorithms in generalized linear models perform asymptotically exact inference under some statistical assumptions. Dictionary learning and matrix factorization are harder problems closely related to deep network learning problems, in particular to the modelling of single intermediate layer. They have been approached using message passing in Kabashima et al. (2016) and Parker et al. (2014), although the resulting predictions are found to be asymptotically inexact (Mailladd et al. 2021). The same problem is faced by the message passing algorithm recently proposed for a multi-layer matrix factorization scenario (Zou et al. 2021). Unfortunately, our framework well
2

---

Under review as a conference paper at ICLR 2022
doesn't 't yield asymptotic exact predictions. Nonetheless, it gives message passing heuristic that for the first time is able to train deep neural networks on natural datasets, therefore sets a reference for the algorithmic applications of this research line.
few papers advocate the success of SGD to the geometrical structure (smoothness and flatness) of the loss landscape in neural networks (Baldassi et al. 2015
Chaudhari et al. 2017 Garipov et al.)
2018 Li et al., 2018 Pittorino et al.) 2021] Feng & Tu 2021).
These considerations do not depend on the particular form of the SGD dynamics and should extend also other types of algorithms, although
SGD is by far the most popular choice among NNs practitioners due to its simplicity, flexibility, speed, and generalization performance.
While our work focuses on message passing schemes, some of the ideas presented here, such as the PasP rule, can be combined with algorithms for Bayesian neural networks' training (Hernández) Lobato & Adams, 2015; Wu et al. 2018). Recent work extends BP by combining it with graph neural networks (Kuck al. 2020; Satorras & Welling (02T). Finally, some work in computational neuroscience shows similarities to our approach (Rao 2007).
3 LEARNING BY MESSAGE PASSING
3.1 POSTERIOR-AS- PRIOR UPDATES
We consider multi-layer pereeptron with L hidden neuron layers, having weight and bias parameters W = (W", b') H We allow for stochastic activations Pd (*x*+112)) where z is the neuron's 's pre- activation vector for layer l, and p is assumed to be factorized over the neurons, no stochasticity is present, P just encodes an element-wise activation function. The probability of output y given an input æ is then given by
ff dz 1: II t=
Ply 2 W)
p 1 el W +b))
(I)
where for convenience we defined x x and g-++ y. In Bayesian framework, given a training
set D = {( Jn)h. and prior distribution over the weights qo (W) in some parametric family, the posterior distribution given by
P,WID,O) II P(y Rn, W) (WV).
Here denotes equality up to normalization factor. Using the posterior one can pute the Bayesian prediction for a new data-point æ through the average P(y xx, D,0) ddW P(yl x. W) P(W D) Unfortunately, the posterior is generically intractable due to the hard-to-compute normalization factor. On the other hand, we are mainly interested in training distribution that covers wide minima of the loss landscape that generalize well (Baldassi al.) 201 and in recovering pointwise estimators within these regions. The Bayesian modeling becomes an auxiliary tool to set the stage for the message passing algorithms seeking flat minima. We also need formalism that allows for mini-batch training speed-up the computation and deal with large datasets. Therefore, we devise an update scheme that we call Posterior-as-Prii
(PasP), where we evolve the parameters 0f of a distribution gor (W) computed as an approximate mini-batch posterior, in such a way that the outcome of the previous iteration becomes the prior in the following step. In the PasP scheme, H¹ retains the memory of past observations. We also add exponential factor p. that we typically set close to 1, tuning the forgetting rate and playing a role similar to the learning rate in SGD. Given mini-batch (X', yy) sampled from the training at time and scalar p > the PasP update reads
g (W)) ~ [P(W (P'''''X''00 x')0'
where denotes approximate equality and do not account for the normalization factor. A first approximation may be needed in the computation of the posterior, a second to project the approximate posterior onto the distribution manifold spanned by 0 Minnaa 2001). In practice, will consider factorized approximate posterior in an exponential family and priors qo in the same family, although Eq. generiially allow for more refined approximations.
3

---

Under review as a conference paper at ICLR 2022
Notice that setting p the Assumed Density Filtering algorithm (Minka 2001]. J. For large enough (including p = 1), the iterations of qøe will concentrate a pointwise estimator. This mechanism mimics the reinforce- ment heuristic commonly used to turn Belief Propagation into a solver for constrained satisfaction problems (Braunstein & Zecchina 2006) and related to flat-minima discovery (see focusing- BP in Baldassi et al. (2016))). ). A different prior updating mechanism which can be understood as empirical Bayes has been used in Baldassi et al. (2016b).
the batch-size to 1, and taking single pass over the dataset, we recover
3.2 INNER MESSAGE PASSING LOOP
While the PasP rule takes care of the reinforcement heuristic across mini-batches, compute the mini-batch posterior in Eq. 3 using message passing approaches derived from Belief Propagation. BP is an iterative scheme for computing marginals and entropies of statistical models Mézard & Montanari] (2009). It is most conveniently expressed on factor graphs, that is bipartite graphs where the two sets of nodes are called variable nodes and factor nodes. They respectively represent the variables involved in the statistical model and their interactions. Message from factor nodes to variable nodes and viceversa are exchanged along the edges of the factor graph for a certain number of BP iterations or until fixed point is reached.
The factor graph for P(W| X y', 0t) can be derived from Eq. 2 with the following additional specifications. For simplicity, we will ignore the bias term in each layer. We assume factorized qa (W), each factor parameterized by its first two moments. In what follows, we drop the PasP iteration index t. For each example (æn. Vo) in the mini-batch, we introduce the auxiliary variables o I, .,....... L, representing the layers' activations. For each example, each neuron the network contributes factor node to the factor graph. The scalar components of the weight matrices and the activation vectors become variable nodes. This construction is presented in Appendix A where also derive the message update rules the factor graph. The factor graph thus defined is extremely loopy and straightforward iteration of BP has convergence issues. Moreover, in presence of homogeneous prior over the weights, the neuron permutation symmetry in each hidden layer induces a strongly attractive symmetric fixed point that hinders learning. We work around these issues by breaking the symmetry at time 0 with an inhomogeneous prior. In our experiments a little initial heterogeneity is sufficient to obtain specialized neurons at each following time step. Additionally, we do not require message passing convergence the inner loop (see Algorithm [ but perform one or few iterations for each 0 update. We also include an inertia term commonly called damping factor in the message updates (see B.2 As we shall discuss, these simple rules suffice to train deep networks by message passing.
For the inner loop we adapt to deep neural networks four different message passing algorithms,, all of which are well known to the literature although derived in simpler settings: Belief Propagation (BP), BP-Inspired (BPI) message passing, mean-field (MF), and approximate message passing (AMP). The last three algorithms can be considered approximations of the first one. In the following paragraphs we will discuss their common traits, present the BP updates as an example, and refer to Appendix [A] for in-depth exposition. For all algorithms, message updates be divided in forward pass and backward pass, as also done in (Fletcher et al. 2018) in a multi-layer inference setting. The BP algorithm is compactly reported in Algorithm] 1
Meaning of messages. All the messages involved in the message passing can be understood in terms of cavity marginals or full marginals (as mentioned in the introduction BP is also known as Cavity Method, see (Mézard & Montanari 2009)). Of particular relevance are mf, and of denoting the mean and variance of the weights W The quantities af,, and A instead denote the mean and variance of the i-th neuron's activation in layer for a given input 2
Scalar free energies. All message passing schemes are conveniently expressed in terms of two functions that correspond the effective free energy (Zdeborová & Krzakala, 2016) of single
4

---

Under review as a conference paper at ICLR 2022
neuron and of single weight respectively:
x (B,,, W, log / dx dz e +Ba (x(2) 12
t=
(4)
(H,, log / dw e e - go(w)
(5)
Notice that for common deterministic activations such as ReLU and sign, the function has analytic and smooth expressions (see Appendix A.8). The same holds for the function &i when go(w) is Gaussian (continuous weights) or a mixture of atoms (discrete weights). At the last layer we impose pL+1 (y|z) Li(y sz))(z)) in binary classification tasks and (yl+
I[ arg max(=)) in multi-class classification (see Appendix A.9). While in our experiments we use hard constraints for the final output, therefore solving a constraint satisfaction problem, would be interesting also
consider soft constraints and introduce temperature, but this is beyond the scope of our work.
Start and end of message passing, At the beginning of new PasP iteration t, we reset the messages (see Appendix [ and run message passing for Tmax iterations. We then compute the new prior's parameters 0++1 from the posterior given by the message passing.
BP Forward pass. After initialization of the messages time t = 0, for each following time we propagate set of message from the first to the last layer and then another set from the last to the first. For an intermediate layer the forward pass reads
Onp
B Abr-1 1-1,7 V(-1,7) in
in
(6)
Szpp
(B(--1 Abr-1 .ii
t-1, v---1,7
(7)
in
fr mis-nn
OH --1 GhT-1 1
kion
(8)
E,T
(H (H GG
Gl.T-1 .l(a)
kki
E (mit )²
A + ohi kn
li
(ofr
+ A.T
(10)
Er Win+i
Σ
brr 2.r Em on
(11)
The equations for the first layer differ slightly and in an intuitive way from the ones above (see Appendix A.3)
BP Backward pass.
The backward pass updates a set of messages from the last to the first layer:
Den = Oupet11 BBttir Altlir
wwh Veni ver lit (g (ghn-s) )²
(12)
p&. = -optti Bitti 1421 wkn
(13)
AGr
Σ
(m )2 (et Iha ob
(14)
in
Bhr
B
miinn #ff
Σ
But f.t
(15)
GH
Σ
Phr - A.T PiT ) + Ain
(knn
(16)
H&r Miion
Σ
(17)
n'
As with the forward pass, we add the caveat that for the last layer the equations are slightly different from the ones above.
5

---

Under review as a conference paper at ICLR 2022
Computational complexity The message passing equations boil down element wise operations and tensor contractions that we easily implement using the GPU friendly julia library Tullio.jl (Abbott) et al. 202Ip. For a layer of input and output size N and considering batch-size of B. the time complexity of a forth-and-bace iteration D(N2B) for all message passing algorithms (BP, BPI, MF, and AMP), the same SGD. The prefactor varies and it is generally larger than SGD (see Appendix B.9). Also, time complexity for message passing is proportional to Tmax (which we typically set to 1). We provide our implementation the GitHub repo anonymous.
Algorithm 1: BP for deep neural networks
// Message passing used the PasP Eq. to approximate.
// the mini-batch posterior.
// Here we specifically refer to BP updates.
// BPI, MF, and AMP updates take the same form but using
// the rules in Appendix A.4, A.5 and A.7 respectively Initialize messages.
for T 1,... max do // Forward Pass
for = 0,... 0....., L.
compute ét, using
compute m f of using {
compute Vi w using 10
// Backward Pass
for 1 = L, ... do
compute g², r using 12
13
compute A', Bº using
compute G H using [6
4 NUMERICAL RESULTS
We implement our message passing algorithms on neural networks with continuous and binary weights and with binary activations. In experiments fix Tmax 1. We typically do not observe an increase performance taking more steps, except for some specific cases and particular for MF layers. We remark that for Tmax the BP and the BPI equations identical, so in most of the subsequent numerical results we will only investigate BP.
We compare algorithms with SGD-based algorithm adapted binary architectures (Hubara ett al. 2016) which we call BinaryNet along the paper (see Appendix B.6 details). Comparison of Bayesian predictions are with the gradient-based Expectation Backpropagation (EBP) algorithm (Soudry et al. 2014 also able to deal with discrete weights and activations. In all architectures we avoid the use bias terms and batch- normalization layers.
We find that message passing algorithms are able to train generic MLP architectures with varying num- bers and sizes of hidden layers. As for the datasets, are able to perform both binary classification and multi-class classification and CIFAR-10. Since these datasets consist of 10 classes, for the binary classification task we divide each dataset in two classes (even odd).
message-passing
standard computer vision datasets such as MNIST, Fashion-MNIST,,
We report that message passing algorithms are able to solve these optimization problems with generalization performance comparable to or better than SGD-based algorithms. Some of the message passing algorithms (BP and AMP in particular) need fewer epochs to achieve low error than the ones required by SGD-based algorithms, even if adaptive methods like Adam are considered. Timings of our GPU implementations of message passing algorithms are competitive with SGD (see Appendix B.9

---

Under review as a conference paper at ICLR 2022
4.1 EXPERIMENTS ACROSS ARCHITECTURES
We select a specific task, multi-class classification on Pashion-MNIST, we compare the message passing algorithms with BinaryNet for different choices of the architecture (i.e. we vary the number and the size the hidden layers). In Fig (Left) we present the learning curves for a MLP with 3 hidden layers with 501 units with binary weights and activations. Similar results hold in our experiments with 2 or 3 hidden layers of 101, 501 or 1001 units and with batch sizes from to from 1024. The parameters used in simulations reported in Appendix [B.3] Results networks with continuous weights can be found in Fig (Right).
4.2 SPARSE LAYERS
Since the BP algorithm has notoriously been successful on sparse graphs, we perform straight- forward implementation of pruning at initialization, i.c. we impose a random boolean mask on the weights that we keep fixed along the training. We call sparsity the fraction of zeroed weights. This kind non-adaptive pruning known to largely hinder learning (Frankle et al. 2021: Sung et al. report results sparse binary networks which train
2021). In the right panel of Fig. a MLP with 2 hidden layers of 101 units on the MNIST dataset. For reference, results on pruning quantized/binary networks
be found in Refs. (Han et al., 2016) Ardakani al. 2017 Tung & Mori 2018; Diffenderfer & Kailkhura, (02T). Experimenting with sparsity up to 90%, We observe that BP and MF perform better than BinaryNet. AMP struggles behind BinaryNet instead.
25
100
BP train
MF
BP test
MF test
95
20
AMP train
BinaryNet train
90
AMP test
BinaryNet test
test accuracy (96)
error (%)
85
BP
75
AMP test
70
Bayes AMP test
MF test
65
Bayes
BinaryMint
0
20
60
80
60
epochs
sparsity (%))
Figure 1: (Left) Training curves of message passing algorithms compared with BinaryNet on the Fashion-MNIST dataset (multi-class classification) with a binary MI.P with hidden layers of 501 units. (Right) Final test accuracy when varying the layer's sparsity in a binary MLP with 2 hidden layers of 101 units on MNIST dataset (multi-class). In both panels the batch-size is 128 and curves are averaged over 5 realizations of the initial conditions (and sparsity pattern in the right panel).
4.3 EXPERIMENTS ACROSS DATASETS
We now fix the architecture, a MLP with 2 hidden layers of 501 neurons each with binary weights and activations. We vary the dataset, i.e. we test the BP-based algorithms on standard computer vision benchmark datasets such MNIST, MaSSI and CIFAR-I0 10, in both the multi-class and binary classification tasks. In Tab. [ we report the final test errors obtained by the message passing algorithms compared to the BinaryNet baseline. See Appendix B.4 for the corresponding training errors and the parameters used in the simulations. We mention that while the test performance is mostly comparable, the train error tends to be lower for the message passing algorithms.
7

---

Under review as a conference paper at ICLR 2022
Dataset
BinaryNet
BP
AMP
MF
MNIST (2 classes)
1.3 13 0.1
0.2
1.400.1
1.2
Fashion- (2 classes)
2.1
2.3
2.1
2.1
CIFAR-10 (2 classes)
30.0 0.3
0.1
3.3
31.1
MNIST
3.2
2.1
2.6
2.3 331
Pashion-MNIST
12.0 +
11.8
0.3
11.9 0.2
12.1 #.2
CIFAR-10
59.0 0.7
58.7
0.3
58.5 0.2
60.4
Table 1: Test error (%) Reshion-MNIST of various algorithms MLP with 2 hidden layers of 501 units, binary weights and activations. All algorithms are trained with batch-size 128 and for 100 epochs. Mean and standard deviations calculated over 5 random initializations.
4.4 LOCALLY BAYESIAN ERROR
The message passing framework used as an estimator of the mini-batch posterior marginals allows us to perform approximate Bayesian prediction, i.e. averaging the pointwise predictions over the approximate posterior. We observe better generalization error from Bayesian predictions compared to point-wise ones, showing that the marginals retain useful information. However, we roughly estimate the marginals with the PasP mini-batch procedure (the exact ones should be computed with full-batch procedure, but this converges with difficulty in our tests). Since BP-based algorithms tend to focus on dense states (as also confirmed by the local energy measure performed in Appendix [B.3). be considered
the Bayesian eтror compute results for binary classification on the MNIST dataset in Fig. 2 and we observe the same performance increase different datasets and architectures. We obtain the Bayesian prediction from the output marginal given by a single forward pass of the message passing. To obtain good Bayesian estimates is important that the posterior distribution does not concentrate too much, otherwise the Bayesian prediction will converge to the prediction of single configuration.
local approximation of the full one. We report
In Fig 2 we also perform comparison of BP (point-wise and Bayesian) with SGD and another algorithm able to perform Bayesian predictions, Expectation Backpropagation (Soudry et al. 2014a) see Appendix|B. B.7 for implementation details.
Binary Weights
Continuous Weights
tart eroon (N2 32
Bayes BP BP
SGD
BP
EBP
Bayes BP
BinaryNet
bayes
bayes EBP
test error (96)
test error (96)
20
40
60
80 100
20
40
60
80
100
epochs
epochs
Figure 2: (Left) Test error curves for Bayesian and point-wise predictions for MLP with 2 hidden layers of 101 units the 2-classes MNIST dataset. We report the results for (Left) binary and (Right) continuous weights. In both cases, we compare SGD, BP (point-wise and Bayesian) and EBP wpsint-wise and Bayesian). See Appendix B.3 for details.
4.5 CONTINUAL LEARNING
Given the high local entropy (i.e. the flatness) the solutions found by the BP-based algorithms (see Appendix B.5), perform additional tests in classic setting, continual learning, where the
8

---

Under review as a conference paper at ICLR 2022
be an advantage. When a deep network trained sequentially on different tasks, it tends to forget exponentially fast previously seen tasks while learning new ones (McCloskey & Cohen 1989 Robins [995] Fusi et al.) 2005). Recent work (Feng & Tuu 2 has shown that searching for flat region in the loss landscape indeed help prevent catastrophic forgetting. Several heuristics have been proposed to mitigate the problem (Kirkpatrick et al. 2017; Aljundi et al. 2018 Zenke et al. 2017 Laborieux et al. 2021 but all require specialized adjustments the loss or the dynamics..
possibilitty of locally rearranging the solutions while keeping low training
Here we show instead that our message passing schemes are naturally prone to learn multiple tasks sequentially, mitigating the characteristic memory issues of the gradient- baased schemes without the need for explicit modifications. As a prototypical experiment, we sequentially trained multi-layer neural network on 6 different versions of the MNIST dataset, where the pixels of the images have been randomly permuted (Goodfellow et al., 2013), giving a fixed budget of 40 epochs on each task. We present the results for two hidden layer neural network with 2001 units on each layer (see Appendix B.3 for details). As can be seen in Fig. 3 at the end of the training the BP algorithm is able to reach good generalization performances on all the tasks. We compared the BP performance with BinaryNet, which already performs better than SGD with continuous weights (see the discussion in Labooorie et al. (2021)). While our BP implementation is not competitive with ad-hoe techniques specifically designed for this problem, it beats non-specialized heuristics. Moreover, we believe that specialized approaches like the one of Laborieux et al. (2021) can be adapted to message passing as well.
100
lost accuracy (56
1051 accurany
60
BP
Ir00
BanyrrNet
BayyNee 1,0
BinaryNet
BinaryNet 1-100.
lask
epochs
Figure 3: Performance of BP and BinaryNet on the permuted MNIST task (see text) for two hidden layer network with 2001 units on each layer and binary weights and activations. The model is trained sequentially on 6 different versions of the MNIST dataset (the tasks), where the pixels have been permuted. (Left) Test accuracy on each task after the network has been trained on all the tasks. (Right) Test accuracy the first task function of the number of epochs. Points averages over 5 independent runs, shaded areas are errors on the mean.
5 DISCUSSION AND CONCLUSIONS
While successful in many fields, message passing algorithms, have notoriously struggled to scale to deep neural networks training problems. Here we have developed a class of fBPedased message passing algorithms and used them within an update scheme, Posterior-as- sesiiior-s--PPP arior (PasP), that makes it possible to train deep and wide multilayer perceptrons by message passing.
We performed experiments binary activations and either binary continuous weights. Future work should try to include different activations, biases, noamaaliomlii,,innn, and convolutional layers as well. Another interesting direction is the algorithmic computation of the (local) entropy of the model from the messages.
Further theoretical work is needed for more complete understanding of the robustness of our methods. Recent developments in message passing algorithms (Rangan et al. 2019) and related theoretical analysis (Goldt al.) 2020) could provide fruitful inspirations. While our algorithms can be used for approximate Bayesian inference, exact posterior calculation is still out of reach for message passing approaches and much technical work is needed in that direction.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Michael Abbott, Dilum Aluthge, N3N5, Simeon Schaub, Carlo Lucibello, Chris Elrod, and Johnny Chen. Tullio.jl julia package, 2021, htk.htttss////tthii
Rahaf Aljundi, Francesca Babiloni, Mohamed Elhoseiny, Marcus Rohrbach, and Tinne Tuytelaars. Memory aware synapses: Learning what (not) to forget. In Proceedings of the European Conference on Computer Vision (ECCV), pp. 139-154, 2018.
Arash Ardakani, Carlo Condo, and Warren J. Gross. Sparsely-connecteo neural networks: Towards ef- ficient VLSI implementation of deep neural networks. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017. URL https: http::::///peeeeeeeeeee wwwp://tttttttttotoeooeoomootmat www.ieeyyyeeeee
Carlo Baldassi, Alfredo Braunstein, Nicolas Brunel, and Riccardo Zecchina. Efficient supervised learning in networks with binary synapses. Proceedings of the National Academy of Sciences, (04926):1107-111 1084, 2007. ISSN 0027-8424. doi: 20.1073//nas.070032441444 URL https:
/ 7/www. pnas.
Carlo Baldassi, Alessandro Ingrosso, Carlo Lucibello, Luca Saglietti, and Riccardo Zecchina. Subdominant dense clusters allow for simple learning and high computational performance in neural networks with discrete synapses.
Phys. Rev. Lett. 115:128101, Sep 2015. URL htttp:://inn:: wpw.nkapps.... wwtpppp...../........... 1103/
doi: 10.1103/Physeeveett. 115. 115.128101.
PbysRevLett. 128101
Carlo Baldassi, Christian Borgs, Jennifer T. Chayes, Alessandro Ingrosso, Carlo Lucibello, Luca Saglietti, and Riccardo Zecchina. Unreasonable effectiveness of learning neural networks: From accessible states and robust ensembles to basic algorithmic schemes. Proceedings of the National Academy of Sciences, 113(48):E7655-E7766 160810311 13.. URL htt.http::////. wwwp://wwwwwoo pnas org/
2016a. ISSN 0027-8424. doi: 10.1073/pnas.
Carlo Baldassi, Federica Gerace, Carlo Lucibello, Luca Saglietti, and Riccardo Zecchina. Learning may need only few bits of synaptic precision. Phys. Rev. E, 93:052313, May 2016b. doi: 10. 1103/PhysRev.99.00222 93. 052313
htth:tts::/ linkiiini..///////// aps org/ dei 1tt.:/1...110/PPyye
Carlo Baldassi, Fabrizio Pittorino, and Riccardo Zecchina. Shaping the learning landscape in neural networks around wide flat minima. Proceedings of the National Academy of Sciences, 1 117(1): 161-170, 2020. ISSN 0027-8424. doi: 10. http333/aaa.190666111111 URL https: /www. pnas htt:/content/117////0
Jean Barbier, Florent Krzakala, Nicolas Macris, Léo Miolane, and Lenka Zdeborová. Optimal errors and phase transitions in high-dimensional generalized linear models. Proceedings of the National Academy of Sciences, 116(1)):451--546 2019. ISSN 0027-8424. doi: 10.10733pnas..8000 1802705116
URL https: wwww pras. wwg.tonteettt.e.eooooooooooooeoe conteottettteee 116 1111/1/11/121111111
Hans Bethe. Statistical theory of superlattices. Proc. Soc. A, 150:552, 1935.
Alfredo Braunstein and Riccardo Zecchina. Learning by message passing in networks of discrete synapses. Phys. Rev. Lett. 96:030201, Jan 2006. doi: 10. 10.1103/Physeeeeettt.. wt..e......0000... URL
https: aps http:////.....11o/..yteeeeee.... 96. 030201
Pratik Chaudhari, Anna Choromanska, Stefano Soatto, Yann LeCun, Carlo Baldassi, Christian Borgs, Jennifer T. Chayes, Levent Sagun, and Riccardo Zecchina. Entropy-sgd: Biasing gradient descent into wide valleys. In 5th International Conference Learning Representations, ICLR 2017, Toulon, France, April 24-26. 2017, Conference Track Proceedings. OpenReview.net, 2017. URL net htwp://wwwweeeeeeefooooreeeeeeee forum?id=BlYfffeee
https:://penrevveee
James Diffenderfer and Bhavya Kailkhura. Multi-prize lottery ticket hypothesis: Finding accurate binary neural networks by pruning randomly weighted network. In International Confer- ence on Learning Representations, 2021. URL htttp:://pperevee net/ wwt.:/rrtfff.i....... forum?idd
mat.0b9iv
10

---

Under review as a conference paper at ICLR 2022
Yu Feng and Yuhai Tu. The inverse variance-flatness relation in stochastic gradient descent is critical for finding flat minima. Proceedings of the National Academy of Sciences, 118(9), 2021.
Alyson K Fletcher, Sundeep Rangan, and Philip Schniter. Inference in deep networks in high dimensions. In 2018 IEEE International Symposium on Information Theory (ISIT), pp. 1884-1888.
IEEE, 2018.
Jonathan Frankle, Gintare Karolina Dziugaite, Daniel Roy, and Michael Carbin. Pruning neural
networks at initialization: Why are we missing the mark? In International Conference Learning Representations, 2021. URL (ttttts::: /ttpt//////p/eeeeee/eeee
wttp:/ooummiid-i--ieeee VyQc- MLK
Stefano Fusi, Patrick Drew, and Larry F Abbott. Cascade models of synaptically stored memories. Neuron, 45(4):599-611, 2005.
Marylou Gabrié. Mean-field inference methods for neural networks, Journal of Physics A: Mathe- matical and Theoretical, 53(22):223002, 2020.
Robert Gallager. Low-density parity-check codes. IRE Transactions on information theory, 8(1): 21-28, 1962.
Timur Garipov, Pavel Izmailov, Dmitrii Podoprikhin, Dmitry P Vetrov, and Andrew G Willson. Loss surfaces, mode connectivity, and fast ensembling of dnns. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (eds.). Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018. httLLhtttts::/proeeeee
neur ps
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Yee Whye Teh and Mike Titterington (eds.), Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, volume 9 of Proceedings of Machine Learning Research, pp. 249-256, Chia Laguna Resort, Sardinia, Italy, 13-15 May 2010. mlr
PMLR. URLpttps://prrceddi.. wtt.://aiin...........ess///s///
html
Sebastian Goldt, Marc Mézard, Florent Krzakala, and Lenka Zdeborová. Modeling the influence of data structure learning in neural networks: The hidden manifold model. Physical Review X, 10 (4):041044, 2020.
Ian J Goodfellow, Mehdi Mirza, Da Xiao, Aaron Courville, and Yoshua Bengio. An empirical investi- gation of catastrophic forgetting in gradient- based neural networks. arXiv preprint arXiv: 1312.6211, 2013.
Song Han, Huizi Mao, and William J. Dally. Deep compression: Compressing deep neural network with pruning, trained quantization and huffman coding. In Yoshua Bengio and Yann LeCun (eds.), 4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings, 2016. URL http::ttt//rtttt org. 1150 00149
José Miguel Hernández-Lohann and Ryan P. Adams. Probabilistic backpropagation for scalable learning of bayesian neural networks. In Proceedings of the 32nd International Conference on International Conference on Machine Learning- Volume 37, ICML'15. pp. 1861-1869. JMLR.org. 2015.
Itay Hubara, Matthieu Courbariaux, Daniel Soudry, Ran El- Yaniv, and Yoshua Bengio. Bi- narized neural networks. In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Gar- nett (eds.), Advances in Neural Information Processing Systems, volume 29, Curran Asso- ciates, Inc., 2016. URL https: http::::///pcoceeiiggeooo/ www.nnnuui.... cc /ttpp//c..ccpppe///////e11 Paper. pdf
Yiding Jiang, Behnam Neyshabur, Hossein Mobahi, Dilip Krishnan, and Samy Bengio. Fantas- tic generalization measures and where to find them. International Conference on Learning Representations, 2020. URL httptttst////pmmt
www./e////to seee//oorumidd-S_gee JBE
Yoshiyuki Kabashima, Florent Krzakala, Mare Mézard, Ayaka Sakata, and Lenka Zdeborová. Phase transitions and sample complexity in bayes-optimal matrix factorization. IEEE Transactions on Information Theory, 62(7):4228 4265, 2016. doi: 00.1109/TT.22011255561
11

---

Under review as a conference paper at ICLR 2022
James Kirkpatrick, Razvan Pascanu, Neil Rabinowitz, Joel Veness, Guillaume Desjardins, Andrei A Rusu, Kieran Milan, John Quan, Tiago Ramalho, Agnieszka Grabska- Grabska-Barwinsker Barwinska, et al. Overcoming catastrophic forgetting in neural networks. Proceedings of the national academy of sciences, 114 (13):3521-3522) 2017.
Jonathan Kuck, Shuvam Chakraborty, Hao Tang, Rachel Luo, Jiaming Song, Ashish Sabharwal, and Stefano Ermon. Belief propagation neural networks. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 667-678. Curran Associates, Inc., 2020. URL
wtw.:/ewwiiinnn...ee.e.... nwuries cc/ pdf.
Axel Laborieux, Maxence Eroult, Tifenn Hirtzlin, and Damien Querlioz. Synaptic metaplas- ticity in binarized neural networks. Nature Communications, 12(1):2549, May 2021. ISSN 2041-1723. doi: 10. 10.1033/44147--02-22222 941467-021-22768-1
URL
1038/
Hao Li, Zheng Xu, Gavin Taylor, Christoph Studer, and Tom Goldstein. Visualizing the loss land- scape of neural nets. In S. Bengio. H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 31. Curran As- sociates, Inc., 2018. URL /ptp/tttpp///rrreeediene neurips cccpppper/201 8/100///fle////
b41b3bb3e 68118866336655556666777777733333
Antoine Maillard, Florent Krzakala, Mare Mézard, and Lenka Zdeborová. Perturbative construction of mean-field equations in extensive-rank matrix factorization and denoising. arXiv preprint arXiv:2/ 10.00:210000875. 2021.
Andre Manoel, Florent Krzakala, Mare Mézard, and Lenka Zdeborová. Multi-layer generalized linear estimation. In 2017 7 IEEE International Symposium Information Theory (ISIT), pp. 2098 2002, 2017. doi: 10. 109/SSTT..1.......... 7.800689..
Michael McCloskey and Neal Cohen. Catastrophic interference in connectionist networks: The sequential learning problem. In Psychology of learning and motivation, volume 24, pp. 109-165. Elsevier, 1989.
Mare Mézard. Mean-field message- message-passing passing equations in the hopfield model and its generalizations. Physical Review E. 95(2):022117, 2017.
Marc Mézard, Giorgio Parisi, and Miguel Angel Virasoro. Spin glass theory and beyond: An Introduction to the Replica Method and Its Applications, volume 9. World Scientific Publishing Company, 1987.
Thomas P. Minka. Expectation propagation for approximate bayesian inference. In Proceedings of the Seventeenth Conference on Uncertainty in Artificial Intelligence, UAI'01, pp. 362-369, San Francisco, CA, USA, 2001. Morgan Kaufmann Publishers Inc ISBN 1558608001.
Marc Mézard and Andrea Montanari. Information, Physics, and Computation. Oxford University Press, Inc., USA, 2009. ISBN 019857083X.
Jason T Parker, Philip Schniter, and Volkan Cevher. Bilinear generalized approximate message passing-part i: Derivation. IEEE Transactions Signal Processing, 62(22):5839-585) 2014.
Judea Pearl. Reverend Bayes inference engines: A distributed hierarchical approach. Cognitive Systems Laboratory, School of Engineering and Applied Science 1982.
R. Peierls. On ising's model of ferromagnetism. Mathematical Proceedings of the Cambridge Philosophical Society, 32(3):477 481, 1936. doi:
Fabrizio Pittorino, Carlo Lucibello, Christoph Feinauer, Gabriele Perugini, Carlo Baldassi, Elizaveta Demyanenko, and Riccardo Zecchina. Entropic gradient descent algorithms and wide flat minima. In International Conference Learning Representations, 2021. URL ht //tp://ppnnaoeee/ revies net. net/fooze forum? 1d=x wwwpamnnddxxxxxxxxxxxxxxoo Dmm
Sundeep Rangan, Philip Schniter, and Alyson K Fletcher. Vector approximate message passing. JEEE Transactions Information Theory, 65 (5(10):6664-666) 2019.
12

---

Under review as a conference paper at ICLR 2022
Rajesh N. Rao. Neural models of Bayesian belief propagation. pp. 239-267. Bayesian brain: Prob- abilistic approaches to neural coding. MIT Press, Cambridge, MA, US, 2007. ISBN 026204238X (Hardcover); 978-0- 378-0-262-04238-3 (Hardcover).
Anthony Robins. Catastrophic forgetting, rehearsal and pseudorchearsal. Connection Science, 7(2): 123-146, 1995.
Victor Garcia Satorras and Max Welling. Neural enhanced belief propagation on factor graphs. In International Conference on Artificial Intelligence and Statisties, pp.
PMLR, 2021.
Daniel Soudry, Itay Hubara, and Ron Meir. Expectation backpropagation: Parameter- free training of multilayer neural networks with continuous discrete weights. In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K. Q. Weinberger (eds.), Advances in Neural Information Processing Systems, volume 27. Curran Associates, Inc., 2014a. URL httpp::/prooceding.. neurips cc cc/papprr/201/ffiee pdf
07
Daniel Soudry, Itay Hubara, and Ron Meir. Expectation backpropagation: Parameter-free training of multilayer neural networks with continuous or discrete weights. In NIPS, volume 1, pp- 2, 2014b.
George Stamateseu, Federica Gerace, Carlo Lucibello, Ian Fuss, and Langford B. White. Critical initialisation continuous approximations of binary neural networks. 2020. URL https
htt.:/iwwwwwweeee.... //openreview wwt. /trt/forumr d=rryloo==DD
Yi-Lin Sung, Varun Nair, and Colin Raffel. Training neural networks with fixed sparse masks, 2021.
Frederick Tung and Greg Mori. Clip-q: Deep network compression learning by in in-parallel pruning- quantization. In 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 7873-7882, 2018.
doi: 10. 10//CV 201000021..
Anqi Wu, Sebastian Nowozin, Edward Meeds, Richard Turner, Jose Miguel Hernandez-Lobatee and Alexander L Gaunt. Deterministic variational inference for robust bayesian neural networks. arXiv preprint 1810.03900 2018.
Jonathan S. Yedidia, William T. Freeman, and Yair Weiss. Understanding Belief Propagation and Its Generalizations, pp. 239-269. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2003.
ISBN 177.68117.
Lenka Zéeborová and Florent Krzakala. Statistical physics of inference: Thresholds and algorithms. Advances in Physics, 65(5)-453-552, 2016.
Friedemann Zenke, Ben Poole, and Surya Ganguli. Continual learning through synaptic intelligence.
In International Conference on Machine Learning, pp. 3987-3995 PMLR, 2017.
Qiuyun Zou, Haochuan Zhang, and Hongwen Yang. Multi-layer bilinear generalized approximate message passing. IEEE Transactions on Signal Processing, 19:4529-4544 2021. doi: 10. 109/ 3100202
13

---

Under review as a conference paper at ICLR 2022
Appendices
CONTENTS
BP-based message passing algorithms
14
Preliminary considerations
14
A.2
Derivation of the BP equations
15
A.3
BP equations
18
A.4
BPI equations
19
A.5
MF equations
20
A.6
Derivation of the AMP equations
21
A.7
AMP equations
22
A.8
Activation Functions
23
A.9
The ArgMax layer
23
Experimental details
25
B.1
of the BP-based scheme
25
B
Damping scheme for the message passing
25
3
Architectures
26
B.4
Varying the dataset
27
B.5
Local energy
27
B.6
SGD implementation (BinaryNet
28
B.
EBP implementation
28
B.8
Unit polarization and overlaps
29
B.9
Computational performance: varying batch-size
30
A
BP-BASED MESSAGE PASSING ALGORITHMS
A.1
PRELIMINARY CONSIDERATIONS
Given mini-batch = {(xn: bn the factor graph defined by Eqs. as:
1
18 is explicitly written
P(W, NWWxx'i 1:1. 1B,
()
p&+1
E+1 km
Σ
II qo (W R.i.e
(18)
t=
R.m.
where x = Fn, x I++1 Un- The derivation of the BP equations for this model straightforward albeit lengthy and involved. It is obtained following the steps presented in multiple papers, books, and reviews, see for instance (Mézard & Montanari] 2009) Zdeborová & Krzakala 2016 Mézard 2017), although it has not been attempted before in deep neural networks. It should be noted that (common) approximation that we take here with respect to the standard BP scheme, is that messages assumed to be Gaussian distributed and therefore parameterized by their mean and variance. This goes by the name of relaxed belied propagation (rBP), just referred to as BP throughout the paper.
We derive the BP equations in A.2 and present them all together in A.3 From BP, we derive other message passing algorithms useful for the deep network training setting, all of which are well known to the literature: IP-Inspired (BPI) message passing A.4 mean-field (MF) A.5 and approximate
14

---

Under review as a conference paper at ICLR 2022
The AMP derivation is the more involved and given in A.6 In all these cases, message updates can divided a forward pass and a backward pass, as also done in Fletcher et al. (2018) in multi-layer inference setting. The BP algorithm is compactly reported in Algorithm
message passing (AMP) A.7
In notation, denotes the layer index, the BP iteration index, k an output neuron index, i an input neuron index, and n a sample index.
We report below, for convenience, some of the considerations also present in the main text.
Meaning of messages. All the messages involved in the message passing equations can be under- stood in terms of cavity marginals or full marginals (as mentioned in the introduction BP is also known as the Cavity Method, see Mézard & Montanari (2009). Of particular relevance are the quantities m and of. denoting the mean and variance the weights W The quantities a and A instead denote mean and variance of the i-th neuron's 's activation in layer in correspondence of an input In--
Scalar free energies. All message passing schemes can be expressed using the following scalar functions, corresponding single neuron and single weight effective free-energies respectively;
(B,A,, V) log / dx dz e A pe (x (2)2) (--et
(19)
(H 0. = log / dw e 2 (o(w).
(20)
These free energies will naturally arise in the derivation of the BP equations Appendix A.2 For the last layer, the neuron function has to be slightly modified:
op b (y.w, V) log / d2 pL+1 (y12)
( 20
(21)
Notice that for common deterministic activations such ReLU and sign, the function has analytic and smooth expressions that we give in Appendix A.8 Same goes for tb when (w) is Gaussian (continuous weights)
mixture of atoms (discrete weights). At the last layer we impose pyl(() = [yy sign(=)) in binary classification tasks. For multi-class clas- sification instead, we have adapt the formalism vectorial pre-activations z and assume [)|+) = I[y arg max(z)) (see Appendix A.9). While in our experiments we use hard constraints for the final output, therefore solving a constraint satisfaction problem, would be inter- esting to also consider generic loss functions. That would require minimal changes to our formalism, but this is beyond the scope of our work.
Binary weights. In our experiments use #1 weights in each layer. Therefore each marginal can be parameterized by a single number and our prior/posterior takes the form
go x Cha...
(22)
The effective free energy function Eq. 20 becomes
(HH G, 0%) = log cosh + 0%,)
(23)
and the messages G can be dropped from the message passing.
Start and end of message passing. At the beginning of new PasP iteration we reset the messages to zero and run message passing for Tmax iterations. We then compute the new prior 10++1 (W) from the posterior given by the message passing iterations.
A.2 DERIVATION OF THE BP EQUATIONS
In order derive the BP equations, start with the following portion of the factor graph reported in Eq. i8 the main text, describing the contribution of a single data example in the inner loop of the PasP updates:
15

---

Under review as a conference paper at ICLR 2022
IIII
pé+1
f+1 Jen
Σ
W hiaiin
where a. Unn 2 L++
yn-
(24)
t=
where we recall that the quantity spondence of the input example
o corresponds to the activation of neuron & in layer in corre-
Let us start by analyzing the single factor:
pf+1
f+1 knn
Σ Whe
(25)
We refer to messages that travel from input output in the factor graph as upgoing or upwards messages, while the ones that travel from output to input as downgoing or backwards messages.
Factor-to-variable-- W messages
The
W messages read:
sf+1 k (Wi+) x
de (Wie) 8/
II
II du (o dus (aftt) pett
Σ
W kit Ii
km
(26)
where vi denotes the messages travelling downwards (from output to input) in the factor graph.
denote the means and variances of the incoming messages respectively with m f and
ki-nn A An
m
duf d (Wh)) W
(27)
Okita
dufs (W(t)) (Whr mpr-m))
(28)
s/ fn / dufn-Nh (o xi
(29)
/ duiinou(a(nn ( 2in-2))
A in
(30)
We now use the central limit theorem to observe that with respect to the incoming messages distri- butions assuming independence of these messages in the large input limit the preactivation is Gaussian random variable:
Σ (t
Whyre ~ NN(uhnnsi Vi Vin-n)
(31)
where:
wf
= E,
We
kar 2
Σ
mfy -m 26
(32)
kn-
Varv
Σ
Σ
(orv- Dinss (mbr-m)² Sinn + obr (2)001)
(33)
Therefore rewrite the outgoing messages
16

---

Under review as a conference paper at ICLR 2022
I dz de (1
(-- (s-Men---Wie wheckn Ween-
t (Wi) &
pe+1
Tnn
e+1
(34)
We now assume = be small compared to the other terms. With second order Taylor expansion we obtain:
el (Whi x f dz du e
(a sen vn
pe+1
s+1
kn
Whon be ae Din Wes + (z wkn wkn- 2 Vin A + (2 ) (W
x 1+
Van++
2V 2V
(35)
Introducing now the function:
x (B,A, = log / dr e- 3At'+Br pe (x(2)
(w=x)
2V
(36)
and defining:
Ikn-ni Oup (Bet1, A whn- Ve Vin-si)
(37)
Knn=i - A wl
, whn-ii Ven-s)
(38)
the expansion for the oeg-mes reads:
log (W se const + s pin-is Whi
2 (A + (imm Thn-s Ain-a (ih (W
1
(39)
Factor-to-vvaraalle- messages The derivation of these messages analogous to the factor-to- variable-W ones in Eq. 26 just reported. The final result for the log-message is:
log (1 rconst + mis+on Sin (ofa- + (mhk-n) )²) pin-si - ofim (Ihm )²) (1ftn)
1
(40)
2
Variable- W -ttt-ouuppu--fcctor messages
The message from variable W to the output factor kn
reads:
1 (W x Pbi, We log
= Ph (Wh)) Me wh, G. (Wr))²
(41)
where we have defined:
Higm = Σ ai t Sknn
(42)
n n'
Gha-- Σ (Anrr-* (1) D Pen-ss
De (ohnr-x))))
(43)
W'yfn
Introducing now the effective free energy:
17

---

Under review as a conference paper at ICLR 2022
G,, log dw Pá e e g
(44)
we can express the first two cumulants of the message ki-sn (WEr) as:
Wi-+ = 0n1 11 ki G Oki) of hi-nn 0H 1b ki Gki-nn Oks)
(45)
(46)
Variabllex-to-innp--ffccoo messages
We write the downgoing message
V (L(2()) o e lor (a()
R -i
(47)
where:
B = Σ mli-in in Pen
(48)
4/ = =E ((ohimm + (m)i-m) Tkm-i oi (ohttts)))
(49)
Variaale-sstoooutpuuuacccoo messages By defining the following cavity quantities:
Bln++ Blnnok mkiin Ikn-ps
(50)
A Ain (ookimm + (mpimm) D Thn-ii Rrco (shm-r)))
(51)
and the following non-cavity ones:
wh. = Σ mii 2/nooo
(52)
Ven Σ (oii-en Ain + (mfrmm)² Din-e + ohson (ifn-s)))
(53)
express the first 2 cumulants of the upgoing messages as:
f/n-+ = (B Aln-kk f-1 V-f-) A A = 03
(54)
= (B A S l-1 v--1)
(55)
Wrapping it up Additional but straightforward considerations are required for the final input and output layers (E 0 and & = respectively), since they do not receive messages from below and above respectively. In the end, thanks to independence assumptions and the central limit theorem that we used throughout the derivations, we arrive to closed set of equations involving the means and the variances (or otherwise the corresponding natural parameters) of the messages. Within the same approximation assumption, we also replace the cavity quantities corresponding to variances with the non-cavity counterparts. Dividing the update equations in forward and backward pass, and ordering them using time indexes in such a way that we have an efficient flow of information, we obtain the set of BP equations presented in the main text Eqs. 6 T7) and in the Appendix Eqs. 660 7I.
A.3 BP EQUATIONS
We report here the end result of the derivation in last section, the complete set of BP equations also presented in the main text as Eqs. 17).
18

---

Under review as a conference paper at ICLR 2022
Initialization At 0:
B
in- 0
(56)
A 0
(57)
in
H kii+n 0
8.
(58)
GLO
(59)
Forward Pass
At cach 7 I,..., Tmaxs for l ....., L:
ser
in 0By (B (m
A
w in
1-1,
(60)
A LT
(B
(B
1-r-- Win f-1, v
(61)
in
OH
1---1 G (%)
ki-mn
(62)
Thi
81 (H 11 Ghr-1 0%)
(63)
VL. kn
=
Σ(
(m
2
lrt +
ki
---
(..) 2 vnn
okk
----1
A
in
(64)
Pir mis on Fin
(65)
In these equations for simplicity we abused the notation, in fact for the first layer of=0,r is fixed and given by the input 2n while A 2=0,r 0 instead.
Backward Pass For 1,..., Tmaz, for L I.....0:
8, 9hn O (Bft ARtliT fit
kn km
(66)
ph.
02 ( A 1t Wkn VliTT
(67)
kn
A Am
Σ (m
ert p.. 2, (
+ oki
kn
ohi
9kn
(68)
k
BL. in
Σ
m mi--on Fknns
(69)
k'yh
Ghi =Σ
P:r A.n
The
A
[kkn
P.r
(70)
H ki-in
Σ
Rot E.T on bk Ikn'
(71)
n' An
In these equations well we abused the notation: calling L the number of hidden neuron layers, when &l L one should use ( w,
w, V) from Eq. 21 instead of pl++111) (B, V).
A.4 BPI EQUATIONS
The Inspirdd algorithm (BPI) is obtained as approximation of BP replacing some cavity quantities with their non-cavity counterparts. What we obtain is generalization the single layer algorithm of Baldassi et al. (2007).
19

---

Under review as a conference paper at ICLR 2022
Forward pass.
= Onp' (B(T-1 : in s
165-1 1-1,T vl-1,7
Fin
(72)
A = 0B8 (B/N A/n
1 win
2-1, 1
(73)
in
mii
trr
On ( (H
(74)
o ki
trr
(75)
VL.
Σ (mf))
2
A an
(1 + o A
(76)
kn
Wkn
Σ
mis
(77)
Backward pass.
Jen-si
Owsttl B Altli wht met aaa v.l
(78)
pf.
-xp--1 (Betli, Attl w Vhni)
(79)
A
Σ (1mfrr + rer 0ki
L,t E,7
(kkn
(80)
Σ
Emki Li E,t
mki Ikn-ti
(81)
&
GH
Σ (aah))) + A
ph.t e.T (,)
(kk
(82)
H
Σ in Ikn
(83)
ki
A.5 MF EQUATIONS
The feaanfieed (MF) equations are obtained as further simplification of BPI, using only non-cavity quantitics. Although the simplification appears minimal at this point, we empirically observe non-negligible discrepancy between the two algorithms in terms of generalization performance and computational time.
Forward pass.
dor
Ogp' (Bln-11 A f-liT yl-1,r) whi in
(84)
A
t.r
Sz (BhT-1, A w
f-1. in ,
(85)
m
t,
= HHv(H ( G 0%)
(86)
E.r
8 pp (H
1,0 - 0
(87)
kii
km
Σ mii
A lor
ks (o
+ oki
A 6,7
in
(88)
kn
f.T
Σ
mai
gl.
(89)
20

---

Under review as a conference paper at ICLR 2022
Backward pass.
9kn
d.r
= Owp
kn Aftli why vei
(90)
p&. - Cupett
(Bkm (Bfttir Alt w Vier
(91)
km
A.
2s 2,r E (mmki Lan oki Thin Oki (9hm
(92)
in.
B
fot d.t E
mia Ham
(93)
in
G
Σ(
A.n kn
A
E, E,T
9kn
(94)
Σ
Fn Ikn
dit lut
(95)
A.6 DERIVATION OF THE AMP EQUATIONS
In order to obtain the AMP equations, we approximate cavity quantities with non-cavity ones in the BP equations Eqs. 60 7I) using a first order expansion. We start with the mean activation:
a.. in
=By (B BB
1 1.--1 AhT-1 1-1, vf-1,T)
ki-m
in 2-1.7 ve-li1)
~B ( (B! - w in
m 1- 1.T-1
ki-n 03 / (Bih Ann Win ?
Er--l f-15 vi-lir)
2 /r 1 f-r-1
mm 9kn
A Pr
(96)
Analogously, for the weight's mean we have:
Mii-nn = (1 1 1 ( 0g1))
ki
& in
Ikn
0m 2- G Oha)
Fin Ibn Sn o ,G Obi))
= mm in
f.r 1 1
9kn ki
(97)
This brings us to:
w
m ki-zn in
Lit sf.
Σ
LiT al.
LT-1 Σ
f,--1
Σ
P.T E,r-1 f,7 mk mks
mki
9kn
ki Fin Fin
Ikn
+ (gkm
Σ
ki
lor l.- 1- E,T
Mkk
Fin
(98)
Let us now apply the same procedure to the other set of cavity messages:
Ikn -wy el (Bethir A ,w - mit AoT E Vhr
ttl Eit
2 etl (Bbtlo Aetlit ,w fot vlat) 1t41, Vilr
f.t a Rg e+1 +
miim
kn ,u
20kn mk Iin kn
(99)
21

---

Under review as a conference paper at ICLR 2022
Σ
Ei7 8,T
mil ki-n Ikn-
Σ
Eit 1,T
Bin E
Oki + st.r
(m ) 2
Mki 9kn
Ikn
(a Σ
Tki mys Ike km
fir Eor per
(100)
H
in Ikn
Σ
RiT 9kn + mk
Eit E
Lit Fin
Eo m
Br E(kin
)
(m
Σ
Ikn
Thr lot Lei Jon in
(101)
We are now able to write down the full AMP equations, that we present in the next section.
A.7 AMP EQUATIONS
In summary, in the last section we derived the AMP algorithm as a closure of the BP messages passing over non-cavity quantities, relying some statistical assumptions on messages and interactions. With respect to the MF message passing, we find some additional terms that go under the name of Onsager corrections. In-depth overviews of the AMP (also known as Mhouless-Anderson-
(TAP)) approach can be found in Refs. (Zdeborová & Krzakala 2016 Mézard 2017 Gabrid (020).
The final form of the AMP equations for the multi-layer perceptron is given below.
Initialization
At 0:
B4.0 0 in
(102)
A 4.0 in
(103)
L.00
0 or some values
(104)
G or some values
(105)
Ikn 0
(106)
Forward Pass At each 7 I,... Tman, for l. = O,..., Lı
2/1 OBy ( (BLT-1 1 1,5 Vf-1.r)
(107)
A 8 e (B/.7-1
1 - 1-1, 1L-1.
An
Win
(108)
mk HH 1 1-1
1 G6.--1 (%
(109)
k3
L. = o 1b (H -1 - (%)
(110)
vl.
tr + oki
ds
Pin
+ to
AeT
(111)
1, Wkn
Σ
.l.7
2.7-1 Σ
2.r
L.-
A E,r
mis
Fin
Ikn
Oii Fin
Ikn
mii
mik
in
+ (ghn
ki
m
A.T-lgEf-1 E.T
in
(112)
22

---

Under review as a conference paper at ICLR 2022
Backward Pass
9kn - e+] (B (Bin
f.7
Ahn win Ven))
A bit
(113)
rl.r 02 (B
A stl, whn: velT)
(114)
kn
kn
An k
Σ
P.T mki
+
tkk
fit rhe - okk 9kn
2)
(115)
B in
Σ
Mki
Ikn
in E
Ihoe
2
oki
sh. Σ
(mkk
)
kn
( Σ
Ok mki Ikn
Et Ei7 p.TTe.
(116)
(1.z)) 2)
G = Σ
in
A
in
r
km
A.T
Ikn
(117)
Σ
in Okn
for
+ mki
Fin
m
Σ
(mis
Ikn kn in Pin
lit
A C, dei
(118)
A.8 ACTIVATION FUNCTIONS
A.8.1 SIGN
In most of our experiments we use sign activations each layer. With this choice, the neuron's free energy 19 takes the form
log
Σ
H
JW VV
+ log(2TV).
1
(119)
=E(-1,+1}
where
H 2 erfc
(120)
Notice that for sign activations the messages A can be dropped.
A.8.2 RELU
For ReLU (x) = max(0, x) activations the free energy
19 becomes
((B,A,,,V) = f
/dndz dudz e 1bu=+ BB 5(x - max (0, 2))
(121)
log
H
w
Niw; B/A.V V + 1)
H VV AAA
BV +w
))
+
1
log log((2 12
AN(B:O, A)
AV
(122)
where
N(xx;1
22
(123)
/ Σ.
A.9 THE ARGMAX LAYER
In order to perform multi-class classification, we have to perform an argmax operation on the last layer of the neural network. Call 2k, for l: 1..., K, the Gaussian random variables output of the last layer of the network in correspondence of some input æ. Assuming the correct label is class k*, the effective partition function Z corresponding the output constraint reads:
23

---

Under review as a conference paper at ICLR 2022
25
25
train
train
20
20
error (%)
15
error (%)
15
10
10
epochs
epochs
Figure 4: MLP with 2 hidden layers with 101 hidden units each, batch-size 128 the Fashion- MNIST dataset. In the first two layers we use the BP equations, while in the last layer the ArgMax ones. (Left) Max layer first version; (Right) ArgMax layer second version. Even if it is possible to reach similar accuracies with the two versions, we decide to use the first one as it is simpler to use.
Zk- /II dz dzz de Vi)
II le
O -2k)
(124)
=
/ daw (Zzrr Vi+)
II H k
2k - Wk
(125)
VVk
Here (xx) is the Heaviside indicator function and we used the definition of from Eq. 120 The integral on the last line cannot be expressed analytically, therefore we have to resort to approximations.
A.9.1 APPROACH 1: JENSEN INEQUALITY
Using the Jensen inequality we obtain:
ΦL- = log Z = log Ee-N(uu Ve-)
II H
-- Wi
(126)
Vi
k#k
Σ k
Ben Vo-) log
2 Wk
(127)
VVx
Reparameterizing the expectation we have:
ŌR-
Σ be
E log (-
Wk+
+
eVVA-
Wk
(128)
VV
The derivative owg du- and 02, wu
6.- that need can then be estimated by sampling (once)
VV Eewsio.1 K. (- Enypey TVe I BewN(
k + h²
Vva
Our d..
(129)
wer -ev-er-
k =
VVe
where we have defined:
N(x)
22/T
K(xx)
(130)
H(xx)
erfcx(z/2)
24

---

Under review as a conference paper at ICLR 2022
A.9.2 APPROACH 2: JENSEN AGAIN
further simplification is obtained by applying Jensen inequality again [28 but in the opposite direction, therefore we renounce to having a bound and look only for an approximation. We have the new effective free energy:
Σ kipk
log E
(- wh- + VvVi- Wk
(-
(131)
V
(- Wki - Wk
Σ kep
log H
(132)
VVA VVo
Vis
This gives, for k + k*:
1- x(-
k + k
(133)
Σ Enigtee 1 K
(-
k k
Vir+VVe
VVar+Vie
Notice that Owg. H..
Eneeee Omc du. In last formulas used the definition of K. in Eq. 130
We show in Fig. the negligible difference between the two ArgMax versions when using BP on the layers before the last one (which performs only the ArgMax)..
B EXPERIMENTAL DETAILS
B.1 HYPER- PARAMETERS OF THE BP-BASED SCHEME
We include here complete list of the hyper-paramede present in the BP-based algorithms. Notice that, like in the SGD type algorithms, many of them can be fixed or is possible to find prescription for their value that works in most cases. However, more effective values of the saperrparameters, in the same way it has been done for SGD. These hyper-parameters are: the mini-batch size bs; the parameter p (that has be tuned similarly the learning rate in SGD); the damping parameter a (that performs a running smoothing on the BP fields along the dynamics by adding a fraction of the field the previous iteration, see Eqs. 134 135)); the initialization coefficient that we use to to sample the parameters of our prior distribution qe (W) according to (0 (0, 1). Different choices of e correspond to different initial distribution of the weights' magnetization m tanh(O(.). ), is shown in Fig. 5) the number of internal steps of reinforcement Tmax and the associated intensity of the internal reinforcement r. The performances of the BP-based algorithms are robust in reasonable range of these syper-parameters A more principled choice of a good initialization condition could be made by adapting the technique from Stamatescu et al. (2020).
expect future research to find even
Notice that among these parameters, the BP dynamics at each layer is mostly sensitive to and a, so that in general consider them layer-dependent. See Sec. [B8 for details on the effect of these parameters on the learning dynamics and on layer polarization (i.e. how the BP dynamics tends to bias the weights towards& single point-wise configuration with high probability). Unless otherwise stated we fix some of the hyper-parameters in particular: bs 128 (results are consistent with other values of the batch-size, from bs up to 1024 in our experiments), 1.0, Taaa 1,
B.2 DAMPING SCHEME FOR THE MESSAGE PASSING
We use a damping parameter a E (0, 1) to stabilize the training, changing the updated rule for the weights' means follows
nu. -0m((H - .%
(134)
mtt =a =am
1--1 + (1 a)) m
f.r
(135)
25

---

Under review as a conference paper at ICLR 2022
P(m)
0.1
0.5
1.0
1.5
2
-1.0
-055
0.5
1.0
Figure 5: Initial distribution of the magnetizations varying the parameter The initial distribution is more concentrated around +1 as increases (i.c. more bimodal and the initial configuration is more polarized).
B.3 ARCIITECTURES
In the experiments in which vary the architecture (see Sec. 4.1 all simulations of the BP-based algorithms use number of internal reinforcement iterations Tmax 1. Learning is performed on the totality of the training dataset, the batch-size is bs 128, the initialization coefficient is 1.0.
For all architectures and all BP approximations, we use & = 0.8 for each layer, apart for the (0.1, 0.1, 0.1, 0.9). Concerning the parameter p, = 0.9 on the last layer for all architectures and BP approximations. On the other layers we use: for the 101-101 and the 501-501 MLPs, p 1.0001 for all BP approximations; for the 101- 101-101 MLP. = 1.0 for BP and AMP while P = 1.001 for MF; for the 501-501-501 MLP p 1.0001 for all BP approximations, For the BinaryNet simulations, the learning rate is Ir 10.0 for all MIP architectures, giving the better performance among the learning rates we have tested,
501-501-501 MLP in which
100, 10, 0.1. 0.001.
We notice that while we need some tuning of the hyper- pneempaarmeters to reach the performances of BinaryNet, possible to them across datasets and architectures (e.g. P = 1 and = 0.8 on each layer) without in general losing more than 20% (relative) of the generalization performances, demonstrating that the BP-based algorithms are effective for learning also with minimal hyper- parameter tuning.
The experiments on the Bayesian error are performed on a MLP with hidden layers of 101 units on the MNIST dataset (binary classification). Learning is performed the totality of the training dataset, the batch-size is = 128, the initialization coefficient pointwise configurations
= 1.0. In order to find the 0.8 each layer and p (1.0001, 1.0001, 0.9), while find the Bayesian ones we use a 0.8 on each layer and (0.9999, 0.9999, 0.9) (these value prevent an excessive polarization of the network towards particular pointwise configurations).
For the continual learning task (see Sec, 4.5) we fixed p and a = 0.8 on each layer as we empirically observed that polarizing the last layer helps mitigating the forgetting while leaving the single-task performances almost unchanged.
In Fig. we report training curves on architectures different from the ones reported the main paper.
26

---

Under review as a conference paper at ICLR 2022
25
25
train
train
BP test
MF test
BP test
MF test
20
AMP train
BinoryNitt train
20
AMP train
BinoryNet Net train
AMP test
BinaryNit test
AMP tast
Bin test
error (%)
15
error (%)
15
10
10
epochs
epochs
Figure 6: Training curves of message passing algorithms compared with BinaryNet the Fashion- MNIST dataset (multi-class classification) with a binary MLP with hidden layers of 501 units. (Right) The batch-size is 128 and curves averaged over realizations of the initial conditions
B.4 VARYING THE DATASET
When varying the dataset (see Sec. all simulation of the BP-based algorithms use a number of internal reinforcement iterations Tiax 1. Learning is performed on the totality of the training dataset, the batch-size is bs 128, the initialization coefficient e = 1.0. For all datasets (MNIST (2 classes), MNSS (2 classes), CIFAR-IO (2 classes), MNIST, FashionMNIST, CIFAR-I0) and all algorithms (BP, AMP, MF) we use p = (1.0001, 1.0001, 0.9) and a 0.8 for each layer. Using in the first layers values of p 1 with 2 0 and sufficiently small typically leads to good results.
For the BinaryNet simulations, the learning rate is ir 10.0 (both for binary classification and multi-class classification), giving the better performance among the learning rates we have tested, Ir 100, 10, 0.1, 0.001. In Tab. 2 we report the final train errors obtained the different datasets.
Dataset
BinaryNet
BP
AMP
MF
MNIST (2 classes)
0.05 + 0.05
0.0 0.0
+ 0.0
0.0
FashionMNISTT (2 classes)
0.3 = 0.1
0.06 0.01
0.06 + 0.01
0.09 1 0.01
CIFAR10 classes)
1.2 0.5
0.4
0.9 0.2
MNIST
0.09 = 0.01
0.12
0.12 0.01
0.03 = 0.01
FashionMNIST
4.0 = 0.5
3.4
3.7
2.5 = 0.2
CIFAR10
13.0 0.9
4.7
4.7
9.2 0.5
Table 2: Train enror (%) on Fashion-MNIST of multilayer perceptron with 2 hidden layers of 501 units each for BinaryNet (baseline), BP, AMP and MF, All algorithms are trained with batch-size 128 and for 100 epochs. Mean and standard deviations are calculated over 5 random initializations.
B.5 LOCAL ENERGY
We adapt the notion of flatness used (Jiang et al. 2020: Pittorino et al.) 2021 that we call local energy, configurations with binary weights. Given weight configuration E (=1)%, define the local energy ò Exain (w, p) as the average difference in training emror Exnin (w) when perturbing w by flipping a random fraction p of its elements:
Farain (w.p) p) Eg Fizin (w 2) Fizai (wr).
(136)
where @ denotes the Hadamard (element-wise product and the expectation is over i.idd entries for equal to -1 with probability p and to +1 with probability 1 p. We report the resulting local energy
profiles (in range (0, Pmnx)) in Fig. right panel for BP and BinaryNet. The relative error grows
27

---

Under review as a conference paper at ICLR 2022
slowly when perturbing the trained configurations (notice the convexity of the curves). This shows that both BP-based and SGD-based algorithms find configurations that lie in relatively flat minima in the energy landscape. The same qualitative phenomenon holds for different architectures and datasets.
0.35
BinaryNet
BP
0.30
0.25
local energy
0.20
0.15
0.10
0.05
0.00
0.00
0.05
0.10
0.15
0.20
0.25
0.30
0.35
flip probability
Figure 7: Local energy curve the point-wise configuration found by the BP algorithm compared with BenaryNet on a MLP with 2 hidden layers of 101 units on the 2-class MNIST dataset.
B.6 SGD IMPLEMENTATION (BINARYNET)
We compare the BP-based algorithms with SGD training for neural networks with binary weights and activations as introduced BinaryNet (Hubara et al. 2016). This procedure consists in keeping continuous version of the parameters which is updated with the SGD rule, with the gradient calculated on the binarized configuration WA sign(w) (w). At inference time the forward pass is calculated with the parameters wg. The backward pass with binary activations is performed with the so called srraight-hrouug estimator.
Our implementation presents some differences with respect the original proposal of the algorithm in (Hubara et al. 2016), order to keep the comparison as fair as possible with the BP-based algorithms, in particular for what concerns the number of parameters. We do not biases normalization layers, therefore in order to keep the pre-activations of each hidden layer normalized we rescale them by VN where N is the size of the previous layer (or the input size in the case of the pre-activations afferent to the first hidden layer). The standard SGD update rule is applied (instead of Adam), and we use the binary cross-entropy loss. Clipping of the continuous configuration in [-1, 1] is applied. We use Xavier initialization (Glorot & Bengio 2010) for the continuous weights. In Fi the main paper, we apply the Adam optimization rule, noticing that performs slightly better in train and test generalization performance compared to the pure SGD one.
batch
B.7 EBP IMPLEMENTATION
Expectation Back Propagation (EBP) Soudry et al. (2014b) parameter-free Bayesian algorithm that uses mean-field (MF) approximation (fully factorized form for the posterior) in an online environment to estimate the Bayesian posterior distribution after the arrival The main differences between EBP and our approach relies in the approximation for the posterior distribution. Moreover we explicitly base the estimation the marginals on the local high entropy structure. The fact that EBP works has clear explanation: certainly it cannot be that the MF assumption holds for multi-layer neural networks. Still, it's certainly very interesting that works. We argue that it might work precisely by virtue of the existence of high local entropy minima and
new data point.
28

---

Under review as a conference paper at ICLR 2022
1.00
BP test
BP train
MF train
MF test
0.75
197 layart
(gab)
0.010
BP lyyert
layer1
20
AMP train
BinaryNet train
0.50
AMP layer! tayer?
0.005
MF layert
AMP test
BinaryNet test
100
50 epochs
100
epochs
erfor (%)
15
1.00
(q0)
0.75
BP Tayer2 layer2
(gab)
0.0050
AMP layar
layerd
0.0025
MI layw22
10
0.50
MF laywr
epochs
epochs
RP Inyar3
0.04
RP lyyer
(g0)
layerd MI layer)
(qab)
layer3
0.2
0.02
MP byyerd
0.00
0
20
40
60
80
100
50 epochs
100
50 epochs
100
epochs
Figure 8: (Right panels) Polarizations (go) and overlaps (g.b) each layer of a MLP with 2 hidden layers of 501 units on the Pashion-MNIS dataset (multi-class), the batch-size bs 128. (Right) Corresponding train and test error curves.
expect to give similar performance to the MF case of our algorithm. The online iteration could in fact be seen way of implementing a reinforcement.
We implemented the EBP code along the lines of the original matlab implementation - In order to perform a fair comparison we removed the biases both in the binary and continuous weights versions. It is worth noticing that faced numerical issues in training with moderate to big batchsize All the experi- ments were consequently limited to a batchsize of 10 patterns
(https://github.co http///xpccationaaaepoongggioioo
B.8 UNIT POLARIZATION AND OVERLAPS
We define the self-overlap or polarization of a given unit a as g8 = E. where N is the number of parameters of the unit and {wf Ji=1 its weights. quantifies how much the unit is polarized N
towards unique point- wise binary configuration (6 corresponding to high confidence in given configurations while o 0 to low). The overlap between two units a and b (considered in the same layer) is qah = + Σ wf w.. The number of parameters N is the same for units belonging the same fully connected layer. We denote by (go) = N... Enen d and (gus) = N... Nont the mean polarization and mean overlap in a given layer (where Nout is the number of units in the layer).
The parameters p and a govern the dynamical evolution of the polarization of each layer during training. A value p ž has the effect to progressively increase the units polarization during training. while p < 1 disfavours dynamics by a smoothing process (the intensity of which depends on the value of a), generically favoring convergence. Given the nature of the updates in Algorithm [ each layer presents its own dynamics given the values of Pe and of at layer É, that in general can differ from each other.
The damping a which takes values in [0, 1] has the effect to slow the
We find that is is beneficial to control the polarization layer-per-layer, see Fig. for the correspond- ing typical behavior of the mean polarization and the mean overlaps during training. Empirically, we have found that (as we could expect) when training is successful the layers polarize progressively towards go 1, i.c. towards precise posnt-wise solution, while the overlaps between units in each hidden layer are such that Gub < (indicating low symmetry between intra-layes units, as expected for -nndunuund solution). To this aim, in most cases af can be the same for each layer, while tuning Pe for each layer allows to find better generalization performances in some cases (but is not strictly necessary for learning).
In particular, it is possible to use the same value Pr for each layer before the last one (E < L where I. is the number of layers in the network), while we have found that the last layer tends to
29

---

Under review as a conference paper at ICLR 2022
polarize immediately during the dynamics (probably due to its proximity to the output constraints). Empirically, it is usually beneficial for learning that this layer does not or only slightly polarize, i.e. (9o) < 1 (this can be achieved by imposing Pr. 1). Learning is anyway possible last layer polarizes towards (go) = along the dynamics, i.e. by choosing Pr. sufficiently large.
when the
As simple general prescription in most experiments leaving Piet. as the only hyper- aaper-parameters to be tuned, akin to the learning rate SGD. Its value has be very close 1.0 value smaller than 1.0 tends depolarize the layers, without focusing particular point-wise binary configuration, while a value greater than 1.0 tends to lead to numerical instabilities and parameters' divergence).
fix 0.8 and PL 0.9, therefore
B.9 COMPUTATIONAL PERFORMANCE: VARYING BATCH- SIZE
In order to compare the time performances of the BP-based algorithms with our implementation of BinaryNet, we report Fig. 9 the time in seconds taken by single epoch of each algorithm in function of the batch-size.
a MLP of 2 layers of 501 units Fashion-MNIST We test both algorithms on a NVIDIA GeForce RTX 2080 Ti GPU. Multi-class and binary classification present very similar time scaling with the batch-size, in both cases comparable with BinaryNet. Let us also notice that BP-based algorithms are able to reach generalization performances comparable to BinaryNet for all the values of the batch-size reported in this section.
102
BP
BPI
AMP
time per epoch (s)
MF
10
BinaryNet
100
X
100
10 batch size
102
103
Figure 9; Algorithms time scaling with the batch-size on a MLP with 2 hidden layers of 501 hidden units each on the Fashion-MNIST dataset (multi-class classification). The reported time (in seconds) refers to one epoch for each algorithm.
30


Reviews:
[{"review_id": "jLs-DW4zyd", "reviewer": "Reviewer_nNGL", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Strengths of the paper**\n-  A new paradigm of deep neural network training is prosed based on well-known belief propagation, which is a very interesting and positive try. I do think that such kind of exploration itself is meaningful for future research. \n- The resultant algorithms achieve comparable performances as the SGD based methods. In particular, the mini-batch implementation running time is also about the same order as SGD, although apparently, it is still slower than the standard SGD algorithms. \n\n**Weaknesses of the paper**\n-  **The first weakness is that there seem no apparent advantages of the performances of the BP-based methods** (even for most complicated BP/BP-I), both in terms of the generalization error and running time (or implementation simplicity). Given this fact, then, one might doubt the practical usage of BP-based methods. As a result, it would be really helpful if the authors could find some scenarios that BP-based methods that are favorable. \n\n Indeed, it is noticed that the authors had already made an effort in this direction, i.e., the evaluation of local Bayes error and local energy, and the application in continual learning,  similar to the Bayesian neural networks. Some comments are as follows:\n\n1. Using more standard benchmark metrics to quantify uncertainty under distributional shift\n\nAlthough local Bayes error and local energy are interesting merits, other standard benchmark metrics to quantify uncertainty under distributional shift such as Expected Calibration Error (ECE) and out of distribution (OOD) entropy might be of more interest [1]. It is thus suggested to add experiments on such standard benchmark metrics [1] and compare with other Bayesian deep learning methods.\n\n2. Adding comparisons with previous methods for continual learning (CL) \n\nAlthough the BP-based method is shown to be well-adapted to continual learning,  this might not be viewed as a special advantage since there are a variety of simple methods for the SGD-based method to enable continual learning [2,3].  All kinds of Bayesian methods (including BP-based) such as variational Bayes, Laplace method et al, are all naturally well-adapted to continual learning within the variational continual learning (VCL) framework[4] and others.  In particular, for binary neural networks considered in this manuscript, there also have been some studies on SGD-based Bayesian training algorithms well-adapted to continual learning, e.g.,[5]. The authors only compare BPI with standard BinaryNet and it is suggested to add some comparison with these previous continual learning algorithms to see if there is any improvement of BP-based methods. \n\n-  **The second weakness is that only binary neural network is considered and there is a lack of evaluation of the continuous weights of BP-based methods**. From my own understanding, the proposed BP-based methods are readily applicable to deal with continuous weights, e.g., AMP was firstly designed to deal with continuous weights. So, why continuous weights are not considered here? It would be helpful if several results for continuous weights can be added with a comparison with SGD based methods.  Otherwise, please add some discussions of the differences between continuous weights and binary weights. \n\n- **The third weakness is that there is a lack of comparisons with several closely related works, in particular, the Expectation Backpropagation (EBP) algorithm [6]**\n\n1. Several closely related works on previous attempts in training deep neural networks using BP-like algorithms are missing. In particular, **[6] proposed one Expectation Backpropagation (EBP) algorithm**, which is applicable to **train deep neural networks with not only binary weights but also continuous weights**. EBP also has a forward pass and backward pass as the paradigm in the current manuscript. Moreover, **EBP has been shown to have similar efficiency and update form as the SGD based method, while achieving competitive performances**.  Although it is based on EP rather than BP in this manuscript, the two are very closely related [7]. In particular, for the AMP variant considered in the current manuscript, **AMP has been proved to be an approximation of EP in [8,9]**. Then, does it imply that the proposed AMP training version is similar to EBP in [6]?  Given such similarity, it is highly suggested to discuss the differences and intrinsic relationships between EBP with the proposed BP-based method, as well as adding comparisons in the experients. \n\n2. Another related method is the proximal mean-field (PMF) method in [10], which is also one training algorithm for deep binary neural networks. **PMF  is proved to be equivalent to a proximal version of the mean-field (MF) method**. As a result, what is the difference between the MF version in the current manuscript from the PMF method in [10]? \n\n3. Moreover, in the Bayesian deep learning community, there are various Bayesian training algorithms using mean-field variational inference methods (eg., [11,12,13]) but are based on SGD methods. Then, what is the key difference between the MF algorithm in the current manuscript with those MF-VI methods? It seems that they (including AMP, BPI, BP) optimize the same variational objective (ELBO bound) but the only difference is the specific optimization methods, previous ones (e.g.,[11,12, 13]) used the SGD to optimize the ELBO bound, while the MF in current manuscript used message passing updates. If so, then maybe the results are expected to be similar or the same? And possibly the BP-based method is not fundamentally different from the SGD method as stated?  Another interesting point is that, from current experimental results, BPI and AMP are basically the same as MF, while apparently BPI and AMP use more accurate (tree-structured, or Bethe) approximations. Can the authors provide some insights into the negligible differences between them? \n\n\n**Additional Technical Comments**\n\n1. It seems that the so-called Posterior-As-Updates (PasP) is simply the core of the Bayesian theorem in the sequential updates setting (here different mini-batch corresponds to different observations, though possibly with an overlap), which I think is also used in [7] similarly. \n\n2. In the experiment parts, e.g, Figure 1 and Table I, why results of BP are missing? \n\n3. After training, how to perform the prediction using the results of BP-based methods? Are they obtained by sampling from the posterior distribution first and then computing the average output of different samples? Please illustrate clearly in the main text. Also, can the authors plot the posterior distribution of the learned weights? \n\n4. Similarly, how the continual learning is performed? Is it using the learned posterior of the previous task as prior over the next task to learn, similarly as [4,5]? \n\n5. Why the training error of BP-based methods are much lower than SGD while the test error is high or about the same? Is there any intuitive explanation? \n\n6. It is unclear of the so-called _additional reinforcement message_ and how the resultant BP-based algorithms are different from the original versions, e.g., MF, AMP. It would be better to give some explanations in the main text if this point is important. \n\n7. The submitted code of this manuscript seems unavailable. \n\n8. It is suggested to add a discussion of the limitations of the BP-based methods from current results. It seems that although it is comparable (or slightly worse with slightly higher complexity) to SGD methods, additional advantages (Bayes, continual learning) are not apparent either, given that a variety of Bayesian deep learning methods can do the same in a (presumably) simpler way.\n\n\n**References**\n\n[1] Ovadia, Yaniv, et al. \"Can you trust your model's uncertainty? Evaluating predictive uncertainty under dataset shift.\" NeurIPS 2019. \n\n[2]  Zenke, Friedemann, Ben Poole, and Surya Ganguli. \"Continual learning through synaptic intelligence.\" ICML, 2017.\n\n[3] Parisi, German I., et al. \"Continual lifelong learning with neural networks: A review.\" Neural Networks 113 (2019): 54-71.\n\n[4] Nguyen C V, Li Y, Bui T D, et al. \"Variational continual learning.\" ICLR 2018.\n\n[5] Meng X, Bachmann R, Khan M E. \"Training binary neural networks using the bayesian learning rule\". ICML 2020.\n\n[6] Soudry, Daniel, Itay Hubara, and Ron Meir. \"Expectation backpropagation: Parameter-free training of multilayer neural networks with continuous or discrete weights.\" NeurIPS. Vol. 1. 2014.\n\n[7] Minka, Tom. Divergence measures and message passing. Technical report, Microsoft Research, 2005.\n\n[8] Meng X, Wu S, Kuang L, et al. \"An expectation propagation perspective on approximate message passing\". IEEE Signal Processing Letters, 2015, 22(8): 1194-1197.\n\n[9]  B. Cakmak, O. Winther, and B. H. Fleury, “S-AMP: Approximatemessage passing for general matrix ensembles,” in IEEE Information Theory Workshop (ITW), Nov. 2014, pp. 192–196.\n\n[10] Ajanthan T, Dokania P K, Hartley R, et al. \"Proximal mean-field for neural network quantization[C]//Proceedings of the IEEE/CVF International Conference on Computer Vision. 2019: 4871-4880.\"\n\n[11] Alex Graves. \"Practical Variational Inference for Neural Networks\". In NIPS, 2011\n\n[12] Charles Blundell, Julien Cornebise, Koray Kavukcuoglu, and Daan Wierstra. Weight Uncertainty in Neural Networks. In ICML, 2015.\n\n[13] Osawa, Kazuki, et al.. \"Practical Deep Learning with Bayesian Principles\". In NeurIPS, 2019.\n\n", "summary_of_the_paper": "This manuscript provides an interesting try on alterative training algorithms for deep neural networks, based on (approximate) message-passing algorithms based on the well-known belief propagation (BP) algorithm.  In particular, the binary neural network is considered and four algorithms (BP, three variants of BP, i.e., BPI, MF, AMP) are proposed within a unified Posterior-As-Prior Update framework. Experiments are conducted on standard supervised classification tasks and continual learning settings, which shows comparable performances as standard SGD based methods. \n\n==========================\nAfter rebuttal:\n=========================\n\nI have read the authors' feedback (many thanks for the detailed point-to-point feedback) and other reviewers' comments and modified the score accordingly. Overall, the proposed scheme is interesting, though strictly speaking the results are not very advantageous (at least from its current results) compared to traditional ones, and some of the comparisons seem not very reasonable/fair. \n\n", "summary_of_the_review": "This paper applies the well-known belief propagation (BP) algorithm and several variants to train deep neural networks with binary weights. Overall I like the topic of this manuscript and it is a good start to explore the potentials of BP-based methods for deep learning. While this is indeed a very interesting try, there are several aspects to be improved for the current manuscript, such as a systematic evaluation of the potential advantages of the proposed BP-based methods, a comparison with previous closely related algorithms especially the EBP algorithm and other Bayesian deep learning methods, as well as clarifications of some related technical points, as detailed above. In addition, given the comparable (or slightly worse performance with higher complexity) but not competitive results of the proposed BP-based algorithms, it is worth a discussion of the intuitive reason behind it. This is not saying that it is not useful to study an algorithm without SOTA performance, but rather on the opposite, it is very useful to explain the (intuitive) underlying reason why it works this way even it is not SOTA, as well as its limitations. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "YBqh09Epq2E", "reviewer": "Reviewer_tYY4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "[Main Strengths] \n\nThis paper's main strength is that the authors' method of using message-passing to train NNs is pretty interesting, the introductory section is well-written, and the implementation GitHub repo is intended to be provided.\n\n================================================================= \n\n[Main Weaknesses] \n\nThe fundamental shortcoming of this study is that, while the basic concept is intriguing, it does not appear to make a significant impact, much like the various flavors of SGD. I invite authors to make the further improvement suggested in Section 4.4, which is to show that message passing is inherently less prone to catastrophic forgetting issues, which will be highly intriguing and will undoubtedly require more clear justification.\n\n================================================================= \n\n[Technical Comments] \n\n1) Is it possible to expand this method to multi-class scenarios, such as extending message-passing decoding algorithms from binary linear codes to non-binary codes?\n2) Furthermore, substantial message passing successes have occurred in the past, particularly for sparse factor graphs. As a result, future applications of Graph neural networks or sparse Transformers will be quite fascinating.\n\n================================================================= \n\n[Typographical comments]\n1) To ensure perfect anonymity, erase the name displayed in Acknowledgement.\n2) On page 3, the term \"PasP rule\" is not defined until it is used in Section 2.\n", "summary_of_the_paper": "[Summary] \n\nThis paper develops a class of fBP-based message-passing algorithms by adding a \n“reinforcement “ term to the BP equations and shows equivalent performance to the binary networks in experiments.", "summary_of_the_review": "Using message-passing to train NNs is intriguing, but, like the various flavors of SGD, it does not appear to make a significant difference.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "NG8qiofnc6P", "reviewer": "Reviewer_jTGp", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Clarity of writing:  The manuscript contains a significant number of typos that, while irritating to read, do not inhibit understanding.  The larger issues are the plethora of undefined or underdefined terminology, e.g., channel functions, damping, etc., the imprecise mathematical formulations, e.g., dimension of vectors, z^l, etc., and the lack of motivation for mathematical formulations, e.g., BP is never really defined and equations (8)-(19) are unmotivated.\n\nNovelty:  The general approach (with the prior) seems novel to me, but it is a bit unclear exactly what other pieces are novel here compared to existing work.  \n\nSignificance:  While it is interesting that a BP style message passing approach can achieve comparable levels of performance to SGD, the overall significance of the works seems somewhat limited.  In particular, I'm not sure that the authors really present a compelling example of when this approach would be preferred over pure SGD based solutions.\n\nSpecific comments:\n\n- The introduction makes vague claims without support, e.g., no citations for applications of BP, \"additional approximation turns out to be benign\", etc.  Consider making it more precise.\n- The paper conflates factorizations with factor graphs (which aren't really discussed at all).\n- \"non-homogeneous\" -> inhomogeneous\n- What is a scalar channel function?  It needs a definition.\n- \"The training error is usually lower for optimized configurations from message passing schemes, suggesting that these algorithms are able to achieve higher capacity than SGD-based algorithms (given the same test error)\"  While, looking that the plots, the convergence of some of the BP variants is certainly better than SGD, I'm not sure that your statement would continue to hold if you ran for another 100 epochs.\n- Do you use adaptive step size methods like ADAM for SGD?  \n- The experiments make claims about deep neural networks, but most of the experimental results are on shallow networks.\n- The number of repeated runs in the experiments (5 in some cases) might be a little small.", "summary_of_the_paper": "The authors describe a \"focused\" belief propagation strategy for learning NNs.  They argue that it continues to exhibit some of the same nice properties that stochastic gradient methods have in practice with the added benefit of allowing the computation of approximate marginals to improve the accuracy of predictions.", "summary_of_the_review": "An interesting approach that is hampered by a poor presentation, somewhat limited experimental results, and only minor justification for why it should be seriously considered as an alternative approach to more well-studied approaches for training neural networks.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "0WlAix6UkHk", "reviewer": "Reviewer_SnTy", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Correctness:\nNo correctness concerns.\n\nTechnical novelty and significance:\nOne of the ideas of the paper---to use belief propagation to estimate the marginals of the weights of a neural network (NN) in order to make probabilistic predictions---is a novel paradigm allowing to attach confidence to NN predictions. This is a research direction with a lot of potential which can lead to better NN performance in many tasks.\nHowever, the paper's theoretical contributions are somewhat limited as they seem to be very similar to the contributions of (Baldassi et al., 2016). Although the authors claim that the novelty of their approach is that their results apply to mini-batch training and deep neural networks, it is unclear how the results derived for deep neural networks differ from those derived for shallow ones in (Baldassi et al., 2016). Can the authors provide a more detailed explanation?\n\nEmpirical novelty and significance:\nThe second numerical experiment (on continual learning) provides empirical justification to use the proposed algorithm to avoid catastrophic forgetting. The downside of the numerical results is that, again, the neural network architectures that are considered are not very deep. They are wide, but this wasn't as emphasized in the text. In the first numerical experiment, the proposed method does not have any advantages with respect to SGD other than a lower training error. The authors mention that this could suggest that their algorithm leads to better NN capacity, but this is not explored any further in the text. I suggest running simulations with deeper neural networks and expanding on the advantages and disadvantages of the proposed BP-scheme.\n\nOther concerns:\n- What is the quality of the approximation in eq. (3), i.e., how much is lost by making this approximation?\n- It would be helpful to have a formal definition for the variables in eqs. (6) and (7).\n- In the caption of Fig. 2, the authors state that \"the training hyperparameters in the two cases are independently selected and generally differ\". How are they selected? By cross-validation?\n\n\n", "summary_of_the_paper": "This paper introduces a belief-propagation message-passing training algorithm for multi-layer neural networks. This algorithm is adapted to mini-batch training and biases distributions toward high entropy solutions. Empirical results show that neural networks with discrete weights and activations trained with this algorithm achieve comparable performance the same networks trained with SGD (BinaryNet), and can make approximate Bayesian predictions that have higher accuracy than pointwise solutions.", "summary_of_the_review": "Although the paper is a close extension of (Baldassi et al. 2016), the idea to use belief propagation to estimate the marginals of the weights of a neural network (NN) in order to make probabilistic predictions is a novel paradigm and the empirical results on continual learning seem promising. I recommend acceptance subject to the clarification of the concerns discussed in the main review.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents a method for training neural networks with belief propagation-based algorithms. The approach is to set a fully factorized prior over weights, compute a forward and backward pass of messages on a minibatch, then set the new prior to be a slightly higher temperature version of the minibatch approximate posterior. This new prior is then used for the next minibatch, and training iterates.

There is a huge range of opinions amongst reviewers. The main thing that reviewers appreciate is the novelty of using belief propagation instead of backpropagation for training neural networks. Finding alternatives to backprop with favorable properties could be hugely impactful, so even small gains in this direction are valuable. The posterior-as-prior update is interesting, and the authors have clearly put in care to getting things working. The main weaknesses are that some of the experiments aren’t always reasonable and fair, the paper is framed to overstate its contribution, and there’s not a clear advantage over standard approaches (e.g., MNIST error rates for a two hidden layer network are >2%).

In the end, this is a very borderline paper, but I find Rev nNGL’s position to be most informative. In particular, the paper frames the main contribution to be message passing as an alternative to SGD for training neural networks, but this is too broad of a framing given the existence of other closely related approaches like Soudry et al pointed out by Rev nNGL. I’d recommend that the authors frame their work as an advance over other message passing-based approaches to training neural networks, and to focus on piecing apart precisely why the proposed approach improves over EBP and alternatives.
Decision: Reject