Reverse engineering a distance metric from the output of a k-NN Suppose that someone has trained a nearest-neighbor algorithm based on some unknown metric. I have a large dataset of $N$ observations and $P$ features. For each observation, I am given $K$ indices corresponding to the $K$ "nearest" points in the (same) dataset.

What is the general type of strategy to learn this metric? Does this type of problem have a standard name? Are there any Kaggle-type competitions with such a task, or is this unusual?
Interesting question. If you supposed that the distance metric was some common one, of course you could just try all the common ones and see what is consistent with the nearest neighbors it returns. 

I can't think of a way to learn this reliably, because you don't have any info about the actual distances. Maybe treat all nearest-neighbor pairs as having 'small' distance and the rest 'large' and training a deep model that tries to learn to predict it across pairs of points. Whatever it comes up with as a metric would approximate it.