Title: Compatibility, Predictions and Optimization in Large-scale Online Decision Making
Date: January 9th, 2024
Time: 3pm - 5pm ET
Location: Groseclose 403 or https://gatech.zoom.us/j/5237023057?pwd=dFpET0IzcEFURmdlUjZFNzErUTJ4QT09
Daan Rutten
Operations Research Ph.D. Student
H. Milton Stewart School of Industrial and Systems Engineering
Georgia Institute of Technology
Committee
Dr. Debankur Mukherjee, Industrial and Systems Engineering, Georgia Institute of Technology (advisor)
Dr. Rayadurgam Srikant, Electrical & Computer Engineering, University of Illinois Urbana-Champaign
Dr. Michael Mitzenmacher, Engineering and Applied Sciences, Harvard University
Dr. Hayriye Ayhan, Industrial and Systems Engineering, Georgia Institute of Technology
Dr. Sigrun Andradottir, Industrial and Systems Engineering, Georgia Institute of Technology
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.