IBM Almaden Research Center

Title:

Coordinate Sampling for Sublinear Optimization and Nearest Neighbor Search

Abstract:

I will describe randomized approximation algorithms for some classical problems of machine learning, where the algorithms have provable bounds that hold with high probability. Some of our algorithms are sublinear, that is, they do not need to touch all the data. Specifically, for a set of points a_1...a_n in d dimensions, we show that finding a d-vector x that approximately maximizes the
margin min_i a_i dot x can be done in O(n+d)/epsilon^2 time, up to logarithmic factors, where epsilon>0 is an additive approximation parameter. This was joint work with Elad Hazan and David Woodruff.

A key step in these algorithms is the use of coordinate sampling to estimate dot products. This simple technique can be an effective alternative to random projection sketching in some settings. I will discuss the potential of coordinate sampling for speeding up some data structures for nearest neighbor searching in the Euclidean setting, via fast approximate distance evaluations.

Bio:

Ken Clarkson is manager of the Computer Science Principles and Methodologies department at IBM Research, Almaden (in San Jose, CA). His work has mostly been on geometric algorithms, in particular on the use of randomization, for such problems as linear programming, nearest neighbor search in metric spaces, simple polygon triangulation, building compressed quadtrees, and computing convex hulls.

 ~~~~~~~~~~~~~~~~~~~~~~

To receive future announcements, please sign up to the cse-seminar email list:

https://mailman.cc.gatech.edu/mailman/listinfo/cse-seminar