A Momentum-Guided Frank-Wolfe Algorithm

Bingcong Li, Mario Coutino, Georgios B. Giannakis, Geert Leus

Research output: Contribution to journalArticleScientificpeer-review

Abstract

With the well-documented popularity of Frank Wolfe (FW) algorithms in machine learning tasks, the present paper establishes links between FW subproblems and the notion of momentum emerging in accelerated gradient methods (AGMs). On the one hand, these links reveal why momentum is unlikely to be effective for FW-type algorithms on general problems. On the other hand, it is established that momentum accelerates FW on a class of signal processing and machine learning applications. Specifically, it is proved that a momentum variant of FW, here termed accelerated Frank Wolfe (AFW), converges with a faster rate ${\cal O}(\frac{1}{k^2})$ on such a family of problems, despite the same ${\cal O}(\frac{1}{k})$ rate of FW on general cases. Distinct from existing fast convergent FW variants, the faster rates here rely on parameter-free step sizes. Numerical experiments on benchmarked machine learning tasks corroborate the theoretical findings.
Original language English 9457128 3597-3611 15 IEEE Transactions on Signal Processing 69 https://doi.org/10.1109/TSP.2021.3087910 Published - 2021

Keywords

• Frank Wolfe method