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 convex and 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 polytope 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.

研究了在线学习算法中的 Follow the Leader (FTL) 算法，证明在一定条件下即使未必为凸损失函数时，其仍可以表现出与曲率相似的性能，同时可以在保证最坏情况下得到良好的结果。