A Directed Isoperimetric Inequality with application to Bregman Near Neighbor Lower Bounds

Abstract

Bregman divergences are important distance measures that are used in applications such as computer vision, text mining, and speech processing, and are a focus of interest in machine learning due to their information-theoretic properties. There has been extensive study of algorithms for clustering and near neighbor search with respect to these divergences. In all cases, the guarantees depend not just on the data size n and dimensionality d, but also on a structure constant μ ≥ 1 that depends solely on a generating convex function φ and can grow without bound independently. In general, this μ parametrizes the degree to which a given divergence is "asymmetric". In this paper, we provide the first evidence that this dependence on μ might be intrinsic. We focus on the problem of ac{ann} search for Bregman divergences. We show that under the cell probe model, any non-adaptive data structure (like locality-sensitive hashing) for c-approximate near-neighbor search that admits r probes must use space Ω(dn1 + μ/c r). In contrast for LSH under l1 the best bound is Ω(dn1+ 1/cr).