The Role of Flexibility in Structure Based Acceleration for Online Convex Optimization
Online convex optimization (OCO) has seen much success for its ability to handle decisionmaking in dynamic, uncertain, or even adversarial environments. We examine the implications of introducing flexibility to OCO framework via three simple modifications to its standard assumptions: we introduce two new concepts of weighted regret and online saddle point problems and study the possibility of making lookahead decisions. We adapt two commonly used offline first order convex optimization algorithms, namely Mirror Descent and Mirror Prox, to an online setting and demonstrate how these new flexibilities are instrumental in exploiting structural properties of functions which results in improved convergence rates. In particular, relaxing the usual OCO assumption of uniform weights (anticipatory decisions) allows us to utilize algorithms that can significantly speed up the convergence and go beyond the established lower bounds on regret for strongly convex (smooth) loss functions.