Finite-budget projected-subgradient training for fixed-target LMNN

Use the finite sample, fixed target sets, weight $\mu \in [0,1]$, and objective $F_{\mu }$ defined by the LMNN objective item. The inputs are an integer budget $T\ge 1$, an initial matrix $M_0\in {\mathbb{S}}_{+}^d$, and positive step sizes ${\eta }_0,\dots ,{\eta }_{T-1}$. Let $m=d(d+1)\mathrm{/}2$ and use $\mathrm{svec}:{\mathbb{S}}^d\to {\mathbb{R}}^m$, the linear isometry that lists the diagonal entries followed by the $\sqrt{2}$-scaled upper-triangle entries in lexicographic order. Set $C^{\mathrm{\prime }}=\mathrm{svec}({\mathbb{S}}_{+}^d)$ and $f(z)=F_{\mu }({\mathrm{svec}}^{-1}(z))$; this is a nonempty closed convex domain and $f$ is convex.

Initialize $z_0=\mathrm{svec}(M_0)$. At each $t=0,\dots ,T-1$, put $M_t={\mathrm{svec}}^{-1}(z_t)$ and compute the Frobenius subgradient

$G_t=(1-\mu ){\sum }_i{\sum }_{j\in N_i}{C}_{ij}+\mu {\sum }_i{\sum }_{j\in N_i}{\sum }_{l:y_l\mathrm{\ne }{y}_i}{\gamma }_{ijl}(M_t)(C_{ij}-C_{il}),$

where $C_{ij}=(x_i-x_j)(x_i-x_j{)}^T$, $h_{ijl}(M)=1+⟨M,C_{ij}-C_{il}{⟩}_F$, ${\gamma }_{ijl}(M)=1$ when $h_{ijl}(M)>0$, and ${\gamma }_{ijl}(M)=0$ when $h_{ijl}(M)\le 0$. Supply the successful oracle response $(f(z_t),\mathrm{svec}(G_t))$ to the finite-budget projected-subgradient method on $C^{\mathrm{\prime }}$ with step size ${\eta }_t$. It updates $z_{t+1}=P_{C^{\mathrm{\prime }}}(z_t-{\eta }_t\mathrm{svec}(G_t))$, where $P_{C^{\mathrm{\prime }}}$ is the unique nearest point in the Euclidean norm. Equivalently, form $A_t=M_t-{\eta }_t{G}_t$, choose an orthogonal eigendecomposition $A_t=U_t\mathrm{diag}({\lambda }_{t,1},\dots ,{\lambda }_{t,d})U_t^T$, and set

$M_{t+1}=U_t\mathrm{diag}(\max \{{\lambda }_{t,1},0\},\dots ,\max \{{\lambda }_{t,d},0\})U_t^T\mathrm{.}$

All $T$ oracle calls succeed; the generic method reports budget-exhausted after $T$ updates. The requested final iterate is $M_T$; its status, completed update count, weighted average, and least-index best observed iterate are also defined by the generic method. The explicit spectral-clipping implementation is choice-free. The equivalent abstract Hilbert-projection interface assumes Countable Choice, as in the general closest-point theorem; that axiom branch is retained separately for the conditional analysis. This finite procedure makes no unconditional convergence, optimality, empirical-error, or generalization claim.

Sample, fixed targets, and objective

Finite-sum convention

Convexity of the objective and feasible cone

Explicit subgradient, kink convention, and uniform bound

Symmetric vectorization

Closedness of the feasible cone

Transport of domain properties and subgradients

Exact Frobenius projection formula

Published finite-budget projected-subgradient procedure

Abstract Hilbert projection interface

Countable Choice for that abstract interface

Weinberger and Saul, Appendix A.1–A.3, printed pp. 238–241

Bubeck, §3.1, printed pp. 262–266

Bertsekas, MIT 6.253 Lecture 15, printed pp. 200–205