Pipeline-generated

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.

✓ 3 results · all verified · 2 also independently AI-judged

Every result on this page is machine-checked by a proof checker and read in full and owner-audited; the judge is an additional, independent cross-model AI review of the proofs. The 1 not AI-judged were verified by owner audit (typically over a confirmed judge false positive), not failures.

AdaBoost and gradient boosting — Examples

1 · Prerequisites

2 · Logical flowchart

3 · Definitions, theorems and proofs

None yet.

4 · Examples, counterexamples and false statements

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passjudge pass (gpt-6-luna)Open item page →

AdaBoost stops at a perfect round

Example

On the two-observation sample $(x_{1}, y_{1}) = (0, + 1)$ and $(x_{2}, y_{2}) = (1, - 1)$ , let the first base classifier return $h_{1} (x_{1}) = + 1$ and $h_{1} (x_{2}) = - 1$ . Its weighted error is $e_{1} = 0$ , so AdaBoost stops and returns $h_{1}$ with zero training error; no coefficient is formed.

Facts & Assumptions

Given: The stated sample, labels, and classifier outputs.

[F1]

Finite-sample AdaBoost.M1 with half-log coefficients: When $e_{m} = 0$ , the algorithm halts and returns $h_{m}$ itself as a perfect classifier without forming a coefficient.

Verification

1.1givenalgebra

Both predictions equal their labels, so the number of training mistakes is $0$ and $e_{1} = 0$ for the initial uniform weights.

2.1F1step 1.1∎

By [F1], the algorithm stops at this round and returns $h_{1}$ ; since both predictions match, its training error is $0$ and no logarithmic coefficient is evaluated.

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passjudge pass (gpt-6-luna)Open item page →

Two AdaBoost rounds with normalized weights

Example

Take four observations with labels $(+ 1, + 1, - 1, - 1)$ , first classifier predictions $(+ 1, + 1, + 1, - 1)$ , and second classifier predictions $(- 1, + 1, - 1, - 1)$ . The two weighted errors are $1 / 4$ and $1 / 6$ ; the normalized weights after the first and second rounds are $(1 / 6, 1 / 6, 1 / 2, 1 / 6)$ and $(1 / 2, 1 / 10, 3 / 10, 1 / 10)$ . The final margins are $(\frac{1}{2} \log (3 / 5), \frac{1}{2} \log (15), \frac{1}{2} \log (5 / 3), \frac{1}{2} \log (15))$ , so one of four examples has nonpositive margin. The normalizer product is $\sqrt{15} / 6$ , which bounds the empirical nonpositive-margin fraction.

Facts & Assumptions

Given: The four labels and two classifier prediction vectors stated in the Example.

[F1]

Finite-sample AdaBoost.M1 with half-log coefficients: For $0 < e_{m} < 1 / 2$ , the algorithm uses $a_{m} = \frac{1}{2} \log ((1 - e_{m}) / e_{m})$ , $Z_{m} = 2 \sqrt{e_{m} (1 - e_{m})}$ , the normalized update $w_{i}^{(m + 1)} = w_{i}^{(m)} e^{- a_{m} y_{i} h_{m} (x_{i})} / Z_{m}$ , and $F_{m} = F_{m - 1} + a_{m} h_{m}$ .

[F2]

AdaBoost's exponential training-loss and nonpositive-margin bound: For completed weak rounds, the fraction with nonpositive margin is at most $\prod_{m} Z_{m}$ .

Verification

1.1givenF1algebra

Initially each weight is $1 / 4$ . The first classifier misclassifies only observation $3$ , so $e_{1} = 1 / 4$ , $a_{1} = \frac{1}{2} \log 3$ , and $Z_{1} = \sqrt{3} / 2$ .

2.1F1step 1.1algebra

The first update gives weight $(1 / 4) e^{a_{1}} / Z_{1} = 1 / 2$ to observation $3$ and weight $(1 / 4) e^{- a_{1}} / Z_{1} = 1 / 6$ to each other observation, hence $w^{(2)} = (1 / 6, 1 / 6, 1 / 2, 1 / 6)$ .

3.1givenF1step 2.1algebra

Under $w^{(2)}$ , the second classifier misclassifies only observation $1$ , so $e_{2} = 1 / 6$ , $a_{2} = \frac{1}{2} \log 5$ , and $Z_{2} = \sqrt{5} / 3$ .

4.1F1step 3.1algebra

The second update gives weight $1 / 2$ to observation $1$ , $1 / 10$ to observations $2$ and $4$ , and $3 / 10$ to observation $3$ , so $w^{(3)} = (1 / 2, 1 / 10, 3 / 10, 1 / 10)$ .

5.1F1F2step 1.1step 3.1algebra∎

The margins $y_{i} F_{2} (x_{i})$ are respectively $a_{1} - a_{2} = \frac{1}{2} \log (3 / 5) < 0$ , $a_{1} + a_{2} = \frac{1}{2} \log 15 > 0$ , $a_{2} - a_{1} = \frac{1}{2} \log (5 / 3) > 0$ , and $a_{1} + a_{2} > 0$ . Thus the nonpositive-margin fraction is $1 / 4$ , while $Z_{1} Z_{2} = \sqrt{15} / 6$ and $1 / 4 \leq \sqrt{15} / 6$ . By [F2] this is within the theorem's empirical bound.

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passOpen item page →

A one-leaf fit can project a nonzero gradient to zero

Example

Take $x_{1} = 0$ , $x_{2} = 1$ , labels $y_{1} = + 1$ , $y_{2} = - 1$ , squared loss $ℓ (y, z) = \frac{1}{2} (z - y)^{2}$ , initial scores $f_{0} (x_{1}) = f_{0} (x_{2}) = 0$ , and maximum tree depth $0$ . The pseudo-residual vector is $(1, - 1)$ , but its one-leaf least-squares tree fit predicts $0$ on both observations. Let $Φ (z_{1}, z_{2}) = \frac{1}{2} (z_{1} - 1)^{2} + \frac{1}{2} (z_{2} + 1)^{2}$ . A vector $u$ is a strict descent direction at $0$ when the derivative of $t \mapsto Φ (t u)$ at $t = 0$ is negative. The fitted vector $u = (0, 0)$ has derivative $0$ , although the unrestricted score gradient is $(- 1, + 1) \neq 0$ . The exact leaf loss minimizer is also $0$ , so the empirical loss stays at $1$ .

Facts & Assumptions

Given: The two-observation sample, squared loss, zero initial scores, and depth cap $0$ stated in the Example.

[F1]

Negative-gradient pseudo-residuals for a finite empirical loss: The pseudo-residual at observation $i$ is the negative second-argument derivative of its loss at the current score.

[F2]

Pseudo-residuals are the negative gradient in sample-score space: The pseudo-residual vector is the negative Euclidean gradient of the empirical score loss.

[F3]

Empirical axis-aligned binary decision trees: The root sample set contains the training indices, and a regression tree's terminal leaf sets partition those indices.

[F4]

Greedy axis-aligned CART growth on a finite sample: At a node whose depth equals the maximum depth, the procedure leaves the node unsplit; regression leaf predictions are sample means.

[F5]

Exact-line-search gradient tree boosting on a finite sample: Each leaf update uses an attained exact minimizer of the empirical loss over its real offset.

[F6]

Directional derivatives and partial derivatives of a map $U \subseteq R^{m} \to R^{n}$ : The directional derivative in direction $u$ is the derivative of the line map $t \mapsto Φ (0 + t u)$ at $t = 0$ .

Verification

1.1givenF1F2algebra

For any constant $c$ , the initial empirical loss is $\frac{1}{2} (c - 1)^{2} + \frac{1}{2} (c + 1)^{2} = c^{2} + 1$ , so $c_{0} = 0$ is an attained minimizer. At these scores, [F1] gives residuals $r_{1} = 1$ and $r_{2} = - 1$ , and [F2] gives $\nabla Φ (0) = (- 1, + 1) \neq 0$ .

2.1F3F4step 1.1algebra

With depth cap $0$ , [F4] leaves the root as a single terminal leaf; by [F3] it contains both observations. Its regression prediction is their residual mean $(1 + (- 1)) / 2 = 0$ , so the fitted direction on the sample is $u = (0, 0)$ .

3.1F2F6step 2.1

Since $t u = (0, 0)$ for every real $t$ , the line map in [F6] is constant and its derivative is $0$ . Thus $u$ is not a strict descent direction, even though the unrestricted gradient in step 1.1 is nonzero.

4.1F5step 1.1step 2.1algebra∎

The sole leaf's loss at offset $γ$ is $\frac{1}{2} (γ - 1)^{2} + \frac{1}{2} (γ + 1)^{2} = γ^{2} + 1$ , whose attained minimum is $1$ at $γ = 0$ . By [F5], the algorithm updates neither training score, so the loss remains $1$ .