Optimal and Adaptive Algorithms for Online Boosting
  We study online boosting, the task of converting any weak online learner into
a strong online learner. Based on a novel and natural definition of weak online
learnability, we develop two online boosting algorithms. The first algorithm is
an online version of boost-by-majority. By proving a matching lower bound, we
show that this algorithm is essentially optimal in terms of the number of weak
learners and the sample complexity needed to achieve a specified accuracy. This
optimal algorithm is not adaptive however. Using tools from online loss
minimization, we derive an adaptive online boosting algorithm that is also
parameter-free, but not optimal. Both algorithms work with base learners that
can handle example importance weights directly, as well as by rejection
sampling examples with probability defined by the booster. Results are
complemented with an extensive experimental study.
