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.

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

References in corpus (5)

• Projection onto the probability simplex: An efficient algorithm with a simple proof, and an application
• An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial bandits
• An Improved Parametrization and Analysis of the EXP3++ Algorithm for Stochastic and Adversarial Bandits
• Following the Leader and Fast Rates in Linear Prediction: Curved Constraint Sets and Other Regularities
• Online convex optimization in the bandit setting: gradient descent without a gradient

Cited by in corpus (1)

• Learning The Best Expert Efficiently