Efficient Large-Scale Distributed Training of Conditional Maximum Entropy Models

by Gideon Mann, Ryan McDonald, Mehryar Mohri, Nathan Silberman and Daniel D. Walker

This works might inspired the previous scanned paper, in that the proposed algorithm looks quite similar. This paper only focused on CME (a special case of convex optimization) and therefore the result is of comparatively limited usage in practice. The key difference of the two is this paper only employs a normal batch solver, unlike the stochastic solver in the latter.

This algorithm is map/reduce friendly, though.

Parallelized Stochastic Gradient Descent

by Martin A. Zinkevich, Markus Weimer, Alex Smola and Lihong Li

This paper talks about a very interesting optimization technique. In online learning, SGD (stochastic gradient descent) is usually applied to optimize the model, since the data come in one by one (or one mini batch by another). For parametric models, the parameters are updated with one or a few samples sequentially.

This paper talks about a parallelized version. Essentially we run several SGD on different machines and aggregate their result by averaging. However, we may even do not distribute all data across all machines. The proof of convergence looks dependent on the convexity of the objective functions but I suspect it may not.

The result is quite interesting when we consider about the popular parallel computation framework, map/reduce. We'd better implement one ASAP.

The Stochastic Gradient Boosted Distributed Decision Trees

by Jerry Ye, Jyh-Herng Chow, Jiang Chen and Zhaohui Zheng

This paper proposed two solutions forr implementing the exact stochastic GBDT, which was developed by the famous statician Friendman. I'd like to scan his two previous papers later as the first study of decision trees (others will be CART and C4.5... I guess).

The map/reduce implementation is based on the previously scanned paper, using horizontal splits while in the MPI implementation using vertical splits. The former is quite directly; the later requires communication using all-to-all broadcasting.

Maybe after studying the GBDT, I would have a better understanding of this paper.

A Framework for Learning from Dsitributed Data Using Sufficient Statistics and its Application to Learning Decision Trees

by Doina Caragea, Adrian Silvescu and Vasant Honavar

This paper addresses training a large-scale problem using two types of split of data: horizontal fragmentation (sample subsets) and vertical fragmentation (feature subsets). The orientation is determined when writing row-wise sample matrix.

The key idea behind this paper is to extract sufficient statistics from  splits of data so that we may aggregate the statistics in the last to get the exact model. This is quite direct in the case of MoE (when each  expert is an exponential family). This paper, however, has the emphasis in decision trees.

The decision trees are trained layer-wise, finding splits of data using features that maximized the information gain (or some similar criteria). The paper discussed two cases:

• if the data are horizontally splitted, each site compute the required statistics and they are all combine to find the best split; the split then is passed back to each site so that each site knows which node the samples are in and they could take a second collection of sufficient stats.
• if the data are vertically splitted, each site could figure out its own split and they will be compared and find the best; however, the split is then represented by the indices (so that each site may understand which samples are in which node);

This solution is accurate and can be applied to implementing the decision trees under map/reduce framework directly. And it should also apply to many hierarchical models too.