AdaBoost and Forward Stagewise Regression are First-Order Convex Optimization Methods
This work provides theoretical insights into boosting methods, which are widely used in machine learning for improving model accuracy, but it is incremental as it builds on existing optimization frameworks.
The paper analyzes AdaBoost and Forward Stagewise Regression by connecting them to the Mirror Descent algorithm in convex optimization, resulting in novel computational guarantees, including convergence bounds for AdaBoost and the first precise complexity results for FS_ε.
Boosting methods are highly popular and effective supervised learning methods which combine weak learners into a single accurate model with good statistical performance. In this paper, we analyze two well-known boosting methods, AdaBoost and Incremental Forward Stagewise Regression (FS$_\varepsilon$), by establishing their precise connections to the Mirror Descent algorithm, which is a first-order method in convex optimization. As a consequence of these connections we obtain novel computational guarantees for these boosting methods. In particular, we characterize convergence bounds of AdaBoost, related to both the margin and log-exponential loss function, for any step-size sequence. Furthermore, this paper presents, for the first time, precise computational complexity results for FS$_\varepsilon$.