Mini-Batch Primal and Dual Methods for SVMs
This work addresses optimization efficiency for SVMs, but it appears incremental as it focuses on mini-batch variants of existing methods.
The paper tackles the problem of using mini-batches for stochastic optimization in SVMs, showing that the spectral norm of the data controls parallelization speedup for both primal SGD and dual SDCA methods, and derives novel mini-batched SDCA variants with guarantees based on the nonsmooth hinge-loss primal problem.
We address the issue of using mini-batches in stochastic optimization of SVMs. We show that the same quantity, the spectral norm of the data, controls the parallelization speedup obtained for both primal stochastic subgradient descent (SGD) and stochastic dual coordinate ascent (SCDA) methods and use it to derive novel variants of mini-batched SDCA. Our guarantees for both methods are expressed in terms of the original nonsmooth primal problem based on the hinge-loss.