Variance-reduced and projection-free stochastic optimization

Elad Hazan, Haipeng Luo

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

17 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
CountryUnited 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

    Hazan, E., & Luo, H. (2016). Variance-reduced and projection-free stochastic optimization. In K. Q. Weinberger, & M. F. Balcan (Eds.), 33rd International Conference on Machine Learning, ICML 2016 (pp. 1926-1936). (33rd International Conference on Machine Learning, ICML 2016; Vol. 3). International Machine Learning Society (IMLS).