Online Convex Optimization Using Predictions∗

Making use of predictions is a crucial, but under-explored, area of online algorithms. This paper studies a class of on-line 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 predic-tions improve as time passes. We prove that achieving sub-linear regret and constant competitive ratio for online algo-rithms requires the use of an unbounded prediction window in adversarial settings, but that under more realistic stochas-tic prediction error models it is possible to use Averaging Fixed Horizon Control (AFHC) to simultaneously achieve sublinear regret and constant competitive ratio in expecta-tion using only a constant-sized prediction window. Fur-thermore, we show that the performance of AFHC is tightly concentrated around its mean