Following the Leader and Fast Rates in Linear Prediction: Curved Constraint Sets and Other Regularities
Following the Leader and Fast Rates in Linear Prediction: Curved Constraint Sets and Other Regularities
复制标题
追随线性预测中的领先者和快速率：曲线约束集和其他规律
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Csaba Szepesvari
中科院分区：
文献类型：
--
作者：
Ruitong Huang;Tor Lattimore;A. György;Csaba Szepesvari
FTL算法，也许是所有在线学习算法中最简单的，当它所使用的损失函数是正曲线时，它表现得很好。在本文中，我们问是否有其他的“幸运”设置，当超光速实现亚线性，“小”遗憾。特别地，我们研究了非空凸紧域上的线性预测的基本问题。在其他结果中，我们证明了域边界的曲率可以像损失是弯曲的一样起作用：在这种情况下，我们证明了只要损失向量的平均值具有远离零的正长度，FTL就享有对数增长率的遗憾，而例如，对于多面体域和随机数据，它享有有限的预期遗憾。基于先前已知的元算法，我们还得到了同时享有最坏情况保证和超光速可用边界的算法。
The follow the leader (FTL) algorithm, perhaps the simplest of all online learning algorithms, is known to perform well when the loss functions it is used on are positively curved. In this paper we ask whether there are other "lucky" settings when FTL achieves sublinear, "small" regret. In particular, we study the fundamental problem of linear prediction over a non-empty convex, compact domain. 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 a logarithmic growth rate of regret, while, e.g., for polyhedral domains and stochastic data it enjoys finite expected regret. Building on a previously known meta-algorithm, we also get an algorithm that simultaneously enjoys the worst-case guarantees and the bound available for FTL.
影响因子：
2.5
作者：
Cesa-Bianchi, N;Conconi, A;Gentile, C
通讯作者：
Gentile, C