Osamu Watanabe (Tokyo Institute of Technology, Japan):
Provably Fast Training Algorithms for Support Vector Machines
Support Vector Machines are a family of algorithms for the
analysis of data based on convex Quadratic Programming.
We focus on their use for classification, where the SVM
algorithms work by maximizing the margin of a classifying
hyperplane in a feature space. In this paper,
based on a variation of Random Sampling Techniques,
techniques successfully used for similar problems, we
derive a randomized algorithm for training SVMs and formally
prove an upper bound on the expected running time
which is quasilinear with respect to the number of data points.
To our knowledge, this is the first algorithm with a quasilinear
bound that can handle SVMs with kernels.
Joint work with J. Balcazar, Y. Dai, and J. Tanaka.