Conditional best-iterate and weighted-average bound for LMNN training

Assume Countable Choice ${\mathrm{A}\mathrm{C}}_{\omega }$. Let $d,n,C$ be positive integers, let $(x_i,y_i{)}_{i=1}^n$ be a finite sample with $x_i\in {\mathbb{R}}^d$ and $y_i\in \{1,\dots ,C\}$, let fixed target sets satisfy $N_i\subseteq \{j\mathrm{\ne }i:y_j=y_i\}$, and let $\mu \in [0,1]$. For symmetric $M$ put $q_M(x,x^{\mathrm{\prime }})=(x-x^{\mathrm{\prime }}{)}^{T}M(x-x^{\mathrm{\prime }})$ and

$F_{\mu }(M)=(1-\mu ){\sum }_i{\sum }_{j\in N_i}{q}_M(x_i,x_j)+\mu {\sum }_i{\sum }_{j\in N_i}{\sum }_{l:y_l\mathrm{\ne }{y}_i}[1+q_M(x_i,x_j)-q_M(x_i,x_l){]}_{+},$

where $[z{]}_{+}=\max \{z,0\}$, and minimize over ${\mathbb{S}}_{+}^d=\{M=M^T:v^{T}Mv\ge 0\text{ for every }v\in {\mathbb{R}}^d\}$. Let $T\ge 1$ be an integer, choose $M_0\in {\mathbb{S}}_{+}^d$ and step sizes ${\eta }_0,\dots ,{\eta }_{T-1}>0$, and suppose a global minimizer $M^{\ast }\in {\mathbb{S}}_{+}^d$ of $F_{\mu }$ exists. For each $t<T$, put $C_{ij}=(x_i-x_j)(x_i-x_j{)}^T$, $h_{ijl}(M)=1+⟨M,C_{ij}-C_{il}{⟩}_F$, and ${\gamma }_{ijl}(M)=1$ if $h_{ijl}(M)>0$ and $0$ if $h_{ijl}(M)\le 0$. Form

$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}),M_t-{\eta }_t{G}_t=U_t\mathrm{diag}({\lambda }_{t,1},\dots ,{\lambda }_{t,d})U_t^T,$

where $U_t$ is orthogonal, and define

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

Set

$A_T={\sum }_{t=0}^{T-1}{\eta }_t,{\bar{M}}_T=\frac{1}{A_T}{\sum }_{t=0}^{T-1}{\eta }_t{M}_t,$

let $M_{\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}$ be the least-index minimizer of $F_{\mu }(M_t)$ over $0\le t<T$, and define

$B_{\mathrm{d}\mathrm{a}\mathrm{t}\mathrm{a}}=(1-\mu ){\sum }_i{\sum }_{j\in N_i}\mathrm{\parallel }{x}_i-x_j{\mathrm{\parallel }}_2^2+\mu {\sum }_i{\sum }_{j\in N_i}{\sum }_{l:y_l\mathrm{\ne }{y}_i}(\mathrm{\parallel }{x}_i-x_j{\mathrm{\parallel }}_2^2+\mathrm{\parallel }{x}_i-x_l{\mathrm{\parallel }}_2^2),R=\mathrm{\parallel }{M}_0-M^{\ast }{\mathrm{\parallel }}_F,$

where $\mathrm{\parallel }z{\mathrm{\parallel }}_2=({\sum }_{r=1}^d{z}_r^2{)}^{1\mathrm{/}2}$ and $\mathrm{\parallel }\cdot {\mathrm{\parallel }}_F$ is the entry-sum Frobenius norm.

Then $A_T>0$, $M_{\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}},{\bar{M}}_T\in {\mathbb{S}}_{+}^d$, and

$\max \{F_{\mu }(M_{\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}})-F_{\mu }(M^{\ast }),F_{\mu }({\bar{M}}_T)-F_{\mu }(M^{\ast })\}\le \frac{R^2+B_{\mathrm{d}\mathrm{a}\mathrm{t}\mathrm{a}}^2{\sum }_{t=0}^{T-1}{\eta }_t^2}{2A_T}\mathrm{.}$

This conditional bound applies to the best observed iterate and weighted average; it does not assert the same bound for the final iterate $M_T$ or any test-error improvement.

Finite projected-subgradient procedure and kink convention

Convexity of the fixed-target objective

Subgradient formula and uniform data bound

Euclidean coordinate reduction

Axiom of Countable Choice

Completeness of finite-dimensional Euclidean space

Hilbert-space definition

Abstract Hilbert projection theorem

Published projected-subgradient best/average bound

Choice-free spectral-clipping projection formula

Bubeck, §3.1, printed pp. 262–266

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

Weinberger and Saul, §3.4 and Appendix A, printed pp. 220–221 and 238–241

The explicit eigenvalue-clipping implementation and its finite local projection formula are choice-free. The proof above separately records the stronger abstract Hilbert-projection route required by the current interface; that branch uses only ${\mathrm{A}\mathrm{C}}_{\omega }$, not the full Axiom of Choice. The hypothesis that $M^{\ast }$ exists is essential to this stated application and is not derived from convexity alone.