We study Smoothed Online Convex Optimization, a version of online convex where the learner incurs a penalty for changing her actions rounds. Given a \Ω(\√d) lower bound on the competitive ratio any online algorithm, where d is the dimension of the action space, we ask what conditions this bound can be beaten. We introduce a novel framework for this problem, Online Balanced Descent (OBD), which by iteratively projecting the previous point onto a carefully chosen set of the current cost function so as to balance the switching costs and costs. We demonstrate the generality of the OBD framework by showing, with different choices of "balance," OBD can improve upon state-of-the-art guarantees for both competitive ratio and regret, in particular, is the first algorithm to achieve a dimension-free competitive ratio, 3 +(1/\α), for locally polyhedral costs, where \α measures the"steepness" of the costs. We also prove bounds on the dynamic regret of OBD the balance is performed in the dual space that are dimension-free and that OBD has sublinear static regret.
No takes yet. Share an insight, caveat, or question.
Chen et al. (2018) studied this question.