# Boosting for Online Convex Optimization

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 33 references that are in the map.
- First posted on arXiv 18 Feb 2021.

## Builds on (most cited first, 13 of 13)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits](https://mlsanity.com/paper/1402.0555/) (2014)
- [The Computational Power of Optimization in Online Learning](https://mlsanity.com/paper/1504.02089/) (2015)
- [Efficient Algorithms for Adversarial Contextual Learning](https://mlsanity.com/paper/1602.02454/) (2016)
- [BISTRO: An Efficient Relaxation-Based Method for Contextual Bandits](https://mlsanity.com/paper/1602.02196/) (2016)
- [Online Gradient Boosting](https://mlsanity.com/paper/1506.04820/) (2015)
- [Improved Regret Bounds for Oracle-Based Adversarial Contextual Bandits](https://mlsanity.com/paper/1606.00313/) (2016)
- [Optimal and Adaptive Algorithms for Online Boosting](https://mlsanity.com/paper/1502.02651/) (2015)
- [Online Agnostic Boosting via Regret Minimization](https://mlsanity.com/paper/2003.01150/) (2020)
- [Online Improper Learning with an Approximation Oracle](https://mlsanity.com/paper/1804.07837/) (2018)
- [Online Boosting Algorithms for Multi-label Ranking](https://mlsanity.com/paper/1710.08079/) (2017)
- [Online Multiclass Boosting](https://mlsanity.com/paper/1702.07305/) (2017)
- [Online Boosting with Bandit Feedback](https://mlsanity.com/paper/2007.11975/) (2020)

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

- [Projection-free Adaptive Regret with Membership Oracles](https://mlsanity.com/paper/2211.12638/) (2022)
- [A Boosting Approach to Reinforcement Learning](https://mlsanity.com/paper/2108.09767/) (2021)
- [Dealing with Expert Bias in Collective Decision-Making](https://mlsanity.com/paper/2106.13539/) (2021)
- [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)
- [Oracle-Efficient Online Classification with Stochastic Inputs and Adversarial Outputs](https://mlsanity.com/paper/2609.33760/) (2026)
- [Minimax-optimal and Locally-adaptive Online Nonparametric Regression](https://mlsanity.com/paper/2410.03363/) (2024)
- [Optimal Bounds for Adversarial Constrained Online Convex Optimization](https://mlsanity.com/paper/2503.13366/) (2025)
- [CLASP: An online learning algorithm for Convex Losses And Squared Penalties](https://mlsanity.com/paper/2601.16072/) (2026)
- [Defensive Boosting for Online Probabilistic Forecasting](https://mlsanity.com/paper/2608.13554/) (2026)
- [ASTRA: ADMM-Accelerated Topology Reconfiguration for Dynamic Satellite Constellations](https://mlsanity.com/paper/2609.33993/) (2026)

## Abstract (arXiv)

We consider the decision-making framework of online convex optimization with a very large number of experts. This setting is ubiquitous in contextual and reinforcement learning problems, where the size of the policy class renders enumeration and search within the policy class infeasible. Instead, we consider generalizing the methodology of online boosting. We define a weak learning algorithm as a mechanism that guarantees multiplicatively approximate regret against a base class of experts. In this access model, we give an efficient boosting algorithm that guarantees near-optimal regret against the convex hull of the base class. We consider both full and partial (a.k.a. bandit) information feedback models. We also give an analogous efficient boosting algorithm for the i.i.d. statistical setting. Our results simultaneously generalize online boosting and gradient boosting guarantees to contextual learning model, online convex optimization and bandit linear optimization settings.