LemmaStatement: AI-adaptedProof: AI-generatedPipeline-generatedprecheck passjudge 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.

Limits of approximate margin-KKT points under MFCQ

Statement

Let $N, d \geq 1$ and let $q_{1}, \dots, q_{N} : R^{d} \to R$ be locally Lipschitz. Let $θ_{*}$ be feasible for $q_{i} (θ) \geq 1$ and satisfy MFCQ in the margin convention. Suppose that for every $ε > 0$ there is a feasible $θ_{ε}$ with $∥ θ_{ε} - θ_{*} ∥_{2} \leq ε$ and multipliers/subgradients witnessing that $θ_{ε}$ is an $(ε, ε)$ -approximate Clarke KKT point. Then $θ_{*}$ is a Clarke KKT point.

Statement references

Clarke subdifferential and closed-graph convention

Approximate margin-KKT and MFCQ definitions

Kaifeng Lyu and Jian Li, Gradient Descent Maximizes the Margin of Homogeneous Neural Networks, Appendix C.1, Theorem C.4

Matus Telgarsky, Deep Learning Theory lecture notes, §9.1

Facts & Assumptions

Given: Locally Lipschitz margins, a feasible point satisfying MFCQ, and for every tolerance a nearby feasible approximate KKT witness with stationarity and complementarity errors no larger than that tolerance.

[F1]

Clarke subdifferential and gradient-flow trajectory: Clarke subdifferentials are compact, locally bounded, and have closed graph; for fixed $v$ , their support function $q_{i}^{\circ} (θ; v)$ is upper semicontinuous in $θ$ .

[F2]

KKT conditions and MFCQ for margin constraints: approximate KKT supplies nonnegative multipliers, subgradients, and the two error bounds; exact KKT is the corresponding zero-error stationarity and complementary-slackness condition.

[F3]

For a nonempty subset of $R^{n}$ with $n \geq 1$ , compactness, closedness and boundedness, pseudocompactness, and attainment of extrema by every continuous real-valued function are equivalent: closed bounded subsets of finite-dimensional Euclidean space are compact.

Proof

technique · bound all approximate witnesses uniformly with the MFCQ direction, then apply the finite-intersection property to nested compact sets of witnesses

1.1F1F2givenalgebra

Let $I = {i : q_{i} (θ_{*}) = 1}$ . If $I = \emptyset$ , every constraint has positive slack near $θ_{*}$ . Local boundedness in [F1] gives a common bound $M$ on all nearby subgradients. For any sufficiently small $ε$ , the approximate witness in [F2] satisfies $λ_{i} \leq ε / c_{i}$ for positive local slack bounds $c_{i}$ , so its stationarity residual gives $∥ θ_{*} ∥_{2} \leq 2 ε + M ε \sum_{i} c_{i}^{- 1}$ . This holds for every small $ε$ , hence $θ_{*} = 0$ ; setting all exact multipliers to zero gives KKT.

1.2F1F2givenconstructalgebra

Suppose $I \neq \emptyset$ . By MFCQ choose $v$ and let $c > 0$ be a common lower bound for $⟨ h, v ⟩$ over active $i$ and $h \in \partial^{\circ} q_{i} (θ_{*})$ ; such a bound exists by compactness and finiteness. Then $q_{i}^{\circ} (θ_{*}; - v) \leq - c$ for each active $i$ . Upper semicontinuity in [F1] gives a neighborhood where every active subgradient satisfies $⟨ h, v ⟩ \geq c / 2$ . Shrink it so each inactive constraint has slack at least $c_{i} > 0$ and all subgradients are bounded by $M$ . For any sufficiently small $ε$ , the approximate witness has $λ_{i} \leq ε / c_{i}$ for inactive $i$ . Dotting its stationarity equation with $v$ therefore bounds the sum of active multipliers by $\frac{2}{c} ((∥ θ_{*} ∥_{2} + 2 ε) ∥ v ∥_{2} + M ∥ v ∥_{2} ε \sum_{i \notin I} c_{i}^{- 1})$ . Thus, for all sufficiently small $ε$ , all multipliers and subgradients in every witness are uniformly bounded.

2.1F1F2F3step 1.2construct

Choose an integer $m_{0}$ large enough that every approximate witness with $ε = 1 / m$ for $m \geq m_{0}$ lies in a fixed closed bounded box $B$ of the finite-dimensional space of parameters, multipliers, and subgradients, using step 1.2. For each $m \geq m_{0}$ , let $K_{m} \subseteq B$ consist of feasible witnesses with $∥ θ - θ_{*} ∥_{2} \leq 1 / m$ , stationarity residual at most $1 / m$ , and aggregate complementarity residual at most $1 / m$ . The hypothesis makes every $K_{m}$ nonempty; continuity and the closed-graph property in [F1] make it closed. Hence each $K_{m}$ is compact by [F3], and $K_{m + 1} \subseteq K_{m}$ .

3.1F1F2F3step 2.1algebra∎

The nested family $(K_{m})_{m \geq m_{0}}$ has the finite-intersection property, since every finite intersection equals its largest-index member. Compactness of $K_{m_{0}}$ therefore makes $⋂_{m \geq m_{0}} K_{m}$ nonempty. Any tuple in this intersection has $θ = θ_{*}$ , zero stationarity residual, and zero complementarity residual, because each corresponding norm/error is at most $1 / m$ for every $m$ . It is consequently an exact Clarke KKT witness by [F2]. This argument selects one point from one nonempty intersection and uses no choice principle.

Depends on

Used by

Homogeneous gradient-flow limit points satisfy margin KKT conditions Theorem

Dependency tree · two levels

10 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

Kaifeng Lyu and Jian Li, Gradient Descent Maximizes the Margin of Homogeneous Neural Networks, Appendix C.1, Theorem C.4 (standard reference, not scraped)
Matus Telgarsky, Deep Learning Theory lecture notes, §9.1 (standard reference, not scraped)