A directed isoperimetric inequality with application to Bregman near neighbor lower bounds

Amirali Abdullah, Suresh Venkatasubramanian

Bregman divergences $D_{\varphi }$ are a class of divergences parametrized by a convex function $\varphi$ and include well known distance functions like ${\ell }_2^2$ and the Kullback-Leibler diverg…