Faster Projection-free Online Learning

Elad Hazan, Edgar Minasyan
Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:1877-1893, 2020.

Abstract

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 $T^{3/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 $T^{2/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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v125-hazan20a, title = {Faster Projection-free Online Learning}, author = {Hazan, Elad and Minasyan, Edgar}, booktitle = {Proceedings of Thirty Third Conference on Learning Theory}, pages = {1877--1893}, year = {2020}, editor = {Abernethy, Jacob and Agarwal, Shivani}, volume = {125}, series = {Proceedings of Machine Learning Research}, month = {09--12 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v125/hazan20a/hazan20a.pdf}, url = {https://proceedings.mlr.press/v125/hazan20a.html}, abstract = { 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 $T^{3/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 $T^{2/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.} }
Endnote
%0 Conference Paper %T Faster Projection-free Online Learning %A Elad Hazan %A Edgar Minasyan %B Proceedings of Thirty Third Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2020 %E Jacob Abernethy %E Shivani Agarwal %F pmlr-v125-hazan20a %I PMLR %P 1877--1893 %U https://proceedings.mlr.press/v125/hazan20a.html %V 125 %X 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 $T^{3/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 $T^{2/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.
APA
Hazan, E. & Minasyan, E.. (2020). Faster Projection-free Online Learning. Proceedings of Thirty Third Conference on Learning Theory, in Proceedings of Machine Learning Research 125:1877-1893 Available from https://proceedings.mlr.press/v125/hazan20a.html.

Related Material