论文标题
对强烈凸集的无投影在线学习
Projection-free Online Learning over Strongly Convex Sets
论文作者
论文摘要
为了有效地通过复杂的约束解决在线问题，包括在线Frank-Wolfe（OFW）在内的无预测算法及其变体最近引起了重大兴趣。但是，在一般情况下，现有的有效预测算法仅实现了$ O（t^{3/4}）$的遗憾，这比基于投射的算法的遗憾要差，其中$ t $是决策回合的数量。在本文中，我们研究了在线学习的特殊情况，即强烈的凸集集，为此我们首先证明OFW可以享受$ O（t^{2/3}）$的更好的遗憾，以实现一般凸损失。关键的想法是通过简单的行搜索规则来完善原始OFW中的衰减阶梯大小。此外，对于强烈凸出的损失，我们通过重新定义OFW中的替代损失函数来提出强烈的OFW变体。我们表明，它在常规凸组上实现了$ O（t^{2/3}）$的遗憾，并且在强凸集的情况下以$ o（\ sqrt {t}）$的更好遗憾绑定。
To efficiently solve online problems with complicated constraints, projection-free algorithms including online frank-wolfe (OFW) and its variants have received significant interest recently. However, in the general case, existing efficient projection-free algorithms only achieved the regret bound of $O(T^{3/4})$, which is worse than the regret of projection-based algorithms, where $T$ is the number of decision rounds. In this paper, we study the special case of online learning over strongly convex sets, for which we first prove that OFW can enjoy a better regret bound of $O(T^{2/3})$ for general convex losses. The key idea is to refine the decaying step-size in the original OFW by a simple line search rule. Furthermore, for strongly convex losses, we propose a strongly convex variant of OFW by redefining the surrogate loss function in OFW. We show that it achieves a regret bound of $O(T^{2/3})$ over general convex sets and a better regret bound of $O(\sqrt{T})$ over strongly convex sets.
