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.