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

AdaBoost's exponential training-loss and nonpositive-margin bound

Statement

Let $M \geq 0$ be a finite sequence of completed rounds of finite-sample AdaBoost.M1, with weighted errors $0 < e_{m} < 1 / 2$ , scores $F_{M} (x) = \sum_{m = 1}^{M} a_{m} h_{m} (x)$ , and $Z_{m} = 2 \sqrt{e_{m} (1 - e_{m})}$ . Then

$\sum_{i = 1}^{N} e^{- y_{i} F_{M} (x_{i})} = N \prod_{m = 1}^{M} Z_{m}$

and

$\frac{1}{N} \sum_{i = 1}^{N} 1 {y_{i} F_{M} (x_{i}) \leq 0} \leq \prod_{m = 1}^{M} Z_{m} .$

The empty product for $M = 0$ is $1$ . Under the algorithm's $+ 1$ tie rule, the empirical classification error is also at most this product. This is a finite training-margin bound only and makes no test-generalization claim.

Statement references

Trevor Hastie, Robert Tibshirani, and Jerome Friedman, The Elements of Statistical Learning, 2nd ed., §10.4, equations (10.8)–(10.15), printed pp. 343–344

Robert E. Schapire, “The Boosting Approach to Machine Learning: An Overview,” §3, equations (2)–(6), PDF pp. 4–5

Facts & Assumptions

Given: A fixed finite binary-labeled sample and a finite sequence of completed rounds with $0 < e_{m} < 1 / 2$ .

[F1]

Finite-sample AdaBoost.M1 with half-log coefficients: The initialization is $w_{i}^{(1)} = 1 / N$ and $F_{0} = 0$ .

[F2]

Finite-sample AdaBoost.M1 with half-log coefficients: The weighted error is $e_{m} = \sum_{i = 1}^{N} w_{i}^{(m)} 1 {h_{m} (x_{i}) \neq y_{i}}$ .

[F3]

Finite-sample AdaBoost.M1 with half-log coefficients: For $0 < e_{m} < 1 / 2$ , $a_{m} = \frac{1}{2} \log \frac{1 - e_{m}}{e_{m}}$ and $Z_{m} = 2 \sqrt{e_{m} (1 - e_{m})}$ .

[F4]

Finite-sample AdaBoost.M1 with half-log coefficients: The update is $w_{i}^{(m + 1)} = w_{i}^{(m)} \exp (- a_{m} y_{i} h_{m} (x_{i})) / Z_{m}$ and $F_{m} (x) = F_{m - 1} (x) + a_{m} h_{m} (x)$ .

[F5]

Finite-sample AdaBoost.M1 with half-log coefficients: The classifier uses ${sign}_{+} (u) = + 1$ for $u \geq 0$ and $- 1$ for $u < 0$ , so ties are assigned to $+ 1$ .

Proof

1.1givenF1F2F3F4algebrainduction

The initial weights sum to $1$ by [F1]. Inductively assume the weights at round $m$ sum to $1$ ; by [F2], the total weights on correct and incorrect examples are $1 - e_{m}$ and $e_{m}$ . For a temporary coefficient $a \geq 0$ , the exponential reweighting sum is $q_{m} (a) = (1 - e_{m}) e^{- a} + e_{m} e^{a}$ . Its second derivative is positive, and $q_{m}^{'} (a) = e_{m} e^{a} - (1 - e_{m}) e^{- a}$ vanishes uniquely at $a = \frac{1}{2} \log ((1 - e_{m}) / e_{m}) > 0$ , which equals the algorithm's coefficient by [F3]. Substitution gives $q_{m} (a_{m}) = 2 \sqrt{e_{m} (1 - e_{m})} = Z_{m}$ . By [F4], the next weights divide the reweighted terms by this exact sum, so they also sum to $1$ . Induction proves normalization at every round and the stated minimization formula.

2.1F1F4step 1.1inductionalgebra

Put $S_{m} = \sum_{i} e^{- y_{i} F_{m} (x_{i})}$ . By [F1], $S_{0} = N$ and $w_{i}^{(1)} = e^{- y_{i} F_{0} (x_{i})} / S_{0}$ . If $w_{i}^{(m)} = e^{- y_{i} F_{m - 1} (x_{i})} / S_{m - 1}$ , then [F4] gives $w_{i}^{(m + 1)} = e^{- y_{i} F_{m} (x_{i})} / (S_{m - 1} Z_{m})$ . Step 1.1 establishes that the weights normalize, so the update denominator is the sum of the reweighted terms and $S_{m} = S_{m - 1} Z_{m}$ . Induction yields $S_{M} = N \prod_{m = 1}^{M} Z_{m}$ .

3.1F5step 2.1algebra∎

If $y_{i} F_{M} (x_{i}) \leq 0$ , then $e^{- y_{i} F_{M} (x_{i})} \geq 1$ ; if the margin is positive, its indicator is zero. Hence each nonpositive-margin indicator is at most its exponential term, and summing and applying step 2.1 proves the stated bound. By [F5], a misclassified positive-label example has negative margin and a misclassified negative-label example has nonpositive margin, so training error is no larger than the bounded nonpositive-margin fraction.

Depends on

Finite-sample AdaBoost.M1 with half-log coefficients

Used by

Two AdaBoost rounds with normalized weights Example

Dependency tree · one level

1 result within one dependency step 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

Trevor Hastie, Robert Tibshirani, and Jerome Friedman, The Elements of Statistical Learning, 2nd ed., 12th printing (standard reference, not scraped)
Robert E. Schapire, "The Boosting Approach to Machine Learning: An Overview," MSRI Workshop on Nonlinear Estimation and Classification, 2002 (standard reference, not scraped)