2022/09/22 by Ryotaro Mitsuboshi, Mitsuboshi, Ryotaro, Kohei Hatano +3 · 1 citation
Computer Science · Engineering · #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning and Algorithms #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2209.10831
openalex publication_date 2022/09/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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)/(ε2) ln \fracmν) 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.