---
title: "Optimal and Adaptive Algorithms for Online Boosting"
authors:
  - "Alina Beygelzimer"
  - "Satyen Kale"
  - "Haipeng Luo"
doi: ""
url: "https://ijcai.org/proceedings/2016/614"
pdf: "https://ijcai.org/proceedings/2016/0614.pdf"
venue: "Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence"
year: 2016
pages: "4120-4123"
track: ""
keywords:
---

# Optimal and Adaptive Algorithms for Online Boosting

Alina Beygelzimer, Satyen Kale, Haipeng Luo

*Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence*, pages 4120-4123.

## 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.