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.