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.
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.
@cite_20
2139224857
We consider stochastic strongly convex optimization with a complex inequality constraint. This complex inequality constraint may lead to computationally expensive projections in algorithmic iterations of the stochastic gradient descent (SGD) methods. To reduce the computation costs pertaining to the projections, we propose an Epoch-Projection Stochastic Gradient Descent (Epro-SGD) method. The proposed Epro-SGD method consists of a sequence of epochs; it applies SGD to an augmented objective function at each iteration within the epoch, and then performs a projection at the end of each epoch. Given a strongly convex optimization and for a total number of @math iterations, Epro-SGD requires only @math projections, and meanwhile attains an optimal convergence rate of @math , both in expectation and with a high probability. To exploit the structure of the optimization problem, we propose a proximal variant of Epro-SGD, namely Epro-ORDA, based on the optimal regularized dual averaging method. We apply the proposed methods on real-world applications; the empirical results demonstrate the effectiveness of our methods. We propose a new distributed algorithm based on alternating direction method of multipliers (ADMM) to minimize sum of locally known convex functions using communication over a network. This optimization problem emerges in many applications in distributed machine learning and statistical estimation. Our algorithm allows for a general choice of the communication weight matrix, which is used to combine the iterates at different nodes. We show that when functions are convex, both the objective function values and the feasibility violation converge with rate @math , where @math is the number of iterations. We then show that when functions are strongly convex and have Lipschitz continuous gradients, the sequence generated by our algorithm converges linearly to the optimal solution. In particular, an @math -optimal solution can be computed with @math iterations, where @math is the condition number of the problem. Our analysis highlights the effect of network and communication weights on the convergence rate through degrees of the nodes, the smallest nonzero eigenvalue, and operator norm of the communication matrix. We study fault-tolerant distributed optimization of a sum of convex (cost) functions with real-valued scalar input output in the presence of crash faults or Byzantine faults. In particular, the goal is to optimize a global cost function @math , where @math is the collection of agents, and @math is agent @math 's local cost function, which is initially known only to agent @math . Since the above global cost function cannot be optimized exactly in presence of crash faults or Byzantine faults, we define two weaker versions of the problem for crash faults and Byzantine faults, respectively. When some agents may crash, the goal for the weaker problem is to generate an output that is an optimum of a function formed as @math where @math is the set of non-faulty agents, @math is the set of faulty agents (crashed agents), @math for each @math and @math is a normalization constant such that @math . We present an iterative algorithm in which each agent only needs to perform local computation, and send one message per iteration. When some agents may be Byzantine, the system cannot take full advantage of the data kept by non-faulty agents. The goal for the associated weaker problem is to generate an output that is an optimum of a function formed as @math such that @math for each @math and @math . We present an iterative algorithm, where only local computation is needed and only one message per agent is sent in each iteration, that ensures that at least @math agents have weights ( @math 's) that are lower bounded by @math . 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.