Boosting: AdaBoost and Gradient Boosting

Intuition Beginner

Boosting builds a strong predictor out of many weak ones, hired one at a time. A weak learner is a rule that is only a little better than a coin flip — a shallow decision tree, sometimes a single yes/no question. On its own it is useless. But boosting runs a hiring process: it keeps a committee, sees where the committee currently gets things wrong, and hires the next weak rule specifically to handle those hard cases.

The trick is the weights. Every training case carries a weight that says how much it matters right now. At the start all cases matter equally. After each new rule joins, the cases it got wrong have their weight raised and the cases it got right have their weight lowered. So the next rule is trained on a reweighted dataset where the still-unsolved cases shout the loudest. Each rule chases the mistakes left behind by the ones before it.

When a rule is finished, it gets a vote in the final committee, and a good rule that made few weighted mistakes gets a louder vote than a barely-better-than-chance one. To predict a new case, every rule votes, the votes are added up with their weights, and the sign of the total is the answer. A flock of stumps, each near-useless, becomes a sharp classifier.

A useful contrast: bagging also combines many trees, but it grows them all in parallel on shuffled copies of the data and averages them to cancel out their noise. Boosting is sequential and corrective — it lowers the committee's mistakes, not just its jitter.

Visual Beginner

Picture three rounds on a scatter of plus and minus points. Round one draws a vertical line; a few points land on the wrong side, and we redraw them bigger. Round two draws a horizontal line aimed at those enlarged points; it fixes them but slips on others, which now grow. Round three cleans up again. No single line separates the data, but the weighted vote of the three does.

Round	Who gets bigger weight	What the new rule targets
1	everyone equal	the best single split
2	round-1 mistakes	the points line 1 missed
3	round-2 mistakes	the points line 2 missed
Final	—	weighted vote of all three

Reading across the panels: the data never changes, only the spotlight on it does, and the final boundary is built from rules that each saw a different version of the difficulty.

Worked example Beginner

Ten training points. A weak learner here is a single threshold rule. We run one round of boosting and read off the new vote and weights.

Start: all ten points have weight $0.1$ (they sum to $1$). The best weak rule we can find misclassifies exactly three of the ten points.

Step 1. Weighted error. The three wrong points each carry weight $0.1$, so the weighted error is $\mathrm{err}=0.1+0.1+0.1=0.3$. The seven correct points contribute nothing to the error.

Step 2. The rule's vote. A rule that is right more often than wrong earns a positive vote, computed as $\alpha =\log \left(\frac{1-\mathrm{err}}{\mathrm{err}}\right)=\log \left(\frac{0.7}{0.3}\right)=\log (2.333)=0.847$. A perfect rule ($\mathrm{err}\to 0$) would earn an enormous vote; a coin-flip rule ($\mathrm{err}=0.5$) earns a vote of $0$.

Step 3. Re-weight. Multiply each wrong point's weight by $e^{\alpha }=e^{0.847}=2.333$ and leave the right points as they are. The three wrong points go from $0.1$ to $0.1\times 2.333=0.233$ each.

Step 4. Renormalize so the weights sum to $1$ again. The new total is $7(0.1)+3(0.233)=0.7+0.7=1.4$. Dividing through, each wrong point now has weight $0.233/1.4=0.167$ and each right point $0.1/1.4=0.071$.

What this tells us: after one round the three hard points carry $0.167$ each — more than double the $0.071$ of the easy ones — so the next weak rule is pulled toward fixing exactly the points the first rule missed, while the first rule keeps its $0.847$ vote in the final committee.

Check your understanding Beginner

Formal definition Intermediate+

Let the training sample be $\{(x_i,y_i){\}}_{i=1}^n$ with $y_i\in \{-1,+1\}$, and let $\mathcal{G}$ be a class of base ("weak") classifiers $G:\mathcal{X}\to \{-1,+1\}$. Boosting produces an additive ensemble $f_M(x)={\sum }_{m=1}^M{\beta }_m{G}_m(x)$ and predicts $\hat{y}(x)=\mathrm{sign}{f}_M(x)$, where the $G_m$ and coefficients ${\beta }_m>0$ are chosen sequentially.

AdaBoost. Maintain weights $w^{(m)}=(w_1^{(m)},\dots ,w_n^{(m)})$ on the sample, initialised $w_i^{(1)}=1/n$. At round $m$:

1. Fit $G_m=\arg {\min }_{G\in \mathcal{G}}{\sum }_{i=1}^n{w}_i^{(m)}1\{y_i\ne G(x_i)\}$, with weighted error ${\mathrm{err}}_m={\sum }_i{w}_i^{(m)}1\{y_i\ne G_m(x_i)\}/{\sum }_i{w}_i^{(m)}$.
2. Set the vote ${\alpha }_m=\frac{1}{2}\log \left(\frac{1-{\mathrm{err}}_m}{{\mathrm{err}}_m}\right)$ (a factor $\frac{1}{2}$ relative to the Freund-Schapire constant absorbs the symmetric coding; both conventions give the same classifier).
3. Update $w_i^{(m+1)}=w_i^{(m)}\exp (-{\alpha }_m{y}_i{G}_m(x_i))$ and renormalise to sum to one. Since $y_i{G}_m(x_i)=+1$ when correct and $-1$ when wrong, this multiplies wrong points by $e^{{\alpha }_m}$ and right points by $e^{-{\alpha }_m}$.

The output is $f_M={\sum }_m{\alpha }_m{G}_m$ and $\hat{y}=\mathrm{sign}{f}_M$.

Forward stagewise additive modelling. Given a loss $L(y,f)$ and a basis $\{G(\cdot ;\gamma )\}$, build $f_m=f_{m-1}+{\beta }_{m}G(\cdot ;{\gamma }_m)$ where, at each step, $({\beta }_m,{\gamma }_m)=\arg {\min }_{\beta ,\gamma }{\sum }_{i=1}^{n}L(y_i,f_{m-1}(x_i)+\beta G(x_i;\gamma ))$, never revisiting the earlier terms. The margin of $f$ at a point is $yf(x)$; positive margin means correct classification with confidence $|f(x)|$.

Exponential loss. $L(y,f)=\exp (-yf)$. Its population risk is $\mathbb{E}[e^{-Yf(X)}]$, and AdaBoost is forward stagewise additive modelling under this loss (proved below).

Gradient boosting. For a differentiable loss $L$, define the empirical risk $\mathcal{R}(f)={\sum }_{i=1}^{n}L(y_i,f(x_i))$ as a function of the vector $(f(x_1),\dots ,f(x_n))$. The pseudo-residual at round $m$ is the negative gradient

$${\tilde{r}}_{im}=-{\left[\frac{\partial L(y_i,f(x_i))}{\partial f(x_i)}\right]}_{f=f_{m-1}},$$

a base learner $h_m$ (typically a regression tree) is fit by least squares to $\{(x_i,{\tilde{r}}_{im})\}$, and the update is $f_m=f_{m-1}+\nu {\rho }_m{h}_m$ with line-searched step ${\rho }_m=\arg {\min }_{\rho }{\sum }_{i}L(y_i,f_{m-1}(x_i)+\rho h_m(x_i))$ and shrinkage (learning rate) $\nu \in (0,1]$.

The notation here — $1\{\cdot \}$ for indicators, $\mathrm{sign}$, the margin $yf(x)$, and the empirical risk $\mathcal{R}$ — is recorded in _meta/NOTATION.md.

Counterexamples to common slips Intermediate+

• "AdaBoost minimises the training misclassification rate directly." It does not. Each round minimises a weighted $0/1$ error to choose $G_m$, but the quantity the whole procedure descends is the exponential loss ${\sum }_i{e}^{-y_i{f}_m(x_i)}$, a smooth surrogate. The misclassification rate is only an upper-bounded by-product (the training-error theorem), not the objective.

• "Exponential loss and binomial deviance give the same boosting algorithm." They share the same population minimiser (the half-log-odds), but exponential loss penalises large negative margins as $e^{-yf}$, far more aggressively than deviance's $\log (1+e^{-yf})$. On mislabelled data this makes AdaBoost less robust; gradient boosting with deviance is the standard fix.

• "More rounds always help, because boosting cannot overfit." The margin theory explains why test error often keeps falling after training error hits zero, but boosting can and does overfit — with noisy labels, deep base trees, or a vast number of rounds. Shrinkage, shallow trees, and early stopping are needed; the no-overfitting claim is a tendency, not a theorem.

Key theorem with proof Intermediate+

The signature result is that AdaBoost's training error is squeezed to zero exponentially fast, as long as every weak learner does a little better than chance. This is the quantitative payoff of reweighting, and it is what justifies calling a collection of barely-useful rules a strong learner.

Theorem (AdaBoost training-error bound; Freund-Schapire). Run AdaBoost for $M$ rounds, let ${\mathrm{err}}_m=\frac{1}{2}-{\gamma }_m$ be the weighted error at round $m$, and let $Z_m={\sum }_i{w}_i^{(m)}\exp (-{\alpha }_m{y}_i{G}_m(x_i))$ be the round-$m$ normalising constant (before renormalisation). Then the training misclassification rate of $f_M={\sum }_m{\alpha }_m{G}_m$ satisfies

$$\frac{1}{n}\sum _{i=1}^{n}1\{y_i\ne \mathrm{sign}{f}_M(x_i)\}\le \prod _{m=1}^M{Z}_m=\prod _{m=1}^{M}2\sqrt{{\mathrm{err}}_m(1-{\mathrm{err}}_m)}\le \exp (-2\sum _{m=1}^M{\gamma }_m^2).$$

In particular, if every weak learner satisfies ${\gamma }_m\ge \gamma >0$, the training error is at most $e^{-2M{\gamma }^2}\to 0$. ^{[Freund 1997]}

Proof. Unrolling the weight recursion from $w_i^{(1)}=1/n$ and writing each renormalisation factor as $Z_m$,

$$w_i^{(M+1)}=\frac{1}{n}\frac{\exp (-{\sum }_{m=1}^M{\alpha }_m{y}_i{G}_m(x_i))}{{\prod }_{m=1}^M{Z}_m}=\frac{1}{n}\frac{e^{-y_i{f}_M(x_i)}}{{\prod }_m{Z}_m}.$$

Because the final weights are a probability vector, ${\sum }_i{w}_i^{(M+1)}=1$, so $\frac{1}{n}{\sum }_i{e}^{-y_i{f}_M(x_i)}={\prod }_m{Z}_m$. The misclassification indicator is dominated by the exponential loss: if $y_i\ne \mathrm{sign}{f}_M(x_i)$ then $y_i{f}_M(x_i)\le 0$ and $e^{-y_i{f}_M(x_i)}\ge 1$, so $1\{y_i\ne \mathrm{sign}{f}_M(x_i)\}\le e^{-y_i{f}_M(x_i)}$. Averaging gives

$$\frac{1}{n}\sum _{i}1\{y_i\ne \mathrm{sign}{f}_M(x_i)\}\le \frac{1}{n}\sum _i{e}^{-y_i{f}_M(x_i)}=\prod _{m=1}^M{Z}_m,$$

the first inequality of the claim. To evaluate $Z_m$, split the sum over correctly and incorrectly classified points. With weights normalised so ${\sum }_i{w}_i^{(m)}=1$, the wrong points carry total weight ${\mathrm{err}}_m$ and the right points $1-{\mathrm{err}}_m$, and $-{\alpha }_m{y}_i{G}_m(x_i)=+{\alpha }_m$ on wrong points, $-{\alpha }_m$ on right points, so

$$Z_m=(1-{\mathrm{err}}_m)e^{-{\alpha }_m}+{\mathrm{err}}_m{e}^{{\alpha }_m}.$$

Minimising over ${\alpha }_m$: $\frac{d{Z}_m}{d{\alpha }_m}=-(1-{\mathrm{err}}_m)e^{-{\alpha }_m}+{\mathrm{err}}_m{e}^{{\alpha }_m}=0$ gives $e^{2{\alpha }_m}=(1-{\mathrm{err}}_m)/{\mathrm{err}}_m$, i.e. ${\alpha }_m=\frac{1}{2}\log \frac{1-{\mathrm{err}}_m}{{\mathrm{err}}_m}$ — exactly the AdaBoost vote. Substituting back, $e^{-{\alpha }_m}=\sqrt{{\mathrm{err}}_m/(1-{\mathrm{err}}_m)}$ and $e^{{\alpha }_m}=\sqrt{(1-{\mathrm{err}}_m)/{\mathrm{err}}_m}$, so

$$Z_m=(1-{\mathrm{err}}_m)\sqrt{\frac{{\mathrm{err}}_m}{1-{\mathrm{err}}_m}}+{\mathrm{err}}_m\sqrt{\frac{1-{\mathrm{err}}_m}{{\mathrm{err}}_m}}=2\sqrt{{\mathrm{err}}_m(1-{\mathrm{err}}_m)}.$$

Writing ${\mathrm{err}}_m=\frac{1}{2}-{\gamma }_m$, $4{\mathrm{err}}_m(1-{\mathrm{err}}_m)=1-4{\gamma }_m^2$, so $Z_m=\sqrt{1-4{\gamma }_m^2}$. The elementary inequality $1-u\le e^{-u}$ at $u=4{\gamma }_m^2$ gives $Z_m\le e^{-2{\gamma }_m^2}$, and the product telescopes to ${\prod }_m{Z}_m\le \exp (-2{\sum }_m{\gamma }_m^2)$. $\square$

Bridge. The choice ${\alpha }_m=\frac{1}{2}\log \frac{1-{\mathrm{err}}_m}{{\mathrm{err}}_m}$ was not an arbitrary scoring rule: the proof shows it is the unique value that minimises the round's normalising constant $Z_m$, and minimising $Z_m$ each round is exactly greedy minimisation of ${\prod }_m{Z}_m=\frac{1}{n}{\sum }_i{e}^{-y_i{f}_M(x_i)}$, the exponential loss. This is the foundational reason the algorithm of reweighting-and-voting and the analysis of exponential-loss descent are one object, and it is exactly the equivalence the Advanced results prove in full as forward stagewise additive modelling. The telescoping identity $w_i^{(M+1)}\propto e^{-y_i{f}_M(x_i)}$ generalises the single-round weight update into a closed form for the cumulative margin, which builds toward the population analysis where minimising $\mathbb{E}[e^{-Yf}]$ pins $f$ to half the log-odds. The exponential bound appears again in the margin theory of 45.07.06, where the same domination $1\{yf\le 0\}\le e^{-yf}$ is sharpened to control not just the sign of the margin but its distribution; putting these together, the bridge is that boosting drives the empirical margin distribution upward, and the training-error theorem is the crudest reading of that fact.

Exercises Intermediate+

Advanced results Master

AdaBoost is one algorithm read two ways: as reweight-and-vote and as coordinate-wise descent on exponential loss. The theory beyond the training-error bound concerns what that descent estimates, why it generalises beyond the point of zero training error, and how the same construction extends from one loss to all differentiable losses.

Theorem 1 (AdaBoost is forward stagewise additive modelling under exponential loss). With $L(y,f)=e^{-yf}$, the forward stagewise update $({\beta }_m,G_m)=\arg {\min }_{\beta ,G}{\sum }_i{e}^{-y_i(f_{m-1}(x_i)+\beta G(x_i))}$ has solution: $G_m$ is the minimiser of the weighted misclassification error with weights $w_i^{(m)}=e^{-y_i{f}_{m-1}(x_i)}$, and ${\beta }_m=\frac{1}{2}\log \frac{1-{\mathrm{err}}_m}{{\mathrm{err}}_m}$, after which the weights update multiplicatively as $w_i^{(m+1)}=w_i^{(m)}{e}^{-{\beta }_m{y}_i{G}_m(x_i)}$ ^{[Hastie 2009]}. Thus the AdaBoost weights are the exponential-loss residual weights, and the AdaBoost vote is the stagewise-optimal coefficient. AdaBoost performs no explicit reweighting "by design"; the reweighting is the gradient of exponential loss.

Theorem 2 (population minimiser and the log-odds). The minimiser of the population exponential risk is $f^{\text{*}}(x)=\arg {\min }_f\mathbb{E}[e^{-Yf(X)}\mid X=x]=\frac{1}{2}\log \frac{\mathrm{Pr}(Y=1\mid x)}{\mathrm{Pr}(Y=-1\mid x)}$, half the log-odds ^{[Hastie 2009]}. Inverting, $\mathrm{Pr}(Y=1\mid x)=1/(1+e^{-2f^{\text{*}}(x)})$, so the boosted score, after monotone transformation, is an estimate of the class-probability log-odds; the same minimiser is shared by the binomial deviance $\log (1+e^{-2yf})$, which is why deviance is the robust drop-in replacement that penalises gross misclassification only linearly rather than exponentially. The sign of $f^{\text{*}}$ is the Bayes classifier, so exponential loss is classification-calibrated (Fisher-consistent).

Theorem 3 (gradient boosting as steepest descent in function space). Treat $\mathcal{R}(f)={\sum }_{i}L(y_i,f(x_i))$ as a function of the vector $\mathbf{f}=(f(x_1),\dots ,f(x_n))$. The unconstrained steepest-descent step is ${\mathbf{f}}_m={\mathbf{f}}_{m-1}-{\rho }_m\nabla \mathcal{R}({\mathbf{f}}_{m-1})$, with gradient components $-{\tilde{r}}_{im}=\partial L(y_i,f(x_i))/\partial f(x_i)$. Restricting the step to the span of a base-learner class, gradient boosting fits $h_m=\arg {\min }_{h\in \mathcal{H}}{\sum }_i({\tilde{r}}_{im}-h(x_i){)}^2$ — the least-squares projection of the negative gradient onto $\mathcal{H}$ — and sets $f_m=f_{m-1}+\nu {\rho }_m{h}_m$ with line search ${\rho }_m$ and shrinkage $\nu$ ^{[Friedman 2001]}. This is functional gradient descent (cross-ref the first-order optimisation theory of 44.06): the only departures from textbook steepest descent are that the gradient lives in ${\mathbb{R}}^n$ over the training inputs and the step is forced into $\mathcal{H}$ so it generalises off-sample.

Theorem 4 (margin distribution and resistance to overfitting). Define the normalised margin of the voting classifier as $\mathrm{margin}(x,y)=y{\sum }_m{\alpha }_m{G}_m(x)/{\sum }_m{\alpha }_m\in [-1,1]$. For voting classifiers, with probability $1-\delta$ over the sample, for all $\theta >0$ simultaneously,

$$\underset{\mathcal{D}}{\mathrm{Pr}}[yf(x)\le 0]\le {\widehat{\mathrm{Pr}}}_S[\mathrm{margin}(x,y)\le \theta ]+O\left(\frac{1}{\sqrt{n}}\sqrt{\frac{d}{{\theta }^2}}\right),$$

where $d$ is a complexity measure (e.g. the VC dimension of $\mathcal{G}$); the bound does not depend on the number of rounds $M$ ^{[Schapire 1998]}. Because AdaBoost continues to increase the margins of training points after the training error reaches zero, the right-hand side keeps decreasing, which is the margin-theoretic account of why test error often falls past the zero-training-error point. The account is partial: boosting can overfit when labels are noisy or base learners too rich, and the margin bound is loose; shrinkage, shallow trees, subsampling, and early stopping remain necessary regularisers.

Synthesis. The central insight is that AdaBoost is exponential-loss minimisation by coordinate descent over the dictionary of weak learners, and every operational feature follows from that one identification. The vote ${\alpha }_m=\frac{1}{2}\log \frac{1-{\mathrm{err}}_m}{{\mathrm{err}}_m}$ is the stagewise-optimal step (Theorem 1), the reweighting is the loss gradient, and the training-error theorem is just the statement that greedy descent on ${\prod }_m{Z}_m$ drives the surrogate — and hence the misclassification rate it dominates — to zero. Putting these together with the population analysis, minimising exponential risk pins the boosted score to half the log-odds (Theorem 2), so boosting is not merely a classifier but a probability estimator, and this is exactly the fact that generalises AdaBoost to gradient boosting: once boosting is descent on a loss, any differentiable loss will do, and the pseudo-residual fit of Theorem 3 is the foundational reason a single framework covers regression, robust regression, and classification. The bridge to generalisation is the margin distribution (Theorem 4): the training-error bound controls only the sign of the margin, while the margin theory controls its spread, and boosting's empirical tendency to keep enlarging margins after zero training error is what the round-independent bound formalises. This is dual to bagging's variance reduction proved for trees in 45.08.04: bagging averages independent high-variance, low-bias trees to cut variance, whereas boosting adds dependent high-bias, low-variance stumps to cut bias, and the two occupy opposite corners of the bias-variance plane while sharing trees as their base object.

Full proof set Master

Proposition 1 (telescoping of the weights; the empirical exponential loss equals ${\prod }_m{Z}_m$). With $w_i^{(1)}=1/n$ and the AdaBoost update renormalised by $Z_m={\sum }_i{w}_i^{(m)}{e}^{-{\alpha }_m{y}_i{G}_m(x_i)}$, one has $w_i^{(M+1)}=\frac{1}{n}{e}^{-y_i{f}_M(x_i)}/{\prod }_{m=1}^M{Z}_m$, hence $\frac{1}{n}{\sum }_i{e}^{-y_i{f}_M(x_i)}={\prod }_{m=1}^M{Z}_m$.

Proof. By induction on $M$. At $M=0$, $w_i^{(1)}=1/n=\frac{1}{n}{e}^{-y_i{f}_0(x_i)}$ with empty product $=1$ and $f_0\equiv 0$. Assume $w_i^{(m)}=\frac{1}{n}{e}^{-y_i{f}_{m-1}(x_i)}/{\prod }_{k<m}{Z}_k$. The renormalised update is $w_i^{(m+1)}=w_i^{(m)}{e}^{-{\alpha }_m{y}_i{G}_m(x_i)}/Z_m$, and substituting the inductive hypothesis with $f_m=f_{m-1}+{\alpha }_m{G}_m$ gives $w_i^{(m+1)}=\frac{1}{n}{e}^{-y_i{f}_m(x_i)}/{\prod }_{k\le m}{Z}_k$. Summing over $i$ and using ${\sum }_i{w}_i^{(M+1)}=1$ (the weights are renormalised to a probability vector) yields ${\sum }_i\frac{1}{n}{e}^{-y_i{f}_M(x_i)}={\prod }_{m\le M}{Z}_m$. $\square$

Proposition 2 (per-round factor and the exponential bound). Each $Z_m=2\sqrt{{\mathrm{err}}_m(1-{\mathrm{err}}_m)}=\sqrt{1-4{\gamma }_m^2}\le e^{-2{\gamma }_m^2}$ for ${\mathrm{err}}_m=\frac{1}{2}-{\gamma }_m$, so ${\prod }_m{Z}_m\le e^{-2{\sum }_m{\gamma }_m^2}$.

Proof. With normalised round weights, $Z_m=(1-{\mathrm{err}}_m)e^{-{\alpha }_m}+{\mathrm{err}}_m{e}^{{\alpha }_m}$; substituting ${\alpha }_m=\frac{1}{2}\log \frac{1-{\mathrm{err}}_m}{{\mathrm{err}}_m}$ gives $Z_m=2\sqrt{{\mathrm{err}}_m(1-{\mathrm{err}}_m)}$ (the back-substitution of Exercise 3). Then $4{\mathrm{err}}_m(1-{\mathrm{err}}_m)=4(\frac{1}{2}-{\gamma }_m)(\frac{1}{2}+{\gamma }_m)=1-4{\gamma }_m^2$, so $Z_m=\sqrt{1-4{\gamma }_m^2}$. The inequality $1-u\le e^{-u}$ with $u=4{\gamma }_m^2$ gives $1-4{\gamma }_m^2\le e^{-4{\gamma }_m^2}$, whence $Z_m\le e^{-2{\gamma }_m^2}$, and the product bound follows. Combined with Proposition 1 and the domination $1\{y_i\ne \mathrm{sign}{f}_M(x_i)\}\le e^{-y_i{f}_M(x_i)}$, the training error is at most ${\prod }_m{Z}_m\le e^{-2{\sum }_m{\gamma }_m^2}$. $\square$

Proposition 3 (exponential-loss population minimiser). For $L(y,f)=e^{-yf}$ with $Y\in \{-1,+1\}$ and $p(x)=\mathrm{Pr}(Y=1\mid x)$, the pointwise minimiser of $\mathbb{E}[e^{-Yf(X)}\mid X=x]$ is $f^{\text{*}}(x)=\frac{1}{2}\log \frac{p(x)}{1-p(x)}$.

Proof. Conditioning on $X=x$, $\mathbb{E}[e^{-Yf}\mid x]=p(x)e^{-f}+(1-p(x))e^f=:\varphi (f)$. Then ${\varphi }^{\prime }(f)=-p(x)e^{-f}+(1-p(x))e^f$, vanishing where $e^{2f}=p(x)/(1-p(x))$, i.e. $f^{\text{*}}(x)=\frac{1}{2}\log \frac{p(x)}{1-p(x)}$; ${\varphi }^{\prime \prime }(f)=p(x)e^{-f}+(1-p(x))e^f>0$ confirms the global minimum (the objective is strictly convex in $f$). Inverting, $\mathrm{Pr}(Y=1\mid x)=e^{2f^{\text{*}}}/(1+e^{2f^{\text{*}}})=1/(1+e^{-2f^{\text{*}}})$. The Bayes rule $\mathrm{sign}(p(x)-\frac{1}{2})$ coincides with $\mathrm{sign}{f}^{\text{*}}(x)$, so exponential loss is classification-calibrated. $\square$

Proposition 4 (gradient-boosting step is the least-squares projection of the negative gradient). Let $\mathcal{R}(\mathbf{f})={\sum }_{i}L(y_i,f(x_i))$ and ${\tilde{r}}_{im}=-{\partial }_{f(x_i)}L(y_i,f(x_i)){|}_{f_{m-1}}$. The base learner $h_m=\arg {\min }_{h\in \mathcal{H}}{\sum }_i({\tilde{r}}_{im}-h(x_i){)}^2$ is the element of $\mathcal{H}$ most aligned with the negative gradient in the empirical inner product, and a positive step along it decreases $\mathcal{R}$ to first order whenever $h_m/\perp \nabla \mathcal{R}$.

Proof. The negative gradient of $\mathcal{R}$ at ${\mathbf{f}}_{m-1}$ has components ${\tilde{r}}_{im}$. For a step ${\mathbf{f}}_{m-1}+\rho \mathbf{h}$ with $\mathbf{h}=(h(x_1),\dots ,h(x_n))$, a first-order expansion gives $\mathcal{R}({\mathbf{f}}_{m-1}+\rho \mathbf{h})=\mathcal{R}({\mathbf{f}}_{m-1})-\rho ⟨{\tilde{\mathbf{r}}}_m,\mathbf{h}⟩+o(\rho )$, where $⟨\cdot ,\cdot ⟩$ is the Euclidean inner product over the $n$ training points. Decreasing $\mathcal{R}$ at first order requires $⟨{\tilde{\mathbf{r}}}_m,\mathbf{h}⟩>0$. Minimising ${\sum }_i({\tilde{r}}_{im}-h(x_i){)}^2=\Vert {\tilde{\mathbf{r}}}_m{\Vert }^2-2⟨{\tilde{\mathbf{r}}}_m,\mathbf{h}⟩+\Vert \mathbf{h}{\Vert }^2$ over $\mathcal{H}$ maximises $⟨{\tilde{\mathbf{r}}}_m,\mathbf{h}⟩$ relative to $\Vert \mathbf{h}{\Vert }^2$, i.e. selects the base learner best aligned with the negative gradient; the orthogonality conditions of the least-squares fit make ${\mathbf{h}}_m$ the projection of ${\tilde{\mathbf{r}}}_m$ onto $\mathcal{H}$. So long as that projection is non-zero, $⟨{\tilde{\mathbf{r}}}_m,{\mathbf{h}}_m⟩=\Vert {\mathbf{h}}_m{\Vert }^2>0$ and the line-searched step ${\rho }_m>0$ strictly decreases $\mathcal{R}$. $\square$

Connections Master

• The base learners boosting combines are the trees of 45.08.04: boosting reweights or refits shallow trees (stumps and small trees at the low-$|T|$ end of the cost-complexity chain), and the instability and high-variance profile established there is precisely the property that makes deep trees wrong for boosting and right for bagging, so this unit specialises the tree object of the prior unit into a sequential, bias-reducing ensemble.

• Boosting reduces bias where bagging and random forests reduce variance, the two facing pages of the bias-variance decomposition: the correlated-average variance formula proved for trees in 45.08.04 explains bagging's gain, while the additive forward-stagewise construction here explains boosting's complementary attack on bias, so the same decomposition organises both ensembles and assigns each its corner of the bias-variance plane.

• The margin-distribution bound of Theorem 4 is the boosting instance of the margin generalisation theory of 45.07.06: the elementary domination $1\{yf\le 0\}\le e^{-yf}$ used in the training-error proof is the seed of the uniform margin bounds there, and the boosting story — test error falling past zero training error — is the empirical phenomenon those bounds were built to explain.

• Gradient boosting is functional gradient descent, an instance of the first-order optimisation methods of [44.06]: the empirical risk $\mathcal{R}(\mathbf{f})$ is descended by steepest steps projected onto a base-learner class, with the learning rate $\nu$ playing the role of a fixed step size and stochastic subsampling mirroring the mini-batching of stochastic gradient methods, so the convergence and step-size intuition from convex optimisation transfers directly to the boosting iteration.

Historical & philosophical context Master

Boosting began as a question in computational learning theory: Kearns and Valiant (1989) asked whether a "weak" PAC-learning algorithm — one only slightly better than chance — could always be boosted into a "strong" one with arbitrarily small error. Schapire (1990) answered yes with the first boosting algorithm, and Freund (1995) simplified it to boost-by-majority. The practical breakthrough was Freund and Schapire's AdaBoost (1995; full version 1997) ^{[Freund 1997]}, which adapted to the weak learners' errors without knowing their edge in advance and came with the exponential training-error bound proved above; it won the 2003 Gödel Prize.

The statistical recasting followed. Friedman, Hastie, and Tibshirani (2000) identified AdaBoost as forward stagewise additive modelling under exponential loss with the half-log-odds population minimiser, moving boosting from a margin-game in learning theory into the regression-modelling framework of The Elements of Statistical Learning ^{[Hastie 2009]}. Friedman (2001) generalised the construction to arbitrary differentiable losses as a gradient boosting machine ^{[Friedman 2001]}, the lineage that runs through MART to the regularised, second-order, sparsity-aware implementations of XGBoost (Chen and Guestrin 2016), LightGBM, and CatBoost that dominate tabular-data competitions. The apparent paradox that AdaBoost keeps improving test error after training error reaches zero prompted the margin theory of Schapire, Freund, Bartlett, and Lee (1998) ^{[Schapire 1998]} and a long debate, including Breiman's (1999) counterexamples, over whether margins fully explain the phenomenon; the resolution is that boosting enlarges the margin distribution but is not immune to overfitting, which is why shrinkage and subsampling became standard.

Bibliography Master

@article{freundschapire1997,
  author  = {Freund, Yoav and Schapire, Robert E.},
  title   = {A decision-theoretic generalization of on-line learning and an application to boosting},
  journal = {Journal of Computer and System Sciences},
  volume  = {55},
  number  = {1},
  pages   = {119--139},
  year    = {1997}
}

@article{friedman2001gbm,
  author  = {Friedman, Jerome H.},
  title   = {Greedy function approximation: a gradient boosting machine},
  journal = {Annals of Statistics},
  volume  = {29},
  number  = {5},
  pages   = {1189--1232},
  year    = {2001}
}

@article{friedmanhastietibshirani2000,
  author  = {Friedman, Jerome and Hastie, Trevor and Tibshirani, Robert},
  title   = {Additive logistic regression: a statistical view of boosting},
  journal = {Annals of Statistics},
  volume  = {28},
  number  = {2},
  pages   = {337--407},
  year    = {2000}
}

@article{schapire1998margins,
  author  = {Schapire, Robert E. and Freund, Yoav and Bartlett, Peter and Lee, Wee Sun},
  title   = {Boosting the margin: a new explanation for the effectiveness of voting methods},
  journal = {Annals of Statistics},
  volume  = {26},
  number  = {5},
  pages   = {1651--1686},
  year    = {1998}
}

@article{schapire1990strength,
  author  = {Schapire, Robert E.},
  title   = {The strength of weak learnability},
  journal = {Machine Learning},
  volume  = {5},
  number  = {2},
  pages   = {197--227},
  year    = {1990}
}

@inproceedings{chenguestrin2016xgboost,
  author    = {Chen, Tianqi and Guestrin, Carlos},
  title     = {{XGBoost}: a scalable tree boosting system},
  booktitle = {Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
  pages     = {785--794},
  year      = {2016}
}

@book{hastie2009esl,
  author    = {Hastie, Trevor and Tibshirani, Robert and Friedman, Jerome},
  title     = {The Elements of Statistical Learning: Data Mining, Inference, and Prediction},
  edition   = {2},
  publisher = {Springer},
  year      = {2009}
}