Faster Projection-free Online Learning
This work addresses efficiency issues in online convex optimization for scenarios where projections are costly, offering a faster algorithm with theoretical guarantees.
The paper tackles the computational bottleneck of projection operations in online learning by introducing a projection-free algorithm based on Follow-the-Perturbed-Leader, achieving a regret bound of T^{2/3} for smooth cost functions, improving upon the long-standing T^{3/4} bound.
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.