Pipeline-generated

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Nearest neighbors and learned metrics

1 · Prerequisites

2 · Logical flowchart

3 · Definitions, theorems and proofs

DefinitionDefinition: Literature-sourcedProof: Not applicableOpen item page →

Mahalanobis pseudometric induced by a positive-semidefinite matrix

Definition

Fix an integer $d \geq 1$ . A real matrix $M \in R^{d \times d}$ is positive semidefinite, written $M ⪰ 0$ , when it is symmetric and $v^{T} M v \geq 0$ for every $v \in R^{d}$ . For $x, x^{'} \in R^{d}$ , define the squared Mahalanobis distance and its nonnegative square root by

$q_{M} (x, x^{'}) : = (x - x^{'})^{T} M (x - x^{'}), d_{M} (x, x^{'}) : = \sqrt{q_{M} (x, x^{'})} .$

The square root is defined because $q_{M} (x, x^{'}) \geq 0$ . A pseudometric is a nonnegative symmetric function that vanishes on the diagonal and satisfies the triangle inequality, but may assign distance zero to distinct points. The function $d_{M}$ is called the Mahalanobis pseudometric associated with $M$ ; $q_{M} = d_{M}^{2}$ is its squared-distance form. The theorem on this page proves the pseudometric properties and the equivalent linear-feature representation.

Definition references

Existence and uniqueness of nonnegative square roots

Weinberger and Saul, §2.1, printed pp. 209–210

Bellet, Habrard, and Sebban, Mahalanobis distance and interpretation, printed pp. 9–10

LemmaStatement: AI-adaptedProof: AI-adaptedOpen item page →

Symmetric matrices are Euclidean under the Frobenius norm

Statement

Let $d \geq 1$ , let $S^{d}$ be the real vector space of symmetric $d \times d$ matrices, and set $m = d (d + 1) / 2$ . Use one-based entry labels $A_{i j} : = A (i - 1, j - 1)$ for $1 \leq i, j \leq d$ , and likewise for every matrix below. Equip $S^{d}$ with the Frobenius inner product $⟨ A, B ⟩_{F} : = \sum_{i = 1}^{d} \sum_{j = 1}^{d} A_{i j} B_{i j}$ and its induced norm. Define $svec : S^{d} \to R^{m}$ by listing $A_{11}, \dots, A_{d d}$ first, followed by $\sqrt{2} A_{i j}$ for $1 \leq i < j \leq d$ in lexicographic order. Then $svec$ is a linear bijection and preserves inner products and norms; in particular, $∥ svec (A) - svec (B) ∥_{2} = ∥ A - B ∥_{F}$ for all $A, B \in S^{d}$ .

Statement references

Entry-sum definition of the Frobenius norm

Euclidean inner product on real coordinate space

Positive square root used in the off-diagonal coordinates

Higham, §2, Theorem 2.1, printed pp. 105–106

Bindel, §2, PDF pp. 1–2

Facts & Assumptions

Given: An integer $d \geq 1$ , symmetric real matrices $A, B \in S^{d}$ , and $m = d (d + 1) / 2$ .

[F1]

For a real matrix, the squared Frobenius norm is the sum of the squares of all entries (The Frobenius norm $∥ A ∥_{F} = (\sum_{i, j} ∣ a_{i j} ∣^{2})^{1 / 2}$ on real or complex matrices). Under the stated entry labels, substituting $i = r + 1$ , $j = s + 1$ gives $\sum_{r < d} \sum_{s < d} A (r, s)^{2} = \sum_{i = 1}^{d} \sum_{j = 1}^{d} A_{i j}^{2}$ ; in particular, when $d = 1$ , $A_{11} = A (0, 0)$ .

[F2]

The Euclidean inner product on $R^{m}$ is the coordinate dot product, with norm the square root of the sum of coordinate squares (The Euclidean inner product $⟨ x, y ⟩ = \sum_{k < n} x_{k} y_{k}$ on $R^{n}$ ).

[F3]

Every nonnegative real number has a unique nonnegative square root, so $\sqrt{2} > 0$ and division by $\sqrt{2}$ is defined (Square roots exist: a unique $\sqrt{a} \geq 0$ with $(\sqrt{a})^{2} = a$ ; the positives are ${x^{2} : x \neq 0}$ ).

Proof

1.1givenF3algebra

The coordinate list has $d + d (d - 1) / 2 = m$ entries. Its first $d$ entries recover each diagonal entry of $A$ , and each later entry recovers the corresponding symmetric pair by division by $\sqrt{2}$ from [F3]. Thus it has a unique inverse on $R^{m}$ ; its coordinate formulas are linear, so $svec$ is a linear bijection.

1.2F2givenalgebra

For $A, B \in S^{d}$ , the Euclidean dot product of their coordinate lists is $\sum_{i} A_{i i} B_{i i} + 2 \sum_{i < j} A_{i j} B_{i j}$ , because each off-diagonal coordinate contributes $(\sqrt{2} A_{i j}) (\sqrt{2} B_{i j})$ . Symmetry gives $⟨ A, B ⟩_{F} = \sum_{i} A_{i i} B_{i i} + \sum_{i < j} (A_{i j} B_{i j} + A_{j i} B_{j i})$ , which is the same expression. Hence $⟨ svec (A), svec (B) ⟩_{2} = ⟨ A, B ⟩_{F}$ .

2.1step 1.2F1F2F3algebra∎

Linearity gives $svec (A) - svec (B) = svec (A - B)$ . Applying step 1.2 to $A - B$ with itself and taking the unique nonnegative square roots from [F1]–[F3] yields $∥ svec (A) - svec (B) ∥_{2} = ∥ A - B ∥_{F}$ . This proves norm preservation.

TheoremStatement: AI-adaptedProof: AI-adaptedOpen item page →

Frobenius projection onto the positive-semidefinite cone is spectral clipping

Statement

Let $d \geq 1$ and let $A \in R^{d \times d}$ be symmetric. There exists an orthogonal eigendecomposition $A = U diag (λ_{1}, \dots, λ_{d}) U^{T}$ . For any such decomposition define $λ_{i}^{+} = \max {λ_{i}, 0}$ and $A_{+} = U diag (λ_{1}^{+}, \dots, λ_{d}^{+}) U^{T}$ . Let $S_{+}^{d}$ be the set of real symmetric matrices $Z$ with $v^{T} Z v \geq 0$ for every $v \in R^{d}$ , and let $∥ B ∥_{F} = (\sum_{i, j} B_{i j}^{2})^{1 / 2}$ . Then $A_{+}$ is the unique minimizer of $∥ A - Z ∥_{F}$ over $Z \in S_{+}^{d}$ , so its value is independent of the chosen orthogonal eigendecomposition.

Statement references

Real spectral theorem

Nonnegative operators and nonnegative eigenvalues

Positive semidefinite forms and operators over the reals

Orthogonal invariance of the Frobenius norm

Entry-sum Frobenius norm

Higham, §2, Theorem 2.1, article pp. 105–106

Bindel, §6, PDF p. 5

Weinberger and Saul, Appendix A.2, printed p. 240

Facts & Assumptions

Given: A real symmetric matrix $A \in R^{d \times d}$ , $d \geq 1$ , and its orthogonal eigendecomposition from the Statement.

[F1]

Every self-adjoint endomorphism of a finite-dimensional real inner-product space has an orthonormal eigenbasis (Real spectral theorem: a self-adjoint endomorphism of a finite-dimensional real inner product space has an orthonormal eigenbasis).

[F2]

A self-adjoint operator is nonnegative exactly when its eigenvalues are nonnegative (A non-negative operator is equivalently self-adjoint with nonnegative eigenvalues, a positive semidefinite matrix in an orthonormal basis, or an operator of the form S^*S).

[F3]

For a finite-dimensional real inner-product space, a self-adjoint operator is nonnegative exactly when its associated symmetric form is positive semidefinite (Over the reals, non-negative and positive operators correspond exactly to positive semidefinite and positive definite symmetric forms).

[F4]

Orthogonal multiplication on either side preserves the Frobenius norm (Spectral and Frobenius norms are unitarily invariant, are given by singular values, and satisfy the sharp rank comparison).

[F5]

The squared Frobenius norm is the sum of the squares of all matrix entries (The Frobenius norm $∥ A ∥_{F} = (\sum_{i, j} ∣ a_{i j} ∣^{2})^{1 / 2}$ on real or complex matrices).

Proof

1.1F1F2F3given

By [F1], choose an orthogonal eigendecomposition of $A$ and define $A_{+}$ as in the Statement. It is symmetric and has eigenvalues $λ_{i}^{+} \geq 0$ . By [F2] its associated operator is nonnegative, and by [F3] its quadratic form is positive semidefinite; hence $A_{+} \in S_{+}^{d}$ .

1.2F4given

Let $Z \in S_{+}^{d}$ and set $W = U^{T} Z U$ . For each coordinate vector $e_{i}$ , $W_{i i} = e_{i}^{T} W e_{i} = (U e_{i})^{T} Z (U e_{i}) \geq 0$ ; also $W$ is symmetric. Orthogonal invariance [F4] gives $∥ A - Z ∥_{F}^{2} = ∥ diag (λ_{1}, \dots, λ_{d}) - W ∥_{F}^{2}$ .

2.1step 1.2F5algebra

Expanding the entry sum [F5], the last square is $\sum_{i} (λ_{i} - W_{i i})^{2} + \sum_{i \neq j} W_{i j}^{2}$ . For every $w \geq 0$ , $(λ_{i} - w)^{2} \geq (λ_{i} - λ_{i}^{+})^{2}$ : if $λ_{i} \geq 0$ the right side is zero and equality is attained only at $w = λ_{i}$ , while if $λ_{i} < 0$ then $w - λ_{i} \geq - λ_{i}$ and equality is attained only at $w = 0$ . Thus every feasible $Z$ has squared distance at least $\sum_{i} (λ_{i} - λ_{i}^{+})^{2}$ .

3.1step 2.1givenalgebra

For $Z = A_{+}$ the conjugated matrix $W$ is $diag (λ_{1}^{+}, \dots, λ_{d}^{+})$ , so all off-diagonal terms vanish and every diagonal term attains its lower bound from step 2.1. Hence $A_{+}$ is a minimizer.

4.1step 2.1step 3.1algebra∎

Equality in the lower bound requires every off-diagonal square in step 2.1 to vanish and every diagonal term to attain its unique scalar minimum. Therefore $W = diag (λ_{1}^{+}, \dots, λ_{d}^{+})$ and $Z = U W U^{T} = A_{+}$ . The minimizer is unique; since the argument applies to any orthogonal eigendecomposition, every allowed decomposition gives this same nearest matrix.

Remarks

The proof above is choice-free: it constructs the unique minimizer from a finite orthogonal eigendecomposition and checks the objective directly. The separate abstract Hilbert-projection route used in the LMNN procedure is recorded under its own Countable Choice assumption.

LemmaStatement: AI-adaptedProof: AI-adaptedOpen item page →

The real positive-semidefinite cone is closed in the Frobenius metric

Statement

For an integer $d \geq 1$ , let $S^{d}$ be the real symmetric $d \times d$ matrices and let $S_{+}^{d} = {M \in S^{d} : v^{T} M v \geq 0 for every v \in R^{d}}$ . With the Frobenius norm $∥ A ∥_{F} = (\sum_{i, j} A_{i j}^{2})^{1 / 2}$ , the set $S_{+}^{d}$ is closed in $S^{d}$ .

Statement references

Entry-sum Frobenius norm

Euclidean inner product on coordinate space

Cauchy–Schwarz for the Euclidean inner product

Closed sets have open complements

Open balls in the Frobenius metric

Higham, §2, Theorem 2.1, article pp. 105–106

Bindel, §6, PDF p. 5

Facts & Assumptions

Given: An integer $d \geq 1$ and the real vector space $S^{d}$ with the Frobenius metric.

[F1]

The Frobenius norm is the Euclidean norm of the matrix-entry list (The Frobenius norm $∥ A ∥_{F} = (\sum_{i, j} ∣ a_{i j} ∣^{2})^{1 / 2}$ on real or complex matrices).

[F2]

The entry inner product is the Euclidean coordinate inner product, so it satisfies Cauchy–Schwarz; expanding entries gives $∥ v v^{T} ∥_{F} = ∥ v ∥_{2}^{2}$ (The Euclidean inner product $⟨ x, y ⟩ = \sum_{k < n} x_{k} y_{k}$ on $R^{n}$ , Cauchy-Schwarz $∣ ⟨ x, y ⟩ ∣ \leq ∥ x ∥_{2} ∥ y ∥_{2}$ with its equality case, the triangle inequality for $∥ \cdot ∥_{2}$ , the parallelogram law and polarisation).

[F3]

A set is closed when its complement is open, and an open set contains a positive-radius ball around each of its points (The metric topology: a set is open when every one of its points has a ball around it inside the set; closed means open complement, Open ball, closed ball and sphere in a metric space).

[F4]

The Frobenius norm is an inner-product norm, so its restriction to $S^{d}$ is a norm; the induced metric is $d_{F} (A, B) : = ∥ A - B ∥_{F}$ (The Frobenius norm $∥ A ∥_{F} = (\sum_{i, j} ∣ a_{i j} ∣^{2})^{1 / 2}$ on real or complex matrices, The inner-product norm is definite, homogeneous, and satisfies the triangle inequality, A norm on a real vector space, the induced metric, and the dictionary with the metric axioms).

Proof

1.1givenchoose

Let $A \in S^{d} ∖ S_{+}^{d}$ . By the definition of $S_{+}^{d}$ , there is $v \in R^{d}$ with $v^{T} A v < 0$ ; necessarily $v \neq 0$ . Set $ρ = - v^{T} A v / (2 ∥ v ∥_{2}^{2}) > 0$ .

2.1step 1.1F1F2F4algebra

For any $Z \in S^{d}$ with $∥ Z - A ∥_{F} < ρ$ , the entry norm [F1], entry inner product, and Cauchy–Schwarz [F2] give $∣ v^{T} (Z - A) v ∣ = ∣ ⟨ Z - A, v v^{T} ⟩_{F} ∣ \leq ∥ Z - A ∥_{F} ∥ v v^{T} ∥_{F} < ρ ∥ v ∥_{2}^{2} = - \frac{1}{2} v^{T} A v$ . Hence $v^{T} Z v < v^{T} A v - \frac{1}{2} v^{T} A v = \frac{1}{2} v^{T} A v < 0$ , so $Z \notin S_{+}^{d}$ .

3.1step 1.1step 2.1F3F4∎

Step 2.1 shows that the open ball $B_{F} (A, ρ)$ in the metric $d_{F}$ is contained in the complement of $S_{+}^{d}$ . Since $A$ was arbitrary in that complement, every point of it has an open ball contained in it; the complement is open by [F3], and therefore $S_{+}^{d}$ is closed.

AlgorithmAlgorithm: Literature-sourcedProof: Not applicablejudge pass (gpt-6-luna)Open item page →

Finite-sample k-nearest-neighbor classifier with fixed tie-breaking

Definition

Let $d, n, C$ be positive integers, let $(x_{i}, y_{i})_{i = 1}^{n}$ be a finite labeled sample with $x_{i} \in R^{d}$ and $y_{i} \in {1, \dots, C}$ , let $M \in R^{d \times d}$ be symmetric with $v^{T} M v \geq 0$ for every $v \in R^{d}$ , let $1 \leq k \leq n$ , and let $x \in R^{d}$ be a query. For each sample index set $δ_{i} = \sqrt{(x - x_{i})^{T} M (x - x_{i})}$ . Order indices $i$ by increasing pairs $(δ_{i}, i)$ in lexicographic order, and let $K_{k} (x)$ be the first $k$ indices in this order. For each class $c \in {1, \dots, C}$ compute $v_{c} (x) = \sum_{i \in K_{k} (x)} 1_{{y_{i} = c}}$ and return the smallest class label attaining $\max_{1 \leq c \leq C} v_{c} (x)$ . Thus equal distances are resolved by the fixed sample-index order, and equal class votes by the smallest class label.

Definition references

Mahalanobis squared distance and its nonnegative square root

Finite-sum convention

Weinberger and Saul, §2.1, printed pp. 209–210, and §3.1, pp. 214–216

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

DefinitionDefinition: Literature-sourcedProof: Not applicablejudge pass (gpt-6-luna)Open item page →

Fixed-target large-margin nearest-neighbor objective

Definition

Fix positive integers $d, n, C$ , a finite labeled sample $(x_{i}, y_{i})_{i = 1}^{n}$ with $x_{i} \in R^{d}$ and $y_{i} \in {1, \dots, C}$ , and a weight $μ \in [0, 1]$ . For each $i$ , fix in advance an integer $k_{i}$ with $0 \leq k_{i} \leq ∣ {j \neq i : y_{j} = y_{i}} ∣$ and a fixed target-neighbor set $N_{i} \subseteq {j \neq i : y_{j} = y_{i}}$ with $∣ N_{i} ∣ = k_{i}$ . These target sets do not change with the matrix being optimized. Let $S_{+}^{d}$ denote the real symmetric matrices $M$ satisfying $v^{T} M v \geq 0$ for all $v \in R^{d}$ , and put $q_{M} (x, x^{'}) = (x - x^{'})^{T} M (x - x^{'})$ . For a real number $z$ , let $[z]_{+} = \max {z, 0}$ . For $M \in S_{+}^{d}$ , define

$ϵ_{p u l l} (M) = \sum_{i = 1}^{n} \sum_{j \in N_{i}} q_{M} (x_{i}, x_{j}), ϵ_{p u s h} (M) = \sum_{i = 1}^{n} \sum_{j \in N_{i}} \sum_{\begin{array}{c} 1 \leq l \leq n \\ y_{l} \neq y_{i} \end{array}} [1 + q_{M} (x_{i}, x_{j}) - q_{M} (x_{i}, x_{l})]_{+},$

and $F_{μ} (M) = (1 - μ) ϵ_{p u l l} (M) + μ ϵ_{p u s 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.

Definition references

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

TheoremStatement: AI-adaptedProof: AI-adaptedOpen item page →

The Mahalanobis distance is a pseudometric and comes from a linear feature map

Statement

Let $d \geq 1$ and let $M \in R^{d \times d}$ be real symmetric and positive semidefinite, meaning $v^{T} M v \geq 0$ for every $v \in R^{d}$ . Define $q_{M} (x, x^{'}) = (x - x^{'})^{T} M (x - x^{'})$ and $d_{M} (x, x^{'}) = \sqrt{q_{M} (x, x^{'})}$ . Then there is a real matrix $L \in R^{d \times d}$ with $M = L^{T} L$ and, for all $x, x^{'} \in R^{d}$ , $d_{M} (x, x^{'}) = ∥ L x - L x^{'} ∥_{2}$ . Consequently $d_{M}$ is nonnegative, symmetric, zero on the diagonal, and satisfies the triangle inequality, without asserting separation of distinct points.

Statement references

Definition of q_M and d_M

Positive semidefinite forms and nonnegative operators over the reals

Factorization of nonnegative operators

Euclidean inner product and norm

Triangle inequality for the Euclidean norm

Nonnegative square-root uniqueness

Weinberger and Saul, §2.1, printed pp. 209–210

Bellet, Habrard, and Sebban, Mahalanobis distance and interpretation, printed pp. 9–10

Facts & Assumptions

Given: An integer $d \geq 1$ , a real symmetric positive-semidefinite matrix $M \in R^{d \times d}$ , and $x, x^{'} \in R^{d}$ .

[F1]

For a finite-dimensional real inner-product space, a symmetric bilinear form is positive semidefinite exactly when its associated self-adjoint operator is nonnegative (Over the reals, non-negative and positive operators correspond exactly to positive semidefinite and positive definite symmetric forms).

[F2]

Every nonnegative endomorphism of a finite-dimensional real inner-product space has the form $S^{*} S$ for a linear endomorphism $S$ (A non-negative operator is equivalently self-adjoint with nonnegative eigenvalues, a positive semidefinite matrix in an orthonormal basis, or an operator of the form S^*S).

[F3]

The Euclidean inner product is $⟨ u, v ⟩ = \sum_{j = 1}^{d} u_{j} v_{j}$ and its induced norm satisfies $∥ u ∥_{2}^{2} = ⟨ u, u ⟩$ (The Euclidean inner product $⟨ x, y ⟩ = \sum_{k < n} x_{k} y_{k}$ on $R^{n}$ ).

[F4]

The Euclidean norm is nonnegative, symmetric under sign change, vanishes only at zero, and satisfies the triangle inequality (Cauchy-Schwarz $∣ ⟨ x, y ⟩ ∣ \leq ∥ x ∥_{2} ∥ y ∥_{2}$ with its equality case, the triangle inequality for $∥ \cdot ∥_{2}$ , the parallelogram law and polarisation).

[F5]

Every nonnegative real has a unique nonnegative square root (Square roots exist: a unique $\sqrt{a} \geq 0$ with $(\sqrt{a})^{2} = a$ ; the positives are ${x^{2} : x \neq 0}$ ).

Proof

1.1givenF1

Regard $M$ as the matrix of an endomorphism $T_{M} : R^{d} \to R^{d}$ , $T_{M} v = M v$ . The associated symmetric bilinear form is $(u, v) \mapsto u^{T} M v$ , so its positive-semidefinite hypothesis and [F1] imply that $T_{M}$ is nonnegative.

2.1step 1.1F2algebra

By [F2], there is an endomorphism $S$ with $T_{M} = S^{*} S$ . Let $L$ be its real matrix in the standard basis; the Euclidean adjoint has matrix $L^{T}$ , hence $M = L^{T} L$ .

3.1step 2.1F3F5algebra

For $h = x - x^{'}$ , steps 2.1 and [F3] give $q_{M} (x, x^{'}) = h^{T} M h = h^{T} L^{T} L h = ⟨ L h, L h ⟩ = ∥ L h ∥_{2}^{2}$ . Both $d_{M} (x, x^{'})$ and $∥ L h ∥_{2}$ are nonnegative and their squares agree, so [F5] gives $d_{M} (x, x^{'}) = ∥ L x - L x^{'} ∥_{2}$ .

4.1step 3.1F4∎

Nonnegativity, symmetry, and zero diagonal follow from the corresponding properties of the Euclidean norm in [F4]. For any $x, y, z \in R^{d}$ , $d_{M} (x, z) = ∥ L x - L z ∥_{2} \leq ∥ L x - L y ∥_{2} + ∥ L y - L z ∥_{2} = d_{M} (x, y) + d_{M} (y, z)$ by the triangle inequality in [F4]. The pseudometric axioms follow.

LemmaStatement: AI-adaptedProof: AI-adaptedOpen item page →

Symmetric vectorization transports closed convex domains and subgradients

Statement

Let $C \subseteq S^{d}$ be a closed convex set of real symmetric matrices in the Frobenius metric, let $F : C \to R$ be convex, let $svec : S^{d} \to R^{m}$ be the symmetric vectorization isometry, and define $C^{'} = svec (C)$ and $f : C^{'} \to R$ by $f (z) = F ({svec}^{- 1} (z))$ . Then $C^{'}$ is closed and convex and $f$ is convex. If $G$ is a Frobenius subgradient of $F$ at $M \in C$ , meaning $F (N) \geq F (M) + ⟨ G, N - M ⟩_{F}$ for every $N \in C$ , then $svec (G)$ is a Euclidean subgradient of $f$ at $svec (M)$ .

Statement references

Symmetric vectorization preserves inner products and distances

Subgradient inequality on a convex domain

Euclidean inner product in coordinates

Convex functions

Convex sets

Closed sets and open complements in a metric topology

Metric balls

Bubeck, §3.1, printed pp. 262–266

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

Facts & Assumptions

Given: A closed convex set $C \subseteq S^{d}$ , a convex function $F : C \to R$ , a point $M \in C$ , and a Frobenius subgradient $G$ at $M$ .

[F1]

The map $svec$ is a linear bijection and preserves inner products and distances (Symmetric matrices are Euclidean under the Frobenius norm).

[F2]

A function is convex when it satisfies the convex-combination inequality, and a set is convex when it contains every convex combination of its points (Convex and strictly convex functions on Euclidean convex sets, A convex subset of $R^{m}$ contains every line segment between two of its points).

[F3]

[F4]

A subgradient supplies a global supporting affine lower bound on the convex function (Subgradients and the subdifferential of a convex function).

Proof

1.1givenF1F2construct

If $z_{0}, z_{1} \in C^{'}$ , choose $M_{0}, M_{1} \in C$ with $z_{i} = svec (M_{i})$ . For $t \in [0, 1]$ , linearity gives $t z_{0} + (1 - t) z_{1} = svec (t M_{0} + (1 - t) M_{1})$ , and the matrix on the right is in $C$ by [F2]. Thus $C^{'}$ is convex.

1.2givenF1F3

Let $z \notin C^{'}$ and set $M = {svec}^{- 1} (z) \notin C$ . Since $C$ is closed, [F3] gives $r > 0$ such that $B_{F} (M, r) \subseteq S^{d} ∖ C$ , where $B_{F} (M, r) = {A \in S^{d} : ∥ A - M ∥_{F} < r}$ . For any $w \in B_{2} (z, r)$ , isometry [F1] gives ${svec}^{- 1} (w) \in B_{F} (M, r)$ , hence $w \notin C^{'}$ . Therefore $B_{2} (z, r) \subseteq R^{m} ∖ C^{'}$ , so the complement of $C^{'}$ is open and $C^{'}$ is closed.

1.3givenF1F2algebra

For $z_{0}, z_{1} \in C^{'}$ with preimages $M_{0}, M_{1}$ , linearity yields ${svec}^{- 1} (t z_{0} + (1 - t) z_{1}) = t M_{0} + (1 - t) M_{1}$ . Applying convexity of $F$ from [given] proves $f (t z_{0} + (1 - t) z_{1}) \leq t f (z_{0}) + (1 - t) f (z_{1})$ , so $f$ is convex.

2.1givenF1F4∎

Let $z = svec (M)$ and take any $w \in C^{'}$ , with preimage $N \in C$ . The assumed subgradient inequality gives $f (w) = F (N) \geq F (M) + ⟨ G, N - M ⟩_{F}$ . By inner-product preservation [F1], this equals $f (z) + ⟨ svec (G), w - z ⟩_{2}$ ; hence $svec (G)$ is a Euclidean subgradient by [F4].

TheoremStatement: AI-adaptedProof: AI-adaptedOpen item page →

The fixed-target LMNN objective is convex

Statement

Let $d, n, C$ be positive integers, let $(x_{i}, y_{i})_{i = 1}^{n}$ be a finite sample with $x_{i} \in R^{d}$ and $y_{i} \in {1, \dots, C}$ , let each fixed target set satisfy $N_{i} \subseteq {j \neq i : y_{j} = y_{i}}$ , and let $μ \in [0, 1]$ . For symmetric $M \in R^{d \times d}$ write $q_{M} (x, x^{'}) = (x - x^{'})^{T} M (x - x^{'})$ and define

$F_{μ} (M) = (1 - μ) \sum_{i = 1}^{n} \sum_{j \in N_{i}} q_{M} (x_{i}, x_{j}) + μ \sum_{i = 1}^{n} \sum_{j \in N_{i}} \sum_{\begin{array}{c} 1 \leq l \leq n \\ y_{l} \neq y_{i} \end{array}} [1 + q_{M} (x_{i}, x_{j}) - q_{M} (x_{i}, x_{l})]_{+},$

where $[z]_{+} = \max {z, 0}$ . Then $F_{μ}$ is convex on the real vector space of symmetric matrices. The feasible set $S_{+}^{d} = {M = M^{T} : v^{T} M v \geq 0 for all v \in R^{d}}$ is convex, so minimizing $F_{μ}$ over $S_{+}^{d}$ is a convex optimization problem.

Statement references

Fixed targets, pull/push loss, and the positive-part convention

Finite-sum convention

Trace as a sum of diagonal entries

Definition of a convex function

Definition of a convex set

Weinberger and Saul, §3.4, printed pp. 220–221

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

Facts & Assumptions

Given: The finite sample, fixed target sets, and parameter $μ \in [0, 1]$ in the Statement.

[F1]

For fixed $a, b \in R^{d}$ , $q_{M} (a, b) = tr (M (a - b) (a - b)^{T})$ , so it is affine-linear in the entries of $M$ (Fixed-target large-margin nearest-neighbor objective, The trace $tr (A)$ as the sum of the diagonal entries).

[F2]

A real-valued function on a convex set is convex when its value at every convex combination is at most the same convex combination of its values (Convex and strictly convex functions on Euclidean convex sets).

[F3]

A subset of a real vector space is convex when it contains every convex combination of any two of its points (A convex subset of $R^{m}$ contains every line segment between two of its points).

Proof

1.1F1givenalgebra

For each fixed pair $(i, j)$ , let $C_{i j} = (x_{i} - x_{j}) (x_{i} - x_{j})^{T}$ . By [F1], $q_{M} (x_{i}, x_{j}) = tr (M C_{i j})$ is linear in $M$ , so every pull term is affine-linear. Each margin expression $h_{i j l} (M) = 1 + tr (M (C_{i j} - C_{i l}))$ is also affine-linear.

2.1F2step 1.1algebra

For any affine-linear $h$ and $0 \leq t \leq 1$ , $h (t M + (1 - t) N) = t h (M) + (1 - t) h (N)$ . The number $t [h (M)]_{+} + (1 - t) [h (N)]_{+}$ is at least $0$ and at least $t h (M) + (1 - t) h (N)$ , hence it is at least their maximum $[h (t M + (1 - t) N)]_{+}$ . Thus each hinge term is convex by [F2].

3.1givenstep 1.1step 2.1F2algebra

Finite sums of affine-linear functions and convex hinge functions are convex, and the coefficients $1 - μ$ and $μ$ are nonnegative because $μ \in [0, 1]$ . Applying the convexity inequality term by term proves $F_{μ}$ is convex on all symmetric matrices, including the endpoint cases $μ = 0$ and $μ = 1$ .

4.1F3givenalgebra∎

If $M, N \in S_{+}^{d}$ and $0 \leq t \leq 1$ , then $t M + (1 - t) N$ is symmetric and for every $v$ , $v^{T} (t M + (1 - t) N) v = t v^{T} M v + (1 - t) v^{T} N v \geq 0$ . Hence $S_{+}^{d}$ is convex by [F3]. Restricting the already convex function $F_{μ}$ to this convex feasible set yields a convex optimization problem.

LemmaStatement: AI-adaptedProof: AI-adaptedOpen item page →

LMNN hinge subgradient formula and a uniform data-dependent bound

Statement

Fix the finite labeled sample, fixed target sets, and $μ \in [0, 1]$ of the LMNN objective. For each $j \in N_{i}$ and each impostor index $l$ with $y_{l} \neq y_{i}$ , set $C_{i j} = (x_{i} - x_{j}) (x_{i} - x_{j})^{T}$ , $D_{i j l} = C_{i j} - C_{i l}$ , and $h_{i j l} (M) = 1 + ⟨ M, D_{i j l} ⟩_{F}$ , where $⟨ A, B ⟩_{F} = \sum_{r, s} A_{r s} B_{r s}$ . Define $γ_{i j l} (M) = 1$ if $h_{i j l} (M) > 0$ and $γ_{i j l} (M) = 0$ if $h_{i j l} (M) \leq 0$ . Put

$G (M) = (1 - μ) \sum_{i} \sum_{j \in N_{i}} C_{i j} + μ \sum_{i} \sum_{j \in N_{i}} \sum_{l : y_{l} \neq y_{i}} γ_{i j l} (M) D_{i j l} .$

For the convex objective $F_{μ}$ on $S_{+}^{d}$ , a Frobenius subgradient at $M$ means a symmetric matrix $G$ such that $F_{μ} (N) \geq F_{μ} (M) + ⟨ G, N - M ⟩_{F}$ for every $N \in S_{+}^{d}$ . Then $G (M)$ is a subgradient at every $M \in S_{+}^{d}$ . Moreover, uniformly in $M$ ,

$∥ G (M) ∥_{F} \leq B_{d a t a} : = (1 - μ) \sum_{i} \sum_{j \in N_{i}} ∥ x_{i} - x_{j} ∥_{2}^{2} + μ \sum_{i} \sum_{j \in N_{i}} \sum_{l : y_{l} \neq y_{i}} (∥ x_{i} - x_{j} ∥_{2}^{2} + ∥ x_{i} - x_{l} ∥_{2}^{2}) .$

At an exact hinge kink $h_{i j l} (M) = 0$ , the selected subgradient coefficient is $0$ .

Statement references

Fixed-target pull/push objective

Convexity on the PSD cone

Subgradient inequality

Frobenius norm and its triangle inequality

Weinberger and Saul, §3.2, printed pp. 216–218, and Appendix A.1, pp. 238–239

Bubeck, §3.1, printed pp. 262–266

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

Facts & Assumptions

Given: The finite sample, fixed target sets and weight $μ$ in the Statement, and $M \in S_{+}^{d}$ .

[F1]

The objective is the finite weighted sum of linear pull terms and positive-part hinge terms with affine arguments (Fixed-target large-margin nearest-neighbor objective).

[F2]

The objective is convex on $S_{+}^{d}$ (The fixed-target LMNN objective is convex).

[F3]

A subgradient is a vector whose inner product gives a global supporting affine lower bound on the convex function (Subgradients and the subdifferential of a convex function).

[F4]

The Frobenius norm is the Euclidean entry norm and its triangle inequality follows from the inner-product norm theorem (The Frobenius norm $∥ A ∥_{F} = (\sum_{i, j} ∣ a_{i j} ∣^{2})^{1 / 2}$ on real or complex matrices, The inner-product norm is definite, homogeneous, and satisfies the triangle inequality).

[F5]

The Euclidean norm on $R^{d}$ satisfies $∥ a ∥_{2}^{2} = \sum_{r} a_{r}^{2}$ (The Euclidean inner product $⟨ x, y ⟩ = \sum_{k < n} x_{k} y_{k}$ on $R^{n}$ ).

Proof

1.1F1algebra

For $a_{i j} = x_{i} - x_{j}$ , the entrywise inner product satisfies $⟨ M, C_{i j} ⟩_{F} = \sum_{r, s} M_{r s} (a_{i j})_{r} (a_{i j})_{s} = a_{i j}^{T} M a_{i j} = q_{M} (x_{i}, x_{j})$ . Thus each hinge has the form $ϕ (M) = \max {0, 1 + ⟨ M, D_{i j l} ⟩_{F}}$ , with affine argument $h_{i j l} (M)$ .

1.2F4F5algebra

For any $a \in R^{d}$ , $∥ a a^{T} ∥_{F}^{2} = \sum_{r, s} (a_{r} a_{s})^{2} = (\sum_{r} a_{r}^{2})^{2}$ , so $∥ C_{i j} ∥_{F} = ∥ x_{i} - x_{j} ∥_{2}^{2}$ by [F5]. By [F4], $∥ D_{i j l} ∥_{F} \leq ∥ C_{i j} ∥_{F} + ∥ C_{i l} ∥_{F} = ∥ x_{i} - x_{j} ∥_{2}^{2} + ∥ x_{i} - x_{l} ∥_{2}^{2}$ .

2.1step 1.1algebra

If $h_{i j l} (M) > 0$ , then $ϕ (M) = h_{i j l} (M)$ and $ϕ (N) \geq h_{i j l} (N) = ϕ (M) + ⟨ D_{i j l}, N - M ⟩_{F}$ for every $N$ . If $h_{i j l} (M) \leq 0$ , then $ϕ (M) = 0$ and $ϕ (N) \geq 0 = ϕ (M) + ⟨ 0, N - M ⟩_{F}$ for every $N$ . Hence $γ_{i j l} (M) D_{i j l}$ is a subgradient of this hinge, including the selected zero coefficient at equality.

3.1step 1.1step 2.1F2F3algebra

Each $C_{i j}$ and $D_{i j l}$ is symmetric, so their weighted sum $G (M)$ is symmetric. Each pull term is linear with Frobenius subgradient $C_{i j}$ . Adding its supporting equality to the hinge supporting inequalities in step 2.1, weighted by the nonnegative coefficients $1 - μ$ and $μ$ , proves $F_{μ} (N) \geq F_{μ} (M) + ⟨ G (M), N - M ⟩_{F}$ for every $N \in S_{+}^{d}$ . Thus $G (M)$ is a subgradient by [F3].

4.1step 1.2givenF4algebra∎

Since each $γ_{i j l} (M) \in {0, 1}$ , the triangle inequality and step 1.2 give $∥ G (M) ∥_{F} \leq (1 - μ) \sum_{i} \sum_{j \in N_{i}} ∥ C_{i j} ∥_{F} + μ \sum_{i} \sum_{j \in N_{i}} \sum_{l : y_{l} \neq y_{i}} ∥ D_{i j l} ∥_{F} \leq B_{d a t a}$ . The bound is finite because the sample and all index sets are finite, and it is independent of $M$ .

AlgorithmAlgorithm: AI-adaptedProof: Not applicableOpen item page →

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

Definition

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

Initialize $z_{0} = svec (M_{0})$ . At each $t = 0, \dots, T - 1$ , put $M_{t} = {svec}^{- 1} (z_{t})$ and compute the Frobenius subgradient

$G_{t} = (1 - μ) \sum_{i} \sum_{j \in N_{i}} C_{i j} + μ \sum_{i} \sum_{j \in N_{i}} \sum_{l : y_{l} \neq y_{i}} γ_{i j l} (M_{t}) (C_{i j} - C_{i l}),$

where $C_{i j} = (x_{i} - x_{j}) (x_{i} - x_{j})^{T}$ , $h_{i j l} (M) = 1 + ⟨ M, C_{i j} - C_{i l} ⟩_{F}$ , $γ_{i j l} (M) = 1$ when $h_{i j l} (M) > 0$ , and $γ_{i j l} (M) = 0$ when $h_{i j l} (M) \leq 0$ . Supply the successful oracle response $(f (z_{t}), svec (G_{t}))$ to the finite-budget projected-subgradient method on $C^{'}$ with step size $η_{t}$ . It updates $z_{t + 1} = P_{C^{'}} (z_{t} - η_{t} svec (G_{t}))$ , where $P_{C^{'}}$ is the unique nearest point in the Euclidean norm. Equivalently, form $A_{t} = M_{t} - η_{t} G_{t}$ , choose an orthogonal eigendecomposition $A_{t} = U_{t} diag (λ_{t, 1}, \dots, λ_{t, d}) U_{t}^{T}$ , and set

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

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.

Definition references

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

TheoremStatement: AI-adaptedProof: AI-adaptedOpen item page →

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

Statement

Assume Countable Choice ${A C}_{ω}$ . Let $d, n, C$ be positive integers, let $(x_{i}, y_{i})_{i = 1}^{n}$ be a finite sample with $x_{i} \in R^{d}$ and $y_{i} \in {1, \dots, C}$ , let fixed target sets satisfy $N_{i} \subseteq {j \neq i : y_{j} = y_{i}}$ , and let $μ \in [0, 1]$ . For symmetric $M$ put $q_{M} (x, x^{'}) = (x - x^{'})^{T} M (x - x^{'})$ and

$F_{μ} (M) = (1 - μ) \sum_{i} \sum_{j \in N_{i}} q_{M} (x_{i}, x_{j}) + μ \sum_{i} \sum_{j \in N_{i}} \sum_{l : y_{l} \neq y_{i}} [1 + q_{M} (x_{i}, x_{j}) - q_{M} (x_{i}, x_{l})]_{+},$

where $[z]_{+} = \max {z, 0}$ , and minimize over $S_{+}^{d} = {M = M^{T} : v^{T} M v \geq 0 for every v \in R^{d}}$ . Let $T \geq 1$ be an integer, choose $M_{0} \in S_{+}^{d}$ and step sizes $η_{0}, \dots, η_{T - 1} > 0$ , and suppose a global minimizer $M^{*} \in S_{+}^{d}$ of $F_{μ}$ exists. For each $t < T$ , put $C_{i j} = (x_{i} - x_{j}) (x_{i} - x_{j})^{T}$ , $h_{i j l} (M) = 1 + ⟨ M, C_{i j} - C_{i l} ⟩_{F}$ , and $γ_{i j l} (M) = 1$ if $h_{i j l} (M) > 0$ and $0$ if $h_{i j l} (M) \leq 0$ . Form

$G_{t} = (1 - μ) \sum_{i} \sum_{j \in N_{i}} C_{i j} + μ \sum_{i} \sum_{j \in N_{i}} \sum_{l : y_{l} \neq y_{i}} γ_{i j l} (M_{t}) (C_{i j} - C_{i l}), M_{t} - η_{t} G_{t} = U_{t} diag (λ_{t, 1}, \dots, λ_{t, d}) U_{t}^{T},$

where $U_{t}$ is orthogonal, and define

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

Set

$A_{T} = \sum_{t = 0}^{T - 1} η_{t}, {\overline{M}}_{T} = \frac{1}{A_{T}} \sum_{t = 0}^{T - 1} η_{t} M_{t},$

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

$B_{d a t a} = (1 - μ) \sum_{i} \sum_{j \in N_{i}} ∥ x_{i} - x_{j} ∥_{2}^{2} + μ \sum_{i} \sum_{j \in N_{i}} \sum_{l : y_{l} \neq y_{i}} (∥ x_{i} - x_{j} ∥_{2}^{2} + ∥ x_{i} - x_{l} ∥_{2}^{2}), R = ∥ M_{0} - M^{*} ∥_{F},$

where $∥ z ∥_{2} = (\sum_{r = 1}^{d} z_{r}^{2})^{1 / 2}$ and $∥ \cdot ∥_{F}$ is the entry-sum Frobenius norm.

Then $A_{T} > 0$ , $M_{b e s t}, {\overline{M}}_{T} \in S_{+}^{d}$ , and

$\max {F_{μ} (M_{b e s t}) - F_{μ} (M^{*}), F_{μ} ({\overline{M}}_{T}) - F_{μ} (M^{*})} \leq \frac{R^{2} + B_{d a t a}^{2} \sum_{t = 0}^{T - 1} η_{t}^{2}}{2 A_{T}} .$

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.

Statement references

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

Facts & Assumptions

Given: The data and objective in the Statement, ${A C}_{ω}$ , an attained minimizer $M^{*}$ , the finite projected-subgradient procedure, and its positive step sizes.

[A1]

Countable Choice selects one element from each member of a countable family of nonempty sets (The Axiom of Countable Choice ( ${A C}_{ω}$ )).

[F1]

The finite target objective is convex on $S_{+}^{d}$ , and this cone is convex (The fixed-target LMNN objective is convex).

[F2]

The real positive-semidefinite cone is closed in the Frobenius metric (The real positive-semidefinite cone is closed in the Frobenius metric).

[F3]

Symmetric vectorization is a linear inner-product isometry to $R^{m}$ and transports closed convex domains and subgradients (Symmetric matrices are Euclidean under the Frobenius norm, Symmetric vectorization transports closed convex domains and subgradients).

[F4]

Euclidean space $R^{m}$ is complete and hence a real Hilbert space under its Euclidean inner product ( $R$ and $R^{n}$ for $n \geq 1$ with the Euclidean metric are complete, componentwise from the Cauchy criterion in $R$ , Hilbert space, The Euclidean inner product $⟨ x, y ⟩ = \sum_{k < n} x_{k} y_{k}$ on $R^{n}$ ).

[F5]

Under Countable Choice, every point of a real Hilbert space has a unique nearest point in each nonempty closed convex set (Projection onto a nonempty closed convex set).

[F6]

The local subgradient formula returns valid subgradients and satisfies $∥ G (M_{t}) ∥_{F} \leq B_{d a t a}$ for every iterate (LMNN hinge subgradient formula and a uniform data-dependent bound).

[F7]

The finite-budget projected-subgradient method updates $z_{t + 1} = P_{C^{'}} (z_{t} - η_{t} g_{t})$ and records its finite status, final iterate, weighted average, and least-index best observed point (Projected subgradient method with finite budget).

[F8]

For a convex objective on a nonempty closed convex Euclidean domain, a finite projected-subgradient run with valid bounded subgradients, an attained minimizer, and an initial-distance bound satisfies the stated best-observed and weighted-average gap estimate (Projected subgradient best-iterate and weighted-average bound).

[F9]

The explicit eigenvalue-clipping update is the unique Frobenius projection onto $S_{+}^{d}$ (Frobenius projection onto the positive-semidefinite cone is spectral clipping).

Proof

1.1A1F1F2F3F4F5F7F9given

Put $m = d (d + 1) / 2$ and $C^{'} = svec (S_{+}^{d})$ . The cone contains $0$ ; [F1] makes it convex, [F2] makes it closed in Frobenius distance, and [F3] transfers both properties to $C^{'}$ . By [F4], $R^{m}$ is a real Hilbert space; under [A1], [F5] gives a unique Euclidean projection onto $C^{'}$ , which is the projection used in [F7]. The explicit matrix update is that projection because [F9] identifies the unique Frobenius-nearest PSD matrix.

1.2F3F6F7given

For every $t < T$ , the displayed data formula in [F6] computes $G (M_{t})$ and its bound. The coordinate transport [F3] makes $svec (G (M_{t}))$ a Euclidean subgradient of $f = F_{μ} \circ {svec}^{- 1}$ with norm $∥ svec (G (M_{t})) ∥_{2} = ∥ G (M_{t}) ∥_{F} \leq B_{d a t a}$ . Thus all $T$ oracle calls in [F7] are valid.

1.3F3F7F8givenalgebra

The point $M^{*}$ maps to a global minimizer $z^{*} = svec (M^{*})$ of $f$ on $C^{'}$ , the initial point satisfies $∥ z_{0} - z^{*} ∥_{2} = R$ , and the positive step sizes give $A_{T} > 0$ . Apply [F8] to the generic run with $N = T$ , subgradient bound $B_{d a t a}$ , and distance bound $R$ . It yields the asserted upper bound for the least-index best observed objective gap and the weighted-average objective gap in Euclidean coordinates.

2.1step 1.3F1F3algebra∎

By linearity of ${svec}^{- 1}$ , the Euclidean weighted average maps to ${\overline{M}}_{T}$ as defined in the Statement. Each iterate lies in $S_{+}^{d}$ , so convexity [F1] puts ${\overline{M}}_{T}$ there; bijectivity also preserves the finite-list minimum, so the Euclidean bound from step 1.3 is exactly the displayed matrix bound.

Remarks

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 ${A C}_{ω}$ , not the full Axiom of Choice. The hypothesis that $M^{*}$ exists is essential to this stated application and is not derived from convexity alone.

4 · Examples, counterexamples and false statements

None yet.

Nearest neighbors and learned metrics

2 · Logical flowchart

3 · Definitions, theorems and proofs

Mahalanobis pseudometric induced by a positive-semidefinite matrix

Definition

Definition references

Symmetric matrices are Euclidean under the Frobenius norm

Statement

Statement references

Facts & Assumptions

Proof

Frobenius projection onto the positive-semidefinite cone is spectral clipping

Statement

Statement references

Facts & Assumptions

Proof

Remarks

The real positive-semidefinite cone is closed in the Frobenius metric

Statement

Statement references

Facts & Assumptions

Proof

Finite-sample k-nearest-neighbor classifier with fixed tie-breaking

Definition

Definition references

Fixed-target large-margin nearest-neighbor objective

Definition

Definition references

The Mahalanobis distance is a pseudometric and comes from a linear feature map

Statement

Statement references

Facts & Assumptions

Proof

Symmetric vectorization transports closed convex domains and subgradients

Statement

Statement references

Facts & Assumptions

Proof

The fixed-target LMNN objective is convex

Statement

Statement references

Facts & Assumptions

Proof

LMNN hinge subgradient formula and a uniform data-dependent bound

Statement

Statement references

Facts & Assumptions

Proof

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

Definition

Definition references

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

Statement

Statement references

Facts & Assumptions

Proof

Remarks

4 · Examples, counterexamples and false statements

Sources