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

Strongly convex RKHS regularized ERM is stable

Statement

Let $(X, Σ_{X})$ and $(Y, Σ_{Y})$ be nonempty measurable instance and label spaces. Let $κ \geq 0$ , and let $H$ be a real Hilbert space of $Σ_{X}$ -measurable real-valued functions on $X$ with kernel sections $K_{x} \in H$ satisfying $f (x) = ⟨ f, K_{x} ⟩_{H}$ and $∥ K_{x} ∥_{H}^{2} = K (x, x) \leq κ^{2}$ for every $x \in X$ . Let $λ > 0$ and $σ \geq 0$ , and let $c : R \times Y \to [0, \infty)$ be measurable with respect to $B (R) \otimes Σ_{Y}$ , convex in its first argument, and $σ$ -Lipschitz there, meaning $∣ c (u, y) - c (v, y) ∣ \leq σ ∣ u - v ∣$ for all $u, v \in R$ and $y \in Y$ . For every $n \geq 1$ , every indexed sample $S = ((x_{1}, y_{1}), \dots, (x_{n}, y_{n}))$ , and every retained index set $J \subseteq [n]$ , define $A_{n, J}$ as the unique attained minimizer over $f \in H$ of

\frac{1}{n} \sum_{j \in J} c (f (x_{j}), y_{j}) + λ ∥ f ∥_{H}^{2} .

Assume every such minimum is attained. For a size- $m$ sample, write $A_{S} : = A_{m, [m]} (S)$ and $A_{S ∖ i} : = A_{m, [m] ∖ {i}} (S ∣_{[m] ∖ {i}})$ , so the deleted objective retains the original denominator $m$ . Then the resulting size-indexed rule is permutation-invariant and has uniform deletion stability

$\sup_{S \in (X \times Y)^{m}, 1 \leq i \leq m, (x, y) \in X \times Y} ∣ c (A_{S} (x), y) - c (A_{S ∖ i} (x), y) ∣ \leq β_{m}, β_{m} : = \frac{σ^{2} κ^{2}}{2 λ m} .$

For fixed $λ$ , this stability envelope is nonincreasing in $m$ . The conclusion supplies no uniform bounded-loss constant $M$ ; any such hypothesis for a concentration bound must be checked separately.

Statement references

Bousquet and Elisseeff, equations (19)–(20), Lemmas 20–21, and Theorem 22 with proof, printed pp. 512–515; equation (20) keeps denominator $m$ after deletion. Full JMLR paper PDF

Mohri, Rostamizadeh, and Talwalkar, Proposition 14.4 with proof, printed pp. 337–339; this gives the corresponding replacement-stability coefficient, with its distinct convention. Full second-edition book PDF

Facts & Assumptions

Given: A supervised sample space, the stated RKHS evaluation property and diagonal bound, a convex $σ$ -Lipschitz loss, $λ > 0$ , and attained full-sample and fixed-denominator deletion minimizers.

[F1]

Uniform deletion stability is the bound on loss change between the full output and the size-indexed deleted output, uniformly over samples, deleted indices, and test observations. Uniform algorithmic stability under deletion

[F2]

In a real inner product space, $∣ ⟨ u, v ⟩ ∣ \leq ∥ u ∥ ∥ v ∥$ . Cauchy–Schwarz: $∣ ⟨ u, v ⟩ ∣ \leq ∥ u ∥ ∥ v ∥$ , with equality exactly for linearly dependent vectors

[A1]

For each sample and deleted index, both displayed objectives attain their minima; the deletion objective uses the same denominator $m$ as the full-sample objective.

Proof

1.1givenA1algebra

Write $F (f) = m^{- 1} \sum_{j = 1}^{m} c (f (x_{j}), y_{j}) + λ ∥ f ∥_{H}^{2}$ and $G (f) = m^{- 1} \sum_{j \neq i} c (f (x_{j}), y_{j}) + λ ∥ f ∥_{H}^{2}$ , with minimizers $f = A_{S}$ and $g = A_{S ∖ i}$ . For any convex $Q$ and $J_{Q} (h) = Q (h) + λ ∥ h ∥^{2}$ , the identity $∥ (1 - t) u + t v ∥^{2} = (1 - t) ∥ u ∥^{2} + t ∥ v ∥^{2} - t (1 - t) ∥ u - v ∥^{2}$ and convexity of $Q$ give $J_{Q} ((1 - t) u + t v) \leq (1 - t) J_{Q} (u) + t J_{Q} (v) - λ t (1 - t) ∥ u - v ∥^{2}$ . If $u$ minimizes $J_{Q}$ , then $J_{Q} (u) \leq J_{Q} ((1 - t) u + t v)$ ; subtracting $(1 - t) J_{Q} (u)$ , dividing by $t > 0$ , and letting $t ↓ 0$ yields $J_{Q} (v) - J_{Q} (u) \geq λ ∥ u - v ∥^{2}$ . Applying this to every retained-set objective shows that each minimizer is unique. Each objective is unchanged by simultaneous reordering of the observations and relabeling of the retained indices, so the family is permutation-invariant. Apply the same gap inequality to $F$ at $f$ with $v = g$ and to $G$ at $g$ with $v = f$ .

2.1A1F2step 1.1algebra

Adding the two inequalities from step 1.1 cancels all common loss terms and both regularizers except the deleted observation, so $2 λ ∥ f - g ∥_{H}^{2} \leq F (g) - F (f) + G (f) - G (g) = m^{- 1} [c (g (x_{i}), y_{i}) - c (f (x_{i}), y_{i})] \leq σ ∣ g (x_{i}) - f (x_{i}) ∣ / m$ . The RKHS identity in the Statement and [F2] give $∣ g (x_{i}) - f (x_{i}) ∣ = ∣ ⟨ g - f, K_{x_{i}} ⟩ ∣ \leq κ ∥ g - f ∥_{H}$ . If $f = g$ the desired norm bound is immediate; otherwise dividing by $2 λ ∥ f - g ∥_{H}$ yields $∥ f - g ∥_{H} \leq σ κ / (2 λ m)$ .

3.1givenA1F1step 2.1algebra∎

For any test pair $(x, y)$ , $σ$ -Lipschitzness and the reproducing-kernel estimate give $∣ c (f (x), y) - c (g (x), y) ∣ \leq σ ∣ ⟨ f - g, K_{x} ⟩ ∣ \leq σ κ ∥ f - g ∥_{H} \leq σ^{2} κ^{2} / (2 λ m)$ . Taking the supremum over samples, deleted indices, and test pairs gives the stated stability coefficient. Since $1 / m$ decreases with $m$ for fixed positive $λ$ , the displayed envelope is nonincreasing.

Depends on

Used by

Absolute-loss RKHS regularization has an explicit stability envelope Example

Dependency tree · two levels

7 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

Olivier Bousquet and André Elisseeff, Stability and Generalization, JMLR 2 (2002), equations (19)–(20), Lemmas 20–21, Theorem 22 (standard reference, not scraped)
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar, Foundations of Machine Learning, 2nd ed., Proposition 14.4 (standard reference, not scraped)