A Caltech Library Service

Online Algorithms: From Prediction to Decision


Chen, Niangjun (2018) Online Algorithms: From Prediction to Decision. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/Z95M63W4.


Making use of predictions is a crucial, but under-explored, area of sequential decision problems with limited information. While in practice most online algorithms rely on predictions to make real time decisions, in theory their performance is only analyzed in simplified models of prediction noise, either adversarial or i.i.d. The goal of this thesis is to bridge this divide between theory and practice: to study online algorithm under more practical predictions models, gain better understanding about the value of prediction, and design online algorithms that make the best use of predictions.

This thesis makes three main contributions. First, 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. Using this general prediction model, we prove that Averaging Fixed Horizon Control (AFHC) can simultaneously achieve sublinear regret and constant competitive ratio in expectation using only a constant- sized prediction window, overcoming the hardnesss results in adversarial prediction models. Second, to understand the optimal use of noisy prediction, we introduce a new class of policies, Committed Horizon Control (CHC), that generalizes both popular policies Receding Horizon Control (RHC) and Averaging Fixed Horizon Control (AFHC). Our results provide explicit results characterizing the optimal use of prediction in CHC policy as a function of properties of the prediction noise, e.g., variance and correlation structure. Third, we apply the general prediction model and algorithm design framework to the deferrable load control problem in power systems. Our proposed model predictive algorithm provides significant reduction in variance of total load in the power system. Throughout this thesis, we provide both average-case analysis and concentration results for our proposed online algorithms, highlighting that the typical performance is tightly concentrated around the average-case performance.

Item Type:Thesis (Dissertation (Ph.D.))
Subject Keywords:Online algorithms; predictions; convex optimization
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Computer Science
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • Wierman, Adam C. (advisor)
  • Low, Steven H. (co-advisor)
Thesis Committee:
  • Wierman, Adam C. (chair)
  • Low, Steven H.
  • Chandrasekaran, Venkat
  • Yue, Yisong
Defense Date:27 September 2017
Non-Caltech Author Email:niangjun (AT)
Funding AgencyGrant Number
Agency for Science, Technology and Research (Singapore)UNSPECIFIED
Record Number:CaltechTHESIS:10182017-210853845
Persistent URL:
Related URLs:
URLURL TypeDescription adapted for Chapter 2 and 3. adapted for Chapter 4. adapted for Chapter 5. adapted for Chapter 5.
Chen, Niangjun0000-0002-2289-9737
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:10530
Deposited By: Niangjun Chen
Deposited On:23 Oct 2017 22:55
Last Modified:04 Oct 2019 00:18

Thesis Files

PDF (Complete Thesis) - Final Version
See Usage Policy.


Repository Staff Only: item control page