An Online Boosting Algorithm with Theoretical Justifications
This work addresses the theoretical gap in online boosting for machine learning practitioners, though it appears incremental as it builds on existing offline methods.
The authors tackled the problem of online boosting by proposing a novel algorithm with theoretical guarantees, adapting from the SmoothBoost algorithm and using online convex programming to determine the number of weak learners, and experiments showed it compares favorably with existing methods.
We study the task of online boosting--combining online weak learners into an online strong learner. While batch boosting has a sound theoretical foundation, online boosting deserves more study from the theoretical perspective. In this paper, we carefully compare the differences between online and batch boosting, and propose a novel and reasonable assumption for the online weak learner. Based on the assumption, we design an online boosting algorithm with a strong theoretical guarantee by adapting from the offline SmoothBoost algorithm that matches the assumption closely. We further tackle the task of deciding the number of weak learners using established theoretical results for online convex programming and predicting with expert advice. Experiments on real-world data sets demonstrate that the proposed algorithm compares favorably with existing online boosting algorithms.