[Ml-stat-talks] Wed: Aryeh Kontorovich on learning in metric spaces

David Mimno mimno at CS.Princeton.EDU
Sun Oct 2 21:04:04 EDT 2011


This Wednesday we will have Aryeh Kontorovich from Ben Gurion
University of the Negev.
The talk will be at 12:30 in CS402. These talks are always interesting, but
this week I am particularly looking forward to learning more about the
"fat-shattering dimension"!

Title:

Learning in Metric Spaces: Classification, Regression, Anomaly Detection

Abstract:

Using Lipschitz extensions for classification in metric spaces was
apparently first proposed by von Luxburg and Bousquet (2004), who also
noted that algorithmically, the solution can be realized as a
nearest-neighbor search. In a COLT 2010 paper, we showed how to
exploit the intrinsic geometry of the metric space to construct highly
efficient classifiers and to derive data-dependent generalization
bounds. We employed the doubling dimension on two fronts:
information-theoretically, to control the fat-shattering dimension of
Lipschitz functions (which yields error estimates), and
algorithmically, to perform approximate nearest-neighbor search
exponentially faster than the exact one. Since then, we have extended
this technique to regression and anomaly detection. The talk, intended
for a broad audience, will present an overview of our recent results,
obtained in collaboration with: Daniel Berend, Lee-Ad Gottlieb, Danny
Hendler, Eitan Menahem, Robert Krauthgamer.


More information about the Ml-stat-talks mailing list