A Momentum-Guided Frank-Wolfe Algorithm

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

doi:10.1109/TSP.2021.3087910

A Momentum-Guided Frank-Wolfe Algorithm

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

Electrical and Computer Engineering

Research output: Contribution to journal › Article › peer-review

17 Scopus citations

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 (US)
Article number	9457128
Pages (from-to)	3597-3611
Number of pages	15
Journal	IEEE Transactions on Signal Processing
Volume	69
DOIs	https://doi.org/10.1109/TSP.2021.3087910
State	Published - 2021

Bibliographical note

Funding Information:
Manuscript received October 2, 2020; revised April 20, 2021; accepted May 31, 2021. Date of publication June 16, 2021; date of current version June 30, 2021. The associate editor coordinating the review of this manuscript and approving it for publication was Dr. Augusto Aubry. This work was supported by the US National Science Foundation under Grant 19001134, and the European ASPIRE project (project 14926 within the STW OTP programme), and in part by the Netherlands Organization for Scientific Research (NWO). The work of Mario Coutino was supported in part by CONACYT. (Corresponding author: Georgios B. Giannakis.) Bingcong Li and Georgios B. Giannakis are with the Department of Electrical and Computer Engineering and the Digital Technology Center, University of Minnesota, Minneapolis, MN 55455 USA (e-mail: [email protected]; [email protected]).

Publisher Copyright:
© 1991-2012 IEEE.

Keywords

Frank Wolfe method
accelerated method
conditional gradient method
momentum
smooth convex optimization

Publisher link

10.1109/TSP.2021.3087910

Find It

Find It at U of M Libraries

Cite this

@article{5ce02c0b61b144e7aec06181c636934a,

title = "A Momentum-Guided Frank-Wolfe Algorithm",

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.",

keywords = "Frank Wolfe method, accelerated method, conditional gradient method, momentum, smooth convex optimization",

author = "Bingcong Li and Mario Coutino and {B. Giannakis}, Georgios and Geert Leus",

note = "Funding Information: Manuscript received October 2, 2020; revised April 20, 2021; accepted May 31, 2021. Date of publication June 16, 2021; date of current version June 30, 2021. The associate editor coordinating the review of this manuscript and approving it for publication was Dr. Augusto Aubry. This work was supported by the US National Science Foundation under Grant 19001134, and the European ASPIRE project (project 14926 within the STW OTP programme), and in part by the Netherlands Organization for Scientific Research (NWO). The work of Mario Coutino was supported in part by CONACYT. (Corresponding author: Georgios B. Giannakis.) Bingcong Li and Georgios B. Giannakis are with the Department of Electrical and Computer Engineering and the Digital Technology Center, University of Minnesota, Minneapolis, MN 55455 USA (e-mail: [email protected]; [email protected]). Publisher Copyright: {\textcopyright} 1991-2012 IEEE.",

year = "2021",

doi = "10.1109/TSP.2021.3087910",

language = "English (US)",

volume = "69",

pages = "3597--3611",

journal = "IEEE Transactions on Signal Processing",

issn = "1053-587X",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

}

TY - JOUR

T1 - A Momentum-Guided Frank-Wolfe Algorithm

AU - Li, Bingcong

AU - Coutino, Mario

AU - B. Giannakis, Georgios

AU - Leus, Geert

N1 - Funding Information: Manuscript received October 2, 2020; revised April 20, 2021; accepted May 31, 2021. Date of publication June 16, 2021; date of current version June 30, 2021. The associate editor coordinating the review of this manuscript and approving it for publication was Dr. Augusto Aubry. This work was supported by the US National Science Foundation under Grant 19001134, and the European ASPIRE project (project 14926 within the STW OTP programme), and in part by the Netherlands Organization for Scientific Research (NWO). The work of Mario Coutino was supported in part by CONACYT. (Corresponding author: Georgios B. Giannakis.) Bingcong Li and Georgios B. Giannakis are with the Department of Electrical and Computer Engineering and the Digital Technology Center, University of Minnesota, Minneapolis, MN 55455 USA (e-mail: [email protected]; [email protected]). Publisher Copyright: © 1991-2012 IEEE.

PY - 2021

Y1 - 2021

N2 - 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.

AB - 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.

KW - Frank Wolfe method

KW - accelerated method

KW - conditional gradient method

KW - momentum

KW - smooth convex optimization

UR - http://www.scopus.com/inward/record.url?scp=85112201195&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85112201195&partnerID=8YFLogxK

U2 - 10.1109/TSP.2021.3087910

DO - 10.1109/TSP.2021.3087910

M3 - Article

AN - SCOPUS:85112201195

SN - 1053-587X

VL - 69

SP - 3597

EP - 3611

JO - IEEE Transactions on Signal Processing

JF - IEEE Transactions on Signal Processing

M1 - 9457128

ER -

A Momentum-Guided Frank-Wolfe Algorithm

Abstract

Bibliographical note

Keywords

Publisher link

Find It

Other files and links

Fingerprint

Cite this