Snacks: a fast large-scale kernel SVM solver
This is an incremental improvement for researchers and practitioners needing faster kernel SVM training on large datasets.
The authors tackled the problem of kernel SVM's quadratic complexity limiting large-scale applications by proposing Snacks, a solver using Nyström approximation and accelerated stochastic subgradient method, which competes with other solvers on benchmark datasets.
Kernel methods provide a powerful framework for non parametric learning. They are based on kernel functions and allow learning in a rich functional space while applying linear statistical learning tools, such as Ridge Regression or Support Vector Machines. However, standard kernel methods suffer from a quadratic time and memory complexity in the number of data points and thus have limited applications in large-scale learning. In this paper, we propose Snacks, a new large-scale solver for Kernel Support Vector Machines. Specifically, Snacks relies on a Nyström approximation of the kernel matrix and an accelerated variant of the stochastic subgradient method. We demonstrate formally through a detailed empirical evaluation, that it competes with other SVM solvers on a variety of benchmark datasets.