Dual SVM Training on a Budget

Support Vector Machines (SVMs) introduced by [5] are popular machine learning methods, in particular for binary classification. They are supported by learning-theoretical guarantees [14], and they exhibit excellent generalization performance in many applications in science and technology [1, 16, 29, 23, 22, 3, 18, 19, 10]. They belong to the family of kernel methods, applying a linear algorithm in a feature space defined implicitly by a kernel function. Training an SVM corresponds to solving a large-scale optimization problem, which can be cast into a quadratic program (QP). The primal problem can be solved directly with stochastic gradient descent (SGD) and accelerated variants [21, 8], while the dual QP is solved with subspace ascent, see [2] and references therein.