Distributed Estimation, Information Loss and Exponential Families
Distributed learning of probabilistic models from multiple data repositories with minimum communication is increasingly important. We study a simple communication-efficient learning framework that first calculates the local maximum likelihood estimates (MLE) based on the data subsets, and then combines the local MLEs to achieve the best possible approximation to the global MLE given the whole dataset. We study this framework's statistical properties, showing that the efficiency loss compared to the global setting relates to how much the underlying distribution families deviate from full exponential families, drawing connection to the theory of information loss by Fisher, Rao and Efron. We show that the "full-exponential-family-ness" represents the lower bound of the error rate of arbitrary combinations of local MLEs, and is achieved by a KL-divergence-based combination method but not by a more common linear combination method. We also study the empirical properties of both methods, showing that the KL method significantly outperforms linear combination in practical settings with issues such as model misspecification, non-convexity, and heterogeneous data partitions.
The main message of this paper is: IF you want to perform density/parameter estimation for an exponential family by dividing the data then combining the locally optimal estimators,  THEN use KL as the combining function BECAUSE  1) if the distribution is a full exponential family then you get the globally optimal solution and 2) if the distribution is a curved exponential family then this the best you can do. The rest of the paper proves these results and showed some empirically evidence on toy datasets.The main message of this paper is theoretical however it still didn't answer a few questions:1- Why do I have to follow the divide and combine approach?  Granted KL is the best if this is all what I can do, but what if I can use asynchronous techniques (or synchronous algorithms) to perform distributed inference? what are the trade-offs?2- At least I would have liked to see point 1 addressed experimentally. 3-  It would be great to link the results in this paper with the following paper:Parallelized Stochastic Gradient Descenthttp://martin.zinkevich.org/publications/nips2010.pdfIt addresses the same setup from an optimization point of view and showed the optimality of the linear averaging method under certain conditions.  Can you relate these two views? Take for instance logistic regression that is also a member of the exponential family, what can you say here?4 - From a practical point of view, even using the method in the paper cited above, there is still a gap between theory and practice. From a hands-on experience on very large dataset (that is hundreds of millions of examples and tens of millions of features), performing divide and combine (via linear average) in a simple SGD setting for even linear/logistic regression results in a solution that is equivalent to the global solution over  5-15% less data (i.e. there is a loss of information). It is not clear to me if this is because of the linear averaging or something more sophisticated can be said using the KL method instead.5 - I understand that this is a theory paper but the experimental section could be stronger. What happens when you vary the number of features, number of groups, Number of model parameters (# of mixtures)?- please mention in the paper under what family (curved or full) is the mixture of Gaussian example?