# Optimal and Adaptive Algorithms for Online Boosting

arXiv: https://arxiv.org/abs/1502.02651 · HTML: https://mlsanity.com/paper/1502.02651/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Feb 2015.

## Built on by (most cited first, 12 of 12)

- [A Boosting Approach to Reinforcement Learning](https://mlsanity.com/paper/2108.09767/) (2021)
- [The sample complexity of multi-distribution learning](https://mlsanity.com/paper/2312.04027/) (2023)
- [Boosting for Online Convex Optimization](https://mlsanity.com/paper/2102.09305/) (2021)
- [Efficient Methods for Online Multiclass Logistic Regression](https://mlsanity.com/paper/2110.03020/) (2021)
- [Efficient Swap Multicalibration of Elicitable Properties](https://mlsanity.com/paper/2511.04907/) (2025)
- [Online Agnostic Multiclass Boosting](https://mlsanity.com/paper/2205.15113/) (2022)
- [Trading-Off Payments and Accuracy in Online Classification with Paid Stochastic Experts](https://mlsanity.com/paper/2307.00836/) (2023)
- [Sample-Efficient Agnostic Boosting](https://mlsanity.com/paper/2410.23632/) (2024)
- [Sample-Optimal Agnostic Boosting with Unlabeled Data](https://mlsanity.com/paper/2503.04706/) (2025)
- [Online Gradient Boosting Decision Tree: In-Place Updates for Efficient Adding/Deleting Data](https://mlsanity.com/paper/2502.01634/) (2025)
- [Defensive Boosting for Online Probabilistic Forecasting](https://mlsanity.com/paper/2608.13554/) (2026)
- [Audit the Scaffold, Not the Checkpoint: A Stationarity Dichotomy for Recursive Self-Improvement in Agentic Coding](https://mlsanity.com/paper/2609.34924/) (2026)

## Abstract (arXiv)

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.