CaltechTHESIS
  A Caltech Library Service

Optimizing Cloud AI Platforms: Resource Allocation and Market Design

Citation

Su, Yu (2021) Optimizing Cloud AI Platforms: Resource Allocation and Market Design. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/bc2t-er54. https://resolver.caltech.edu/CaltechTHESIS:06072021-172842077

Abstract

The numerous applications of data-driven algorithms and tools across diverse industries have led to tremendous successes in recent years. As the volume of massive data that is created, collected, and consumed continues to grow, there are many new imposed challenges faced by today's cloud AI platforms that support the deployment of machine learning algorithms on a large scale. In this thesis, we tackle the emerging challenges within cloud AI systems and beyond by adopting approaches from the fields of resource allocation and market design.

First, we propose a new scheduler, Generalized Earliest Time First (GETF), and provide the provable, worst-case approximation guarantees for the goals of minimizing both makespan and total weighted completion time of tasks with precedence constraints on related machines with machine-dependent communication times. These two results address long-standing open problems. Further, we adopt the classic speed scaling function to model power consumption and use mean response time to measure the performance. We propose the concept of pseudo-size to quantify importance of tasks and design a family of two-stage scheduling frameworks based on the approximation of pseudo-size. Assuming a good approximation of pseudo-size, we are able to provide the first provable bound of a linear combination of performance and energy goals under this setting.

Second, we study the design of mechanisms for data acquisition in settings with information leakage and verifiable data. We provide the first characterization of an optimal mechanism for data acquisition if agents are concerned about privacy and their data is correlated with each other. Additionally, the mechanism allows, for the first time, a trade-off between the bias and variance of the estimator. Transitioning from the data market into the energy market, we propose a new pricing scheme, which is applicable to general non-convex costs, and allows using general parametric pricing functions. Optimizing for the quantities and the price parameters simultaneously, and the ability to use general parametric pricing functions allows our scheme to find prices that are typically economically more efficient and less discriminatory than those of the existing schemes while still supporting a competitive equilibrium. In addition, we supplement the proposed method with a computationally efficient polynomial-time approximation algorithm, which can be used to approximate the optimal quantities and prices for general non-convex cost functions.

Item Type:Thesis (Dissertation (Ph.D.))
Subject Keywords:Cloud AI Systems, Resource Allocation, Market Design
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Computing and Mathematical Sciences
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • Wierman, Adam C.
Thesis Committee:
  • Yue, Yisong (chair)
  • Low, Steven H.
  • Perona, Pietro
  • Wierman, Adam C.
Defense Date:25 May 2021
Record Number:CaltechTHESIS:06072021-172842077
Persistent URL:https://resolver.caltech.edu/CaltechTHESIS:06072021-172842077
DOI:10.7907/bc2t-er54
Related URLs:
URLURL TypeDescription
https://doi.org/10.1145/3374888.3374897DOIAdapted into Chapter 2 of this thesis.
https://arxiv.org/abs/2004.14639arXivAdapted into Chapter 2 of this thesis.
https://arxiv.org/abs/2105.14262arXivAdapted into Chapter 4 of this thesis.
https://doi.org/10.1287/opre.2019.1900DOIAdapted into Chapter 5 of this thesis.
ORCID:
AuthorORCID
Su, Yu0000-0002-7159-4542
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:14254
Collection:CaltechTHESIS
Deposited By: Yu Su
Deposited On:08 Jun 2021 15:44
Last Modified:17 Jun 2021 20:54

Thesis Files

[img] PDF - Final Version
See Usage Policy.

1MB

Repository Staff Only: item control page