Alphabeta Math
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.

A smooth quadratic loss without global Lipschitzness has unbounded stability

Example

Let the instance space be {∗} with its full sigma-algebra, let the label and action spaces be R with their Borel sigma-algebras, take P to be the point mass at 0, use predictors fw(∗)=w, and use loss ℓ(u,y)=12(u−y)2. For w,y∈R, write g(w,(∗,y))=ℓ(fw(∗),y)=12(w−y)2. For sample size n=1, start at w0=0, use I1=1 and α1=1/2, and set w1=w0−α1∂wg(w0,ZI1). For every a∈R, compare the neighboring samples Sa=((∗,a)) and S0=((∗,0)) at test observation z0=(∗,0). Their output losses differ by a2/8. Since a is arbitrary, this procedure has no finite uniform replacement stability coefficient. The loss is convex and its gradient is 1-Lipschitz but its values are not globally Lipschitz in w, so this example lies outside the convex SGD theorem's hypotheses and is not a counterexample to that theorem.

Example references

Uniform stability for randomized learning rules defines the finite replacement-stability requirement.

Expected generalization of convex stochastic gradient training requires global Lipschitzness of the per-example loss.

Hardt, Recht, and Singer, arXiv-version Theorem 3.8 (conference Theorem 3.7): full arXiv paper.

Facts & Assumptions

Given: The singleton instance space, quadratic loss, one-step update, neighboring samples, and test observation in the Example.

[F1]

Uniform stability for randomized learning rules: a finite stability coefficient must bound the expected test-loss difference for every pair of samples differing in at most one coordinate and every test observation.

[F2]

Expected generalization of convex stochastic gradient training: the convex SGD guarantee requires a finite global value-Lipschitz constant for every per-example loss.

Verification

1.1givenconstructalgebra

For any w,y and increment h, g(w+h,(∗,y))−g(w,(∗,y))=h(w−y)+h2/2, so the difference quotient tends to w−y and ∂wg(w,(∗,y))=w−y. Thus for Sa=((∗,a)) the first update is w1(Sa)=0−12(0−a)=a/2, while for S0 it is w1(S0)=0.

2.1F1step 1.1givenalgebra

At test observation z0=(∗,0), g(w1(Sa),z0)=12(a/2)2=a2/8 and g(w1(S0),z0)=0. As ∣a∣→∞ the absolute difference is unbounded, contradicting any finite uniform coefficient by [F1].

3.1F2givenstep 1.1algebra∎

By step 1.1, ∣∂wg(w,(∗,y))−∂wg(v,(∗,y))∣=∣w−v∣, so its gradient is 1-Lipschitz. For 0≤t≤1, direct expansion gives (1−t)g(w,(∗,y))+tg(v,(∗,y))−g((1−t)w+tv,(∗,y))=t(1−t)(w−v)2/2≥0, so it is convex. But for y=0, ∣g(w,(∗,0))−g(0,(∗,0))∣/∣w∣=∣w∣/2 for w≠0, which is unbounded. Thus no finite global Lipschitz constant exists, and [F2] does not apply.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

20 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