A Caltech Library Service

Smoothed Online Convex Optimization in High Dimensions via Online Balanced Descent

Chen, Niangjun and Goel, Gautam and Wierman, Adam (2018) Smoothed Online Convex Optimization in High Dimensions via Online Balanced Descent. . (Unpublished)

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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

Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription Paper
Chen, Niangjun0000-0002-2289-9737
Goel, Gautam0000-0002-7054-7218
Wierman, Adam0000-0002-5923-0199
Additional Information:© 2018 N. Chen, G. Goel & A. Wierman. Niangjun Chen and Gautam Goel contributed equally to this work.
Record Number:CaltechAUTHORS:20190627-130339504
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:96789
Deposited By: Tony Diaz
Deposited On:27 Jun 2019 20:36
Last Modified:23 Dec 2022 18:29

Repository Staff Only: item control page