A stochastic approximation view of boosting

The boosting as a stochastic approximation algorithm is considered. This new interpretation provides an alternative theoretical framework for investigation. Following the results of stochastic approximation theory a stochastic approximation boosting algorithm, SABoost, is proposed. By adjusting its step sizes, SABoost will have different kinds of properties. Empirically, it is found that SABoost with a small step size will have smaller training and testing errors difference, and when the step size becomes large, it tends to overfit (i.e. bias towards training scenarios). This choice of step size can be viewed as a smooth (early) stopping rule. The performance of AdaBoost is compared and contrasted.