# Boosting as Frank-Wolfe

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 17 references that are in the map.
- First posted on arXiv 22 Sep 2022.

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

- [XGBoost: A Scalable Tree Boosting System](https://mlsanity.com/paper/1603.02754/) (2016)
- [On the Global Linear Convergence of Frank-Wolfe Optimization Variants](https://mlsanity.com/paper/1511.05932/) (2015)
- [Functional Frank-Wolfe Boosting for General Loss Functions](https://mlsanity.com/paper/1510.02558/) (2015)

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

- [Boosting Revisited: Benchmarking and Advancing LP-Based Ensemble Methods](https://mlsanity.com/paper/2507.18242/) (2025)
- [Online Combinatorial Linear Optimization via a Frank-Wolfe-based Metarounding Algorithm](https://mlsanity.com/paper/2310.12629/) (2023)

## Abstract (arXiv)

Some boosting algorithms, such as LPBoost, ERLPBoost, and C-ERLPBoost, aim to solve the soft margin optimization problem with the ℓ1-norm regularization. LPBoost rapidly converges to an ε-approximate solution in practice, but it is known to take Omega(m) iterations in the worst case, where m is the sample size. On the other hand, ERLPBoost and C-ERLPBoost are guaranteed to converge to an ε-approximate solution in O(frac1ε2 ln fracmnu) iterations. However, the computation per iteration is very high compared to LPBoost. To address this issue, we propose a generic boosting scheme that combines the Frank-Wolfe algorithm and any secondary algorithm and switches one to the other iteratively. We show that the scheme retains the same convergence guarantee as ERLPBoost and C-ERLPBoost. One can incorporate any secondary algorithm to improve in practice. This scheme comes from a unified view of boosting algorithms for soft margin optimization. More specifically, we show that LPBoost, ERLPBoost, and C-ERLPBoost are instances of the Frank-Wolfe algorithm. In experiments on real datasets, one of the instances of our scheme exploits the better updates of the secondary algorithm and performs comparably with LPBoost.