TheoremStatement: AI-adaptedProof: AI-adaptedPipeline-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.

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.

Depends on

Used by

Dependency tree · two levels

22 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Kilian Q. Weinberger and Lawrence K. Saul, Distance Metric Learning for Large Margin Nearest Neighbor Classification, JMLR 10 (2009), 207–244 (standard reference, not scraped)
Aurélien Bellet, Amaury Habrard, and Marc Sebban, A Survey on Metric Learning for Feature Vectors and Structured Data, arXiv:1306.6709v4 (2014) (standard reference, not scraped)