Generalization Error and Algorithmic Convergence of Median Boosting

Part of Advances in Neural Information Processing Systems 17 (NIPS 2004)

Authors

Balázs Kégl

Abstract

We have recently proposed an extension of ADABOOST to regression that uses the median of the base regressors as the final regressor. In this paper we extend theoretical results obtained for ADABOOST to median boosting and to its localized variant. First, we extend recent results on ef- ficient margin maximizing to show that the algorithm can converge to the maximum achievable margin within a preset precision in a finite number of steps. Then we provide confidence-interval-type bounds on the gener- alization error.