[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"!


Learning in Metric Spaces: Classification, Regression, Anomaly Detection


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