*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
Ken Clarkson
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
