Efficient distance metric learning by adaptive sampling and mini-batch stochastic gradient descent (SGD)

DOI10.1007/S10994-014-5456-XMaRDI QIDQ493732zbMATH OpenOpenAlexFDO

Authors Qi Qian, Rong Jin, Jinfeng Yi, Shenghuo Zhu, Lijun Zhang

Publication date 4 September 2015

Published in Machine Learning (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1304.1192

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Sampling theory, sample surveys (62D05)

Abstract: Distance metric learning (DML) is an important task that has found applications in many domains. The high computational cost of DML arises from the large number of variables to be determined and the constraint that a distance metric has to be a positive semi-definite (PSD) matrix. Although stochastic gradient descent (SGD) has been successfully applied to improve the efficiency of DML, it can still be computationally expensive because in order to ensure that the solution is a PSD matrix, it has to, at every iteration, project the updated distance metric onto the PSD cone, an expensive operation. We address this challenge by developing two strategies within SGD, i.e. mini-batch and adaptive sampling, to effectively reduce the number of updates (i.e., projections onto the PSD cone) in SGD. We also develop hybrid approaches that combine the strength of adaptive sampling with that of mini-batch online learning techniques to further improve the computational efficiency of SGD for DML. We prove the theoretical guarantees for both adaptive sampling and mini-batch based approaches for DML. We also conduct an extensive empirical study to verify the effectiveness of the proposed algorithms for DML.

Recommendations

• Fast generalization rates for distance metric learning. Improved theoretical analysis for smooth strongly convex distance metric learning
• Adaptive sampling for incremental optimization using stochastic gradient descent
• An efficient method for clustered multi-metric learning
• Survey on distance metric learning and dimensionality reduction in data mining
• Positive semidefinite metric learning using boosting-like algorithms

Cites work

• scientific article; zbMATH DE number 1869443 (Why is no real title available?)
• scientific article; zbMATH DE number 2107836 (Why is no real title available?)
• Distance metric learning for large margin nearest neighbor classification
• Large scale online learning of image similarity through ranking
• Online submodular minimization
• Prediction, Learning, and Games

Cited in

(3)

• Safe triplet screening for distance metric learning
• A fast diagonal distance metric learning approach for large-scale datasets
• Fast generalization rates for distance metric learning. Improved theoretical analysis for smooth strongly convex distance metric learning

Describes a project that uses

Uses Software

• LMNN
• LIBSVM
• UCI

This page was built for publication: Efficient distance metric learning by adaptive sampling and mini-batch stochastic gradient descent (SGD)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q493732)