Online Convex Optimization Using Predictions
- 15 June 2015
- conference paper
- conference paper
- Published by Association for Computing Machinery (ACM)
- Vol. 43 (1), 191-204
- https://doi.org/10.1145/2745844.2745854
Abstract
Making use of predictions is a crucial, but under-explored, area of online algorithms. This paper studies a class of online optimization problems where we have external noisy predictions available. We propose a stochastic prediction error model that generalizes prior models in the learning and stochastic control communities, incorporates correlation among prediction errors, and captures the fact that predictions improve as time passes. We prove that achieving sublinear regret and constant competitive ratio for online algorithms requires the use of an unbounded prediction window in adversarial settings, but that under more realistic stochastic prediction error models it is possible to use Averaging Fixed Horizon Control (AFHC) to simultaneously achieve sublinear regret and constant competitive ratio in expectation using only a constant-sized prediction window. Furthermore, we show that the performance of AFHC is tightly concentrated around its mean.Keywords
Funding Information
- National Science Foundation (CNS- 1319820 EPAS-1307794 CNS-0846025 CCF-1101470)
- Australian Research Council (DP130101378)
This publication has 39 references indexed in Scilit:
- Balance your bids before your bitsPublished by Association for Computing Machinery (ACM) ,2014
- Performance Bounds and Suboptimal Policies for Multi-Period InvestmentFoundations and Trends® in Optimization, 2014
- A tale of two metricsPublished by Association for Computing Machinery (ACM) ,2013
- Energy Efficient Geographical Load Balancing via Dynamic Deferral of WorkloadPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2012
- Robust and flexible power-proportional storagePublished by Association for Computing Machinery (ACM) ,2010
- Concentration InequalitiesLecture Notes in Computer Science, 2004
- Robust model predictive control: A surveyPublished by Springer Science and Business Media LLC ,1998
- Web server workload characterizationPublished by Association for Computing Machinery (ACM) ,1996
- An optimal on-line algorithm for metrical task systemJournal of the ACM, 1992
- A decomposition theorem and bounds for randomized server problemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1992