Convergence and Consistency of Greedy Boosting Procedures

• Activity Number: 431
• Type: Invited
• Date/Time: Thursday, August 7, 2003 : 8:30 AM to 10:20 AM
• Sponsor: IMS
• Author(s): Tong Zhang*+
• Companies: IBM T.J. Watson Research Center
• Keywords: boosting ; greedy algorithm ; early stopping ; consistency

Abstract

In the greedy optimization formulation of boosting procedures, we seek to minimize a certain convex loss defined on the linear function space spanned by a (possibly infinite) set of library functions. I will discuss the convergence and consistency of greedy boosting under general loss functions based on two different points of views: 1) One norm regularization: Specifically, we show how to obtain numerical convergence rate when the optimization is constrained in the convex hull of the library functions. A consistency condition based on iid samples will be presented where the complexity is controlled by adjusting one-norm of the weights with respect to the library functions. 2) Early stopping: Present a convergence analysis when the optimization is performed on the whole linear function space. The analysis also illustrates the importance of using small step-sizes in boosting procedures. In this framework, we show that consistency can be achieved through early stopping. Part of this work was joint with Shie Mannor and Ron Meir, and part with Bin Yu.