Abstract

We show that the Subgradient algorithm is universal for online learning onthe simplex in the sense that it simultaneously achieves $O(\sqrt N)$ regretfor adversarial costs and $O(1)$ pseudo-regret for i.i.d costs. To the best ofour knowledge this is the first demonstration of a universal algorithm on thesimplex that is not a variant of Hedge. Since Subgradient is a popular andwidely used algorithm our results have immediate broad application.

 

Quick Read (beta)