AdaBoost

The algorithm#

Given $(x_i, y_i)_{i=1}^{n}$ with $y_i \in {-1, +1}$, initialise weights $w_i = 1/n$. For rounds $t = 1 \dots T$:

1. Fit weak learner $h_t$ to the weighted data.
2. Compute the weighted error $\varepsilon_t = \sum_i w_i \, \mathbb{1}[h_t(x_i) \neq y_i]$.
3. Set the member's vote strength $\alpha_t = \tfrac{1}{2} \ln \frac{1 - \varepsilon_t}{\varepsilon_t}$.
4. Update $w_i \leftarrow w_i \exp(-\alpha_t y_i h_t(x_i))$ and renormalise.

Final classifier: $H(x) = \operatorname{sign}\left(\sum_{t=1}^{T} \alpha_t h_t(x)\right)$.

Where:

• $w_i$ — the current weight of example $i$ (grows when the ensemble errs on it).
• $\varepsilon_t$ — round $t$'s weighted error; $\varepsilon_t < 0.5$ makes $\alpha_t > 0$.
• $\alpha_t$ — how loudly $h_t$ votes; approaches $\infty$ as $\varepsilon_t \to 0$.

Source: Freund and Schapire (1997), A decision-theoretic generalization of on-line learning and an application to boosting, JCSS — building on Schapire (1990), The strength of weak learnability, which answered Kearns and Valiant's question in the affirmative.

Training error bound#

With edge $\gamma_t = \tfrac{1}{2} - \varepsilon_t$, the training error satisfies

$$ \frac{1}{n} \sum_i \mathbb{1}[H(x_i) \neq y_i] \;\leq\; \prod_{t=1}^{T} \sqrt{1 - 4\gamma_t^2} \;\leq\; \exp\left(-2 \sum_{t=1}^{T} \gamma_t^2\right) $$

Any persistent edge $\gamma_t \geq \gamma > 0$ drives training error down exponentially in $T$. The surprise, historically, was that test error often kept improving after training error hit zero. The margin theory of Schapire, Freund, Bartlett and Lee (1998), Boosting the margin, explains this: further rounds keep enlarging the classification margins, and generalisation bounds depend on margins rather than on $T$.

The statistical view#

Friedman, Hastie and Tibshirani (2000), Additive logistic regression: a statistical view of boosting, showed AdaBoost performs forward stagewise additive modelling that minimises the exponential loss

$$ L(y, F) = \exp(-yF(x)) $$

Where $F$ is the accumulating ensemble score. This reframing did three things: it explained the weight update (the exponential loss's gradient), it exposed the noise fragility (exponential penalty on large negative margins, i.e. confident mistakes), and it opened the door to swapping in other losses — which is precisely gradient boosting (Friedman, 2001).

Noise sensitivity is not only an empirical finding: Long and Servedio (2010), Random classification noise defeats all convex potential boosters, prove any convex-loss booster of this family can be driven to chance accuracy by symmetric label noise.

Complexity and variants#

Per round: one weak-learner fit on $n$ weighted rows — for stumps, $O(n d)$ with $d$ features after an $O(n d \log n)$ presort. Memory is the ensemble itself, $O(T)$ stumps.

• SAMME (Zhu et al., 2009) — the multiclass generalisation; the only variant remaining in scikit-learn.
• LogitBoost (Friedman et al., 2000) — same skeleton, logistic loss.
• Gradient boosting (Friedman, 2001) — replaces reweighting with fitting the loss gradient; with regularisation and clever engineering it becomes XGBoost and LightGBM, which have displaced AdaBoost in practice.

AdaBoost's lasting importance is conceptual: weak learnability equals strong learnability, and hard examples deserve more attention — an idea that resurfaces in hard-negative mining and focal loss.

What to learn next#

• XGBoost — boosting's modern form, where residuals replace reweighting.
• LightGBM — the fast engine that industrialised gradient boosting.
• Why ensembles work — the theory both families share.