content_image/416069.jpg content_image/416070.jpg content_image/416095.jpg content_image/416094.jpg content_image/416093.jpg content_image/416092.jpg
(b) the subgraphs G$_{i}$$_{←}$$_{r}$ ( t ) . 

Similarly, define the subgraph G$_{i}$ ( t ) to be the subgraph using all r ∈ N$_{out}$ ( i ) . 

3) Input update: For all ( i, j ) ∈ E , let G$_{i}$$_{←}$$_{j}$ ( t + 1) be the subgraph containing the node x$_{j}$ and for all ℓ ∈ N$_{in}$ ( j ) ̸ = i : 

(a) the edges ( ℓ, j ) ; 

(b) the output nodes y$_{ℓ}$ ; and 

(c) the subgraphs G$_{ℓ}$$_{→}$$_{j}$ ( t ) . 

Similarly, define the subgraph G$_{j}$ ( t ) to be the subgraph using all ℓ ∈ N$_{in}$ ( j ) . Set t = t + 1 and return to step 1. 

Now let H$_{i}$$_{→}$$_{j}$ ( t ) be the sigma algebra generated by the components y$_{ℓ}$ contained in the computation subgraph G$_{i}$$_{→}$$_{j}$ ( t ) . Similarly, let H$_{i}$$_{←}$$_{j}$ ( t ) be the sigma algebra gen- erated by the components y$_{ℓ}$ contained in the computation subgraph G$_{i}$$_{←}$$_{j}$ ( t ) . To analyze the BP algorithm with the “ge- nie” initialization in Appendix B, let H genie i → j ( t ) and H genie i ← j ( t ) be respectively the sigma algebras generated by the entire vector y and the variable x$_{r}$ not in the computation subgraphs G$_{i}$$_{→}$$_{j}$ ( t ) and G$_{i}$$_{←}$$_{j}$ ( t ) . The following results are standard for BP and can be proven using arguments as in [41]. 

Lemma 4: Consider the sigma algebras H$_{i}$$_{←}$$_{j}$ ( t ) and H$_{i}$$_{→}$$_{j}$ ( t ) defined above. 

(a) In the standard BP algorithm in Section III, the distribu- tions p x i ← $_{j}$( t, x$_{j}$ ) are H$_{i}$$_{←}$$_{j}$ ( t ) measurable, and the dis- tribution p z i → $_{j}$( t, z$_{i}$ ) and likelihood function p u i → $_{j}$( t, u$_{j}$ ) are H$_{i}$$_{→}$$_{j}$ ( t ) measurable. 

(b) In the relaxed BP algorithm, ̂ x$_{i}$$_{←}$$_{j}$ ( t ) and ̂ q$_{i}$$_{←}$$_{j}$ ( t ) are H$_{i}$$_{←}$$_{j}$ ( t ) measurable and ̂ z$_{i}$$_{→}$$_{j}$ ( t ) and ̂ u$_{i}$$_{→}$$_{j}$ ( t ) are H$_{i}$$_{→}$$_{j}$ ( t ) measurable. 

Similarly, under the oracle initialization described in Appendix B, the above statements hold with H$_{i}$$_{←}$$_{j}$ ( t ) and H$_{i}$$_{→}$$_{j}$ ( t ) replaced by H genie i ← j ( t ) and H genie i → j ( t ) . 

Lemma 5: Consider the standard BP algorithm in Section III and the computation subgraphs defined above. 

(a) If G$_{i}$$_{←}$$_{j}$ ( t ) is a tree, then p x i ← $_{j}$( t, x$_{j}$ ) is the conditional distribution of x$_{j}$ given H$_{i}$$_{←}$$_{j}$ ( t ) . z 

(b) If G$_{i}$$_{→}$$_{j}$ ( t ) is a tree, then p i → $_{j}$( t, z$_{i}$ ) is the conditional distribution of z$_{i}$$_{→}$$_{j}$ given H$_{i}$$_{→}$$_{j}$ ( t ) . 

Similarly, under the genie initialization, the above statements hold with H$_{i}$$_{←}$$_{j}$ ( t ) and H$_{i}$$_{→}$$_{j}$ ( t ) replaced by H genie i ← j ( t ) and H genie i → j ( t ) . 

Lemma 6: Consider the relaxed BP algorithm in Section IV under the assumptions in Section V. 

(a) If G$_{i}$$_{←}$$_{j}$ ( t ) is a tree, then all the terms ($_{̂}$ z$_{ℓ}$$_{→}$$_{j}$ ( t ) , µ z i → $_{j}$( t )) are independent for different values ℓ ∈ N$_{in}$ ( j ) ̸ = i . x 

(b) If G$_{i}$$_{→}$$_{j}$ ( t ) is a tree, then the random vectors θ i ← $_{r}$( t ) are independent for different values r ∈ N$_{out}$ ( i ) ̸ = j . 

We prove this by induction. It is clear that (42a) holds for t = 1 . In part B below we will show that if (42a) holds for some t , then so does (42c) and (42d). Then, in part C, we will show that if (42c) holds for some t , then (42a) holds for t +1 . This will complete the induction argument. Part A provides a preliminary calculation that we need in part C. 

## APPENDIX E 

## PROOF OF THEOREM 1(A) 

## A. Derivatives of the Score Function 

The following lemma characterizes the derivatives D$_{r}$ ( y,$_{̂}$ z, µ ) in (16). The result can also be found in [14], but we sketch the proof here for completeness. We will use this result below in the analysis of the output node update. 

Lemma 7: Fix ̂ z and µ and consider random variables y and z generated by z ∼ N ($_{̂}$ z + u, µ ) and y ∼ p$_{Y}$$_{|}$$_{Z}$ ( y | z ) for some u ∈$_{R}$ . Consider the derivative of the score function in (16). Then, 

<img src='content_image/416069.jpg'>

<img src='content_image/416070.jpg'>

Proof: To simplify the notation, we will drop the depen- dence on ̂ z and µ . So, we will write, for example, D$_{1}$ ( y ) for D$_{1}$ ( y,$_{̂}$ z, µ ) . To prove (51a), we first note that 

<img src='content_image/416095.jpg'>

Now, for the first term in (52), note that using the definition of D$_{1}$ ( y ) in (16), we have 

<img src='content_image/416094.jpg'>

Similarly, the second term in (52) can be simplified by eval- uating the second-order derivative in the definition of D$_{2}$ ( y ) to obtain 

<img src='content_image/416093.jpg'>

Now, 

<img src='content_image/416092.jpg'>

