Algorithms with Predictions

Summary of the project

Algorithms that operate in a state of uncertainty occupy a central place within the design and analysis of algorithms. While traditional approaches are based on analysis under complete lack of information, algorithms with predictions seek to leverage some inherently inaccurate information in regards to the missing parts of the input. Here, the objective is to design algorithms that are robust to prediction errors, and at the same time perform well if the prediction is relatively accurate. Previous work under this very recent framework has focused, almost exclusively, on: predictions that are single-type, deterministic, and often provided by very powerful oracles; techniques that are based predominantly on worst-case competitive analysis; and online problems, in which the input is revealed as a sequence of items.

In this project, we will substantially strengthen and expand the foundations of the nascent, and fast-growing area of algorithms with predictions, by addressing all aspects of algorithm development: modeling, design, framework of theoretical analysis, and performance evaluation. Specifically, we put forward three main objectives. The first is the advancement of new models that better capture the structure and semantics of algorithms with predictions, but are also amenable to theoretical analysis. This will help us bridge the large gap between some fundamentally different models, as well as study algorithms in more realistic, yet largely understudied settings such as distributional and multiple predictions. Our second objective is to pursue new analysis techniques, that better reflect the power and limitations of algorithms with predictions. This will allow us to obtain a more nuanced evaluation beyond ``worst-case'' considerations, provide a better understanding of the impact of the prediction error on the performance of the algorithms, and leverage unexplored techniques based on continuous optimization. Our third objective is to introduce and exploit the concepts of predictions in settings that go beyond online computation, namely in distributed computation and parallelism, in streaming and approximation (offline) algorithms, as well as in algorithmic aspects of search games. This will help us apply mathematical tools and expertise to fields in which predictions can be beneficial, but where very little previous work (or none at all) has addressed such connections. Our end objective is to capture, and efficiently analyze, realistic settings that often occur in practical domains, in the context of well-known problems and applications.