CaltechAUTHORS
  A Caltech Library Service

Using Predictions in Online Optimization: Looking Forward with an Eye on the Past

Chen, Niangjun and Comden, Joshua and Liu, Zhenhua and Gandhi, Anshul and Wierman, Adam (2016) Using Predictions in Online Optimization: Looking Forward with an Eye on the Past. In: SIGMETRICS '16 Proceedings of the 2016 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Science. ACM , New York, NY, pp. 193-206. ISBN 978-1-4503-4266-7. http://resolver.caltech.edu/CaltechAUTHORS:20170110-153001767

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20170110-153001767

Abstract

We consider online convex optimization (OCO) problems with switching costs and noisy predictions. While the design of online algorithms for OCO problems has received considerable attention, the design of algorithms in the context of noisy predictions is largely open. To this point, two promising algorithms have been proposed: Receding Horizon Control (RHC) and Averaging Fixed Horizon Control (AFHC). The comparison of these policies is largely open. AFHC has been shown to provide better worst-case performance, while RHC outperforms AFHC in many realistic settings. In this paper, we introduce a new class of policies, Committed Horizon Control (CHC), that generalizes both RHC and AFHC. We provide average-case analysis and concentration results for CHC policies, yielding the first analysis of RHC for OCO problems with noisy predictions. Further, we provide explicit results characterizing the optimal CHC policy as a function of properties of the prediction noise, e.g., variance and correlation structure. Our results provide a characterization of when AFHC outperforms RHC and vice versa, as well as when other CHC policies outperform both RHC and AFHC.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1145/2896377.2901464DOIArticle
http://dl.acm.org/citation.cfm?doid=2896377.2901464PublisherArticle
ORCID:
AuthorORCID
Chen, Niangjun0000-0002-2289-9737
Additional Information:© 2016 ACM. This work is partially supported by the NSF through CNS-1464388, CNS-1464151, CNS-1319820, NETS-1518941 and an A*STAR NSS (PhD) scholarship.
Funders:
Funding AgencyGrant Number
NSFCNS-1464388
NSFCNS-1464151
NSFCNS-1319820
NSFNETS-1518941
Agency for Science, Technology and Research (A*STAR)UNSPECIFIED
Record Number:CaltechAUTHORS:20170110-153001767
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20170110-153001767
Official Citation:Niangjun Chen, Joshua Comden, Zhenhua Liu, Anshul Gandhi, and Adam Wierman. 2016. Using Predictions in Online Optimization: Looking Forward with an Eye on the Past. In Proceedings of the 2016 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Science (SIGMETRICS '16). ACM, New York, NY, USA, 193-206. DOI: http://dx.doi.org/10.1145/2896377.2901464
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:73399
Collection:CaltechAUTHORS
Deposited By: Kristin Buxton
Deposited On:11 Jan 2017 03:15
Last Modified:27 Oct 2017 18:23

Repository Staff Only: item control page