Reviews: Learning Nearest Neighbor Graphs from Noisy Distance Samples

This paper defines a new learning problem of learning 1-NN graph on a metric space consisting of n points using a noisy distance oracle. Ignoring the metric structure, the problem can be viewed n separate best arm identification problems (for each node find its nearest neighbor by calling the oracle). The best arm identification problem can solved by UCB-like methods that maintain confidence intervals for each distance and has been studied extensively in the literature. The paper proposes an improved algorithm that exploits the triangle inequality and symmetry of the underlying metric in order to improve the confidence intervals. As the paper shows that the improvement doesn't help much for the worst-case metric space.