Fixed-target large-margin nearest-neighbor objective

Fix positive integers $d,n,C$, a finite labeled sample $(x_i,y_i{)}_{i=1}^n$ with $x_i\in {\mathbb{R}}^d$ and $y_i\in \{1,\dots ,C\}$, and a weight $\mu \in [0,1]$. For each $i$, fix in advance an integer $k_i$ with $0\le k_i\le \mathrm{\mid }\{j\mathrm{\ne }i:y_j=y_i\}\mathrm{\mid }$ and a fixed target-neighbor set $N_i\subseteq \{j\mathrm{\ne }i:y_j=y_i\}$ with $\mathrm{\mid }{N}_i\mathrm{\mid }=k_i$. These target sets do not change with the matrix being optimized. Let ${\mathbb{S}}_{+}^d$ denote the real symmetric matrices $M$ satisfying $v^{T}Mv\ge 0$ for all $v\in {\mathbb{R}}^d$, and put $q_M(x,x^{\mathrm{\prime }})=(x-x^{\mathrm{\prime }}{)}^{T}M(x-x^{\mathrm{\prime }})$. For a real number $z$, let $[z{]}_{+}=\max \{z,0\}$. For $M\in {\mathbb{S}}_{+}^d$, define

${ϵ}_{\mathrm{p}\mathrm{u}\mathrm{l}\mathrm{l}}(M)={\sum }_{i=1}^n{\sum }_{j\in N_i}{q}_M(x_i,x_j),{ϵ}_{\mathrm{p}\mathrm{u}\mathrm{s}\mathrm{h}}(M)={\sum }_{i=1}^n{\sum }_{j\in N_i}{\sum }_{\begin{array}{c}1\le l\le n\\ y_l\mathrm{\ne }{y}_i\end{array}}[1+q_M(x_i,x_j)-q_M(x_i,x_l){]}_{+},$

and $F_{\mu }(M)=(1-\mu ){ϵ}_{\mathrm{p}\mathrm{u}\mathrm{l}\mathrm{l}}(M)+\mu {ϵ}_{\mathrm{p}\mathrm{u}\mathrm{s}\mathrm{h}}(M)$. This is the fixed-target LMNN training surrogate; it is not a test-error or calibrated/generalization-risk quantity. The quantity $q_M$ is a squared distance, while its square root is the Mahalanobis pseudometric.

Positive-semidefinite matrices and squared Mahalanobis distance

Finite sums over the sample and fixed target sets

Trace as the sum of diagonal entries

Weinberger and Saul, §§3.1–3.2, printed pp. 214–218

Bellet, Habrard, and Sebban, §3.2, printed pp. 12–13