Variance-reduced and projection-free stochastic optimization

Elad Hazan, Haipeng Luo

Research output: Chapter in Book/Report/Conference proceedingConference contribution

22 Scopus citations

Abstract

The Frank-Wolfe optimization algorithm has recently regained popularity for machine learning applications due to its projection-free property and its ability to handle structured constraints. However, in the stochastic learning setting, it is still relatively understudied compared to the gradient descent counterpart. In this work, leveraging a recent variance reduction technique, we propose two stochastic Frank-Wolfe variants which substantially improve previous results in terms of the number of stochastic gradient evaluations needed to achieve 1 - e accuracy. For example, we improve from O(1/ϵ) to O(ln1/ϵ) if the objective function is smooth and strongly convex, and from 0(1/ϵ2) to O(1/ϵ15) if the objective function is smooth and Lipschitz. The theoretical improvement is also observed in experiments on real-world datasets for a mulliclass classification application.

Original languageEnglish (US)
Title of host publication33rd International Conference on Machine Learning, ICML 2016
EditorsKilian Q. Weinberger, Maria Florina Balcan
PublisherInternational Machine Learning Society (IMLS)
Pages1926-1936
Number of pages11
ISBN (Electronic)9781510829008
StatePublished - Jan 1 2016
Event33rd International Conference on Machine Learning, ICML 2016 - New York City, United States
Duration: Jun 19 2016Jun 24 2016

Publication series

Name33rd International Conference on Machine Learning, ICML 2016
Volume3

Other

Other33rd International Conference on Machine Learning, ICML 2016
Country/TerritoryUnited States
CityNew York City
Period6/19/166/24/16

All Science Journal Classification (ASJC) codes

  • Artificial Intelligence
  • Software
  • Computer Networks and Communications

Fingerprint

Dive into the research topics of 'Variance-reduced and projection-free stochastic optimization'. Together they form a unique fingerprint.

Cite this