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

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 mu >= 1 that depends solely on a generating convex function phi and can grow without bound independently. In general, this mu parametrizes the degree to which a given divergence is "asymmetric". In this paper, we provide the first evidence that this dependence on mu might be intrinsic. We focus on the problem of approximate nearest neighbor (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 Omega(dn(1+mu/cr)) In contrast for LSH under l(1) the best bound is Omega(dn(1+1/cr)). Our results interpolate between known lower bounds both for LSH-based ANN under l(1) as well as the generally harder partial match (Partial Match) problem (in non-adaptive settings). The bounds match the former when mu is small and the latter when mu is Omega(d/log n). This further strengthens the intuition that Partial Match corresponds to an "asymmetric" version of ANN, as well as opening up the possibility of a new line of attack for lower bounds on Partial Match. Our new tool is a directed variant of the standard boolean noise operator. We prove a generalization of the BonamiBeckner hypercontractivity inequality (restricted to certain subsets of the Hamming cube), and use this to prove the desired directed isoperimetric inequality that we use in our data structure lower bound.