CaltechAUTHORS
  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) https://resolver.caltech.edu/CaltechAUTHORS:20190627-130339504

[img] PDF - Submitted Version
See Usage Policy.

429kB

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20190627-130339504

Abstract

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
http://arxiv.org/abs/1803.10366arXivDiscussion Paper
ORCID:
AuthorORCID
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:https://resolver.caltech.edu/CaltechAUTHORS:20190627-130339504
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:96789
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:27 Jun 2019 20:36
Last Modified:23 Dec 2022 18:29

Repository Staff Only: item control page