• Calendar

March 19, Tuesday
12:00 – 13:00

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. Joint work with Lee-Ad Gottlieb and Robert Krauthgamer