Contributions We propose a novel approach, LoOp, which finds optimal hard negatives in the embedding space,
and maximizes the contribution of each tuple in computing the pair-based metric learning loss. Our approach presents the solution to a general problem, namely finding the minimum distance between two bounded curves, which can be useful in other applications as well. Generating hard negatives in the embedding space, our approach utilizes all training samples and does not rely on a subset of samples like mining-based methods. It also avoids the computational load and training complexity introduced by generation-based methods. We also explore the optimality of LoOp with a gradient-based theoretical analysis of the loss function. Our approach generalizes well to various metric learning losses, and it can be easily combined without any increase in optimization difficulty or additional parameters. It outperforms state-of-the-art mining and generation-based methods on three benchmark datasets, Cars196 [1]}, CUB-200-2011 [2]}, and Stanford Online Products [3]}.
