  We present a dual subspace ascent algorithm for support vector machine
training that respects a budget constraint limiting the number of support
vectors. Budget methods are effective for reducing the training time of kernel
SVM while retaining high accuracy. To date, budget training is available only
for primal (SGD-based) solvers. Dual subspace ascent methods like sequential
minimal optimization are attractive for their good adaptation to the problem
structure, their fast convergence rate, and their practical speed. By
incorporating a budget constraint into a dual algorithm, our method enjoys the
best of both worlds. We demonstrate considerable speed-ups over primal budget
training methods.
