caa a22 4500 605478473 CHVBK 20210128100405.0 cr unu---uuuuu 210128e20150601xx s 000 0 eng 10.1007/s10994-014-5456-x doi (NATIONALLICENCE)springer-10.1007/s10994-014-5456-x Efficient distance metric learning by adaptive sampling and mini-batch stochastic gradient descent (SGD) [Elektronische Daten] [Qi Qian, Rong Jin, Jinfeng Yi, Lijun Zhang, Shenghuo Zhu] 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 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. The Author(s), 2014 Loss Function nationallicence Hybrid Approach nationallicence Adaptive Sampling nationallicence Pairwise Constraint nationallicence Stochastic Gradient Descent nationallicence Qian Qi Department of Computer Science and Engineering, Michigan State University, 48824, East Lansing, MI, USA aut Jin Rong Department of Computer Science and Engineering, Michigan State University, 48824, East Lansing, MI, USA aut Yi Jinfeng Department of Computer Science and Engineering, Michigan State University, 48824, East Lansing, MI, USA aut Zhang Lijun Department of Computer Science and Engineering, Michigan State University, 48824, East Lansing, MI, USA aut Zhu Shenghuo NEC Laboratories America, 95014, Cupertino, CA, USA aut Machine Learning Springer US; http://www.springer-ny.com 99/3(2015-06-01), 353-372 0885-6125 99:3<353 2015 99 10994 https://doi.org/10.1007/s10994-014-5456-x text/html Onlinezugriff via DOI BK010053 XK010053 XK010000 Metadata rights reserved Springer special CC-BY-NC licence nationallicence 1 research-article jats NATIONALLICENCE NATIONALLICENCE NL-springer NATIONALLICENCE 856 40 https://doi.org/10.1007/s10994-014-5456-x text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Qian Qi Department of Computer Science and Engineering, Michigan State University, 48824, East Lansing, MI, USA aut NATIONALLICENCE 700 1- Jin Rong Department of Computer Science and Engineering, Michigan State University, 48824, East Lansing, MI, USA aut NATIONALLICENCE 700 1- Yi Jinfeng Department of Computer Science and Engineering, Michigan State University, 48824, East Lansing, MI, USA aut NATIONALLICENCE 700 1- Zhang Lijun Department of Computer Science and Engineering, Michigan State University, 48824, East Lansing, MI, USA aut NATIONALLICENCE 700 1- Zhu Shenghuo NEC Laboratories America, 95014, Cupertino, CA, USA aut NATIONALLICENCE 773 0- Machine Learning Springer US; http://www.springer-ny.com 99/3(2015-06-01), 353-372 0885-6125 99:3<353 2015 99 10994