Optimality of the Subgradient Algorithm in the Stochastic Setting

Daron Anderson, Douglas Leith

We show that the Subgradient algorithm is universal for online learning on the simplex in the sense that it simultaneously achieves $O(\sqrt{N})$ regret for adversarial costs and $O…