Using Predictions in Online Optimization with Switching Costs: A Fast Algorithm and A Fundamental Limit

Abstract

This paper studies an online optimization problem with switching costs and a finite prediction window. We propose a computationally efficient algorithm, Receding Horizon Gradient Descent (RHGD), which only requires a finite number of gradient evaluations at each time. We show that both the dynamic regret and the competitive ratio of the algorithm decay exponentially fast with the length of the prediction window. Moreover, we provide a fundamental lower bound on dynamic regret for general online algorithms with a finite prediction window, and show that the dynamic regret of any online algorithm, even with more computation, decays at most exponentially when increasing prediction window size. This demonstrates that limited prediction information, instead of limited computational power, is the key constraint to performance in online decision making. Lastly, we present simulation results to test our algorithm numerically.