A PARTAN-Accelerated Frank-Wolfe Algorithm for Large-Scale SVM Classification

The Frank-Wolfe algorithm (hereafter FW) is a classical method for convex optimization that has seen a substantial revival in interest from researchers [1, 2, 3]. Recent results have shown that the family of FW algorithms enjoys powerful theoretical properties such as iteration complexity bounds that are independent of the problem size, provable primal-dual convergence rates, and sparsity guarantees that hold during the whole execution of the algorithm [4, 2]. Furthermore, several variants of the basic procedure exist which can improve the convergence rate and practical performance of the basic FW iteration [5, 6, 7, 8]. Finally, the fact that FW methods work with projection-free iterations is an essential advantage in applications such as matrix recovery, where a projection step (as needed, e.g., by proximal methods) has a super-linear complexity [2, 9]. As a result, FW is now considered a suitable choice for large-scale optimization 1 problems arising in several contexts such as Machine Learning, statistics, bioinformatics and other fields [10, 11, 12].