I wanted to know how gradient descent can be used to minimize the distance function in approximate k nearest neighbor algorithm as mentioned in paper "Efficient K-Nearest Neighbor Graph Construction for Generic Similarity Measures" by Dong et al. where the author says "The approximate K-NNG can be viewed as K × N functions, each being the distance between one of the N objects and its k-th NN. The algorithm is simply to simultaneously minimize these K × N functions with the gradient descent method, hence the name “NN-descent”. https://www.cs.princeton.edu/cass/papers/www11.pdf

Like is there some regression formula or thing based on weights associated with neighbors closer to query that can be used to describe gradient descent in this case


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.