You may want to look at the paper: "P-packSVM: Parallel Primal grAdient desCent Kernel SVM" from ICDM 2009. It presents an extension of Pegasos to non-linear ke

You may want to look at the paper: "P-packSVM: Parallel Primal grAdient desCent Kernel SVM" from ICDM 2009. It presents an extension of Pegasos to non-linear kernels. Evaluating the pairwise kernels <x_i,x_j> and continuously updating the estimate of the norm of the implicit weight vector w seem to be the main hurdles to achieving the performance gains seen with linear kernels. The key takeaway from the paper (for me) was that the computation time on a single processor was not significantly better than that of the standard implementation provided by SVM-Light. However, with a variety of tricks permitted by the use of an SGD/Pegasos-like method, the authors were able to get significant speedup when using a compute cluster, allowing a good reduction in computation times (e.g. ~200x reduction on 512 processors).