Randomized Block Frank-Wolfe for Convergent Large-Scale Learning

Understand

Owing to their low-complexity iterations, Frank-Wolfe (FW) solvers are well suited for various large-scale learning tasks.

• When block-separable constraints are present, randomized block FW (RB-FW) has been shown to further reduce complexity by updating only a fraction of coordinate blocks per iteration.
• To circumvent the limitations of existing methods, the present work develops step sizes for RB-FW that enable a flexible selection of the number of blocks to update per iteration while ensuring convergence and feasibility of the iterates.
• To this end, convergence rates of RB-FW are established through computational bounds on a primal sub-optimality measure and on the duality gap.