A Scalable Dual Approach to Semidefinite Metric Learning

Chunhua Shen, Junae Kim, Lei Wang

Distance metric learning plays an important role in many vision problems. Previous work of quadratic Mahalanobis metric learning usually needs to solve a semidefinite programming (SDP) problem. A standard interiorpoint SDP solver has a complexity of O(n^6.5) (with n the number of variables), and can only solve problems up to a few thousand variables. Since the number of variables is D(D + 1)/2 (D is the dimension of input data), this corresponds to a limit around D < 100. This high complexity hampers the application of metric learning to highdimensional problems. In this work, we propose a very efficient approach to this metric learning problem. We formulate a Lagrange dual approach which is much simpler to optimize, and we can solve much larger Mahalanobis metric learning problems. Roughly, the proposed approach has a time complexity of O(t · D^3) with t ≈ 20 ∼ 30 for most problems in our experiments. The proposed algorithm is scalable and easy to implement. Experiments on various datasets show its similar accuracy compared with state-ofthe- art. We also demonstrate that this idea may also be able to be applied to other SDP problems such as maximum variance unfolding.

Keywords: distance metric learning, dual approach, semidefinite programming


Status: published
Type: Conference Paper
Conference/location: IEEE Computer Vision and Pattern Recognition (CVPR) 2011
Conference URL:
Full text