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
![]() |
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: |
| ||||||||
ORCID: |
| ||||||||
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