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.

Gradient tree boosting does not increase empirical loss

Statement

For any finite run of the defined gradient tree boosting algorithm for which the initial constant and every leaf line minimizer are attained, let $L_{m} = \sum_{i = 1}^{N} ℓ (y_{i}, f_{m} (x_{i}))$ . At every completed round $m$ , $L_{m} \leq L_{m - 1}$ , and hence $L_{M} \leq L_{0}$ . This is a finite-step empirical-loss statement only; it asserts no convergence or generalization result.

Statement references

Trevor Hastie, Robert Tibshirani, and Jerome Friedman, The Elements of Statistical Learning, 2nd ed., §10.10.3, Algorithm 10.3, printed p. 361

Facts & Assumptions

Given: One completed finite boosting round, the finite training sample, and the attained leafwise minimizers.

[F1]

Exact-line-search gradient tree boosting on a finite sample: The tree's terminal regions determine the update, and each $γ_{j m}$ attains the minimum of the corresponding leaf loss over all real offsets.

[F2]

Empirical axis-aligned binary decision trees: A finite tree has nonempty terminal sample sets that partition the training indices, and each training observation follows its unique leaf path.

[F3]

Greedy CART minimizes the listed split loss and terminates: With finite depth, the CART procedure returns a finite tree with nonempty children at every split.

Proof

1.1givenF2F3

Fix a completed round $m$ . By [F2] and [F3], its leaf index sets $I_{j m} = {i : x_{i} \in R_{j m}}$ are finitely many nonempty sets whose disjoint union is ${1, \dots, N}$ .

2.1F1step 1.1given

For every leaf $j$ , its attained minimizer $γ_{j m}$ has loss no greater than the admissible offset $0$ , so $\sum_{i \in I_{j m}} ℓ (y_{i}, f_{m - 1} (x_{i}) + γ_{j m}) \leq \sum_{i \in I_{j m}} ℓ (y_{i}, f_{m - 1} (x_{i}))$ .

3.1F1F2step 1.1step 2.1algebra∎

By the update rule, each training score $f_{m} (x_{i})$ uses the offset for its unique leaf. Summing the inequalities in step 2.1 over the partition in step 1.1 gives $L_{m} = \sum_{j} \sum_{i \in I_{j m}} ℓ (y_{i}, f_{m - 1} (x_{i}) + γ_{j m}) \leq \sum_{j} \sum_{i \in I_{j m}} ℓ (y_{i}, f_{m - 1} (x_{i})) = L_{m - 1}$ . Applying this to each of the finitely many rounds yields $L_{M} \leq L_{0}$ .

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

Trevor Hastie, Robert Tibshirani, and Jerome Friedman, The Elements of Statistical Learning, 2nd ed., 12th printing (standard reference, not scraped)