Boosting as Frank-Wolfe

09/22/2022
by   Ryotaro Mitsuboshi, et al.
0

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 Ω(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(1/ϵ^2lnm/ν) 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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset