论文标题
更快的无投影在线学习
Faster Projection-free Online Learning
论文作者
论文摘要
在许多在线学习问题中，基于梯度的方法的计算瓶颈是投影操作。因此，在许多问题中，最有效的算法基于Frank-Wolfe方法，该方法通过线性优化代替了预测。但是，在一般情况下，与基于投影的方法相比，在线无投影方法需要更多的迭代：最知名的后悔界限为$ t^{3/4} $。尽管在弗兰克·沃尔夫（Frank-Wolfe）方法的各种变体上进行了重大研究，但这种界限一直保持不变十年。在本文中，我们给出了一种有效的无投影算法，该算法保证了$ t^{2/3} $遗憾的一般在线凸优化，并具有平稳的成本功能和每次迭代的一项线性优化计算。与以前的Frank-Wolfe方法相比，我们的算法是使用下面扰动领导者方法得出的，并使用在线原始二元框架进行分析。
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.
