Sublinear Optimization

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’ll describe information-theoretic lower bounds that show our running times to be nearly best possible in the unit-cost RAM model.