Using Predictions in Online Optimization
- 14 June 2016
- conference paper
- conference paper
- Published by Association for Computing Machinery (ACM)
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.Keywords
Funding Information
- National Science Foundation (CNS-1319820, NETS-1518941, CNS-1464151, CNS-1464388,)
This publication has 42 references indexed in Scilit:
- Online Learning and Online Convex OptimizationFoundations and Trends® in Machine Learning, 2011
- Server farms with setup costsPerformance Evaluation, 2010
- Power and performance management of virtualized computing environments via lookahead controlCluster Computing, 2008
- Logarithmic regret algorithms for online convex optimizationMachine Learning, 2007
- Constrained model predictive control: Stability and optimalityAutomatica, 2000
- Robust model predictive control: A surveyPublished by Springer Science and Business Media LLC ,1998
- Multi-armed bandits with switching penaltiesIEEE Transactions on Automatic Control, 1996
- Model predictive control: Theory and practice—A surveyAutomatica, 1989
- A modified quadratic cost problem and feedback stabilization of a linear systemIEEE Transactions on Automatic Control, 1977
- A New Approach to Linear Filtering and Prediction ProblemsJournal of Basic Engineering, 1960