Following the Leader and Fast Rates in Linear Prediction: Curved Constraint Sets and Other Regularities
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.
After rebuttal ================  Reviewer 5 brings up a good point about the importance of the condition on the losses in Thm 3.4. It is important that this gets sufficiently emphasized in the final version of the paper, as the authors promise in their rebuttal, because the high-level message that fast rates *only* depend on the curvature of the constraint set is too simplistic.   Original review ================     In online convex optimization, it is known that Follow-the-leader (FTL) achieves logarithmic regret for strongly convex losses, but FTL is generally considered unsuitable for linear losses, because it may then suffer linear regret. The present paper shows that, even for linear losses, FTL may be able to achieve logarithmic regret (for curved domains) or even finite regret (for polyhedral domains), provided that the average of the cost vectors stays away from 0. Technically, the results are based on Proposition 3.1, which rewrites the regret in terms of the differences between consecutive leaders, together with arguments showing that shape of the domain may cause the difference between leaders in consecutive rounds to be small. 
The results of this paper are interesting for multiple reasons: 1) FTL is widely considered the most natural algorithm, it often works well in practice, and it is the standard algorithm in batch learning, so it seems strange that the online learning literature should be so dismissive of it.  2) As mentioned by the authors, it raises the question of whether the shape of the domain can also affect the regret rates for other methods. (Although regularized methods like gradient descent do not necessarily hit the boundary of the domain on every round like FTL, in high dimensions it does not seem unlikely that the domain constraints can be active quite frequently.)  Comments:  There is something that confuses me in the proof of Theorem 3.4: at the top of page 6 a plane P is constructed that is spanned by tilde{theta}_1 and w_2 - w_1, and passes through w_1. Under the assumptions of the theorem, I believe that w_i is simply a scaling of tilde{theta}_i. So then P is also spanned by tilde{theta}_1 and tilde{theta}_2 and passes through the origin. But then P also passes through tilde{theta}_2, so why is it necessary to consider the projection of tilde{theta}_2 onto P?  I would suggest mentioning that the bound on the regret in terms of the number of leader changes in Theorem 3.11 is well-known, or at least follows easily from the be-the-leader lemma (for which you cite Lemma 2.1 of Shalev-Shwartz.)  Minor comments:  I wonder if Proposition 3.2 might extend to non-differentiable points Theta_t as well if the FTL choice w_t is suitably defined in case of ties. For instance, for the experts setting, I would guess that setting w_t to the uniform distribution on the set of leaders might do the trick. In general, the right definition might be arrived at by looking at Follow-the-Regularized leader and then letting the learning rate tend to infinity.  Could you perhaps say something about why the lower bound on ||Theta_t|| is necessary for curved domains in Theorem 3.4, but not for polyhedral domains in Theorem 3.11? I guess this lower bound comes in in Theorem 3.4 in order to control the difference between w_{t+1} and w_t, right? So then in a sense the two results are analogous after all.  Instead of requiring that Phi be differentiable in your results, I would suggest requiring that the FTL leader be unique, which seems easier to interpret.  The fonts in Figure 2 are very small, making it hard to read.