Faster Projection-free Online Learning

Elad Hazan, Edgar Minasyan

Research output: Contribution to journalConference articlepeer-review

24 Scopus citations


In many online learning problems the computational bottleneck for gradient-based methods is the projection operation. For this reason, in many problems the most efficient algorithms are based on the Frank-Wolfe method, which replaces projections by linear optimization. In the general case, however, online projection-free methods require more iterations than projection-based methods: the best known regret bound scales as T3/4. Despite significant work on various variants of the Frank-Wolfe method, this bound has remained unchanged for a decade. In this paper we give an efficient projection-free algorithm that guarantees T2/3 regret for general online convex optimization with smooth cost functions and one linear optimization computation per iteration. As opposed to previous Frank-Wolfe approaches, our algorithm is derived using the Follow-the-Perturbed-Leader method and is analyzed using an online primal-dual framework.

Original languageEnglish (US)
Pages (from-to)1877-1893
Number of pages17
JournalProceedings of Machine Learning Research
StatePublished - 2020
Event33rd Conference on Learning Theory, COLT 2020 - Virtual, Online, Austria
Duration: Jul 9 2020Jul 12 2020

All Science Journal Classification (ASJC) codes

  • Artificial Intelligence
  • Software
  • Control and Systems Engineering
  • Statistics and Probability


  • Follow-the-Perturbed-Leader
  • Frank-Wolfe method
  • Online optimization


Dive into the research topics of 'Faster Projection-free Online Learning'. Together they form a unique fingerprint.

Cite this