Locality-Sensitive Hashing for f-Divergences: Mutual Information Loss and Beyond

Lin Chen, Hossein Esfandiari, Gang Fu, Vahab S. Mirrokni

In modern data science, items are frequently represented as probability distributions—for instance, a document as a distribution over topics, or a user as a distribution over watched videos. To find "similar" items in these contexts, practitioners rely on information-theoretic distance measures like Jensen-Shannon (JS) divergence or Mutual Information Loss (MIL).

While standard techniques like Locality-Sensitive Hashing (LSH) excel at accelerating searches for simple Euclidean ($L^2$) distances, they struggle with these complex measures. Previous attempts to hash JS divergence were either data-dependent (requiring recalculation if the dataset changes) or lacked rigorous theoretical guarantees. This paper bridges the gap between information theory and efficient search by developing the first provably efficient, data-independent LSH schemes for $f$-divergences and Kreĭn kernels.

Two Paths to Efficient Hashing

The authors tackle the challenge of hashing complex probability distributions through two distinct mathematical frameworks: an approximation path and a lossless path.

1. The Approximation Path for $f$-Divergences

The authors propose a simple but powerful reduction tool for $f$-divergences. They demonstrate that if a complex divergence (like Generalized JS) can be approximated using a "hashable" distance (like the squared Hellinger distance), it can inherit the LSH properties of that simpler distance.

The core insight—termed the Hellinger Bridge—is the proof that the squared Hellinger distance is essentially half of the $L^2$ distance between the square roots of the probability vectors. Because $L^2$ hashing is well-understood, the authors can hash $f$-divergences by simply taking the square root of the data and applying standard Gaussian random projections.

Upper and lower bounds for the Generalized JS divergence approximation across weight parameter lambda.

This provides a tight, two-sided approximation result showing that Generalized JS divergence is bounded by the squared Hellinger distance. For JS divergence, the approximation factor is shown to be at least 0.69, and for triangular discrimination, it is at least 0.5.

2. The Lossless Path for Kreĭn Kernels

A Kreĭn kernel is a function that can be expressed as the difference between two positive definite kernels ($K = K_1 - K_2$). The authors develop a general method to reduce any Kreĭn kernel search to a Maximum Inner Product Search (MIPS).

By using explicit feature maps, they transform the data into a space where the kernel value corresponds to a simple dot product. Unlike the $f$-divergence approach, this reduction is theoretically "lossless." Crucially, the authors prove that Mutual Information Loss (MIL)—a vital metric for model compression and feature clustering—is a Kreĭn kernel, allowing it to be hashed efficiently for the first time.

Empirical Validation and Key Results

The authors evaluated their algorithms on several standard machine learning benchmarks, treating the data as probability distributions (e.g., Reuters-21578 for topic distributions, and $L^1$-normalized MNIST/CIFAR-10 images).

  • Data Independence: Unlike prior work requiring Singular Value Decomposition (SVD) on the entire dataset, these new methods are data-independent. Hash functions can be generated without prior knowledge of the data points, vastly improving scalability.
  • Empirical Speedup: On the Fashion MNIST dataset, the proposed LSH scheme achieved a 10x to 12x speedup over brute-force search while maintaining high precision (the fraction of true nearest neighbors correctly retrieved).
  • Robustness: The performance of the Generalized JS hashing remained stable across different values of the weight parameter $\lambda$, proving the method's versatility across various applications.

Limitations and Future Directions

While these methods represent a significant leap forward, the authors note a few limitations. In the Kreĭn-LSH section, they acknowledge a known issue in MIPS reductions: adding a "norm-balancing" term can sometimes dominate the distance, potentially degrading LSH performance. They suggest using "norm-ranging" (partitioning data by its length) to mitigate this effect.

Additionally, while the Kreĭn kernel approach is lossless, the $f$-divergence approach remains an approximation. Future research may investigate whether lossless transforms exist for a broader range of $f$-divergences, and how to better handle extremely sparse distributions that might challenge the random projection step.

Summary updated

Abstract

Computing approximate nearest neighbors in high dimensional spaces is a central problem in large-scale data mining with a wide range of applications in machine learning and data science. A popular and effective technique in computing nearest neighbors approximately is the locality-sensitive hashing (LSH) scheme. In this paper, we aim to develop LSH schemes for distance functions that measure the distance between two probability distributions, particularly for f-divergences as well as a generalization to capture mutual information loss. First, we provide a general framework to design LHS schemes for f-divergence distance functions and develop LSH schemes for the generalized Jensen-Shannon divergence and triangular discrimination in this framework. We show a two-sided approximation result for approximation of the generalized Jensen-Shannon divergence by the Hellinger distance, which may be of independent interest. Next, we show a general method of reducing the problem of designing an LSH scheme for a Krein kernel (which can be expressed as the difference of two positive definite kernels) to the problem of maximum inner product search. We exemplify this method by applying it to the mutual information loss, due to its several important applications such as model compression.
BibTeX
@inproceedings{chen2019locality,
  author = {Lin Chen and Hossein Esfandiari and Gang Fu and Vahab S. Mirrokni},
  title = {{Locality-Sensitive Hashing for f-Divergences: Mutual Information Loss and Beyond}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
}
Figure