Following the Leader and Fast Rates in Online Linear Prediction: Curved Constraint Sets and Other Regularities
Following the Leader and Fast Rates in Online Linear Prediction: Curved Constraint Sets and Other Regularities
复制标题
追随在线线性预测的领先者和快速率：曲线约束集和其他规律
DOI：
--
复制
发表时间：
2017
影响因子：
6
通讯作者：
Csaba Szepesvari
中科院分区：
文献类型：
--
作者：
Ruitong Huang;Tor Lattimore;A. György;Csaba Szepesvari
遵循领导者（FTL）是一种简单的在线学习算法，当损失功能是凸的，并且在本文中呈现良好的态度，我们询问当FTL尤其是较低的遗憾时，我们是否还有其他设置。在凸面上，与非空内部的紧凑型域的线性预测的基本问题。弯曲：在这种情况下，我们证明，只要损失向量的含义远离零，FTL就会享受对数遗憾，而对于Polytope域和随机数据，它也会享受预期的遗憾。通过在集合的强凸与其边界的最小曲率之间建立同等性，从而强烈凸出以前已知的元算法，我们还获得了一种算法，当数据“容易”时，我们就可以享受最差的保证和较小的FTL遗憾。当约束集是椭球时，正则化领导者算法或通过基于收缩的FTL变体）。
Follow the leader (FTL) is a simple online learning algorithm that is known to perform well when the loss functions are convex and positively curved. In this paper we ask whether there are other settings when FTL achieves low regret. In particular, we study the fundamental problem of linear prediction over a convex, compact domain with non-empty interior. Amongst other results, we prove that the curvature of the boundary of the domain can act as if the losses were curved: In this case, we prove that as long as the mean of the loss vectors have positive lengths bounded away from zero, FTL enjoys logarithmic regret, while for polytope domains and stochastic data it enjoys finite expected regret. The former result is also extended to strongly convex domains by establishing an equivalence between the strong convexity of sets and the minimum curvature of their boundary, which may be of independent interest. Building on a previously known meta-algorithm, we also get an algorithm that simultaneously enjoys the worst-case guarantees and the smaller regret of FTL when the data is ‘easy’. Finally, we show that such guarantees are achievable directly (e.g., by the follow the regularized leader algorithm or by a shrinkage-based variant of FTL) when the constraint set is an ellipsoid.