Stochastic Frank-Wolfe methods for nonconvex optimization

Sashank J. Reddi, Suvrit Sra, Barnabas Poczos, Alex Smola

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

86 Scopus citations

Abstract

We study Frank-Wolfe methods for nonconvex stochastic and finite-sum optimization problems. Frank-Wolfe methods (in the convex case) have gained tremendous recent interest in machine learning and optimization due to their projection-free property and their ability to exploit structured constraints. However, our understanding of these algorithms in the nonconvex setting is fairly limited. In this paper, we propose nonconvex stochastic Frank-Wolfe methods and analyze their convergence properties. Furthermore, for objective functions that decompose into a finite-sum, we leverage ideas from variance reduction for convex optimization to obtain new variance reduced nonconvex Frank-Wolfe methods that have provably faster convergence than the classical Frank-Wolfe method.

Original languageEnglish
Title of host publication54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages1244-1251
Number of pages8
ISBN (Electronic)9781509045495
DOIs
StatePublished - 10 Feb 2017
Externally publishedYes
Event54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016 - Monticello, United States
Duration: 27 Sep 201630 Sep 2016

Publication series

Name54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016

Conference

Conference54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016
Country/TerritoryUnited States
CityMonticello
Period27/09/1630/09/16

Fingerprint

Dive into the research topics of 'Stochastic Frank-Wolfe methods for nonconvex optimization'. Together they form a unique fingerprint.

Cite this