@inproceedings{kunapuli2012mirror,
author="Kunapuli, Gautam and Shavlik, Jude",
editor="Flach, Peter A. and De Bie, Tijl and Cristianini, Nello",
title="Mirror Descent for Metric Learning: A Unified Approach",
booktitle="Machine Learning and Knowledge Discovery in Databases",
year="2012",
publisher="Springer Berlin Heidelberg",
address="Berlin, Heidelberg",
pages="859--874",
isbn="978-3-642-33460-3",
doi="10.1007/978-3-642-33460-3_60",
url="https://doi.org/10.1007/978-3-642-33460-3_60"
}“Most metric learning methods are characterized by diverse loss functions and projection methods, which naturally begs the question: is there a wider framework that can generalize many of these methods? In addition, ever persistent issues are those of scalability to large data sets and the question of kernelizability. We propose a unified approach to Mahalanobis metric learning: an online regularized metric learning algorithm based on the ideas of composite objective mirror descent (comid). The metric learning problem is formulated as a regularized positive semi-definite matrix learning problem, whose update rules can be derived using the comid framework. This approach aims to be scalable, kernelizable, and admissible to many different types of Bregman and loss functions, which allows for the tailoring of several different classes of algorithms. The most novel contribution is the use of the trace norm, which yields a sparse metric in its eigenspectrum, thus simultaneously performing feature selection along with metric learning.”
“In this work, we consider the Mahalanobis metric learning problem applied to $k$-nearest neighbors classification. The Mahalanobis metric is a distance function that is of the form $d(\bold{x},\bold{z}) = \parallel L \bold{x} - L \bold{z} \parallel_{2}$.”
“…. We formulate the problem in the spirit of Shalev-Shwartz et al. [9]1, where the goal is to incrementally learn a metric, given triplets of the form $(\bold{x}_{t}, \bold{z}_{t}, y_{t})_{t=1}^{T}$. The label $y_{t} = 1$ indicates that training point $\bold{x}_{t}$ is similar to $\bold{z}_{t}$ and $y=-1$ indicates dissimilarity.”
“The metric we learn is of the form $d(\bold{x}, \bold{z}) = \parallel L(\bold{x} - \bold{z}) \parallel_{2}$, where $L \in \mathbb{R}^{n \times m}$ is a linear transformation. Since learning this metric directly is difficult owing to non-convexity, we consider instead:”
\[ \tag{1} \begin{aligned} d_{M}(\bold{x}, \bold{z})^{2} &= (\bold{x} - \bold{z})^{\prime} L^{\prime} L(\bold{x} - \bold{z}) \cr &= (\bold{x} - \bold{z})^{\prime} M (\bold{x} - \bold{z}) \end{aligned} \]
“with $M \in \mathbb{S}_{+}^{n}$, the cone of positive semi-definite (psd) matrices. Given $T$ labeled pairs of points… we learn $(M, \mu)$…. This condition can be formulated via the constraints”
\[ \tag{2} \begin{aligned} \forall (\bold{x}, \bold{z}, y=+1) &\implies d_{M}(\bold{x}, \bold{z})^{2} \leq \mu - 1 \cr \forall (\bold{x}, \bold{z}, y=-1) &\implies d_{M}(\bold{x}, \bold{z})^{2} \geq \mu + 1 \end{aligned} \]
“which can be written simply as $y_{t}(\mu - d_{M}(\bold{x}_{t}, \bold{z}_{t})^{2}) \geq 1$. …. We define the margin function for a pair of instances $\bold{x}_{t}$ and $\bold{z}_{t}$, given a label $y_{t}$, as”
\[ \tag{3} \begin{aligned} m(\bold{x}_{t}, \bold{z}_{t}, y_{t}) &= y_{t}(\mu - d_{M}(\bold{x}_{t}, \bold{z}_{t})^{2}) \cr &= y_{t} (\mu - (\bold{x}_{t} - \bold{z}_{t})^{\prime} M (\bold{x}_{t}, \bold{z}_{t})). \end{aligned} \]
“This lets us define several loss functions….”
“[W]e also incorporate regularization into the problem so that the resulting metric has sparsity. [M]inimizing the trace-norm of $M$ i.e., the sum of the singular values of $M$ yields sparsity in the spectrum of $M$, thus minimizing the rank of $M$. Given $T$ samples, the overall problem is one of regularized loss minimization, which leads to an optimization problem of the form”
\[ \tag{4} \min_{M \succeq 0, \mu \geq 1} \frac{1}{T} \sum_{t=1}^{T} \ell_{t}(M, \mu) + \rho r(M), \]
“where the loss function $\ell_{t} : \mathbb{S}_{+}^{n} \times \mathbb{R} \rightarrow \mathbb{R}$ and the regularization function $r : \mathbb{S_{+}^{n}} \rightarrow \mathbb{R}$ are both convex and $\rho \in \mathbb{R}_{+}$ is the regularization parameter.”
“The Bregman divergence [13]2 with respect to a strictly convex function $\psi$ is defined as $B_{\psi}(\bold{x}, \bold{z}) = \psi(\bold{x}) - \psi(\bold{z}) - \nabla \psi(\bold{z})^{\prime}(\bold{x} - \bold{z})$.”
“The mirror descent algorithm [14]3 is an iterative proximal-gradient method for minimizing a convex function, $\phi : \Omega \rightarrow \mathbb{R}$. Based on this approach, an update in the online setting, with function $\phi_{t}$ is”
\[ \tag{5} \bold{w}_{t+1} = \argmin_{\bold{w} \in \Omega} B_{\phi} (\bold{w}, \bold{w_{t}}) + \eta \nabla^{\prime} \phi_{t} (\bold{w_{t}}) (\bold{w} - \bold{w}_{t}). \]
“Recently, Duchi et al. [15]4 generalized mirror descent to the case where the functions $\phi_{t} = \ell_{t} + r$ are composite, consisting of loss and regularization terms:”
\[ \tag{6} \bold{w}_{t+1} = \argmin_{\bold{w} \in \Omega} B_{\phi} (\bold{w}, \bold{w_{t}}) + \eta \textcolor{magenta}{\ell_{t}} \nabla^{\prime} \phi_{t} (\bold{w_{t}}) (\bold{w} - \bold{w}_{t}) \textcolor{magenta}{+ \eta r(\bold{w})}. \]
“The subtle, yet significant difference between $(\textcolor{orange}{5})$ and $(\textcolor{orange}{6})$ is that the entire composite function $\phi_{t}$ is not linearized. Rather, only $\ell_{t}$ is linearized; this leads to the composite mirror descent algorithm (COMID). The reason for this partial linearization is because general mirror descent applied to $\ell_{1}$-regularization does not lead to sparse updates, whereas the COMID update does.”
“[W]e … formulate metric learning as an online problem. …. The goal is to optimize the objective $(\textcolor{orange}{4})$ in an online manner i.e. at each iteration… the algorithm receives a labeled pair of points…, which has an associated loss function $\ell_{t}(M, \mu)$, and the estimates $M_{t+1}$ and $\mu_{t+1}$ are calculated using a composite mirror descent update rule. Since we are interested in sparse updates as well, we use the trace norm, $\mid\mid\mid M \mid\mid\mid$, the effect of which is controlled via a regularization parameter $\rho \gt 0$. …. At each step, we compute updates given a learning rate $\eta \gt 0$, … according to”
\[ \tag{7} M_{t+1} = \argmin_{M \succeq 0} B_{\psi} (M, M_{t}) + \eta \langle \nabla_{M} \ell_{t} (M_{t}, \mu_{t}), M - M_{t} \rangle + \eta \rho \mid\mid\mid M \mid\mid\mid, \]
\[ \tag{8} \mu_{t+1} = \argmin_{\mu \geq 1} B_{\psi}(\mu, \mu_{t}) + \eta \nabla_{\mu} \ell_{t} (M_{t}, \mu_{t})^{\prime} (\mu - \mu_{t}). \]
“This metric learning formulation has several advantages:”
“The update rule $(\textcolor{orange}{7})$ can be broken down into two separate updates:”
\[ \tag{9} M_{t+\frac{1}{2}} = \argmin{M} B_{\psi}(M, M_{t}) + \eta \langle \nabla_{M} \ell_{t} (M_{t}, \mu_{t}), M - M_{t} \rangle, \]
\[ \tag{10} M_{t+1} = \argmin_{M \succeq 0} B_{\psi}(M, M_{t+\frac{1}{2}}) + \eta \rho \mid\mid\mid M \mid\mid\mid. \]
“The gradient condition of $(\textcolor{orange}{9})$: $0 \in \nabla \psi (M_{t+\frac{1}{2}}) - \nabla \psi (M_{t}) + \eta \nabla_{M} \ell_{t} (M_{t}, \mu_{t})$, gives us the intermediate solution: $M_{t+\frac{1}{2}} = \nabla \psi^{-1} ( \nabla \psi (M_{t}) - \eta \nabla_{M} \ell_{t} (M_{t}, \mu_{t}) )$, which can be used to solve $(\textcolor{orange}{10}).$”
Proposition 1. The optimal solution to $(\textcolor{orange}{10})$ is given by
\[ \tag{12} \begin{aligned} M_{t+1} &= \nabla \psi^{-1} (S_{\eta \rho} (\nabla \psi (M_{t+\frac{1}{2}}) )) \cr &= V \nabla \psi^{-1} (\text{diag} (S_{\eta \rho} (\lambda))) V^{\prime}. \end{aligned} \]
where $\nabla \psi (M_{t+\frac{1}{2}}) = \nabla \psi (M_{t}) - \eta \nabla_{M} \ell_{t} (M_{t}, \mu_{t}) = V \text{diag} (\lambda) V^{\prime}$
Proposition 2. The optimal solution to $(\textcolor{orange}{8})$ is given by
\[ \tag{13} \mu_{t+1} = \max (\nabla \psi^{-1} (\nabla \psi (\mu_{t}) - \eta \nabla_{\mu} \ell_{t} (M_{t}, \mu_{t})), 1). \]
“At the $t$-th iteration, with $M_{t} = V_{t} \nabla \psi (\Lambda_{t}) V_{t}^{\prime}$, we have:”
\[ \begin{aligned} (\text{Intermediate~gradient}) && \nabla \psi (M_{t+\frac{1}{2}}) &= V_{t} \nabla \psi (\Lambda_{t}) V_{t}^{\prime} - \alpha \bold{u}_{t} \bold{u}_{t}^{\prime} \cr (\text{EVD of intermediate gradient}) && \nabla \psi (M_{t+\frac{1}{2}}) &= V_{t+1} \Lambda_{t+1} V_{t+1}^{\prime} \cr (\text{Matrix update/thresholding}) && M_{t+1} &= V_{t+1} \nabla \psi^{-1} (S_{\eta \rho} (\Lambda_{t+1})) V_{t+1}^{\prime} \end{aligned} \]
“The complete algorithm is described below.”
Algorithm 1 Mirror Descent for Metric Learning
“Given that the updates are embarrassingly parallelizable, an immediate target is the massive data setting, where we need to learn with millions of data points. In addition, the approach is also amenable to the addition of local geometry constraints in order to learn low-dimensional geometry-aware metrics that lead to representable models. Finally, the kernel-MDML approach is a very powerful extension to linear metric learning, with applications in colored dimensionality reduction and manifold alignment.”
[9] Shalev-Shwartz, S. Singer, Y., Ng, A.Y.: Online and batch learning of pseudometrics. In: Proc. 21st ICML. (2004) 94-102 ↩
[13] Bregman, L.M.: The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming. USSR Computational Mathematics and Mathematical Physics 7 (1967) 200-217 ↩
[14] Beck, A., Teboulle, M.: Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters 31 (2003) 167-175 ↩
[15] Duchi, J. Shalev-Shwartz, S., Singer, Y., Tewari, A.: Composite objective mirror descent. In: COLT. (2010) 14-26 ↩