December 15, Wednesday 14:15, Room 303, Jacobs Building

Efficient Classification for Metric Data

Lecturer : Lee-Ad Gottlieb

Lecturer homepage : http://www.cs.nyu.edu/~adi/

Affiliation : The Hebrew University, Jerusalem, Israel

Recent advances in large-margin classification of data residing in general 
metric spaces (rather than Hilbert spaces) enable classification under 
various natural metrics, such as edit and earthmover distance. The general 
framework developed for this purpose by von Luxburg and Bousquet [JMLR, 
2004] left open the question of computational efficiency and providing 
direct bounds on classification error. We design a new algorithm for 
classification in general metric spaces, whose runtime and accuracy depend 
on the doubling dimension of the data points. It thus achieves superior 
classification performance in many common scenarios. The algorithmic core 
of our approach is an approximate (rather than exact) solution to the 
classical problems of Lipschitz extension and of Nearest Neighbor Search. 
The algorithms generalization performance is established via the 
fat-shattering dimension of Lipschitz classifiers.

This is joint work with Aryeh Kontorovich and Robert Krauthgamer.