Is the relative contrast theorem from Beyer et al. paper: "On the Surprising Behavior of Distance Metrics in High Dimensional Space" misleading?

Question

This is cited very often when mentioning the curse of dimensionality and goes

(righthand formula called relative contrast)

$$ \lim_{d\rightarrow \infty} \text{var} \left(\frac{||X_d||_k}{E[||X_d||_k]} \right) = 0, \text{then}: \frac{D_{\max^{k}_{d}} - D_{\min^{k}_{d}}}{D_{\min^{k}_{d}}} \rightarrow 0$$

The result of the theorem shows that the difference between the maximum and minimum distances to a given query point does not increase as fast as the nearest distance to any point in high dimensional space. This makes a proximity query meaningless and unstable because there is poor discrimination between the nearest and furthest neighbor.

link

Yet if one actually tries out calculating the relative contrast for sample values, meaning one takes a vector containing very small values and calculates the distance to the zero vector and does the same for a vector containing much larger values, and one then compares the values for a dimension of 3 and a dimension $10^9$ times bigger, one will see that, while the ratio does decrease, the change is so vanishingly small as to be irrelevant for the number of dimensions actually used in practice (or does anyone know anyone working with data with dimensions the size of Graham's number - which I would guess is the size needed for the effect described the paper to actually be relevant - I think not).

As previously mentioned, this theorem is very often cited to support the statement that measuring proximity based on euclidean space is a poor strategy in a high dimensional space, the authors say so themselves, and yet the proposed behaviour does not actually take place, making me think this theorem has been used in a misleading fashion.

Example: with d the dimension

a=np.ones((d,)) / 1e5
b=np.ones((d,)) * 1e5
dmin,dmax=norm(a), norm(b)
(dmax-dmin)/dmin

for d=3
9999999999.0
for d=1e8
9999999998.9996738

And with 1e1 instead of 1e5 (let's say the data is normalized)
for d=3
99.0
for d=1e8
98.999999999989527

Answer 1

No, the theorem is not misleading. It can certainly be applied incorrectly, but that's true for any theorem.

Here's simple MATLAB script to demonstrate how it works:

xd = randn(1e5,10000);
%%
cols = [1,10,100,1000,10000];
for c = cols
    xdt = table(xd(:,1:c));
    res = table2array(rowfun(@norm,xdt));
    mr = mean(res);
    res1 = var(res/mr);
    res2 = (max(res) - min(res))/min(res);
    fprintf('res1: %f, res2: %f\n',res1,res2)
end

The OUTPUT:

res1: 0.568701, res2: 2562257.458668
res1: 0.051314, res2: 9.580602
res1: 0.005021, res2: 0.911065
res1: 0.000504, res2: 0.221981
res1: 0.000050, res2: 0.063720

In my code res1 and res2 are the two expressions in your equation from the paper: one for variance, and the second one for the contrast.

You can see how both go to zero as supposed to when dimensions go from 1 to 10,000.

Answer 2

First, the name of the paper is wrong in your question: you meant this paper by Beyer et al where the theorem was originally introduced, and not this paper by Aggarwal et al, which you wrongly named in your OP and was written after the paper by Beyer et. al.

Next, what do you mean by "misleading"? It'd be misleading if:

1. There existed a counterexample to this theorem by Beyer et al, and that's not possible since the proof in the first paper by them is correct. I see in the comments that people are asking for a concrete example, which is below.

2. To quote you "this theorem is very often cited to support the statement that measuring proximity based on euclidean space is a poor strategy in a high dimensional space, the authors say so themselves, and yet the proposed behaviour does not actually take place, making me think this theorem has been used in a misleading fashion." Again, the bahavio(u)r does occur in high dimensions, as shown in the family of examples below: the key element is to have iid features/components of the random variable generating the iid random samples.

A family of examples that satisfies the hypothesis of the theorem by Beyer et. al. (relative variance $Var\left[\frac{||X^{(d)}||}{\mathbb{E}||X^{(d)}||}\right]$" goes to zero) and hence the statement also holds (relative contrast goes to zero), is given in this paper "Concentration of Fractional Distances (Wertz. et. al.)", which basically states that (see its Theorem 5, P. 878)

Theorem 5: If $X^{(d)}=(X_1 \dots X_d) \in \mathbb{R}^d$ is a $d$ -dimensional random vector with iid components, then $\frac{||X^{(d)}||}{\mathbb{E}||X^{(d)}||} \to_{p}1 \iff Var\left[\frac{||X^{(d)}||}{\mathbb{E}||X^{(d)}||}\right] \to 0, d \to \infty.$

So this means that if your generated iid random sample by using a random vector whose components are iid (e.g. a normal $\mathcal{N}(0, I_d)$ random vector), then its "relative variance $Var\left[\frac{||X^{(d)}||}{\mathbb{E}||X^{(d)}||}\right]$" will go to zero, and hence by Beyer's theorem the maximum norm (=distance to the query point as the origin) divided by minimum norm (=distance to the query point as origin) will converge in probability to $1,$ or equivalently the "relative contrast" (i.e. the ratio of the distances between the farthest and nearest point to the origin, minus one) wil go to zero as well.

P.S. for application-minded people, you're welcome to take a look at my relevant question here, seeking practical applications of these theorems.