Lazy Online Gradient Descent is Universal on Polytopes
This provides a simpler and more broadly applicable algorithm for online optimization on polytopes, benefiting researchers and practitioners in machine learning and optimization.
The paper proves that Lazy Online Gradient Descent achieves O(1) pseudo-regret against i.i.d. opponents and O(sqrt(N)) worst-case regret on polytope domains, addressing computational inefficiencies in existing methods like Hedge that require lifting and assume unique optimizers.
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 achieving the well-known $O(\sqrt N)$ worst-case regret bound. For comparison the bulk of the literature focuses on variants of the Hedge (exponential weights) algorithm on the simplex. These can in principle be lifted to general polytopes; however the process is computationally unfeasible for many important classes where the number of vertices grows quickly with the dimension. The lifting procedure also ignores any Euclidean bounds on the cost vectors, and can create extra factors of dimension in the pseudo-regret bound. Gradient Descent is simpler than the handful of purpose-built algorithms for polytopes in the literature, and works in a broader setting. In particular existing algorithms assume the optimiser is unique, while our bound allows for several optimal vertices.