Answer: The Blessing of Averaging: Boosting Margins

Key Idea / Intuition

A single deep tree overfits because it has a sharp, brittle decision boundary with no confidence — it is exactly right on training points but for the wrong reasons. Boosting does something subtler: even after all training points are correctly classified, the ensemble keeps increasing the margin on each training point (the gap between the vote for the correct class and the vote for the wrong class). A larger margin means the classifier is more confidently correct, and this is what prevents overfitting. The complexity penalty that matters is not the number of rounds $T$ alone, but the distribution of margins over the training set.

---

Formal Proof / Solution

Part (a): Training error bound

Setup. At round $t$, AdaBoost maintains a distribution $D_t$ over training examples. The weak learner returns $h_t$ with weighted error

$\varepsilon_t = \sum_{i: h_t(x_i) \neq y_i} D_t(i) \leq \frac{1}{2} - \gamma.$

The voting weight is $\alpha_t = \frac{1}{2}\ln\!\frac{1-\varepsilon_t}{\varepsilon_t} > 0$, and the distribution update is

$D_{t+1}(i) = \frac{D_t(i)\exp(-\alpha_t y_i h_t(x_i))}{Z_t}$

where $Z_t$ is a normalization constant.

Telescoping the normalization constants. The final (unnormalized) weight of example $i$ is proportional to

$\exp\!\left(-y_i \sum_{t=1}^T \alpha_t h_t(x_i)\right) = \exp(-y_i f(x_i))$

where $f(x_i) = \sum_t \alpha_t h_t(x_i)$ is the margin score. The final ensemble $H(x_i) = \text{sign}(f(x_i))$.

An example $i$ is misclassified iff $y_i f(x_i) \leq 0$, hence $\mathbf{1}[H(x_i)\neq y_i] \leq e^{-y_i f(x_i)}$.

Therefore:

$\text{Training error} = \frac{1}{n}\sum_{i=1}^n \mathbf{1}[H(x_i)\neq y_i] \leq \frac{1}{n}\sum_{i=1}^n e^{-y_i f(x_i)}.$

Bounding the normalization product. One can show by direct calculation that at each round:

$Z_t = 2\sqrt{\varepsilon_t(1-\varepsilon_t)}.$

Since $\varepsilon_t \leq \frac{1}{2}-\gamma$, we have $\varepsilon_t(1-\varepsilon_t) \leq \frac{1}{4}-\gamma^2$, so

$Z_t \leq 2\sqrt{\tfrac{1}{4}-\gamma^2} = \sqrt{1-4\gamma^2} \leq e^{-2\gamma^2}.$

The overall sum telescopes:

$\frac{1}{n}\sum_{i=1}^n e^{-y_i f(x_i)} = \prod_{t=1}^T Z_t \leq \left(e^{-2\gamma^2}\right)^T = e^{-2\gamma^2 T}.$

Hence:

$\boxed{\text{Training error} \leq e^{-2\gamma^2 T}.}$

Training error vanishes exponentially fast in the number of rounds.

---

Part (b): The paradox and its resolution

The apparent paradox. Once training error hits zero (which happens after roughly $T^* \sim \frac{\ln n}{2\gamma^2}$ rounds), every single training point is correctly classified. If model complexity were measured purely by whether training points are memorized, boosting should immediately overfit. Yet empirically (and theoretically), test error keeps decreasing for many more rounds beyond $T^*$.

The resolution: margins keep growing. Even after training error is zero, the signed margin

$m_i = y_i \cdot \frac{f(x_i)}{\sum_t \alpha_t}$

continues to increase for most training points with each additional round. A point with a large margin is correctly classified by a wide majority of the weak learners — even if some noise corrupts a few of them, the ensemble vote is robust. A point with a small margin is only narrowly correct, and small perturbations can flip it.

The right complexity measure. Schapire, Freund, Bartlett & Lee (1998) showed that the generalization bound for boosting depends not on $T$ directly, but on the margin distribution:

$\text{Test error} \leq \hat{P}[m_i \leq \theta] + O\!\left(\sqrt{\frac{d/n}{\theta^2}}\right)$

where $d$ is the VC dimension of the base class and $\theta > 0$ is a margin threshold. As boosting proceeds, $\hat{P}[m_i \leq \theta]$ (the fraction of training points with small margin) decreases — so the bound keeps shrinking even when all points are already correctly classified.

Intuitive summary. Think of the margin as a confidence score. Boosting does not just find a separator; it keeps pushing training points away from the decision boundary. This is analogous to how an SVM maximizes the geometric margin rather than just finding any hyperplane that separates the data. The "model complexity" that matters for generalization is measured by how thin the margin is, not by the raw number of rounds or parameters.

Takeaway: Boosting resists overfitting because additional rounds increase the minimum margin over training data, not because the model is simple. This is a deep insight: fitting the training data more confidently can actually reduce generalization error.