  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.
