Abstract

Traditional distance metric learning with side information usually formulates the objectives using the covariance matrices of the data point pairs in the two constraint sets of must-links and cannotlinks. Because the covariance matrix computes the sum of the squared -norm distances, it is prone to both outlier samples and outlier features. To develop a robust distance metric learning method, we propose a new objective for distance metric learning using the -norm distances. The resulted objective is challenging to solve, because it simultaneously minimizes and maximizes (minmax) a number of non-smooth -norm terms. As an important theoretical contribution of this paper, we systematically derive an efficient iterative algorithm to solve the general -norm minmax problem. We performed extensive empirical evaluations, where our new distance metric learning method outperforms related state-of-the-art methods in a variety of experimental settings.