论文标题
利用可行集合的曲率，以更快地预测在线学习
Exploiting the Curvature of Feasible Sets for Faster Projection-Free Online Learning
论文作者
论文摘要
在本文中，我们为在线凸优化（OCO）开发了新的无预测算法。在线梯度下降（OGD）是经典OCO算法的一个示例，该算法保证了最佳$ o（\ sqrt {t}）$遗憾。但是，OGD和其他基于投影的OCO算法需要在可行的集合上执行欧几里得投影$ \ Mathcal {C} \ subset \ Mathbb {r}^d $，每当他们的迭代台上$ \ Mathcal {c} $时。对于各种兴趣集，此投影步骤可以在计算上是昂贵的，尤其是当环境维度很大时。这促使开发无投影的OCO算法，这些算法将欧几里得预测换成通常便宜的操作，例如线性优化（LO）。但是，最新的基于LO的算法仅实现次优$ o（T^{3/4}）$对General OCO的遗憾。在本文中，我们利用了无参数的在线学习的最新结果，并开发了一种OCO算法，该算法每回合向Loacle进行两个呼叫，并实现近乎最佳的$ \ widetilde {o} {o}（\ sqrt {t} $）$ horeve y时，每当可行的设置强烈地固定时，我们还提出了一种通用凸组集的算法，该算法使$ \ widetilde o（d）$每回合的通话数量预期的电话数量，并保证$ \ widetilde o（t^{2/3}）$遗憾，改善了先前的最佳$ o（t^{3/4}）$。我们通过强烈的凸面来近似于任何凸的$ \ mathcal {c} $来实现后者，在其中可以使用$ \ widetilde {o}（d）$ $ \ mathcal {c} $的loacle呼叫数量来执行lo。
In this paper, we develop new efficient projection-free algorithms for Online Convex Optimization (OCO). Online Gradient Descent (OGD) is an example of a classical OCO algorithm that guarantees the optimal $O(\sqrt{T})$ regret bound. However, OGD and other projection-based OCO algorithms need to perform a Euclidean projection onto the feasible set $\mathcal{C}\subset \mathbb{R}^d$ whenever their iterates step outside $\mathcal{C}$. For various sets of interests, this projection step can be computationally costly, especially when the ambient dimension is large. This has motivated the development of projection-free OCO algorithms that swap Euclidean projections for often much cheaper operations such as Linear Optimization (LO). However, state-of-the-art LO-based algorithms only achieve a suboptimal $O(T^{3/4})$ regret for general OCO. In this paper, we leverage recent results in parameter-free Online Learning, and develop an OCO algorithm that makes two calls to an LO Oracle per round and achieves the near-optimal $\widetilde{O}(\sqrt{T})$ regret whenever the feasible set is strongly convex. We also present an algorithm for general convex sets that makes $\widetilde O(d)$ expected number of calls to an LO Oracle per round and guarantees a $\widetilde O(T^{2/3})$ regret, improving on the previous best $O(T^{3/4})$. We achieve the latter by approximating any convex set $\mathcal{C}$ by a strongly convex one, where LO can be performed using $\widetilde {O}(d)$ expected number of calls to an LO Oracle for $\mathcal{C}$.
