Optimality of the Subgradient Algorithm in the Stochastic Setting

Abstract

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(1)$ pseudo-regret for i.i.d costs. To the best of our knowledge this is the first demonstration of a universal algorithm on the simplex that is not a variant of Hedge. Since Subgradient is a popular and widely used algorithm our results have immediate broad application.

6 figures, Corrected off-by-one errors coming from proof in Appendix A. Replaced with newer Version April 2020