  In this paper, we evaluate the performance of various parallel optimization
methods for Kernel Support Vector Machines on multicore CPUs and GPUs. In
particular, we provide the first comparison of algorithms with explicit and
implicit parallelization. Most existing parallel implementations for multi-core
or GPU architectures are based on explicit parallelization of Sequential
Minimal Optimization (SMO)---the programmers identified parallelizable
components and hand-parallelized them, specifically tuned for a particular
architecture. We compare these approaches with each other and with implicitly
parallelized algorithms---where the algorithm is expressed such that most of
the work is done within few iterations with large dense linear algebra
operations. These can be computed with highly-optimized libraries, that are
carefully parallelized for a large variety of parallel platforms. We highlight
the advantages and disadvantages of both approaches and compare them on various
benchmark data sets. We find an approximate implicitly parallel algorithm which
is surprisingly efficient, permits a much simpler implementation, and leads to
unprecedented speedups in SVM training.
