Back to search

Georgia Institute of Technology

Compatibility, Predictions and Optimization in Large-scale Online Decision Making

Abstract

dc:description.abstract

The last few years have seen a shift in server architecture towards large-scale, dedicated data centers. The massive scale of these datacenters has highlighted important, unsolved problems in the optimization of such large-scale service systems. Many of the mathematical problems abstracted from these challenges form fundamental problems in the field of online decision making and require a combination of tools from probability, stochastic processes and online algorithms together with new insights to be solvable. This thesis broadly addresses three of these problems, as detailed below. In Chapter 2, we consider a large-scale, parallel-server system, where tasks of a particular type can only be routed to a small subset of servers. The task-server constraints are represented by a bipartite graph where vertices represent task types and servers, respectively. The analysis of these systems has historically relied heavily on mean-field analysis. However, due to the lack of exchangeability in the constrained system, mean-field techniques fundamentally break down. In this chapter, we develop a novel coupling-based approach to establish the mean-field approximation for a large class of sparse graphs, including spatial graphs. The method extends the scope of mean-field analysis far beyond the classical full-flexibility setup. In Chapter 3, we consider a large-scale, parallel-server system with an unknown arrival rate, where each server is able to adjust its processing speed. The objective is to minimize the system cost, which consists of a power cost to maintain the servers' processing speed and a quality of service cost depending on the tasks' sojourn times. We draw on ideas from stochastic approximation to design a novel speed scaling algorithm and prove that the server's processing speeds converge to the globally asymptotically optimum value. Curiously, the algorithm is fully distributed and does not require any communication between servers. A key contribution of our approach lies in demonstrating how concepts from the stochastic approximation literature can be leveraged to effectively tackle learning problems in large-scale, distributed systems. In Chapter 4, we consider learning-augmented algorithms, where the decision maker has access to a machine learning model which provides untrusted and potentially inaccurate predictions of future inputs. The goal of the decision maker is to exploit the predictions if they are accurate, while guaranteeing performance that is not much worse than the hindsight optimal sequence of decisions, even when predictions are inaccurate. We consider two applications: capacity scaling and smoothed online optimization. For both applications, we design a novel algorithm and prove a competitive ratio guarantee as a function of the predictions' accuracy. Interestingly, we identify a fundamental trade-off between the competitive ratio in the worst- and best-case, which we prove is necessary for any algorithm.

Degree

thesis:*
Level thesis:degree_level
Doctoral
Department dc:contributor.department
Industrial and Systems Engineering
Grantor dc:publisher
Georgia Institute of Technology
Year dc:date.issued
2024

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Rutten, Daan
Advisor dc:contributor.advisor
  • Mukherjee, Debankur
Committee members dc:contributor.committeemember
  • Srikant, Rayadurgam
  • Mitzenmacher, Michael
  • Ayhan, Hayriye
  • Andradottir, Sigrun

Subjects

dc:subject × 11

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/1853/75185

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Rutten, Daan. Compatibility, Predictions and Optimization in Large-scale Online Decision Making. Doctoral thesis, Georgia Institute of Technology, 2024. https://hdl.handle.net/1853/75185