Boosting as Frank-Wolfe

arXiv2209.10831MaRDI QIDQ6411557

Author name not available (Why is that?)

Publication date: 22 September 2022

Abstract: Some boosting algorithms, such as LPBoost, ERLPBoost, and C-ERLPBoost, aim to solve the soft margin optimization problem with the $el{l}_1$-norm regularization. LPBoost rapidly converges to an $epsilon$-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 $epsilon$-approximate solution in $O(frac1epsilo{n}^{2}lnfracmu)$ 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.

Has companion code repository: https://github.com/rmitsuboshi/boosting_as_frank_wolfe

This page was built for publication: Boosting as Frank-Wolfe

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6411557)