CaltechTHESIS
  A Caltech Library Service

Online Algorithms: From Prediction to Decision

Citation

Chen, Niangjun (2018) Online Algorithms: From Prediction to Decision. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/Z95M63W4. https://resolver.caltech.edu/CaltechTHESIS:10182017-210853845

Abstract

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) gmail.com
Funders:
Funding AgencyGrant Number
Agency for Science, Technology and Research (Singapore)UNSPECIFIED
Record Number:CaltechTHESIS:10182017-210853845
Persistent URL:https://resolver.caltech.edu/CaltechTHESIS:10182017-210853845
DOI:10.7907/Z95M63W4
Related URLs:
URLURL TypeDescription
http://doi.acm.org/10.1145/2745844.2745854DOIArticle adapted for Chapter 2 and 3.
http://doi.acm.org/10.1145/2896377.2901464DOIArticle adapted for Chapter 4.
http://doi.acm.org/10.1145/2487166.2487179DOIArticle adapted for Chapter 5.
http://ieeexplore.ieee.org/document/7040398/PublisherArticle adapted for Chapter 5.
ORCID:
AuthorORCID
Chen, Niangjun0000-0002-2289-9737
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:10530
Collection:CaltechTHESIS
Deposited By: Niangjun Chen
Deposited On:23 Oct 2017 22:55
Last Modified:04 Oct 2019 00:18

Thesis Files

[img]
Preview
PDF (Complete Thesis) - Final Version
See Usage Policy.

1MB

Repository Staff Only: item control page