Large 00008

Sublinear Optimization

Elad Hazan

Recorded 13 June 2012 in Lausanne, Vaud, Switzerland

Event: SuRI - I&C - Summer Research Institute


In many modern optimization problems, specifically those arising in machine learning, the amount data is too large to apply standard convex optimization methods. We'll discuss new optimization algorithms that make use of randomization to prune the data produce a correct solution albeit running in time which is smaller than the data representation, i.e. sublinear running time. We'll present such sublinear-time algorithms for linear classification, support vector machine training, semi-definite programming and other optimization 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.

Watched 1077 times.