Challenges in Competitive Online Optimisation

Introduction

Online decision-making, characterized by the need to make decisions without knowledge of the future, lies at the heart of numerous applications. Despite its prevalence, our grasp of effective strategies for handling the associated uncertainty remains poor. Through the lens of the established framework of online algorithms as well as the emerging field of learning-augmented algorithms, this project aims to address central challenges in decision making under uncertainty.

Research Background

While there has been extensive research on online algorithms, many of the field's core challenges remain unresolved. However, several recent discoveries of new algorithmic design and analysis techniques have opened up novel avenues for overcoming previous obstacles.

Advancements in Machine Learning

Alongside these technical advancements, the rise of machine learning is now significantly enriching our toolset for dealing with uncertainty. This has motivated the recent emergence of the field of learning-augmented algorithms. Here, an algorithm's input is augmented with predictions, aiming for near-optimal performance if predictions are reasonably good, while still retaining classical worst-case guarantees even for highly erroneous predictions.

Project Objectives

Inspired by these recent developments, this project aims to substantially elevate our understanding of decision-making under uncertainty. The main objectives are:

1. To explore new directions around the concept of work functions.
2. To elevate the mirror descent technique into a generic tool for online algorithm design.
3. To develop universal techniques for designing learning-augmented algorithms.
4. To expand the scope of learning-augmented algorithms to new domains.

Theoretical Contributions

The project addresses questions at the forefront of theoretical computer science, building on the PI's recent success in resolving several long-standing problems, and strives for foundational contributions to the timely issue of leveraging machine-learned predictions for improved algorithm design.