# AdaBoost assumption of weak classifier

I've read and think I got a good grasp of the math behind AdaBoost, but I wasn't able to understand why AdaBoost requires a weak base-classifier?

Specifically, I'm dealing with AdaBoost using decision-tree as base-classifier. So, what if my DT wasn't "weak"? So instead of using a stump (DT with depth of 1), what should happen with AdaBoost if I used deeper tree for example?

I found this, but I'm not it fully answers my question

• Where are you seeing that a weak base-classifier is required? Jun 9, 2020 at 1:51

Practically, I'm unsure why one would need to rely on AdaBoost if we already had a strong classifier. Tl;dr: I don't believe that having a weak learner is requirement for AdaBoost to work.

I can try to walk through some of the analysis. We'll deal with empirical error, and then generalization error.

Empirical Error (train)

We define a weak learner as any classifier with error rate $$\frac{1}{2} - \gamma$$ for $$\gamma \in (0, \frac{1}{2})$$. In the case you're worried about, $$\gamma$$ is close to $$\frac{1}{2}$$.

Let $$J(\theta^{(i)})$$ be the error of AdaBoost after $$i$$ rounds; we can prove the following rate-of-convergence result:

$$J(\theta^{(i+1)}) \leq \sqrt{1 - 4\gamma^2} J(\theta^{(i)})$$.

This is proven by Duchi here. So if we denote $$\gamma$$ for the weak learner after round $$i$$ as $$\gamma_i$$, we can write $$J(\theta^{(T)}) \leq \prod_{t=1}^T \sqrt{1 - 4\gamma_t^2} \leq exp\left(-2 \sum_{t=1}^T \gamma_t^2\right) \leq exp\left(-2\gamma^2T\right)$$ for $$\gamma = \underset{t}{\min}\gamma_t$$. So, basically, the empirical error vanishes exponentially. Note that this occurs regardless of $$\gamma$$; it simply trades off with $$T$$, so we don't necessarily need a particular type of weak learner, just any classifier with better-than-random error rate.

Generalization Error (test)

Dealing with generalization error is a little bit past my mathematical abilities. But, using basic statistical learning theory, it's a result from Vapnik (1971) that $$\varepsilon(h) \leq \hat{\varepsilon}(h) + O\left(\frac{1}{\sqrt{m}}\sqrt{d\log\frac{m}{d} + \log\frac{1}{\delta}}\right)$$ for classifiers under the empirical risk minimization (ERM) learning framework with high probability ($$1-\delta$$). Note $$d = VC(\mathcal{H})$$, the VC-dimension of the hypothesis class of $$H$$. We can treat AdaBoost this way since it is a classifier that tries to minimize some empirical risk (i.e. training loss) on a training dataset (this is hand-wavey, but the definition of ERM isn't the point here). I believe the notes here build on these principles and show a similar bound on the generalization error of Adaboost, that is;

$$\varepsilon(h) \leq \hat{\varepsilon}(h) + O\left(\frac{1}{\sqrt{m}}\sqrt{\frac{\log m\log|\mathcal{H}|}{\theta^2} + \log\frac{1}{\delta}}\right)$$

where they treat Adaboost as a max-margin classifier with margin $$\theta$$; unfortunately, I don't think I'll be much help in elucidating this particular formula. Note, however, that there is no dependence on $$\gamma$$ here except in the first $$\hat{\varepsilon}(h)$$ term, which vanishes regardless of $$\gamma$$ as $$T \to \infty$$. So a particular type of weak learner is again unnecessary -- we just need a better-than-random learner.

• I agree. The interesting thing about AdaBoost is that it works even with weak learners, which is not a trivial fact (though I think it's less interesting a fact than I did when I first saw it) Jun 9, 2020 at 3:10
• Thanks a lot - this really cleared this up for me. Everywhere I read about AdaBoost it started out with weak-classifiers, but I wasn't sure this is an actual requirement for the algorithm. As you showed, it isn't really. I'll chew some more on the math - thanks! Jun 9, 2020 at 6:31