Efficient Stochastic Optimization for Low-Rank Distance Metric Learning

No. 1: Thirty-First AAAI Conference On Artificial Intelligence

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 31

AAAI Technical Track: Heuristic Search and Optimization

Although distance metric learning has been successfully applied to many real-world applications, learning a distance metric from large-scale and high-dimensional data remains a challenging problem. Due to the PSD constraint, the computational complexity of previous algorithms per iteration is at least O(d2) where d is the dimensionality of the data.In this paper, we develop an efficient stochastic algorithm Êfor a class of distance metric learning problems with nuclear norm regularization, referred to as low-rank DML. By utilizing the low-rank structure of the intermediate solutions and stochastic gradients, the complexity of our algorithm has a linear dependence on the dimensionality d. The key idea is to maintain all the iterates Êin factorized representations Êand construct Êstochastic gradients that are low-rank. In this way, the projection onto the PSD cone can be implemented efficiently by incremental SVD. Experimental results on several data sets validate the effectiveness and efficiency of our method.

10.1609/aaai.v31i1.10649