Heavy Ball Momentum for Conditional Gradient

Bingcong Li; Alireza Sadeghi; Georgios B. Giannakis

Heavy Ball Momentum for Conditional Gradient

Bingcong Li, Alireza Sadeghi, Georgios B. Giannakis

Electrical and Computer Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

1 Scopus citations

Abstract

Conditional gradient, aka Frank Wolfe (FW) algorithms, have well-documented merits in machine learning and signal processing applications. Unlike projection-based methods, momentum cannot improve the convergence rate of FW, in general. This limitation motivates the present work, which deals with heavy ball momentum, and its impact to FW. Specifically, it is established that heavy ball offers a unifying perspective on the primal-dual (PD) convergence, and enjoys a tighter per iteration PD error rate, for multiple choices of step sizes, where PD error can serve as the stopping criterion in practice. In addition, it is asserted that restart, a scheme typically employed jointly with Nesterov’s momentum, can further tighten this PD error bound. Numerical results demonstrate the usefulness of heavy ball momentum in FW iterations.

Original language	English (US)
Title of host publication	Advances in Neural Information Processing Systems 34 - 35th Conference on Neural Information Processing Systems, NeurIPS 2021
Editors	Marc'Aurelio Ranzato, Alina Beygelzimer, Yann Dauphin, Percy S. Liang, Jenn Wortman Vaughan
Publisher	Neural information processing systems foundation
Pages	21244-21255
Number of pages	12
ISBN (Electronic)	9781713845393
State	Published - 2021
Event	35th Conference on Neural Information Processing Systems, NeurIPS 2021 - Virtual, Online Duration: Dec 6 2021 → Dec 14 2021

Publication series

Name	Advances in Neural Information Processing Systems
Volume	26
ISSN (Print)	1049-5258

Conference

Conference	35th Conference on Neural Information Processing Systems, NeurIPS 2021
City	Virtual, Online
Period	12/6/21 → 12/14/21

Bibliographical note

Funding Information:
This work is supported by NSF grants 1901134, 2126052, and 2128593. The authors would also like to thank the anonymous reviewers for their feedback.

Publisher Copyright:
© 2021 Neural information processing systems foundation. All rights reserved.

OpenUrl availability

Full text

Cite this

Li, B., Sadeghi, A., & Giannakis, G. B. (2021). Heavy Ball Momentum for Conditional Gradient. In MA. Ranzato, A. Beygelzimer, Y. Dauphin, P. S. Liang, & J. Wortman Vaughan (Eds.), Advances in Neural Information Processing Systems 34 - 35th Conference on Neural Information Processing Systems, NeurIPS 2021 (pp. 21244-21255). (Advances in Neural Information Processing Systems; Vol. 26). Neural information processing systems foundation.

Heavy Ball Momentum for Conditional Gradient. / Li, Bingcong; Sadeghi, Alireza; Giannakis, Georgios B.
Advances in Neural Information Processing Systems 34 - 35th Conference on Neural Information Processing Systems, NeurIPS 2021. ed. / Marc'Aurelio Ranzato; Alina Beygelzimer; Yann Dauphin; Percy S. Liang; Jenn Wortman Vaughan. Neural information processing systems foundation, 2021. p. 21244-21255 (Advances in Neural Information Processing Systems; Vol. 26).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Li, B, Sadeghi, A & Giannakis, GB 2021, Heavy Ball Momentum for Conditional Gradient. in MA Ranzato, A Beygelzimer, Y Dauphin, PS Liang & J Wortman Vaughan (eds), Advances in Neural Information Processing Systems 34 - 35th Conference on Neural Information Processing Systems, NeurIPS 2021. Advances in Neural Information Processing Systems, vol. 26, Neural information processing systems foundation, pp. 21244-21255, 35th Conference on Neural Information Processing Systems, NeurIPS 2021, Virtual, Online, 12/6/21.

Li B, Sadeghi A, Giannakis GB. Heavy Ball Momentum for Conditional Gradient. In Ranzato MA, Beygelzimer A, Dauphin Y, Liang PS, Wortman Vaughan J, editors, Advances in Neural Information Processing Systems 34 - 35th Conference on Neural Information Processing Systems, NeurIPS 2021. Neural information processing systems foundation. 2021. p. 21244-21255. (Advances in Neural Information Processing Systems).

Li, Bingcong ; Sadeghi, Alireza ; Giannakis, Georgios B. / Heavy Ball Momentum for Conditional Gradient. Advances in Neural Information Processing Systems 34 - 35th Conference on Neural Information Processing Systems, NeurIPS 2021. editor / Marc'Aurelio Ranzato ; Alina Beygelzimer ; Yann Dauphin ; Percy S. Liang ; Jenn Wortman Vaughan. Neural information processing systems foundation, 2021. pp. 21244-21255 (Advances in Neural Information Processing Systems).

@inproceedings{5a4605a49f144c2d97825b021f0affa0,

title = "Heavy Ball Momentum for Conditional Gradient",

abstract = "Conditional gradient, aka Frank Wolfe (FW) algorithms, have well-documented merits in machine learning and signal processing applications. Unlike projection-based methods, momentum cannot improve the convergence rate of FW, in general. This limitation motivates the present work, which deals with heavy ball momentum, and its impact to FW. Specifically, it is established that heavy ball offers a unifying perspective on the primal-dual (PD) convergence, and enjoys a tighter per iteration PD error rate, for multiple choices of step sizes, where PD error can serve as the stopping criterion in practice. In addition, it is asserted that restart, a scheme typically employed jointly with Nesterov{\textquoteright}s momentum, can further tighten this PD error bound. Numerical results demonstrate the usefulness of heavy ball momentum in FW iterations.",

author = "Bingcong Li and Alireza Sadeghi and Giannakis, {Georgios B.}",

note = "Funding Information: This work is supported by NSF grants 1901134, 2126052, and 2128593. The authors would also like to thank the anonymous reviewers for their feedback. Publisher Copyright: {\textcopyright} 2021 Neural information processing systems foundation. All rights reserved.; 35th Conference on Neural Information Processing Systems, NeurIPS 2021 ; Conference date: 06-12-2021 Through 14-12-2021",

year = "2021",

language = "English (US)",

series = "Advances in Neural Information Processing Systems",

publisher = "Neural information processing systems foundation",

pages = "21244--21255",

editor = "Marc'Aurelio Ranzato and Alina Beygelzimer and Yann Dauphin and Liang, {Percy S.} and {Wortman Vaughan}, Jenn",

booktitle = "Advances in Neural Information Processing Systems 34 - 35th Conference on Neural Information Processing Systems, NeurIPS 2021",

}

TY - GEN

T1 - Heavy Ball Momentum for Conditional Gradient

AU - Li, Bingcong

AU - Sadeghi, Alireza

AU - Giannakis, Georgios B.

N1 - Funding Information: This work is supported by NSF grants 1901134, 2126052, and 2128593. The authors would also like to thank the anonymous reviewers for their feedback. Publisher Copyright: © 2021 Neural information processing systems foundation. All rights reserved.

PY - 2021

Y1 - 2021

N2 - Conditional gradient, aka Frank Wolfe (FW) algorithms, have well-documented merits in machine learning and signal processing applications. Unlike projection-based methods, momentum cannot improve the convergence rate of FW, in general. This limitation motivates the present work, which deals with heavy ball momentum, and its impact to FW. Specifically, it is established that heavy ball offers a unifying perspective on the primal-dual (PD) convergence, and enjoys a tighter per iteration PD error rate, for multiple choices of step sizes, where PD error can serve as the stopping criterion in practice. In addition, it is asserted that restart, a scheme typically employed jointly with Nesterov’s momentum, can further tighten this PD error bound. Numerical results demonstrate the usefulness of heavy ball momentum in FW iterations.

AB - Conditional gradient, aka Frank Wolfe (FW) algorithms, have well-documented merits in machine learning and signal processing applications. Unlike projection-based methods, momentum cannot improve the convergence rate of FW, in general. This limitation motivates the present work, which deals with heavy ball momentum, and its impact to FW. Specifically, it is established that heavy ball offers a unifying perspective on the primal-dual (PD) convergence, and enjoys a tighter per iteration PD error rate, for multiple choices of step sizes, where PD error can serve as the stopping criterion in practice. In addition, it is asserted that restart, a scheme typically employed jointly with Nesterov’s momentum, can further tighten this PD error bound. Numerical results demonstrate the usefulness of heavy ball momentum in FW iterations.

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

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

M3 - Conference contribution

AN - SCOPUS:85125025601

T3 - Advances in Neural Information Processing Systems

SP - 21244

EP - 21255

BT - Advances in Neural Information Processing Systems 34 - 35th Conference on Neural Information Processing Systems, NeurIPS 2021

A2 - Ranzato, Marc'Aurelio

A2 - Beygelzimer, Alina

A2 - Dauphin, Yann

A2 - Liang, Percy S.

A2 - Wortman Vaughan, Jenn

PB - Neural information processing systems foundation

T2 - 35th Conference on Neural Information Processing Systems, NeurIPS 2021

Y2 - 6 December 2021 through 14 December 2021

ER -

Heavy Ball Momentum for Conditional Gradient

Abstract

Publication series

Conference

Bibliographical note

OpenUrl availability

Other files and links

Fingerprint

Cite this