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

The perceptron makes at most R squared over gamma squared mistakes

Statement

Let $((x_{i}, y_{i}))_{i = 1}^{n}$ be a finite ordered sample with $n \geq 1$ , $x_{i} \in R^{d}$ , and $y_{i} \in {- 1, + 1}$ . Put ${\tilde{x}}_{i} = (x_{i}, 1) \in R^{d + 1}$ , with Euclidean inner product $⟨ u, v ⟩ = u^{T} v$ and norm $∥ u ∥_{2} = (u^{T} u)^{1 / 2}$ . Suppose $∥ {\tilde{x}}_{i} ∥_{2} \leq R$ for every $i$ and there is a unit vector $u \in R^{d + 1}$ and $γ > 0$ such that $y_{i} ⟨ u, {\tilde{x}}_{i} ⟩ \geq γ$ for every $i$ . The zero-initialized cyclic procedure that visits the sample in the stated order and updates $w \leftarrow w + y_{i} {\tilde{x}}_{i}$ whenever $y_{i} ⟨ w, {\tilde{x}}_{i} ⟩ \leq 0$ makes at most $R^{2} / γ^{2}$ updates and stops after a finite pass with no updates. At each visit, before its update, the procedure predicts $+ 1$ if $⟨ w, {\tilde{x}}_{i} ⟩ > 0$ and $- 1$ otherwise; a prediction mistake is a visit on which this prediction differs from $y_{i}$ . The total number of such mistakes before termination is at most $R^{2} / γ^{2}$ . The returned weight vector has strictly positive signed margin on every sample point.

Statement references

The cyclic perceptron update procedure

Cauchy–Schwarz: $∣ ⟨ u, v ⟩ ∣ \leq ∥ u ∥ ∥ v ∥$ , with equality exactly for linearly dependent vectors

Hastie, Tibshirani, and Friedman, ESL, §4.5.1 and Exercise 4.6

Cornell CS4780 Spring 2018, Lecture 3, “Perceptron Convergence”

Facts & Assumptions

Given: A finite ordered sample, the augmented vectors ${\tilde{x}}_{i}$ , the bounds $∥ {\tilde{x}}_{i} ∥_{2} \leq R$ , a unit separator $u$ with signed margin at least $γ > 0$ , and the zero-initialized cyclic procedure in the Statement.

[F1]

The algorithm initializes $w = 0$ , predicts $+ 1$ when $⟨ w, {\tilde{x}}_{i} ⟩ > 0$ and $- 1$ otherwise, updates $w \leftarrow w + y_{i} {\tilde{x}}_{i}$ exactly when $y_{i} ⟨ w, {\tilde{x}}_{i} ⟩ \leq 0$ , and stops after a full pass with no updates. The cyclic perceptron update procedure

[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

Proof

1.1givenF1algebra

After each update on point $i$ , the separator progress changes by $⟨ u, w + y_{i} {\tilde{x}}_{i} ⟩ - ⟨ u, w ⟩ = y_{i} ⟨ u, {\tilde{x}}_{i} ⟩ \geq γ$ . Starting at zero, after $M$ updates $⟨ u, w_{M} ⟩ \geq M γ$ .

1.2F1givenalgebra

At an update, [F1] gives $y_{i} ⟨ w, {\tilde{x}}_{i} ⟩ \leq 0$ and $y_{i}^{2} = 1$ , so $∥ w + y_{i} {\tilde{x}}_{i} ∥_{2}^{2} = ∥ w ∥_{2}^{2} + 2 y_{i} ⟨ w, {\tilde{x}}_{i} ⟩ + ∥ {\tilde{x}}_{i} ∥_{2}^{2} \leq ∥ w ∥_{2}^{2} + R^{2}$ . Since $w_{0} = 0$ , after $M$ updates $∥ w_{M} ∥_{2}^{2} \leq M R^{2}$ .

2.1step 1.1step 1.2F2givenalgebra

If $M = 0$ , the bound is immediate. If $M > 0$ , [F2] and $∥ u ∥_{2} = 1$ give $M γ \leq ⟨ u, w_{M} ⟩ \leq ∥ w_{M} ∥_{2} \leq \sqrt{M} R$ , whence $M \leq R^{2} / γ^{2}$ . Thus only finitely many updates occur.

3.1F1step 2.1algebra∎

At a visit to point $i$ , if $y_{i} = + 1$ and the classifier is wrong, its score is at most zero; if $y_{i} = - 1$ and the classifier is wrong, its score is positive. In either case $y_{i} ⟨ w, {\tilde{x}}_{i} ⟩ \leq 0$ , so every prediction mistake triggers an update by [F1]. Thus the number of mistakes is at most the number of updates and is bounded by step 2.1. An infinite run would complete infinitely many passes, each with at least one update; that would contradict the finite update bound. Therefore a pass with no updates occurs, and during that pass every point has strictly positive signed margin because the update test is $\leq 0$ . The algorithm stops and returns a training-separating weight vector.

Depends on

Used by

Nothing in the library uses this result yet.

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

Hastie, Tibshirani, and Friedman, The Elements of Statistical Learning, 2nd ed., corrected 12th printing (standard reference, not scraped)
Cornell CS4780 Spring 2018, Lecture 3: The Perceptron (standard reference, not scraped)