text: This paper concerns the distributed training of nonlinear kernel machines on Map-Reduce. We show that a re-formulation of Nystr "om approximation based solution which is solved using gradient based techniques is well suited for this, especially when it is necessary to work with a large number of basis points. The main advantages of this approach are: avoidance of computing the pseudo-inverse of the kernel sub-matrix corresponding to the basis points; simplicity and efficiency of the distributed part of the computations; and, friendliness to stage-wise addition of basis points. We implement the method using an AllReduce tree on Hadoop and demonstrate its value on a few large benchmark datasets.
  @cite_20: It is an extreme challenge to produce a nonlinear SVM classifier on very large scale data. In this paper we describe a novel P-packSVM algorithm that can solve the Support Vector Machine (SVM) optimization problem with an arbitrary kernel. This algorithm embraces the best known stochastic gradient descent method to optimize the primal objective, and has 1 ? dependency in complexity to obtain a solution of optimization error ?. The algorithm can be highly parallelized with a special packing strategy, and experiences sub-linear speed-up with hundreds of processors. We demonstrate that P-packSVM achieves accuracy sufficiently close to that of SVM-light, and overwhelms the state-of-the-art parallel SVM trainer PSVM in both accuracy and efficiency. As an illustration, our algorithm trains CCAT dataset with 800k samples in 13 minutes and 95 accuracy, while PSVM needs 5 hours but only has 92 accuracy. We at last demonstrate the capability of P-packSVM on 8 million training samples.
summary: P-packsvm @cite_20 uses primal stochastic gradient descent (SGD) applied in the kernel feature space. Training examples are partitioned into various nodes. The most expensive computation of an SGD iteration is the calculation of the output associated with a given example. This is done by passing the example to all nodes, locally computing the sub-outputs associated with the nodes and then using MPI AllReduce operation to get the summed output to all nodes. A packing strategy is used to do @math iterations together; since @math effort is involved, @math is kept small, say 100. P-packsvm is shown to work well on an MPI environment. On other distributed settings with communication overheads it can become slow due to the large number ( @math ) of iterations.