RELAXED BELIEF PROPAGATION 12 (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 ) . E [ D$_{1}$ ( y,$_{̂}$ z, µ ) | u ] = − u E [ D$_{2}$ ( y,$_{̂}$ z, µ ) | u = 0] + O ( u $^{2}$) , (51a) var [ D$_{1}$ ( y,$_{̂}$ z, µ ) | u ] = E [ D$_{2}$ ( y,$_{̂}$ z, µ ) | u = 0] + O ( u $^{2}$) . (51b) 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, A. Derivatives of the Score Function 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. 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. Now, 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 (b) If G$_{i}$$_{→}$$_{j}$ ( t ) is a tree, then the random vectors θ x i ← $_{r}$( t ) are independent for different values r ∈ N$_{out}$ ( i ) = j . (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 . (b) If G$_{i}$$_{→}$$_{j}$ ( t ) is a tree, then p z i → $_{j}$( t, z$_{i}$ ) is the conditional distribution of z$_{i}$$_{→}$$_{j}$ given H$_{i}$$_{→}$$_{j}$ ( t ) . (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 ) . 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. APPENDIX E PROOF OF THEOREM 1(A) ∫ ∂ 2 ∂u 2 p$_{Y}$$_{|}$$_{U}$ ( y | u ) ∣ u =0 dy = ∂ 2 ∂u 2 ∫ p$_{Y}$$_{|}$$_{U}$ ( y | u ) ∣ u =0 dy = ∂ 2 ∂u $_{2}$(1) = 0 . (55) E [ D$_{2}$ ( y ) | u = 0] = ∫ 1 p$_{Y}$$_{|}$$_{U}$ ( y | 0) ( ∂ ∂u p$_{Y}$$_{|}$$_{U}$ ( y | u ) ∣ u =0 ) 2 dy − ∫ ∂ 2 ∂u 2 p$_{Y}$$_{|}$$_{U}$ ( y | u ) ∣ u =0 dy. (54) ∫ p$_{Y}$$_{|}$$_{U}$ ( y | 0) D$_{1}$ ( y ) dy = − ∫ p$_{Y}$$_{|}$$_{U}$ ( y | 0) ∂ ∂u log p$_{Y}$$_{|}$$_{U}$ ( y | u )$^{∣}$ ∣ ∣ u =0 dy = − ∫ ∂ ∂u p$_{Y}$$_{|}$$_{U}$ ( y | u )$^{∣}$ ∣ ∣ u =0 dy = − ∂ ∂u ∫ p$_{Y}$$_{|}$$_{U}$ ( y | u ) dy ∣ u =0 = − ∂ ∂u (1) = 0 . (53) E [ D$_{1}$ ( y ) | u ] = ∫ p$_{Y}$$_{|}$$_{U}$ ( y | u ) D$_{1}$ ( y ) dy = ∫ p$_{Y}$$_{|}$$_{U}$ ( y | 0) D$_{1}$ ( y ) dy + u$^{∫}$ ∂ ∂u p$_{Y}$$_{|}$$_{U}$ ( y | u )$^{∣}$ ∣ ∣ u =0 D$_{1}$ ( y ) dy + O ( u $^{2}$) . (52) Now, for the first term in (52), note that using the definition of D$_{1}$ ( y ) in (16), we have 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