ExampleConstruction: AI-generatedVerification: AI-generatedPipeline-generatedjudge pass (gpt-6-luna)

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.

One decreasing LMNN projection step is not a convergence certificate

Example

Take $d = 1$ , $n = 2$ , one class with labels $y_{1} = y_{2} = 1$ , sample points $x_{1} = 0$ , $x_{2} = 1$ , fixed target sets $N_{1} = {2}$ and $N_{2} = {1}$ , and $μ = 0$ . For every feasible scalar matrix $M = [m]$ with $m \geq 0$ , the fixed-target objective is $F_{0} ([m]) = 2 m$ and has minimum $0$ at $M = [0]$ . Start from $M_{0} = [2]$ , use one update $T = 1$ and step size $η_{0} = \frac{1}{4}$ . The finite projected-subgradient method returns $M_{1} = [\frac{3}{2}]$ and reduces the objective from $4$ to $3$ , but the returned point is still strictly suboptimal. Thus a decreasing finite step does not certify convergence or optimality.

Example references

Fixed-target LMNN objective

LMNN subgradient at the selected iterate

Finite projected-subgradient update

Facts & Assumptions

Given: The two-point sample, the target sets, $μ = 0$ , the initial matrix, and the single stepsize in the Example.

[F1]

The pull term is the sum of squared Mahalanobis distances over fixed targets, the push term sums only over differently labeled impostors, and $F_{μ} = (1 - μ) ϵ_{p u l l} + μ ϵ_{p u s h}$ (Fixed-target large-margin nearest-neighbor objective).

[F2]

At an exact projected-subgradient step, use the explicit formula for $G (M)$ , taking hinge coefficient zero at a kink (LMNN hinge subgradient formula and a uniform data-dependent bound).

[F3]

The update is $M_{t + 1}$ equal to Frobenius projection of $M_{t} - η_{t} G_{t}$ onto the PSD cone, equivalently eigenvalue clipping (Finite-budget projected-subgradient training for fixed-target LMNN).

Verification

1.1givenF1algebra

For a scalar feasible matrix $M = [m]$ , $q_{M} (0, 1) = q_{M} (1, 0) = m$ . Since the labels agree, there are no impostor terms; hence $F_{0} ([m]) = 2 m$ , which is minimized over $m \geq 0$ at $m = 0$ . Therefore $F_{0} (M_{0}) = 4$ .

1.2givenF2F3algebra

The two pull matrices are both $[1]$ , and $μ = 0$ , so the selected subgradient is $G_{0} = [2]$ by [F2]. The update [F3] clips $M_{0} - η_{0} G_{0} = [2 - \frac{1}{4} \cdot 2] = [\frac{3}{2}]$ to the PSD cone, leaving $M_{1} = [\frac{3}{2}]$ .

2.1step 1.1step 1.2algebra∎

Then $F_{0} (M_{1}) = 3 < 4 = F_{0} (M_{0})$ , but $F_{0} (M_{1}) = 3 > 0 = F_{0} ([0])$ . Thus the step decreases the objective while the finite returned iterate is still suboptimal, so this step supplies no convergence or optimality certificate.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

18 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.