March 20th, Wednesday 14:30, Room 303, Jacobs Building ** NOTICE UNUSUAL HOUR **
Title: Nearest Neighbors: Old and New
Lecturer: Arye Kontorovich
Lecturer homepage
: http://www.cs.bgu.ac.il/~karyeh/
Affiliation : Computer Science Department, Beg-Gurion University
We offer a new perspective on the nearest neighbor classifier, which
yields tighter risk asymptotics than the classic Cover-Hart analysis.
As a by-product, our analysis suggests a natural solution to the
problem of noisy labels/outliers. Our result holds in doubling metric
spaces, of which Euclidean spaces are a special case. The classifier
may be learned in linear time and evaluated on new points in
logarithmic time via approximate nearest neighbors.
Time permitting, we'll discuss recent results on metric dimensionality
reduction as well.