Information-optimal optimization in machine learning
---------------------------------------------------------------------------
Linear classification is a fundamental problem of machine learning, in which
positive and negative examples of a concept are represented in Euclidean
space by their feature vectors, and we seek to find a hyperplane separating
the two classes of vectors. We give the first sublinear-time (information-optimal)
algorithms for linear classification, support vector machine training, and other
related problems in machine learning, including the kernelized versions of these
problems. These new algorithms are based on a primal-dual approach, and use
a combination of novel sampling techniques and the randomized implementation
of online learning algorithms. We give lower bounds which show our running
times to be nearly best possible in the unit-cost RAM model.
Joint work with Ken Clarkson and David Woodruff, appeared in FOCS 2010.