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.

本研究提出了利用随机梯度下降中的小批量和自适应采样两种策略来有效地减少 DML 的计算复杂度，证明了这些方法的理论保证，并进行了广泛的实证研究以验证所提出算法的有效性。