Supplementary Material A Proofs

This section provides the full proof of the theorems stated in the main paper. Specifically, for a "softened" sample We proceed to show the correctness of the backward pass. Therefore, the claim at the beginning of this paragraph holds. Plug in Eq. (14), we have context Finally, we note that Alg. 1 and 2 both run in time O ( |p| |D|). A.2 Useful Lemmas This section provides several useful lemmas that are later used in the proof of Thm. 4. Lemma 1. F ollowing this decomposition, we construct Alg. 4 that computes the entropy of every nodes in a Consider the example PC in Figure 1.