Campus Event Calendar
Event Entry
What and Who
Approximate Near Neighbor Search for Bregman Divergences
Suresh Venkatasubramanian
University of Utah
AG1 Mittagsseminar (own work)
AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Friday, 1 March 2013
13:30
30 Minutes
Warning: Time has changed!
Warning: Title has changed!
E1 4
024
Saarbrücken
Abstract
The Bregman divergences are a class of distance functions that generalize the Euclidean distance, the Kullback-Leibler divergence, and many other distances that appear naturally in statistics and machine learning. These distance functions also generalize projective duality and behave combinatorially very similar to Euclidean spaces.
However, they are not symmetric and lack a triangle inequality. This makes designing approximation algorithms for core questions like near neighbor search difficult. In this talk, I'll present the first provably approximate nearest-neighbor (ANN) algorithms for Bregman divergences. These process queries in O(log n) time for Bregman divergences in fixed dimensional spaces and can handle queries in pollywog time for a more abstract class of distance measures (containing Bregman divergences) which satisfy certain structural properties. Both of these bounds apply to both the regular asymmetric Bregman divergences as well as their symmetrized versions.
Joint work with Amirali Abdullah and John Moeller.
Contact
Parinya Chalermsook
--email hidden
passcode not visible
logged in users only
Parinya Chalermsook, 02/26/2013 17:03
Parinya Chalermsook, 02/19/2013 23:58
Parinya Chalermsook, 02/11/2013 18:25 -- Created document.
Parinya Chalermsook, 02/19/2013 23:58
Parinya Chalermsook, 02/11/2013 18:25 -- Created document.