Distributed Parameter Estimation in Probabilistic Graphical Models
This paper presents foundational theoretical results on distributed parameter estimation for undirected probabilistic graphical models. It introduces a general condition on composite likelihood decompositions of these models which guarantees the global consistency of distributed estimators, provided the local estimators are consistent.
Paper Summary:--------------The paper focuses on the problem of distributed parameter estimation in MRFs through the use of a composite likelihood function. The authors identify a class of composite likelihood functions for which one can learn the parameters of an MRF in a fully-parallel but globally consistent manner. The authors introduce the Strong LAP Condition characterizing the graph structure of an MRF and show that if the auxiliary MRF A_q corresponding to a clique for interest q satisfies the Strong LAP condition then globally consistent estimates of the parameters corresponding to A_q can be computed locally. This new condition on the structure of the MRF allows the authors to tie together two prior approaches by Liu et al, and Mizrahi et al. for distributed parameter estimation. Moreover, the conditional LAP formulation extends the original LAP algorithm to densely connected graphs. High-level comments:-------------------The paper studies the important problem of distributed parameter estimation in PGMs. I think the techniques put forward in this paper provide an interesting theoretical basis for characterizing families of networks that are amenable to efficient distributed learning and inference algorithms with consistency guarantees. The technical development is sound and the corresponding definitions, prepositions and theorems are clearly stated. The paper presents some novel ideas as it extends prior work on LAP. More precisely, prior work was using marginal distributions to estimate network parameters, thus, evaluating the partition function, while the current framework shows how parameter estimates can be derived using conditional distributions, and hence, avoiding the computation of the partition function. Finally, the proposed framework unifies two different models previously proposed. However, the discussion on the differences between LAP and Strong LAP should be improved. Detailed comments on this can be found in the weak points below. Detailed comments:-------------------1) Strong points:(a) Interesting formulations and sound theoretical analysis. (b) Unifying framework over two different lines of work. To some extend this work completes is a complement to previous work by Liu et al. by providing the necessary conditions under which the assumptions of Liu et al. hold.(c) The theoretical framework was used to derive efficient localized parameter estimators. It will be very interesting how these techniques apply to real data, and how they compare with LAP under instances where LAP is also efficient. 2) Weak points:(a) The comparison between LAP and strong LAP should be improved. Now, Theorem 9 and Proposition 2 seem to state the same thing. Notice that the way they are stated Theorem 9 includes Proposition 2, i.e., normalized potentials and identifiable parameters. So either Theorem 9 or Proposition 2 should be restated as there is no difference between them. In fact theorem 9 seems to be trying to draw a connection between preposition 8 and the previously stated LAP condition but this is done without success. (b)The discussion in the intro should be extended to give a high-level description of why the Strong LAP condition leads to a more efficient estimator. In fact the reason is the computation of conditional versus marginal distributions. Also, section 5 should be extended with examples. Figure 1 is there but no mention of it is included in section 5.(c) The statement about the complexity of LAP being exponential in the number of cliques (the same for the centralized estimators) should be that it is exponential in the number of network variables since computing the partition function enumerates all possible assignments of values to these variables. So basically exponential in the clique size but not the number of cliques.  (d) Typos: Some minor typos Page 1, line 034 allows us transfer -> allows us to tranfer Page 1, line 039 lead -> led Page 1, line 040 factorization - > factorization Page 2, line 086 i.e. -> i.e.,  Page 3, line 160 i.e. that -> i.e., (without that) Page 3, line 143 optimising - > optimizing Page 3, line 149 optimisation -> optimization