Fast Bourgain embedding (or similar embeddings)?

Question

Currently I am working on applications of Bourgain Embedding (or similar embeddings of finite metric spaces to $l_2$) to automatic feature engineering for machine learning/data science ( http://www.orges-leka.de/automatic_feature_engineering.html, https://github.com/orgesleka/bourgain_embedding/blob/master/bourgain.py ). The method works quite well, but the only drawback is its runtime $O(N^2)$ where $N$ is the number of data points to be embedded. I have seen ( https://arxiv.org/abs/1805.07674 ) and it is a natural idea to chose $n < N$ random data points and to do the Bourgain embedding for those points. But the only proven preserved quantity is the distance distribution. My question is, if there is a way to speed up the Bourgain embedding while preserving the low distortion? This would be potentially useful for large datasets and I think it would have applications in data science / machine learning. Thanks for your help!

Answer 1

There is a way to speed-up Bourgain's embedding in case if the original metric space has low "intrinsic dimension". The resulting algorithm will have a theoretical runtime $O(CN\log^2(N))$, where $C$ is a constant depending only on "intrinsic dimension". And also will show speedups over the standard Bourgain's embedding varying between one and several orders of magnitude on natural machine learning datasets.

The idea is to use Nearest Neighbor search in metric spaces. When you construct the standard Bourgain Embedding you do the following. For each coordinate you fix a random subset $A$ of you metric space $X$. Then for each point $x \in X$ you compute $d(x,A)$ and this is the value of you coordinate. You need $O(|X||A|)$ operations to do this if you use the brute force method. If $|A| \approx |X| = n$ you have $O(n^2)$ just from this step. But let's do this in a sneaky way instead.

We will use [1] "Cover trees for nearest neighbor" by Beygelzimer, Alina, Sham Kakade, and John Langford. https://www.cc.gatech.edu/~isbell/reading/papers/cover-tree-icml.pdf

First we construct the "cover tree data structure" on $A$. Which can be done in $O(C|A|\log|A|)$ time. (All constants $C$ in this text are different constants not related to each other.) This data structure allows to compute nearest neighbors in $O(C\log|A|)$ time. Thus, computing all $n$ required distances will take $O(Cn\log|A|)$ operations.

Since we have $C\log(n)$ coordinates the runtime of the whole algorithm will be $O(CN\log^2(N))$. I assume that computations of $d(x,A)$ is the only computationally heavy part of Bouragin's Algorithm. Thus, we probably will have the same speed up on natural machine learning datasets as in "nearest neighbor via cover trees" vs brute force, see [1].

PS:I'm currently working on writing some kind of academic paper out of this observation. But struggling since I'm a mathematician and don't really know how to write CS papers. I implemented Beygelzimer-Kakade-Langford in Java. But now I'm not sure what to do next. It would be cool to write some kinda of package, maybe people will try to use it. But I'm so noob at coding. Probably I should choose the language wise and not stick with Java out of habit. Probably should use parallelization. Also I'am only familiar with CPU computations but I heard that practitioners mostly use GPU/TPU. So If you can give me an advice or want to collaborate with me please email me at [email protected].