Is AdaBoost less or more prone to overfitting?

Question

I have read various (seemingly) contradicting statements whether or not AdaBoost (or other boosting techniques) are less or more prone to overfitting compared to other learning methods.

Are there good reasons to believe one or the other? If it depends, what does it depend on? What are the reasons that AdaBoost is less/more prone to overfitting?

Answer 1

As you say a lot has been discussed about this matter, and there's some quite heavy theory that has gone along with it that I have to admit I never fully understood. In my practical experience AdaBoost is quite robust to overfitting, and LPBoost (Linear Programming Boosting) even more so (because the objective function requires a sparse combination of weak learners, which is a form of capacity control). The main factors that influence it are:

• The "strength" of the "weak" learners: If you use very simple weak learners, such as decision stumps (1-level decision trees), then the algorithms are much less prone to overfitting. Whenever I've tried using more complicated weak learners (such as decision trees or even hyperplanes) I've found that overfitting occurs much more rapidly

• The noise level in the data: AdaBoost is particularly prone to overfitting on noisy datasets. In this setting the regularised forms (RegBoost, AdaBoostReg, LPBoost, QPBoost) are preferable

• The dimensionality of the data: We know that in general, we experience overfitting more in high dimensional spaces ("the curse of dimensionality"), and AdaBoost can also suffer in that respect, as it is simply a linear combination of classifiers which themselves suffer from the problem. Whether it is as prone as other classifiers is hard to determine.

Of course you can use heuristic methods such as validation sets or $k$-fold cross-validation to set the stopping parameter (or other parameters in the different variants) as you would for any other classifier.

Answer 2

I agree with most of the points mentioned in tdc comment. however, I have to add and correct few things.

• As shown in L2Boost by Peter Bühlmann, as the number of weak learners (rounds of boosting) increases, the bias converges exponentially fast while the variance increases by geometrically diminishing magnitudes which means: It overfits much slower than most of the other methods.
• It was wrongly mentioned in Zach comment that it is better than random forest in terms of overfit. It is completely wrong. In fact, according to theory (look at original random forest paper by Breiman), Random Forest is absolutely immune against overfitting as long as its weak classifiers don't overfit to data.
• Unlike what mentioned in tdc comment, most of boosting methods are highly sensitive to the labeling noise and may easily overfit in the presence of labeling noise.
• In datasets where Bayes error rates are far from 0 (i.e., features are not discriminative enough) boosting methods can easily overfit , as well. Because they try to reduce the training error to zero while in reality even the optimal classifier, i.e., Bayes classifier can reach to a lets say 40% error rate.
• finally, and this has not been published any where (to the best of my knowledge) there is a kind of overfitting in which the generalization error does not increase as the boosting rounds increases but it does not decreases either. It means the algorithm has stuck in a local optima. In this situation, the training error constantly decreases while the test error remains almost constant. So far, we never considered this phenomenon as an indication of overfitting but I believe it is a sign of overfitting and by using more complex weak learners, (strange!) we may in fact go against it (This last point should be considered with caution :D)