A Communication-Efficient Parallel Algorithm for Decision Tree
Decision tree (and its extensions such as Gradient Boosting Decision Trees and Random Forest) is a widely used machine learning algorithm, due to its practical effectiveness and model interpretability. With the emergence of big data, there is an increasing need to parallelize the training process of decision tree. However, most existing attempts along this line suffer from high communication costs. In this paper, we propose a new algorithm, called Parallel Voting Decision Tree (PV-Tree), to tackle this challenge. After partitioning the training data onto a number of (e.g., M ) machines, this algorithm performs both local voting and global voting in each iteration. For local voting, the top-k attributes are selected from each machine according to its local data. Then, globally top-2k attributes are determined by a majority voting among these local candidates. Finally, the full-grained histograms of the globally top-2k attributes are collected from local machines in order to identify the best (most informative) attribute and its split point. PV-Tree can achieve a very low communication cost (independent of the total number of attributes) and thus can scale out very well. Furthermore, theoretical analysis shows that this algorithm can learn a near optimal decision tree, since it can find the best attribute with a large probability. Our experiments on real-world datasets show that PV-Tree significantly outperforms the existing parallel decision tree algorithms in the trade-off between accuracy and efficiency.
This paper proposes a new parallel algorithm for training decision trees (for classification or regression). The main idea of this algorithm is to distribute the data on different nodes and then at each node, to identify the top-k splits on each data subset, determine globally to top-2k splits by voting individual top-k lists and then identify the best ones among them by combining histograms from individual workers. A theoretical analysis is performed that gives a lower bound on the probability to find the globally optimal split depending on the main method parameters. Several experiments are conducted on two large-scale datasets, where PV-tree are shown to outperform other parallel decision tree implementation. 
Given the popularity of decision trees, proposing an efficient parallel implementation of this method is of course very relevant. The proposed parallelization is original with respect to existing methods and it should indeed lead to less communications than other methods. The theoretical analysis is sound and I like the discussion of the impact of the main problem and method parameters that follows from the lower bound provided in theorem 4.1. Experiments are conducted on two very large problems, where, in the limit of the tested settings (see below), PV-tree is clearly shown to outperform other parallel implementations, in terms of both computing times to reach a given accuracy level and communication costs.  I nevertheless have two major concerns with the proposed parallelization. First, given the way it works, the performance of the algorithm is clearly affected by the number of workers and this number thus needs to be tuned for optimal performance. This is a serious drawback as It means that the algorithm can not benefit from large number of workers. From my understanding, this problem is not shared by other parallelizations. Using more machines with these methods might not always give significant improvement in terms of computing times but at least, it will not deteriorate predictive performance. While the experiments show the impact of the number of workers on PV-trees, the impact on other methods should be also studied in comparison. Experiments should show if PV-tree is still the best method on LTR (resp. CTR) when the number of machines grows (far) beyond 8 (resp. 32) machines.  Second, I'm also puzzled by this statement from the authors in Section 5.2.1 (and similar statements are given in Section 4):  "Only when the entire training data are huge (and thus distribution of the training data on each local machine can be similar to that of the entire training data), the full power of PV-Tree can be realized."  If this is indeed true, then I'm wondering why it's actually needed to distribute the data over different machines and why just selecting the best split over a single random subset of N/M examples at each node is not enough. (Or similarly is the tree built using PV-tree really better than a tree grown using only the subset of data available at one of the worker?) Indeed, if the distribution of the training data on each local machine is assumed, for the method to work, to be similar to that of the entire data, then the local top-k splits are expected to be the same as the global top-k splits and there is no need to vote over several workers. I think that this should be checked in the experiments. Do we really need to vote over several workers or is one worker not actually enough, in the conditions (in terms of the number of workers) where PV-tree works best?  The paper is very pleasant to read. Several important details are however missing in the textual description of the algorithms and in the pseudocodes. Some points that need to be clarified are as follows: - How are PV-tree and the competitors implemented? (language, framework, etc) - The pseudocode does not clearly indicate how and when the data is distributed. At each node or only once globally? What about other methods? What is included in their communication cost? - I don’t find the pseudo-codes very clear, probably because of the use of an object oriented formalism. Most functions/methods are not defined and it’s not always easy to guess what they are doing from their names. I think it could be improved. - Which information is contained in the histograms, in particular in the case of continuous attributes? How is this information merged between workers to yield the global histogram and how is the split threshold determined from this histogram? I don't have a clear idea of what kind of information is actually communicated between the machines. - Is the global split found using the call ‘globalHistograms.FindBestSplit()’ at the end of Algorithm 3 exactly the same as the split that would have been obtained with all available data (assuming the optimal variable is among the 2k selected ones).