Locality-Sensitive Hashing for f-Divergences: Mutual Information Loss and Beyond
This work addresses the need for efficient nearest neighbor search in high-dimensional spaces for machine learning applications like model compression, but it is incremental as it extends existing LSH methods to new distance functions.
The authors tackled the problem of designing locality-sensitive hashing (LSH) schemes for f-divergences and mutual information loss, providing a general framework and specific schemes for generalized Jensen-Shannon divergence and triangular discrimination, with a two-sided approximation result for the former.
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.