Improved Optimistic Mirror Descent for Sparsity and Curvature

Understand

Online Convex Optimization plays a key role in large scale machine learning.

• Early approaches to this problem were conservative, in which the main focus was protection against the worst case scenario.
• But recently several algorithms have been developed for tightening the regret bounds in easy data instances such as sparsity, predictable sequences, and curved losses.
• In this work we unify some of these existing techniques to obtain new update rules for the cases when these easy instances occur together.