Lazy Online Gradient Descent is Universal on Polytopes

Daron Anderson, Douglas Leith

We prove the familiar Lazy Online Gradient Descent algorithm is universal on polytope domains. That means it gets $O(1)$ pseudo-regret against i.i.d opponents, while simultaneously…