Step #1: Nearest neighbor batch construction.
The way of constructing mini-batches for training has a massive impact on performance in metric learning [1]}, [2]}.
One of the most widely used methods for batch construction is the \(pk\) -sampling: It randomly chooses \(p\)  unique classes, and then randomly samples \(k\)  instances per class. Since this method leverages class labels of training data, it is however prohibited in an unsupervised learning setting. We instead propose a new strategy based on the nearest neighbor search.
For each mini-batch, it randomly samples \(q\)  queries and then searches for \(k-1\)  nearest neighbors of each query; including both queries and their nearest neighbors, the mini-batch becomes of size \(qk\) . Our strategy is simple, fast, yet allows mini-batches to include diverse and relevant samples.
