## Following the Leader and Fast Rates in Online Linear Prediction: Curved Constraint Sets and Other Regularities

*Ruitong Huang, Tor Lattimore, András György, Csaba Szepesvári*; 18(145):1−31, 2017.

### Abstract

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.

[abs][pdf][bib]