Many thanks for your efforts. If I understand your work correctly, I think your method to compute the distance will also be computationally expensive as it needs additionally to calculate the distance between a huge number of points $x$ in $X$ to their nearest neighbors in $Y$. Apart from this, I don't understand why it is obvious that $d(x,Y) \leq d(x,Y_1)$? if the random set $Y_1$ contains the closest values of $Y$ to $X$ then $d(x,Y) \geq d(x,Y_1)$! Am I missing something?

@MattF. So the most important and interesting is to find a known efficient method to find the nearest neighbor for all points in huge sets then I can work on the bound for the distance

@MattF. As you know, the distance above is used as a metric to compare the similarity between two sets in neural networks. Unfortunately, I can't compute it exactly because of the amount of points since it needs to to search for the closest neighbor in Y for each point in X and to do the same again for each point in Y. Consequently, I am looking in literature for efficient methods to find the nearest neighbor in order to use them and to bound the distances above.

@MattF. Thanks for your help and the edit. I wrote to bound in the original question because it is hard to compute the distance exactly and an algorithm should be used to approximate or bound the distance. Hope it is clear?