Optimal and Adaptive Algorithms for Online Boosting

@InProceedings{pmlr-v37-beygelzimer15,
  title = 	 {Optimal and Adaptive Algorithms for Online Boosting},
  author = 	 {Beygelzimer, Alina and Kale, Satyen and Luo, Haipeng},
  booktitle = 	 {Proceedings of the 32nd International Conference on Machine Learning},
  pages = 	 {2323--2331},
  year = 	 {2015},
  editor = 	 {Bach, Francis and Blei, David},
  volume = 	 {37},
  series = 	 {Proceedings of Machine Learning Research},
  address = 	 {Lille, France},
  month = 	 {07--09 Jul},
  publisher =    {PMLR},
  pdf = 	 {http://proceedings.mlr.press/v37/beygelzimer15.pdf},
  url = 	 {https://proceedings.mlr.press/v37/beygelzimer15.html},
  abstract = 	 {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. The second algorithm is adaptive and parameter-free, albeit not optimal.}
}